基于查詢轉換的RDF高效查詢方法

佟 強，程經緯，張 富，張麗麗，馬宗民

（1.東北大學 軟件學院，沈陽110819；2.東北大學 信息科學與工程學院，沈陽110819）

0 引 言

語義Web的核心是通過為Web資源添加能夠被計算機理解的語義元數據，使Web成為一個通用的信息交換媒介。資源描述框架（RDF，Resource description framework）是語義Web資源標注的推薦標準［1］?，F有的大部分RDF 管理系統都采用DBMS來存儲和管理RDF 數據。這樣，就可以利用關系數據庫成熟的數據查詢和優化技術來達到高效查詢RDF 數據集的目的。RDF 的 標 準 查 詢 語 言 是SPARQL［2］（Simple protocol and RDF query language），而關系數據庫的標準查詢語言是SQL，因此需要將SPARQL查詢轉換為SQL查詢。

Kiminki等通過在SPARQL 語言與SQL 語言中間定義了一種新的過渡性語言AQL，實現了SPARQL查詢到SQL 查詢方法實現［3］。這類方法由于需要定義中間語言，并且需要進行兩次語言的轉換，所以相對復雜、費時。采用直接映射轉換的 方 法 相 對 較 多，Chebotko 等［4］通 過 研 究SPARQL查詢的匹配原理，推理出了三元組圖模式匹配原理的SQL 表示，提出了SPARQL 查詢中不同圖模式到SQL查詢的轉換實現方法，該方法采用的主要思想是對基本圖模式實行邊轉換邊查詢的策略，并且一個SPARQL查詢中的多個圖模式之間采用順序處理的方式完成。Elliott等人在文獻［4］的基礎上提出了全面轉換SPARQL到SQL的算法［5］，實現了包含在SELECT 查詢模式內大部分查詢到SQL 查詢的轉換，與文獻［4］不同的是，該方法不是順序處理每個基本圖模式，而是采用類似樹模型存儲關系操作符，遞歸完成FlatSPARQLtoSQL實驗系統的設計。國內浙江大學的Zhou 等通過重寫用戶提供的SPARQL語義查詢，提供更多的查詢信息，由此提出了重寫后 的SPARQL 查 詢 到SQL 查 詢 的 實 現 方 法［6］。吳濤等對SPARQL查詢機制進行了分析，基于圖模式的實現方式提出了語義Web查詢語言的轉換方法，但轉換范圍只限于圖模式的轉換，不能接受SELECT 之外的其他查詢模式［7］。雷云飛等通過在關系表之間添加鍵值約束聯系，使關系表具有一定語義，進而分析關系表的查詢與SPARQL 查詢的聯系，但是并沒有給出SPARQL 語言到SQL 語言的轉換方法和規則［8］。王 進 鵬 等［9］給 出 了 圖 模 式 關 系 代 數 與SQL語句之間的轉換方法。該方法需要首先將SPARQL轉換為關系代數，再執行關系代數到SQL的轉換。此外，ASK 和DESCRIBE 等其他查詢形式的轉換還沒有實現。

本文提出的查詢轉換方法采用了一次轉換后再執行的策略，能夠有效地降低查詢轉換的時間，提高執行效率。此外，包含了不同的查詢模式和圖模式，擴展了可接受查詢的范圍。

1 轉換基本思想

從形式上看，一個SPARQL查詢一般由五部分組成：聲明、查詢形式與結果集、數據集、圖模式和結果修飾。

聲明：將一個用IRI表示的資源縮寫成一個簡單的命名空間的形式，目的就是為了方便標記和節省存儲空間。這部分在查詢轉換中并不涉及。

查詢形式與結果集：SPARQL 包含四類查詢模 式 SELECT、CONSTRUCT、ASK 和DECRIBLE，模式匹配的結果形成結果集或RDF圖。

數據集：在SPARQL查詢中，采用FROM 子句和FROM NAMED 子句對數據集進行描述。數據集中可以包括一個沒有名字的默認圖，以及零個或者多個通過URI進行識別的具名圖。

