王 鑫,徐 強(qiáng),柴樂樂,楊雅君,4,柴云鵬

1(天津大學(xué) 智能與計算學(xué)部,天津 300354)

2(天津市認(rèn)知計算與應(yīng)用重點(diǎn)實驗室,天津 300354)

3(中國人民大學(xué) 信息學(xué)院,北京 100872)

4(數(shù)字出版技術(shù)國家重點(diǎn)實驗室,北京 100871)

智能數(shù)據(jù)管理是人工智能發(fā)展的重要基石.知識圖譜是智能數(shù)據(jù)的主要表現(xiàn)形式.資源描述框架(resource description framework,簡稱RDF)是由國際萬維網(wǎng)聯(lián)盟(W3C)制定的表示知識圖譜的推薦標(biāo)準(zhǔn).隨著知識圖譜相關(guān)技術(shù)的不斷發(fā)展,RDF三元組數(shù)據(jù)日益激增,并且被廣泛地應(yīng)用在多個領(lǐng)域,包括科學(xué)、生物信息、商業(yè)智能和社交網(wǎng)絡(luò)等[1].在現(xiàn)實世界中,RDF數(shù)據(jù)集往往達(dá)到數(shù)億條三元組數(shù)據(jù).目前,如何有效管理大規(guī)模 RDF智能圖數(shù)據(jù)受到越來越多的關(guān)注.與傳統(tǒng)的關(guān)系型數(shù)據(jù)庫中進(jìn)行的查詢不同,RDF數(shù)據(jù)上 SPARQL的基本圖模式(BGP)操作語義等價于數(shù)學(xué)上的子圖同態(tài)[2],這是一個著名的NP完全問題[3],即SPARQL查詢可以轉(zhuǎn)化為子圖匹配問題.因此,提高SPARQL查詢性能已成為亟待解決的技術(shù)問題.

RDF數(shù)據(jù)模型是一種特殊的語義圖數(shù)據(jù)模型,表示為實體-關(guān)系或者類關(guān)系圖,基本構(gòu)件包括實體、屬性和值,通過屬性和值描述資源之間的關(guān)系.每條RDF三元組數(shù)據(jù)的格式為(s,p,o),是一個陳述,其中,s是主語,p是謂語,o是賓語.(s,p,o)表示資源s與資源o之間具有聯(lián)系p,或表示資源s具有屬性p且其取值為o.RDF數(shù)據(jù)的主語和謂語都是以統(tǒng)一資源標(biāo)識符(uniform resource identifier,簡稱URI)來標(biāo)識,賓語以URI或者字面值(literal)標(biāo)識.一條三元組數(shù)據(jù)可以被看做一條有向邊,其中,主語和賓語為頂點(diǎn).一個三元組的賓語可作為另一個三元組中的主語,于是,RDF數(shù)據(jù)形成一種有向標(biāo)簽圖.

RDF智能圖數(shù)據(jù)上的查詢語言隨著RDF數(shù)據(jù)的發(fā)展不斷發(fā)展,早期查詢語言包括RQL,RDQL,SquishQLD等[4].目前被廣泛使用的是SPARQL(simple protocol and RDF query language),該查詢語言是W3C提出的RDF圖上的標(biāo)準(zhǔn)查詢語言.基本圖模式(basic graph pattern,簡稱BGP)是SPARQL中最常用、最基本的查詢模式.實際上,每個SPARQL查詢的核心部分是一個BGP查詢.例如:在維基百科數(shù)據(jù)集DBpedia中查詢內(nèi)陸國家及其人口數(shù),SPARQL BGP查詢?nèi)鐖D1所示.

Fig.1 An example SPARQL BGP queryQ圖1 示例SPARQL BGP查詢Q

目前,處理大規(guī)模RDF智能圖數(shù)據(jù)查詢的研究工作分為兩大類——單機(jī)和分布式.單機(jī)SPARQL查詢引擎,如RDF-3X[5]和gStore[6],采用基于空間換時間策略構(gòu)建不同的索引方案,利用索引減少查詢匹配的搜索空間;分布式SPARQL查詢處理系統(tǒng)以是否采用分解查詢圖策略分為兩類:一類方法將SPARQL查詢圖分解為三元組模式(triple pattern,至少包含一個變量的三元組)[7-11]或者帶有局部結(jié)構(gòu)信息子圖的集合,先對分解后的查詢子圖進(jìn)行匹配,之后對子圖的匹配結(jié)果進(jìn)行連接操作獲得最終匹配結(jié)果;另一類方法直接處理完整查詢圖[12-14],大部分通過圖探索減少連接操作的較高代價,通過優(yōu)化探索計劃提高查詢性能.

本文將RDF圖內(nèi)嵌的語義和結(jié)構(gòu)作為啟發(fā)式信息(h-值),并利用h-值將RDF查詢圖分解為星形結(jié)構(gòu)(高度為1的樹)的集合進(jìn)行匹配.Lai等人[15]指出:無向無標(biāo)簽圖上基于星形-連接的算法[16]在評估包含多邊的星形時會生成大量中間匹配結(jié)果,如:將包含3條邊的星形結(jié)構(gòu)匹配到最大度為1 000的數(shù)據(jù)圖,產(chǎn)生109個匹配結(jié)果.為此,他們提出了基于MapReduce[17]的TwinTwigJoin算法,將查詢圖分解成TwinTwig結(jié)構(gòu),該結(jié)構(gòu)只包含一條邊或兩條相連的邊.造成上述問題的根本原因是:頂點(diǎn)和邊缺乏可區(qū)別信息時,星型結(jié)構(gòu)匹配過程可能會產(chǎn)生大量的中間結(jié)果.但是RDF圖中的頂點(diǎn)標(biāo)簽是獨(dú)一無二的URIs,同時,邊是有方向且?guī)?biāo)簽的,因此,Lai等人在文獻(xiàn)[15]中提出的問題在RDF圖中不存在.與分解成TwinTwig結(jié)構(gòu)[15]相比,星形分解策略可以保持更多原始查詢圖的信息,同時,在MapReduce計算模型下可以在更少次MapReduce迭代操作內(nèi)結(jié)束查詢.

本文的主要貢獻(xiàn)如下:

(1) 提出了基于MapReduce計算模型的有效SPARQL基本圖模式匹配算法,利用RDF智能圖數(shù)據(jù)豐富的語義和自身的圖特性設(shè)計星形分解策略,并給出中間結(jié)果較少的星形匹配順序來提高查詢效率,每輪MapReduce操作按序連接一個星形結(jié)構(gòu)直至匹配結(jié)束;

(2) 為進(jìn)一步提高算法的性能,引入兩種優(yōu)化技術(shù):一個通過基于布隆過濾器的鄰居信息編碼技術(shù)過濾MapReduce操作中的無用數(shù)據(jù)輸入,另一個技術(shù)推遲笛卡爾積操作以提高查詢效率;

(3) 在主流大數(shù)據(jù)處理框架 Spark下實現(xiàn)了上述算法,并在標(biāo)準(zhǔn)合成數(shù)據(jù)集 WatDiv[18]和真實數(shù)據(jù)集DBpedia上進(jìn)行了大量實驗,驗證了算法的有效性、高效性和可伸縮性,并對查詢匹配的時間開銷與數(shù)據(jù)集規(guī)模及集群中節(jié)點(diǎn)數(shù)量的關(guān)系進(jìn)行分析.

