林曉慶,張 富,程經(jīng)緯

(1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,沈陽(yáng) 110819; 2.遼東學(xué)院 信息工程學(xué)院,遼寧 丹東 118003)

0 概述

資源描述框架(Resource Description Framework,RDF)現(xiàn)已成為語(yǔ)義網(wǎng)數(shù)據(jù)表示和交換的核心模型,因此,可用的RDF數(shù)據(jù)越來(lái)越多。RDF數(shù)據(jù)是陳述的集合,形式為(Subject,Predicate,Object)三元組,其中,Subject為主語(yǔ),Predicate為謂詞,用于聯(lián)結(jié)主語(yǔ)和賓語(yǔ),Object為賓語(yǔ)。SPARQL是標(biāo)準(zhǔn)的RDF數(shù)據(jù)查詢語(yǔ)言,因其可對(duì)RDF數(shù)據(jù)查詢以獲得有用的Web信息,故被廣泛應(yīng)用。但是在SPARQL查詢執(zhí)行處理過(guò)程中會(huì)產(chǎn)生大量冗余的中間結(jié)果,尤其在處理大規(guī)模的RDF數(shù)據(jù)時(shí),這大幅降低了SPARQL查詢的執(zhí)行效率。因此,SPARQL查詢優(yōu)化處理成為了研究熱點(diǎn)。

早期的RDF搜索系統(tǒng)是面向RDF三元組行存儲(chǔ)的關(guān)系式數(shù)據(jù)庫(kù)管理系統(tǒng),例如Jena[1]及Sesame[2]等。這些系統(tǒng)利用關(guān)系式數(shù)據(jù)庫(kù)管理系統(tǒng)的查詢處理模塊對(duì)RDF數(shù)據(jù)進(jìn)行存儲(chǔ)和處理。SW-store[3]、RDF-3x[4]、Hexastore[5]和gStore[6]能夠有效地處理大規(guī)模的RDF數(shù)據(jù),其中SW-store采用垂直分割存儲(chǔ),將三元組表按謂詞進(jìn)行分割,能夠快速合并聯(lián)接。目前多數(shù)SPARQL優(yōu)化技術(shù)主要通過(guò)制定一個(gè)最優(yōu)的查詢執(zhí)行計(jì)劃來(lái)減少中間結(jié)果。文獻(xiàn)[4]利用動(dòng)態(tài)規(guī)劃方法估計(jì)最優(yōu)的查詢執(zhí)行計(jì)劃,該方法需要指數(shù)級(jí)數(shù)量的時(shí)間和空間的開銷,而且沒有利用RDF數(shù)據(jù)圖結(jié)構(gòu)信息。文獻(xiàn)[6]提出一種VS樹和VS*樹索引,利用子圖匹配進(jìn)行帶通配符處理或精確的SPARQL查詢處理。文獻(xiàn)[7]通過(guò)RDF圖屬性路徑索引過(guò)濾掉冗余的中間結(jié)果,取得了較好的效果,但該方法不處理包含文字和空節(jié)點(diǎn)的三元組模式,并且只利用了屬性路徑索引信息。文獻(xiàn)[8]提出了一個(gè)對(duì)大規(guī)模RDF數(shù)據(jù)動(dòng)態(tài)計(jì)算查詢代價(jià)的查詢優(yōu)化方法,但該方法需要較大的存儲(chǔ)開銷。目前,基于分布式RDF存儲(chǔ)的查詢搜索引擎開發(fā)也吸引了很多研究者的注意[9-11],這些分布式RDF系統(tǒng)能夠減少輸入的聯(lián)結(jié),比集中式存儲(chǔ)更能有效地提高查詢性能,因?yàn)榫W(wǎng)絡(luò)上傳輸查詢中間結(jié)果的開銷很大。文獻(xiàn)[12]提出2個(gè)輔助的索引結(jié)構(gòu):ID-塊位矩陣和ID-謂詞位矩陣,通過(guò)查詢處理器動(dòng)態(tài)地產(chǎn)生聯(lián)結(jié)執(zhí)行的順序以降低中間結(jié)果。文獻(xiàn)[13]利用在原始的RDF數(shù)據(jù)圖上提煉有效的RDF圖索引,通過(guò)該索引進(jìn)行中間結(jié)果過(guò)濾。文獻(xiàn)[14]則結(jié)合哈希映射和選擇策略樹進(jìn)行SPARQL的查詢優(yōu)化。

