雙索引機制的RDF數(shù)據(jù)圖查詢方法研究

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

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

1 引 言

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

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

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

2 相關(guān)工作

關(guān)鍵詞查詢方法主要分為兩類,一類是將RDF數(shù)據(jù)轉(zhuǎn)化為RDF圖,支持頂點查詢但不支持邊查詢;另一類是將RDF數(shù)據(jù)轉(zhuǎn)化為RDF二分圖,既支持頂點查詢又支持邊查詢.

第一類的關(guān)鍵詞查詢可分為兩種情況.

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

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

第二類的關(guān)鍵詞查詢同樣也可分為兩類.

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

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

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

3 相關(guān)定義

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

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

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

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

圖1 RDF圖示例Fig.1 RDF graph

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

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

圖2 RDF子圖Fig.2 RDF subgraph

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

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

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

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

圖3 索引關(guān)系Fig.3 Index relation

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

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

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

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

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

圖4 鄰接標(biāo)簽矩陣Fig.4 Adjacency label matrix

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

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

1)G的樹根是R;

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

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

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

4 雙索引查詢方法

雙索引查詢方法主要由索引構(gòu)建和關(guān)鍵詞查詢兩部分構(gòu)成.本節(jié)首先給出索引構(gòu)造算法的描述,然后利用索引之間的關(guān)系設(shè)計關(guān)鍵詞查詢算法,并給出其算法的偽代碼描述.

4.1 索引構(gòu)造算法

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

索引構(gòu)造算法描述:

Step1.定義兩個三維數(shù)組VertexIndex和EdgeIndex,其中VertexIndex存儲每個子圖的頂點位置和標(biāo)簽信息,EdgeIndex存儲每個子圖的謂詞位置,標(biāo)簽信息及其父節(jié)點的位置.

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

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

結(jié)合上面對索引構(gòu)造算法的具體描述,給出索引構(gòu)造算法具體實現(xiàn)的偽代碼描述.

算法1．索引構(gòu)建算法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．a(chǎn)dd(VL(r))5． whileLocationQueueisnotemptydo6． currentLocation=LocationQueue．poll()7． for(k=0；k

4.2 基于索引的關(guān)鍵詞查詢算法

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

關(guān)鍵詞查詢算法:

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

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

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

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

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

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

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

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

結(jié)合上面對關(guān)鍵詞查詢算法的具體描述,下面給出關(guān)鍵詞查詢算法具體實現(xiàn)的偽代碼描述.

算法2．關(guān)鍵詞查詢算法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]．a(chǎn)dd(p)13． endif14． if(forallk∈K，v．path[k]！=null)then15． result<-allpathswillbemergedfork16． if(！resultSet．contains(result))then17． resultSet．a(chǎn)dd(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 實驗與結(jié)果分析

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

5.1 實驗環(huán)境及實驗數(shù)據(jù)

實驗環(huán)境配置如表1所示.

表1 實驗環(huán)境
Table 1 Experimental environment

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

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

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

表2 查詢示例
Table 2 Query sample

查詢關(guān)鍵詞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中查詢的響應(yīng)時間.為了控制索引的存儲空間,KREAG方法將索引的步長設(shè)置為8.

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

圖5 關(guān)鍵詞查詢響應(yīng)時間Fig.5 Keywords query response time

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

圖6 top-k查詢響應(yīng)時間Fig.6 top-k query response time

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

5.3 索引空間評估

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

表3 索引空間
Table 3 Index space

存儲空間/MBBLINKS1216KREAG743QMRDI52

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

6 總 結(jié)

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

[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樹的關(guān)鍵詞查詢方法[J].小型微型計算機系統(tǒng),2010,31(1):119-123.

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

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