本文第1節(jié)介紹相關(guān)工作.第2節(jié)介紹RDF圖和SPARQL基本圖模式查詢的預(yù)備知識.第3節(jié)描述如何存儲RDF數(shù)據(jù),分解SPARQL查詢,并在分布式計算框架MapReduce下匹配查詢.第4節(jié)提出兩種優(yōu)化技術(shù):一個通過基于布隆過濾器的鄰居信息編碼過濾掉 MapReduce迭代中無用的數(shù)據(jù)輸入;另一優(yōu)化技術(shù)將星形匹配過程中的笛卡爾積推遲到MapReduce迭代結(jié)束來減少該過程中大量無用的笛卡爾積.第5節(jié)在標(biāo)準(zhǔn)合成數(shù)據(jù)集和真實數(shù)據(jù)集上進(jìn)行實驗,并在第6節(jié)對全文總結(jié).

1 相關(guān)工作

近年來,研究者逐步意識到圖數(shù)據(jù)管理的重要性,高效處理RDF數(shù)據(jù)已成為該方向的研究熱點(diǎn)之一.本節(jié)將對目前已有的大規(guī)模RDF數(shù)據(jù)上SPARQL查詢研究工作進(jìn)行介紹,主要分為以下兩類.

1.1 單機(jī)系統(tǒng)上的RDF圖查詢處理

RDF-3X查詢引擎[5]采用原生態(tài)的三元組存儲模式,將RDF數(shù)據(jù)和按照SPO排列的15種SPO(包含SPO中1,2或3個)索引壓縮存儲在B+-樹中,以冗余存儲提高查詢性能.該方法通過自底向上的動態(tài)規(guī)劃算法選擇出代價最優(yōu)的連接順序.另外,RDF-3X收集單個實體的統(tǒng)計信息,大量使用合并連接來換取較高查詢效率.gStore[6]是基于圖的單機(jī) SPARQL查詢引擎,使用鄰接鏈表存儲 RDF圖,并將頂點(diǎn)類和實體用固定長度的比特串編碼壓縮存儲,通過建立VS*-樹索引結(jié)構(gòu)提高查詢處理效率并采用剪枝策略減少搜索空間.

隨著Tim Berners-Lee發(fā)起的Linked Data運(yùn)動的持續(xù)推進(jìn),各個領(lǐng)域發(fā)布的RDF數(shù)據(jù)一直持續(xù)增長,數(shù)據(jù)規(guī)模達(dá)到百億級.單機(jī)已經(jīng)無法有效處理現(xiàn)有規(guī)模 RDF數(shù)據(jù)上的 SPARQL查詢[19],分布式/并行技術(shù)已成為RDF數(shù)據(jù)管理不可或缺的工具.

1.2 分布式系統(tǒng)上的RDF圖查詢處理

近年來,大量研究者和實踐者提出了若干種方法分布式處理大規(guī)模RDF圖上的SPARQL查詢問題,分兩類敘述.

(1) 分解查詢圖.

SHARD[7]基于三元組存儲處理RDF數(shù)據(jù)集上的SPARQL查詢,查詢圖被分解為三元組模式(包含變量的三元組,即一個查詢子句)的集合,通過在三元組模式上迭代將變量綁定到數(shù)據(jù)圖的頂點(diǎn),該綁定必須同時滿足查詢中的所有約束.每一輪 MapRedue操作通過連接操作只添加一個查詢子句.類似地,HadoopRDF[8]中查詢圖的最小分解單位也是三元組模式,并且它也使用MapReduce計算框架將RDF三元組基于謂語劃分到多個小文件中.SPARQL查詢中的一個子句,也就是一個三元組模式,只能同時參與到一個 Hadoop作業(yè)中.這兩種方法都沒有使用查詢圖的結(jié)構(gòu)信息,需要過多的MapReduce迭代操作,并且大量的連接操作導(dǎo)致很高的查詢代價.而本文利用部分圖的結(jié)構(gòu)特性,在每次MapReduce迭代中添加一個星形,可以在更少的迭代次數(shù)內(nèi)完成查詢匹配,從而提高查詢效率.同樣地,S2X[9]雖然建立在分布式圖計算框架GraphX[20]上實現(xiàn)SPARQL的BGP匹配,查詢圖也被分解成查詢子句,也就是三元組模式.首先,BGP查詢中所有的三元組模式被匹配;其次,通過迭代計算逐漸舍棄部分中間結(jié)果;最后,將剩余的匹配結(jié)果進(jìn)行連接操作,這一階段可能會導(dǎo)致大量的中間結(jié)果.另外,Virtuoso[10]和S2RDF[11]基于關(guān)系數(shù)據(jù)庫處理RDF圖查詢,將SPARQL查詢子句轉(zhuǎn)化為SQL語句,通過關(guān)系表的連接操作得到匹配結(jié)果.S2RDF[11]引入關(guān)系劃分模型ExtVP存儲RDF數(shù)據(jù),該方法基于Spark[21]并行計算框架,可以有效最小化查詢輸入大小.但是ExtVP存儲方案的預(yù)處理需要提前在垂直劃分表上作大量的連接操作,代價非常高.本文將RDF圖分布式存儲在多個鄰接鏈表中,可以同時在各個主語頂點(diǎn)的鄰接鏈表上并行進(jìn)行MapReduce計算,加快查詢處理.

(2) 完整查詢圖.

Trinity.RDF[12]將RDF數(shù)據(jù)模型化為原始圖的形式,并使用鍵-值存儲RDF數(shù)據(jù),將頂點(diǎn)標(biāo)識符作為鍵,頂點(diǎn)的鄰接鏈表作為值.采用基于代價的方法找到最優(yōu)探索計劃,利用圖探索而不是連接操作減少中間結(jié)果量,但是最終結(jié)果需要在集群中心節(jié)點(diǎn)上使用單線程獲得.此外,Peng等人[13]采用局部計算和裝配的分布式框架基于gStore執(zhí)行SPARQL查詢.在局部計算階段,集群中每個節(jié)點(diǎn)匹配完整查詢,然后在裝配階段,大量的本地局部匹配結(jié)果被發(fā)送到中心節(jié)點(diǎn)進(jìn)行連接操作獲得最終的結(jié)果.當(dāng)匹配過程的中間結(jié)果規(guī)模較大時,這兩種方法在最后階段可能是一個性能瓶頸,而本文可以通過 Reduce函數(shù)并行連接星形匹配結(jié)果得到答案集.TriAD[14]使用MPI協(xié)議處理SPARQL查詢,建立6個SPO索引,并將RDF三元組劃分到這些索引中,同時,使用基于本地的概括圖加速查詢.同樣,采用自底向上的動態(tài)規(guī)劃算法確定最小代價估計的三元組模式匹配順序.但是與本文方法相比,TriAD中大量的索引導(dǎo)致數(shù)據(jù)冗余,空間消耗大,如果數(shù)據(jù)變動需更新大量索引.