為提高SPARQL查詢的執(zhí)行效率,本文根據(jù)RDF數(shù)據(jù)圖的結(jié)構(gòu)特點(diǎn),通過(guò)使用屬性路徑與基于關(guān)系的存儲(chǔ)模型,提出一種兩階段SPARQL查詢優(yōu)化方法。第一階段將SPARQL查詢按所含的公共變量進(jìn)行分塊,第二階段則利用選擇度計(jì)算最長(zhǎng)屬性路徑,從而過(guò)濾中間冗余結(jié)果。

1 SPARQL查詢及查詢執(zhí)行

SPARQL[15]已經(jīng)被W3C推薦為RDF數(shù)據(jù)的標(biāo)準(zhǔn)查詢語(yǔ)言,是一種通過(guò)在RDF數(shù)據(jù)上進(jìn)行三元組模式匹配來(lái)獲取結(jié)果的查詢語(yǔ)言。一個(gè)基本的SPARQL查詢由SELECT子句和WHERE子句構(gòu)成,其中,“pattern1”“pattern2”等都是三元組模式,操作符“.”聯(lián)結(jié)2個(gè)三元組模式,每個(gè)三元組模式都由主語(yǔ)、謂詞、賓語(yǔ)構(gòu)成,這三項(xiàng)為文字或者為變量。在查詢中,將已知的用文字表示,未知的用變量表示,如下所示。

SELECT ?variable1 ?variable2…

WHERE {pattern1.pattern2.… }

由LUBM基準(zhǔn)給出的第9個(gè)查詢實(shí)例Q9如下所示。在該實(shí)例查詢中,查詢所有學(xué)生、教師及課程并且滿足課程由學(xué)生選擇、教師教授學(xué)生、授課老師是學(xué)生的指導(dǎo)教師,“rdf”和“ub”都是前綴,“?X rdf:type ub:Student”等都是三元組模式。本文處理的SPARQL查詢可以包含謂詞為變量的三元組模式。

PREFIX rdf:

PREFIX ub:

SELECT ?X ?Y ?Z WHERE{

?X rdf:type ub:Student .

?Y rdf:type ub:Faculty .

?Z rdf:type ub:Course .

?X ub:advisor ?Y .

?Y ub:teacherOf ?Z .

?X ub:takesCourse ?Z}

圖1 Q9的一個(gè)查詢執(zhí)行計(jì)劃

表1 不同聯(lián)結(jié)產(chǎn)生的中間結(jié)果數(shù)量

2 SPARQL查詢優(yōu)化

本文優(yōu)化方法流程如圖2所示。在第一階段,將SPARQL查詢圖進(jìn)行分塊,在塊內(nèi)按每個(gè)聯(lián)結(jié)代價(jià)重新排序并執(zhí)行部分聯(lián)結(jié),代價(jià)的估計(jì)根據(jù)聯(lián)結(jié)產(chǎn)生中間結(jié)果的數(shù)量;在第二階段,利用最長(zhǎng)屬性路徑索引過(guò)濾掉冗余的中間結(jié)果,與文獻(xiàn)[7]方法中的屬性路徑過(guò)濾類似,但本文在過(guò)濾時(shí)使用最長(zhǎng)屬性路徑進(jìn)行匹配過(guò)濾,而不是某一個(gè)路徑長(zhǎng)度范圍內(nèi)的所有屬性路徑進(jìn)行過(guò)濾,避免了過(guò)多的重復(fù)計(jì)算。

圖2 本文方法流程

本文的查詢執(zhí)行計(jì)劃是一個(gè)圖而不是一棵樹,便于重用塊內(nèi)聯(lián)結(jié)的結(jié)果。以Q9的一個(gè)查詢圖(見圖3(a))為例,在第一階段,將SPARQL查詢圖按含有相同的聯(lián)結(jié)變量進(jìn)行分塊,圖3(b)即為Q9查詢圖的一個(gè)分塊,然后根據(jù)三元組模式都含有相同的聯(lián)結(jié)變量“?X”劃分為一塊。

