一種基于樹搜索的RDF查詢算法

劉江江，董榮勝

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004)

資源描述框架(resource description framework, 簡稱RDF)是由國際萬維網(wǎng)聯(lián)盟(W3C)提出的對萬維網(wǎng)上信息進(jìn)行描述的推薦標(biāo)準(zhǔn)[1]，被廣泛應(yīng)用到社交網(wǎng)絡(luò)、生命科學(xué)和科學(xué)研究等各種領(lǐng)域[2]，如文獻(xiàn)[3-5]都使用RDF表示它們的元數(shù)據(jù)。隨著語義網(wǎng)關(guān)系抽取技術(shù)的發(fā)展，單個(gè)RDF數(shù)據(jù)集已達(dá)到億級三元組規(guī)模，如何提高RDF的查詢性能已經(jīng)受到了工業(yè)界和學(xué)術(shù)界的普遍關(guān)注。目前，基于關(guān)系數(shù)據(jù)庫的存儲(chǔ)模式(如TripleBit[6]等)在查詢時(shí)存在大量的自連接操作等問題；基于基本三元組(如RDF-3X[7]等)的存儲(chǔ)模式采用了窮舉的方式建立索引，在查詢時(shí)存在內(nèi)存空間消耗較大的問題?；趫D的查詢技術(shù)(如gStore[8-9]、TurboHOM++[10]、AMBER[11]等)是指將RDF數(shù)據(jù)和SPARQL建模為圖，從而將RDF的查詢轉(zhuǎn)化為圖匹配問題中的子圖同態(tài)問題[12]，該問題已經(jīng)被證明為一個(gè)NP完全問題[13]。

Bonnici等[14]在2013年提出了一種子圖同構(gòu)算法RI，該算法顯示出良好的查詢性能。與傳統(tǒng)的子圖匹配算法相比，SPARQL查詢中包含變量，傳統(tǒng)的子圖匹配算法無法有效解決RDF查詢問題。鑒于此，在RI算法基礎(chǔ)上提出一種RDF查詢算法RI-Triples：1)用4種變量節(jié)點(diǎn)索引來減少變量節(jié)點(diǎn)的候選域。2)采用一種基于貪心思想的靜態(tài)的查詢圖節(jié)點(diǎn)排序策略，為查詢圖生成一個(gè)節(jié)點(diǎn)匹配序列。在匹配過程中，該匹配序列能夠提前引入更多的約束條件以修剪不匹配的分支，而無需使用任何復(fù)雜修剪規(guī)則。3)采用RDF測試基準(zhǔn)LUBM[15]進(jìn)行實(shí)驗(yàn)，分別從搜索空間和查詢時(shí)間對RI-Triples算法進(jìn)行分析。實(shí)驗(yàn)結(jié)果表明，RI-Triples具有良好的擴(kuò)展性和查詢性能。

1 相關(guān)基礎(chǔ)知識

定義1有向標(biāo)簽圖可定義為一個(gè)六元組G=〈V,Lv,Mv,E,Le,Me〉,其中V表示節(jié)點(diǎn)的集合，E∈(V×V)表示邊的集合，Lv表示節(jié)點(diǎn)標(biāo)簽集合，Le表示邊標(biāo)簽的集合，Mv表示節(jié)點(diǎn)到標(biāo)簽的映射函數(shù)：V→Lv，Me表示邊到標(biāo)簽的映射函數(shù)：E→Le[16]。

定義3在子圖匹配中，搜索空間樹(search space tree，簡稱SST)用來表示查詢圖中的節(jié)點(diǎn)到數(shù)據(jù)圖中的節(jié)點(diǎn)所有可能映射的集合。SST有一個(gè)虛擬根，每個(gè)可能的匹配序列被稱為一個(gè)分支。分支中的每個(gè)節(jié)點(diǎn)(ui,vi)表示查詢圖中的節(jié)點(diǎn)ui與數(shù)據(jù)圖的節(jié)點(diǎn)vi之間的一個(gè)可能匹配。

SST的一個(gè)實(shí)例如圖1所示。在查詢圖中標(biāo)簽為{*}的是變量節(jié)點(diǎn)，可以匹配數(shù)據(jù)圖中的任何一個(gè)節(jié)點(diǎn)。在圖1(c)、(d)中，標(biāo)記為虛線的分支為滿足子圖同態(tài)的一個(gè)實(shí)例，序列μ1對應(yīng)的搜索空間為3，而序列μ2對應(yīng)的搜索空間為6。

圖1 搜索空間樹實(shí)例

2 將RDF和SPARQL建模為圖

