李國鼎,馮志勇,b,饒國政,b,王 鑫,b

(天津大學(xué)a.計算機(jī)科學(xué)與技術(shù)學(xué)院;b.天津市認(rèn)知計算與應(yīng)用重點實驗室,天津300072)

基于BSP的SPARQL基本圖模式查詢算法

李國鼎a,馮志勇a,b,饒國政a,b,王 鑫a,b

(天津大學(xué)a.計算機(jī)科學(xué)與技術(shù)學(xué)院;b.天津市認(rèn)知計算與應(yīng)用重點實驗室,天津300072)

隨著語義網(wǎng)的不斷發(fā)展,發(fā)布在互聯(lián)網(wǎng)上的資源描述框架(RDF)數(shù)據(jù)達(dá)到百億級三元組規(guī)模,并且呈現(xiàn)幾何增長趨勢,針對RDF數(shù)據(jù)的單機(jī)SPARQL查詢方法已經(jīng)不再適用。為此,提出一種基于整體同步并行(BSP)模型的SPARQL基本圖模式查詢算法。根據(jù)RDF有向圖數(shù)據(jù)特性及基本圖模式定義,將整個查詢過程分成匹配和迭代2個階段,在匹配出所需查詢的三元組模式后,通過迭代使部分解逐步逼近完全解,得到最終查詢結(jié)果。利用HAMA分布式計算框架進(jìn)行算法實現(xiàn),實驗結(jié)果表明,與基于MapReduce的SPARQL查詢算法相比,該算法具有較高的查詢效率,能為大規(guī)模RDF數(shù)據(jù)的快速SPARQL查詢提供支持。

語義網(wǎng);資源描述框架;SPARQL查詢;基本圖模式;整體同步并行模型;HAMA框架

1 概述

資源描述框架(Resource Description Framework,RDF)是語義網(wǎng)中表示和交換機(jī)器可理解信息的標(biāo)準(zhǔn)數(shù)據(jù)模型[1-3]。RDF數(shù)據(jù)是一類典型的圖數(shù)據(jù),主語和賓語分別形成圖中的點,謂語是圖中的邊[4]。SPARQL作為一項W3C推薦標(biāo)準(zhǔn),可以用來對 RDF數(shù)據(jù)集進(jìn)行查詢[5]。SPARQL(Simple Protocol and RDF Query Language)查詢的核心是基本圖模式(Basic Graph Pattern,BGP)[6-8]?；緢D模式是圖模式匹配問題的一個子集,而圖模式匹配問題實際上是最大團(tuán)問題的子問題,其復(fù)雜度是N-P的[9]。同時,在關(guān)聯(lián)數(shù)據(jù)運動的推動下,RDF數(shù)據(jù)規(guī)模以爆炸式的速度快速增長,由TB級向PB級甚至EB級遞進(jìn),并已經(jīng)達(dá)到了大數(shù)據(jù)的規(guī)模[6]。在RDF圖數(shù)據(jù)增長為大數(shù)據(jù)的情況下,單機(jī)性能的增長已經(jīng)不能滿足RDF數(shù)據(jù)的增長,在單機(jī)上處理RDF大數(shù)據(jù)有明顯瓶頸,甚至已經(jīng)變得不可能。

為解決單機(jī)性能不足的問題,文獻(xiàn)[10-12]提出基于MapReduce分布式計算模型實現(xiàn)的SPARQL基本圖模式算法,這些算法一般分為2個階段:選擇階段和連接階段。在選擇階段,針對每個RDF三元組依次用所有SPARQL三元組模式進(jìn)行匹配,過濾出滿足條件的三元組,并加以標(biāo)識。在連接階段,通過一定的選擇策略得到連接點序列,根據(jù)該序列將選擇階段得到的結(jié)果合并成新的三元組。合并過程中不斷迭代,最終得到完整的SPARQL查詢結(jié)果。

由此可見,現(xiàn)有的SPARQL基本圖模式算法存在以下問題:(1)由于單機(jī)性能的增長滿足不了RDF數(shù)據(jù)幾何級增長,用于單機(jī)的算法在大數(shù)據(jù)情況下不適用。(2)MapReduce方法不是原生的圖算法,而且大量事實表明,MapReduce只適合批處理。

針對以上問題,利用整體同步并行(Bulk Synchronous Parallel,BSP)模型適用于圖計算的特點,以及BSP模型的實現(xiàn)框架——HAMA的高效率,本文提出基于BSP的SPARQL基本圖模式查詢算法,并與基于MapReduce的算法進(jìn)行比較。

