MPPIE：基于消息傳遞的RDFS并行推理框架*

呂小玲，王　鑫,3+，馮志勇，饒國(guó)政，張小旺，許光全

1.天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津3000722.天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津3000723.南大通用數(shù)據(jù)技術(shù)股份有限公司，天津300384

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0451-15

?

MPPIE：基于消息傳遞的RDFS并行推理框架*

呂小玲1,2，王鑫1,2,3+，馮志勇1,2，饒國(guó)政1,2，張小旺1,2，許光全1,2

1.天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300072
2.天津市認(rèn)知計(jì)算與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，天津300072
3.南大通用數(shù)據(jù)技術(shù)股份有限公司，天津300384

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0451-15

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61373035, 61100049, 61373165 (國(guó)家自然科學(xué)基金); the National High Technology Research and Develfopment Program of China under Grant No. 2013AA013204 (國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-08-12, http://www.cnki.net/kcms/detail/11.5602.TP.20150812.1623.002.html

Key words: resource description framework (RDF); RDFS inference; message passing; Pregel; parallel inference

摘要：隨著語(yǔ)義Web的快速發(fā)展，RDF（resource description framework）語(yǔ)義數(shù)據(jù)規(guī)模呈現(xiàn)爆炸性增長(zhǎng)趨勢(shì)，大規(guī)模語(yǔ)義數(shù)據(jù)上的推理工作面臨嚴(yán)峻挑戰(zhàn)?；谙鬟f機(jī)制提出了一種新的RDFS（RDF schema）并行推理方案。利用RDF圖數(shù)據(jù)結(jié)構(gòu)，建立RDFS推理過(guò)程的圖上加邊模型。以頂點(diǎn)為計(jì)算中心，根據(jù)不同推理模型，向其他頂點(diǎn)傳遞推理消息，完成推理操作。當(dāng)所有推導(dǎo)出的新三元組以邊的形式加入原RDF圖中時(shí)，整個(gè)推理過(guò)程結(jié)束。在基于消息傳遞模型的開(kāi)源框架Giraph上，實(shí)現(xiàn)了RDFS并行推理框架MPPIE（message passing parallel inference engine）。實(shí)驗(yàn)結(jié)果表明，在標(biāo)準(zhǔn)數(shù)據(jù)集LUBM和真實(shí)數(shù)據(jù)集DBpedia上，MPPIE執(zhí)行速度均比當(dāng)前性能最好的語(yǔ)義推理引擎WebPIE快一個(gè)數(shù)量級(jí)，且展現(xiàn)了良好的可伸展性。

關(guān)鍵詞：資源描述框架（RDF）；RDFS推理；消息傳遞；Pregel；并行推理

1　引言

近年來(lái)，語(yǔ)義Web得到了快速的發(fā)展，行業(yè)應(yīng)用數(shù)據(jù)越來(lái)越多地選用資源描述框架（resource description framework，RDF）格式進(jìn)行發(fā)布，語(yǔ)義數(shù)據(jù)規(guī)模呈現(xiàn)爆炸性增長(zhǎng)。截至2014年4月，LOD（Linked Open Data）收集的RDF數(shù)據(jù)集已經(jīng)超過(guò)了1 000個(gè)[1]。大規(guī)模RDF數(shù)據(jù)的異構(gòu)性對(duì)語(yǔ)義數(shù)據(jù)的管理工作提出了新挑戰(zhàn)，而RDF推理使數(shù)據(jù)管理的復(fù)雜性進(jìn)一步加深[2]。如何能夠高效解決大規(guī)模RDF數(shù)據(jù)的推理問(wèn)題成為許多研究工作的焦點(diǎn)。

并行化推理方案能夠有效地利用并行計(jì)算技術(shù)解決大規(guī)模RDF數(shù)據(jù)的推理問(wèn)題[2]。目前已有基于集群的并行推理算法[3-5]和基于新型硬件的并行推理算法[6-8]等相關(guān)的推理工作研究，然而這些解決方案僅將傳統(tǒng)的推理技術(shù)直接遷移到對(duì)應(yīng)的并行計(jì)算框架之中，并未充分利用數(shù)據(jù)原有的特性，致使推理效率低下。針對(duì)這些問(wèn)題，本文提出了一種基于消息傳遞機(jī)制的新方法來(lái)處理RDF模式（RDF schema，RDFS）并行推理問(wèn)題。

利用RDF數(shù)據(jù)的圖結(jié)構(gòu)，將推理產(chǎn)生新三元組的過(guò)程映射為在圖上的兩頂點(diǎn)之間添加新邊的過(guò)程?；谙鬟f機(jī)制設(shè)計(jì)并實(shí)現(xiàn)了RDFS并行推理框架MPPIE（message passing parallel inference engine）。MPPIE對(duì)RDFS推理規(guī)則進(jìn)行分析，采用高效的規(guī)則執(zhí)行順序，減少推理中的迭代操作，提高推理效率。以頂點(diǎn)為計(jì)算中心，頂點(diǎn)間通過(guò)消息傳遞進(jìn)行通信。通過(guò)實(shí)驗(yàn)與當(dāng)前性能最好的開(kāi)源推理引擎WebPIE（Wed-scale parallel inference engine）[4]進(jìn)行對(duì)比，在標(biāo)準(zhǔn)數(shù)據(jù)集LUBM和真實(shí)數(shù)據(jù)集DBpedia上進(jìn)行測(cè)試的結(jié)果表明，MPPIE的執(zhí)行性能比WebPIE高一個(gè)數(shù)量級(jí)。

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

（1）結(jié)合RDF數(shù)據(jù)的圖結(jié)構(gòu)特點(diǎn)，提出了將推理抽象成在圖上兩個(gè)頂點(diǎn)之間添加新邊的思想，有效地利用了數(shù)據(jù)本身的結(jié)構(gòu)特性。

（2）提出了一種高效的規(guī)則執(zhí)行機(jī)制，減少了推理迭代次數(shù)，提高了推理執(zhí)行效率。

（3）基于消息傳遞機(jī)制，設(shè)計(jì)了一種新的RDFS并行推理算法，以自然的方式執(zhí)行推理過(guò)程。

（4）在Apache Giraph（http://giraph.apache.org/）框架下，實(shí)現(xiàn)了RDFS并行推理框架MPPIE。實(shí)驗(yàn)表明，MPPIE執(zhí)行速度比基于MapReduce的推理算法快一個(gè)數(shù)量級(jí)以上。

本文組織結(jié)構(gòu)如下：第2章介紹當(dāng)前RDFS推理的相關(guān)工作；第3章研究RDFS推理，并給出Pregel[9]模型的相關(guān)概念；第4章描述基于消息傳遞機(jī)制的并行推理框架MPPIE；第5章為實(shí)驗(yàn)與分析；最后進(jìn)行總結(jié)與展望。

2　相關(guān)工作

在眾多推理的研究中，單機(jī)推理系統(tǒng)[10-11]可伸展性差，難以適應(yīng)大規(guī)模RDF數(shù)據(jù)推理的需求，因此采用并行化方法解決推理問(wèn)題已經(jīng)成為一種趨勢(shì)。目前的并行推理研究主要分為以下3類：

（1）閉包計(jì)算推理

閉包計(jì)算推理是指計(jì)算所有隱含信息。Weaver 與Hendler[3]利用MPI（message passing interface）并行技術(shù)，將推理任務(wù)劃分成多個(gè)獨(dú)立子任務(wù)，每個(gè)物理節(jié)點(diǎn)均保存一份完整的模式數(shù)據(jù)，最后合并各個(gè)節(jié)點(diǎn)上的推理結(jié)果，但該技術(shù)會(huì)產(chǎn)生大量重復(fù)數(shù)據(jù)。基于MapReduce技術(shù)，WebPIE[4]的推理過(guò)程由多個(gè)Map和Reduce操作組成，通過(guò)規(guī)則間的依賴關(guān)系，完成推理計(jì)算，是目前開(kāi)源性能最好的并行推理引擎。Liu等人[5]將WebPIE的工作擴(kuò)展到模糊pD規(guī)則推理之中，其效果與WebPIE相當(dāng)。顧榮等人[12]基于MapReduce實(shí)現(xiàn)高效可擴(kuò)展的語(yǔ)義推理引擎。在新型硬件的基礎(chǔ)上，文獻(xiàn)[6]利用共享內(nèi)存體系結(jié)構(gòu)，實(shí)現(xiàn)了RDFS推理，但可擴(kuò)展性受到機(jī)器核數(shù)的限制。Peters等人[7-8]利用Rete[13]算法實(shí)現(xiàn)了語(yǔ)義推理，但通信代價(jià)較高。文獻(xiàn)[14]利用分布式哈希表進(jìn)行推理，然而無(wú)法有效處理大規(guī)模數(shù)據(jù)，可擴(kuò)展性較差。此外，Oren等人[15]基于數(shù)據(jù)劃分提出了divide-conquerswap策略，實(shí)現(xiàn)了Marvin，但其性能取決于輸入數(shù)據(jù)規(guī)模。文獻(xiàn)[16]使用規(guī)則集[17]實(shí)現(xiàn)了增量式推理，然而可擴(kuò)展性受限于機(jī)器核數(shù)。

（2）查詢時(shí)推理

查詢時(shí)推理僅根據(jù)給定查詢推理出與查詢相關(guān)的隱含三元組。Kaoudi等人[18]在分布式哈希表的基礎(chǔ)上，完成前向鏈接推理與反向鏈接推理的實(shí)現(xiàn)與對(duì)比，以查詢驅(qū)動(dòng)反向鏈接推理，但存在負(fù)載均衡問(wèn)題。Salvadores等人[19]研究了RDFS的反向鏈接推理，以分布式存儲(chǔ)系統(tǒng)4store為基礎(chǔ)，將MRDF規(guī)則[20]推理形式化，并進(jìn)行性能以及可伸展性測(cè)試，但是實(shí)現(xiàn)規(guī)則集較簡(jiǎn)單。文獻(xiàn)[21]在查詢過(guò)程中融入RDFS推理，查詢重寫(xiě)將在掃描處理該查詢必需的文件時(shí)進(jìn)行，根據(jù)重寫(xiě)后的查詢，掃描所有與之相關(guān)的三元組數(shù)據(jù)，然而該方法僅實(shí)現(xiàn)了subClass規(guī)則。

（3）混合推理

一些研究工作充分利用上述兩者的優(yōu)勢(shì)，提出混合式推理方案。QueryPIE[22]分析了前向鏈接與反向鏈接推理的優(yōu)缺點(diǎn)，提出了一種混合推理方法：首先在查詢前完成模式數(shù)據(jù)的推理，以此減少查詢中的重復(fù)計(jì)算；然后利用提前推理的結(jié)果對(duì)推理樹(shù)進(jìn)行剪枝，避免多余計(jì)算。Rya[23]基于Apache Accumulo完成了混合推理，但實(shí)現(xiàn)規(guī)則較少。

值得注意的是，各類研究適用于不同情況。本文屬于閉包計(jì)算推理，與其他兩類不具可比性。利用RDF數(shù)據(jù)的圖結(jié)構(gòu)，將推理過(guò)程映射為在圖上兩個(gè)頂點(diǎn)之間添加新邊的過(guò)程，提出了一種新的基于消息傳遞機(jī)制的并行推理框架，以RDF圖中的頂點(diǎn)為計(jì)算單元，執(zhí)行推理操作。

3　基本概念

RDF是W3C提出的標(biāo)準(zhǔn)數(shù)據(jù)表示格式，能夠?qū)⒄Z(yǔ)義Web中的信息表達(dá)成機(jī)器理解的語(yǔ)義信息。

