關皓元，朱 斌，李冠宇，趙 玲

(大連海事大學 信息科學技術學院，遼寧 大連 116026)(*通信作者電子郵箱rabitlee@163.com)

0 引言

資源描述框架(Resource Description Framework, RDF)是經(jīng)W3C認證的用來描述語義Web中機器信息的標準數(shù)據(jù)模型，SPARQL是面向RDF圖的標準圖查詢語言[1-2]。模式匹配是SPARQL查詢處理中的核心問題，其目的是在復雜的RDF圖數(shù)據(jù)中快速地搜索符合查詢請求的結果。也就是說，面向RDF圖的模式匹配是在RDF數(shù)據(jù)圖中搜索到同構于查詢圖的數(shù)據(jù)子圖的遍歷過程(圖1)，因此，該問題也可以稱為子圖匹配問題[3]。隨著RDF數(shù)據(jù)量不斷地增加，RDF數(shù)據(jù)模型對語義數(shù)據(jù)的表示也更加復雜，由于查詢圖的復雜性以及RDF數(shù)據(jù)的海量性，在查詢處理的過程中時間效率很難得到保證，因此，本文提出一種基于RDF圖結構切分的高效子圖匹配方法。

在關系模型中，一條RDF數(shù)據(jù)被定義為三元組〈s,p,o〉,其中，s(subject)是主題，p(predicate)是謂詞，o(object)是賓語，謂詞表示主題與賓語之間的語義關系。一個RDF數(shù)據(jù)集以圖的形式表示，圖中的頂點表示主題與賓語，而謂詞被映射到連接兩個頂點的有向邊(主題指向賓語)上作為頂點之間語義關系的表示(圖1數(shù)據(jù)圖G)。

在SPARQL查詢中，查詢語句以三元組模式表示，一個三元組模式就是一個限制條件，與三元組類似，但頂點標簽可以是變量(謂詞為變量的情況極其罕見，因此在本文的討論中被忽略)，而一組包含多個限制條件的SPARQL查詢則以查詢圖的形式表示(圖1查詢圖Q)。在簡單的SPARQL查詢中，可以將RDF圖分為3種基本結構[4]，如圖2所示，分別為鏈形結構、環(huán)形結構與星形結構，然而隨著RDF數(shù)據(jù)大量被發(fā)布，SPARQL查詢也隨之變得越來越復雜，一個復雜的RDF圖往往是由以上3種結構交互連接而成的。

圖1 面向RDF圖的模式匹配

圖2 RDF圖的基本結構

RDF圖結構的復雜趨勢也導致了在查詢中節(jié)點的選擇性隨之變差，在圖結構足夠復雜時，也使得子圖匹配問題成為了NP-Complete問題[3]，以上兩點使得面向圖的查詢處理成為了一項艱難的挑戰(zhàn)。RDF- 3X[5]對此作出的對策是將RDF數(shù)據(jù)按照主題、謂詞及賓語的選擇性進行區(qū)分存儲，分別設計了6個三元組表(spo,pos,ops,sop,pso,osp)，但是當數(shù)據(jù)量巨大的時候，表與表之間的跨表連接將產(chǎn)生很高的連接代價。而R3F[6]是將圖形結構分解為以謂詞為基準的路徑，通過RDF數(shù)據(jù)之間的語義關系進行查詢，但是采用將數(shù)據(jù)降維的方法在面向環(huán)路及星形圖結構時，容易導致數(shù)據(jù)信息丟失從而降低了查準率。與上述兩種方法不同的是，GraSS[3]則是從RDF圖結構特征的方面入手，由于星形結構的組成往往是決定RDF圖結構復雜程度的重要因素之一，GraSS將數(shù)據(jù)圖中兩兩相鄰的星形結構的公共節(jié)點作為特征項以建立基于hash編碼的模式索引，但卻忽略了鏈形結構與環(huán)形結構對查詢過程中節(jié)點連接的影響。

基于此，本文通過發(fā)掘查詢圖與RDF數(shù)據(jù)圖的結構與語義信息，建立一種高效地處理模式匹配的方法——RSM(RDF Subgraph Matching)。為了保證數(shù)據(jù)信息不丟失，在該方法中提出了基于分類學思想方法的RDF圖結構切分規(guī)則并按照該規(guī)則將復雜查詢圖切分為多個簡單查詢子圖，以便于降低整個執(zhí)行過程的計算復雜度，其中，查詢子圖的匹配結果之間互相影響，從而提升了RDF數(shù)據(jù)的選擇性。通過對RDF數(shù)據(jù)圖的語義信息的分析，建立了相鄰謂詞結構倒排索引，用來定義查詢子圖的節(jié)點搜索空間，搜索空間中的節(jié)點稱為查詢節(jié)點的綁定節(jié)點。對比以往的單向謂詞路徑索引，本文同時考慮了數(shù)據(jù)圖中的節(jié)點作為主題與賓語的不同謂詞結構，該索引加快了節(jié)點的過濾且因為倒排索引的方便性與高效性，不會導致因為數(shù)據(jù)圖結構復雜而產(chǎn)生巨大搭建代價的后果。在定義了節(jié)點初始搜索空間后，通過相鄰的查詢子圖結構來縮小搜索空間的范圍，在最終確定的搜索空間中尋找到節(jié)點所在的子圖結構并作為查詢子圖的綁定子圖。最后，將幾個綁定子圖進行連接并作為最終結果圖輸出。