圖模式：SPARQL 查詢基于圖模式匹配實現［10］，最簡單的圖模式是三元組模式，類似于RDF三元組，但主語、謂語或賓語位置允許出現變量。復雜圖模式包括：基本圖模式、組圖模式、可選圖模式和多圖模式。

結果修飾：結果修飾符能夠影響查詢的返回結果，使查詢在作用范圍的廣度和作用效果的程度上都有顯著增強。

例1 給定一個圖模式為三元組模式的SPARQL查詢：

01 SELECT？name

02 FROM ＜http：／／example.org／foaf／aliceFoaf＞

03 WHERE｛？x name？name.｝轉換為下面的SQL查詢：

SELECT tri＿1.o

FROM Triple AS tri＿1

WHERE tri＿1.p＝“name”AND tri＿1.res＝“http：／／example.org／foaf／aliceFoaf”

SELECT：SPARQL 中SELECT 關 鍵 字 之后跟隨的是變量名集合，SQL 中則是屬性列集合，需要將這兩種名字在形式上進行轉換。這里定義函數label（？a）為SPARQL 查詢中變量？a的名字到SQL 屬性列名的映射。在得到的SELECT 列選擇中需要指定屬性列來自于哪個具體的關系表，如例1 中name屬性列來自于關系表tri＿1。

FROM：SQL 中FROM 關 鍵 字 后 給 出 的 是查詢數據所在的源表，可以包含關系表的別名形式，例1中為Triple表分配了別名tri＿1。本文中所有的三元組都存儲在一個關系表中，所以在進行每一步的查詢操作時，都需要對關系表進行分配別名操作，避免直接修改源數據。

WHERE：SPARQL查詢中WHERE中包含的是RDF 三元組需要滿足的圖匹配條件集合。SQL查詢中WHERE 后面是檢索記錄需要滿足的條件集合。例1 中SPARQL 查詢中出現的WHERE條件約束｛？x name？name.｝，轉換到SQL查詢的形式為：｛tri＿1.p＝”name”AND tri＿1.res ＝”http：／／example.org／ foaf／aliceFoaf”｝。

可以看出，在轉換過程中將SPARQL三元組圖模式中的常量術語轉換成了SQL 查詢中的關系屬性列值的約束條件，并且將原SPARQL查詢的FROM 轉換到了對SQL 關系表屬性列res的值約束上。所以，SQL 查詢中的WHERE 約束條件主要根據SPARQL查詢中FROM 中規定的RDF圖約束以及WHERE 中的圖模式匹配條件生成。

2 圖模式轉換

2.1 基本圖模式轉換

基本圖模式是三元組圖模式的有限集合。對于包含在WHERE約束條件中的SPARQL 三元組圖模式進行SQL轉換，主要是對其中的各個項（sp，op，pp）進行分析，根據項是常量還是變量分別給出不同的處理策略。此外還要判斷在SPARQL查詢中是否給定了RDF圖的限制。

項為常量：這時需要針對該位置的屬性列名添加是約束條件到生成的WHERE約束條件中；

項為變量：這時需要比較該項與其他項是否相同，如果相同，則在生成的WHERE 約束條件中添加相應位置屬性列名的等值約束；

含有對RDF圖的限制：這時需要在WHERE條件集合中添加res等于相應RDF 圖URI的屬性值約束條件。

下面給出函數genWhere（tp，G）。該函數根據對SPARQL 查詢中三元組圖模式的形式進行分析，形成SQL 查詢中WHERE 約束條件的表達式。其具體實現如下：

函數：genWhere（tp，G）

輸入：三元組圖模式tp（sp，pp，op），RDF 數據集G

輸出：SQL查詢WHERE條件約束

01 初始化where＝””，alias＝tri＿（＋＋i）

02 if tp.sp?var

03 then where＋＝“And”＋alias＋“.s＝tp.sp”

04 if tp.pp?var

05 then where＋＝“And”＋alias＋“.p＝tp.pp”

06 if tp.op?var

07 then where＋＝“And”＋alias＋“.o＝tp.op”