不同于以上方法,本文將SPARQL BGP查詢圖分解為星形的集合,利用RDF數(shù)據(jù)豐富語義和圖的結(jié)構(gòu)確定中間結(jié)果較少的星形匹配順序.在MapReduce并行計算中,Map函數(shù)在分布式鄰接鏈表上并行匹配星形,Reduce函數(shù)并行連接星形與已經(jīng)生成的查詢子圖的匹配結(jié)果,加快查詢速度.

2 預(yù)備知識

本節(jié)將詳細(xì)介紹相關(guān)背景知識,包括RDF圖、SPARQL BGP查詢圖、BGP匹配及星形分解等定義,為理解本文后續(xù)算法奠定基礎(chǔ).

2.1 RDF圖及SPARQL查詢

定義1(RDF圖).設(shè)U和L分別是統(tǒng)一資源標(biāo)識符和字面值的有限集合,元組(s,p,o)∈U×U×(U∪L)叫做RDF三元組,每個三元組t=(s,p,o)表示資源s和資源o有關(guān)系p,或者資源s有值為o的屬性p,其中,s,p和o分別表示主語、謂語和賓語.一個有限三元組的集合被稱為RDF圖.用V,E,Σ分別表示RDF圖G的頂點(diǎn)、邊和邊標(biāo)簽的集合,正式定義為:V={s|(s,p,o)∈G}∪{o|(s,p,o)∈G},E?V×V,并且Σ={p|(s,p,o)∈G}.函數(shù)lab:E→Σ返回圖G中邊的標(biāo)簽.

本文定義的RDF圖不考慮RDF標(biāo)準(zhǔn)定義中的空節(jié)點(diǎn)(blank node),實際上,本文所研究的問題與空節(jié)點(diǎn)的包含是正交的,在RDF圖定義中省略空節(jié)點(diǎn)是為了使表述更簡潔.圖2是從DBpedia數(shù)據(jù)集中摘取的RDF圖示例G,為節(jié)省空間,對URI進(jìn)行了壓縮表示.RDF數(shù)據(jù)中的每條三元組可以被看做是RDF圖中一條有向帶標(biāo)簽的邊.

定義2(查詢圖).用Var表示與U和L不相交的變量的無限集合,Var中每個元素的名字按照慣例以字符“?”開始(如?x∈Var).RDF圖G上的 SPARQL基本圖模式(basic graph pattern,簡稱 BGP)查詢Q被定義為如下形式:Q={(si,pi,oi)|(si,pi,oi)∈(U∪Var)×(U∪Var)×(U∪L∪Var)},其中,tpi=(si,pi,oi)是三元組模式.SPARQL BGP 查詢Q也被稱為查詢圖GQ.

Fig.2 An example RDF graphG圖2 RDF示例圖G

用V(Q),E(Q)分別表示查詢圖GQ中頂點(diǎn)和邊的集合,對每一個頂點(diǎn)u∈V(Q),如果u∈Var,那么u可以匹配RDF圖G中的任意頂點(diǎn)v∈V;否則,u只可以匹配與它標(biāo)簽相同的頂點(diǎn)v∈V.

定義3(SPARQL BGP匹配).RDF圖G上的SPARQL BGP查詢Q的語義定義為:

(1)μ是從V(Q)中的頂點(diǎn)到V中頂點(diǎn)的映射;

(2) (G,μ)Q當(dāng)且僅當(dāng)對任意(si,pi,oi)∈Q滿足:i)si和oi可以分別匹配μ(si)和μ(oi);ii) (μ(si),μ(oi))∈E;

iii)pi∈Var或lab((μ(si),μ(oi)))與pi相同;

(3)Ω(Q)是使(G,μ)Q滿足的μ的集合,也就是RDF圖G上SPARQL BGP查詢GQ的答案集.

定義4(星形).星形是一棵高度為1的樹,表示為T=(r,L),其中:(1)r是T的根節(jié)點(diǎn);(2)L是二元組(pi,li)的集合,也就是說,li是樹T的葉子,(r,pi,li)是從r到li的邊.用V(T)和E(T)分別表示星形T中頂點(diǎn)和邊的集合.

定義5(星形分解).SPARQL BGP查詢Q={tp1,…,tpn}的星形分解定義為D={T1,…,Tm},其中,(1)Ti是一個星形;(2).

根據(jù)定義4可知:本文定義的星形結(jié)構(gòu)中,邊的方向都是從根節(jié)點(diǎn)指向葉子節(jié)點(diǎn).用Sub(Q)表示查詢Q中主語的集合,那么Sub(Q)就是查詢Q的星形分解D中星形根節(jié)點(diǎn)的集合.如圖3所示,給出SPARQL BGP示例查詢圖Q1及其星形分解D1,包含3個星形T1,T2,和T3.

Fig.3 An example SPARQL BGP query graphQ1and the corresponding star decompositionD1圖3 SPARQL BGP示例查詢圖Q1及其星形分解D1

2.2 MapReduce并行計算模型

MapReduce是谷歌提出的用來處理和生成大數(shù)據(jù)集的并行編程模型,可以運(yùn)行在由很多普通機(jī)器組成的集群上[18].MapReduce的用戶通過自己編寫Map和Reduce兩個函數(shù)來表達(dá)并行計算.MapReduce計算模型具體定義如下.

定義6(MapReduce計算模型).MapReduce計算模型中包括若干輪Map和Reduce任務(wù),每輪MapReduce任務(wù)包括一個 Map函數(shù)和一個 Reduce函數(shù),其中,Map函數(shù)定義為 Map:(k1,v1)→[(k2,v2)],Reduce函數(shù)定義為Reduce:(k2,[v2])→[(k3,v3)],其中,[(ki,vi)]表示key/value對的列表.在Map和Reduce之間是一個shuffle過程,該過程中,相同key的全部value值被發(fā)送給同一Reduce函數(shù).

在MapReduce計算中,Map函數(shù)輸入一個key/value對(k1,v1),輸出新的key/value對集合[(k2,v2)]作為中間結(jié)果,并將此輸出發(fā)送給Reduce函數(shù),Reduce函數(shù)以接收到的一個中間值key和對應(yīng)于該key的value集合,也就是(k2,[v2])作為輸入,通過歸并這些value,生成新的key/value集合[(k3,v3)]并輸出.

3 BGP查詢匹配算法

本節(jié)詳細(xì)介紹本文的 SPARQL BGP查詢匹配方法,具體分為3部分:首先,采用分布式鄰接鏈表存儲RDF圖;其次,將給定的SPARQL BGP查詢分解為星形的集合并確定這些星形的匹配順序;最后介紹基于MapReduce模型的分布式算法.

3.1 存儲模式

本文采用分布式鄰接鏈表模式存儲RDF圖,對RDF圖中的頂點(diǎn)v∈V,用N(v)表示頂點(diǎn)v的鄰居信息,N(v)={(pi,vi)|(v,pi,vi)∈G}.RDF示例圖G的鄰接鏈表存儲方案見表1.RDF三元組中,URIs或者字面值通常是很長字符串,如果直接存儲大規(guī)模的原始數(shù)據(jù)而不做其他改變,會浪費(fèi)大量的存儲空間.本文采用編碼映射方法,用唯一的ID(整數(shù))代替RDF圖中頂點(diǎn)和邊的標(biāo)簽,也就是URIs或者字面值.通過該方法可以壓縮RDF數(shù)據(jù)集的存儲空間,同時,用整數(shù)代替長的字符串可以簡化并加速后期的SPARQL查詢處理.