定義1（RDF三元組t）一條RDF三元組t由主語(yǔ)s、謂語(yǔ)p、賓語(yǔ)o組成，表示成：

t=(s,p,o)∈U?B×U?B×U?B?L

其中U、B和L分別為統(tǒng)一資源標(biāo)識(shí)符（uniform resource identifier，URI）的集合、匿名節(jié)點(diǎn)的集合以及字面值的集合。主語(yǔ)集合、謂語(yǔ)集合以及賓語(yǔ)集合分別由S、P、O表示。

定義2（RDF圖G）有限條三元組t的集合構(gòu)成RDF圖G={t|t∈S×P×O}。其中，G映射到圖結(jié)構(gòu)上的頂點(diǎn)集合為V={v|v∈S?O}，邊的集合為E= {e|e= ,λ(e)=p,u∈S,p∈P,v∈O}，其中標(biāo)簽函數(shù)λ:E→P將邊映射到謂語(yǔ)。

G是一種具有語(yǔ)義的特殊的有向標(biāo)簽圖。某些三元組的謂語(yǔ)可作為其他三元組的主語(yǔ)或賓語(yǔ)出現(xiàn)，即V?P≠?。圖形上表現(xiàn)為允許邊作為頂點(diǎn)出現(xiàn)，在數(shù)學(xué)上將這種圖稱為3-均勻超圖。

下面將介紹RDFS推理規(guī)則以及Pregel計(jì)算模型。本文方法正是在Pregel模型的基礎(chǔ)上實(shí)現(xiàn)了RDFS推理。

3.1RDFS推理規(guī)則

RDFS提供了RDF數(shù)據(jù)的數(shù)據(jù)模型定義，擴(kuò)展了基本的RDF詞匯，描述了類和屬性之間的關(guān)系。RDFS規(guī)則集被證明是完備的[24]，是推理研究中首選的規(guī)則集。表1中所列的規(guī)則集用R表示。

Table 1 RDFS inference rules表1　RDFS推理規(guī)則集

RDFS規(guī)則集中的R1、R4a與R4b表示每個(gè)三元組中的主語(yǔ)與賓語(yǔ)為字面值或者資源，對(duì)推理并無(wú)實(shí)際意義，因此不進(jìn)行討論。為了簡(jiǎn)潔起見(jiàn)，后文將使用表2中謂語(yǔ)的縮寫(xiě)形式。

Table 2 Abbreviation for predicates of RDFS rules表2　RDFS規(guī)則集中謂語(yǔ)的縮寫(xiě)形式

定義3（推理）給定RDF圖G與規(guī)則集R，根據(jù)R中的某條規(guī)則ri得到G中蘊(yùn)含的三元組集合T的過(guò)程稱為推理過(guò)程，記作G├riT。

定義4（RDF圖的推理閉包G*）給定RDF圖G與完備的規(guī)則集R，G*為G的推理閉包，那么G*=Gα當(dāng)且僅當(dāng)Gα=Gα-1，其中Gα滿足：

（1）G0=G

（2）Gα=Gα-1?{t|Gα-1├riT,t∈T,ri∈R}

當(dāng)RDF圖通過(guò)迭代應(yīng)用推理規(guī)則得到推理閉包時(shí)，推理工作結(jié)束。所得到的推理閉包G*為最終包含所有隱含信息的RDF圖。

3.2Pregel計(jì)算模型

Google為了處理大規(guī)模圖計(jì)算領(lǐng)域中的問(wèn)題，提出了一種基于整體同步并行（bulk synchronous parallel，BSP）[25]的分布式圖計(jì)算模型Pregel，能夠有效地解決大規(guī)模圖計(jì)算問(wèn)題。

定義5（Pregel計(jì)算模型）整個(gè)計(jì)算過(guò)程由一系列稱之為超步（superstep）的迭代步驟組成，以頂點(diǎn)為中心進(jìn)行計(jì)算，計(jì)算由消息驅(qū)動(dòng)。Pregel模型中部分核心操作符的定義如下：

（1）輸入數(shù)據(jù)圖G。Idv表示頂點(diǎn)V的標(biāo)識(shí)符集合。對(duì)?v∈V，定義映射：

①id:V→Idv，返回v的唯一標(biāo)識(shí)符；

②inEdges:V→E，返回v的入邊集合；

③outEdges:V→E，返回v的出邊集合。