08 if tp.sp ＝ ＝tp.pp

09 then where＋＝“And”＋alias＋“.s＝”＋alias＋“.p”

10 if tp.sp＝＝tp.op

11 then where＋＝“And”＋alias＋“.s＝”＋alias＋“.o”

12 if tp.pp＝tp.op

13 then where＋＝“And”＋alias＋“.p＝”＋alias＋“.o”

14 where＋＝“And（”

15 for each g in G

16 where＋＝“OR”＋alias＋“.res＝g”

17 where ＋＝“）”

18 return where

在genWhere（tp，G）的函數實現中，分別對上述三種情況進行了分析，并對where值進行了相應的條件添加。在第02到07行中，處理了第一種情況，分別對圖模式中的每個常量項進行判斷，并對where添加屬性值約束條件；在第08到13行中，處理了第二種情況，分別判斷了三元組中任意兩個變量項相同的情況，并在where中添加了屬性列間的約束條件；在第14 至17 行，對SPARQL 查詢中指定RDF 圖的情況進行了處理，在where條件中添加了屬性列res的值約束條件。在形成的where條件表達式中每個項約束條件都是以AND 為連接，RDF 圖約束之間用OR 連接。

根據以上的分析進而提出只包含基本圖模式的SPARQL查詢到SQL 的轉換方法，現定義一個函數trans（m，G）以實現該功能。該函數對基本圖模式的構成進行分析，并將其轉換為SQL 查詢。

函數：trans（bgp，G）

輸入：基本圖模式bgp，RDF數據集G

輸出：SQL查詢

01 初始化select＝“”，from＝“”，where＝“”，first＝true

02 for each？a in bgp

a）if first＝＝true then first＝false else select＋＝“，”

b）select＋＝label（？a）

03 from＋＝“Triple AS”＋tri＿i

04 for each tp in bgp

05 where＋＝genWhere（tp，G）

06 return query＝“SELECT”＋select＋“FROM”＋

from＋ “WHRER”＋

where＋ “AS T＿”＋（＋＋j）

SQL 查 詢 的 結 構 是“SELECT＋FROM ＋WHERE”形式，所以trans函數要實現這三個基本結構的生成。在該算法中，第02 行生成SELECT 語句，第03 行 生 成FROM 子 句，為 要查詢的數據表分配別名，第06 行將genWhere（tp，G）產生的約束條件添加到生成的SQL 查詢中。

2.2 SPARQL復雜圖模式的分解

這里用m 表示復雜圖模式，將其表示為子模式連接形式為m.leftchild op m.rightchild，其中op可以為AND、OPT 和UNION，分別代表組圖模式、可選圖模式和多圖模式。

復雜圖模式分解的基本思想是：首先分別對復雜圖模式中每個子模式進行轉換，得到相應的SQL子查詢，然后根據子模式之間的邏輯關系，將子查詢結果按照不同的連接形式添加到最終的FROM 源表約束中。

2.2.1 組圖模式到SQL語言的轉換

滿足組圖模式的每一個結果必須對該組圖模式內的每個基本圖模式都匹配成功。假定r為存儲RDF數據集的關系表中的一條記錄。對于任意滿足trans（m.leftchild AND m.rightchild，G）的記錄r，r必定同時滿足trans（m.leftchild，G）和trans（m.rightchild，G）。在關系代數中，這種同時滿足的關系可以用表之間的內連接來表示。

具體地說，首先轉換子模式，得到SQL 查詢trans（m.leftchild，G）的結果集合R1 和trans（m.rightchild，G）的結果集合R2；然后根據m.leftchild和m.rightchild之間的AND 關系，對結果關系表R1和R2進行內連接操作。

下面給出組圖模式到SQL 轉換的函數trans（m，AND，G）。連接條件設定為“TRUE AND（m.leftchild.a ＝m.rightchild.a OR m.leftchild.a is null OR m.rightchild.a is null）”，其中“m.leftchild.a＝m.rightchild.a”代表兩個關系表之間的自然連接條件，“m.leftchild.a is null”代表的是當m.leftchild中含有可選圖模式時，變量？a未被綁定的情況。