每條RDF三元組數(shù)據(jù)可以形式化表示為〈S,P,O〉，其中S、P、O分別為主語或資源、謂語或?qū)傩?、賓語或?qū)傩灾?。RDF中的主語和謂語通常使用統(tǒng)一資源標(biāo)識符(uniform resource identifier，簡稱URI)進(jìn)行標(biāo)識，賓語使用URI或者文字(Literal)進(jìn)行標(biāo)識[17]。RDF數(shù)據(jù)實(shí)例如表1所示。

表1 RDF數(shù)據(jù)

RDF數(shù)據(jù)中的主語和賓語可被視為節(jié)點(diǎn)，謂語可被視為有向邊。因此，RDF數(shù)據(jù)可建模為一個(gè)有向標(biāo)簽圖，其構(gòu)建過程如定義4所示。

定義4RDF數(shù)據(jù)圖可定義為一個(gè)六元組。

1)V=Vc∪Ve∪Vl，表示RDF數(shù)據(jù)中的主語和賓語對應(yīng)的節(jié)點(diǎn)組成的集合。其中：Vc為類的集合；Ve為實(shí)體的集合；Vl為文字的集合。

2)Lv表示節(jié)點(diǎn)的標(biāo)簽集合。若節(jié)點(diǎn)v∈Vl，則節(jié)點(diǎn)標(biāo)簽對應(yīng)的是文字；若節(jié)點(diǎn)v∈Vc∪Ve，則節(jié)點(diǎn)標(biāo)簽對應(yīng)的是URI。

3)Mv∶V→Lv，表示節(jié)點(diǎn)到標(biāo)簽的雙射函數(shù)。

4)E={〈vi,vj〉}，表示連接主語和賓語對應(yīng)的節(jié)點(diǎn)的有向邊的集合。

5)Le表示邊的標(biāo)簽的集合。

6)Me:E→Le,表示邊到標(biāo)簽的雙射函數(shù)。

將表1的RDF數(shù)據(jù)建模為RDF數(shù)據(jù)圖。在構(gòu)建過程中，構(gòu)建并維護(hù)2個(gè)哈希表，分別為節(jié)點(diǎn)映射表vHash和邊映射表eHash，如表2、3所示。將主語和賓語映射到節(jié)點(diǎn)，將謂語映射為邊的標(biāo)簽。圖2為RDF數(shù)據(jù)圖。

表2 節(jié)點(diǎn)映射表

表3 邊映射表

圖2 RDF數(shù)據(jù)圖

SPARQL[18]是W3C推薦的RDF標(biāo)準(zhǔn)查詢語言，它與SQL的語法相似，SPARQL查詢的一個(gè)實(shí)例如下：

select ?x ?y ?z

where{

?x emailAddress ?z.

?x memberOf ?y.

?x type Student.

?y subOrganizationOf University0.

?y type Department}

其中，select子句指明要返回結(jié)果的變量，where子句指明查詢條件。在實(shí)際應(yīng)用中，查詢中通常很少出現(xiàn)謂語為變量的情況，因此，僅關(guān)注主語和賓語為變量的情況及select/where基本操作。查詢圖構(gòu)建過程如定義5所示。

4)EQ={〈ui,uj〉}為連接連主語和賓語對應(yīng)節(jié)點(diǎn)的有向邊的集合。

SPARQL查詢圖的構(gòu)建過程和RDF數(shù)據(jù)圖相似，查詢圖中常量節(jié)點(diǎn)標(biāo)簽可通過節(jié)點(diǎn)映射表vHash獲得，而邊標(biāo)簽可通過邊映射表eHash獲得。在查詢圖中，標(biāo)簽為{*}的節(jié)點(diǎn)可匹配數(shù)據(jù)圖中的任何一個(gè)節(jié)點(diǎn)。圖3為SPARQL查詢對應(yīng)的查詢圖。

圖3 SPARQL查詢圖

3 RI-Triples算法

3.1 索引

在SPARQL查詢圖中，對一個(gè)變量節(jié)點(diǎn)u0而言，通常有以下4種組合方式：

1)變量節(jié)點(diǎn)u0存在入射邊，與之相連的是一個(gè)常量節(jié)點(diǎn)u1；

2)變量節(jié)點(diǎn)u0存在入射邊，與之相連的是一個(gè)變量節(jié)點(diǎn)u2；

3)變量節(jié)點(diǎn)u0存在出射邊，與之相連的是一個(gè)常量節(jié)點(diǎn)u3；

4)變量u0存在出射邊，與之相連的是一個(gè)變量節(jié)點(diǎn)u4。