Table 1 Adjacency list storage schema表1 鄰接鏈表存儲模式

3.2 基于貪心策略的星形分解

這里介紹基于RDF圖的結(jié)構(gòu)信息和RDF內(nèi)含語義的星形分解算法,該算法利用本文自定義的啟發(fā)式信息h-值對SPARQL BGP查詢圖Q進(jìn)行分解,并找到中間結(jié)果較少的星形匹配順序,從而提高SPARQL BGP的查詢性能.

在本文中,星形是最小的匹配單位,在RDF圖的鄰接鏈表N(v)上匹配星形T時,如果星形T的根節(jié)點(diǎn)可以匹配鄰接鏈表N(v)的主語頂點(diǎn)v,對于星形T的所有葉子節(jié)點(diǎn)li得到它們在鄰接鏈表N(v)上可以匹配的頂點(diǎn)的集合,本文將此集合定義為葉子節(jié)點(diǎn)li的候選集S(li).接下來具體介紹星形在RDF鄰接鏈表上的匹配過程,其匹配算法的偽代碼見算法1.

算法1.星形匹配算法.

輸入:星形T=(r,L),其中,L={(p1,l1),…,(pt,lt)},v∈V,鄰接鏈表N(v);

輸出:星形T在N(v)上的匹配結(jié)果:Ωv(T)={μ1,μ2,…,μn}.

在鄰接鏈表N(v)上匹配星形T的過程包括:(1) 第2行匹配星形的根節(jié)點(diǎn)T.r和RDF圖中的頂點(diǎn)v;(2) 第3行到第7行獲得星形T的每個葉子節(jié)點(diǎn)li可以匹配的RDF圖中頂點(diǎn)的候選集合S(li);(3) 第8行在星形T所有葉子節(jié)點(diǎn)的候選集合S(li)上做笛卡爾積操作,得到星形T在鄰接鏈表N(v)上的匹配結(jié)果Ωv(T);(4) 第9行返回星形T在鄰接鏈表N(v)上的匹配結(jié)果Ωv(T).因此,星形T在RDF圖G中的匹配結(jié)果Ω(T)為Ωv(T)的并集,其中,v∈V.

例 1:根據(jù)算法 1,星形T1在 RDF示例圖G上有 6個匹配結(jié)果,包括{?w1→DekkerT,?x→KoontzD},{?w1→KingS,?x→GoldingW},{?w1→GibsonW,?x→SpeculativeFiction},{?w1→GibsonW,?x→BorgesJL},{?w1→GoldingW,?x→VerneJ}和{?w1→DekkerT,?x→KingS}.星形T2在 RDF示例圖G上有 4個匹配結(jié)果,包括{?x→KingS,?y→TheShining,?g→GothicFiction,?w2→GoldingW,?c→Portland,?a→NationalBookA},{?x→KingS,?y→TheStand,?g→GothicFiction,?w2→GoldingW,?c→Portland,?a→NationalBookA}等,T3有{?y→House,?p→ThomasNelson,?g→HorrorFiction},{?y→TheShining,?p→Doubleday,?g→GothicFiction},{?y→LordoftheFiles,?p→FaberandFaber,?g→Allegory}這3個匹配結(jié)果.

考慮匹配順序T1T3T2,因為星形T1和T3沒有共享的頂點(diǎn),所以對星形T1和T3的匹配結(jié)果進(jìn)行連接操作時生成 6×3=18個中間結(jié)果;另一匹配順序T2T3T1只生成 1個中間結(jié)果{?x→KingS,?y→TheShining,?g→GothicFiction,?w2→GoldingW,?c→Portland,?a→NationalBookA,?p→Doubleday,?g→GothicFiction}.基于星形分解進(jìn)行SPARQL BGP查詢匹配時,不同的星形匹配順序產(chǎn)生的中間結(jié)果有明顯差異.

對RDF圖G上的查詢Q,用Pred(u)表示頂點(diǎn)u的屬性(也就是謂語)集合,Pred(u)={pi|(u,pi,ui)∈Q}.函數(shù)freq:Σ→?返回謂語p在RDF圖G中的頻率,其中freq(p)=|{(si,p,oi)|(si,p,oi)∈G}|,?表示自然數(shù)的集合.本文的啟發(fā)式信息h-值由兩個因子決定:(1) 在查詢圖中頂點(diǎn)的出度越大,該頂點(diǎn)的鄰居節(jié)點(diǎn)中變量個數(shù)可能越多,那么以該頂點(diǎn)為根的星形被匹配時會綁定更多的變量;(2) 查詢圖中,頂點(diǎn)的出邊標(biāo)簽在RDF數(shù)據(jù)圖中越稀有,該頂點(diǎn)的選擇度越高,也就是當(dāng)匹配以該點(diǎn)為根節(jié)點(diǎn)的星形時會產(chǎn)生相對少的匹配結(jié)果.如果頂點(diǎn)u的所有屬性都是變量,則h(u)=0;否則,查詢圖中頂點(diǎn)u的h-值的具體定義如下:

由例 1可知,對相同的星形分解結(jié)果,不同的星形匹配順序在查詢執(zhí)行過程中產(chǎn)生的中間結(jié)果數(shù)目明顯不同,基于此查詢性能有非常顯著的差異.因此,本文以基于 RDF圖的結(jié)構(gòu)信息和豐富語義的h-值作為啟發(fā)信息,通過貪心策略對 BGP查詢圖進(jìn)行分解,并得到中間結(jié)果較少的星形匹配順序.該分解策略的算法偽代碼見算法2.

算法2.星形分解算法.

輸入:SPARQL BGP查詢Q:{tp1,…,tpn};

輸出:星形分解隊列D:{T1,…,Tm}.

算法2根據(jù)h-值將RDF查詢圖分解為星形的集合并給出匹配順序,具體過程如下:第3行、第4行將Qc中h-值最大的常量頂點(diǎn)作為第1個星形的根節(jié)點(diǎn),這樣只在與該查詢圖中常量頂點(diǎn)匹配的數(shù)據(jù)頂點(diǎn)的鄰接鏈表上進(jìn)行匹配,可以很大程度減少中間結(jié)果.如果查詢圖中的主語都是變量,第5行、第6行將Sub(Q)中h-值最大的頂點(diǎn)作為第1個星形的根節(jié)點(diǎn).然后,第7行調(diào)用genStar(r,Q,D)函數(shù)生成以r為根節(jié)點(diǎn)的星形T,并加入星形分解隊列D中(第14行、第15行),第16行刪除查詢Q中已加入到D中的三元組模式.第8行～第11行迭代生成新的星形,直至Q中的三元組模式(也就是查詢圖中的邊)被分解完,其中,第9行得到新生成星形根節(jié)點(diǎn)的候選頂點(diǎn)的集合Mv,這些候選的根節(jié)點(diǎn)與已經(jīng)生成的星形分解隊列D中至少分享一個相同的頂點(diǎn).第10行、第11行在候選集中選擇h-值最大的頂點(diǎn)作為根節(jié)點(diǎn)并生成新的星形.