函數：trans（m，AND，G）

輸入：組圖模式m，RDF數據集G

輸出：SQL查詢

01 query＋＝“（”＋trans（m.leftchild，G）＋“INNER JOIN”＋trans（m.rightchild，G）

02 first＝true

03 for m.leftchild與m.rightchild的相同屬性列a

04 if first＝true

05 then first＝false

06 else query＋＝“AND（m.leftchild.a＝ m.rightchild.a OR m.leftchild.a is null OR m.rightchild.a is null）”

07 query＋＝“ON TRUE”

08 query＋＝“）AS T＿”＋（＋＋j）

09 return query

2.2.2 可選圖模式到SQL語言的轉換

可選圖模式由OPTIONAL 子句構成，其功能是對OPTIONAL 子句內的圖模式可選匹配，如果匹配失敗，就用NULL來代替變量綁定。在關系代數中，這種選擇的概念可以用左連接體現。

可選圖模式中包含著兩類OPTIONAL 子句，一類是平行OPTIONAL 子句，一類是嵌套OPTIONAL子句。

嵌套 OPTIONAL 子句是指在一個OPTIONAL 子 句 中 還 包 含 至 少 一 個OPTIONAL 子句。嵌套OPTIONAL 子句的轉換方式為：先使用基本圖模式進行查詢，然后再將得出的關系表與整個嵌套OPTIONAL子句的查詢結果進行左連接操作。

下面分析平行OPTIONAL 子句，如例2 所示。

例2 （平行OPTIONAL 子句）給定一個包含平行OPTIONAL子句的SPARQL查詢如下：

01 SELECT？a，？n，？ew

02 WHERE｛

03 ｛？a name？n.｝

04 OPTIONAL｛？a email？ew.｝

05 OPTIONAL｛？a web？ew.｝

06 ｝

此查詢共包含三個基本圖模式gp1、gp2、gp3，分別在第03、04、05行內。對應的圖模式查詢結果分別為：R1（a，n），R2（a，ew），R3（a，ew）。

首先，gp1與gp2的查詢結果合并表示為：

然后進行Rres與R3的連接，其連接條件分為兩種情況：

（1）如果共享變量在Rres中已經綁定，則R3中同一變量必須綁定相同的值。

（2）如果共享變量在Rres中未被綁定，即值為NULL，則R3可以對該變量進行任意值的綁定。

根據以上的分析，可以將Rres與R3的連接表示為：Rres（a，n，ew）＝

因為在Rres與R3之間存在著兩個相關聯變量？a和？ew。在Rres中變量？a必須綁定，所以在連接條件中需判斷Rres.a＝R3.a。第04 行可選圖模式中變量？ew 如果未被綁定（Rres.ew is NULL），則在第05行的可選圖模式中進行綁定操作。

根據以上對各種情況的分析，給出OPTIONAL子句到SQL 的轉換函數trans（m，OPT，G）。

函數：trans（m，OPT，G）

輸入：組圖模式m，RDF數據集G

輸出：SQL查詢

01 query＋＝“（”＋trans（m.leftchild，G）＋ “LEFT OUTER JOIN”＋

02trans（m.rightchild，G）

03 first＝true

04 for m.leftchild與m.rightchild的相同屬性列a

05 if first＝true then first＝false else query＋＝“AND（m.leftchild.a＝ m.rightchild.a OR m.leftchild.a is null OR m.rightchild.a is null）”

06 query＋＝“ON true”

07 query＋＝“）AS T＿”＋（＋＋j）

08 return query

該轉換方法的原理是：首先利用trans（m，G）將m.leftchild 和m.rightchild 轉 換 為SQL 查詢；然后利用關系代數中左連接操作上述SQL 查詢的結果表。如果m.leftchild 與m.rightchild中存在相同的變量屬性列a，則m.leftchild：∝m.rightchild的連接條件為“m.leftchild.a＝m.rightchild.a ?m.leftchild.a is NULL ?m.rightchild.a is NULL”。

