雙索引機制的RDF數據圖查詢方法研究

鄭志蘊,丁 陽,李 倫,李 鈍

(鄭州大學 信息工程學院,鄭州 450001)

1 引 言

隨著RDF1數據的增加,普通用戶查詢語義網數據的需求也在逐漸增加.通常RDF數據查詢處理任務主要采用基于查詢語言(比如RDQL、SPARQL等)的方法進行.其中SPARQL(simple protocol and RDF query language)2是 W3C 提出的 RDF 數據查詢標準語言,也是被廣泛采用的一種 RDF 查詢語言.但是對于普通用戶,這種形式化RDF數據查詢方法的語法規則比較復雜,使用起來比較困難.因此從用戶體驗角度出發,關鍵詞的檢索方法是一種有效的查詢機制,不僅能夠保證查詢的高效性,而且可以避免使用復雜的結構查詢語言.

目前常用的關鍵詞查詢技術是將 RDF數據表示為一個帶標簽的有向圖,圖中的頂點對應三元組中的主語和賓語,謂詞為邊.使用圖表示RDF數據既能保持數據間的關聯信息又不喪失語義信息[1],因此RDF數據的查詢處理通常被轉化為圖匹配問題,即在RDF數據圖上定位包含關鍵詞的斯坦納樹(Steiner Tree)[2],且主要分為兩類.一類是將RDF數據轉化為RDF圖,該方法支持頂點的查詢,但不支持邊上的關聯信息作為查詢對象,因此為解決該問題提出了另一類方法,將RDF圖轉化為RDF二分圖.該方法將邊上信息進行封裝作為RDF圖的另一類頂點,在不破壞實體間關聯關系的情況下,實現頂點和邊的查詢.然而轉化后增加了圖中頂點的個數使得關鍵詞查詢的存儲空間增大,查詢效率降低.因此如何在保證查找效率和存儲空間的情況下,實現RDF頂點和邊的查詢成為一個重要的問題.

本文提出一種雙索引機制的RDF數據圖查詢方法(QMRDI),支持頂點和邊的查詢.該方法首先將RDF數據建模為RDF數據圖,然后將入度為0的頂點作為根節點,使用廣度優先的方法對RDF圖進行分割從而提高關鍵詞的查找效率;其次根據鄰接標簽矩陣為每一個RDF子圖構建一個頂點索引和邊索引,利用字符串匹配的方法確定查詢關鍵詞所在子圖的頂點索引和邊索引的位置,通過兩個索引的關系實現頂點和邊的查詢;最后利用相關性評測函數對查詢結果子圖進行相關性排序,輸出top-k個查詢結果子圖.

2 相關工作

關鍵詞查詢方法主要分為兩類,一類是將RDF數據轉化為RDF圖,支持頂點查詢但不支持邊查詢;另一類是將RDF數據轉化為RDF二分圖,既支持頂點查詢又支持邊查詢.

第一類的關鍵詞查詢可分為兩種情況.

1)無索引結構[3-5].其中EASE[4]通過將RDF數據建模為RDF圖,利用RDF圖的鄰接矩陣的N次方找到top-k個包含關鍵詞的斯坦納圖作為查詢結果子圖.該方法的時間復雜度為O(n2)(n為RDF圖中頂點的個數).然而,查詢的響應時間會隨著n的變大而變大,極大影響查詢的效率.

2)引入索引結構[6，7].何昊等人提出的BLINKS[6]和SLINKS[6]方法以及司馬強等人提出的模板樹方法[7]等均是為了提高關鍵詞查找效率而提前構建索引結構.其中最為經典是BLINKS[6]將數據圖劃分成不同的塊,并為每一塊構建一個塊索引和塊內索引.利用塊索引查找關鍵頂點所在的子圖,然后通過塊內信息進行關鍵頂點的路徑查詢,最終將各個子圖所得的路徑進行合并得到查詢結果.但是由于BLINKS采用為圖中每一個頂點構建一個最短通路索引的方法,這樣構建的索引不僅重復度比較高,并且不利于最終路徑的查找.

