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

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

1.天津大學計算機科學與技術學院，天津3000722.天津市認知計算與應用重點實驗室，天津3000723.南大通用數據技術股份有限公司，天津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.天津大學計算機科學與技術學院，天津300072
2.天津市認知計算與應用重點實驗室，天津300072
3.南大通用數據技術股份有限公司，天津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 (國家自然科學基金); the National High Technology Research and Develfopment Program of China under Grant No. 2013AA013204 (國家高技術研究發展計劃(863計劃)).

Received 2015-06,Accepted 2015-08.

CNKI網絡優先出版: 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的快速發展，RDF（resource description framework）語義數據規模呈現爆炸性增長趨勢，大規模語義數據上的推理工作面臨嚴峻挑戰?；谙鬟f機制提出了一種新的RDFS（RDF schema）并行推理方案。利用RDF圖數據結構，建立RDFS推理過程的圖上加邊模型。以頂點為計算中心，根據不同推理模型，向其他頂點傳遞推理消息，完成推理操作。當所有推導出的新三元組以邊的形式加入原RDF圖中時，整個推理過程結束。在基于消息傳遞模型的開源框架Giraph上，實現了RDFS并行推理框架MPPIE（message passing parallel inference engine）。實驗結果表明，在標準數據集LUBM和真實數據集DBpedia上，MPPIE執行速度均比當前性能最好的語義推理引擎WebPIE快一個數量級，且展現了良好的可伸展性。

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

1　引言

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

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

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

本文的主要貢獻如下：

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

（2）提出了一種高效的規則執行機制，減少了推理迭代次數，提高了推理執行效率。

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

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

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

2　相關工作

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

（1）閉包計算推理

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

（2）查詢時推理

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

（3）混合推理

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

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

3　基本概念

RDF是W3C提出的標準數據表示格式，能夠將語義Web中的信息表達成機器理解的語義信息。

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

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

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

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

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

下面將介紹RDFS推理規則以及Pregel計算模型。本文方法正是在Pregel模型的基礎上實現了RDFS推理。

3.1RDFS推理規則

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

Table 1 RDFS inference rules表1　RDFS推理規則集

RDFS規則集中的R1、R4a與R4b表示每個三元組中的主語與賓語為字面值或者資源，對推理并無實際意義，因此不進行討論。為了簡潔起見，后文將使用表2中謂語的縮寫形式。

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

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

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

（1）G0=G

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

當RDF圖通過迭代應用推理規則得到推理閉包時，推理工作結束。所得到的推理閉包G*為最終包含所有隱含信息的RDF圖。

3.2Pregel計算模型

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

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

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

①id:V→Idv，返回v的唯一標識符；

②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存在活躍與停機兩種狀態。在每個超步中，活躍狀態頂點并行執行用戶定義的Compute方法。在每個v上定義如下函數：

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

②voteToHalt()，將頂點狀態置為停機；

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

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

如圖1所示，白色頂點代表活躍狀態頂點，灰色頂點代表停機狀態頂點。

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

每一個接收到消息的活躍狀態頂點將執行一次Compute方法。該方法接收來自前一個超步的消息集合M，完成相應的計算后，可發送消息給下一個超步中的某個計算頂點，也可進行停機操作。當所有頂點都已達到停機狀態，且沒有消息傳遞時，計算停止。

4　RDFS并行推理框架MPPIE

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

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

證明由定義3可知，?ri∈R有G├riT。因為G由有限條三元組構成，且RDFS規則集是完備的，根據定義4，那么必然?α，使得Gα=Gα-1，其中G0=G，Gα=Gα-1?{t|Gα-1├riT,t∈T,ri∈R}。因此，在RDFS規則集R下，有G*=Gα?！?/p>

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

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

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

4.1推理抽象模型

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

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

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

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

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

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

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

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

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規則執行順序優化

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

由圖3的推理模型可以看出，前兩類推理模型較簡單，僅根據RDF圖中的一條邊，便可進行加邊操作，完成推理。實現過程較簡單，故不再討論。對其余4類模型中的規則，依據條件與結論包含的三元組類型的不同，進一步進行如表3所示的分類。

Table 3 Classification of RDFS rules表3　RDFS推理規則分類

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

定理2按照圖4的規則執行順序，所有規則執行一遍即可完成推理。

證明圖4為有向無環圖（directed acyclic graph，DAG），形成了一種拓撲序。在該拓撲序中，R9依賴于R2、R3和R11，R2與R3依賴于R7，同時R7依賴于R5。依據該拓撲序，執行一遍即可完成推理?！?/p>

Fig.4 Execution order of rules圖4　規則執行順序

4.3RDFS并行推理算法

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

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

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

推理模型3傳遞閉包規則的推理

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

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

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

（2）接收消息的頂點根據消息內容添加新邊。此新邊可作為下一輪推理中的條件，因此向此新邊的目的頂點發送消息，使其變為活躍狀態。

（3）重復執行以上兩個步驟，直至所有頂點都達到停機狀態。

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

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

輸入：消息集合M

輸出：是否停機

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 //奇數次超步，加邊

9. For?m∈M do

10.創建新邊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 //偶數次超步，確定新邊信息，并發送消息

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中兩次迭代完成一次加邊過程：第一次迭代確定加邊信息，并把相關信息發送給需要加邊的頂點；第二次迭代根據接收到的加邊信息，完成加邊。

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

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

推理模型4 sp繼承規則的推理

算法2為sp繼承算法。活躍頂點判斷出邊屬性是否有父屬性，若存在父屬性，則以父屬性作為新邊的謂語，完成對應的加邊操作。

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

輸入：消息集合M

輸出：是否停機