2.2.3 多圖模式到SQL語言的轉換

多圖模式中子模式之間由UNION 關鍵字連接，表示滿足任一子模式的查詢結果都是多圖模式的查詢結果。文獻［4］為解決UNION 多圖模式到基本圖模式的方法，引入了操作符。該操作符對結果關系表的操作用關系代數的形式表示如下：

R1∪R2＝（R1：∝R2）UNION（R2：∝R1）

在處理多表連接操作時，連接條件設定為false，目的是只進行兩表屬性列的合并，屬性值不參與表的合并，使得生成兩個關系表的屬性結構相同，能夠直接執行SQL中的UNION 操作。該處理方法可以用函數trans（m，UNION，G）表示。

函數：trans（m，UNION，G）

輸入：組圖模式m，RDF數據集G

輸出：SQL查詢

01 query＋＝”（（”＋trans（m.leftchild，G）＋”

LEFT OUTER JOIN”＋

trans（m.rightchild，G）＋”On（false））”

＋”UNION（”＋trans（m.rightchild，G）＋”

LEFT OUTER JOIN”＋

trans（m.leftchild，G）＋”On（false））”＋”AS

T＿”＋（＋＋j）

02 return query

3 結果修飾符與其他查詢模式

SPARQL語言包含多個結果修飾符和查詢模式，影響結果返回的形式和順序。在轉換過程中，需要將這些結果修飾符和查詢模式映射到SQL語言中相應的關鍵字。

3.1 結果修飾符到SQL的映射

3.1.1 相同關鍵字結果修飾符的映射

SPARQL 中 結 果 修 飾 符 DISTINCT、ORDER BY、LIMIT n 和OFFSET m 在SQL中同樣存在，且用法和功能相同，因此可以直接映射。當SPARQL 查詢中出現這些關鍵字時，在SQL查詢中SELECT 關鍵字后添加該關鍵字即可。

3.1.2 FILTER 到SQL的映射

FILTER（expr（r））實現對結果集的限制，只有使expr（r）為真的數據記錄或者三元組才可以在結果集中表現出來。其中的布爾型表達式expr（r）會涉及到很多方面，包括邏輯符號（Error！Objects cannot be created from editing field codes.），數字運算符號（＜，≤，≥，＞，＝），一元運算符包括bound，isIRI和一些其他運算符等。

當SPARQL 查詢中出現FILTER 關鍵字時，只需在轉換后的SQL 查詢的WHERE 條件集合中添加FILTER 內的限制條件即可。當變量出現在關系表中時，在WHERE 中添加對變量值的約束。另外需要考慮的是其中涉及到的數據類型的轉換，以及String字符串的轉換和比較操作。

在轉換中需要以下幾個替換規則：將變量var用變量名代替，如？a的變量名為a；文字型和URI都轉換為字符型，數值型轉換成”l”型；邏輯運算符?、?和?分別替換成NOT、AND 和OR；expr為“bound（？x）”替換成“x is not NULL”。

3.2 SPARQL查詢模式轉換

SPARQL查詢語言中包含著四種查詢模式：SELECT、CONSTRUCT、DESCRIBE和ASK。

3.2.1 SELECT 查詢模式轉換方法

首先定義包含SELECT 查詢模式的SPARQL查詢Q＝｛Ssel，G，Tree｝，其中Ssel表示查詢變量集合；G 代表SPARQL查詢中指定的RDF圖；參數Tree就是包含了所有圖模式和限定約束條件的SPARQL結構樹的根節點。

SELECTtoSQL 算法的主要思想是：根據WHERE中包含的圖模式，分別對每個圖模式進行轉換，得到相應的SQL 子查詢，然后根據各個圖模式之間的邏輯關系，將得到的SQL子查詢按照不同的連接形式添加到最終的FROM 源表約束中。

算法：SELECTtoSQL

輸入：SPARQL查詢Q＝｛Ssel，G，Tree｝

輸出：SQL查詢

01 初始化select＝“”，from＝“”，i＝1，query＝“”