例 2:考慮上文提及的示例查詢Q1,h(?w1)=1/6,h(?x)=5/2,h(?y)=2/3.根據(jù)算法 2,第 1個選擇的根節(jié)點(diǎn)是頂點(diǎn)?x,生成星形T1′,也就是圖2 中的星形T2.然后,根據(jù)h-值按序生成星形T2′,T3′,即圖2 中的星形T3,T1.

3.3 基于MapReduce的SPARQL BGP匹配算法

上節(jié)算法2將給定的BGP查詢圖分解為星形的集合,同時給定這些星形的匹配順序,該匹配順序利用啟發(fā)式信息h-值生成,使得以此順序匹配這些星形時可以產(chǎn)生較少的中間結(jié)果,提高查詢性能.本節(jié)將詳細(xì)介紹如何按算法2產(chǎn)生的星形匹配順序在左深連接(left-deep join)框架下基于MapReduce模型回答SPARQL BGP查詢.

定義7(局部查詢圖).給定 BGP查詢圖GQ,算法 2生成星形分解D并給出星形的匹配順序T1…Tm,滿足.局部查詢圖Pj,1≤j≤m是查詢圖GQ的子圖,滿足:(1);(2).

由定義7可知,P1=T1,Pm=GQ.用Ω(Ti)和Ω(Pi)分別表示星形Ti和局部查詢圖Pi的匹配結(jié)果.將局部查詢圖Pt-1與星形Tt頂點(diǎn)交集的匹配結(jié)果作為連接的鍵μkey:V(Pt-1)∩V(Tt)→V,連接Ω(Pt-1)與Ω(Tt)可得到Ω(Pt).每次MapReduce迭代操作新匹配一個星形,并且從第 2次迭代開始,將已經(jīng)匹配的局部查詢圖的結(jié)果與新匹配的星形結(jié)果進(jìn)行連接操作.圖4為處理SPARQL BGP查詢方法的MapReduce總體框架圖.并行SPARQL BGP查詢匹配算法SDec通過多次MapReduce迭代計算得到查詢結(jié)果,具體算法偽代碼見算法3.

算法3.SDec算法.

輸入:RDF圖G=(V,E,Σ),星形分解隊列D:{T1,…,Tm};

輸出:答案集:Ω(Q).

Fig.4 MapReduce framework of our SPARQL BGP matching algorithm圖4 SPARQL BGP匹配算法的MapReduce框架圖

算法3第2行～第7行通過MapReduce操作,按算法2給定的順序匹配星形,每輪MapReduce迭代連接局部子圖和星形的匹配結(jié)果,直到所有星形被匹配.Map函數(shù)由兩部分組成:(1) Map函數(shù)輸入值為N(v)時,算法3在RDF圖的鄰居信息N(v)上并行匹配星形Tt,并且將匹配結(jié)果μ以(μkey,μ)對輸出(第11行～第19行);(2) 輸入值為Ω(Pt-1)中的匹配結(jié)果μ時,輸出(μkey,μ)對(第 20行～第 22行).第 23行～第 25行,Reduce函數(shù)以映射μkey為鍵,連接局部查詢圖Pt-1和星形Tt的匹配結(jié)果,生成Pt的匹配結(jié)果.

定理1.給定RDF圖G和查詢圖GQ,假定算法2分解GQ為星形隊列D={T1,…,Tm}.算法3給出正確查詢結(jié)果并且MapReduce迭代次數(shù)為m.

證明:算法3在第1輪MapReduce迭代的Map函數(shù)中調(diào)用算法 1匹配星形T1,得到答案集Ωv(T1),也就是Ω(P1);從第2輪開始,算法3按照算法2給定的匹配順序,在每輪MapReduce迭代的Map函數(shù)中匹配一個新的星形Tt并得到查詢結(jié)果Ω(Tt),在Reduce函數(shù)中,將上輪得到的局部查詢圖Pt-1的匹配結(jié)果Ω(Pt-1)與星形Tt匹配結(jié)果Ω(Tt)進(jìn)行連接得到Ω(Pt),從而在第m輪MapReduce中得到Ω(Pm),也就是查詢Q的答案集.證畢. □

定理2.算法3的時間復(fù)雜度為,其中,m為星形個數(shù),|V|為 RDF圖的頂點(diǎn)大小,|Nmax|和|Lmax|分別是RDF圖G和查詢圖GQ中最大的出度.

證明:算法3在第m輪MapReduce迭代計算后得到查詢Q的答案集,其時間復(fù)雜度由兩部分組成:(1) 星形匹配的時間復(fù)雜度為;(2) 連接操作的時間復(fù)雜度為.最壞情況下,星形Tt的每個葉子可以匹配頂點(diǎn)v∈V的所有鄰居頂點(diǎn),也就是.因此,算法 3 的時間復(fù)雜度為.證畢.□

4 優(yōu)化技術(shù)

本節(jié)提出兩個優(yōu)化技術(shù),提高基本算法的查詢效率.雖然不能降低算法的復(fù)雜度,但是經(jīng)過實驗驗證,可以明顯提高查詢效率.其中,一個技術(shù)通過布隆過濾器編碼頂點(diǎn)的鄰居信息減少數(shù)據(jù)輸入,另一技術(shù)通過推遲笛卡爾積提高查詢性能.

4.1 基于布隆過濾器的鄰居信息編碼

布隆過濾器(Bloom filter)利用位數(shù)組簡潔地表示一個集合,并且可以快速檢索一個元素是否在這個集合中,是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu).布隆過濾器有可能會出現(xiàn)錯誤判斷,但不會漏掉判斷.它的核心思想是,利用多個不同的哈希函數(shù)來解決沖突.

布隆過濾器BF初始時是一個包含m位的位數(shù)組,每一位都置為0,即,BF整個數(shù)組的元素都設(shè)置為0.隨后,每添加一個元素x,BF使用k個相互獨(dú)立的哈希函數(shù),分別將集合中的每個元素映射到{1,…,m}的范圍中,將數(shù)組中對應(yīng)的比特位置為1.最后,判斷y是否屬于BF時,只需要對y使用k個哈希函數(shù)得到k個哈希值:如果所有hashi(y)的位置都是1(1≤i≤k),即k個位置都被設(shè)置為1了,那么y是集合中的元素;否則,就認(rèn)為y不是集合中的元素.

在布隆過濾器中,根據(jù)輸入元素個數(shù)n和BF數(shù)組位數(shù)m,可得到使誤判(flase positive)率f最小的哈希函數(shù)的個數(shù)k:k=ln2m/n.此外,哈希函數(shù)個數(shù)k與誤判率f滿足等式k=-log2f.由該等式可知:k越大,誤判率f小.本文借鑒布隆過濾器中的參數(shù)設(shè)置對RDF圖中主語的鄰居邊及頂點(diǎn)進(jìn)行編碼時,但是不再判斷一個元素是否在BF集合中,而是判斷一個布隆過濾器集合是否是另一個布隆過濾器集合的子集.形式化定義為:如果BF1&&BF2=BF1,那么布隆過濾器BF1是BF2的子集;否則,就認(rèn)為不是.即:判斷布隆過濾器BF1是否是布隆過濾器BF2的子集時,如果所有BF1為1的位置,BF2對應(yīng)的位置都被設(shè)置為1了,那么布隆過濾器BF1是BF2的子集;否則就認(rèn)為不是.