本文的主要工作如下：

1)提出了相鄰謂詞結構索引。將數(shù)據(jù)圖中的節(jié)點按照相鄰謂詞結構進行分類存儲，以便于子圖匹配中節(jié)點的過濾。

2)提出了基于中心覆蓋節(jié)點的圖結構切分規(guī)則。通過整數(shù)線性規(guī)劃建模解決最小中心覆蓋集合的選擇問題以確定一個查詢圖中的中心覆蓋節(jié)點集合，按照集合中的中心覆蓋節(jié)點將查詢圖切分為若干查詢子圖。

3)提出了最佳連接順序建模方法，并據(jù)此生成查詢計劃。在中心覆蓋集合確定之后，需要計算查詢子圖與子圖中節(jié)點的處理順序，提出用于計算處理順序的建模方法，并根據(jù)最佳處理順序生成相應的查詢計劃。

4)方法與算法有效性實證的實驗對比分析。采用真實世界數(shù)據(jù)集與合成數(shù)據(jù)集來進行廣泛的實驗來評估RSM方法的適用性與高效性，綜合實驗結果表明RSM的查詢處理性能要高于RDF- 3X、R3F與GraSS[3]。

1 相關工作

子圖匹配也稱為子圖同構問題，對該問題的研究已經(jīng)成為了熱點[7-8]。文獻[9-10]提出了基于啟發(fā)式規(guī)則的三元組模式重排序算法來解決此問題，但是在RDF圖結構十分復雜的情況下，這種將圖轉化為RDF三元組的解決方案的效果并不理想。目前一些主流的方法是通過建立索引結構來解決子圖同構問題。本文按照處理模型將其分為基于三元組的索引與基于圖形結構的索引，詳解如下。

1)基于三元組的索引。RDF- 3X是一種基于關系表的SPARQL查詢引擎。它使用B+樹作為基本索引結構，以三元組〈s,p,o〉中的元素分別作為索引基準與列表排序Key而設計了6種屬性表來分類存儲RDF數(shù)據(jù)，查詢優(yōu)化器將屬性表的統(tǒng)計信息轉換為連接樹，連接樹決定了查詢性能，但是表中的元素自連接與表間的跨表連接會產(chǎn)生較高的查詢代價，隨著數(shù)據(jù)量變大，RDF- 3X的查詢代價成指數(shù)增長。Jena[11]和Sesame[12]通過建立一張大型三元組屬性表來存儲RDF數(shù)據(jù)，在表中同時訪問幾個屬性并將其進行聚類可以加快節(jié)點過濾并減少連接的次數(shù)，最后將結果存儲在單個表中，但是它需要用戶提供聚類決策并保留先前的查詢日志，由于這種大型表的建立并不規(guī)范化，很容易導致連接過程中的控制與屬性重復，從而產(chǎn)生較高的查詢時間與中間結果冗余的情況。

2)基于圖特征的索引。基于圖結構的索引是在三元組的基礎上添加了對于結構的考慮。GRIN(Graph based RDF INdex)[13]使用圖分割技術并參考節(jié)點距離的信息來建立基于圖查詢的索引，索引結構是一個平衡二叉樹，樹中每個節(jié)點代表一個三元組；但是GRIN將索引保存在內存中，當數(shù)據(jù)量較大時，這種存儲方式會產(chǎn)生高昂的代價。在Graph indexing[14]中，作者提出了“辨別比率”來計算子圖的“辨別力”，當該子圖的辨別力“很強”時，便以該子圖作為特征索引。g-index具有較好的過濾性能，但是這種方法具有很高的局限性，它要求子圖具有特點鮮明的結構，當子圖選擇性較差時，處理效果并不明顯。GraSS重點在于處理星形結構的RDF圖，將數(shù)據(jù)圖中星形結構的子圖的公共頂點作為特征項來建立基于hash編碼的模式索引，通過在含有星形結構的查詢圖中搜索符合特征項的頂點來進行子圖過濾，GraSS對于星形結構較多的圖查詢處理是十分高效的，但是當面對數(shù)據(jù)圖或查詢圖為大量的鏈形結構與環(huán)形結構時，則沒有具體應對的方法。RP-filter(RDF Predicate-filter)[15]和R3F采用了將圖形結構分解為路徑信息的索引方案，通過建立謂詞路徑索引將節(jié)點分類存儲，索引是樹形結構，樹中的邊代表路徑，節(jié)點代表謂詞。RDF圖中的節(jié)點通過連接其的不同謂詞分類存儲在節(jié)點列表中；但是，這種方法將圖結構分解為路徑，容易導致原本的信息丟失，并且如果圖結構十分復雜(存在環(huán)路或星形連接)，僅僅依靠謂詞路徑并不能完全過濾掉無用的中間結果。