第二類的關鍵詞查詢同樣也可分為兩類.

1)無索引結構[8].鄭志蘊等人提出的KERBG[8]是一種基于二分圖的RDF關鍵詞擴展查詢方法.該方法將RDF三元組中的謂詞單獨分開作為一類頂點,稱為謂詞頂點;RDF三元組中主體和客體作為另一類頂點,稱為實體頂點.通過實體頂點到謂詞頂點再到實體頂點的通路保持實體之間的關聯.然后依據RDF二分圖的反對稱鄰接矩陣及其冪矩陣,實現關鍵詞查詢的快速響應.但是隨著RDF數據的增加,轉化為二分圖的時間也在增加.

2)引入索引結構[9].李慧穎等人提出的KREAG[9]是基于實體三元組關聯圖的RDF數據關鍵詞查詢方法.該方法將RDF數據建模為頂點帶標簽的實體三元組關聯圖,文本信息全部封裝在關聯圖頂點標簽上,不僅支持用戶對關系進行查詢,而且將RDF數據中實體間關聯關系轉化為關聯圖中頂點間的通路,有效保持了RDF數據的語義性.然而轉化后的RDF二分圖增加了圖中頂點的個數,使得構建索引的長度增加從而影響索引的存儲空間.

通過對上述方法的分析研究,提出雙索引機制的RDF數據圖查詢方法,目的是在不需要轉化為二分圖的情況下,實現頂點和邊的查詢,同時提高關鍵詞查詢的效率,降低索引的存儲空間.

3 相關定義

RDF數據是指以RDF三元組形式組織起來的語義信息,可以通過有向圖模型表示.本文用(s,p,o)描述一個RDF三元組,并簡記為t,用s(t)、p(t)和o(t)分別表示三元組中的主體、謂詞和客體.下面給出RDF有向圖的定義.

定義1(RDF有向圖).設G=表示一個帶標簽的RDF有向圖,其中由RDF三元組中主體和客體組成的頂點集合V={v|v∈s(T)∪o(T)},主體和客體之間關系的謂詞組成的有向邊的集合E={},邊的方向由主體頂點指向客體頂點.L是標簽的集合,L=Lv∪Lp,其中Lv表示頂點標簽,Lp表示謂詞標簽.

圖1是一個真實的RDF數據片段的RDF有向圖表示,圖中邊上的標簽存儲了部分URI信息.

為了提高關鍵詞查找效率,將給定的RDF圖進行分割,此處采用文獻[7]所給的方法,RDF圖分割方法的定義如下.

圖1 RDF圖示例Fig.1 RDF graph

定義2(RDF圖分割方法[7]).設G=表示一個帶標簽的RDF有向圖,將所有入度為0的頂點作為根節點,從任意的一個根節點出發利用廣度優先的方法將所有遍歷到的頂點構建成一個包含該根節點的RDF子圖.

利用該方法對圖1進行分割,分割后得到的子圖如圖2中(a)和(b)所示.

圖2 RDF子圖Fig.2 RDF subgraph

定義3(頂點索引和邊索引).設Gr=表示一個分割后的子圖,其中r代表該子圖的入度為0的頂點,從該頂點出發可以到達圖中的任一頂點.

頂點索引(簡稱VI)是一個二元組VI=(VL,Lv),VL表示主體或者客體頂點的下標,從0開始計數;Lv表示頂點標簽.

邊索引(簡稱為EI)是一個三元組EI=(PL,Lp,PaL),PL表示謂詞的下標,從0開始計數;Lp表示謂詞標簽;對于?Vi,Vj∈V,p(t)∈E,若存在從Vi到Vj的關系序列Vip(t)Vj,則稱Vi為p(t)的父節點,將其父節點的下標記為PaL,從0開始計數.若PaL=0,代表該謂詞的父節點是根節點r.