對 RDF數(shù)據(jù)圖中的每個主語s的鄰居信息基于布隆過濾器進(jìn)行編碼,并將此編碼作為它的簽名,表示為Sig(s).把主語s的每條出邊e=(s,o)∈V×V用k個哈希函數(shù)映射成長度為M+N的位數(shù)組ecd(e).前M位表示邊標(biāo)簽的編碼,用k個哈希函數(shù)hi(i=1,…,k)將M位中的k位置為“1”.本文選取經(jīng)典的字符串哈希函數(shù),如BKDRHash,APHash,DJBHash等.對第i個哈希函數(shù)hi,設(shè)置前M位中的第hi(lab(e)) modM位為“1”,其中,hi(lab(e))表示邊標(biāo)簽lab(e)的哈希值.后N位表示頂點(diǎn)的編碼,其方式與上述類似,將后N位中的k位采用不同的哈希函數(shù)置為“1”.將主語s所有出邊的位數(shù)組ecd(e)按位或操作后得到它的簽名Sig(s)=ecd(e1)|…|ecd(et),其中,ei為主語s的出邊.

如圖5所示,對RDF圖G的頂點(diǎn)GoldingW及圖3中的星形T3進(jìn)行鄰居信息編碼.首先對頂點(diǎn)GoldingW的出邊(GoldingW,LordoftheFlies)進(jìn)行編碼,將邊標(biāo)簽notableWork映射成長度為8的位數(shù)組,具體操作如下:首先求哈希值A(chǔ)PHash(notableWork)和DJBHash(notableWork),并對這兩個哈希值mod 8得到余數(shù)2和7;然后將位數(shù)組從左到右的第 2位和第 7位置為 1(從第 0位開始),其余位置為 0,如圖5所示;類似地,將相鄰頂點(diǎn)LordoftheFlies映射到長度為12的位數(shù)組,取APHash和DJBHash函數(shù)的值并mod 12得到余數(shù)進(jìn)行編碼,將邊標(biāo)簽的位數(shù)組和頂點(diǎn)的位數(shù)組連接得到邊(GoldingW,LordoftheFlies)的編碼ecd((GoldingW,LordoftheFlies));最后,將不同出邊的編碼按位或操作得到GoldingW頂點(diǎn)的簽名Sig(GoldingW).值得注意的是:沒有出邊的頂點(diǎn),其簽名的所有位默認(rèn)為0.同樣地,對星形T3進(jìn)行鄰居信息編碼,邊標(biāo)簽literaryGenre的兩個哈希值mod 8得到余數(shù)3和5后編碼位數(shù)組,如圖5所示.因星形中的頂點(diǎn)?g為變量,所以它的位數(shù)組12位都置為0,將這兩個位數(shù)組連接后得到編碼ecd((literaryGenre,?g)),計算其他邊的編碼進(jìn)行或操作后,得到星形T3的鄰居信息編碼Sig(T3).

Fig.5 Procedure of the signature generation of vertex labeledGoldingWand starT3圖5 主語GoldingW和星形T3簽名的生成過程

本文第3節(jié)將SPARQL BGP查詢圖分解為星形結(jié)構(gòu)的集合,對星形T采用相同的方式進(jìn)行編碼,每個星形結(jié)構(gòu)也生成一個長度固定的位數(shù)組做為簽名,表示為Sig(T).當(dāng)星形T中的邊或頂點(diǎn)為變量時,它的所有編碼位都置為0.

剪枝規(guī)則.星形T在鄰居信息N(v)上匹配時:如果Sig(T)&Sig(v)≠Sig(T),在N(v)上匹配星形T的過程被剪掉.

在每輪MapReduce操作中,Map函數(shù)在每個頂點(diǎn)的鄰接鏈表上并行匹配一個新的星形T.如果在頂點(diǎn)v的鄰接鏈表上匹配星形T時滿足剪枝規(guī)則,也就是星形T的鄰居邊標(biāo)簽集合不是頂點(diǎn)v鄰居邊標(biāo)簽的子集,或者星形的葉子節(jié)點(diǎn)的集合不是頂點(diǎn)v鄰居頂點(diǎn)的子集,那么星形T在頂點(diǎn)v的鄰接鏈表上必然沒有匹配結(jié)果,因此不再進(jìn)行算法1的星形匹配.本文通過上述剪枝規(guī)則減少M(fèi)apReduce迭代過程中無用的數(shù)據(jù)輸入,同時減少大量沒必要的星形匹配過程中涉及的計算,以此優(yōu)化BGP查詢.

例3:如圖5所示,當(dāng)在鄰接鏈表N(GoldingW)上匹配星形T3時,因為Sig(T3)&Sig(GoldingW)≠Sig(T3)所以在鄰接鏈表N(GoldingW)上的星形T3的匹配過程被減掉,從而可以減少中間結(jié)果.

4.2 推遲笛卡爾積操作

在本文的基本算法中,初始星形匹配階段在匹配星形T=(r,L),其中,L={(p1,l1),…,(pt,lt)},v∈V時,首先根據(jù)葉子節(jié)點(diǎn)的標(biāo)簽在各個主語v的鄰接鏈表N(v)上得到各個葉子節(jié)點(diǎn)li的候選集合S(li),然后通過葉子節(jié)點(diǎn)候選集合的笛卡爾積{v}×S(l1)×…×S(lt),得到星形T的所有匹配結(jié)果.但是大部分星形匹配結(jié)果無法形成最終的查詢答案,從而導(dǎo)致在星形匹配階段做了很多無用的笛卡爾積操作,在Reduce階段連接代價過高.

本文的優(yōu)化算法在星形匹配階段僅僅得到各葉子節(jié)點(diǎn)的候選集合即可.在Map函數(shù)中計算局部查詢圖Pt-1和星形Tt的頂點(diǎn)交集V(Pt-1)∩V(Tt)中的各個頂點(diǎn)的候選集,并通過這些頂點(diǎn)候選集的笛卡爾積得到Reduce函數(shù)連接的鍵.MapReduce操作結(jié)束后,通過剩余頂點(diǎn)候選集的笛卡爾積得到最終的查詢結(jié)果.將各個星形匹配過程中葉子節(jié)點(diǎn)候選集的笛卡爾積推遲到MapReduce操作結(jié)束的時候,做過濾部分無用的計算.

