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

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

1.天津大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津3000722.天津市認(rèn)知計算與應(yīng)用重點實驗室，天津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，饒國政1,2，張小旺1,2，許光全1,2

1.天津大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津300072
2.天津市認(rèn)知計算與應(yīng)用重點實驗室，天津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 (國家自然科學(xué)基金); the National High Technology Research and Develfopment Program of China under Grant No. 2013AA013204 (國家高技術(shù)研究發(fā)展計劃(863計劃)).

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

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

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

1　引言

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

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

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

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

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

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

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

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

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

2　相關(guān)工作

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

（1）閉包計算推理

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

（2）查詢時推理

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

（3）混合推理

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

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

3　基本概念

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

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

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

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

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

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

下面將介紹RDFS推理規(guī)則以及Pregel計算模型。本文方法正是在Pregel模型的基礎(chǔ)上實現(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表示每個三元組中的主語與賓語為字面值或者資源，對推理并無實際意義，因此不進(jìn)行討論。為了簡潔起見，后文將使用表2中謂語的縮寫形式。

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

定義3（推理）給定RDF圖G與規(guī)則集R，根據(jù)R中的某條規(guī)則ri得到G中蘊(yùn)含的三元組集合T的過程稱為推理過程，記作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圖通過迭代應(yīng)用推理規(guī)則得到推理閉包時，推理工作結(jié)束。所得到的推理閉包G*為最終包含所有隱含信息的RDF圖。

3.2Pregel計算模型

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

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

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

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

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

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

對?e∈E，定義：

①p:E→P，返回e上的謂語；

②srcId:E→Idv，返回e的源頂點；

③dstId:E→Idv，返回e的目的頂點。

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

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

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

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

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

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

Fig.1 Pregel computation model圖1　Pregel計算模型

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

4　RDFS并行推理框架MPPIE

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

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

證明由定義3可知，?ri∈R有G├riT。因為G由有限條三元組構(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推理計算是有限的。推理得到的G*為包含G中所有隱含三元組的RDF圖。

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

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

4.1推理抽象模型

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

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

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

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

（4）R7：兩個條件，且生成邊為已存在邊的兩個頂點間的新邊。

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

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

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

Fig.3 Inference model圖3　推理模型

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

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

由圖3的推理模型可以看出，前兩類推理模型較簡單，僅根據(jù)RDF圖中的一條邊，便可進(jìn)行加邊操作，完成推理。實現(xiàn)過程較簡單，故不再討論。對其余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按照圖4的規(guī)則執(zhí)行順序，所有規(guī)則執(zhí)行一遍即可完成推理。

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

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

4.3RDFS并行推理算法

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

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

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

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

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

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

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

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

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

例4圖5展示了傳遞閉包規(guī)則sc的推理過程。傳遞屬性鏈上共有3個頂點。在超步0時所有頂點處于活躍狀態(tài)，只有頂點2同時滿足入邊與出邊上包含sc屬性，因此向需要添加新邊的頂點1發(fā)送消息，激活下一超步中頂點1。在超步1時，頂點1添加新邊(1，sc，3)，并向頂點3發(fā)送消息。在超步2時，所有頂點沒有新邊需要添加，狀態(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ān)信息發(fā)送給需要加邊的頂點；第二次迭代根據(jù)接收到的加邊信息，完成加邊。

個超步能夠完成傳遞閉包推理計算。

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

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

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

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

輸入：消息集合M

輸出：是否停機(jī)

1. For?eo∈v.outEdges do

2. If eo.p∈subP.srcIds then //subP存儲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è)該頂點有N條出邊的屬性存在父屬性，且其中父屬性平均個數(shù)為K個，那么該算法的時間復(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的計算過程，得到(db:Rain_Man, ex:acting, db:Tom_Cruise)與(db: Rain_Man, ex:involving, db:Tom_Cruise)。

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

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

算法3為類型推理算法?；钴S頂點分別判斷出邊屬性上是否包含定義域以及入邊屬性上是否包含值域，若滿足其中之一，則添加對應(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存儲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存儲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è)該頂點包含定義域的屬性個數(shù)平均為d個，且有K個定義域，包含值域的屬性個數(shù)平均為h個，且有N個值域，那么該算法的時間復(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的計算過程，得到(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頂點判斷出邊中的屬性是否包含sc，同時入邊中的屬性是否包含type，如兩者同時滿足，則完成對應(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è)該頂點共有K條入邊和N條出邊，則超步0的時間復(fù)雜度為O(K×N)。在K條入邊中，假設(shè)有k條邊的謂語為type，在N條出邊中有n條邊的謂語為sc，則共會發(fā)送k×n條消息。在超步1的時間復(fù)雜度為O(k×n)。因此，該算法的時間復(fù)雜度為O(K×N+k×n)。

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

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

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

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

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

歸納步驟。假設(shè)第k次推理過程中，?ri∈R有Gk=Gk-1?{t|Gk-1├riT,t∈T,ri∈R}，且Gk-1├riT的推理結(jié)果可靠。當(dāng)?shù)趉+1次添加新邊時，根據(jù)以上算法，以Gk作為輸入數(shù)據(jù)圖。當(dāng)滿足規(guī)則的條件時，添加相應(yīng)的結(jié)論，那么有Gk├riT的推理結(jié)果是可靠的，此時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é)論。同時，按照圖4的規(guī)則執(zhí)行順序進(jìn)行推理時，t可由推理規(guī)則推出，即t∈EM。而假設(shè)為t?EM，矛盾。因此得證?！?/p>

5　實驗

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

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

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

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

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

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

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

5.2實驗結(jié)果及分析

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

5.2.1執(zhí)行性能測試與對比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3與YARM工作的性能比較

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

6　總結(jié)與展望

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

下一步工作將從以下兩個角度展開：（1）減少消息傳遞，如優(yōu)化并行計算過程，采取更優(yōu)的模式數(shù)據(jù)與實例數(shù)據(jù)的存儲劃分方案等。（2）目前的工作僅考慮了RDFS推理規(guī)則集，在未來的工作中，將擴(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ò)展的語義推理引擎[J].計算機(jī)學(xué)報, 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會員，主要研究領(lǐng)域為分布式推理計算，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年于南開大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)副教授，CCF高級會員，主要研究領(lǐng)域為語義Web數(shù)據(jù)管理，圖數(shù)據(jù)庫，大規(guī)模知識處理。

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高級會員，主要研究領(lǐng)域為知識工程，服務(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.

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

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會員，主要研究領(lǐng)域為人工智能，數(shù)據(jù)庫，語義網(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—），男，湖南瀏陽人，2008年于天津大學(xué)獲得博士學(xué)位，現(xiàn)為天津大學(xué)計算機(jī)學(xué)院副教授，CCF高級會員，主要研究領(lǐng)域為可信計算，安全與隱私。

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

中圖分類號：TP31

ddoi:10.3778/j.issn.1673-9418.1507072