基于查詢(xún)轉(zhuǎn)換的RDF高效查詢(xún)方法

佟 強(qiáng)，程經(jīng)緯，張 富，張麗麗，馬宗民

（1.東北大學(xué) 軟件學(xué)院，沈陽(yáng)110819；2.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng)110819）

0 引 言

語(yǔ)義Web的核心是通過(guò)為Web資源添加能夠被計(jì)算機(jī)理解的語(yǔ)義元數(shù)據(jù)，使Web成為一個(gè)通用的信息交換媒介。資源描述框架（RDF，Resource description framework）是語(yǔ)義Web資源標(biāo)注的推薦標(biāo)準(zhǔn)［1］。現(xiàn)有的大部分RDF 管理系統(tǒng)都采用DBMS來(lái)存儲(chǔ)和管理RDF 數(shù)據(jù)。這樣，就可以利用關(guān)系數(shù)據(jù)庫(kù)成熟的數(shù)據(jù)查詢(xún)和優(yōu)化技術(shù)來(lái)達(dá)到高效查詢(xún)RDF 數(shù)據(jù)集的目的。RDF 的 標(biāo) 準(zhǔn) 查 詢(xún) 語(yǔ) 言 是SPARQL［2］（Simple protocol and RDF query language），而關(guān)系數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)查詢(xún)語(yǔ)言是SQL，因此需要將SPARQL查詢(xún)轉(zhuǎn)換為SQL查詢(xún)。

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

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

1 轉(zhuǎn)換基本思想

從形式上看，一個(gè)SPARQL查詢(xún)一般由五部分組成：聲明、查詢(xún)形式與結(jié)果集、數(shù)據(jù)集、圖模式和結(jié)果修飾。

聲明：將一個(gè)用IRI表示的資源縮寫(xiě)成一個(gè)簡(jiǎn)單的命名空間的形式，目的就是為了方便標(biāo)記和節(jié)省存儲(chǔ)空間。這部分在查詢(xún)轉(zhuǎn)換中并不涉及。

查詢(xún)形式與結(jié)果集：SPARQL 包含四類(lèi)查詢(xún)模 式 SELECT、CONSTRUCT、ASK 和DECRIBLE，模式匹配的結(jié)果形成結(jié)果集或RDF圖。

數(shù)據(jù)集：在SPARQL查詢(xún)中，采用FROM 子句和FROM NAMED 子句對(duì)數(shù)據(jù)集進(jìn)行描述。數(shù)據(jù)集中可以包括一個(gè)沒(méi)有名字的默認(rèn)圖，以及零個(gè)或者多個(gè)通過(guò)URI進(jìn)行識(shí)別的具名圖。

圖模式：SPARQL 查詢(xún)基于圖模式匹配實(shí)現(xiàn)［10］，最簡(jiǎn)單的圖模式是三元組模式，類(lèi)似于RDF三元組，但主語(yǔ)、謂語(yǔ)或賓語(yǔ)位置允許出現(xiàn)變量。復(fù)雜圖模式包括：基本圖模式、組圖模式、可選圖模式和多圖模式。

結(jié)果修飾：結(jié)果修飾符能夠影響查詢(xún)的返回結(jié)果，使查詢(xún)?cè)谧饔梅秶膹V度和作用效果的程度上都有顯著增強(qiáng)。

例1 給定一個(gè)圖模式為三元組模式的SPARQL查詢(xún)：

01 SELECT？name

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

03 WHERE｛？x name？name.｝轉(zhuǎn)換為下面的SQL查詢(xún)：

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 關(guān) 鍵 字 之后跟隨的是變量名集合，SQL 中則是屬性列集合，需要將這兩種名字在形式上進(jìn)行轉(zhuǎn)換。這里定義函數(shù)label（？a）為SPARQL 查詢(xún)中變量？a的名字到SQL 屬性列名的映射。在得到的SELECT 列選擇中需要指定屬性列來(lái)自于哪個(gè)具體的關(guān)系表，如例1 中name屬性列來(lái)自于關(guān)系表tri＿1。