基于對上述的問題分析，本文提出了基于查詢圖結構切分的子圖匹配方法(RSM)以解決因RDF圖結構復雜而導致RDF查詢圖與數(shù)據(jù)圖中節(jié)點的選擇性變弱從而產(chǎn)生大量中間結果冗余的問題。通過將查詢圖分解為結構相對簡單的查詢子圖來增強子圖與節(jié)點的選擇性，并通過相鄰謂詞結構索引與查詢子圖的相鄰結構加快節(jié)點的過濾過程。在RSM處理過程中所涉及到的相關定義與相鄰謂詞結構索引的建立將在第2章詳細闡述。

2 基本定義與謂詞索引

2.1 數(shù)據(jù)圖與查詢圖

RDF作為一種概念建模的方式，其想法是將關于語義信息的陳述表示為形如主題-謂詞-賓語的三元組(Subject,Predicate,Object)。在關系數(shù)據(jù)庫中，由于謂詞是具有指向性的語義關系詞，RDF數(shù)據(jù)集被抽象為有向圖，稱為數(shù)據(jù)圖，本文對數(shù)據(jù)圖的定義如下。

定義1 數(shù)據(jù)圖。數(shù)據(jù)圖(圖3)是一個RDF圖G=(V,E,L,ψ)。其中：V是查詢圖中的頂點集合，E?V×V代表連接圖中任意兩個頂點的有向邊的集合，L是頂點與邊的標簽的集合，映射函數(shù)ψ:V∪E→L。

圖3 RDF數(shù)據(jù)圖示例

SPARQL的基本訪問模式稱為元組模式，與RDF三元組相同的是，在關系數(shù)據(jù)庫中，元組模式同樣被抽象為有向圖，而不同之處在于主題及賓語可能是變量，本文對于查詢圖的定義如下。

定義2 查詢圖。查詢圖(圖4)可定義為五元組Q=(VQ,EQ,L,ψQ,vars)。其中：VQ表示查詢圖中的頂點集合，EQ?VQ×VQ代表連接兩個頂點的有向邊的集合，L是查詢圖中頂點與邊的標簽集合，映射函數(shù)ψQ:V∪E→L，vars表示圖中變量的集合。

圖4表示的是與圖3中數(shù)據(jù)圖所對應的查詢圖。其中，頂點是變量，〈?v1,p2,?v2〉是一個三元組模式。從圖4中可以看出，數(shù)據(jù)圖中的三元組〈v4,p2,v7〉是三元組模式〈?v1,p2,?v2〉的一個匹配答案，本文將匹配答案稱為綁定，與查詢圖結構匹配的數(shù)據(jù)子圖稱為綁定子圖。

定義3 綁定子圖。查詢圖Q的一個綁定子圖(圖5)B=(VB,EB,L,ψB,S)。其中：滿足Q的單映射函數(shù)f:VB→VQ,且VB?V；映射函數(shù)ψB:VB∪EB→L，L是綁定子圖中頂點與邊上標簽映射的集合；S是查詢子圖中各節(jié)點的搜索空間，VB∈S。

圖4 查詢圖示例

圖5 綁定子圖

2.2 相鄰謂詞結構索引

本文根據(jù)查詢圖與數(shù)據(jù)圖中節(jié)點相鄰謂詞結構來定義查詢圖中節(jié)點的初步搜索空間，并將搜索空間中的節(jié)點稱為綁定節(jié)點。數(shù)據(jù)圖與查詢圖中的節(jié)點相匹配的節(jié)點相鄰謂詞結構必須是相同的。