02 for 先序遍歷SPARQL 結構樹Tree中的每個節點m

03 if m 為基本圖模式（組圖模式）節點then trans（m，AND，G）

04 if m 為可選圖模式節點then trans（m，OPT，G）

05 if m 為多圖模式節點then trans（m，UNION，G）

06 first＝true

07 for each？aError！Objects cannot be created from editing field codes.Ssel

08 if first＝true then first＝false

09 else select＋＝“，”

10 select＋＝label（？a）

11 from＋＝query＋“AS T＿”＋（＋＋j）

12 return“SELECT”＋select＋“FROM”＋from其中select代表需要投影的屬性列集合，from 代表源表選擇，query 表示條件約束條件集合。算法使用子查詢生成的關系表作為源數據表，也就是將query查詢生成的關系表作為FROM 中的數據源部分。因為組圖模式是由基本圖模式通過AND 連接而成，第03行對基本圖模式的判斷和對組圖模式的判斷合并在一起。R 作為一個臨時關系表用于存儲基本圖模式轉換后的查詢結果。第04行和05行分別是對可選圖模式和多圖模式進行處理。第07至10行形成了select需要投影的屬性列集合。最后第12行對結果關系表進行投影操作，選擇在Ssel中出現并且以其中的變量名命名的屬性列，最終返回V，完成SELECT 查詢。

3.2.2 CONSTRUCT 查詢模式轉換

CONSTRUCT 查詢模式按照用戶指定的圖模板返回一個RDF圖，其中查詢結果置換圖模板中的變量。

CONSTRUCT 查詢模式會先按照WHERE約束條件對數據集進行查詢操作，然后將結果以CONSTRUCT 中指定的RDF 三元組形式輸出。由于RDF圖存儲在關系數據庫中，所以只能用關系表近似地表示作為查詢結果的RDF圖。

將CONSTRUCT 查詢轉換為SQL 查詢的主要思想是：以RDF圖G 和Tree結構樹的根節點作為參數調用SELECTtoSQL 算法，返回CONSTRUCT 中要求的變量綁定。為了使關系表包含CONSTRUCT 中的所有屬性，包括常量屬性列和變量屬性列，需要對擁有變量屬性列的關系表和擁有常量屬性列的關系表進行笛卡爾積操作。針對形成的全屬性列關系表，根據CONSTRUCT 中出現的每個基本圖模式的屬性結構，投影出相應的屬性列，并把相應的元組加入到結果關系表中。最后，依據元組所屬圖和元組的主語使用GROUP BY 關鍵字對結果關系表的元組進行分組排序，將結果集返回給用戶。上述轉換思想形式化表示為以下算法：

算法：CONSTRUCTtoSQL

輸入：CONSTRUCT query Q ＝（Sty，G，Tree）

輸出：SQL query result

01 建立一個臨時表X，擁有Sty 中常量屬性列Adcol＝（literal1，literal2，…）

02 設Ssel為Sty中要求表示的變量集合

03 CREATE VIEW V／＊建立視圖V 作為結果關系表＊／

04 視圖Y＝exec（SELECTtoSQL（Ssel，G，Tree））

05 Y＝Y×X ／＊兩個關系表的笛卡爾積＊／

06 for Sty中每個gpi

07 確定該圖模式的屬性結構

08 從Y 中投影出圖模式中包含的屬性列，并將元組加入到V 中

09 對V 中的元組進行分類（GROUP BY（res，s））

10 return V

其中Sty 表示CONSTRUCT 內的結果輸出格式，可以包含多個基本圖模式；參數Tree是包含了所有圖模式和限定約束條件的結構樹的根節點；G 代表要查詢的RDF 圖集合。第01行中建立臨時表X，包含了CONSTRUCT 中要返回格式的常量屬性列。第02 行的Ssel 代表著CONSTRUCT 中需要返回的變量集合。第04行以G 和Tree作為參數調用SELECTtoSQL函數，將中間結果集存儲在視圖Y 中。第05 行將擁有變量屬性列的Y 與擁有常量屬性列的X 進行笛卡爾積操作，并以此更新視圖Y，目的是使關系表中每條記錄都包含CONSTRUCT 要求返回的全部屬性列。第06 到08 行將Y 中記錄按照CONSTRUCT 的要求把相應的屬性列進行重新排列，加入到結果關系表V 中。第09 行是對V中的記錄進行分組排列，主分組詞為res，即RDF圖的URI，次分組詞為三元組的主語。最后將結果關系表返回給用戶，完成從CONSTRUCT 查詢模式到SQL的轉換。

