Sparql查詢的轉換系統和方法

2023-09-22 02:31:30 2

專利名稱：Sparql查詢的轉換系統和方法
技術領域：
本發明涉及資料庫查詢，尤其涉及資料庫查詢語句的執行效率，更具體地說，涉及 一種用於SPARQL查詢的轉換的系統和方法。
背景技術：
近年來，關係資料庫管理系統的成功引入了大量橫向模式的數據。隨著各種應用 中對本體(ontology)越來越多的使用，在現有關係資料庫管理系統上支持RDF (Resource Description Framework的縮寫，資源描述框架)查詢已吸引了關係資料庫研究人員和語 義網研究人員兩方面的注意。一方面，將關係數據表達為RDF圖使得可以對不同資源進行 統一的訪問，以利於信息的聯合和集中。另一方面，暴露關係資料庫中鎖存的大量數據可以 豐富語義網的內容。圖1示出了虛擬RDF存儲的結構框圖。在客戶端，使用SPARQL(Simple Protocol and RDF Query Language的縮寫，簡單協議和RDF查詢語言)進行查詢，查詢引擎利用 D2R(Database to Relationaldatabase)映射單元將SPARQL語句翻譯為SQL i吾句，以對關 係數據庫進行查詢。SPARQL 是 W3C (World Wide Web Consortium 的縮寫，全球資訊網聯盟)的 RDF 查詢語 言推薦標準，它是為RDF開發的一種查詢語言和數據獲取協議，其語法單元結構有以下幾 種三元組，(以下簡稱為<s p o 「與」模式:「或」模式UNI0N過濾條件Filter (條件)典型地，語義查詢可以分為兩類，肯定的語義查詢和否定的語義查詢。例如，為了 在超市中找到顏色(color)為白色(white)的尿布(diaper)，可以進行如下簡單的肯定的 SPARQL 查詢< ？ x typeof diaperX ？ x color white〉如果是為了在超市中找到非白色的尿布，則本應進行如下查詢 ！ (1)其中「 ！ 」表示邏輯「非」，符號「 ！ 」只是一個示例，本領域技術人員應認識到，任何 可以表達「非」邏輯的表示方式都是可以的。但是，現有SPARQL語言中的語法模式都是以 肯定形式表達的，沒有「！ 」這樣的語法結構，即不支持否定模式的直接查詢，因此不支持式(1) 中的「！〈？ x color white〉」。又例如，希望找到這樣的兩種產品，他們可以通過第三種產品捆綁銷售，但是不能 直接捆綁銷售，並且不能自己和自己捆綁銷售。假如某超市中商品捆綁銷售的情況如下(以「_」標識捆綁銷售)
(a)啤酒-尿布，尿布-牛奶；(b)啤酒-紅酒，紅酒-水，啤酒-水。假若按下面的式(2)進行查詢Select ？ X，？ z where {！〈？ x BundleSale ？ z> ！〈？ x BundleSale ？ x>} (2)則查詢結果將為(a)，因為啤酒和牛奶不捆綁銷售，啤酒自己和牛奶自己也不捆綁 銷售，但是它們通過尿布捆綁銷售。由上可見，例如「！ 」這樣的顯式否定模式的查詢非常有用。但是，現有 SPARQL語言中卻不存在顯式否定模式的語法結構。為此，現有技術中，在SPARQL語言中以肯定的方式來間接描述否定模式，抽象為 代數關係式即為P1 ！ P2 = P1-P1P2，「P1P2」代表兩個以「與」邏輯組合的三元組，將其稱 為隱式否定模式。例如，為了表達式(1)中的查詢，可以使用這樣的形式Select ？ x where {Filter ( ？ x ！ = ？ y)}又例如，為了表達式(2)中的查詢，可以使用這樣的形式Select ？ X，？ z where {〈？ m BundleSale ？ o>〈？ a BundleSale ？ b>Filter (( ？ x ！ = m OR z ！ = n)0R( ？ x ！ = a OR z ！ = c))}但是，在將上述隱式否定模式編譯為SQL語句的實際運算過程中，不等條件「？ x ！ = y」會產生很多不必要的連接操作，而連接操作空間成本很高。其次，「！=」運算 翻譯成SQL語句後將會很繁瑣。最後，不等條件會轉換為若干肯定斷言和否定斷言的組合， 增加運算量。總之，現有的SPARQL查詢難以支持全語義查詢，並且現有的將SPARQL轉換為 SQL的系統和方法性能不理想。

發明內容
因此，本發明的主要目的是提供一種能夠高效地將SPARQL查詢語句轉換為SQL語 句的系統和方法。根據本發明的一個方面，提供了一種用於SPARQL查詢的轉換的系統，包括語法/ 詞法分析器，用於解析SPARQL查詢；隱式否定模式檢測器，用於檢測解析後的SPARQL查詢 中的隱式否定模式；隱式否定模式轉換器，用於將檢測出的隱式否定模式轉換為顯式否定 模式；分離器，用於將顯式否定模式和解析後的SPARQL查詢中的肯定模式分離；否定模式 轉換器，用於將所述顯式否定模式轉換為否定部分的SQL語句；肯定模式轉換器，用於將所 述肯定模式轉換為肯定部分的SQL語句；以及組合器，用於組合所述否定部分的SQL語句和 所述肯定部分的SQL語句。根據本發明的另一方面，提供了一種用於SPARQL查詢的轉換的方法，包括以下步 驟語法/詞法分析，解析SPARQL查詢；隱式否定模式檢測，檢測解析後的SPARQL查詢中 的隱式否定模式；隱式否定模式轉換，將檢測出的隱式否定模式轉換為顯式否定模式；將 顯式否定模式和解析後的SPARQL查詢中的肯定模式分離；否定模式轉換，將所述顯式否定模式轉換為否定部分的SQL語句；肯定模式轉換，將所述肯定模式轉換為肯定部分的SQL語 句；以及組合所述否定部分的SQL語句和所述肯定部分的SQL語句。根據本發明的另一方面，提供了一種用於SPARQL查詢的轉換的系統，包括語法/ 詞法分析器，用於解析SPARQL查詢；隱式否定模式檢測器，用於檢測解析後的SPARQL查詢 中的隱式否定模式，並輸出檢測出的隱式否定模式和肯定模式；隱式否定模式轉換器，用於 將檢測出的隱式否定模式轉換為否定部分的SQL語句；肯定模式轉換器，用於將所述肯定 模式轉換為肯定部分的SQL語句；以及組合器，用於組合所述否定部分的SQL語句和所述肯 定部分的SQL語句。根據本發明的另一方面，提供了一種用於SPARQL查詢的轉換的方法，包括以下步 驟語法/詞法分析，解析SPARQL查詢；隱式否定模式檢測，檢測SPARQL查詢中的隱式否 定模式，並輸出檢測出的隱式否定模式和肯定模式；隱式否定模式轉換，將檢測出的隱式否 定模式轉換為否定部分的SQL語句；肯定模式轉換，將所述肯定模式轉換為肯定部分的SQL 語句；以及組合所述否定部分的SQL語句和所述肯定部分的SQL語句。


為了更加清楚地理解本發明及其優點，現在結合附圖進行具體描述。附圖中相似 的參考標號代表相似的部件或特徵。在附圖中圖1是示出本發明的應用環境的框圖；圖2是示出根據本發明的一個實施例的SPARQL查詢的轉換系統框圖；圖3是示出隱式否定模式的實例的視圖；圖4是示出根據本發明一個實施例的否定模式轉換器的工作流程圖；圖5是示出根據本發明的實施例，組合器基於左外連接(LEFTOUTER JOIN)命令進 行的組合處理的示意圖；圖6是示出根據本發明的實施例，組合器基於EXIST命令進行的組合處理的示意 圖；圖7是示出根據本發明的另一個實施例的SPARQL查詢的轉換系統框圖；以及圖8是示出根據本發明的實施例，從SPARQL查詢語句中提取出的連通子圖及各自 的最大連通相似子圖的示意圖。
具體實施例方式以下將參考附圖具體描述本發明的示例性實施例。本發明旨在對SPARQL查詢到SQL查詢的轉換過程進行改進。為了清楚地說明該 改進，引入一種顯式否定模式的表達，在將一個SPARQL語句轉換為SQL語句的過程中，首先 將SPARQL語句中的隱式否定模式轉換為顯式否定模式，從而優化轉換過程和所得到的SQL 語句。在一個實施例中，將顯式否定模式表示為！ ，即在普通的三元組前加上一 個表示否定意義的符號「！ 」。！ 表示不存在的實例。根據封閉世界假定， 有！ = 。當然，本領域技術人員可以意識到，其他表示方式也是可行的。在定義了顯式否定模式之後，SPARQL中的任何現有的否定模式都可以使用顯式否
7定模式表達三元組的否定！ 「與」模式的否定！ UNI0N ！ 「或」模式的否定！ ！ 三元組的雙重否定圖2示出根據本發明的一個實施例的支持SPARQL查詢的轉換的系統框圖。如圖 2所示，該系統由三大部分組成語法/詞法分析器21、隱式否定模式適配器22、以及全語 義SPARQL適配器23。以下結合圖2描述根據本發明一個實施例的系統如何將一個帶有隱 式否定模式的SPARQL查詢語句高效地轉換為SQL語句。首先，SPARQL查詢語句(下文亦稱「SPARQL語句，，或「SPARQL查詢」)進入語法 /詞法分析器21，語法/詞法分析器21解析該SPARQL語句。作為一種標準的查詢語言， SPARQL的查詢語句的解析過程在本領域中是公知的，因此不再贅述。解析後的SPARQL語句進入隱式否定模式適配器22，隱式否定模式適配器用於檢 測所述解析後的SPARQL語句中的隱式否定模式並將其轉換為顯式否定模式。其中，隱式否 定模式適配器22包括隱式否定模式檢測器221和隱式否定模式轉換器222。在隱式否定模式檢測器221，檢測解析後的SPARQL語句中的隱式否定模式，如果 該解析後的SPARQL語句具有隱式否定模式，則將其傳遞到隱式否定模式轉換器222，否則 直接輸出到下一級。以下詳細描述隱式否定模式檢測器221如何檢測解析後的SPARQL語句中的隱式 否定模式。圖3中示出了隱式否定模式的一個實例。可以總結出，隱式否定模式具有以下四 個特徵。第一，具有與肯定模式重複的三元組，這些三元組與肯定模式的三元組的不同之 處僅在於相應的變量不同，例如，在圖3中，〈？ y typeofdiaper>是肯定模式三元組< ？ x typeof diaper〉的重複，不同之處僅在於與肯定模式三元組中的變量x相應的變量y不 同；第二，所述不同的相應變量還存在於一個附加三元組中，例如，在圖3中，變量y還 存在於三元組< ？ y color white)中；第三，在過濾條件表達式中，肯定模式與隱式否定模式中所述相應的變量存在不 等關係「！=」，例如，在圖3中，過濾條件表達式為「？ x! = y」；第四，如果存在多個隱式否定模式，則含有不等關係「！=，，的過濾條件表達式以 「或(OR)」模式連接。隱式否定模式檢測器221根據以上所述的四個特徵檢測隱式否定模式，即，當一 個SPARQL查詢同時具備以上四個特徵時，認為該SPARQL查詢具有隱式否定模式。所屬技 術領域的技術人員應當知道，可以有各種方式檢測上述四個特徵。按照本發明的一個實施例，隱式否定模式檢測器221可通過對輸入的SPARQL查詢 進行如下處理，以檢測以上四個特徵。首先，將SPARQL查詢中的過濾條件範化為析取範式。析取範式是指由有限個簡單 合取式構成的析取式。設Ai(i = 1，2，...，s)為簡單合取式，則A = A1 V A2 V ... V As
8為析取範式，例如，
p，則由Al，A2，A3構造的析取 範式為
。這種範化為本領域技術人員 已知的；然後，從過濾條件中提取具有成立不等關係「 ！=」的兩個相應的不同變量(以下 稱為不等變量對)的條件；提取該SPARQL查詢中由三元組代表的連通子圖，並且根據不等變量對和連通子 圖匹配出最大連通相似子圖，比較最大連通相似子圖與原連通子圖以找出二者之間的差 異，該差異代表了隱式否定模式中的附加三元組，該附加三元組與最大連通相似子圖所代 表的三元組構成了隱式否定模式。我們仍以上文提到的SPARQL查詢為例Select ？ X，？ z where {〈？ m BundleSale ？ o>〈？ a BundleSale ？ b>Filter (( ？ x ！ = m OR z ！ = n)0R( ？ x ！ = a OR z ！ = c))}由該查詢中提取出的由三元組構成的三個連通子圖如圖8中左側所示。根據不 等變量對(x，m), (x，a), (z, n)和(z，c)，在該三個連通子圖中匹配出各自的最大連通相 似子圖，如圖8中間所示。比較圖8左側的連通子圖和中間的最大連通相似子圖，尋找出 二者之間的差異，如圖8中右側所示。該差異分別代表了〈？ m BundleSale ？ n>和〈？ aBundleSale ？ a>這兩個附加三元組。這兩個附加三元組合併各自的最大連通相似子圖所 代表的三元組，得到檢測出的兩個隱式否定模式〈？ m BundleSale ？ o> 和〈？ a BundleSale ？ b>。可選地，可根據不等變量對的數量和連通子圖的數量確定尋找最大連通相似子圖 的順序，以減少計算量。當連通子圖數量較大時，對於不等條件列表中的每個變量對驗證連 通子圖中的相似子圖；當不等變量對的數量較大時，對於每個連通子圖中的各個子圖驗證 不等變量對。當隱式否定模式檢測器221檢測出隱式否定模式時，該具有隱式否定模式的解析 後的SPARQL語句被送入隱式否定模式轉換器222。隱式否定模式轉換器222通過以下處理 將隱式否定模式轉換為顯式否定模式。首先，去除隱式否定模式中與肯定模式重複的三元組，以圖3所示的隱式否定模 式「〈？ y typeof diaperX ？ y color white〉」為例，移除其中的重複三元組「〈？ y typeof diaper〉」之後，剩下附加三元組「〈？ ycolor white〉」。然後，將附加三元組中的 變量y替換為肯定模式〈？ xcolor white〉」中的相應變量x，附加三元組「〈？ y color white〉」被轉換為「〈？ x color white〉」。最後，在轉換後的附加三元組前面加上否定標 志「！ 」，使其成為顯式否定模式「！ ！ Filter (條 件)」，可將「〈？ x p y>」輸入到肯定模式轉換器233，而將「！ Filter (條 件)」輸入到否定模式轉換器232。或者，作為替代地，也可以將「〈？ x p ？ y>Filter(條 件)」輸入到肯定模式轉換器233，而將「！ 」輸入到否定模式轉換器232。兩 種方案對於最後的轉換結果來說是等效的。我們在此假設採用第一種方案。否定模式轉換器232用於將輸入的解析後的SPARQL語句中的否定模式轉換為待 組合的否定部分的SQL語句。圖4示出否定模式轉換器的工作流程圖。以下參考圖4中的流程對否定模式轉換器232中的處理進行具體描述。首先，在步驟401，搜索要轉換的SPARQL匹配單元mu。該匹配單元mu具有比如「 ！ Filter (條件)」的形式。在步驟402，建立一個新的SELECT語句，在SQL中，SELECT語句包括WHERE、 SELECT、FROM三個子句。在步驟403，生成WHERE子句。通過將匹配單元mu中的各個條件進行「與(AND)，， 操作來生成WHERE子句中的條件。在步驟404，生成SELECT子句。具體來說，將匹配單元mu中的變量放入SELECT子 句中。在步驟405，生成FROM子句。具體來說，將匹配單元mu中的表格名稱提取出來放 入FROM子句。直到步驟405，我們已得到如下的否定部分的SQL語句N_st Select Tl. Coll, Tl. Col2 FROM qTable T1WHERE 條件 1AND 條件 2AND......條件 N其中，Tl是謂語為q的查詢所對應的表格的名稱，查詢變量位於T1的列Tl. Coll 和 Tl. Col2 中。在步驟406，對變量映射表N-map進行維護，變量映射表N-map是這樣的表，在該表 中，否定模式查詢中的變量與查詢表格中的列一一對應。例如，表1是變量映射表的一個實 例，其中，變量x和y分別與表T1中的列Col 1和Col2對應
10 表1在步驟407，判斷是否還存在其他待轉換的匹配單元，如果否，則結束整個流程，如 果是，則返回步驟401。肯定模式轉換器233將SPARQL語句中的肯定模式三元組轉換為SQL語句。例如， 將SPARQL中的「〈？ x p ？ y>」轉換為以下肯定部分的SQL語句P_st Select T2. Coll, T2.Col2 FROM pTable T1並且維護如表2所示的變量映射表P-map 表2由於現有SPARQL語言中存在肯定模式，所以這種轉換的實現方式在本領域是公 知的，在此不再詳細描述。隨後，將否定模式轉換器232輸出的否定部分的SQL語句N-st和否定部分的變量 映射表N-map和肯定模式轉換器233輸出的肯定部分的SQL語句P_st和肯定部分的變量映 射表P-map輸入到組合器234。組合器234將N_st和P_st組合為最終的SQL語句R_st。在進行組合時，由於SQL語法的多樣性，組合器234可以選擇不同的方式將否定部 分的SQL語句N-st和肯定部分的SQL語句P-st組合成完整的SQL語句。具體來說，存在 三種方案基於NOT IN命令的方案、基於NOT EXIST命令的方案以及基於LEFT 0UTERJ0IN 命令的方案。經本發明的發明人研究發現，基於NOT IN命令的方案並非在所有情況下都適用。 只有當待轉換的SPARQL語句中的多個變量之間存在依賴關係時，其才能被轉換為含有NOT IN命令的SQL語句。而基於NOT EXIST命令的方案和基於LEFT OUTER JOIN命令的方案二 者都可以將任意一個SPARQL語句轉換為SQL語句，而無論待轉換的SPARQL語句中的變量 是否存在依賴關係。因此，本發明將重點描述後兩種方案。基於左外連接命令的SQL查詢語句的一般格式為Select vl, v2,...From T1LEFT OUTER JOIN T2LEFT OUTER JOIN. . . ON (on 條件)Where (Where 條件)以下描述根據第一實施例的組合器234基於左外連接(LEFT0UTER JOIN)語句工 作的流程。步驟1，將肯定模式轉換器233輸出的所有肯定部分的SQL語句P_st組合起來 成為組合的肯定部分SQL語句(以下稱為comb-st)，將肯定模式轉換器233輸出的所有 肯定部分的變量映射表P-map組合起來成為組合的肯定部分的變量映射表(以下稱為
11comb-map)。此步驟是本領域技術人員公知的技術，並且也可以在肯定模式轉換器233中實 現。步驟2，將否定模式轉換器222輸出的否定部分的SQL語句N_st逐一地與在步驟 1中得到的comb-st組合。步驟2的具體實現如下所述對於否定部分的變量映射表N-map中的每個變量V，令E1代表在comb-map中變量 v所映射到的列，比如在表2中變量x映射到的列T2. Coll ；令E2為在N-map中該變量v所 映射到的列，比如在表1中變量x映射到的列Tl. Coll ；生成On條件「El = E2」並將其添 加到on條件列表中；將comb-st所對應的表左外連接一條N-st所對應的表，以條件列表中的已生成條 件為On條件；將上一步中進行了左外連接處理的表添加到R-st的From子句中；對於comb-map中的每個變量V，將其映射到的列添加到R_st的Select子句中；對於N-map中的每個變量V，令E2代表在N_map中變量v所映射到的列，在Where 子句中添加條件「E2is NULL」，這是因為，在左外連接操作所生成的表中，否定模式中的變 量所對應的列的內容應為「NULL」。例如，如表3-5所示，表3和表4在執行了「T3LEFT0UTER JOIN T40N(T3. ID = T4. ID) 」之後生成表5，其中表5中的第一行右側兩列的內容為「NULL」; 表3 表 4 表 5將comb-st禾口 n_st的Where子句添力口至lj R-st的Where子句中。
通過以上步驟，組合器234可容易地將肯定模式轉換器233和否定模式轉換器232 的輸出組合成為基於左外連接的最終的SQL語句。圖5是組合器234基於左外連接(LEFT OUTER JOIN)命令進行的組合處理的一個實例的示意圖，由圖5中可以清楚地看到SPARQL 查詢語句各部分與SQL查詢語句各部分之間的對應關係。在組合器234的第二實施例中，組合器234還可以基於N0TEXIST命令的解決方案 將肯定模式轉換器233和否定模式轉換器232的輸出組合成為最終的SQL語句。以下將描 述其具體處理過程。在本實施例中，步驟1同第一實施例中的步驟1類似，將肯定模式轉換器233輸 出的P-st組合起來成為comb-st，將肯定模式轉換器233輸出的所有P-map組合起來成為 comb—map。步驟2，將否定模式轉換222輸出的N-st和N-map分別逐一地與在步驟1中得到 的 comb-st 禾口 comb-map 組合。步驟2的具體實現與第一實施例中的不同，具體來說對於N-map中的每個變量V，令E1代表在comb-map中該變量v所映射到的列，比 如在表2中變量x映射到的列T2. Coll ；令E2為在N-map中該變量v所映射到的列，比如 在表1中變量x映射到的列Tl. Coll ；生成條件「El = E2」並將其以「與(AND) 」的方式添 加到N-st的Where子句中；將條件「E2is NOT NULL」以「與(AND) 」的方式添加到N-st的 Where子句中；在如上述步驟生成的N-st作為EXIST命令的表達式在外層加上NOT EXIST,並將 NOT EXIST及其表達式共同作為條件放入comb-st的Where子句中。應注意的是，如果存在多個N-st，則應從每個N-st都生成一個NOT EXIST子句，將 生成的多個NOT EXIST子句以「與(AND)，，的方式連接起來，共同作為comb-st的Where子 句，以形成最終的SQL語句R-st。通過以上步驟，組合器234可容易地將肯定模式轉換器233和否定模式轉換器232 的輸出組合成為基於EXIST的SQL語句。圖6是組合器234基於EXIST語句進行的組合處 理的一個實例的示意圖，由圖6中可以清楚地看到SPARQL查詢語句各部分與SQL查詢語句 各部分之間的對應關係。到此為止，已經描述了組合器234將肯定模式轉換器233和否定模式轉換器232 的輸出組合成為SQL語句的兩個優選實施例。作為參考，在此分別給出基於EXIST命令和 基於左外連接命令將各種SPARQL查詢轉換為SQL語句的結果示例。1.基於EXIST命令的轉換1. 1SPARQL 查詢〈？ x, p, ol> ！ SQL 查詢Select Tl. xCol From pTable Tl where Tl. yCol = oland NOT EXIST(Select T2.xCol From qTable T2 where(Tl. xCol = T2. xCol AND T2.yCol = o2 AND T2.xCol is NOT NULL))1. 2SPARQL 查詢〈？ x, p, ？ y> ！ SQL 查詢Select Tl. xCol, Tl. yCol From pTable Tl where N0TEXIST(Select T2.xCol From qTable T2 where(Tl. xCol = T2.xColAND T2.yCol = o2 AND T2.xCol is NOT NULL))
13
1. 3SPARQL 查詢〈？ x, p, ？ y> ！ SQL 查詢Select Tl. xCol, Tl. yCol From pTable T1 where NOTEXIST(Select T2. xCol, T2.yCol From qTable T2where(Tl.xCol = T2. xCol)AND(Tl. yCol = T2. yCol) AND (T2. xCol isNOT NULL) AND(T2. yCol is NOT NULL))1. 4SPARQL 查詢〈？ x, p, y> ！ SQL 查詢Select Tl. xCol, Tl. yCol From pTable Tl where NOTEXIST (Select T2. xCol, T2.yCol From qTable T2where(Tl.xCol = T2. yCol)AND(Tl. yCol = T2. xCol) AND (T2. yCol isNOT NULL) AND(T2. xCol is NOT NULL))2.基於左外連接(LEFT OUTER JOIN)命令的轉換2. 1 SPARQL 查詢 ！ SQL 查詢Select Tl.xCol From pTable T1LEFT OUTER JOINqTable T2on (Tl. xCol = T2.xCol and Tl. yCol = oland T2.yCol = o2)where (T2. xCol is NULL)2. 2SPARQL 查詢〈？ x, p, ？ y> ！ SQL 查詢Select Tl.xCol，Tl. yCol From pTable Tl LEFT0UTER JOIN qTable T2on (Tl. xCol = T2.xCol and T2. yCol = o2)where (T2. xCol is NULL)2. 3SPARQL 查詢〈？ x, p, y> ！ SQL 查詢Select Tl.xCol，Tl. yCol From pTable Tl LEFT0UTER JOIN qTable T2on (Tl. xCol = T2. xCol)AND(Tl. yCol = T2. yCol) where (T2. xCol is NULL) AND (T2. yCol is NULL)2. 4 SPARQL 查詢〈？ x, p, y> ！ SQL查詢:Select Tl. xCol,Tl. yCol From pTable Tl LEFT0UTER JOIN qTable T2 on (Tl. xCol = T2. yCol)AND (Tl. yCol = T2. xCol) where (T2. yCol is NULL) AND (T2. xCol is NULL)在本發明的第二實施例中，示出了一種更簡化的SPARQL查詢的轉換系統和方法。 下面參考圖7進行描述。圖7是示出根據本發明的另一個實施例的用於SPARQL查詢的轉換的系統的框圖。 如圖7中所示，本實施例中的SPARQL查詢的轉換系統包括語法/詞法分析器71、模式檢測 分離器72、否定模式直接轉換器732、肯定模式轉換器733以及組合器734。其中，語法/ 詞法分析器71、肯定模式轉換器733以及組合器734和第一實施例中的語法/詞法分析器 21、肯定模式轉換器233以及組合器234的功能相同，在此省略對其的描述。在模式檢測分離器72檢測解析後的SPARQL語句中的隱式否定模式，並且將檢測 出的隱式否定模式傳遞到否定模式直接轉換器732，將其餘部分，即肯定模式的部分傳遞到 肯定模式轉換器733。模式檢測分離器72檢測解析後的SPARQL語句中的隱式否定模式的 原理與第一實施例中的隱式否定模式檢測器221基本相同，只是本實施例中的模式檢測分 離器72除了輸出檢測出的隱式否定模式以外，還輸出肯定模式的部分到肯定模式轉換器 733，因此，本實施例中的模式檢測分離器72實際上起到了檢測和分離兩個作用。本實施例中的否定模式直接轉換器732與第一實施例中的隱式否定模式轉換器222不同，其綜合了第一實施例中的隱式否定模式轉換器222和否定模式轉換器232的功 能。具體來說，本實施例中的否定模式直接轉換器732不需要將從模式檢測分離器72傳遞 過來的隱式否定模式先轉換為在第一實施例中定義的顯式否定模式「！ 」，而 是將SPARQL語句中的隱式否定模式直接轉換為SQL語句的否定部分。具體處理過程如下 所述。步驟1，識別出隱式否定模式中的重複三元組和附加三元組。步驟2，搜索要轉換的SPARQL匹配單元mu』。該匹配單元mu』是附加三元組及其 過濾條件。後續步驟與步驟402-407相同。經過以上處理，否定模式直接轉換器732輸出的否定部分的SQL語句與第一實施 例中的否定模式轉換器232的輸出相同。以上描述了一種可以高效地將基於虛擬RDF存儲的SPARQL查詢轉換為SQL查詢 的系統和方法。本領域技術人員將會認識到，可以以方法、系統或電腦程式產品的形式提 供本發明的實施例。因此，本發明可以採取全硬體實施例、全軟體實施例，或者軟體和硬體 的組合的實施例的形式。本發明的事件處理系統可以以硬體、軟體或二者組合來實現。當 以硬體實現時，系統的各個組成部分可以是分立的部件，各個組成部分中的一個或多個也 可以集成在一起。硬體和軟體的典型結合可以是帶有電腦程式的通用計算機系統，當程 序被加載並執行時，控制計算機系統，從而可以執行上述的方法。本發明可以嵌入在電腦程式產品中，它包括使此處描述的方法得以實施的所有 特徵。所述電腦程式產品被包含在一個或多個計算機可讀存儲介質(包括但不限於，磁 盤存儲器、CD-ROM、光學存儲器等)中，所述計算機可讀存儲介質具有包含於其中的計算機 可讀程序代碼。已參考根據本發明的方法、系統及電腦程式產品的流程圖和/或方框圖說明了 本發明。流程圖和/或方框圖中的每個方框，以及流程圖和/或方框圖中的方框的組合顯 然可由電腦程式指令實現。這些電腦程式指令可被提供給通用計算機、專用計算機、嵌 入式處理器或者其它可編程的數據處理設備，從而指令產生用於實現在流程圖和/或方框 圖的一個或多個方框中規定的功能的裝置。當參考示例性實施例示出和描述本發明的同時，本領域技術人員將理解，可以不 脫離如所附權利要求所定義的本發明的精神和範圍而作出各種形式的修改和變更。僅出於 描述而不是限制的目的描述了示例性實施例。因此，本發明的範圍不受具體實施例的限定， 而是受所附權利要求的限定，並且該範圍內所有的修改、變更都應理解為包含在本發明中。
1權利要求
一種用於SPARQL查詢的轉換的系統，包括語法/詞法分析器，用於解析SPARQL查詢；隱式否定模式檢測器，用於檢測解析後的SPARQL查詢中的隱式否定模式；隱式否定模式轉換器，用於將檢測出的隱式否定模式轉換為顯式否定模式；分離器，用於將所述顯式否定模式和解析後的SPARQL查詢中的肯定模式分離；否定模式轉換器，用於將所述顯式否定模式轉換為否定部分的SQL語句；肯定模式轉換器，用於將所述肯定模式轉換為肯定部分的SQL語句；以及組合器，用於組合所述否定部分的SQL語句和所述肯定部分的SQL語句。
2.如權利要求1所述的系統，其中，所述隱式否定模式檢測器包括 用於將SPARQL查詢中的過濾條件範化為析取範式的部件；用於從所述過濾條件中提取具有不等變量對的條件的部件；用於提取SPARQL查詢中各個三元組所代表的連通子圖並且匹配出各自的最大連通相 似子圖的部件；以及用於根據各個最大連通相似子圖以及其與各自的連通子圖之間的差異匹配隱式否定 模式的部件。
3.如權利要求1或2所述的系統，其中，所述隱式否定模式轉換器包括 用於去除隱式否定模式中與肯定模式重複的三元組的部件；用於以肯定模式中的相應變量替換隱式否定模式中的附加三元組中的變量的部件；以及用於將表示「非」邏輯的標誌附加到轉換後的附加三元組的部件。
4.如權利要求1或2所述的系統，其中，所述否定模式轉換器包括 用於搜索要轉換的SPARQL匹配單元的部件；用於建立新的SELECT語句的部件；用於生成WHERE子句的部件；用於生成SELECT子句的部件；用於生成FROM子句的部件；用於維護變量映射表的部件；以及用於判斷是否存在其他未轉換的匹配單元的部件。
5.如權利要求1或2所述的系統，其中，所述組合器包括用於將否定部分的SQL語句逐一地與組合後的肯定部分的SQL語句組合成結果SQL語 句的部件。
6.如權利要求5所述的組合器，其中，所述結果SQL語句包含EXIST命令。
7.如權利要求5所述的組合器，其中，所述結果SQL語句包含左外連接命令。
8.如權利要求1或2所述的系統，其中所述顯式否定模式的形式為三元組附加表示 「非」邏輯的標誌。
9.一種用於SPARQL查詢的轉換的方法，包括以下步驟 語法/詞法分析，解析SPARQL查詢；隱式否定模式檢測，檢測解析後的SPARQL查詢中的隱式否定模式； 隱式否定模式轉換，將檢測出的隱式否定模式轉換為顯式否定模式；將顯式否定模式和解析後的SPARQL查詢中的肯定模式分離； 否定模式轉換，將所述顯式否定模式轉換為否定部分的SQL語句； 肯定模式轉換，將所述肯定模式轉換為肯定部分的SQL語句；以及 組合所述否定部分的SQL語句和所述肯定部分的SQL語句。
10.如權利要求9所述的方法，其中，所述隱式否定模式檢測步驟進一步包括以下步驟將SPARQL查詢中的過濾條件範化為析取範式； 從所述過濾條件中提取具有不等變量對的條件；提取SPARQL查詢中各個三元組所代表的連通子圖並且匹配出各自的最大連通相似子 圖；以及根據各個最大連通相似子圖以及其與各自的連通子圖之間的差異匹配隱式否定模式。
11.如權利要求9或10所述的方法，其中，所述隱式否定模式轉換步驟進一步包括以下 步驟去除隱式否定模式中與肯定模式重複的三元組；以肯定模式中的相應變量替換隱式否定模式中的附加三元組中的變量；以及 將表示「非」邏輯的標誌附加到轉換後的附加三元組。
12.如權利要求9或10所述的方法，其中，所述否定模式轉換步驟進一步包括以下步驟搜索要轉換的SPARQL匹配單元； 建立新的SELECT語句； 生成WHERE子句； 生成SELECT子句； 生成FROM子句； 維護變量映射表；以及判斷是否存在其他未轉換的匹配單元，如果是，則返回到所述搜索步驟。
13.如權利要求9或10所述的方法，其中，所述用於組合的步驟進一步包括 將否定部分的SQL語句逐一地與組合後的肯定部分的SQL語句組合成結果SQL語句。
14.如權利要求13所述的方法，其中，所述結果SQL語句包含EXIST命令。
15.如權利要求13所述的方法，其中，所述結果SQL語句包含左外連接命令。
16.如權利要求9或10所述的方法，其中所述顯式否定模式的形式為三元組附加表示 「非」邏輯的標誌。
17.一種用於SPARQL查詢的轉換的系統，包括 語法/詞法分析器，用於解析SPARQL查詢；模式檢測分離器，用於檢測解析後的SPARQL查詢中的隱式否定模式，並分離地輸出檢 測出的隱式否定模式和肯定模式；否定模式直接轉換器，用於將檢測出的隱式否定模式轉換為否定部分的SQL語句； 肯定模式轉換器，用於將所述肯定模式轉換為肯定部分的SQL語句；以及 組合器，用於組合所述否定部分的SQL語句和所述肯定部分的SQL語句。
18.如權利要求17所述的系統，其中，所述否定模式直接轉換器包括用於識別所述隱式否定模式中的附加三元組的部件；用於搜索由所述附加三元組和過濾條件構成的要轉換的SPARQL匹配單元的部件；用於建立新的SELECT語句的部件；用於生成WHERE子句的部件；用於生成SELECT子句的部件；用於生成FROM子句的部件；用於維護變量映射表的部件；以及用於判斷是否存在其他未轉換的匹配單元的部件。
19.一種用於SPARQL查詢的轉換的方法，包括以下步驟 語法/詞法分析，解析SPARQL查詢；模式檢測分離，檢測解析後的SPARQL查詢中的隱式否定模式，並分離地輸出檢測出的 隱式否定模式和肯定模式；否定模式直接轉換，將檢測出的隱式否定模式轉換為否定部分的SQL語句； 肯定模式轉換，將所述肯定模式轉換為肯定部分的SQL語句；以及 組合所述否定部分的SQL語句和所述肯定部分的SQL語句。
20.如權利要求19所述的方法，其中，所述否定模式直接轉換步驟進一步包括以下步驟識別所述隱式否定模式中的附加三元組；搜索由所述附加三元組和過濾條件構成的要轉換的SPARQL匹配單元； 建立新的SELECT語句； 生成WHERE子句； 生成SELECT子句； 生成FROM子句； 維護變量映射表；以及判斷是否存在其他未轉換的匹配單元，如果是，則返回到所述搜索步驟。
全文摘要
一種用於SPARQL查詢的轉換的系統，包括語法/詞法分析器，用於解析SPARQL查詢；隱式否定模式檢測器，用於檢測解析後的SPARQL查詢中的隱式否定模式；隱式否定模式轉換器，用於將檢測出的隱式否定模式轉換為顯式否定模式。分離器，用於將顯式否定模式和解析後的SPARQL查詢語句中的肯定模式分離；否定模式轉換器，用於將所述顯式否定模式轉換為否定部分的SQL語句；肯定模式轉換器，用於將所述肯定模式轉換為肯定部分的SQL語句；以及組合器，用於組合所述否定部分的SQL語句和所述肯定部分的SQL語句。
文檔編號G06F17/30GK101853257SQ20091013254
公開日2010年10月6日 申請日期2009年3月31日 優先權日2009年3月31日
發明者孫行智, 曹鋒, 潘越, 胡崗, 馬力 申請人:國際商業機器公司