2 基本定義

為描述方便,給出RDF基本圖模式查詢以及相關(guān)定義[7-8]。

定義1 (RDF三元組)三元組由主語、謂語和賓語構(gòu)成,記為spo:

其中,I表示國際化資源標(biāo)識符(Internationalized Resource Identifiers,IRI);B為空節(jié)點;L為RDF文字。為描述方便,記:

定義2 (RDF圖)RDF圖是一系列的三元組集合,簡寫為RDF_G:

定義3 (三元組模式)三元組模式和三元組相似,但是允許變量的使用,三元組模式記為t:

其中,V是所有變量的集合。SPARQL查詢中最簡單的圖模式就是三元組模式。

定義4 (基本圖模式)基本圖模式(Basic Graph Pattern,BGP)由一系列的三元組模式組成:

定義5 (查詢映射)假設(shè)變量V到RDF_T的映射為μ:V→RDF_T,則針對BGP的查詢?yōu)?

其中,μ(BGP)表示在映射μ下BGP中替換了變量的三元組集合。μ(BGP)集中任意一個元素是BGP查詢的一個解,對μ(BGP)集合的求解是算法的最終目的。

3 基本圖模式查詢算法

3.1 BSP算法框架

BSP計算模型由哈佛大學(xué)Viliant教授于1990年提出[13-14]。宏觀上,BSP計算模型由一系列超步組成,這種結(jié)構(gòu)類似于串行程序結(jié)構(gòu),而具體到一個超步內(nèi)部,又分為3個部分:(1)本地計算階段:各個計算節(jié)點對本地數(shù)據(jù)進(jìn)行計算;(2)全局通信階段:計算節(jié)點對非本地數(shù)據(jù)進(jìn)行通信和處理;(3)同步階段:等待所有同步結(jié)束。

基于BSP的這些特性,Google在2010年提出了一個基于BSP模型的商業(yè)系統(tǒng)——Pregel系統(tǒng),把BSP模型運用在分布式計算中[15]。Google用Pregel來處理大型的圖數(shù)據(jù),把圖中一個點看成是BSP模型中一個計算節(jié)點。HAMA是BSP模型的一個開源實現(xiàn)[16]。HAMA計算框架可以用來進(jìn)行圖、矩陣、復(fù)雜網(wǎng)絡(luò)等大型科學(xué)計算,HAMA圖編程模型具體如下:

該模型描述了一個BSP超步的計算過程,以點為計算單元,主要包括3個部分:

(1)定義相關(guān)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),包括一個點中值的類型VertexType、邊的類型EdgeType、消息的類型MessageType。

(2)每個點的輸入都來自上一個超步的消息。

(3)在每個計算函數(shù)中定義2類操作:修改該點值的操作setValue()和發(fā)送消息操作sendMessageTo()。

3.2 HAMA圖編程模型實例化

MessageType與VertexType是HAMA編程模型中定義的抽象數(shù)據(jù)類型,針對RDF數(shù)據(jù)的特點,把VertexType實例化為Vertex變量,把MessageType實例化為Message變量。為了更清晰地描述這2種類型的數(shù)據(jù)結(jié)構(gòu),定義了相關(guān)中間變量。

定義6 中間量定義:

(1)Path表示當(dāng)前已經(jīng)匹配的SPARQL三元組模式,是BGP的一個部分解,滿足:

(2)Description表示變量V和RDF_T之間的對應(yīng)關(guān)系,Description由一系列變量和RDF_T對組成的集合,即:

(3)value集合表示一個RDF_T點當(dāng)前獲知的所有Path和相應(yīng)的Description:

定義7 BSP圖編程模型中MessageType的數(shù)據(jù)類型Message:

其中,BSP計算過程中消息的數(shù)據(jù)結(jié)構(gòu)則可以用Message表達(dá),一條消息包括了一條Path和Path相應(yīng)的Description。

定義8 BSP圖編程模型中VertexType的數(shù)據(jù)類型Vertex:

其中,在BSP模型中,RDF_G圖的RDF_T點中的值用Vertex表示,每個點除了有唯一的id之外,還有對應(yīng)的value。當(dāng)Path等于BGP時,整個SPARQL查詢完成,此時部分解等于完全解,整個運算過程停止。

3.3 RDF基本圖模式查詢算法

通過對整個基本圖模式計算過程的分解,根據(jù)計算任務(wù)的不同,定義2類超步:

(1)原子匹配超步:每個點匹配出該點滿足的SPARQL三元組模式。