圖3給出的是圖2(a)的頂點索引和邊索引,其中實線箭頭指向該頂點的父節點,虛線箭頭指向該謂詞的父節點.

圖3 索引關系Fig.3 Index relation

下面以謂詞year和頂點Breitbart為例說明兩個索引的關系:

1)year的父節點的下標PaL(year)=2,說明year的父節點為頂點索引中下標為2的頂點,即Breitbart

2)Breitbart的下標為2,因此其父節點的下標PaL(Breitbart)=2-1=1,即Breitbart的父節點為邊索引中下標為1的謂詞,即author.

定義4(鄰接標簽矩陣).設G=,對于?Vi,Vj∈V,p(t)∈E,若存在從Vi到Vj的關系序列Vip(t)Vj,則在Vi和Vj的鄰接標簽矩陣中記錄p(t)的標簽信息.

圖4給出圖2(a)的鄰接標簽矩陣.

圖4 鄰接標簽矩陣Fig.4 Adjacency label matrix

給定RDF有向圖G=(邊的權重均為1)和關鍵詞查詢K={k1,k2…ks}.首先根據字符串匹配確定匹配關鍵詞頂點的集合,則K的查詢結果定義如下.

定義5(查詢結果樹).設與關鍵詞K匹配的頂點的集合是M(K)={m1,m2…ms},查詢結果定義為一棵滿足下面條件的有向樹:

1)G的樹根是R;

2)對于每一個集合mi中的某個頂點vi,存在從R到vi的有向通路.

目前的方法[10-11]利用結果的緊湊性進行評分,此處采用[10]所給評分函數的定義.

定義6(評分函數[10]).設K={k1,k2…ks}的查詢結果為RK,定義其評分函數為Score(RK)=Length(RK),其中Length(RK)為查詢結果從樹根到所有葉子節點的路徑之和.

4 雙索引查詢方法

雙索引查詢方法主要由索引構建和關鍵詞查詢兩部分構成.本節首先給出索引構造算法的描述,然后利用索引之間的關系設計關鍵詞查詢算法,并給出其算法的偽代碼描述.

4.1 索引構造算法

為了提高關鍵詞查找效率,首先為RDF圖構建索引,其中索引包括頂點索引和謂詞索引.下面是對索引算法的描述和完整的偽代碼.

索引構造算法描述:

Step1.定義兩個三維數組VertexIndex和EdgeIndex,其中VertexIndex存儲每個子圖的頂點位置和標簽信息,EdgeIndex存儲每個子圖的謂詞位置,標簽信息及其父節點的位置.

Step2.將子圖入度為0的頂點的下標VL(r)和標簽信息Lv(r)存放在VertexIndex中,同時將VL(r)放入到隊列LocationQueue中.若隊列Queue!=null,根據定義4所得的鄰接標簽矩陣判斷該頂點的相鄰頂點,若當前鄰接標簽矩陣的值adjLabel!=null則將該謂詞的下標,標簽信息以及currentLocation的值存放到EdgeIndex中,同時將其相鄰頂點的下標及其標簽信息存放在VertexIndex.若當前鄰接標簽矩陣的值adjLabel=null說明該頂點不與當前頂點相鄰,繼續考察下一個頂點.

Step3.重復上面的步驟,直至隊列為空為止.

結合上面對索引構造算法的具體描述,給出索引構造算法具體實現的偽代碼描述.