例4:匹配查詢圖Q1時,在前3輪的Map函數(shù)中,僅需要得到每個星形葉子節(jié)點(diǎn)的候選集.如圖6所示,第2輪 MapReduce中,通過V(P1)∩V(T3)={?y,?g}中頂點(diǎn)的候選集合的笛卡爾積,得到星形T3中{?y,?g}的匹配結(jié)果{?y→House,?g→HorrorFiction},{?y→TheStand,?g→GothicFiction} 和 {?y→LordoftheFlies,?g→Allegory};P1中{?y,?g}的匹配結(jié)果{?y→TheStand,?g→GothicFiction}和{?y→TheShining,?g→GothicFiction}.將這些匹配結(jié)果作為鍵,在 Reduce過程中進(jìn)行連接操作,可以觀察到,僅當(dāng){?y→TheStand,?g→GothicFiction}可以得到局部查詢圖P2的匹配結(jié)果.類似地,在第 3輪 MapReduce中,通過V(P2)∩V(T1)={?x}中頂點(diǎn)候選集合的笛卡爾積,得到星形T1和局部查詢圖P2中{?x}的匹配結(jié)果集合,以這些匹配結(jié)果作為鍵值,在Reduce中進(jìn)行連接操作.最后,通過剩余頂點(diǎn)集合{?a,?c,?w2,?p,?w1}中各頂點(diǎn)的候選集的笛卡爾積,得到查詢Q1的最終匹配結(jié)果{?y→TheShining,?g→GothicFiction,?x→KingS,?a→NationalBookA,?c→Portland,?w2→GoldingW,?p→Doubleday,?w2→DekkerT}.在基本算法SDec中,Map函數(shù)在鄰接鏈表N(GibsonW)上匹配星形T2時需要各個葉子節(jié)點(diǎn)的候選集的笛卡爾積S(?a)×S(?c)×S(?w2)×S(?g)×S(?y),然而查詢圖中頂點(diǎn)?x匹配 RDF數(shù)據(jù)圖中頂點(diǎn)GibsonW并不能形成最終答案,因此,基本算法做了無用的笛卡爾積,代價較高.相反,優(yōu)化算法通過推遲笛卡爾積提前過濾掉在鄰接鏈表N(GibsonW)上的笛卡爾積操作.

Fig.6 Matching process of the example SPARQL BGP query graphQ1圖6 SPARQL BGP示例查詢圖Q1查詢匹配過程

5 實 驗

本節(jié)在合成數(shù)據(jù)集和真實數(shù)據(jù)集上驗證算法的有效性和可擴(kuò)展性,并且與SHARD,S2X和SDec的優(yōu)化版本的算法比較.不與S2RDF和TriAD方法作比較的原因如下.

(1) S2RDF使用ExtVP索引提高查詢效率,但是預(yù)處理時間代價過高,嚴(yán)重限制了該系統(tǒng)對大規(guī)模數(shù)據(jù)集的適用性,最新的文獻(xiàn)[22]中通過實驗也驗證了這一點(diǎn).例如:在相同的實驗環(huán)境下,S2RDF預(yù)處理DBpedia數(shù)據(jù)集的時間超過2.5個小時,遠(yuǎn)大于本文SDec系統(tǒng)的查詢執(zhí)行時間;

(2) 如文獻(xiàn)[22]所述,TriAD假設(shè)數(shù)據(jù)必須裝載到集群的內(nèi)存中,如果數(shù)據(jù)量超過了集群內(nèi)存大小,TriAD將不再適用.而本文沒有這個限制條件,而且TriAD借助了大量的索引加快查詢.

因此,與這兩種方法進(jìn)行比較實驗是不公平的.

本文的SDec算法與圖劃分策略和分布式集群環(huán)境上的存儲策略是獨(dú)立無關(guān)的.實際上,本文使用分布式文件系統(tǒng)HDFS(Hadoop distributed file system)的默認(rèn)劃分策略.

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

本文實驗平臺使用的分布式集群包括 8個相同的計算節(jié)點(diǎn),每個節(jié)點(diǎn)使用主頻為 3.60GHz的 Intel(R)Core(TM) i7-7700四核處理器,其內(nèi)存大小為16GB,硬盤大小為500GB.節(jié)點(diǎn)間通信使用1000Mbps以太網(wǎng).實驗平臺所用集群的所有節(jié)點(diǎn)均使用Linux 64-bit CentOS操作系統(tǒng),其使用的Hadoop版本號為2.7.4,Spark版本號為2.2.0.本文原型系統(tǒng)的所有代碼均用Scala語言實現(xiàn).

本實驗使用的數(shù)據(jù)包括WatDiv標(biāo)準(zhǔn)合成數(shù)據(jù)集以及DBpedia真實數(shù)據(jù)集,這兩個數(shù)據(jù)集都是RDF數(shù)據(jù)集.WatDiv是一個標(biāo)準(zhǔn)的RDF合成數(shù)據(jù)集,允許用戶定義自己的數(shù)據(jù)集并生成不同大小的數(shù)據(jù)集,本文使用了3個不同規(guī)模的WatDiv數(shù)據(jù)集(也就是WatDiv1M,WatDiv10M和WatDiv100M)進(jìn)行實驗測試和比較;DBpedia數(shù)據(jù)集是從維基百科中提取的一個真實數(shù)據(jù)集.本次實驗中,所有數(shù)據(jù)集均為N-Triple格式,具體統(tǒng)計信息見表2.本文根據(jù)RDF查詢圖的形狀將它們分為4類,包括線性查詢(linear queries,簡稱L)、星形查詢(star queries,簡稱S)、雪花形查詢(snowflake queries,簡稱F)和復(fù)雜查詢(complex queries,簡稱C),見表3.本文使用WatDiv數(shù)據(jù)集給定的20個基本查詢模板進(jìn)行實驗測試.因為缺乏DBpedia數(shù)據(jù)集上的查詢模板,本文設(shè)計8個查詢覆蓋上文提及的4個查詢種類.

Table 2 Datasets表2 數(shù)據(jù)集

Table 3 Queries表3 查詢

5.2 實驗結(jié)果

本節(jié)分4組實驗進(jìn)行詳細(xì)介紹,包括改變優(yōu)化算法中哈希函數(shù)個數(shù)k、改變數(shù)據(jù)集規(guī)模及改變集群中節(jié)點(diǎn)個數(shù)來驗證優(yōu)化算法SDecopt、基本算法Sdec,SHARD和S2X這4種方法的效率和可伸縮性.以下實驗結(jié)果中,每個查詢測試3次取平均值,避免隨機(jī)誤差.

(1) 改變編碼優(yōu)化技術(shù)中參數(shù)k測試查詢性能.

本組實驗分別設(shè)置哈希函數(shù)個數(shù)k=1,2,3,在WatDiv100M數(shù)據(jù)集上測試20個模板查詢.隨著k從1增加到3,誤判率f減小,可以在星形匹配階段過濾更多的無用數(shù)據(jù)輸入,加快數(shù)據(jù)查詢;同時,隨著RDF數(shù)據(jù)圖中主語簽名的位數(shù)組長度變長,占用內(nèi)存空間越多,影響查詢效率.

如圖7所示,當(dāng)k=3時,編碼鄰居信息增加查詢運(yùn)行時內(nèi)存帶來的影響占主要因素,導(dǎo)致查詢時間增加;k=2時,在絕大部分查詢上可以取得最好的查詢性能.隨著哈希函數(shù)個數(shù)從1到3,鄰居信息BF編碼的運(yùn)行時內(nèi)存變化.本文以下的所有實驗中,優(yōu)化方法中的哈希函數(shù)個數(shù)k取值為2.

(2) SPARQL BGP查詢性能測試.