對(duì)?e∈E，定義：

①p:E→P，返回e上的謂語(yǔ)；

②srcId:E→Idv，返回e的源頂點(diǎn)；

③dstId:E→Idv，返回e的目的頂點(diǎn)。

（2）并行操作。?v∈V，v存在活躍與停機(jī)兩種狀態(tài)。在每個(gè)超步中，活躍狀態(tài)頂點(diǎn)并行執(zhí)行用戶定義的Compute方法。在每個(gè)v上定義如下函數(shù)：

①getSuperstep()，獲取當(dāng)前超步次序；

②voteToHalt()，將頂點(diǎn)狀態(tài)置為停機(jī)；

③sendMessage(vid,message)，將message發(fā)送給頂點(diǎn)id為vid的頂點(diǎn)；

④addEdge(e)，將邊e添加到圖上。

如圖1所示，白色頂點(diǎn)代表活躍狀態(tài)頂點(diǎn)，灰色頂點(diǎn)代表停機(jī)狀態(tài)頂點(diǎn)。

Fig.1 Pregel computation model圖1　Pregel計(jì)算模型

每一個(gè)接收到消息的活躍狀態(tài)頂點(diǎn)將執(zhí)行一次Compute方法。該方法接收來(lái)自前一個(gè)超步的消息集合M，完成相應(yīng)的計(jì)算后，可發(fā)送消息給下一個(gè)超步中的某個(gè)計(jì)算頂點(diǎn)，也可進(jìn)行停機(jī)操作。當(dāng)所有頂點(diǎn)都已達(dá)到停機(jī)狀態(tài)，且沒(méi)有消息傳遞時(shí)，計(jì)算停止。

4　RDFS并行推理框架MPPIE

RDFS的推理過(guò)程是RDF圖上迭代應(yīng)用推理規(guī)則的過(guò)程，當(dāng)RDF圖中所有隱含信息都作為顯式數(shù)據(jù)出現(xiàn)時(shí)，即在當(dāng)前規(guī)則下，計(jì)算得到數(shù)據(jù)集的推理閉包時(shí)，迭代停止。定理1保證了由G能夠得到G*。

定理1給定RDFS規(guī)則集R，由RDF圖G可以得到G*。

證明由定義3可知，?ri∈R有G├riT。因?yàn)镚由有限條三元組構(gòu)成，且RDFS規(guī)則集是完備的，根據(jù)定義4，那么必然?α，使得Gα=Gα-1，其中G0=G，Gα=Gα-1?{t|Gα-1├riT,t∈T,ri∈R}。因此，在RDFS規(guī)則集R下，有G*=Gα。□

根據(jù)定理可知，RDFS推理計(jì)算是有限的。推理得到的G*為包含G中所有隱含三元組的RDF圖。

Fig.2 An example for RDFS inference圖2　RDFS推理示例

例1圖2為RDFS推理示例。這里的RDF圖來(lái)自于DBpedia數(shù)據(jù)集[26]，其中非實(shí)線的邊代表隱含的三元組。當(dāng)所有非實(shí)線的邊作為推理出的新邊添加到該RDF圖上時(shí)，即得到推理閉包。

4.1推理抽象模型

對(duì)于RDF圖數(shù)據(jù)，MPPIE將推理過(guò)程抽象成在圖上兩個(gè)頂點(diǎn)之間添加新邊的過(guò)程。執(zhí)行推理時(shí)，各個(gè)規(guī)則的結(jié)論作為圖上新邊出現(xiàn)的形式有所差異。根據(jù)這些差異，將規(guī)則分為以下6類：

（1）R6、R10：僅一個(gè)條件，且生成邊為一條從該頂點(diǎn)出發(fā)，指向自身的邊。

（2）R8、R12、R13：僅一個(gè)條件，生成邊為一條從該頂點(diǎn)出發(fā)，指向其他頂點(diǎn)的邊。

（3）R5、R11：兩個(gè)條件，具有傳遞性特點(diǎn)，且生成邊的兩個(gè)頂點(diǎn)由另一中間頂點(diǎn)相連。

（4）R7：兩個(gè)條件，且生成邊為已存在邊的兩個(gè)頂點(diǎn)間的新邊。

（5）R2、R3：兩個(gè)條件，且生成邊的兩個(gè)頂點(diǎn)分別為某一條邊上其中一個(gè)頂點(diǎn)以及與邊上謂語(yǔ)相鄰邊上的目的頂點(diǎn)。

（6）R9：兩個(gè)條件，不具有傳遞性特點(diǎn)，且生成邊的兩個(gè)頂點(diǎn)由另一中間頂點(diǎn)相連。由于其不具備傳遞性特點(diǎn)，故與（3）進(jìn)行了區(qū)分。

規(guī)則的不同特點(diǎn)決定了其在推理過(guò)程中需采用不同方式進(jìn)行推理。通過(guò)以上分析，可將RDFS推理規(guī)則集抽象成6種不同的推理模型，如圖3所示。其中虛線代表推理過(guò)程中產(chǎn)生的新邊，即規(guī)則的結(jié)論。

Fig.3 Inference model圖3　推理模型

在RDF圖中，MPPIE將推理過(guò)程表示為不同推理模型的組合。

例2在圖2中，(dbo:Actor, sc, ex:Artist)與(dbo: Artist, sc, ex:Person)滿足推理模型3，得到(dbo:Actor, sc, ex:Person)。

4.2規(guī)則執(zhí)行順序優(yōu)化

在RDFS規(guī)則集的條件和結(jié)論中，三元組類型可為任意實(shí)例三元組，或以type、sc、sp、dom和ran為謂語(yǔ)的三元組。當(dāng)某條規(guī)則結(jié)論的三元組類型恰好與另一條規(guī)則條件中某一三元組類型相一致時(shí)，前一規(guī)則的結(jié)論可作為后一規(guī)則的條件。例如，R2的結(jié)論是以type為謂語(yǔ)的一條三元組，R9的條件包含以type為謂語(yǔ)的三元組以及以sc為謂語(yǔ)的三元組，那么R2的輸出可作為R9的輸入。

由圖3的推理模型可以看出，前兩類推理模型較簡(jiǎn)單，僅根據(jù)RDF圖中的一條邊，便可進(jìn)行加邊操作，完成推理。實(shí)現(xiàn)過(guò)程較簡(jiǎn)單，故不再討論。對(duì)其余4類模型中的規(guī)則，依據(jù)條件與結(jié)論包含的三元組類型的不同，進(jìn)一步進(jìn)行如表3所示的分類。

Table 3 Classification of RDFS rules表3　RDFS推理規(guī)則分類

在表3中，“條件包含”或“結(jié)論包含”分別表示規(guī)則的條件或結(jié)論中至少有一條三元組滿足該類型。同一行中結(jié)論包含的規(guī)則應(yīng)在條件包含的規(guī)則之前執(zhí)行，如第一行中，規(guī)則R7應(yīng)在規(guī)則R2、R3之前執(zhí)行。根據(jù)規(guī)則間的依賴關(guān)系，合理安排規(guī)則的執(zhí)行順序，可減少規(guī)則間的迭代，從而減少消息傳遞次數(shù)。MPPIE的規(guī)則執(zhí)行順序如圖4所示。

定理2按照?qǐng)D4的規(guī)則執(zhí)行順序，所有規(guī)則執(zhí)行一遍即可完成推理。

證明圖4為有向無(wú)環(huán)圖（directed acyclic graph，DAG），形成了一種拓?fù)湫?。在該拓?fù)湫蛑?，R9依賴于R2、R3和R11，R2與R3依賴于R7，同時(shí)R7依賴于R5。依據(jù)該拓?fù)湫?，?zhí)行一遍即可完成推理。□

Fig.4 Execution order of rules圖4　規(guī)則執(zhí)行順序

4.3RDFS并行推理算法