FROM：SQL 中FROM 關(guān) 鍵 字 后 給 出 的 是查詢(xún)數(shù)據(jù)所在的源表，可以包含關(guān)系表的別名形式，例1中為T(mén)riple表分配了別名tri＿1。本文中所有的三元組都存儲(chǔ)在一個(gè)關(guān)系表中，所以在進(jìn)行每一步的查詢(xún)操作時(shí)，都需要對(duì)關(guān)系表進(jìn)行分配別名操作，避免直接修改源數(shù)據(jù)。

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

可以看出，在轉(zhuǎn)換過(guò)程中將SPARQL三元組圖模式中的常量術(shù)語(yǔ)轉(zhuǎn)換成了SQL 查詢(xún)中的關(guān)系屬性列值的約束條件，并且將原SPARQL查詢(xún)的FROM 轉(zhuǎn)換到了對(duì)SQL 關(guān)系表屬性列res的值約束上。所以，SQL 查詢(xún)中的WHERE 約束條件主要根據(jù)SPARQL查詢(xún)中FROM 中規(guī)定的RDF圖約束以及WHERE 中的圖模式匹配條件生成。

2 圖模式轉(zhuǎn)換

2.1 基本圖模式轉(zhuǎn)換

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

項(xiàng)為常量：這時(shí)需要針對(duì)該位置的屬性列名添加是約束條件到生成的WHERE約束條件中；

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

含有對(duì)RDF圖的限制：這時(shí)需要在WHERE條件集合中添加res等于相應(yīng)RDF 圖URI的屬性值約束條件。

下面給出函數(shù)genWhere（tp，G）。該函數(shù)根據(jù)對(duì)SPARQL 查詢(xún)中三元組圖模式的形式進(jìn)行分析，形成SQL 查詢(xún)中WHERE 約束條件的表達(dá)式。其具體實(shí)現(xiàn)如下：

函數(shù)：genWhere（tp，G）

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

輸出：SQL查詢(xún)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）的函數(shù)實(shí)現(xiàn)中，分別對(duì)上述三種情況進(jìn)行了分析，并對(duì)where值進(jìn)行了相應(yīng)的條件添加。在第02到07行中，處理了第一種情況，分別對(duì)圖模式中的每個(gè)常量項(xiàng)進(jìn)行判斷，并對(duì)where添加屬性值約束條件；在第08到13行中，處理了第二種情況，分別判斷了三元組中任意兩個(gè)變量項(xiàng)相同的情況，并在where中添加了屬性列間的約束條件；在第14 至17 行，對(duì)SPARQL 查詢(xún)中指定RDF 圖的情況進(jìn)行了處理，在where條件中添加了屬性列res的值約束條件。在形成的where條件表達(dá)式中每個(gè)項(xiàng)約束條件都是以AND 為連接，RDF 圖約束之間用OR 連接。

根據(jù)以上的分析進(jìn)而提出只包含基本圖模式的SPARQL查詢(xún)到SQL 的轉(zhuǎn)換方法，現(xiàn)定義一個(gè)函數(shù)trans（m，G）以實(shí)現(xiàn)該功能。該函數(shù)對(duì)基本圖模式的構(gòu)成進(jìn)行分析，并將其轉(zhuǎn)換為SQL 查詢(xún)。

函數(shù)：trans（bgp，G）

輸入：基本圖模式bgp，RDF數(shù)據(jù)集G

輸出：SQL查詢(xún)

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 查 詢(xún) 的 結(jié) 構(gòu) 是“SELECT＋FROM ＋WHERE”形式，所以trans函數(shù)要實(shí)現(xiàn)這三個(gè)基本結(jié)構(gòu)的生成。在該算法中，第02 行生成SELECT 語(yǔ)句，第03 行 生 成FROM 子 句，為 要查詢(xún)的數(shù)據(jù)表分配別名，第06 行將genWhere（tp，G）產(chǎn)生的約束條件添加到生成的SQL 查詢(xún)中。

2.2 SPARQL復(fù)雜圖模式的分解

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

復(fù)雜圖模式分解的基本思想是：首先分別對(duì)復(fù)雜圖模式中每個(gè)子模式進(jìn)行轉(zhuǎn)換，得到相應(yīng)的SQL子查詢(xún)，然后根據(jù)子模式之間的邏輯關(guān)系，將子查詢(xún)結(jié)果按照不同的連接形式添加到最終的FROM 源表約束中。