圖3 Q9查詢圖及其分塊

2.1 選擇度計(jì)算

選擇度根據(jù)匹配聯(lián)結(jié)pn的三元組個(gè)數(shù)計(jì)算獲得,匹配的三元組數(shù)量越多,選擇度最小,計(jì)算公式如下:

SELECTIVITY=min(sel(p1),sel(p2),…,sel(pn))

如果#(p1)<#(p2)<#(p3),則sel(p1)>sel(p2)>sel(p3)。為節(jié)省空間和時(shí)間,選擇度的計(jì)算針對(duì)至多含有一個(gè)查詢變量的三元組模式。最頻繁的一種三元組模式是(?S,P,O),即給定三元組的主語(yǔ)P、謂詞O,返回對(duì)應(yīng)三元組中主語(yǔ)S的值。

本文建立一個(gè)OPS(賓語(yǔ),謂詞,主語(yǔ))索引[5]計(jì)算選擇度。指定賓語(yǔ)和謂詞可以獲取對(duì)應(yīng)的主語(yǔ)id列表和匹配的三元組個(gè)數(shù),以此來(lái)實(shí)現(xiàn)塊內(nèi)最優(yōu)執(zhí)行計(jì)劃,索引結(jié)構(gòu)如表2所示,其目的是先執(zhí)行聯(lián)結(jié)次數(shù)較少的聯(lián)結(jié),減少不必要的聯(lián)結(jié)。

表2 OPS索引結(jié)構(gòu)

2.2 屬性路徑索引

本節(jié)介紹屬性路徑索引,對(duì)第二階段剩余聯(lián)結(jié)進(jìn)行過(guò)濾。屬性路徑索引是從RDF數(shù)據(jù)圖中提取的,本文的RDF數(shù)據(jù)圖的定義采用文獻(xiàn)[16]中的定義:

定義1一個(gè)RDF數(shù)據(jù)圖是一個(gè)三元組(V,L,E)。其中:V是一個(gè)有限的節(jié)點(diǎn)集,VE表示實(shí)體節(jié)點(diǎn),VC表示類節(jié)點(diǎn),VV表示數(shù)據(jù)節(jié)點(diǎn),構(gòu)成不相交的并集VEVCVV;L是一個(gè)有限的邊標(biāo)簽集合,L=LRLA{type,subclass},LR代表實(shí)體之間的邊,LA代表實(shí)體和數(shù)據(jù)值之間的邊;E是一個(gè)有限的邊集,邊的形式為:e(v1,v2),v1,v2∈VE,e∈L,只有v1,v2∈VE,e∈LR;e∈LA,當(dāng)且僅當(dāng)v1∈VE且v2∈VV;e=type當(dāng)且僅當(dāng)v1∈VE且v2∈VC;及e=subclass當(dāng)且僅當(dāng)v1,v2∈VC。

本文定義一個(gè)RDF實(shí)體關(guān)系圖以用于建立屬性路徑索引:

定義2一個(gè)RDF實(shí)體關(guān)系圖G’是一個(gè)三元組(V’,L’,E’),其中,頂點(diǎn)V’=VE,邊標(biāo)簽L’=LR,且E’?E,E’聯(lián)結(jié)2個(gè)實(shí)體節(jié)點(diǎn)。VE表示實(shí)體頂點(diǎn)的集合(例如IRIs),只有RDF數(shù)據(jù)中存在邊e(v1,v2)∈E’并且v1,v2∈VE,RDF實(shí)體關(guān)系圖中存在邊e(v1,v2)∈VE。

本文的屬性路徑索引是建立在RDF實(shí)體關(guān)系圖上,不包括數(shù)值類型的三元組,如圖4所示。包含數(shù)值的三元組在第一階段進(jìn)行處理。

圖4 RDF實(shí)體關(guān)系示意圖

定義3入邊屬性路徑是一個(gè)三元組謂詞的序列,如果一條路徑的終端節(jié)點(diǎn)是n,則稱這是一條節(jié)點(diǎn)n的入邊屬性路徑。