MPPIE將RDF圖上的每個(gè)頂點(diǎn)作為并行計(jì)算的單元，每個(gè)頂點(diǎn)通過(guò)消息傳遞進(jìn)行通信，按照規(guī)則執(zhí)行順序完成推理過(guò)程。在初始超步中，分別判斷鄰邊是否可以匹配某一推理模型。若匹配，則根據(jù)相應(yīng)的推理模型添加新邊。當(dāng)加邊操作完成后，如需進(jìn)行下一步迭代，則將相關(guān)信息傳遞到下一輪超步計(jì)算中，否則將該頂點(diǎn)置為停機(jī)狀態(tài)。當(dāng)所有隱含信息均以新邊形式建立在原RDF圖上時(shí)，整個(gè)推理過(guò)程結(jié)束。最終得到的RDF推理閉包圖即為結(jié)果圖。

例3在圖2中，該RDF圖在超步0中，所有頂點(diǎn)都處于活躍狀態(tài)，依據(jù)圖4的規(guī)則執(zhí)行順序執(zhí)行推理。例如頂點(diǎn)dbo:acting檢測(cè)出鄰邊滿足R5，將對(duì)應(yīng)的目的頂點(diǎn)ex:involving的信息以消息的形式傳遞給需要添加新邊的頂點(diǎn)dbo:staring。在下個(gè)超步中，dbo:staring接收到該消息，添加新邊(dbo:staring, sp, ex:involving)，并將狀態(tài)置為停機(jī)。以此類推，當(dāng)所有推理規(guī)則都執(zhí)行完畢，推理結(jié)束。

下面對(duì)其余4類推理模型分別介紹其并行算法。

推理模型3傳遞閉包規(guī)則的推理

推理模型3包括sp以及sc傳遞規(guī)則。

算法1詳細(xì)描述了傳遞閉包算法，主要步驟包括：

（1）對(duì)于所有處于活躍狀態(tài)的頂點(diǎn)，判斷入邊與出邊是否同時(shí)包含同一傳遞屬性。若包含，向該入邊的源頂點(diǎn)發(fā)送添加新邊的消息，同時(shí)將狀態(tài)置為停機(jī)。

（2）接收消息的頂點(diǎn)根據(jù)消息內(nèi)容添加新邊。此新邊可作為下一輪推理中的條件，因此向此新邊的目的頂點(diǎn)發(fā)送消息，使其變?yōu)榛钴S狀態(tài)。

（3）重復(fù)執(zhí)行以上兩個(gè)步驟，直至所有頂點(diǎn)都達(dá)到停機(jī)狀態(tài)。

例4圖5展示了傳遞閉包規(guī)則sc的推理過(guò)程。傳遞屬性鏈上共有3個(gè)頂點(diǎn)。在超步0時(shí)所有頂點(diǎn)處于活躍狀態(tài)，只有頂點(diǎn)2同時(shí)滿足入邊與出邊上包含sc屬性，因此向需要添加新邊的頂點(diǎn)1發(fā)送消息，激活下一超步中頂點(diǎn)1。在超步1時(shí)，頂點(diǎn)1添加新邊(1，sc，3)，并向頂點(diǎn)3發(fā)送消息。在超步2時(shí)，所有頂點(diǎn)沒(méi)有新邊需要添加，狀態(tài)全部為停機(jī)，傳遞閉包推理結(jié)束。

算法1傳遞閉包算法Compute(M)

輸入：消息集合M

輸出：是否停機(jī)

1. curStep?getSuperstep();

2. If curStep = 0 then

3. For?ei∈v.inEdges,?eo∈v.outEdges do //tranP同為sc或sp

4.If ei.p =tranP and eo.p = tranP then