2.2.1 組圖模式到SQL語(yǔ)言的轉(zhuǎn)換

滿(mǎn)足組圖模式的每一個(gè)結(jié)果必須對(duì)該組圖模式內(nèi)的每個(gè)基本圖模式都匹配成功。假定r為存儲(chǔ)RDF數(shù)據(jù)集的關(guān)系表中的一條記錄。對(duì)于任意滿(mǎn)足trans（m.leftchild AND m.rightchild，G）的記錄r，r必定同時(shí)滿(mǎn)足trans（m.leftchild，G）和trans（m.rightchild，G）。在關(guān)系代數(shù)中，這種同時(shí)滿(mǎn)足的關(guān)系可以用表之間的內(nèi)連接來(lái)表示。

具體地說(shuō)，首先轉(zhuǎn)換子模式，得到SQL 查詢(xún)trans（m.leftchild，G）的結(jié)果集合R1 和trans（m.rightchild，G）的結(jié)果集合R2；然后根據(jù)m.leftchild和m.rightchild之間的AND 關(guān)系，對(duì)結(jié)果關(guān)系表R1和R2進(jìn)行內(nèi)連接操作。

下面給出組圖模式到SQL 轉(zhuǎn)換的函數(shù)trans（m，AND，G）。連接條件設(shè)定為“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”代表兩個(gè)關(guān)系表之間的自然連接條件，“m.leftchild.a is null”代表的是當(dāng)m.leftchild中含有可選圖模式時(shí)，變量？a未被綁定的情況。

函數(shù)：trans（m，AND，G）

輸入：組圖模式m，RDF數(shù)據(jù)集G

輸出：SQL查詢(xún)

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語(yǔ)言的轉(zhuǎn)換

可選圖模式由OPTIONAL 子句構(gòu)成，其功能是對(duì)OPTIONAL 子句內(nèi)的圖模式可選匹配，如果匹配失敗，就用NULL來(lái)代替變量綁定。在關(guān)系代數(shù)中，這種選擇的概念可以用左連接體現(xiàn)。

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

嵌套 OPTIONAL 子句是指在一個(gè)OPTIONAL 子 句 中 還 包 含 至 少 一 個(gè)OPTIONAL 子句。嵌套OPTIONAL 子句的轉(zhuǎn)換方式為：先使用基本圖模式進(jìn)行查詢(xún)，然后再將得出的關(guān)系表與整個(gè)嵌套OPTIONAL子句的查詢(xún)結(jié)果進(jìn)行左連接操作。

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

例2 （平行OPTIONAL 子句）給定一個(gè)包含平行OPTIONAL子句的SPARQL查詢(xún)?nèi)缦拢?/p>

01 SELECT？a，？n，？ew

02 WHERE｛

03 ｛？a name？n.｝

04 OPTIONAL｛？a email？ew.｝

05 OPTIONAL｛？a web？ew.｝

06 ｝

此查詢(xún)共包含三個(gè)基本圖模式gp1、gp2、gp3，分別在第03、04、05行內(nèi)。對(duì)應(yīng)的圖模式查詢(xún)結(jié)果分別為：R1（a，n），R2（a，ew），R3（a，ew）。

首先，gp1與gp2的查詢(xún)結(jié)果合并表示為：

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

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

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

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

因?yàn)樵赗res與R3之間存在著兩個(gè)相關(guān)聯(lián)變量？a和？ew。在Rres中變量？a必須綁定，所以在連接條件中需判斷Rres.a＝R3.a。第04 行可選圖模式中變量？ew 如果未被綁定（Rres.ew is NULL），則在第05行的可選圖模式中進(jìn)行綁定操作。

根據(jù)以上對(duì)各種情況的分析，給出OPTIONAL子句到SQL 的轉(zhuǎn)換函數(shù)trans（m，OPT，G）。

函數(shù)：trans（m，OPT，G）

輸入：組圖模式m，RDF數(shù)據(jù)集G

輸出：SQL查詢(xún)

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

該轉(zhuǎn)換方法的原理是：首先利用trans（m，G）將m.leftchild 和m.rightchild 轉(zhuǎn) 換 為SQL 查詢(xún)；然后利用關(guān)系代數(shù)中左連接操作上述SQL 查詢(xún)的結(jié)果表。如果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語(yǔ)言的轉(zhuǎn)換