定義4 綁定節(jié)點。與SPARQL查詢所對應的RDF圖節(jié)點綁定為Ans(Q)={θ|θ(GQ)}，其中GQ是G的子圖同構；對于v∈VQ,Ans(Q,v)是v在Q上的映射，Ans(Q,?v)={θ(v|θ∈Ans(Q)},θ(v)將θ映射到v上;相鄰謂詞結構P(p|v)表示節(jié)點及其傳入(節(jié)點為o)或傳出(節(jié)點為s)謂詞結構。

這里需要注意，因為謂詞具有指向性，數(shù)據(jù)圖中會存在入度或出度為0的節(jié)點，因此本文同時考慮了頂點作為主題與賓語的兩種情況而分別提出了基于傳出和傳入謂詞結構的頂點倒排列表，如表1所示。

表1 基于傳入、傳出謂詞結構的頂點列表

根據(jù)表1中的數(shù)據(jù)可進行查詢圖中節(jié)點的過濾，圖4中節(jié)點?v2的傳入謂詞結構為p2，因此可在表1中找到?v2的搜索空間S1(p2|v3,v6,v7,v12,v15,v18)，而?v2具有傳出謂詞結構p3，在表1中找到?v2的搜索空間S2(p3|v1,v7,v11,v13)，綜合S1和S2將搜索空間壓縮，最后找到符合子圖同構的?v2綁定節(jié)點為v7；同理可得到查詢圖Q中其余頂點的搜索空間為:S(?v1)={v4,v8,v11},S(?v3)={v5,v11},S(?v4)={v8},S(?v5)={v6,v12},S(?v6)={v2,v11,v14,v17},S(?v7)={v3,v6,v7,v12,v15,v18}。

當查詢圖中節(jié)點較多且結構復雜時，一個查詢子圖中的節(jié)點可能存在多個綁定，將查詢圖作為整體進行謂詞結構匹配的方式較為繁瑣，在第3章本文將會介紹基于查詢圖切分的子圖匹配方法，通過查詢子圖的相鄰子圖可以進一步縮小搜索空間。

3 RSM-查詢圖切分方法

3.1 查詢圖結構切分

RSM的核心在于將查詢圖分解為若干個結構簡單的查詢子圖，本文給出的分解規(guī)則如下：選取中心覆蓋節(jié)點，將該節(jié)點及其相鄰節(jié)點劃分為一個查詢子圖，若兩個相鄰節(jié)點與中心節(jié)點構成封閉圖形，則子圖中包括該圖形。對于中心覆蓋節(jié)點的選擇，要求按照其劃分的查詢子圖能夠覆蓋全部查詢圖以確保RDF數(shù)據(jù)不被破壞。

定義5 查詢子圖。查詢圖Q的一個查詢子圖q=(M,N,T)。其中，M是中心覆蓋節(jié)點集合且M?VQ；N是中心覆蓋節(jié)點的鄰居節(jié)點集合且N={?v|?v∈VQ∩(?va,?vb)∈EQ};T是連接中心覆蓋節(jié)點的兩個鄰居節(jié)點的邊界集合，T={tn|tn=(?va,?vb),T?Q且tn∈EQ}。

如圖6所示，圖4查詢圖被分解為3個查詢子圖q1、q2、q3。左側查詢圖中RDF節(jié)點?v2、?v3以及?v4為中心覆蓋節(jié)點，即中心覆蓋集合M={?v2,?v3,?v4}。在查詢子圖中，中心覆蓋節(jié)點是圖形中心點，且要保證RDF信息不被破壞，要求查詢圖中的所有節(jié)點至少被一個查詢子圖所覆蓋，限制條件如下：

?{?va,?vb}∈EQ? ?va∈M∪?vb∈M

(1)

?{?va,?vb},{?vc,?vb}∈EQ? ?vb∈M

(2)

其中：式(1)確保查詢圖中任意一條邊至少被一個查詢子圖所覆蓋；式(2)確保了中心覆蓋節(jié)點是查詢子圖的中心節(jié)點。查詢圖結構分解之后的查詢子圖可對進一步縮小節(jié)點的搜索空間提供幫助，3.2節(jié)將對此進行詳細闡述。

圖6 查詢圖結構切分

3.2 縮小搜索空間范圍

基于傳入和傳出謂詞結構頂點列表可以確立查詢圖中節(jié)點的搜索空間，但是當數(shù)據(jù)圖數(shù)據(jù)量較大時，某一節(jié)點的搜索空間范圍很大，例如查詢子圖q2中，?v3搜索空間為S?v3={v5,v11}，有兩個節(jié)點符合?v3相鄰謂詞結構，當?v3→v5時，其綁定子圖的相鄰節(jié)點為v4,v6，當?v3→v11時，其綁定子圖的相鄰節(jié)點為v10，v12。也就是說，僅僅從頂點列表中進行節(jié)點過濾，q2的綁定子圖有兩個，這時需要考慮相鄰子圖結構，若一個查詢子圖中的節(jié)點出現(xiàn)在其相鄰子圖中，那么該節(jié)點的搜索空間中的綁定節(jié)點必須同時滿足兩個子圖結構，本文稱其為公共節(jié)點特征。

定義6 公共節(jié)點特征。令(?va,?vb)∈Eq1,(?vc,?vb)∈Eq2,q1與q2為相鄰查詢子圖。當q1→g1,q2→g2且g1與g2為相鄰子圖,并滿足(?va,?vb) → (va,vb),(?vc,?vb) → (vc,vb)時，?(va,vb)∈Eg1且(vc,vb)∈Eg2。

圖7展示了根據(jù)公共節(jié)點特征進行特征搜索的過程，g1，g2分別為q2的兩個綁定子圖(曲線1所示)。為了進一步縮小搜索空間，需將其與相鄰查詢子圖比較(曲線2所示)，如圖可知q1與q2中存在公共節(jié)點?v1,因此將q1定義為q2的鄰域子圖，在q1中，?v1的搜索空間為{v4,v8,v11}，前文通過?v3確定了?v1的可能綁定節(jié)點為v4,v10，因此從這兩者可得出v4是?v1的綁定節(jié)點，進而確定?v3的綁定節(jié)點為v5。

圖7 特征搜索

在確定了q2的綁定子圖后，根據(jù)其相鄰結構，可快速縮小q1、q3的搜索空間并最終找到其綁定子圖，這也體現(xiàn)了RSM的優(yōu)勢所在，不需要將查詢圖整體作為搜索單位，而只取其一部分簡單結構即可找到與其相鄰的查詢子圖的綁定子圖，進而確定查詢圖的同構子圖。與傳統(tǒng)的模式匹配方法相比，可大幅度提升查詢效率；但是在處理過程中需要注意一點，一個查詢圖中可能存在不同的中心覆蓋集合，這也導致了搜索空間的處理過程不同，從而產(chǎn)生不同的查詢代價。在3.3節(jié)會給出最小中心覆蓋集合的計算及處理過程。

3.3 最小中心覆蓋集合的計算

由于中心覆蓋節(jié)點的選擇不同，一個查詢圖可以有多種切分方式，進而存在同個查詢圖中出現(xiàn)多個中心覆蓋集合的情況。例如圖6中查詢圖的一個中心覆蓋集合M1={?v2,?v3,?v4}，從圖中可以發(fā)現(xiàn)M2={?v1,?v2,?v5,?v6}同樣符合中心覆蓋集合的條件。這里需要進行最小中心覆蓋集合的計算，要求集合中節(jié)點數(shù)量盡可能最少，并且要保證查詢子圖完全覆蓋查詢圖，即任意兩個相鄰的查詢子圖必須存在公共節(jié)點。計算最小中心覆蓋集合問題屬于圖結構搜索問題，這類問題是NP-hard[16]，本文將其建模為整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)問題，建模如下：