例如,Q9中的“?X ub:advisor ?Y.?Y ub:teacherOf ?Z”聯(lián)結(jié),存在一條“?Z”的入邊屬性路徑“ub:advisor→ub:teacherOf”。表3顯示了圖4中的屬性路徑索引指向的頂點(diǎn)列表。例如,如果某一個(gè)SPARQL查詢中存在聯(lián)結(jié)“?n1p1?n2.?n2.p2?n3.?n3?p3?n4”,可以通過(guò)找到屬性路徑“”所包含的節(jié)點(diǎn)列表“v8,v9”對(duì)結(jié)果集進(jìn)行過(guò)濾,而不必進(jìn)行大量中間結(jié)果集的合并。

表3 屬性路徑索引指向的頂點(diǎn)

本文使用前綴樹結(jié)構(gòu)存儲(chǔ)屬性路徑索引,前綴樹中的每一節(jié)點(diǎn)有一個(gè)指向?qū)?yīng)謂詞路徑的節(jié)點(diǎn)列表的指針。該屬性路徑索引結(jié)構(gòu)與信息檢索中的倒排索引有些類似。每個(gè)入邊屬性路徑可以看作是倒排索引的一個(gè)單詞,節(jié)點(diǎn)列表相當(dāng)于倒排索引中排序的文檔ID號(hào)。屬性路徑索引中有大量重復(fù)的部分,如圖5所示,、、等都包含p1、p2,如果不采用前綴樹存儲(chǔ),就需要更多的存儲(chǔ)單元來(lái)存儲(chǔ)重復(fù)的路徑信息。因此,通過(guò)前綴樹對(duì)具有相同的謂詞前綴可以只存儲(chǔ)一次,節(jié)省了存儲(chǔ)空間。通過(guò)屬性路徑索引可以快速找到指定屬性路徑對(duì)應(yīng)的節(jié)點(diǎn)列表,從而起到過(guò)濾冗余節(jié)點(diǎn)的作用。對(duì)于屬性路徑的長(zhǎng)度取值如表3所示。本文按照文獻(xiàn)[8]中的經(jīng)驗(yàn)值取最大值為3。為更好地對(duì)數(shù)據(jù)進(jìn)行壓縮存儲(chǔ),本文并不存儲(chǔ)實(shí)際的節(jié)點(diǎn)ID號(hào),而是以節(jié)點(diǎn)ID號(hào)差值代之,這與文獻(xiàn)[4]中的壓縮三元組相似。

圖5 屬性路徑索引的前綴樹

圖6所示為當(dāng)SPARQL查詢中含有謂詞為變量的聯(lián)結(jié)的情況。把謂詞變量當(dāng)作一個(gè)特殊的謂詞處理,用pv代替。例如,在圖6中,頂點(diǎn)“?v4”的所有入邊屬性路徑為、、,將“?p”用pv代替,其中,Vlist(p1,pv)是謂詞路徑p1→pv對(duì)應(yīng)的頂點(diǎn)集合,并且這些屬性路徑的第一個(gè)謂詞必須是p1。

圖6 含有謂詞變量的SPARQL查詢

本文的兩階段查詢處理算法描述如下:

算法兩階段SPARQL查詢優(yōu)化算法

輸入SPARQL查詢queryStr,屬性路徑前綴樹Trie

輸出合并聯(lián)結(jié)后的結(jié)果集Results

1.Parse queryStr;

2.Block queryStr into n blocks;/*對(duì)所有的聯(lián)結(jié)進(jìn)行分塊,把含有公共變量的聯(lián)結(jié)劃分為一塊*/

3.For i←0 to n-1

4.Filter out joins with (?S,P,O) by get Variable Selectivity(queryStr.variable[i]) in order;/*對(duì)每個(gè)分塊中(?S,P,O)的聯(lián)結(jié)利用選擇度進(jìn)行過(guò)濾*/

5.end For

6.For each variable v∈Variables

7.filterList←getVertexList(Trie,v);

8.Combine Results using filterList;/*Variables存放queryStr中的所有變量,通過(guò)前綴樹Trie,用每個(gè)變量的最長(zhǎng)入邊屬性路徑過(guò)濾冗余的節(jié)點(diǎn),并對(duì)過(guò)濾后的結(jié)果集Results進(jìn)行合并*/