采用鄰接表的方式存儲(chǔ)RDF數(shù)據(jù)圖，對于組合1)，通過訪問常量節(jié)點(diǎn)u1的鄰接表以減小變量節(jié)點(diǎn)u0的候選域。對于組合3)，采用冗余存儲(chǔ)的方式構(gòu)造了逆鄰接表以減少變量節(jié)點(diǎn)u0的候選域。對于組合2)和4)，分別構(gòu)建與邊ei標(biāo)簽相關(guān)的終止和起始節(jié)點(diǎn)的集合

P-Out(ei)={vj|〈vi,vj〉∈E,

和

P-In(ei)={vi|〈vi,vj〉∈E,

若變量節(jié)點(diǎn)u0至少存在以上2種索引，則將節(jié)點(diǎn)相關(guān)索引的最小候選域作為該變量的最終候選域。

3.2 查詢圖節(jié)點(diǎn)排序

如圖2所示，在匹配過程中，一個(gè)良好的查詢圖節(jié)點(diǎn)匹配順序有利于顯著減少搜索空間,從而提高查詢速度。在查詢圖節(jié)點(diǎn)的排序過程中，基于貪心思想,查詢圖輸出一個(gè)按照約束大小排序的節(jié)點(diǎn)匹配序列μ，因此，在匹配階段能提前修剪不滿足的分支。

對于查詢圖初始節(jié)點(diǎn)的選擇，每個(gè)查詢圖節(jié)點(diǎn)u計(jì)算得分為

其中：CR(u)為節(jié)點(diǎn)u的最小候選域；avgdeg(CR(u))為節(jié)點(diǎn)u的候選節(jié)點(diǎn)的平均度；deg(u)為節(jié)點(diǎn)u的度。首先，從起始節(jié)點(diǎn)的候選集合中移除僅有一個(gè)鄰居的變量節(jié)點(diǎn)，且該鄰居節(jié)點(diǎn)仍為變量節(jié)點(diǎn)。原因在于,選擇這類節(jié)點(diǎn)不會(huì)減小其鄰居變量節(jié)點(diǎn)的候選域，違反了最大約束優(yōu)先原則。若候選集非空，則選擇該集合中得分最低的節(jié)點(diǎn)作為初始節(jié)點(diǎn)；若候選集為空，則該SPARQL查詢中只包含一個(gè)主語和賓語都為變量的三元組，仍選擇得分最低的節(jié)點(diǎn)作為初始節(jié)點(diǎn)。

在查詢圖節(jié)點(diǎn)排序過程中，將有向邊視為無向邊。假設(shè)查詢圖當(dāng)前部分節(jié)點(diǎn)的匹配序列為μ=(u0,u1,…,um-1)，um是下一個(gè)待插入的候選節(jié)點(diǎn)。在節(jié)點(diǎn)排序的過程中，提出邊驗(yàn)證集的概念，表示數(shù)據(jù)圖中um的候選節(jié)點(diǎn)和ui的候選節(jié)點(diǎn)之間所存在的邊，其中ui∈μ且um為ui的鄰居節(jié)點(diǎn)。

1)若ui、um為常量節(jié)點(diǎn)，則只需在數(shù)據(jù)圖中驗(yàn)證邊(vi,vm)一次，邊(ui,um)驗(yàn)證集的大小為1。

2)若ui為變量節(jié)點(diǎn)，um為常量節(jié)點(diǎn)(或ui為常量節(jié)點(diǎn)，um為變量節(jié)點(diǎn))，邊(ui,um)驗(yàn)證集的大小為數(shù)據(jù)圖中節(jié)點(diǎn)vm(或vi)與其鄰居節(jié)點(diǎn)之間的邊標(biāo)簽為L(ui,um)的邊的數(shù)量。

3)若ui、um為變量節(jié)點(diǎn)，邊(ui,um)驗(yàn)證集的大小為數(shù)據(jù)圖中標(biāo)簽為L(ui,um)的邊的數(shù)量。

排序算法迭代執(zhí)行直到所有的節(jié)點(diǎn)都被插入μ中。在排序過程中，使用以下規(guī)則為um的每個(gè)候選節(jié)點(diǎn)計(jì)算得分：

1)Vm,vis={ui:(ui,um)∈EQ,0≤i

2)Vm,neig={uj:(ui,uj)∈EQ,(um,uj)∈EQ,0≤im}，表示與um相連且與集合μ內(nèi)至少有一個(gè)節(jié)點(diǎn)相連的節(jié)點(diǎn)集合。

3)Vm,ver=min{P(ui,um):ui∈μ}，計(jì)算節(jié)點(diǎn)驗(yàn)證集。