多圖模式中子模式之間由UNION 關(guān)鍵字連接，表示滿(mǎn)足任一子模式的查詢(xún)結(jié)果都是多圖模式的查詢(xún)結(jié)果。文獻(xiàn)［4］為解決UNION 多圖模式到基本圖模式的方法，引入了操作符。該操作符對(duì)結(jié)果關(guān)系表的操作用關(guān)系代數(shù)的形式表示如下：

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

在處理多表連接操作時(shí)，連接條件設(shè)定為false，目的是只進(jìn)行兩表屬性列的合并，屬性值不參與表的合并，使得生成兩個(gè)關(guān)系表的屬性結(jié)構(gòu)相同，能夠直接執(zhí)行SQL中的UNION 操作。該處理方法可以用函數(shù)trans（m，UNION，G）表示。

函數(shù)：trans（m，UNION，G）

輸入：組圖模式m，RDF數(shù)據(jù)集G

輸出：SQL查詢(xún)

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

LEFT OUTER JOIN”＋

trans（m.rightchild，G）＋”O(jiān)n（false））”

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

LEFT OUTER JOIN”＋

trans（m.leftchild，G）＋”O(jiān)n（false））”＋”AS

T＿”＋（＋＋j）

02 return query

3 結(jié)果修飾符與其他查詢(xún)模式

SPARQL語(yǔ)言包含多個(gè)結(jié)果修飾符和查詢(xún)模式，影響結(jié)果返回的形式和順序。在轉(zhuǎn)換過(guò)程中，需要將這些結(jié)果修飾符和查詢(xún)模式映射到SQL語(yǔ)言中相應(yīng)的關(guān)鍵字。

3.1 結(jié)果修飾符到SQL的映射

3.1.1 相同關(guān)鍵字結(jié)果修飾符的映射

SPARQL 中 結(jié) 果 修 飾 符 DISTINCT、ORDER BY、LIMIT n 和OFFSET m 在SQL中同樣存在，且用法和功能相同，因此可以直接映射。當(dāng)SPARQL 查詢(xún)中出現(xiàn)這些關(guān)鍵字時(shí)，在SQL查詢(xún)中SELECT 關(guān)鍵字后添加該關(guān)鍵字即可。

3.1.2 FILTER 到SQL的映射

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

當(dāng)SPARQL 查詢(xún)中出現(xiàn)FILTER 關(guān)鍵字時(shí)，只需在轉(zhuǎn)換后的SQL 查詢(xún)的WHERE 條件集合中添加FILTER 內(nèi)的限制條件即可。當(dāng)變量出現(xiàn)在關(guān)系表中時(shí)，在WHERE 中添加對(duì)變量值的約束。另外需要考慮的是其中涉及到的數(shù)據(jù)類(lèi)型的轉(zhuǎn)換，以及String字符串的轉(zhuǎn)換和比較操作。

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

3.2 SPARQL查詢(xún)模式轉(zhuǎn)換

SPARQL查詢(xún)語(yǔ)言中包含著四種查詢(xún)模式：SELECT、CONSTRUCT、DESCRIBE和ASK。

3.2.1 SELECT 查詢(xún)模式轉(zhuǎn)換方法

首先定義包含SELECT 查詢(xún)模式的SPARQL查詢(xún)Q＝｛Ssel，G，Tree｝，其中Ssel表示查詢(xún)變量集合；G 代表SPARQL查詢(xún)中指定的RDF圖；參數(shù)Tree就是包含了所有圖模式和限定約束條件的SPARQL結(jié)構(gòu)樹(shù)的根節(jié)點(diǎn)。

SELECTtoSQL 算法的主要思想是：根據(jù)WHERE中包含的圖模式，分別對(duì)每個(gè)圖模式進(jìn)行轉(zhuǎn)換，得到相應(yīng)的SQL 子查詢(xún)，然后根據(jù)各個(gè)圖模式之間的邏輯關(guān)系，將得到的SQL子查詢(xún)按照不同的連接形式添加到最終的FROM 源表約束中。

算法：SELECTtoSQL