9.end For

10.Output Results;

該算法主要分為3個(gè)部分:

1)對(duì)輸入的SPARQL查詢進(jìn)行分析并分塊(算法第1步和第2步)。

2)對(duì)于塊內(nèi)的每個(gè)形如(?S,P,O)的三元組模式,利用選擇度函數(shù)getVariableSelectivity進(jìn)行過(guò)濾(算法第3步～第5步),在該階段內(nèi)利用選擇度函數(shù)將對(duì)形式為(?S,P,O)的聯(lián)結(jié)進(jìn)行重新排序,首先執(zhí)行當(dāng)前查詢模式中聯(lián)接代價(jià)最小的查詢模式,盡可能地降低在查詢過(guò)程中產(chǎn)生的中間結(jié)果的數(shù)量。

3)對(duì)剩余的三元組利用屬性路徑索引Trie進(jìn)行過(guò)濾(算法第6步～第9步),這是第2輪的中間結(jié)果過(guò)濾,因?yàn)閷傩月窂街辽侔粋€(gè)三元組模式,所以利用屬性路徑過(guò)濾能夠比單個(gè)三元組模式過(guò)濾掉更多的中間結(jié)果,最后輸出顯示合并后的結(jié)果(算法第10步)。

本文算法的時(shí)間復(fù)雜度主要由第6步～第9步?jīng)Q定,為O(n×e),其中,n為輸入的SPARQL查詢中變量的數(shù)量,e為SPARQL查詢中每個(gè)變量的平均入邊數(shù)量。算法的時(shí)間受SPARQL查詢中變量的數(shù)量以及變量的入邊數(shù)量影響。

3 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)使用公開數(shù)據(jù)集LUBM、YAGO2、SPARQL基準(zhǔn)數(shù)據(jù)集(SP2B)[17]及DBpedia SPARQL 基準(zhǔn)數(shù)據(jù)集(DBSPB)[18],并用開源的RDF-3X[4]系統(tǒng)(0.3.5版本)、TripleBit[12]做比較。通過(guò)LUBM的generator,產(chǎn)生了10 000個(gè)大學(xué)的LUBM數(shù)據(jù)集。表4是這4個(gè)數(shù)據(jù)集的統(tǒng)計(jì)信息。其中,

YAGO2包含94個(gè)謂詞,LUBM和SP2B分別包含17個(gè)和77個(gè)謂詞,DBSPB包含39 675個(gè)謂詞。DBSPB是多個(gè)領(lǐng)域數(shù)據(jù)集的合并,YAGO2是一個(gè)異構(gòu)數(shù)據(jù)集Wordnet和Wikipedia的合并,而LUBM和SP2B則是關(guān)于同類領(lǐng)域關(guān)系的描述。

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

表5顯示了最大長(zhǎng)度為3的屬性路徑索引信息,包括屬性路徑索引指向的節(jié)點(diǎn)數(shù)量以及整個(gè)索引的大小。因?yàn)長(zhǎng)UBM數(shù)據(jù)集具有相對(duì)單一結(jié)構(gòu)化的模式特點(diǎn),所以其包含較少的節(jié)點(diǎn)。

表5 屬性路徑索引信息

本文使用LUBM數(shù)據(jù)集基準(zhǔn)中Q1～Q9進(jìn)行比較實(shí)驗(yàn)。表6顯示了2種方法對(duì)Q1～Q9產(chǎn)生的中間結(jié)果數(shù)量。通過(guò)比較可知:無(wú)論是簡(jiǎn)單結(jié)構(gòu)查詢還是復(fù)雜結(jié)構(gòu)查詢?nèi)鏠2和Q9,本文方法都比RDF-3X產(chǎn)生更少的中間結(jié)果;在查詢Q1與Q5上,本文方法與TripleBit方法產(chǎn)生的中間結(jié)果數(shù)量比較接近,因?yàn)闆]有找到可過(guò)濾的屬性路徑索引。

表6 LUBM數(shù)據(jù)集中間結(jié)果數(shù)量

