基于RDF圖結(jié)構(gòu)切分的高效子圖匹配方法

關(guān)皓元，朱 斌，李冠宇，趙 玲

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

0 引言

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

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

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

圖1 面向RDF圖的模式匹配

圖2 RDF圖的基本結(jié)構(gòu)

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

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

本文的主要工作如下：

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 基本定義與謂詞索引

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

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

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

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

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

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

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

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

圖4 查詢圖示例

圖5 綁定子圖

2.2 相鄰謂詞結(jié)構(gòu)索引

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

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

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

表1 基于傳入、傳出謂詞結(jié)構(gòu)的頂點(diǎn)列表

根據(jù)表1中的數(shù)據(jù)可進(jìn)行查詢圖中節(jié)點(diǎn)的過濾，圖4中節(jié)點(diǎn)?v2的傳入謂詞結(jié)構(gòu)為p2，因此可在表1中找到?v2的搜索空間S1(p2|v3,v6,v7,v12,v15,v18)，而?v2具有傳出謂詞結(jié)構(gòu)p3，在表1中找到?v2的搜索空間S2(p3|v1,v7,v11,v13)，綜合S1和S2將搜索空間壓縮，最后找到符合子圖同構(gòu)的?v2綁定節(jié)點(diǎn)為v7；同理可得到查詢圖Q中其余頂點(diǎn)的搜索空間為: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}。

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

3 RSM-查詢圖切分方法

3.1 查詢圖結(jié)構(gòu)切分

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

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

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

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

(1)

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

(2)

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

圖6 查詢圖結(jié)構(gòu)切分

3.2 縮小搜索空間范圍

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

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

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

圖7 特征搜索

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

3.3 最小中心覆蓋集合的計(jì)算

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

(3)

(4)

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

(5)

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

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

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}

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

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

|EQ|=|VQ|-1

(6)

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

(7)

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

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

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

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

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

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

4.1 計(jì)算最佳子圖處理順序

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

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

(8)

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

(9)

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

(10)

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

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

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

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

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

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

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

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

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

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

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

輸出:匹配結(jié)果集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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

5.2 實(shí)驗(yàn)分析

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

圖9 索引壓縮對比

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

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

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

圖10 查詢響應(yīng)時(shí)間對比實(shí)驗(yàn)結(jié)果

6 結(jié)語

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