(3)

(4)

n∈{0,1};?v∈VQ

(5)

其中n是二進制數(shù)，當?v是中心覆蓋節(jié)點時，n=1，否則為0。式(3)使中心覆蓋集合M中節(jié)點的數(shù)量最小化；式(4)確保了兩個相鄰子圖的中心覆蓋節(jié)點必有公共鄰居節(jié)點存在；式(5)給出了n和?v的取值范圍。

以圖4的查詢圖為例，基于ILP建模的最小中心覆蓋集合的計算過程如下：

minimizen0+n1+n2+n3+n4+n5+n6

s.t.n0+n1≥1; {?v1,?v2}

n0+n2≥1; {?v1,?v3}

n1+n3≥1; {?v2,?v4}

n2+n4≥1; {?v3,?v5}

n4+n3≥1; {?v5,?v4}

n3+n5+n6≥1; {?v4,?v6}

n3+n6+n5≥1; {?v4,?v7}

n5+n6+n3≥1; {?v6,?v7}

?i,0≤i≤6,ni∈{0,1}

雖然對于圖的最小中心覆蓋集合的計算問題為NP-hard，但是對于具有幾十個節(jié)點和幾百條邊的復雜查詢圖來說，計算時間是合理的。例如對于300個節(jié)點和1 800條邊的查詢圖來說，不到6 s的時間內即可計算出其最小中心覆蓋集合。

對于一些結構簡單的RDF圖來說，中心覆蓋節(jié)點的選擇相對容易，比如圖2中鏈形結構的查詢圖是由節(jié)點串聯(lián)表示的路徑圖，如果鏈中節(jié)點個數(shù)為奇數(shù)，則從起點開始偶數(shù)節(jié)點即為中心覆蓋節(jié)點，奇數(shù)節(jié)點則相反；對于簡單環(huán)路(三角形)而言，圖中任意節(jié)點即為中心覆蓋節(jié)點。式(6)和(7)分別給出了一個查詢圖滿足鏈形結構與環(huán)路結構的條件：

|EQ|=|VQ|-1

(6)

|EQ|=|VQ|(|VQ|-1)/2

(7)

對于星形結構而言，圖中節(jié)點與邊的關系要滿足式(6)，并且圖中必定存在中心節(jié)點，即與其他節(jié)點均有謂詞表示的關系，那么中心節(jié)點即為星形查詢圖的中心覆蓋節(jié)點。對于星形圖的中心節(jié)點的定義如下。