算法1．索引構建算法Input：G=(V，E，L)isadatagraph；Kisasetofkeywordnodes；Output：EdgeIndexandVertexIndex1． LocationQueue<-anemptylocationqueue2． VertexIndex[Root][num][0]=VL(r)3． VertexIndex[Root][num][1]=Lv(r)4． LocationQueue．add(VL(r))5． whileLocationQueueisnotemptydo6． currentLocation=LocationQueue．poll()7． for(k=0；k

4.2 基于索引的關鍵詞查詢算法

基于索引的關鍵詞查詢算法主要有關鍵詞匹配、根節點的確定和查詢結果的生成三部分.關鍵詞匹配:使用字符串匹配方法確定查詢關鍵詞所在的位置.根節點的確定:查找一個可以到達所有關鍵頂點的根節點.最后將所得的候選結果,根據評分函數進行從低到高的排序,將前k個結果返回給用戶.下面給出關鍵詞查詢算法的具體描述.

關鍵詞查詢算法:

Step1.獲取包含所有查詢關鍵詞的子圖,給匹配的RDF子圖中所有頂點和邊定義一個存儲到達輸入關鍵頂點路徑的數組v.path[k].

Step2.定義兩個三維數組Vertex和Edge分別存放每個子圖中與相應關鍵詞匹配的頂點索引和邊索引的位置,并用flag區分兩類頂點,將Vertex和Edge中的所有元素放入隊列Q中.

Step3.依次遍歷隊列中的元素,輸出該元素對應的路徑p中的第一個元素,該元素是可以到達關鍵頂點的最新頂點的位置,最后一個元素是關鍵頂點的位置,分別記為first(p)和last(p),確定last(p)所對應的關鍵詞,并將路徑p存入v.path[k]中.

Step4.判斷first(p)所對應的頂點是否可以到達其余所有的關鍵頂點.若是,則將所有到達關鍵詞的路徑進行合并.否則,則根據first(p)的值以及定義3中所介紹的頂點索引和邊索引的關系查找first(p)的父節點.若first(p)的標志位flag=0,說明與該關鍵詞匹配的頂點屬于頂點索引中的元素,

3http://lsdis.cs.uga.edu/Projects/SemDis/Swetodblp

則first(p)父節點的位置為PaL(first(p))=first(p)-1.若first(p)的標志位flag=1,說明與該關鍵詞匹配的頂點屬于邊索引中的元素,則取出邊索引中first(p)對應的父節點的位置PaL(first(p)).

Step5.將PaL(first(p))添加到路徑p中,并放入隊列Q中.重復上面的步驟直至隊列為空為止.

Step6.使用評分函數對候選結果進行排序,返回前k個查詢結果.

結合上面對關鍵詞查詢算法的具體描述,下面給出關鍵詞查詢算法具體實現的偽代碼描述.

算法2．關鍵詞查詢算法Input：G=(V，E，L)isadatagraph；Kisasetofkeywordnodes；resultSetisasetofqueryresults；Output：answertoKBegin1． resultSet=null2． Q<-anemptyqueue3． forv∈V&k∈Kdo4． v．path[k]<-null5． endfor6． Q．insert(Vertex[Root][k][m])7． Q．insert(Edge[Root][k][m])8． whileQisnotemptydo9． p<-Q．remove()10． v<-first(p)11． if(forallk∈Kcorrespondingtolast(p))then12． v．path[k]．add(p)13． endif14． if(forallk∈K，v．path[k]！=null)then15． result<-allpathswillbemergedfork16． if(！resultSet．contains(result))then17． resultSet．add(result)18． endif19． endif20． else21． if(first(p)．flag=1)then22． PaL(first(p))=EdgeIndex[Root][first(p)][1]23． endif24． else25． if(first(p)．flag=0)then26． PaL(first(p))=first(p)-127． endif28． Q．insert(PaL(first(p))->p)29． endwhile30． sorttheresultSetbyscorefunction31． returntop-kresults32． end

5 實驗與結果分析

為了驗證本文提出方法的性能,實驗使用Java語言和MySQL數據庫編程實現本文的查詢方法QMRDI,在保證查詢準確率的情況下與現有的BLINKS[6]和KREAG[9]方法進行對比.

5.1 實驗環境及實驗數據

實驗環境配置如表1所示.

表1 實驗環境
Table 1 Experimental environment

組件詳細描述JDK版本1．7．0＿03MyEclipse10．0OSWindows7sp132位CPUInteli3?21303．40GHz內存4G

實驗采用真實的數據集swetodblp3,數據主題是計算機科學領域發表文章的信息.該數據中共包含681636個三元組,存儲占用53.6MB,邊數和頂點數分別為1026375和373219.其中入度為0的頂點的個數為16439,使用了637s完成對RDF數據集的分割.

本文在數據集上測試了兩組共10個查詢(表2),分別包含3-5個查詢關鍵詞.第一組Q1-Q5是不包含關系的測試查詢.第二組Q6-Q10是包含關系的測試查詢.

表2 查詢示例
Table 2 Query sample

查詢關鍵詞Q1Breitbart 573 DatabaseQ2ADDS Modern Kim95Q31995 OQL[C++] 2002?01?03 QueryQ4Nathan DBMS Goodman95 ModernQ5Kelley Schema 621 kim95DatabaseQ6author ACFHK95 typeQ7Pages book＿title relationQ8Author year 1995 ManagementQ9Kowalski E&P label last＿modifiedQ10Rusin chapter＿of kim95 type Book

5.2 查找效率

圖5分別顯示了BLINKS,KREAG和本文所提方法QMRDI對表2中查詢的響應時間.為了控制索引的存儲空間,KREAG方法將索引的步長設置為8.

從圖5中可得知,BLINKS的響應時間最長,原因是該方法需要在每個子圖中基于塊內索引和塊間索引的雙層搜索實現關鍵詞的查詢且所得查詢結果可能并沒有包含所有的關鍵頂點而造成無效查詢,因此雖然結構圖規模小于RDF圖,但是其響應時間并不理想.KREAG方法需要遍歷匹配的關鍵詞索引中的每個記錄,造成一些無效查詢,影響了查詢效果.BLINKS在第6-10的關鍵詞查詢時間相比于1-5的關鍵詞查詢時間有所下降,主要是因為該方法不支持關系查詢,導致匹配的關鍵頂點下降,從而響應的時間偏低.而本文提出的方法QMRDI的響應時間最短,主要是因為首先確定包含所有關鍵詞的子圖,避免在沒有包含所有關鍵詞的子圖中查詢;其次提前為每個子圖構建了頂點索引和邊索引,并按照索引中記錄的位置進行路徑查找,不需要遍歷索引中的每個記錄,從而節約大量的時間.

圖5 關鍵詞查詢響應時間Fig.5 Keywords query response time

圖6分別顯示了BLINKS,KREAG和QMRDI方法返回top-k個查詢結果的查詢響應時間,該查詢響應時間為表2中10次查詢的平均時間.

圖6 top-k查詢響應時間Fig.6 top-k query response time

從圖6中可以看到,隨著k值的增加各個方法的響應時間均在增加,而QMRDI響應時間的增長比較緩慢,主要是因為在同一個子圖中可返回多個查詢結果.KREAG的響應時間次之,根據匹配的關鍵頂點的最短通路索引進行路徑查詢時,k值越大則該方法需要查詢的路徑越長,造成無效查詢越多,從而影響查詢的時間.BLINKS的響應時間最長,隨著k的增加需要返回的結果隨之增加,該方法需要在更多的不同子圖內進行路徑的查詢和合并,才能返回查詢結果.

5.3 索引空間評估

表3分別顯示了BLINKS,KREAG和QMRDI方法所占存儲空間大小,KREAG方法將索引的步長設置為8.

表3 索引空間
Table 3 Index space

存儲空間/MBBLINKS1216KREAG743QMRDI52

從表3中可知QMRDI所占空間最小,接近于整個RDF數據的存儲空間,因為該方法只為每一個子圖構建了一個頂點索引和謂詞索引,因此實際上的存儲空間就等于所有頂點(不包含重復的入度為0的頂點)和邊的存儲空間之和即O(V+E).KREAG是將RDF圖轉化為RDF二分圖,因此頂點有三元組的個數和實體頂點的個數兩部分構成,且為每一個頂點構建一個索引,因此索引所占的空間為O((VP+VE)2)(VP是三元組頂點的個數,VE是實體頂點的個數).BLINKS方法主要有塊索引和塊內索引兩部分構成,同樣采用為每一個頂點構建一個索引,因此其存儲的空間為O(∑nb+BP)(其中nb代表該塊內頂點的個數,B代表塊的大小,P代表門戶頂點的個數).

6 總 結

為了實現頂點和邊的查詢,本文提出雙索引機制的RDF數據圖查詢方法.該方法首先將RDF數據建模為RDF數據圖,然后對圖進行分割;其次為每一個RDF子圖構建一個頂點索引和邊索引,利用兩個索引的關系實現頂點和邊的查詢;最后利用相關性評測函數對查詢結果子圖進行相關性排序,輸出top-k個查詢結果.通過實驗可知本文提出的方法在查詢效率和存儲空間上優于其它方法.

[1] Du Fang,Chen Yue-guo,Du Xiao-yong,et al.Survey of RDF query processing techniques [J].Journal of Software(JSW),2013,24(6):1222-1242.

[2] Zhang Yu,Jin Shun-fu,Liu Guo-hua,et al.Minimum steiner tree based method to keyword search[J].Journal of Chinese Computer Systems,2010,31(1):119-123.

[3] Bhalotia G,Hulgeri A,Nakhe C,et al.Keyword searching and browsing in database using BANKS[C].Proceedings of the 18thInternational Conference on Data Engineering(ICDE),2002:431-440.

[4] Li Guo-liang,Ooi B C,Feng Jian-hua,et al.Ease:an effective 3-in-1 keyword search method for unstructured,semi-structured and structured data[C].Proceedings of the ACM Conference on Management of Data(SIGMOD),2008:903-914.

[5] Cui Yi-tong,Feng Zhi-yong,Wang Xin,et al.Research on large-scale RDF data query method based on graph clustering[J].Journal of Chinese Computer Systems,2015,36(12):2625-2628.

[6] He Hao,Wang Hai-xun,Yang Jun,et al.BLINKS:ranked keyword searches on graphs [C].Proceedings of the ACM Conference on Management of Data(SIGMOD),2007:305-316.

[7] Qiang Sima,Li Hui-ying.Keyword query approach over RDF data based on tree template[C].Proceedings of International Conference on Big Data Analysis(ICBDA),2016:1-6.

[8] Zheng Zhi-yun,Wang Zheng-tao,Zhang Xing-jin,et al.KERBG:keyword expansion query approach over RDF data based on bipartite graph [J].Journal of Computer Science,2016,43(11):272-279.

[9] Li Hui-ying,Qu Yu-zhong.KREAG:keyword query approach over RDF data based on entity-triple association graph[J].Journal of Computers(JCP),2011,34(5):825-835.

[10] Tran T,Ladwig G.Index structures and Top-k join algorithms for native keyword search databases[C].Proceedings of the ACM International Conference on Information and Knowledge Management(CIKM),2011:1505-1514.

[11] Li Jian-xin,Liu Cheng-fei,Zhou Rui,et al.Top-k keyword search over probabilistic XML data[C].Proceedings of the IEEE International Conference on Data Engineering(ICDE),2011:673-684.

附中文參考文獻：

[2] 張 宇,金順福,劉國華,等.基于最小Steiner樹的關鍵詞查詢方法[J].小型微型計算機系統,2010,31(1):119-123.

[5] 催義童,馮志勇,王 鑫,等.基于圖聚類算法的大規模RDF數據查詢方法研究[J].小型微型計算機系統,2015,36(12):2625-2628.

[9] 李慧穎,瞿裕忠.KREAG:基于實體三元組關聯圖的RDF數據關鍵詞查詢方法[J].計算機學報,2011,34(5):825-835.