(2)構(gòu)建SPARQL超步:每個點根據(jù)已知的信息和收到的消息,逐步構(gòu)建完整的SPARQL查詢。

原子匹配超步在整個基本圖模式計算過程中只迭代一次,這個過程稱為匹配。構(gòu)建SPARQL超步要迭代多次,這個過程稱為迭代。

3.3.1 RDF三元組模式匹配

BSP匹配過程可以看作是整個計算過程的初始化階段。這個過程含有一個原子匹配超步(算法1)。此過程可以描述為:每個點對其作為起點的所有邊匹配SPARQL查詢中的每一個三元組模式,如果匹配成功則更新Vertex值并發(fā)送相應(yīng)的Message。這一步目的是獲得初始的原子匹配信息,并把這些信息告訴下一個階段。

算法1 原子匹配超步

3.3.2 RDF基本圖模式查詢迭代

迭代過程的輸入是匹配過程的輸出。為了使匹配信息擴(kuò)散到每一個相關(guān)計算節(jié)點,包含多個構(gòu)建SPARQL超步(算法2)。由于Path是BGP的一個部分解,Path中含有部分的匹配信息。每一個超步都是Path不斷逼近BGP的過程,也是匹配信息不斷完善的過程。當(dāng)Path等于BGP時,則完整的基本圖模式查詢構(gòu)建完成。

算法2 構(gòu)建SPARQL超步

對照BSP模型,算法2中一個超步主要含有2個動作,對來自上一個超步Message的處理,以及向下一個超步發(fā)送Message。算法2提到的Message和Path比較Description信息是否沖突,主要是看變量V和RDF_T點之間的映射關(guān)系μ是否有不一致的情況。

在整個算法結(jié)束之后,HAMA計算框架輸出的是RDF_G的點集。此時,還需要把 Vertex值中Path=BGP的點過濾出來,根據(jù)Description信息,最后得到SPARQL查詢結(jié)果。

4 實驗結(jié)果與分析

為分析本文提出的BSP基本圖模式算法的時間復(fù)雜度,對SPARQL基本圖模式查詢進(jìn)行詳細(xì)實驗。實驗主要考察比較本文算法和MapReduce基本圖模式算法在運行時間上的差異。

4.1 實驗設(shè)計

本文實驗的軟硬件環(huán)境配置如下:三節(jié)點的集群服務(wù)器,所有節(jié)點的配置都相同。每個節(jié)點的操作系統(tǒng)均為64位Ubuntu 12.04,JDK采用64位1.6.25版本,HAMA采用6.0版本,Hadoop采用1.0.4版本。硬件配置,CPU均為Intel i3-2120 3.30 GHz,內(nèi)存為4 GB。

由于HAMA計算框架不同于Hadoop,要求一個Job的所有Task同時參加計算。由于實驗機(jī)器性能的限制,每一臺機(jī)器只能進(jìn)行3個HAMA Task, 3臺機(jī)器一共只能進(jìn)行9個HAMA Task。所測試的數(shù)據(jù)集為DBpediapage_link_en數(shù)據(jù)集的一個子集。

不失一般性,考察3個查詢。

4.2 實驗結(jié)果

圖1展示了基本圖模式算法在MapReduce和BSP下的處理時間。可以看出,針對直徑長的BGP查詢,本文提出的BSP算法相對MapReduce算法有優(yōu)勢。在Q1和Q2中,BSP算法比MapReduce算法查詢時間短,在Q3中,BSP算法與MapReduce算法性能接近。

圖1 算法查詢時間比較

4.3 實驗分析

本節(jié)主要對算法的時間復(fù)雜度進(jìn)行分析。

BSP計算一共有N個超步。ms,ghs和ls分別表示是一個超步中本地計算、通信、同步的時間。MapReduce模型的計算時間TMR為:

MapReduce計算一共迭代L步。mi,si和ri分別表示一次迭代中 Map,Shuffle-sort,Reduce的時間。

將本文提出的基于 BSP模型的算法與基于MapReduce模型的算法進(jìn)行對比,可以看出,2種算法的復(fù)雜度在一個級別。但是2種算法的并行度不一樣,而并行度可以通過迭代次數(shù)反映出來,迭代次數(shù)越少并行度越高,反之也成立。