定義7 星形圖中心節(jié)點。星形查詢中存在節(jié)點vc，使得(vc,n)∈EQ，n∈Vm成立，其中Vm為查詢圖的其余所有節(jié)點的集合，那么vc即為查詢圖的中心節(jié)點。

在RDF圖上的查詢過程可以看作在匹配節(jié)點間進行連接的操作，并將執(zhí)行計劃的輸出形式表示為二叉樹，其中二叉樹的葉子是節(jié)點，而父親是葉節(jié)點間的連接操作(如圖8)。整體的查詢計劃的輸出形式為左深二叉樹，這樣做的目的在于每個父親節(jié)點的右孩子即為下一個待查詢節(jié)點。

子圖匹配的效率往往取決于查詢圖中節(jié)點的處理順序。例如圖4的中心覆蓋集合M={?v2,?v3,?v4}，集合中的每個節(jié)點代表其所在的查詢子圖，在集合M中，子圖處理順序有6種，每種順序產(chǎn)生的執(zhí)行代價有所不同。在第4章將會對計算最佳執(zhí)行順序作出詳細闡述，并依照該順序生成相應執(zhí)行計劃的執(zhí)行算法。

圖8 查詢執(zhí)行計劃

4 生成查詢執(zhí)行計劃

4.1 計算最佳子圖處理順序

本節(jié)主要對于最佳子圖處理順序的計算作出詳細論述，本文將查詢計劃表示為查詢圖的節(jié)點連接過程，圖4的中心覆蓋集合M={?v2,?v3,?v4}的以中心覆蓋節(jié)點為單位的查詢計劃為ψM=(?v2??v3??v4)=((?v2??v3)??v4),將查詢計劃展開，得到ψM=(?v1??v2??v3??v5??v4??v6??v7)。因為3個查詢子圖之間均存在公共節(jié)點，因此這樣的連接順序有6種(3個中心覆蓋節(jié)點的排列組合)，分別為：ψM1=(?v2??v3??v4)，ψM2=(?v2??v4??v3)，ψM3=(?v3??v2??v4)，ψM4=(?v3??v4??v2)，ψM5=(?v4??v2??v3)，ψM6=(?v4??v3??v2)。對于該問題的計算，本文將采用GraphQL[17]與SG-Match[16]所設計的成本模型，該模型基于對貪心算法的修改，基本單位為單個節(jié)點，將搜索空間中綁定節(jié)點數(shù)量最小的節(jié)點作為當前處理節(jié)點。由于RSM采用將查詢圖切分的方法，基本單位不是單個節(jié)點而是整個查詢子圖，需要通過計算查詢子圖的整體代價，再計算查詢子圖中的節(jié)點處理順序，因此修改為如下代價模型：

|Ψ(?vi)|=|?vi|/(|qi|+|qj| )

(8)

Cost(oi)=Cost(|ψ(?vi)|×|ψ(?vj)| )

(9)

Cost(oi×?vk)=Cost(oi)×|ψ(?vk)|×γx

(10)

其中：式(8)用于計算待查詢節(jié)點的代價，是其搜索空間中綁定節(jié)點數(shù)量與該節(jié)點所在查詢子圖中節(jié)點數(shù)量的比值，qj是否存在取決于節(jié)點是否為公共節(jié)點；式(9)用于計算前兩個待查詢節(jié)點連接的代價；式(10)用于計算后續(xù)待查詢節(jié)點連接的整體代價；γ是影響因子，當執(zhí)行計劃中待連接節(jié)點過多時，為了防止數(shù)據(jù)量過多而導致計算結果過大，將γ設置為2，這使得計算過程得到最好的結果；x是后續(xù)節(jié)點?vk的先前節(jié)點數(shù)量。

以查詢子圖q1的計算過程舉例，q1的查詢代價可表示為ψq1=(?v2?v1?v4)，基于本文的代價模型，首先需要計算查詢子圖中每個待查詢節(jié)點的代價，再計算整體代價。為了提高處理的效率，節(jié)點的搜索空間定義為初次搜索空間，即根據(jù)前文設計的頂點列表來計算與查詢節(jié)點對應的綁定節(jié)點數(shù)量，而不參考圖形結構。根據(jù)代價模型得出查詢子圖q1、q2、q3的處理代價：

ψq1=(?v2??v1??v4)=0.17

ψq2=(?v3??v1??v5)=0.89

ψq3=(?v4??v2??v5??v6??v7)=1.92

根據(jù)計算結果可知，查詢圖q1、q2、q3的最佳執(zhí)行計劃為ψM=(?v2??v3??v4)。

4.2 生成最佳執(zhí)行計劃