4)Vm,unv={uj:(um,uj)∈EQ,(ui,uj)?EQ,0≤im}，表示不在集合μ中，也不與集合中μ的任意頂點(diǎn)相連，但與節(jié)點(diǎn)um相連的節(jié)點(diǎn)集合。

假設(shè)ua、ub為um的2個(gè)候選節(jié)點(diǎn)，依次比較候選節(jié)點(diǎn)在Vm.vis、Vm.neig、Vm.ver和Vm.unv的得分。選擇規(guī)則如下：

1)|Va,vis|>|Vb,vis|；

2)|Va,vis|=|Vb,vis|,|Va,neig|>|Vb,nieg|；

3)|Va,vis|=|Vb,vis|,|Va,neig|=|Vb,neig|,|Va,ver|<|Vb,ver|；

4)|Va,vis|=|Vb,vis|,|Va,neig|=|Vb,neig|,|Va,ver|=|Vb,ver|,|Va,unv|<|Vb,unv|。

若滿足當(dāng)前選項(xiàng)，則選擇ua作為當(dāng)前最優(yōu)候選節(jié)點(diǎn)，否則繼續(xù)判斷下一項(xiàng)。若ua和ub具有相同的得分，則任意選擇一個(gè)節(jié)點(diǎn)作為最優(yōu)候選節(jié)點(diǎn)。算法流程如下：

算法1查詢圖節(jié)點(diǎn)排序算法

輸入：查詢圖Q，數(shù)據(jù)圖G

輸出：節(jié)點(diǎn)匹配序列μ，序列μ中節(jié)點(diǎn)的父節(jié)點(diǎn)序列μpt

1.u0=getStartVertex(G, Q);//選擇起始節(jié)點(diǎn)

2.addu0toμand removeu0fromV;

3.for(m=1 ton)do//n為查詢圖節(jié)點(diǎn)數(shù)量

4.CR(um)={u:u∈neig(um),u?μ};

5.Om=[0,0,0,0];//初始化um最優(yōu)得分序列

6.for(eachu∈CR(um))do//為um的每個(gè)候選節(jié)點(diǎn)計(jì)算得分序列，選出最優(yōu)候選節(jié)點(diǎn)

7.Vm,vis={ui:(ui,um)EQ, 0≤i

8.Vm,neig={uj:(ui,uj)EQ,(um,uj)EQ,0≤im};

9.Vm,ver=min{P(ui,um):ui∈μ};

10.Vm,unv={uj:(um,uj)EQ,(ui,uj)?EQ,0≤im};

11.ifOm≤[|Vm,vis|,|Vm,neig|,Nm,ver,|Vm,unv|]then//Nm,ver為集合Vm,ver的大小的倒數(shù)

12.um=u;

13.Om=[|Vm,v i s|,|Vm,neig|,Nm,ver,|Vm,unv|];

14.end if

15. end for

16. insertumto μ;

17. insert pt(um)to μpt;//計(jì)算與um具有最小邊驗(yàn)證集的節(jié)點(diǎn)ui插入序列μpt中

18.end for

19.return μ and μpt

3.3 查詢匹配

在匹配過程中，通過查詢圖節(jié)點(diǎn)匹配序列和RDF數(shù)據(jù)圖可構(gòu)造出一顆搜索空間樹。采用深度優(yōu)先策略對搜索空間樹進(jìn)行遍歷，并修剪搜索空間樹中不滿足子圖同態(tài)約束的分支。假設(shè)當(dāng)前分支M={(u0,v0),(u1,v1),…,(um-1,vm-1)}，(um,vm)為待插入節(jié)點(diǎn)，其中vi=Mhom(ui)，0≤i

2)候選節(jié)點(diǎn)vm的入度和出度大于等于um的入度和出度，即|neig-(um)|≤|neig-(vm)|,|neig+(um)|≤|neig+(vm)|。

若當(dāng)前分支所有節(jié)點(diǎn)都滿足子圖同態(tài)約束，則該分支為一個(gè)完整匹配序列。依次遍歷搜索空間樹的每個(gè)分支，可得到RDF數(shù)據(jù)圖中與SPARQL查詢圖滿足子圖同態(tài)約束的所有匹配序列。

4 實(shí)驗(yàn)

RI-Triples算法用C++實(shí)現(xiàn)，實(shí)驗(yàn)運(yùn)行在Ubuntu1 6.04 LTS，硬件平臺(tái)為Inter(R)Core(TM)i5-4590 CPU 3.30 GHz，運(yùn)行內(nèi)存為16 GiB。