在BSP方式中,由于SPARQL查詢可以通過信息傳遞,因此每個節(jié)點中記錄的SPARQL三元組模式的增長是擴(kuò)散性的,整個計算過程的迭代次數(shù)是lb(D)。其中,D是SPARQL模式圖中點的直徑。MapReduce根據(jù)選擇連接點策略的不同,會有不同的迭代次數(shù)。本文選用目前普遍使用的貪婪選擇策略做比較,貪婪選擇策略即每次選取出現(xiàn)次數(shù)最多的變量作為連接點,在這種選擇策略下迭代次數(shù)小于等于N。

根據(jù)不同的模式圖可以得到不同的比較結(jié)果。例如,在圖 2(a)中,BSP需要迭代 lb(N)次, MapReduce需要迭代N次。而在圖2(b)中BSP和MapReduce都只需迭代有限常數(shù)次,BSP迭代3次, MapReduce迭代2次?？梢钥闯?BSP迭代次數(shù)的最壞情況和 MapReduce迭代次數(shù)最好情況基本一致。

同時,本文提出的BSP算法也有不足,在一些情況下,該算法會產(chǎn)生大量消息,稱為消息風(fēng)暴。在圖1中Q3的處理時間BSP比MapReduce更長。因為在該RDF圖中,謂語全部是“dbpedia-owl:wikiPage-WikiLink”,所以“?x,dbpedia-owl:wikiPageWikiLink,? y”中匹配了全部的RDF_T點,并且消息會在這些點之間反復(fù)傳遞,形成性能瓶頸。

5 未來工作方向

為滿足更大數(shù)據(jù)量和更低運算復(fù)雜度的要求,未來將對以下優(yōu)化策略進(jìn)行進(jìn)一步研究:

(1)合并多個查詢:在本文算法中,都是針對一個SPARQL查詢的算法。在現(xiàn)實場景中,用戶會同時提交多個SPARQL查詢。在該算法基礎(chǔ)上,可以通過更名和合并策略來實現(xiàn)同時處理多個SPARQL查詢。比如有2個查詢“SELECT who1,who2 WHERE{? who1 like?who2}”和“SELECT who1,who2 WHERE {?who1 hate?who2}”可以更名合并為“SELECT who1,who2,who3,who4 WHERE{?who1 like? who2,?who3 hate?who4}”。由于BSP的并行特性,因此在處理多個查詢中使用更名和合并策略會減少查詢時間。

(2)預(yù)處理:在查詢前可以對RDF數(shù)據(jù)進(jìn)行預(yù)處理,去除一些在計算過程中會增加計算量和通信量,但與計算結(jié)果無關(guān)的點和邊。比如,對于數(shù)據(jù)“: tom:like:kate.:kete:hate:jim.:jim:like:tom”和SPARQL查詢“SELECT who1,who2,who3 WHERE {?who1 like?who2,?who2 hate?who3}”在RDF圖中,三元組“:jim:like:tom”和結(jié)果集并無太多關(guān)系,但是在BSP計算過程中,該邊仍然要參與計算,同時增加消息傳遞量。

(3)改善HAMA圖劃分:BSP實現(xiàn)模型HAMA默認(rèn)對圖數(shù)據(jù)中的點哈希劃分到各個計算節(jié)點上。為提高運算速度,可以修改HAMA源代碼來改善對圖數(shù)據(jù)中點哈希劃分策略,使每個計算節(jié)點中的點聯(lián)系更加緊密,從而減少計算節(jié)點之間的通信量,達(dá)到提高運算速度的效果。

6 結(jié)束語

本文根據(jù)BSP計算模型適用于圖數(shù)據(jù)的特性,提出一種基于BSP的SPARQL基本圖模式查詢算法。該算法將SPARQL基本圖模式分解成2個階段:匹配階段和迭代階段,先匹配出每個要查詢的三元組模式,然后通過迭代使部分解逐步逼近完全解,最后得到查詢結(jié)果。利用BSP模型計算框架——HAMA,驗證了該算法的正確性,并與基于 MapReduce的SPARQL基本圖模式算法進(jìn)行對比,具有較好的查詢效率。在后續(xù)工作中,將對算法進(jìn)行改進(jìn),降低時間和空間復(fù)雜度,并且進(jìn)一步完善SPARQL查詢,從而覆蓋更多的SPARQL查詢語法。

[1] Berners-Lee T,Hendler J,Lassila O.The Semantic Web [C]//Proceedings of ASWC'09.Shanghai,China: [s.n.],2009:6-9.

[2] 姜龍翔,王 鑫,李 旭,等.一種大規(guī)模RDF語義數(shù)據(jù)的分布式存儲方案[J].計算機(jī)應(yīng)用與軟件,2011, 28(11):30-32.