在得到查詢子圖的處理順序之后，需要計算單個子圖內節(jié)點的處理順序，本文采用了GraphQL的計算模型，該模型采用貪心算法的思想，將子圖內綁定節(jié)點最小的作為當前處理節(jié)點，比如q1中?v2和?v4都只含有一個綁定節(jié)點，因此可將二者之一作為首處理節(jié)點。據(jù)此提出算法1作為執(zhí)行計劃。

在算法1中，首先初始化當前子圖位置，當前節(jié)點位置與匹配結果集F，調用MinimalCostSG方法，從查詢計劃中獲取子圖順序(第1)～3)行)。然后獲取當前查詢圖q1，調用MinimalCandidateNodes方法，從q1中獲取當前綁定節(jié)點數(shù)目最小節(jié)點，從搜索空間S中獲取其綁定節(jié)點并存儲與F中(第5)～10)行)。之后獲取下一節(jié)點并重復此工作，直到j到達q1的最后一個位置并溢出，此時一個查詢子圖中的節(jié)點已完全匹配，此時調用UpdateS方法，通過匹配節(jié)點來更新其余節(jié)點的搜索空間并將i推向下一位置來獲取q2，初始化j(第12)～15)行)，返回第2)行。當i的位置溢出時，說明全部的查詢子圖已經(jīng)處理完成，匹配結果集F中已存在各節(jié)點的綁定節(jié)點，之后根據(jù)數(shù)據(jù)圖及查詢圖的結構再一次過濾多余節(jié)點，最后得到精確結果并輸出(第16)～20)行)。算法1的時間復雜度取決于輸入的中心覆蓋集合中節(jié)點的數(shù)量，其中m為中心覆蓋集合中的節(jié)點數(shù)量。算法1展示了RSM的整體處理流程，這里需要注意一點，因為將中心覆蓋集合M以及查詢計劃ψM作為算法的輸入，而在子圖及子圖中的節(jié)點的選擇過程中，本文采取了貪心算法的思想，及在查詢計劃ψM中選擇當前處理子圖，再在待處理子圖中以當前綁定節(jié)點數(shù)量最小的節(jié)點作為子圖中當前處理節(jié)點，基于貪心算法的思想將子圖與節(jié)點的處理順序按照其選擇性強弱進行排序，以使得生成的執(zhí)行計劃是最佳的。

算法1 RSM執(zhí)行計劃。

輸入:數(shù)據(jù)圖G,查詢圖Q,中心覆蓋集合M,查詢計劃ψM,搜索空間S,子圖當前位置i,子圖中節(jié)點當前位置j。

輸出:匹配結果集F。

1)

initializationi=0,j=0,F={} then

2)

leti→qi,j→vj

3)

qi→ getMinimalCostSG(ψM) then

4)

foreachvj∈Vdo

5)

ifvj∈qido

6)

v=vj→ getMinimalCandidateNodes(Q,G,Sj) then

7)

v→F;F→Sj

8)

j=j++

9)

return then

10)

back to step 5)

11)

elsej=j++

12)

untilj=|qi| do

13)

i=i++,j=0

14)

Sj=S→ getUpdateS(vj,sj) then

15)

return then

16)

back to step 2)

17)

untili=|ψM| do

18)

returnF→ getUpdateF(G,Q,S) then

19)

OutputF

20)

end

5 實驗結果與分析

5.1 實驗環(huán)境與數(shù)據(jù)集設置

本文的實驗設備采用Windows 7 64位系統(tǒng)，CPU采用Intel Core i5- 4200M@ 2.50 GHz，內存為8 GB，采用Cassandra(可快速處理大規(guī)模圖數(shù)據(jù)的關系數(shù)據(jù)庫)作為RSM的底層數(shù)據(jù)存儲。