5.sendMessage (ei.srcId , Message (eo.dstId) ;

6.End if

7. End for

8. Else if curStep % 2 = 1 then //奇數(shù)次超步，加邊

9. For?m∈M do

10.創(chuàng)建新邊e;

11.e.srcId←v.id,e.srcId←m.vid,e.p←tranP ;

12.v.addEdge(e) ; //添加新邊

13.sendMessage(e.dstId, Message(v.id)) ;

14.End for

Fig.5 An example for transitivity closure圖5　傳遞閉包示例

15. Else //偶數(shù)次超步，確定新邊信息，并發(fā)送消息

16. For?m∈M do

17. For?eo∈v.outEdges do

18. If eo.p = tranP then

19.sendMessage(m.vid, Message (eo.dstId)) ;

20. End if

21. End for

22. End for

23. End if

24. voteToHalt();

算法1中兩次迭代完成一次加邊過(guò)程：第一次迭代確定加邊信息，并把相關(guān)信息發(fā)送給需要加邊的頂點(diǎn)；第二次迭代根據(jù)接收到的加邊信息，完成加邊。

個(gè)超步能夠完成傳遞閉包推理計(jì)算。

第k次進(jìn)行添加新邊操作時(shí)，所有新邊集合中邊的最長(zhǎng)距離為2k。此類新邊的目的頂點(diǎn)稱為邊緣頂點(diǎn)。所有以此類新邊的源點(diǎn)為起始點(diǎn)的新邊集合中，若包含新邊距離小于2k的新邊，向這些新邊的目的頂點(diǎn)發(fā)送的消息為多余的消息。因此，在算法1中，僅需向邊緣頂點(diǎn)發(fā)送消息。在第11行前添加：If 2curStep= e.step進(jìn)行判斷，其中以e.step表示兩點(diǎn)之間的路徑長(zhǎng)度。該優(yōu)化策略可減少不必要的消息傳遞。

推理模型4 sp繼承規(guī)則的推理

算法2為sp繼承算法?；钴S頂點(diǎn)判斷出邊屬性是否有父屬性，若存在父屬性，則以父屬性作為新邊的謂語(yǔ)，完成對(duì)應(yīng)的加邊操作。

算法2 sp繼承算法Compute(M)

輸入：消息集合M

輸出：是否停機(jī)

1. For?eo∈v.outEdges do

2. If eo.p∈subP.srcIds then //subP存儲(chǔ)p為sp的邊

3.For?d∈subP.dstIds do

4.創(chuàng)建新邊e;

5.e.srcId←v.id,e.dstId←eo.dstId,e.p←d ;

6.v.addEdge(e) ;

7.End for

8.End if

9. End for

10. voteToHalt();

該算法在一輪迭代中即可完成sp繼承規(guī)則的推理。假設(shè)該頂點(diǎn)有N條出邊的屬性存在父屬性，且其中父屬性平均個(gè)數(shù)為K個(gè)，那么該算法的時(shí)間復(fù)雜度為O(N×K)。

例5如圖2所示，(db:Rain_Man, dbo:staring, db: Tom_Cruise)與(dbo:staring, sp, ex:acting)，(db:Rain_ Man, dbo:acting, db:Tom_Cruise)與(dbo:acting, sp, ex: involving)滿足推理模型4，根據(jù)算法2的計(jì)算過(guò)程，得到(db:Rain_Man, ex:acting, db:Tom_Cruise)與(db: Rain_Man, ex:involving, db:Tom_Cruise)。

推理模型5類型規(guī)則的推理

推理模型5包括dom以及ran類型規(guī)則。

算法3為類型推理算法。活躍頂點(diǎn)分別判斷出邊屬性上是否包含定義域以及入邊屬性上是否包含值域，若滿足其中之一，則添加對(duì)應(yīng)的新邊信息。

算法3類型推理算法Compute(M)

輸入：消息集合M

輸出：是否停機(jī)

1. curStep?getSuperstep();

2. If curStep = 0 then

3. For?eo∈v.outEdges do

4. If eo.p∈domain.srcIdsthen//domain存儲(chǔ)p為dom的邊

5.For?d∈domain.dstIds do //R2添加新邊操作

6.創(chuàng)建新邊e;

7.e.srcId←v.id,e.dstId←d,e.p←type ;

8.v.addEdge(e) ;

9.End for

10.End if

11. End for

12. For?ei∈v.inEdges do

13. If ei.p∈range.srcIds then //range存儲(chǔ)p為ran的邊

14.For?d∈range.dstIds do //R3添加新邊操作

15.創(chuàng)建新邊e;

16.e.srcId←v.id,e.dstId←d,e.p←type ;

17.v.addEdge(e) ;

18.End for

19.End if

20. End for

21. End if

22. voteToHalt();

該算法在一輪迭代中即可完成新邊的添加，僅判斷邊上的屬性是否包含定義域或者值域。假設(shè)該頂點(diǎn)包含定義域的屬性個(gè)數(shù)平均為d個(gè)，且有K個(gè)定義域，包含值域的屬性個(gè)數(shù)平均為h個(gè)，且有N個(gè)值域，那么該算法的時(shí)間復(fù)雜度為O(d×K+h×N)。

例6如圖2所示，(db:Rain_Man, dbo:staring, db: Tom_Cruise)與(dbo:staring, dom, dbo:Film)，(db:Rain_ Man, ex:involving, db:Tom_Cruise)與(dbo: involving, dom, dbo:Work)，(db:Rain_Man, dbo:staring, db:Tom_ Cruise)與(dbo:staring, ran, dbo:Actor)，(db:Rain_Man, ex:involving, db:Tom_Cruise)與(dbo: involving, ran, dbo:Person)滿足推理模型5，根據(jù)算法3的計(jì)算過(guò)程，得到(db:Rain_Man, type, dbo:Film)、(db:Rain_Man, type, dbo:Work)、(db:Tom_Cruise, type, dbo:Actor)以及(db:Tom_Cruise, type, dbo:Person)。

推理模型6 sc繼承規(guī)則的推理

算法4為sc繼承算法?；钴S頂點(diǎn)判斷出邊中的屬性是否包含sc，同時(shí)入邊中的屬性是否包含type，如兩者同時(shí)滿足，則完成對(duì)應(yīng)的添加新邊的操作。

算法4 sc繼承算法Compute(M)

輸入：消息集合M

輸出：是否停機(jī)

1. curStep?getSuperstep();

2. If curStep = 0 then

3. For?ei∈v.inEdges,?eo∈v.outEdges do

4.If ei.p = type and eo.p = sc then

5.sendMessage (ei.srcId , Message (eo.dstId )) ;

6.End if

7.End for

8. Else //接收到新邊信息，進(jìn)行加邊操作

9.For?m∈M do

10.創(chuàng)建新邊e;

11.e.srcId←v.id,e.dstId←m.vid,e.p←type ;

12.v.addEdge(e);

13.End for

14. End if

15. voteToHalt();

假設(shè)該頂點(diǎn)共有K條入邊和N條出邊，則超步0的時(shí)間復(fù)雜度為O(K×N)。在K條入邊中，假設(shè)有k條邊的謂語(yǔ)為type，在N條出邊中有n條邊的謂語(yǔ)為sc，則共會(huì)發(fā)送k×n條消息。在超步1的時(shí)間復(fù)雜度為O(k×n)。因此，該算法的時(shí)間復(fù)雜度為O(K×N+k×n)。

例7如圖2所示，(db:Tom_Cruise, type, dbo:Actor) 與(dbo:Actor, sc, dbo:Artist)滿足推理模型6，根據(jù)算法4的計(jì)算過(guò)程，由頂點(diǎn)dbo:Actor發(fā)送消息到頂點(diǎn)db:Tom_Cruise。db:Tom_Cruise接收到消息后，添加新邊(db:Tom_Cruise, type, dbo:Artist)。

下面對(duì)MPPIE并行推理算法的正確性進(jìn)行證明。

定理4給定RDF圖G以及RDFS規(guī)則集R，由以上算法可得到G*。

證明首先證明算法的可靠性（歸納法）。

歸納基礎(chǔ)。第1次推理添加新邊時(shí)，根據(jù)以上算法，僅有滿足規(guī)則的條件才能得到相應(yīng)的結(jié)論。該結(jié)論作為新邊加入到G中，即滿足?ri∈R，G├riT推理結(jié)果可靠，此時(shí)G1=G?{t|G├riT,t∈T,ri∈R}。

歸納步驟。假設(shè)第k次推理過(guò)程中，?ri∈R有Gk=Gk-1?{t|Gk-1├riT,t∈T,ri∈R}，且Gk-1├riT的推理結(jié)果可靠。當(dāng)?shù)趉+1次添加新邊時(shí)，根據(jù)以上算法，以Gk作為輸入數(shù)據(jù)圖。當(dāng)滿足規(guī)則的條件時(shí)，添加相應(yīng)的結(jié)論，那么有Gk├riT的推理結(jié)果是可靠的，此時(shí)Gk+1=Gk?{t|Gk├riT,t∈T,ri∈R}。由假設(shè)可知，前k次推理結(jié)果可靠，那么第k+1次推理結(jié)果可靠。

其次證明算法的完備性（反證法）。

假設(shè)由所提出的算法推理得到的結(jié)果集合為EM，t∈G*但t?EM。若t∈G*，由定義4可知，t必為某一規(guī)則的結(jié)論。同時(shí)，按照?qǐng)D4的規(guī)則執(zhí)行順序進(jìn)行推理時(shí)，t可由推理規(guī)則推出，即t∈EM。而假設(shè)為t?EM，矛盾。因此得證。□

5　實(shí)驗(yàn)

基于開(kāi)源框架Apache Giraph實(shí)現(xiàn)了MPPIE。Giraph是Pregel計(jì)算模型的實(shí)現(xiàn)，底層為Hadoop （http://hadoop.apache.org/）框架，通過(guò)消息驅(qū)動(dòng)頂點(diǎn)完成計(jì)算。本文與WebPIE進(jìn)行對(duì)比實(shí)驗(yàn)。

5.1實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)集群由8臺(tái)節(jié)點(diǎn)構(gòu)成，由一臺(tái)Gigabit以太網(wǎng)交換機(jī)連接。每個(gè)計(jì)算節(jié)點(diǎn)配置為Intel?Xeon?CPU E5 @ 2.00 GHz，內(nèi)存為64 GB，并配置1 TB硬盤(pán)。操作系統(tǒng)為64位Ubuntu 12.04 LTS Server，Giraph版本1.1.0，Hadoop版本0.20.203。

實(shí)驗(yàn)選用標(biāo)準(zhǔn)數(shù)據(jù)集LUBM（Lehigh University Benchmark）[27]和真實(shí)數(shù)據(jù)集DBpedia 3.9進(jìn)行測(cè)試。MPPIE采用與WebPIE相同的數(shù)據(jù)編碼方案。所有測(cè)試數(shù)據(jù)經(jīng)過(guò)壓縮編碼后，均勻分布在各個(gè)計(jì)算節(jié)點(diǎn)上。

LUBM作為標(biāo)準(zhǔn)語(yǔ)義知識(shí)庫(kù)，已經(jīng)成為大規(guī)模語(yǔ)義應(yīng)用的測(cè)試基準(zhǔn)。以隨機(jī)的形式生成某大學(xué)部門(mén)、教師以及學(xué)生等數(shù)據(jù)信息。本實(shí)驗(yàn)生成5組規(guī)模不同的LUBM數(shù)據(jù)集：LUBM- 200、LUBM- 400、LUBM-600、LUBM-800和LUBM-1000，分別代表了200、400、600、800和1 000個(gè)大學(xué)的數(shù)據(jù)，三元組條數(shù)從27.64×106到138.32×106不等。

DBpedia是從維基百科中抽取出的結(jié)構(gòu)化信息數(shù)據(jù)，被廣泛應(yīng)用在語(yǔ)義Web領(lǐng)域相關(guān)應(yīng)用的實(shí)驗(yàn)測(cè)試之中。本實(shí)驗(yàn)選取了DBpedia的部分?jǐn)?shù)據(jù)，分別為：instance_types_en、mappingbased_properties_en和specific_mappingbased_properties_en數(shù)據(jù)集。其三元組規(guī)模達(dá)到42.53×106條。

表4為所選用實(shí)驗(yàn)數(shù)據(jù)集的詳細(xì)信息。

5.2實(shí)驗(yàn)結(jié)果及分析