輸入：SPARQL查詢(xún)Q＝｛Ssel，G，Tree｝

輸出：SQL查詢(xún)

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

02 for 先序遍歷SPARQL 結(jié)構(gòu)樹(shù)Tree中的每個(gè)節(jié)點(diǎn)m

03 if m 為基本圖模式（組圖模式）節(jié)點(diǎn)then trans（m，AND，G）

04 if m 為可選圖模式節(jié)點(diǎn)then trans（m，OPT，G）

05 if m 為多圖模式節(jié)點(diǎn)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 表示條件約束條件集合。算法使用子查詢(xún)生成的關(guān)系表作為源數(shù)據(jù)表，也就是將query查詢(xún)生成的關(guān)系表作為FROM 中的數(shù)據(jù)源部分。因?yàn)榻M圖模式是由基本圖模式通過(guò)AND 連接而成，第03行對(duì)基本圖模式的判斷和對(duì)組圖模式的判斷合并在一起。R 作為一個(gè)臨時(shí)關(guān)系表用于存儲(chǔ)基本圖模式轉(zhuǎn)換后的查詢(xún)結(jié)果。第04行和05行分別是對(duì)可選圖模式和多圖模式進(jìn)行處理。第07至10行形成了select需要投影的屬性列集合。最后第12行對(duì)結(jié)果關(guān)系表進(jìn)行投影操作，選擇在Ssel中出現(xiàn)并且以其中的變量名命名的屬性列，最終返回V，完成SELECT 查詢(xún)。

3.2.2 CONSTRUCT 查詢(xún)模式轉(zhuǎn)換

CONSTRUCT 查詢(xún)模式按照用戶(hù)指定的圖模板返回一個(gè)RDF圖，其中查詢(xún)結(jié)果置換圖模板中的變量。

CONSTRUCT 查詢(xún)模式會(huì)先按照WHERE約束條件對(duì)數(shù)據(jù)集進(jìn)行查詢(xún)操作，然后將結(jié)果以CONSTRUCT 中指定的RDF 三元組形式輸出。由于RDF圖存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中，所以只能用關(guān)系表近似地表示作為查詢(xún)結(jié)果的RDF圖。

將CONSTRUCT 查詢(xún)轉(zhuǎn)換為SQL 查詢(xún)的主要思想是：以RDF圖G 和Tree結(jié)構(gòu)樹(shù)的根節(jié)點(diǎn)作為參數(shù)調(diào)用SELECTtoSQL 算法，返回CONSTRUCT 中要求的變量綁定。為了使關(guān)系表包含CONSTRUCT 中的所有屬性，包括常量屬性列和變量屬性列，需要對(duì)擁有變量屬性列的關(guān)系表和擁有常量屬性列的關(guān)系表進(jìn)行笛卡爾積操作。針對(duì)形成的全屬性列關(guān)系表，根據(jù)CONSTRUCT 中出現(xiàn)的每個(gè)基本圖模式的屬性結(jié)構(gòu)，投影出相應(yīng)的屬性列，并把相應(yīng)的元組加入到結(jié)果關(guān)系表中。最后，依據(jù)元組所屬圖和元組的主語(yǔ)使用GROUP BY 關(guān)鍵字對(duì)結(jié)果關(guān)系表的元組進(jìn)行分組排序，將結(jié)果集返回給用戶(hù)。上述轉(zhuǎn)換思想形式化表示為以下算法：

算法：CONSTRUCTtoSQL

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

輸出：SQL query result

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

02 設(shè)Ssel為Sty中要求表示的變量集合

03 CREATE VIEW V／＊建立視圖V 作為結(jié)果關(guān)系表＊／

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

05 Y＝Y(jié)×X ／＊兩個(gè)關(guān)系表的笛卡爾積＊／

06 for Sty中每個(gè)gpi

07 確定該圖模式的屬性結(jié)構(gòu)

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

09 對(duì)V 中的元組進(jìn)行分類(lèi)（GROUP BY（res，s））

10 return V

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

3.2.3 DESCRIBE查詢(xún)模式轉(zhuǎn)換

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

算法：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 中的每個(gè)變量綁定xi

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

08 for V 中的每個(gè)記錄行提取出謂詞pi和賓語(yǔ)oi

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