本文將RSM與RDF- 3X、R3F、GraSS對于結構復雜程度不同的查詢圖的查詢響應時間進行對比，實驗將分別采用合成數(shù)據(jù)集SNIB(社交網(wǎng)絡基準http://www.w3.org/wiki/Social_Network_Intelligence_BenchMark)與真實世界數(shù)據(jù)集YAGO2[18]。其中，合成數(shù)據(jù)集SNIB源于社交網(wǎng)絡，例如Facebook、Google Intelligence等，該數(shù)據(jù)集中的RDF圖結構包括鏈形、環(huán)以及星形等若干基本結構所組合成的復雜結構；而真實數(shù)據(jù)集YAGO2是從維基百科、WordNet[19]衍生的知識庫，該數(shù)據(jù)集的RDF圖包含960萬個節(jié)點和3 300萬條邊，其提供的數(shù)據(jù)集更接近于真實查詢。

5.2 實驗分析

一共做了兩個對比實驗，實驗過程采用控制變量法，在不影響節(jié)點過濾的情況下，將相鄰謂詞結構索引進行壓縮，使其大小近似于RDF- 3X的三元組屬性索引以排除因索引的較大差異對實驗結果的影響(R3F同樣不考慮標簽值，可排除索引影響，GraSS只針對星形圖建立索引，普遍性與適用性不如RDF- 3X)，僅通過改變查詢圖中的結構復雜程度來比較3種方法的查詢響應時間。圖9表示了相鄰謂詞結構索引經(jīng)壓縮后與R3F、RDF- 3X、GraSS的索引大小比較，從對比圖中可知，經(jīng)壓縮后的相鄰謂詞結果索引的大小隨著三元組數(shù)據(jù)量增多的上升趨勢與RDF- 3X、R3F近乎相同，且在數(shù)據(jù)量相同的情況下，索引的大小差距小于50 MB，因此對內存配置的要求也近乎相同，由于GraSS重點針對星形RDF圖來建立索引，因此在數(shù)據(jù)集中存在的鏈形結構與環(huán)形結構數(shù)量任意的情況下，其索引在一般情況下是最小的。

圖9 索引壓縮對比

本文以每組SPARQL查詢中的元組模式數(shù)量來表示查詢圖的復雜程度，一組SPARQL查詢可處理為一個查詢圖，元組模式的數(shù)量范圍區(qū)間為[3,15](稱為查詢圖復雜度)。在SNIB和YAGO2數(shù)據(jù)集中：查詢圖尺寸為3或4時，查詢圖結構往往為鏈結構與環(huán)結構，有少量的星形結構出現(xiàn)；當查詢圖尺寸為5以上時，會頻繁地出現(xiàn)組合結構。對于每個查詢圖尺寸，本文從兩個數(shù)據(jù)集中分別隨機設置20個查詢圖與之對應，以保證查詢圖結構的隨機性與復雜性。本文共設置了兩個實驗，實驗1采用了SNIB數(shù)據(jù)集，實驗2則采用YAGO2數(shù)據(jù)集，實驗1與實驗2的對比結果分別對應于圖10(a)與圖10(b)。

圖10(a)顯示了實驗1的對比結果，當查詢中的元組模式數(shù)量較少(生成的查詢圖結構相對簡單)時，RSM的查詢響應時間要稍慢于R3F，而RDF- 3X和GraSS在元組數(shù)量較少時的響應時間要長于RSM，當元組數(shù)為3時，查詢圖結構大多為鏈查詢或少量的環(huán)查詢，因此可以看到元組數(shù)從3提升到5(出現(xiàn)了組合查詢)的時候，RSM的響應時間減少了0.08 s(表3)。而GraSS對于鏈形結構與環(huán)形結構并沒有采取有效的處理措施，因此在查詢圖復雜度升高后，對于復雜查詢圖的處理效率提升得并不明顯，隨著元組模式數(shù)量的增多，RSM查詢響應時間的上升趨勢要遠小于RDF- 3X、R3F與GraSS，因此，RSM在SNIB數(shù)據(jù)集上對于結構復雜的查詢圖的查詢處理效率是相對較高的。

在實驗2中，當查詢圖復雜程度為13(具有13個元組模式的SPARQL查詢)時，可以看出RDF- 3X的查詢響應速度出現(xiàn)大幅度減慢的情況，說明此刻RDF- 3X的索引表中數(shù)據(jù)因為太多地進行跨表連接而產(chǎn)生的中間結果冗余情況已經(jīng)嚴重影響查詢效率。與實驗1相同的是，在處理簡單圖時，RSM的高效性并不明顯，但隨著圖結構復雜程度的提升，RSM的查詢響應時間要遠低于RDF- 3X與R3F。而GraSS同樣是隨著查詢圖的復雜度提升而體現(xiàn)出高效性，但由于其僅對于星形結構進行有效處理，因此其整體進行查詢處理的響應時間均要高于RSM，因此，從實驗1與實驗2中得出的共同結論為，在處理結構復雜的查詢圖時，RSM的查詢響應時間更短，具有更高的查詢效率。

圖10 查詢響應時間對比實驗結果

6 結語

為了提高對于復雜查詢圖的查詢效率，提出了一種基于RDF圖切分的子圖匹配方法——RSM，提出了相鄰謂詞結構索引來用于節(jié)點的過濾，并為其處理過程設計了相關問題建模與詳細舉例。在實驗部分，本文分別采用了合成數(shù)據(jù)集SNIB、真實世界數(shù)據(jù)集YAGO2并與RDF- 3X、R3F、GraSS等主流查詢方法進行實驗對比以驗證RSM的普適性與高效性。實驗結果證明，在處理結構復雜的查詢圖時，RSM的查詢響應時間更少，效率更高。在接下來的工作中，將對RSM的可擴展性進行充分研究，將RSM應用在分布式處理平臺上，并進一步研究圖結構的切分規(guī)則，使切分得到的子圖結構選擇性更加突出。