從YAGO2中,挑選屬性路徑長(zhǎng)度為3～7的查詢各10個(gè),計(jì)算平均查詢執(zhí)行時(shí)間和中間結(jié)果數(shù)量。圖7顯示了平均執(zhí)行時(shí)間和中間結(jié)果的數(shù)量隨著屬性路徑長(zhǎng)度的變化情況。從中可以看出:除了屬性路徑長(zhǎng)度為3時(shí)外,本文方法的執(zhí)行時(shí)間和中間結(jié)果數(shù)量整體上都要低于RDF-3X,而且本文方法的執(zhí)行時(shí)間和中間結(jié)果數(shù)量隨著屬性路徑長(zhǎng)度變化增加緩慢;3種方法的執(zhí)行時(shí)間曲線都隨著屬性路徑長(zhǎng)度的增加而上升;本文方法雖然不是整體上都超過(guò)了TripleBit方法,但在路徑長(zhǎng)度為3、4時(shí)本文方法與TripleBit方法的曲線非常接近,但本文的執(zhí)行時(shí)間曲線比方法RDF-3X和TripleBit都平滑。TripleBit每次選擇最小的選擇性變量所對(duì)應(yīng)的查詢模式執(zhí)行,以此來(lái)降低在查詢過(guò)程中的中間結(jié)果集的大小,TripleBit性能降低的主要原因是查詢中包含更多聯(lián)結(jié)或者訪問更多選擇度索引塊。所以,對(duì)于屬性路徑長(zhǎng)度較小的查詢,本文方法與TripleBit方法過(guò)濾效果相差不大,但對(duì)于屬性路徑較長(zhǎng)的查詢,本文方法優(yōu)于TripleBit方法。

圖7 YAGO2數(shù)據(jù)集上的查詢性能比較

為驗(yàn)證本文方法能夠適用于各種不同的RDF數(shù)據(jù)集,對(duì)數(shù)據(jù)集DBSPB和SP2B分別構(gòu)建查詢Q10～Q13和Q14～Q17,查詢結(jié)果如圖8所示。這些查詢都有4次～5次的聯(lián)接次數(shù)并且有較長(zhǎng)的屬性路徑。查詢的執(zhí)行時(shí)間分別顯示在圖9(a)和圖9(b)中。從中可以看出,除了查詢Q10與Q17外,本文方法在這兩個(gè)數(shù)據(jù)集上實(shí)現(xiàn)的查詢執(zhí)行時(shí)間都優(yōu)于RDF-3X與TripleBit方法。查詢Q11、Q12、Q13、Q15、Q14及Q16在執(zhí)行時(shí)間上明顯少于RDF-3X與TripleBit方法,主要原因是本文通過(guò)最長(zhǎng)屬性路徑索引過(guò)濾掉大量無(wú)用的中間結(jié)果,TripleBit方法對(duì)于聯(lián)結(jié)比較多的查詢需要?jiǎng)討B(tài)計(jì)算最優(yōu)選擇性的三元組模式并且需要訪問更多的索引塊。對(duì)于查詢Q10與Q17,雖然沒有TripleBit方法執(zhí)行效率高,但是相差不大,沒有超過(guò)的原因是在前綴樹索引結(jié)構(gòu)中沒有找到可過(guò)濾的屬性路徑。

圖8 本文方法在DBSPB和SP2B數(shù)據(jù)集上的SPARQL查詢結(jié)果

圖9 查詢執(zhí)行時(shí)間比較

4 結(jié)束語(yǔ)

本文提出一種兩階段的SPARQL查詢處理方法,一方面通過(guò)計(jì)算選擇度找出聯(lián)結(jié)數(shù)最小的聯(lián)結(jié),另一方面利用屬性路徑索引過(guò)濾冗余中間結(jié)果。雖然屬性路徑索引的存儲(chǔ)耗費(fèi)了一定的存儲(chǔ)空間,但大幅提高了SPARQL查詢的執(zhí)行效率。在不同的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法對(duì)中間結(jié)果過(guò)濾的可行性、有效性。未來(lái)將進(jìn)一步提高聯(lián)結(jié)選擇度計(jì)算的準(zhǔn)確度,并將本文方法運(yùn)用到MapReduce等并行及分布式環(huán)境中。