10 根據(jù)res和s進(jìn)行結(jié)果排序

11 return V

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

3.2.4 ASK 查詢(xún)模式轉(zhuǎn)換

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

算法：ASKtoSQL

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

輸出：BOOLEAN（true／false）

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

02 return true

03 else

04 return false

3.3 SPARQL查詢(xún)到SQL查詢(xún)的實(shí)現(xiàn)方法

綜上，給出SPARQLtoSQL 算法，該算法根據(jù)不同查詢(xún)模式，分別作出不同函數(shù)調(diào)用，實(shí)現(xiàn)任一SPARQL查詢(xún)到SQL查詢(xún)的轉(zhuǎn)換。

算法：SPARQLtoSQL

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

輸出：結(jié)果關(guān)系表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 實(shí)驗(yàn)及結(jié)果分析

根據(jù)上述分析，實(shí)現(xiàn)了SPARQLtoSQL查詢(xún)轉(zhuǎn)換系統(tǒng)，以Wine本體作為實(shí)驗(yàn)數(shù)據(jù)對(duì)系統(tǒng)進(jìn)行評(píng)測(cè)，選擇12個(gè)具有代表性的SPARQL 查詢(xún)作為輸入（如表1所示），并對(duì)實(shí)驗(yàn)結(jié)果與其他兩種 現(xiàn) 有 的 轉(zhuǎn) 換 方 法 SparqlTOSql［4］和FlatSqlJoinMySQL［5］進(jìn)行了分析和比較。

表1 查詢(xún)實(shí)例Table 1 Query examples

圖1給出了三種不同查詢(xún)策略的查詢(xún)響應(yīng)時(shí)間。查詢(xún)響應(yīng)時(shí)間是指從輸入SPARQL查詢(xún)，經(jīng)過(guò)查詢(xún)轉(zhuǎn)換，到查找出滿(mǎn)足匹配條件的RDF數(shù)據(jù)所用的時(shí)間。由于前兩種方法不支持Q9到Q12的查詢(xún)模式，所以不對(duì)這四個(gè)查詢(xún)實(shí)例的查詢(xún)響應(yīng)時(shí)間做對(duì)比。由圖可知本文提出的查詢(xún)轉(zhuǎn)換策略的查詢(xún)響應(yīng)時(shí)間最短。與FlatSqlJoinMySQL方法相比，由于該方法使用的方法是延續(xù)SparqlToSql方法中的多次轉(zhuǎn)換多次查詢(xún)的策略，所以與本文提出的多次轉(zhuǎn)換一次查詢(xún)的方法相比查詢(xún)響應(yīng)時(shí)間略長(zhǎng)。

圖1 查詢(xún)響應(yīng)時(shí)間對(duì)比圖Fig.1 The query response time of different systems

5 結(jié)束語(yǔ)

本文提出了SPARQL查詢(xún)到SQL查詢(xún)的轉(zhuǎn)換方法，給出了圖模式、結(jié)果修飾符和不同查詢(xún)模式到SQL 的轉(zhuǎn)換規(guī)則，構(gòu)建了SPARQLtoSQL查詢(xún)轉(zhuǎn)換系統(tǒng)。以往轉(zhuǎn)換算法通常采用邊轉(zhuǎn)換邊執(zhí)行的方式，導(dǎo)致轉(zhuǎn)換耗時(shí)、效率低。本文采用一次轉(zhuǎn)換再執(zhí)行的方式，顯著提高了轉(zhuǎn)換效率。

［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，F(xiàn)otouhi 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］吳濤.語(yǔ)義網(wǎng)本體查詢(xún)語(yǔ)言轉(zhuǎn)換技術(shù)的研究與實(shí)現(xiàn)［D］.北京：北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，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］雷云飛，黃劉生，陳國(guó)良.RDF 查詢(xún)語(yǔ)言到SQL 語(yǔ)言的轉(zhuǎn)換原理及其實(shí)現(xiàn)方法［J］.計(jì)算機(jī)研究與發(fā)展，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］王進(jìn)鵬，張亞非，苗壯.SPARQL 查詢(xún)的關(guān)系代數(shù)表示與轉(zhuǎn)換方法［J］.計(jì)算機(jī)工程與應(yīng)用，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.