[3] Bizer C,Heath T,Berners-Lee T.Linked Data——The Story So Far[J].International Journal on Semantic Web and Information Systems,2009,5(3):1-22.

[4] Jiang Yang,Feng Zhiyong,Wang Xin,et al.Adapting Property Path forPolynomial-time Evaluation and Reasoning on Semantic Web[J].Transactions of Tianjin University,2013,19:130-139.

[5] 杜 方,陳躍國,杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述[J].軟件學(xué)報,2013,24(6):1222-1242.

[6] 陶 俊,孫 坦.基于Linked Data的RDF關(guān)聯(lián)框架綜析[J].現(xiàn)代圖書情報技術(shù),2011,12:1-8.

[7] Perez J,Arenas M,Gutierrez C.Semantics of SPARQL [R].Universidad de Chile,Tech Rep:TR/DCC-2006-17,2006.

[8] Pérez J,Arenas M,Gutierrez C.Semantics and Complexity of SPARQL[M]//Isabel C,Stefan D,Dean A,et al.The Semantic Web.Berlin,Germany:Springer, 2006:30-43.

[9] Gallagher B.Matching Structure and Semantics:A Survey on Graph-based Pattern Matching[C]//Proceedings of AAAI FS'06.[S.l.]:AAAI Press,2006:45-53.

[10] 何少鵬,黎建輝,沈志宏,等.大規(guī)模的RDF數(shù)據(jù)存儲技術(shù)綜述[J].網(wǎng)絡(luò)新媒體技術(shù),2013,2(1):8-16.

[11] Myung J,Yeon J,Lee S.SPARQL Basic Graph Pattern Processing with Iterative MapReduce[C]//Proceedings of 2010 Workshop on Massive Data Analytics on the Cloud.[S.l.]:ACM Press,2010:6-12.

[12] Kulkarni P.Distributed SPARQL Query Engine Using MapReduce[D].Edinburgh,UK:The University of Edinburgh,2010:18-31.

[13] Valiant L G.A Bridging Model for Parallel Computation [J].Communications of the ACM,1990,33(8): 103-111.

[14] Valiant L G.Bulk-synchronous Parallel Computer:USA, 5083265[P].1992-01-21.

[15] Malewicz G,Austern M H,Bik A J C,et al.Pregel:A System forLarge-scale Graph Processing[C]// Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures.Calgary, Canada:ACM Press,2010:135-146.

[16] HAMA[EB/OL].(2013-05-24).http://hama.apache.org/.

[17] Campbell D K G.A SurveyofModelsofParallel Computation[D].York,UK:University of York,1997.

編輯 陸燕菲

SPARQL Basic Graph Pattern Search Algorithm Based on Bulk Synchronous Parallel

LI Guo-dinga,FENG Zhi-yonga,b,RAO Guo-zhenga,b,WANG Xina,b
(a.School of Computer Science and Technology;b.Tianjin Key Laboratory of Cognitive Computing and Application,Tianjin University,Tianjin 300072,China)

With the advance of semantic Web,the Resource Description Framework(RDF)data published on the Web reaches the scale of ten billion triples,and it shows a geometric growth trend.Simple Protocol and RDF Query Language (SPARQL)query methods on stand-alone machine are no longer applicable.For this problem,this paper proposes a SPARQL Basic Graph Pattern(BGP)search algorithm based on Bulk Synchronous Parallel(BSP)model.According to the graph nature of RDF data and the definition of BGP,it divides the whole process into“matching”stage and“iteration”stage.First match each triple patterns and then iterate to get the query results eventually.It implements the algorithm by HAMA distributed computing framework.Experimental results show that it has higher query efficiency than SPARQL algorithm based on MapReduce,and it can support the SPARQL query of the large scale RDF data.

semantic Web;Resource Description Framework(RDF);SPARQL search;Basic Graph Pattern(BGP); Bulk Synchronous Parallel(BSP)model;HAMA framework

1000-3428(2014)09-0037-05

A

TP311

10.3969/j.issn.1000-3428.2014.09.008

國家"863"計劃基金資助項目(2013AA013204);國家自然科學(xué)基金資助項目(61373165,61070202)。

李國鼎(1989-),男,碩士研究生,主研方向:語義網(wǎng),軟件工程;馮志勇,教授、博士、博士生導(dǎo)師;饒國政(通訊作者),博士;王 鑫,講師、博士。

2013-08-28

2013-10-15E-mail:leeguoding@tju.edu.cn