所有實(shí)驗(yàn)均使用了完整的RDFS規(guī)則集作為推理規(guī)則集，所有實(shí)驗(yàn)結(jié)果均為平均值。首先，在LUBM數(shù)據(jù)集和DBpedia數(shù)據(jù)集上測(cè)試并對(duì)比了MPPIE與WebPIE的推理執(zhí)行性能。其次，測(cè)試了不同規(guī)模的LUBM數(shù)據(jù)集對(duì)推理性能的影響。最后，進(jìn)行了集群可伸展性實(shí)驗(yàn)，設(shè)計(jì)了在1到8個(gè)節(jié)點(diǎn)規(guī)模的集群下MPPIE與WebPIE性能變化實(shí)驗(yàn)。

5.2.1執(zhí)行性能測(cè)試與對(duì)比

在6組數(shù)據(jù)上測(cè)試并對(duì)比MPPIE與WebPIE執(zhí)行性能，各自推理執(zhí)行時(shí)間如表5所示。

Table 4 Information of datasets表4　數(shù)據(jù)集統(tǒng)計(jì)信息

Table 5 Comparison of reasoning time表5　推理執(zhí)行時(shí)間對(duì)比

MPPIE推理時(shí)間在14.37 s到41.78 s之間。實(shí)驗(yàn)結(jié)果表明，相比WebPIE，MPPIE的推理執(zhí)行速度快一個(gè)數(shù)量級(jí)以上。MPPIE的效率明顯高于基于Map-Reduce的推理工作的執(zhí)行效率，其原因分析如下：（1）采用的消息傳遞機(jī)制更適合于圖上的推理工作；（2）以頂點(diǎn)為中心進(jìn)行計(jì)算，充分考慮了RDF圖數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)；（3）由推理得到的結(jié)果作為圖上的新邊存儲(chǔ)時(shí)，若該邊在圖中已經(jīng)存在，則不再重復(fù)添加，減少了重復(fù)數(shù)據(jù)處理過(guò)程。

5.2.2數(shù)據(jù)規(guī)模對(duì)推理性能的影響

選取從200到1 000個(gè)大學(xué)規(guī)模不等的LUBM數(shù)據(jù)集進(jìn)行數(shù)據(jù)可伸展性測(cè)試。圖6展示了MPPIE與WebPIE各自的推理執(zhí)行時(shí)間。

Fig.6 Scalability test using datasets with different scale圖6　不同規(guī)模數(shù)據(jù)集對(duì)推理性能的影響測(cè)試

實(shí)驗(yàn)結(jié)果表明，隨著LUBM數(shù)據(jù)集規(guī)模的增大，MPPIE推理時(shí)間與數(shù)據(jù)集規(guī)?；境示€性增長(zhǎng)趨勢(shì)。

在每個(gè)數(shù)據(jù)集上，WebPIE推理執(zhí)行時(shí)間均明顯高于MPPIE。取兩者的比值作為評(píng)價(jià)MPPIE相比于WebPIE執(zhí)行速度快慢的標(biāo)準(zhǔn)，該值表示執(zhí)行速度提升的倍數(shù)，比值越大，說(shuō)明MPPIE性能越好。圖7展示了在不同規(guī)模數(shù)據(jù)集上，MPPIE執(zhí)行速度相比于WebPIE提升的倍數(shù)變化趨勢(shì)。

Fig.7 Multiples of reasoning speed圖7　推理執(zhí)行速度提升倍數(shù)

隨著LUBM數(shù)據(jù)集規(guī)模不斷增大，MPPIE執(zhí)行速度提升的倍數(shù)呈現(xiàn)下降趨勢(shì)，但其下降趨勢(shì)逐漸平緩。主要由于在推理過(guò)程中，各個(gè)集群節(jié)點(diǎn)上消息傳遞的通信代價(jià)隨著推理數(shù)據(jù)規(guī)模增大而有所增加，導(dǎo)致推理速度提升的倍數(shù)呈下降趨勢(shì)。根據(jù)此趨勢(shì)，預(yù)測(cè)推理速度提升的倍數(shù)可能達(dá)到某個(gè)閾值，且至少較WebPIE高一個(gè)數(shù)量級(jí)。

在LUBM數(shù)據(jù)集上，平均提升倍數(shù)為38.26倍，在DBpedia數(shù)據(jù)集上，平均提升倍數(shù)為30.23倍。整體平均提升倍數(shù)為34.25倍。

此外，推理過(guò)程中的吞吐率是衡量推理性能的主要指標(biāo)，表示單位時(shí)間內(nèi)推理出的三元組條數(shù)。對(duì)于不同的數(shù)據(jù)集，MPPIE推理平均吞吐率如圖8所示。

Fig.8 Average throughput of reasoning圖8　推理的平均吞吐率

實(shí)驗(yàn)結(jié)果顯示，在LUBM數(shù)據(jù)集上，隨著數(shù)據(jù)規(guī)模的不斷增大，吞吐率逐漸上升，最高可以達(dá)到798.23 KTriples/s。而在DBpedia數(shù)據(jù)集上，其隱含的三元組條數(shù)與LUBM-200相近，但吞吐率小于LUBM-200的吞吐率。分析DBpedia與LUBM數(shù)據(jù)集的特點(diǎn)可知，相比于標(biāo)準(zhǔn)數(shù)據(jù)集LUBM，真實(shí)數(shù)據(jù)集DBpedia的復(fù)雜度較高，實(shí)驗(yàn)結(jié)果說(shuō)明數(shù)據(jù)集的復(fù)雜度會(huì)影響推理過(guò)程中的吞吐率。

5.2.3集群規(guī)模對(duì)推理性能的影響

集群規(guī)模從1個(gè)節(jié)點(diǎn)逐漸增加到8個(gè)節(jié)點(diǎn)，對(duì)MPPIE的推理性能變化進(jìn)行了評(píng)估。數(shù)據(jù)集選用真實(shí)數(shù)據(jù)集DBpedia和標(biāo)準(zhǔn)數(shù)據(jù)集LUBM-1000。集群規(guī)模對(duì)推理性能影響的實(shí)驗(yàn)結(jié)果如圖9所示。

在DBpedia與LUBM-1000數(shù)據(jù)集上，圖9中（a）與（b）的實(shí)驗(yàn)結(jié)果均顯示，隨著集群規(guī)模的增大，MPPIE推理執(zhí)行時(shí)間迅速下降。當(dāng)集群規(guī)模不斷增大時(shí)，由于集群中各個(gè)節(jié)點(diǎn)之間的通信代價(jià)會(huì)逐漸增加，致使并行推理計(jì)算的時(shí)間逐漸趨近某個(gè)極限閾值。同時(shí)，圖9顯示，在1至8個(gè)節(jié)點(diǎn)的集群上，MPPIE達(dá)到極限閾值的速度慢于WebPIE，說(shuō)明其可伸展性優(yōu)于WebPIE。

Fig.9 Scalability test using clusters with different scales圖9　不同規(guī)模集群上可伸展性測(cè)試

隨著集群規(guī)模的增大，消息傳遞的代價(jià)將會(huì)增加并趨于平緩，下面討論消息傳遞的復(fù)雜度。

假設(shè)推理過(guò)程中需發(fā)送的消息總數(shù)為M。當(dāng)在單節(jié)點(diǎn)上進(jìn)行推理時(shí)，消息的傳遞無(wú)需通過(guò)節(jié)點(diǎn)間的通信來(lái)完成，節(jié)點(diǎn)之間的通信代價(jià)為0。設(shè)集群中有n個(gè)節(jié)點(diǎn)，數(shù)據(jù)均勻分布在這n個(gè)節(jié)點(diǎn)上。假設(shè)傳遞某條消息的兩個(gè)頂點(diǎn)位于不同的節(jié)點(diǎn)，該消息傳遞所帶來(lái)的節(jié)點(diǎn)間的通信代價(jià)為δ。隨著n的增大，數(shù)據(jù)分布將會(huì)更加分散，傳遞消息的兩個(gè)頂點(diǎn)位于不同節(jié)點(diǎn)上的可能性增大。最壞情況下，M條消息均需跨節(jié)點(diǎn)傳遞，那么由消息傳遞所帶來(lái)的通信代價(jià)為M×δ。即隨著集群增大到某一值，由消息傳遞所帶來(lái)的通信代價(jià)達(dá)到極限，其最壞復(fù)雜度為O(M×δ)。