3.2.3 DESCRIBE查詢模式轉換

DESCRIBE查詢返回關于某個變量？descri的全部描述。首先，找到每個滿足Where條件的？descri的變量綁定bind。然后，尋找以bind為主語的元組和以bind為主語的元組中的謂詞為主語的元組，以及以bind為賓語的元組。最后，將所有的元組按照RDF 圖IRI和主體進行分組排列返回給用戶。DESCRIBE 查詢轉換形式化表示為以下算法：

算法：DESCRIBEtoSQL

輸入：SPARQL query Q＝（Descri，G，Tree）

輸出：SQL query result

01 CREATE VIEW V

02 if（isIRI（Descri））

03 V＝exec（SELECTtoSQL（＊，Descri，Tree）））

04 if（isVAR（Descri））

05 X＝exec（SELECTtoSQL（Descri，G，Tree））

06 for X 中的每個變量綁定xi

07 添加exec（SELECTtoSQL（＊，G，（s＝xi）））的返回結果到表V 中

08 for V 中的每個記錄行提取出謂詞pi和賓語oi

09 添加exec（SELECTtoSQL（＊，G，（（s＝pi）UNION（s＝oi））））的返回結果到V 中

10 根據res和s進行結果排序

11 return V

其中Descri為要查詢的變量或者IRI，WHERE為約束條件，G 為指定的RDF 圖集合。第02、03行處理DESCRIBE 關鍵字后面描述的是一個RDF圖IRI的情況，此時將該IRI內的所有元組存入 視 圖 V 中。第04 到10 行 處 理 的 是DESCRIBE關鍵字后面要描述的是某一個變量的情況，此時將滿足圖模式匹配的變量綁定存放到臨時表X 中。接下來查找以X 中任意的變量綁定為主語的元組并將其添加到V 中。第08、09行查找以V 中元組的謂詞或者賓語為主語的元組，并且不斷地將元組加入到V 中，直到V 中所有元組都被訪問過。最后對V 中的元組進行分組排列返回給用戶。

3.2.4 ASK 查詢模式轉換

ASK 查詢模式用于檢測符合Where條件約束的變量匹配是否存在，若存在則返回true，否則返回false。根據其含義，若執行SELECTtoSQL（＊，G，Where）得到的結果集不為空，則返回true；否則返回false。其中G 為所有RDF 圖的集合，Where為ASK 查詢模式中的圖模式集合。

算法：ASKtoSQL

輸入：SPARQL query Q＝｛G，WHERE｝

輸出：BOOLEAN（true／false）

01 if（exec（（SELECTtoSQL（＊，G，WHERE）））返回結果不為空）

02 return true

03 else

04 return false

3.3 SPARQL查詢到SQL查詢的實現方法

綜上，給出SPARQLtoSQL 算法，該算法根據不同查詢模式，分別作出不同函數調用，實現任一SPARQL查詢到SQL查詢的轉換。

算法：SPARQLtoSQL

輸入：SPARQL query Q＝｛Pattern，Ssel，G，Tree｝

輸出：結果關系表V 或者布爾值

01 Switch（Pattern）｛

02 Case SELECT：

03 query＝SELECTtoSQL（Ssel，G，Tree）；輸出V＝exec（query）；

04 Case CONSTRUCT：

05 V ＝exec（CONSTRUCTtoSQL（Ssel，G，Tree））；輸出V；

06 Case（DESCRIBE）：

07 V＝exec（DESCRIBEtoSQL（Ssel，G，Tree））；輸出V；