實(shí)驗(yàn)采用基于圖存儲(chǔ)和基本三元組的典型代表算法gStore和RDF-3X作為對比。實(shí)驗(yàn)采用RDF測試基準(zhǔn)LUBM，其提供了數(shù)據(jù)生成器和14個(gè)查詢模板，用LUBM數(shù)據(jù)生成器生成LUBM6M、LUBM13M、LUBM33M三個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的具體信息如表4所示。

表4 RDF數(shù)據(jù)集信息

表5為在LUBM6M、LUBM13M和LUBM33M數(shù)據(jù)集上每個(gè)查詢對應(yīng)的答案數(shù)量。查詢Q1、Q3～Q5、Q7、Q8、Q10～Q13在不同的數(shù)據(jù)集有相同數(shù)量的答案，與數(shù)據(jù)集的大小無關(guān)，這些查詢通常被稱為常量路徑查詢。而查詢Q2、Q6、Q9、Q14的答案數(shù)量隨著數(shù)據(jù)集的增大而線性增大，這些查詢通常被稱為增量路徑查詢。

表5 LUBM數(shù)據(jù)集中每個(gè)查詢的答案數(shù)量

表6為RI_Triples算法在每個(gè)LUBM數(shù)據(jù)集上執(zhí)行不同查詢時(shí)的搜索空間。從表6可看出，常量路徑查詢在不同的數(shù)據(jù)集上具有相同的搜索空間，而增量路徑查詢的搜索空間隨著數(shù)據(jù)集的增大呈線性增長。

表6 LUBM中每個(gè)查詢的搜索空間

表7為gStore、RDF-3X和RI-Triples算法在每個(gè)LUBM數(shù)據(jù)集上執(zhí)行查詢的時(shí)間。分別統(tǒng)計(jì)每個(gè)算法在不同的LUBM數(shù)據(jù)集的常量路徑查詢之和，可以得出，在LUBM6M、LUBM13M和LUBM33M數(shù)據(jù)集上，RI-triples的常量路徑查詢時(shí)間分別為gStore的0.35、0.11和0.24倍，為RDF-3X的0.29、0.10和0.24倍。在常量路徑查詢中，通常至少包含一個(gè)實(shí)體節(jié)點(diǎn)，這些查詢的候選域不會(huì)隨著數(shù)據(jù)集大小而變化。對于常量路徑查詢，RI-triples在不同的數(shù)據(jù)集上具有相同的查詢圖節(jié)點(diǎn)匹配順序，因此，在不同的數(shù)據(jù)集上具有相同的搜索空間和近似的查詢時(shí)間。

表7 gStore、RDF-3X和RI-Triples在LUBM數(shù)據(jù)集上查詢時(shí)間

對于增量路徑查詢，查詢的候選域隨著數(shù)據(jù)集的增大而增大。對于查詢Q6、Q14，RI-triples的查詢時(shí)間分別為gStore的0.24～0.34倍，為RDF-3X的0.08～0.10倍。對于查詢Q9，在LUBM6數(shù)據(jù)集中，RI-Triples查詢速度略慢于gStore，在LUBM13M和LUBM33M數(shù)據(jù)集中，RI-Triples的查詢時(shí)間分別為gStore的0.42、0.85倍，為RDF-3X的0.39、0.44倍。對于查詢Q2，在LUBM6M數(shù)據(jù)集上，RI-triples的查詢效率更高；在LUBM13M數(shù)據(jù)集上，gStore查詢得更快，RI-triples次之；在LUBM33M數(shù)據(jù)集上，RI-triples的查詢時(shí)間慢于gStore和RDF-3X。

對于常量路徑查詢，RI-Triples在不同的LUBM數(shù)據(jù)集上有近似的查詢時(shí)間，而對于增量路徑查詢，RI-Triples查詢時(shí)間隨著數(shù)據(jù)集增大而線性增大。因此，RI-Triples算法具有良好的擴(kuò)展性。在以上的查詢中，與gStore和RDF-3X算法相比，RI-Triples算法具有較高的查詢效率。

5 結(jié)束語

提出了一種基于樹搜索的RDF查詢算法RI-Triples，采用一種輕量級索引以減小查詢圖變量節(jié)點(diǎn)的候選域，基于貪心策略按照約束大小為查詢圖輸出一個(gè)節(jié)點(diǎn)匹配序列。實(shí)驗(yàn)結(jié)果表明，RI-Triples具有良好的擴(kuò)展性，能夠有效回答大規(guī)模RDF查詢問題。未來將針對RDF查詢中謂語為變量的情況及關(guān)鍵詞查詢的Top-k查詢等問題進(jìn)行進(jìn)一步的研究。