取單節(jié)點(diǎn)與多節(jié)點(diǎn)推理執(zhí)行時(shí)間的比值作為該多節(jié)點(diǎn)推理計(jì)算的相對(duì)加速比，該值可表示集群規(guī)模對(duì)推理性能的影響程度。隨著集群規(guī)模的增大相對(duì)加速化的變化趨勢(shì)趨于平緩，說(shuō)明計(jì)算性能已達(dá)到極限。MPPIE與WebPIE的相對(duì)加速比變化趨勢(shì)如圖10所示。

Fig.10 Relative speedup in clusters with different scales圖10　不同規(guī)模集群上的相對(duì)加速比

當(dāng)集群規(guī)模由1個(gè)節(jié)點(diǎn)增長(zhǎng)到8個(gè)節(jié)點(diǎn)時(shí)，在DBpedia數(shù)據(jù)集上，MPPIE的相對(duì)加速比增加到5.72。在LUBM-1000數(shù)據(jù)集上，MPPIE的相對(duì)加速比增加到9.48。而WebPIE的相對(duì)加速比并不是很明顯，并在大于4個(gè)節(jié)點(diǎn)的集群上，相對(duì)加速比達(dá)到極限。實(shí)驗(yàn)結(jié)果表明，MPPIE具有良好的可伸展性，且明顯優(yōu)于WebPIE。

5.3與YARM工作的性能比較

文獻(xiàn)[12]提出的YARM（yet another reasoning system with MapReduce）是基于MapReduce實(shí)現(xiàn)的語(yǔ)義推理工作，其性能相比于其他基于MapReduce的工作有明顯提高。實(shí)驗(yàn)結(jié)果表明YARM實(shí)驗(yàn)性能相比于Reasoning-Hadoop[28]提高10倍左右。Reasoning-Hadoop與WebPIE同為Urbani等人的工作，不同的是WebPIE將Reasoning-Hadoop的工作擴(kuò)充到OWL Horst規(guī)則集上。在實(shí)驗(yàn)中，僅選用WebPIE的RDFS推理部分進(jìn)行實(shí)驗(yàn)對(duì)比。因此，文獻(xiàn)[12]所對(duì)比的Reasoning-Hadoop與MPPIE選用的WebPIE為同一工作。實(shí)驗(yàn)結(jié)果表明，MPPIE相比于WebPIE平均快30倍以上。文獻(xiàn)[12]集群采用1個(gè)主控制節(jié)點(diǎn)，16個(gè)計(jì)算節(jié)點(diǎn)，且單節(jié)點(diǎn)性能優(yōu)于本工作所用集群中的單節(jié)點(diǎn)性能。但無(wú)論集群規(guī)模多大，并行計(jì)算的性能提升倍數(shù)理論上是與硬件配置無(wú)關(guān)的。顯然，如果在相同的硬件上，MPPIE平均會(huì)比YARM快3倍左右。

6　總結(jié)與展望

RDF圖數(shù)據(jù)本身的特點(diǎn)決定了其更適合于在基于消息傳遞機(jī)制的圖計(jì)算框架下進(jìn)行處理，本文基于消息傳遞機(jī)制提出了一種新的RDFS并行推理框架MPPIE。將RDFS推理規(guī)則的推理過(guò)程映射為圖上兩個(gè)頂點(diǎn)之間添加新邊的過(guò)程，并根據(jù)不同的加邊特點(diǎn)，抽象出不同的推理模型。推理過(guò)程中，以RDF圖上的每個(gè)頂點(diǎn)為獨(dú)立計(jì)算的單元，通過(guò)消息驅(qū)動(dòng)頂點(diǎn)完成推理計(jì)算。標(biāo)準(zhǔn)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，MPPIE推理執(zhí)行速度較WebPIE 快25倍以上，最高可達(dá)58倍。實(shí)驗(yàn)數(shù)據(jù)顯示，MPPIE可伸展性明顯優(yōu)于WebPIE。

下一步工作將從以下兩個(gè)角度展開(kāi)：（1）減少消息傳遞，如優(yōu)化并行計(jì)算過(guò)程，采取更優(yōu)的模式數(shù)據(jù)與實(shí)例數(shù)據(jù)的存儲(chǔ)劃分方案等。（2）目前的工作僅考慮了RDFS推理規(guī)則集，在未來(lái)的工作中，將擴(kuò)展到OWL等表達(dá)能力更豐富的規(guī)則集中。

References:

[1] Schmachtenberg M, Bizer C, Paulheim H. Adoption of the linked data best practices in different topical domains[C]// LNCS 8796: Proceedings of the 13th International Semantic Web Conference, Riva del Garda, Italy, Oct 19-23, 2014. Cham, Switzerland: Springer International Publishing, 2014: 245-260.

[2] Kaoudi Z, Manolescu I. RDF in the clouds: a survey[J]. The VLDB Journal, 2015, 24(1): 67-91.

[3] Weaver J, Hendler J. Parallel materialization of the finite RDFS closure for hundreds of millions of triples[C]//LNCS 5823: Proceedings of the 8th International Semantic Web Conference, Chantilly, USA, Oct 25-29, 2009. Berlin, Heidelberg: Springer, 2009: 682-697.

[4] Urbani J, Kotoulas S, Maassen J, et al. OWL reasoning with WebPIE: calculating the closure of 100 billion triples[C]// LNCS 6088: Proceedings of the 7th Extended Semantic Web Conference, Heraklion, Greece, May 30-Jun 3, 2010. Berlin, Heidelberg: Springer, 2010: 213-227.

[5] Liu Chang, Qi Guilin, Wang Haofen, et al. Large scale fuzzy pD*reasoning using MapReduce[C]//LNCS 7031: Proceedings of the 10th International Semantic Web Conference, Bonn, Germany, Oct 23- 27, 2011. Berlin, Heidelberg: Springer, 2011: 405-420.

[6] Heino N, Pan J Z. RDFS reasoning on massively parallel hardware[C]//LNCS 7649: Proceedings of the 11th International Semantic Web Conference, Boston, USA, Nov 11-15, 2012. Berlin, Heidelberg: Springer, 2012: 133-148.

[7] Peters M, Brink C, Sachweh S, et al. Rule-based reasoning on massively parallel hardware[C]//Proceedings of the 9th International Workshop on Scalable Semantic Web Knowledge Base Systems, Sydney,Australia, Oct 21, 2013: 33-49.

[8] Peters M, Brink C, Sachweh S, et al. Scaling parallel rulebased reasoning[C]//LNCS 8465: Proceedings of the 11th Extended Semantic Web Conference, Anissaras, Greece, May 25-29, 2014. Cham, Switzerland: Springer InternationalPublishing, 2014: 270-285.

[9] Malewicz G, Austern M H, Bik A J C, et al. Pregel: a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, USA, Jun 6-11, 2010. New York, USA:ACM, 2010: 135-146.

[10] Broekstra J, Kampman A, van Harmelen F. Sesame: a generic architecture for storing and querying RDF and RDF schema [C]//LNCS 2342: Proceedings of the 1th International Semantic Web Conference, Sardinia, Italy, Jun 9- 12, 2002. Berlin, Heidelberg: Springer, 2002: 54-68.

[11] Wilkinson K, Sayers C, Kuno H A, et al. Efficient RDF storage and retrieval in Jena2[C]//Proceedings of the 1st International Workshop on Semantic Web and Databases, Berlin, Germany, Sep 7-8, 2003. Berlin, Heidelberg: Springer, 2003: 131-150.

[12] Gu Rong, Wang Fangfang, Yuan Chunfeng, et al. YARM: efficient and scalable semantic reasoning engine based on MapReduce[J]. Chinese Journal of Computers, 2015, 38(1): 74-85.