08 Case（ASK）：

09 b＝exec（ASKtoSQL（G，Tree））；輸出b；

10 ｝

4 實驗及結果分析

根據上述分析，實現了SPARQLtoSQL查詢轉換系統，以Wine本體作為實驗數據對系統進行評測，選擇12個具有代表性的SPARQL 查詢作為輸入（如表1所示），并對實驗結果與其他兩種 現 有 的 轉 換 方 法 SparqlTOSql［4］和FlatSqlJoinMySQL［5］進行了分析和比較。

表1 查詢實例Table 1 Query examples

圖1給出了三種不同查詢策略的查詢響應時間。查詢響應時間是指從輸入SPARQL查詢，經過查詢轉換，到查找出滿足匹配條件的RDF數據所用的時間。由于前兩種方法不支持Q9到Q12的查詢模式，所以不對這四個查詢實例的查詢響應時間做對比。由圖可知本文提出的查詢轉換策略的查詢響應時間最短。與FlatSqlJoinMySQL方法相比，由于該方法使用的方法是延續SparqlToSql方法中的多次轉換多次查詢的策略，所以與本文提出的多次轉換一次查詢的方法相比查詢響應時間略長。

圖1 查詢響應時間對比圖Fig.1 The query response time of different systems

5 結束語

本文提出了SPARQL查詢到SQL查詢的轉換方法，給出了圖模式、結果修飾符和不同查詢模式到SQL 的轉換規則，構建了SPARQLtoSQL查詢轉換系統。以往轉換算法通常采用邊轉換邊執行的方式，導致轉換耗時、效率低。本文采用一次轉換再執行的方式，顯著提高了轉換效率。

［1］RDF 1.1Concepts and Abstract Syntax［EB／OL］.2014.http：／／www.w3.org／TR／rdf11－concepts／.

［2］SPARQL 1.1Query Language［EB／OL］.2013.http：／／www.w3.org／TR／sparql11－query／

［3］Kiminki S，Knuuttila J，Hirvisalo V.SPARQL to SQL translation based on an intermediate query language［C］∥Proc of 6th International Workshop on Scalable Semantic Web Knowledge Base Systems，Shanghai，China，2010：32－47.

［4］Chebotko A，Lu S，Fotouhi F.Semantics preserving SPARQL－to－SQL translation［J］.Data ＆Knowledge Engineering（DKE），2009，68（10）：973－1000.

［5］Elliott B，Cheng E，Thomas－Ogbuji C.A complete translation from SPARQL into efficient SQL［C］∥Proc of 2009International Database Engineering Applications Symposium，Cetraro（Calabria），Italy，2009：31－42.

［6］Zhou C Y，Zheng Y W.Query rewriting from SPARQL to SQL for relational database integration［J］.IEIT Journal of Adaptive ＆Dynamic Computing，2010，1（1）：1－8.

［7］吳濤.語義網本體查詢語言轉換技術的研究與實現［D］.北京：北京工業大學計算機學院，2009.Wu Tao.Research and implementation of translation techniques of semantic Web ontology query language［D］.Beijing：College of Computer Science，Beijing University of Technology，2009.

［8］雷云飛，黃劉生，陳國良.RDF 查詢語言到SQL 語言的轉換原理及其實現方法［J］.計算機研究與發展，2004，41（7）：1251－1257.Lei Yun－fei，Huang Liu－sheng，Chen Guo－liang.Principle of converting RDF query language to SQL and its implementation［J］.Journal of Computer Research and Development，2004，41（7）：1251－1257.

［9］王進鵬，張亞非，苗壯.SPARQL 查詢的關系代數表示與轉換方法［J］.計算機工程與應用，2011，47（22）：110－113.Wang Jin－peng，Zhang Ya－fei，Miao Zhuang.Algebra representation and transformation for SPARQL query［J］.Computer Engineering and Application，2011，47（22）：110－113.

［10］Chen Y.Using SPARQL to query RDF data［J］.Technological Development of Enterprise，2007，26（7）：6－10.