本組實驗分別在合成數(shù)據(jù)集WatDiv100M和真實數(shù)據(jù)集DBpedia上驗證集群節(jié)點(diǎn)個數(shù)為8時本文所提方法的查詢效率.如圖8所示,在合成數(shù)據(jù)集 WatDiv上,SDecopt在 20個模板查詢上都可以獲得最高的查詢效率;同時,SDec也優(yōu)于SHARD和S2X.在本文中,運(yùn)行時間超過1×104s用INF表示.如圖8所示:對查詢F3和C2,S2X不能在該時間限制內(nèi)結(jié)束,而本文的優(yōu)化算法僅需要19.24s和36.92s就可以得到查詢結(jié)果.對剩余的18個查詢,本文優(yōu)化算法的查詢時間與S2X相比提高了7倍～40倍,平均查詢時間提高17倍.究其原因:S2X將BGP中所有三元組模式的匹配結(jié)果進(jìn)行連接操作會產(chǎn)生大量的中間結(jié)果,代價較高;而本文的最小匹配結(jié)構(gòu)為星形,同時考慮 RDF圖的豐富語義和結(jié)構(gòu)信息,減少了大量無用的中間結(jié)果.與 SHARD相比,SDecopt的查詢時間提高了16倍～99倍,平均查詢時間提高40倍.SHARD采用三元組存儲也將BGP查詢分解為三元組模式進(jìn)行匹配,在包含3列的數(shù)據(jù)表上進(jìn)行連接操作,連接代價高.因此,SDecopt算法的查詢時間比S2X和SHARD平均提高了一個數(shù)量級.

Fig.7 Experiments of changing the number of hash functionsk and the run memory圖7 改變哈希函數(shù)個數(shù)k的實驗結(jié)果及運(yùn)行時內(nèi)存變化

Fig.8 Query efficiency of different SPARQL processors over synthetic dataset圖8 不同SPARQL處理器在合成數(shù)據(jù)集上的查詢效率

此外,與基本算法SDec相比,優(yōu)化算法時間減少了60.68%～87.00%,即,SDecopt可以更有效地評估BGP查詢.該實驗結(jié)果說明,本文的優(yōu)化技術(shù)效果非常顯著.原因包含以下兩點(diǎn):(1) 優(yōu)化算法對鄰居信息進(jìn)行 BF編碼,在星形匹配階段,如果星形結(jié)構(gòu)的簽名與RDF圖中主語s的簽名不匹配,直接將N(s)上的星形匹配剪掉,以此過濾掉大量的無用計算;(2) 基本算法在星形匹配階段進(jìn)行了大量的無用笛卡爾積,而優(yōu)化算法通過推遲笛卡爾積操作減少很多無用的笛卡爾積操作,提高了查詢性能.

如圖9所示,在真實數(shù)據(jù)集DBpedia上,SDecopt在所有查詢上的效率也是最高的.回答查詢C2時S2X報錯,導(dǎo)致時間缺失.這說明S2X無法有效回答涉及大量中間結(jié)果的復(fù)雜查詢.對于剩余的7個查詢,優(yōu)化算法SDecopt查詢時間比S2X快7倍～497倍,平均查詢時間比S2X快120倍;同時,與SHARD相比,優(yōu)化算法SDecopt查詢時間快7倍～26倍,平均查詢時間快15倍.即:在真實數(shù)據(jù)集上,本文算法的平均時間也比SHARD和S2X快一個數(shù)量級.另外,由圖9觀察到:優(yōu)化算法的查詢時間明顯提高,比基本算法SDec查詢時間減少49.63%～78.71%.

(3) 改變數(shù)據(jù)集規(guī)模的查詢性能測試.

本組實驗通過改變WatDiv數(shù)據(jù)集規(guī)模從1M～100M在8個節(jié)點(diǎn)的集群上測試18個查詢.本文將這18個查詢分為4個查詢種類,分別計算SDec,SDecopt,S2X和SHARD的4類平均查詢時間.如圖10所示,隨著數(shù)據(jù)規(guī)模增大,所有SPARQL查詢處理器的查詢時間都增加,SHARD和S2X的查詢時間增加幅度遠(yuǎn)大于本文方法.觀察圖10可知:數(shù)據(jù)集規(guī)模從10M個三元組增加到100M個三元組,S2X和SHARD的查詢性能嚴(yán)重下降.如:對雪花形查詢,SHARD和S2X在WatDiv100M上需要將近1000s的時間才可以得到查詢結(jié)果,而本文的優(yōu)化算法僅需10s左右.

Fig.9 Query efficiency of different SPARQL processors over real-world dataset圖9 不同SPARQL查詢處理器在真實數(shù)據(jù)集上的查詢效率

Fig.10 Experiment results of changing the size of datasets圖10 改變數(shù)據(jù)集規(guī)模的實驗結(jié)果

(4) 算法可伸縮性測試.

本組實驗在 WatDiv100M和 DBpedia數(shù)據(jù)集上進(jìn)行,改變集群節(jié)點(diǎn)個數(shù),從 4～8.從每類查詢中隨機(jī)選取 1個查詢,也就是L4,S4,F2,C3.如圖11所示:隨著集群節(jié)點(diǎn)個數(shù)的增加,在合成數(shù)據(jù)集WatDiv上,這4個SPARQL查詢處理器的查詢時間減少.原因是隨著集群節(jié)點(diǎn)個數(shù)的增加,CPU核數(shù)增加,查詢過程中計算的并行度增加,查詢所需的總時間減少.由圖11可以看出,SDecopt的查詢性能始終是最高的.

Fig.11 Experiment results of changing the number of sites on synthetic dataset WatDiv100M圖11 改變集群節(jié)點(diǎn)個數(shù)在合成數(shù)據(jù)集WatDiv100M上的實驗結(jié)果

在真實數(shù)據(jù)集DBpedia上,改變集群節(jié)點(diǎn)的個數(shù)驗證算法的可伸縮性.本次實驗選取L1,S1,F1,C1查詢,即,從每類查詢中隨機(jī)選取1個查詢進(jìn)行實驗.如圖12所示:隨著集群節(jié)點(diǎn)個數(shù)從4增加到8,上述4個SPARQL查詢處理方法的查詢時間逐漸減少.

Fig.12 Experiment results of changing the number of sites on real-world dataset DBpedia圖12 改變集群節(jié)點(diǎn)個數(shù)在真實數(shù)據(jù)集DBpedia上的實驗結(jié)果

6 總 結(jié)

本文提出了基于MapReduce框架的查詢處理器SDec,有效回答大規(guī)模RDF智能圖數(shù)據(jù)上的SPARQL BGP查詢.本文的SDec算法利用RDF圖內(nèi)嵌的豐富語義和RDF圖結(jié)構(gòu)分解查詢圖為星形集合,并確定這些星形的匹配順序,以此減少星形匹配過程中的中間結(jié)果.此外,為了進(jìn)一步提高查詢算法的效率,本文設(shè)計了兩個優(yōu)化技術(shù),包括對鄰居信息編碼過濾無用的數(shù)據(jù)輸入和推遲笛卡爾積操作改進(jìn)基本算法的性能.合成數(shù)據(jù)集和真實數(shù)據(jù)集上的大量實驗驗證了本文所提算法的有效性、高效性和伸縮性,并且實驗結(jié)果顯示,本文的算法優(yōu)于SHARD和S2X.