1. For?eo∈v.outEdges do

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

3.For?d∈subP.dstIds do

4.創建新邊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繼承規則的推理。假設該頂點有N條出邊的屬性存在父屬性，且其中父屬性平均個數為K個，那么該算法的時間復雜度為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，根據算法2的計算過程，得到(db:Rain_Man, ex:acting, db:Tom_Cruise)與(db: Rain_Man, ex:involving, db:Tom_Cruise)。

推理模型5類型規則的推理

推理模型5包括dom以及ran類型規則。

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

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

輸入：消息集合M

輸出：是否停機

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.創建新邊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.創建新邊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();

該算法在一輪迭代中即可完成新邊的添加，僅判斷邊上的屬性是否包含定義域或者值域。假設該頂點包含定義域的屬性個數平均為d個，且有K個定義域，包含值域的屬性個數平均為h個，且有N個值域，那么該算法的時間復雜度為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，根據算法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繼承規則的推理

算法4為sc繼承算法。活躍頂點判斷出邊中的屬性是否包含sc，同時入邊中的屬性是否包含type，如兩者同時滿足，則完成對應的添加新邊的操作。

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

輸入：消息集合M

輸出：是否停機

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 //接收到新邊信息，進行加邊操作

9.For?m∈M do

10.創建新邊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();

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

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

下面對MPPIE并行推理算法的正確性進行證明。

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

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

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

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

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

假設由所提出的算法推理得到的結果集合為EM，t∈G*但t?EM。若t∈G*，由定義4可知，t必為某一規則的結論。同時，按照圖4的規則執行順序進行推理時，t可由推理規則推出，即t∈EM。而假設為t?EM，矛盾。因此得證?！?/p>

5　實驗

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

5.1實驗環境與數據集

實驗集群由8臺節點構成，由一臺Gigabit以太網交換機連接。每個計算節點配置為Intel?Xeon?CPU E5 @ 2.00 GHz，內存為64 GB，并配置1 TB硬盤。操作系統為64位Ubuntu 12.04 LTS Server，Giraph版本1.1.0，Hadoop版本0.20.203。

實驗選用標準數據集LUBM（Lehigh University Benchmark）[27]和真實數據集DBpedia 3.9進行測試。MPPIE采用與WebPIE相同的數據編碼方案。所有測試數據經過壓縮編碼后，均勻分布在各個計算節點上。

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

DBpedia是從維基百科中抽取出的結構化信息數據，被廣泛應用在語義Web領域相關應用的實驗測試之中。本實驗選取了DBpedia的部分數據，分別為：instance_types_en、mappingbased_properties_en和specific_mappingbased_properties_en數據集。其三元組規模達到42.53×106條。

表4為所選用實驗數據集的詳細信息。

5.2實驗結果及分析

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

5.2.1執行性能測試與對比

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

Table 4 Information of datasets表4　數據集統計信息

Table 5 Comparison of reasoning time表5　推理執行時間對比

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

5.2.2數據規模對推理性能的影響

選取從200到1 000個大學規模不等的LUBM數據集進行數據可伸展性測試。圖6展示了MPPIE與WebPIE各自的推理執行時間。

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

實驗結果表明，隨著LUBM數據集規模的增大，MPPIE推理時間與數據集規?；境示€性增長趨勢。

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

Fig.7 Multiples of reasoning speed圖7　推理執行速度提升倍數

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

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

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

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

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

5.2.3集群規模對推理性能的影響

集群規模從1個節點逐漸增加到8個節點，對MPPIE的推理性能變化進行了評估。數據集選用真實數據集DBpedia和標準數據集LUBM-1000。集群規模對推理性能影響的實驗結果如圖9所示。

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

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

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

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

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

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

當集群規模由1個節點增長到8個節點時，在DBpedia數據集上，MPPIE的相對加速比增加到5.72。在LUBM-1000數據集上，MPPIE的相對加速比增加到9.48。而WebPIE的相對加速比并不是很明顯，并在大于4個節點的集群上，相對加速比達到極限。實驗結果表明，MPPIE具有良好的可伸展性，且明顯優于WebPIE。

5.3與YARM工作的性能比較

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

6　總結與展望

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

下一步工作將從以下兩個角度展開：（1）減少消息傳遞，如優化并行計算過程，采取更優的模式數據與實例數據的存儲劃分方案等。（2）目前的工作僅考慮了RDFS推理規則集，在未來的工作中，將擴展到OWL等表達能力更豐富的規則集中。

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.

附中文參考文獻：

[12]顧榮,王芳芳,袁春風,等. YARM:基于MapReduce的高效可擴展的語義推理引擎[J].計算機學報, 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—），女，河北唐山人，天津大學碩士研究生，CCF會員，主要研究領域為分布式推理計算，RDF數據管理。

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年于南開大學獲得博士學位，現為天津大學副教授，CCF高級會員，主要研究領域為語義Web數據管理，圖數據庫，大規模知識處理。

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—），男，內蒙古呼和浩特人，1996年于天津大學獲得博士學位，現為天津大學教授、博士生導師，CCF高級會員，主要研究領域為知識工程，服務技術，安全軟件工程。

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年于天津大學獲得博士學位，現為天津大學副教授，CCF會員,主要研究領域為知識工程，軟件工程。

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年于北京大學獲得博士學位，現為天津大學副教授，CCF會員，主要研究領域為人工智能，數據庫，語義網。

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年于天津大學獲得博士學位，現為天津大學計算機學院副教授，CCF高級會員，主要研究領域為可信計算，安全與隱私。

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.

文獻標志碼：A

中圖分類號：TP31

ddoi:10.3778/j.issn.1673-9418.1507072