[13] Forgy C L. Rete: a fast algorithm for the many pattern/many object pattern match problem[J]. Artificial Intelligence, 1982, 19(1): 17-37.

[14] Fang Qiming, Zhao Ying, Yang Guangwen, et al. Scalable distributed ontology reasoning using DHT-based partitioning[C]// LNCS 5367: Proceedings of the 3rd Asian Semantic Web Conference, Bangkok, Thailand, Dec 8- 11, 2008. Berlin, Heidelberg: Springer, 2008: 91-105.

[15] Oren E, Kotoulas S, Anadiotis G, et al. Marvin: distributed reasoning over large-scale semantic Web data[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2009, 7(4): 305-316.

[16] Urbani J, Margara A, Jacobs C, et al. Dynamite: parallel materialization of dynamic RDF data[C]//LNCS 8218: Proceedings of the 12th International Semantic Web Conference, Sydney, Australia, Oct 21- 25, 2013. Berlin, Heidelberg: Springer, 2013: 657-672.

[17] Munoz S, Pérez J, Gutierrez C. Minimal deductive systems for RDF[C]//LNCS 4519: Proceedings of the 4th European Semantic Web Conference, Innsbruck, Austria, Jun 3-7, 2007. Berlin, Heidelberg: Springer, 2007: 53-67.

[18] Kaoudi Z, Miliaraki I, Koubarakis M. RDFS reasoning and query answering on top of DHTs[C]//LNCS 5318: Proceedings of the 7th International Semantic Web Conference, Karlsruhe, Germany, Oct 26-30, 2008. Berlin, Heidelberg: Springer, 2008: 499-516.

[19] Salvadores M, Correndo G, Harris S, et al. The design and implementation of minimal RDFS backward reasoning in 4store[C]//LNCS 6643: Proceedings of the 8th Extended Semantic Web Conference, Heraklion, Greece, May 29-Jun 2, 2011. Berlin, Heidelberg: Springer, 2011: 139-153.

[20] Mu?oz S, Pérez J, Gutierrez C. Simple and efficient minimal RDFS[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2009, 7(3): 220-234.

[21] Husain M, McGlothlin J, Masud M M, et al. Heuristicsbased query processing for large RDF graphs using cloud computing[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(9): 1312-1327.

[22] Urbani J, van Harmelen F, Schlobach S, et al. QueryPIE: backward reasoning for OWL Horst over very large knowledge bases[C]//LNCS 7031: Proceedings of the 10th International Semantic Web Conference, Bonn, Germany, Oct 23-27, 2011. Berlin, Heidelberg: Springer, 2011: 730-745.

[23] Punnoose R, Crainiceanu A, Rapp D. Rya: a scalable RDF triple store for the clouds[C]//Proceedings of the 1st International Workshop on Cloud Intelligence, Istanbul, Turkey, Aug 31, 2012. New York, USA:ACM, 2012: 4.

[24] Hayes P. RDF semantics. W3C Recommendation, 2004.

[25] Valiant L G. A bridging model for parallel computation[J]. Communications of the ACM, 1990, 33(8): 103-111.

[26] Auer S, Bizer C, Kobilarov G, et al. DBpedia: a nucleus for a Web of open data[C]//LNCS 4825: Proceedings of the 6th International Semantic Web Conference, Busan, Korea, Nov 11-15, 2007. Berlin, Heidelberg: Springer, 2007: 722-735.

[27] Guo Yuanbo, Pan Zhengxiang, Heflin J. LUBM: a benchmark for OWL knowledge base systems[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2005, 3(2): 158-182.

[28] Urbani J, Kotoulas S, Oren E, et al. Scalable distributed reasoning using MapReduce[C]//Proceedings of the 8th International Semantic Web Conference, Chantilly, USA, Oct 21-25, 2009. Berlin, Heidelberg: Springer, 2009: 634-649.

附中文參考文獻(xiàn)：

[12]顧榮,王芳芳,袁春風(fēng),等. YARM:基于MapReduce的高效可擴(kuò)展的語(yǔ)義推理引擎[J].計(jì)算機(jī)學(xué)報(bào), 2015, 38(1): 74-85.

LV Xiaoling was born in 1989. She is an M.S. candidate at Tianjin University, and the member of CCF. Her research interests include parallel inference and RDF data management.

呂小玲（1989—），女，河北唐山人，天津大學(xué)碩士研究生，CCF會(huì)員，主要研究領(lǐng)域?yàn)榉植际酵评碛?jì)算，RDF數(shù)據(jù)管理。

WANG Xin was born in 1981. He received the Ph.D. degree from Nankai University in 2009. Now he is an associate professor at Tianjin University, and the senior member of CCF. His research interests include semantic Web data management, graph databases and large-scale knowledge processing.

王鑫（1981—），男，天津人，2009年于南開(kāi)大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)副教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)檎Z(yǔ)義Web數(shù)據(jù)管理，圖數(shù)據(jù)庫(kù)，大規(guī)模知識(shí)處理。

FENG Zhiyong was born in 1965. He received the Ph.D. degree from Tianjin University in 1996. Now he is a professor and Ph.D. supervisor at Tianjin University, and the senior member of CCF. His research interests include knowledge engineering, service technology and security software engineering.

馮志勇（1965—），男，內(nèi)蒙古呼和浩特人，1996年于天津大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)橹R(shí)工程，服務(wù)技術(shù)，安全軟件工程。

RAO Guozheng was born in 1977. He received the Ph.D. degree from Tianjin University in 2009. Now he is an associate professor at Tianjin University, and the member of CCF. His research interests include knowledge engineering and software engineering.

饒國(guó)政（1977—），男，湖北武穴人，2009年于天津大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)副教授，CCF會(huì)員,主要研究領(lǐng)域?yàn)橹R(shí)工程，軟件工程。

ZHANG Xiaowang was born in 1980. He received the Ph.D. degree from Peking University in 2011. Now he is an associate professor at Tianjin University, and the member of CCF. His research interests include artificial intelligence, databases and semantic Web.

張小旺（1980—），男，安徽池州人，2011年于北京大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，?shù)據(jù)庫(kù)，語(yǔ)義網(wǎng)。

XU Guangquan was born in 1979. He received the Ph.D. degree from Tianjin University in 2008. Now he is an associate professor at Tianjin University, and the senior member of CCF. His research interests include trusted computing, security and privacy.

許光全（1979—），男，湖南瀏陽(yáng)人，2008年于天津大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計(jì)算機(jī)學(xué)院副教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭尚庞?jì)算，安全與隱私。

MPPIE: RDFS Parallel Inference Framework Based on Message Passing?

LVXiaoling1,2,WANG Xin1,2,3+, FENG Zhiyong1,2, RAO Guozheng1,2, ZHANG Xiaowang1,2, XU Guangquan1,2
1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China
2. Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin 300072, China
3. General Data Technology Co., Ltd., Tianjin 300384, China

+ Corresponding author: E-mail: wangx@tju.edu.cn

LV Xiaoling, WANG Xin, FENG Zhiyong, et al. MPPIE: RDFS parallel inference framework based on message passing. Journal of Frontiers of Computer Science and Technology, 2016, 10(4): 451-465.

Abstract:Reasoning over semantic data poses a challenge, since large volumes of RDF (resource description framework) data have been published with the rapid development of the Semantic Web. This paper proposes an RDFS (RDF schema) parallel inference framework based on message passing mechanism. The graph structure of RDF data is exploited to abstract inference process to an edge addition model. Vertices execute the parallel inference algorithm, which can send reasoning messages to other vertices to complete inference process. When all derivations are regarded as new edges of initial RDF graph, the computation terminates. MPPIE (message passing parallel inference engine), the RDFS parallel inference framework, is implemented on top of open source framework Giraph. The experimental results on both benchmark dataset LUBM and real world dataset DBpedia show that the performance of the proposed method outperforms WebPIE, the state-of-art semantic scalable inference engine. Furthermore, the proposed method provides good scalability.

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP31

ddoi:10.3778/j.issn.1673-9418.1507072