基于Spark的大規(guī)模語義規(guī)則后向鏈推理系統(tǒng)

顧 榮,王善永,郭 晨,袁春風(fēng),黃宜華

(1. 南京大學(xué) 計算機軟件新技術(shù)國家重點實驗室，江蘇 南京 210093； 2. 江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇 南京 210093)

0 引言

1998年，創(chuàng)建萬維網(wǎng)聯(lián)盟(W3C)的蒂姆·伯納斯·李(Tim BernersLee)前瞻性地提出了語義網(wǎng)(semantic web)的概念，希望通過給萬維網(wǎng)上的文檔添加語義(meta data)，使得萬維網(wǎng)成為一個能被計算機理解的通用信息交換媒介。2001年，萬維網(wǎng)聯(lián)盟制定了語義網(wǎng)行動計劃，經(jīng)過十多年的發(fā)展，語義網(wǎng)相關(guān)的理論基礎(chǔ)和技術(shù)規(guī)范逐漸得到完善，符合語義網(wǎng)數(shù)據(jù)模型規(guī)范的語義數(shù)據(jù)快速積累。與此同時，語義技術(shù)不斷地在商業(yè)和研究等領(lǐng)域獲得應(yīng)用。例如，在商業(yè)領(lǐng)域，全球最大的搜索引擎公司Google創(chuàng)建了Google知識圖譜(Google Know-ledge Graph)[1]，使用語義檢索從多種信息源獲取信息，輔助提高Google搜索引擎的搜索質(zhì)量；在醫(yī)學(xué)領(lǐng)域，藥物研究者利用語義技術(shù)來發(fā)現(xiàn)藥物之間的聯(lián)系，輔助藥物開發(fā)。另一方面，語義推理技術(shù)受軟硬件環(huán)境所限，還無法非常高效地推理大規(guī)模語義數(shù)據(jù)，尤其是大規(guī)模并行化的后向鏈語義推理問題還沒有高效的處理方法。

自MapReduce[2]被提出以來，大數(shù)據(jù)處理技術(shù)在存儲、查詢和計算方面都取得了快速的突破性發(fā)展。近幾年來，以Spark[3]為代表的內(nèi)存計算技術(shù)逐漸成熟，其典型的吞吐量大、可靠性高、部署成本低廉等特點，為大規(guī)模數(shù)據(jù)處理提供了可靠的平臺，成為大規(guī)模語義推理的一個新的研究方向。

傳統(tǒng)的后向鏈語義推理是一種單機串行的推理方法，目前已有并行化的后向鏈語義推理方法出現(xiàn)，但大多是支持簡單規(guī)則的弱推理。本文在研究了后向鏈語義推理算法和總結(jié)前人方法的基礎(chǔ)之上，提出了一種基于Spark大數(shù)據(jù)計算平臺的大規(guī)模并行化語義規(guī)則后向鏈推理方法，歸納為以下三個方面。

(1) 針對大規(guī)模推理問題，設(shè)計了實時預(yù)計算本體數(shù)據(jù)閉包的策略，避免了頻繁出現(xiàn)的本體模式在實時推理階段的重復(fù)計算。

(2) 在后向鏈語義推理的過程中設(shè)計了優(yōu)化措施，進一步提高了推理的效率。在逆向推理階段，根據(jù)推理模式在不同層次間的數(shù)據(jù)依賴關(guān)系，盡早剪除無效推理分支。在查詢階段，利用Spark SQL優(yōu)化查詢過程。

(3) 設(shè)計并實現(xiàn)了基于Spark 平臺的大規(guī)模分布式RDFS/OWL后向鏈語義推理系統(tǒng)。

本文第一節(jié)簡要介紹了語義推理的相關(guān)概念；第二節(jié)介紹了后向鏈語義推理的相關(guān)工作；第三節(jié)分析并設(shè)計了后向鏈語義推理的框架流程；第四節(jié)介紹了后向鏈推理的逆向推理和查詢優(yōu)化；第五節(jié)分別在LUBM和DBpedia數(shù)據(jù)集上對系統(tǒng)進行了實驗；最后對全文進行了總結(jié)。

1 背景知識

1.1 語義推理相關(guān)概念

資源描述框架(resource description framework， RDF)是萬維網(wǎng)聯(lián)盟指定的一種靈活且領(lǐng)域無關(guān)的數(shù)據(jù)模型。在使用RDF描述某一特定領(lǐng)域知識時，需要專門定義一套領(lǐng)域相關(guān)的詞匯表，并以某種語言來刻畫詞匯表的語義，這就是RDF Schema[4]，簡稱為RDFS。RDFS在RDF的基礎(chǔ)上，給用戶描述特定領(lǐng)域中的類和屬性提供了標(biāo)準(zhǔn)語義。

RDFS主要包含類、屬性、子類、子屬性、值域和定義域等幾個核心概念，其表達能力相對有限，難以描述萬維網(wǎng)中更加復(fù)雜的結(jié)構(gòu)關(guān)系，于是W3C又制定了描述能力更強的網(wǎng)絡(luò)本體語言O(shè)WL(web ontology language)[5]，提供了更強大的知識表示和推理能力。但同時我們也看到，OWL的每個版本都有幾個精簡子集(OWL Lite，OWL2 QL，OWL2 RL等)，更強的表達能力意味著更高的計算復(fù)雜度，甚至不可判定，即不能夠推理出符合復(fù)雜本體描述語言語義的結(jié)論(比如 OWL Full)。目前已實現(xiàn)的推理引擎中，大部分是實現(xiàn)了對OWL精簡子集的推理或者是僅支持部分語義，OWL Horst就是這樣一種被廣泛接受的具有較強表達能力并能大幅度降低計算復(fù)雜度的規(guī)則集?；贠WL Horst規(guī)則集的推理又稱為pD*推理，涵蓋了所有RDFS蘊涵(RDFS entailment)和D蘊涵(D entailment)，成為語義推理中使用最廣泛的規(guī)則集[6]。OWL Horst規(guī)則集包含了RDFS規(guī)則集。另外OWL Horst規(guī)則集中的某些規(guī)則，例如，規(guī)則rdfp5a: (v,p,w)=>(v, owl: sameAs,v)和rdfp5b: (v,p,w)=>(w, owl: sameAs,w)表達了任意三元組的主語和賓語都是和自身相似的，這對推理應(yīng)用以及用戶來說都沒有意義。在大多數(shù)語義推理系統(tǒng)[6-8]中，都沒有考慮這些沒有意義的規(guī)則的推理。在此，忽略掉RDFS規(guī)則集和OWL Horst規(guī)則集中對推理沒有意義的規(guī)則，把其他規(guī)則列于表1中并重新編號，便于后文對這些規(guī)則的引用，其中規(guī)則R1到規(guī)則R6屬于RDFS規(guī)則集。

表1RDFSOWLHorst規(guī)則集

基于規(guī)則的推理方法又分為前向鏈推理和后向鏈推理[9]。

前向鏈推理就是根據(jù)規(guī)則推導(dǎo)出結(jié)論的過程，在推理發(fā)生時，推理機應(yīng)用規(guī)則到要推理的數(shù)據(jù)上，并把推理結(jié)果存儲到數(shù)據(jù)庫中，一旦推理完成，知識庫將是完整的，即所有隱式數(shù)據(jù)都被顯式化了。這樣，語義推理問題就變成了單純的查詢問題。其缺點也是顯而易見的，隱式知識顯式化要額外占用大量存儲空間，同時數(shù)據(jù)庫也不可能一直保持不變，一旦數(shù)據(jù)庫有新知識插入，那么推理任務(wù)就需要重新做一遍，這是非常耗時的。

后向鏈推理就是反向應(yīng)用規(guī)則，例如，命題A1,A2,…,An→B，要證明B只要去證明規(guī)則的前件A1,A2,…,An。從推理發(fā)生的時機來說，后向鏈推理就是有查詢請求的時候針對這個查詢請求執(zhí)行的推理。后向鏈推理不需要額外存儲隱式知識，它只是在查詢時才挖掘隱含知識，這降低了存儲空間開銷，并且在數(shù)據(jù)庫更新時不需要額外的操作。不過，處理的代價也是顯然的，就是查詢請求因為附帶上推理而造成響應(yīng)時間的延長。后向鏈推理特別適合應(yīng)用在知識庫更新頻繁的場景下。本文主要研究基于Spark的并行化后向鏈推理算法。

1.2 分布式系統(tǒng)Spark介紹

Spark是由UC Berkeley AMPLab實驗室于2009年發(fā)布的分布式內(nèi)存計算框架，它是Berkeley Data Analysis Stack(BDAS)中的核心項目。RDD[3](resilient distributed dataset)是Spark中的核心數(shù)據(jù)結(jié)構(gòu)。Spark定義了RDD上的三種操作： 轉(zhuǎn)換(transformation)、動作(action)和控制(control)。轉(zhuǎn)換包括map、join、filter、union等Spark內(nèi)置函數(shù)，它從一個RDD計算出另一個RDD，比如模式匹配操作相當(dāng)于RDD上filter操作，合并兩個集合的操作相當(dāng)于RDD上的union操作，而把一個數(shù)據(jù)集合內(nèi)的每一個元素映射成另一種形式的操作，相當(dāng)于RDD上的map操作。

RDD上的動作包含reduce、count、collect、saveAsTextFile等Spark內(nèi)置函數(shù)，比如合并一個集合里所有元素的操作相當(dāng)于RDD上的reduce操作，統(tǒng)計一個數(shù)據(jù)集合里有多少個元素的操作相當(dāng)于RDD上的count操作，把數(shù)據(jù)保存到存儲系統(tǒng)的操作相當(dāng)于RDD上的saveAsTextFile操作。RDD上的轉(zhuǎn)換仍然得到RDD，而RDD上的動作是返回一個本地數(shù)據(jù)類型給Driver進程，或者把RDD寫入文件系統(tǒng)。控制操作包括cache、persist、checkpoint等Spark內(nèi)置函數(shù)，控制操作不改變RDD,也不返回本地數(shù)據(jù)類型，而是緩存RDD、設(shè)置檢查點等，用于Spark程序的性能調(diào)優(yōu)。

2 相關(guān)工作

前向鏈推理在RDF數(shù)據(jù)更新后需要重新計算，計算整個閉包時間較長，但在查詢時不需要查詢以外的開銷；而后向鏈語義推理是一種推理發(fā)生在查詢時的推理方法，對RDF數(shù)據(jù)更新不敏感，但增加了查詢的時間開銷。隨著RDF數(shù)據(jù)增長速度越來越快，前向鏈語義推理的弊端逐漸顯現(xiàn)出來，后向鏈語義推理開始進入人們的視野。RDF數(shù)據(jù)管理系統(tǒng)Jena[10]使用一個類似于Prolog引擎的邏輯程序來提供對后向鏈語義推理的支持，允許自定義推理規(guī)則集，但功能較弱，單機的架構(gòu)難以處理大規(guī)模RDF數(shù)據(jù)。AllegroGraph[11]是一個商用的大規(guī)模圖數(shù)據(jù)庫，它的后向鏈語義推理引擎RDFS++支持RDFS規(guī)則集和OWL規(guī)則集中的部分規(guī)則，并且有較高的性能表現(xiàn)。但為了提高性能，它犧牲了推理的完備性和對規(guī)則集的完整支持。Virtuoso[12]是一種基于列存儲系統(tǒng)的后向鏈語義推理系統(tǒng)，但該系統(tǒng)沒有進行特殊的優(yōu)化，并且只支持RDFS和OWL的少部分規(guī)則。

文獻[13]和文獻[14]提出了一種對規(guī)則條件的執(zhí)行次序進行優(yōu)化選擇，從而提高推理效率的方法。文獻[15]提出了OLDT，這是一種避免推理樹過深和避免規(guī)則擴展陷入死循環(huán)的方法。文獻[16]和文獻[17]提出了查詢策略選擇函數(shù)，并綜合了規(guī)則條件執(zhí)行次序的優(yōu)化方法[13-14]、OLDT[15]和sameAs 優(yōu)化方法，提出了一種優(yōu)化的后向鏈推理方法。該方法是一種在單機上遞歸執(zhí)行的方法，不能處理大規(guī)模RDF數(shù)據(jù)。文獻[18]提出了一種RDF數(shù)據(jù)存儲與查詢系統(tǒng)，支持后向鏈推理，但只支持rdfs: subClassOf、rdfs: subPropertyOf和owl: EquivalentProperty三種語義的推理。文獻[7]提出了QueryPIE，這是一種基于高性能計算平臺DAS4 的后向鏈語義推理方法，它通過對推理樹的剪枝和把RDF數(shù)據(jù)映射為數(shù)字ID來加速推理過程，支持OWL Horst規(guī)則集的后向鏈推理，具有很高的處理能力。但是，該方法存在兩個方面的不足： (1)高性能硬件加速不具有普適性；(2)把大規(guī)模RDF數(shù)據(jù)映射為數(shù)字ID存在著更新數(shù)據(jù)開銷大和推理前后的RDF數(shù)據(jù)與數(shù)字ID相互映射開銷大的問題。

3 后向鏈語義推理分析和系統(tǒng)設(shè)計

3.1 后向鏈語義推理過程分析

后向鏈語義推理是一種目標(biāo)驅(qū)動的推理方式。表2給出了一個簡單推理規(guī)則集的例子，該規(guī)則集包含三條規(guī)則，定義了子屬性關(guān)系、對稱關(guān)系和傳遞關(guān)系。

表2 簡單規(guī)則集舉例

假設(shè)要求解Lliy為誰工作，推理查詢模式是(Lily， worksFor，？who)，記為Q，推理規(guī)則使用表2的簡單規(guī)則集。除了直接到知識庫里查找符合結(jié)論的三元組之外，還要考慮應(yīng)用規(guī)則推導(dǎo)出結(jié)論。首先觀察規(guī)則，發(fā)現(xiàn)Q比規(guī)則R4的結(jié)論更具體，即Q是將R4結(jié)論三元組中的若干變量替換成具體RDF數(shù)據(jù)得到的。所以在推理過程中，有可能通過規(guī)則R4推理出三元組T，使得T比Q更具體。于是，將Q的主語、謂語和賓語與規(guī)則R4的結(jié)論一一對應(yīng)，并實例化規(guī)則R4 的條件(即把變量s替換為“Lily”，把變量q替換為“worksFor”)，就能得到兩條新的三元組模式(Lily,？p,？who)、(？p, rdfs: subPropertyOf, worksFor)，這兩條三元組模式又作為新的推理查詢，同時滿足這兩條推理查詢模式的三元組將應(yīng)用規(guī)則R4推導(dǎo)出滿足模式Q的結(jié)論。同理，規(guī)則O3和O4也能用來推導(dǎo)出三元組模式Q。使用表2中給出的規(guī)則集進行三元組模式Q的推理，其過程可以用一顆推理樹來表示(圖1)。

圖1中，推理樹中根節(jié)點表示推理模式Q，圓角矩形框代表所運用的規(guī)則，直角矩形框代表新的推理查詢模式。每條三元組模式下應(yīng)用的規(guī)則屬于“或”的關(guān)系，而每條規(guī)則下展開的三元組模式屬于“與”的關(guān)系。這樣每個推理模式從上至下依次展開，對于每個矩形節(jié)點的三元組模式，將對知識庫進行查詢，查詢的結(jié)果從下往上使用規(guī)則推導(dǎo)出上層結(jié)論。在最頂層得到的推理結(jié)果就是最終的查詢結(jié)果。

圖1 簡單規(guī)則集上的推理樹示例

3.2 后向鏈語義推理的并行化和系統(tǒng)設(shè)計

通過3.1節(jié)對后向鏈推理的過程分析，我們發(fā)現(xiàn)整個算法可以分成三個主要階段： (1)逆向推理(推理模式擴展); (2)查詢(查詢模式匹配); (3)正向推理(根據(jù)規(guī)則合并結(jié)果集)。

在逆向推理階段，推理樹被自上而下創(chuàng)建(圖1)。逆向推理找出能夠證明結(jié)論的隱式證據(jù)，這一過程根據(jù)給定的規(guī)則集擴展出新的推理模式，不需要操作大規(guī)模語義數(shù)據(jù)。在查詢階段，查詢模式在大規(guī)模語義數(shù)據(jù)上匹配滿足條件的三元組。這一階段需要全局地過濾語義數(shù)據(jù)，時間開銷比較大。在正向推理階段，規(guī)則應(yīng)用在查詢結(jié)果集上，從而推導(dǎo)出結(jié)論。

結(jié)合對后向鏈語義推理過程的分析，我們把后向鏈語義推理中的查詢過程用RDD上的filter操作來實現(xiàn)，由各個計算節(jié)點并行計算，加快查詢過程。假設(shè)語義數(shù)據(jù)已經(jīng)載入內(nèi)存并以RDD表示，圖2演示了RDD上的查詢過程。

圖2 用RDD表示的查詢過程

查詢完成之后，需要在多個查詢結(jié)果上應(yīng)用規(guī)則推導(dǎo)結(jié)論，用Spark的RDD模型來刻畫的話，就是在多個結(jié)果RDD上使用join操作，如圖3所示。

圖3 用RDD表示的正向推理過程

結(jié)合Spark大數(shù)據(jù)計算平臺的特點，本文提出了大規(guī)模并行化后向鏈語義推理方案，如圖4所示。系統(tǒng)架構(gòu)圖中主要包含逆向推理層、存儲與查詢層、正向推理層。逆向推理層實現(xiàn)規(guī)則擴展，在Driver端串行執(zhí)行，其中圓角矩形表示規(guī)則，直角矩形表示三元組模式，帶陰影的直角矩形是本體三元組模式。存儲與查詢層實現(xiàn)存儲與查詢優(yōu)化，存儲上采用RDD的高級封裝形式DataFrame，虛線框表示DataFrame，查詢使用Spark SQL模塊加速。正向推理層實現(xiàn)在查詢結(jié)果上推導(dǎo)結(jié)論，根據(jù)應(yīng)用的規(guī)則不同，分別使用了不同的優(yōu)化方法。

圖4 大規(guī)模并行化后向鏈語義推理系統(tǒng)架構(gòu)

4 逆向推理與查詢優(yōu)化

4.1 本體數(shù)據(jù)閉包共享

表1中，不管是RDFS還是OWL規(guī)則集，每條規(guī)則的條件總是包含至少一條本體三元組輸入，因此本體三元組模式在規(guī)則擴展的推理樹里會頻繁出現(xiàn)。另一方面，本體術(shù)語詞匯來自于本體描述語言，數(shù)量有限，這限制了本體模式的數(shù)量，因此在大量的后向鏈推理請求中，本體模式會被重復(fù)推理。所以本文提出了共享本體推理查詢結(jié)果的優(yōu)化方法，以此降低推理查詢時的計算開銷。

4.1.1 RDFS規(guī)則集上的本體數(shù)據(jù)閉包算法

RDFS規(guī)則集中，規(guī)則R3推導(dǎo)出的結(jié)論可以作為規(guī)則R4的條件，而規(guī)則R4推導(dǎo)出的結(jié)論又可能是規(guī)則R1和規(guī)則R2的條件，分析RDFS規(guī)則間的這種依賴關(guān)系可以發(fā)現(xiàn)，推理結(jié)論是本體三元組的規(guī)則，規(guī)則條件都是本體三元組，因此RDFS本體三元組的推理不依賴于實例數(shù)據(jù)，在本體數(shù)據(jù)上即可完成。RDFS本體數(shù)據(jù)閉包的計算用偽代碼描述見算法1。

算法1 RDFSOntologyClosure輸入:本體三元組onto_triples輸出:本體三元組閉包rdfs_closuresc=onto_triples.filter(t=>t._2.equals(“rdfs:subClas-sOf”)) .map(t=>(t._1,t._3))DO{ inferredTriples=sc.map(t=>(t._2,t._1)) .join(sc) .filter(t=>t._2._1!=t._2._2) .map(t=>(t._2._1,t._2._2)) sc=sc.union(inferredTriples) .distinct}WHILE(schaschanged)//rdfs:subPropertyOf的計算和以上類似rdfs_closure=onto_triples.union(sc).union(sp)RETURNrdfs_closure

4.1.2 RDFS規(guī)則集上的本體數(shù)據(jù)閉包算法

從表1中OWL Horst規(guī)則集來看，OWL Horst規(guī)則集的依賴關(guān)系比RDFS規(guī)則集復(fù)雜得多，不存在一個拓撲序，并且本體三元組的推理涉及實例數(shù)據(jù)，因此不能用RDFS本體數(shù)據(jù)閉包的計算方法。在OWL本體數(shù)據(jù)閉包的計算方法中，用所有的本體三元組模式做推理查詢，這時候本體數(shù)據(jù)閉包可能缺失一些隱式的本體三元組，導(dǎo)致推理結(jié)果不完整。此時，把推理出來的本體三元組模式插入到本體閉包中，重新用本體三元組模式做推理查詢，并把推理結(jié)果插入到本體閉包中，如此循環(huán)，直到推理不出更多新的本體三元組，本體數(shù)據(jù)閉包就完整地計算出來了[19]。OWL本體數(shù)據(jù)閉包的計算方法用偽代碼描述如下。

算法2 OWLOntologyClosure輸入:Ontologytriples:OTKnowledgeBase:KB //instancetriplesOntologytriplepatterns:Qs輸出:Ontologyclosure:owl_closureDO Inferred-triples={} FORqINQsDO Inferred-triples+=Backward-chaining-reasoner(q) END OT.insertAll(Inferred-triples)WHILEInferred-triplesisnotemptyowl_closure=OTRETURNowl_closure

4.2 使用本體數(shù)據(jù)閉包優(yōu)化的規(guī)則擴展過程

根據(jù)RDFS規(guī)則的輸出中謂語是否是rdf: type、本體詞匯或可綁定變量，可以把RDFS規(guī)則分為以下三類。

(1) 輸出三元組的謂語是本體詞匯的規(guī)則： R3、R6。

(2) 輸出三元組的謂語是rdf: type的規(guī)則： R1、R2、R5。

(3) 輸出三元組的謂語是可綁定變量的規(guī)則： R4。

在接下來的分析中，將引用4.1.1節(jié)計算的RDFS本體數(shù)據(jù)閉包rdfs_closure，并記為G1。

對于第一類規(guī)則，即規(guī)則R3 和R6，在本體三元組數(shù)據(jù)閉包已經(jīng)計算出來的情況下，推理樹生長到本體三元組模式的節(jié)點，可以直接從本體閉包中讀取本體三元組模式的推理結(jié)果，因而推理樹在擴展到本體三元組模式的節(jié)點時不需要繼續(xù)擴展。

對于第二類規(guī)則，以規(guī)則R1： (p, rdfs: domain,x)&(s,p,o)=>(s, rdf: type,x)為例，根據(jù)推理模式的主語、謂語、賓語是已知還是可綁定變量，分為七種組合情況。這里，對于主、謂、賓都是自由變量的完全查詢模式不予討論。其原因一是沒有限制條件的查詢沒有實際意義，二是這將導(dǎo)致后向鏈推理引擎推理出所有蘊涵知識，相當(dāng)于做了前向鏈推理的事情，失去了后向鏈推理的意義。實際上，在應(yīng)用規(guī)則擴展查詢的過程中，也不會產(chǎn)生主、謂、賓全都是變量的模式(規(guī)則擴展過程中被優(yōu)化掉了)。所以在本文中不再討論推理模式中主、謂、賓都是變量的情況。

(1) 推理模式中只有主語為變量(?subj, pred, obj)。這種情況下，將推理模式帶入規(guī)則R1，發(fā)現(xiàn)推理模式的謂語pred一定是rdf: type，否則無法由規(guī)則R1推出。在謂語是rdf: type的情況下，規(guī)則R1可擴展該查詢，得到兩個新的推理模式(?p, rdfs: domain, obj)和(?subj, ?p, ?o)。這些新的推理模式作為推理樹的分支，即推理樹在該分支生長，生成的分支也就是新的推理模式，可以繼續(xù)遞歸地做推理查詢。

(2) 推理模式只有謂語為變量(subj, ?pred, obj)。這種情況下，規(guī)則R1推導(dǎo)的結(jié)論里謂語是rdf: type，即如果規(guī)則R1對該推理模式有貢獻，貢獻一定是(subj, rdf: type, obj)。而(?p, rdfs: domain, obj)&(subj, ?p, ?o)=>(subj, rdf: type, obj)，本體三元組模式(?p, rdfs: domain, obj)在本體閉包G1中找出所有?p的集合p_set，對每一個p∈p_set，有新的推理模式(subj, p, ?o)，這些新模式作為推理樹的分支，即推理樹在該分支生長，生成的每個分支繼續(xù)遞歸地做推理查詢。

(3) 推理模式只有賓語為變量(subj, pred, ?obj)。這種情況下，推理模式的謂語pred等于rdf: type，否則規(guī)則R1對該推理模式?jīng)]有貢獻。推理模式代入規(guī)則R1后，有： (subj, pred, ?obj)<=(?p, rdfs: domain, ?obj)&(subj, ?p, ?o)。對這兩個新的推理模式的處理有兩種方式，一種是綁定變量方式，另一種是自由變量方式。

(4) 推理模式中主語和謂語都是變量(?subj, ?pred, obj)。這種情況下，應(yīng)用規(guī)則R1把推理模式的謂語綁定為rdf: type，推理模式變?yōu)??subj, rdf: type, obj)，即退化為(1)中的情況。

(5) 推理模式中主語和賓語都是變量(?subj, pred, ?obj)。這種情況下，推理模式的謂語pred一定等于rdf: type，否則不能由規(guī)則R1推導(dǎo)出來。對每一個pi,rdfs: domain,obji∈G1(pi, rdfs: domain, obji)∈G1，代入規(guī)則R1后，有(?subj,pi,?o)=>(?subj,rdf: type,obji)(?subj, pi,?o)=>(?subj, rdf: type,obji)，即在該節(jié)點將產(chǎn)生新的分支(?subj,pi,?o)(?subj, pi, ?o)。

(6) 推理模式中謂語和賓語都是變量(subj, ?pred, ?obj)。這種情況下，綁定推理模式中的謂語“?pred”為rdf: type，推理模式變?yōu)?subj, rdf: type, ?obj)，即退化為(3)中的情況。

(7) 推理模式是無參三元組模式(subj， pred， obj)。這種情況下，推理模式謂語pred一定等于rdf: type，否則規(guī)則R1不能推導(dǎo)出該模式。代入規(guī)則R1后，有(?p, rdfs: domain, obj)&(subj, ?

p, ?o)=>(subj, rdf: type, obj)。對于每一個pi,rdfs: domain,obj∈G1(pi, rdfs: domain, obj)∈G1，有(subj,pi,?o)=>(subj,rdf: type,obj)(subj,pi,?o)=>(subj,rdf: type,obj)，其中，(subj,pi,?o)(subj,pi,?o)是推理樹的新分支。

對于第三類規(guī)則，即規(guī)則R4： (s,p,o)&(p, rdfs: subPropertyOf,q)=>(s,q,o)，規(guī)則的結(jié)論是完全推理模式，與任意推理模式兼容。三元組推理模式pattern根據(jù)主語、謂語和賓語是已知量還是自由變量，可以分為七種情況進行類似的處理： 推理模式中只有主語為變量(?subj, pred, obj)、推理模式中只有謂語為變量(subj, ?pred, obj)、推理模式中只有賓語為變量(subj, pred, ?obj)、推理模式中主語和謂語都是變量(?subj, ?pred, obj)、推理模式中主語和賓語都是變量(?subj, pred, ?obj)、推理模式中謂語和賓語都是變量(subj, ?pred, ?obj)、推理模式是無參三元組模式(subj， pred， obj)。

4.3 快速剪枝優(yōu)化

在一個三元組模式擴展的推理樹中，同一條分支上的不同節(jié)點可能擁有相同的變量，同一個變量在不同節(jié)點上必須滿足不同的三元組模式。如果不同節(jié)點上的三元組模式推理出的該變量集合沒有交集，那么該分支不會產(chǎn)生最終的有效推理結(jié)果。例如，對于圖1中最深層的規(guī)則O3擴展出的兩個新的三元組模式(?p, rdf: type, owl: SymmetricProperty)和(?who, ?p, Lliy)。其中的變量?p 和 ?who 與上層規(guī)則R4的兩個條件模式(?p, rdfs: subPropertyOf, worksFor)和(Lyli, ?p, ?who)中的變量?p 和 ?who指代相同。如果某兩個模式中的同一變量的解空間沒有交集，則該分支的推理結(jié)果也是空集。

對于較為容易判斷的本體三元組模式(?p, rdfs: subPropertyOf, worksFor)和(?p, rdf: type, owl: SymmetricProperty)，如果推理中能快速判斷出沒有同時滿足這兩個模式的RDF數(shù)據(jù)項，那么該推理分支就可以直接丟棄，省去了進一步的推理計算過程。實際上，在4.2節(jié)基于本體閉包的規(guī)則擴展優(yōu)化基礎(chǔ)上，對于同一推理分支上的兩個本體三元組模式，可以快速判斷結(jié)果集是否有交集。利用這一優(yōu)化方案能夠快速剔除一些無效的計算分支。

4.4 基于Spark SQL的查詢優(yōu)化

針對后向鏈語義推理中涉及多次查詢，并且正向推理階段需要在查詢結(jié)果上做連接的需求，本節(jié)提出一種基于底層分布式計算框架Spark的RDF數(shù)據(jù)存儲方案和使用Spark SQL進行查詢的執(zhí)行方案。

Spark SQL[20]是Apache Spark的一個組件，使得用戶可以在Spark上進行數(shù)據(jù)的關(guān)系操作。Spark SQL對RDD進行了更高級的封裝，稱為DataFrame，用來支持數(shù)據(jù)的存儲和操作。另外在查詢作業(yè)的各個階段，Spark SQL也設(shè)計了若干優(yōu)化方式提升查詢作業(yè)的性能。

Spark的核心數(shù)據(jù)結(jié)構(gòu)是RDD，RDD可以看作是Java對象的集合，Spark并不能看到Java對象內(nèi)部的細節(jié)。與RDD類似，DataFrame也是一個分布式數(shù)據(jù)容器，但是DataFrame內(nèi)部除了數(shù)據(jù)以外，還維護了數(shù)據(jù)的結(jié)構(gòu)信息，即Schema，兩者組合使得DataFrame看起來更像傳統(tǒng)數(shù)據(jù)庫中的一張二維表。這兩種組織結(jié)構(gòu)的區(qū)別見圖5。

圖5 RDD與DataFrame結(jié)構(gòu)的差異

由于Spark對RDD元素的內(nèi)部細節(jié)一無所知，所以RDD包含的數(shù)據(jù)進入內(nèi)存(觸發(fā)計算或者cache)時是按行存儲的。而DataFrame的數(shù)據(jù)進入內(nèi)存時，是按列存儲的，這樣做有兩個好處。

(1) Spark可以根據(jù)DataFrame中列的類型信息，用更有針對性的結(jié)構(gòu)存儲每列的數(shù)據(jù)，有利于壓縮數(shù)據(jù)以提升操作性能。Spark SQL的查詢優(yōu)化器還能對查詢列的類型進行針對性的優(yōu)化。

(2) 在行存儲的情況下，數(shù)據(jù)的每一行會生成一個Java對象;在大數(shù)據(jù)的情況下，行存儲會生成數(shù)量繁多的小對象，對Java GC造成巨大壓力。而使用列存儲的方式，每列數(shù)據(jù)只會生成一個或幾個對象(在大數(shù)據(jù)情況下為了防止單個對象過大，每列會生成幾個對象)，對象的數(shù)目顯著降低，Java GC的壓力也會隨之減輕。

此外，Spark SQL在查詢作業(yè)的不同階段設(shè)計了若干優(yōu)化方式。謂詞下推是一個使得過濾操作提前進行的優(yōu)化措施。由于DataFrame也具有RDD惰性計算的特性，這就使得Spark SQL可以分析整個查詢作業(yè)，將過濾操作(filter等)盡可能前推，甚至可以前推到讀取數(shù)據(jù)時，從而有效地減少參加運算和傳輸?shù)臄?shù)據(jù)量。列剪枝也是一種精簡數(shù)據(jù)量的技術(shù)，由于DataFrame是按列組織的，同時具有Schema信息，使得Spark SQL可以分析查詢作業(yè)，精簡掉查詢過程中不需要的列,減少參與運算和傳輸?shù)臄?shù)據(jù)量。

由于Spark SQL和DataFrame的上述優(yōu)勢，本文將后向鏈語義推理的查詢和正向推理階段表達成一系列對DataFrame的查詢作業(yè)。

本系統(tǒng)將經(jīng)過規(guī)則作用擴展出的若干相互之間為“與”關(guān)系的三元組包裝為一個請求。在3.1節(jié)的例子中，三元組(Lily，？p，？who)和(？p， rdfs: subPropertyOf， worksFor)是被規(guī)則R4作用擴展出來的，于是會被包裝為一個請求。當(dāng)請求中的所有三元組都不能利用規(guī)則進行擴展時，就應(yīng)觸發(fā)查詢與正向推理。若三元組中存在本體術(shù)語詞，則直接在本體閉包中查詢，否則應(yīng)在實例數(shù)據(jù)中查詢。

得到每個請求的結(jié)果后，結(jié)果就可以沿著推理樹向上前進，與其他分支產(chǎn)生的結(jié)果進行合并。如此循環(huán)往復(fù)，直到所有結(jié)果前進到樹根，原問題得解。

基于Spark SQL的查詢過程用偽代碼描述如下。

算法3 基于SparkSQL的查詢過程輸入:一個查詢請求:query:Set輸出:結(jié)果DataFrame:resres=newDataFramequery.foreach(triple=>{ sql=GenerateSQL(triple) tmp=sqlContest.execute(sql) res=connectAccordingToRule(res,tmp)})RETURNres

5 性能評估

5.1 實驗環(huán)境與設(shè)置

本節(jié)我們從推理時間、數(shù)據(jù)可擴展性和計算節(jié)點可擴展性三個方面對本文提出的系統(tǒng)進行評估,實驗使用的集群節(jié)點配置如表3所示。

表3 計算節(jié)點配置表

5.2 實驗環(huán)境與設(shè)置

5.2.1 合成數(shù)據(jù)集及測試樣例

The Lehigh University Benchmark(LUBM)[21]提供標(biāo)準(zhǔn)的本體數(shù)據(jù)集和用于生成實例數(shù)據(jù)集的數(shù)據(jù)生成工具，并且包含一組標(biāo)準(zhǔn)查詢測試樣例，可用于測試查詢性能也可以用于測試后向鏈語義推理性能。使用LUBM可以生成任意規(guī)模的模擬數(shù)據(jù)集，給語義推理系統(tǒng)的性能測試帶來了方便。

實驗中使用了LUBM-100、LUBM-200、LUBM-400、LUBM-600、LUBM-800、LUBM-1000六種規(guī)模不同的LUBM數(shù)據(jù)，分別包含13 million、25 million、50 million、78 million、100 million、133 million條三元組。下文將此數(shù)據(jù)集簡稱為LUBM數(shù)據(jù)集。實驗使用LUBM Benchmark提供的14條標(biāo)準(zhǔn)查詢樣例進行測試。

5.2.2 真實數(shù)據(jù)集及測試樣例

DBpedia[22]是在社區(qū)共同努力下從Wikipedia抽取的結(jié)構(gòu)化數(shù)據(jù)集，數(shù)據(jù)來源多領(lǐng)域、多語言，允許用戶從中查詢維基百科的數(shù)據(jù)以及從維基百科連接到的其他數(shù)據(jù)源。本文實驗使用DBpedia英文版數(shù)據(jù)，包含DBpedia-50、DBpedia-100、DBpedia-150和DBpedia-200四組數(shù)據(jù)，分別包含50 million、100 million、150 million和200 million條三元組。下文將此數(shù)據(jù)集簡稱為DBpedia數(shù)據(jù)集。本文篩選了四個用于DBpedia測試的樣例，包含兩個簡單推理模式和兩個復(fù)雜推理模式。DBpQ1用于推理Alanthurai所屬的國家；DBpQ2用于推理英文DBpedia中所有的游戲；DBpQ3用于推理意大利制作的所有電影；DBpQ4用于推理所有國家及其首都。

5.3 實驗環(huán)境與設(shè)置

5.3.1 推理性能測試

性能實驗使用的Spark和HDFS集群由一個主節(jié)點和12個計算節(jié)點組成，每個節(jié)點的軟件和硬件配置見表3。本系統(tǒng)在LUBM數(shù)據(jù)集上的推理查詢性能實驗結(jié)果如圖6和圖7所示。

圖6 在LUBM數(shù)據(jù)集上基于RDFS規(guī)則集的推理性能

由圖6和圖7所示的實驗數(shù)據(jù)可見，在兩個規(guī)則集上本系統(tǒng)的性能表現(xiàn)差異不大。在一千萬條LUBM數(shù)據(jù)規(guī)模上，簡單推理查詢(如Q1、Q6、Q10、Q11、Q14)都可以在幾百毫秒的時間級別上完成推理，復(fù)雜的推理查詢(如Q2、Q4、Q9等)都可以在秒級完成；在一億三千萬條LUBM數(shù)據(jù)規(guī)模上，推理時間有所升高，但也都可以在32s內(nèi)完成推理。

本系統(tǒng)在DBpedia數(shù)據(jù)集上的推理查詢性能實驗結(jié)果如圖8和圖9所示。

由實驗數(shù)據(jù)可見，本系統(tǒng)在推理實驗選取的四個推理模式時，可以在一兩億條三元組的真實數(shù)據(jù)集上完成秒級的后向鏈推理。

觀察兩個規(guī)則集下處理推理請求的時間，發(fā)現(xiàn)處理基于OWL規(guī)則集的推理請求要比基于RDFS規(guī)則集的推理請求更為耗時。這是因為OWL后向鏈推理是在RDFS后向鏈推理的基礎(chǔ)上提出的，不僅完全包含RDFS規(guī)則集，而且OWL規(guī)則集的復(fù)雜度就像其描述能力一樣比RDFS規(guī)則集高出許多。但是在實驗中發(fā)現(xiàn)，OWL的后向鏈推理性能與RDFS相比雖有差異，但并沒有差太多。原因有兩點，一是數(shù)據(jù)集的復(fù)雜度不高，二是OWL規(guī)則集比RDFS規(guī)則集多出來的規(guī)則沒有像RDFS規(guī)則集那么廣泛地被應(yīng)用。

對比LUBM數(shù)據(jù)集和DBpedia數(shù)據(jù)集上的實驗后發(fā)現(xiàn)，基于Spark的并行化語義后向鏈推理系統(tǒng)不管是在合成數(shù)據(jù)集上還是在真實數(shù)據(jù)集上，都能在幾秒到幾十秒的時間內(nèi)完成后向鏈語義推理，表現(xiàn)出了很好的推理性能。對于數(shù)據(jù)頻繁更新的知識庫來說，后向鏈語義推理每次幾十秒的開銷相對于前向鏈推理動輒幾十分鐘甚至幾個小時[23]來說進步很大。

圖7 在LUBM數(shù)據(jù)集上基于OWL規(guī)則集的推理性能

圖8 在DBpedia數(shù)據(jù)集上基于RDFS規(guī)則集的推理性能

圖9 在DBpedia數(shù)據(jù)集上基于OWL規(guī)則集的推理性能

5.3.2 數(shù)據(jù)可擴展性測試

一個設(shè)計良好的大規(guī)模語義推理系統(tǒng)應(yīng)當(dāng)能夠處理各種規(guī)模的數(shù)據(jù)。為了考察系統(tǒng)的數(shù)據(jù)可擴展性，在保證計算集群的環(huán)境配置不變的情況下，測試本系統(tǒng)在不同數(shù)據(jù)規(guī)模下的執(zhí)行時間。同時，語義推理不只對規(guī)則復(fù)雜度敏感，數(shù)據(jù)的復(fù)雜度也會對結(jié)果產(chǎn)生影響。實驗中選用的LUBM大學(xué)數(shù)據(jù)由工具生成，數(shù)據(jù)復(fù)雜度不隨規(guī)模變化。下面，本系統(tǒng)會基于RDFS和OWL規(guī)則集，分別進行數(shù)據(jù)擴展性實驗。在LUBM數(shù)據(jù)集上，本系統(tǒng)的數(shù)據(jù)可擴展性如圖10和圖11所示。

圖10 數(shù)據(jù)擴展性實驗(LUBM+RDFS)

圖11 數(shù)據(jù)擴展性實驗(LUBM+OWL)

實驗數(shù)據(jù)顯示，本系統(tǒng)在兩個規(guī)則集下再次表現(xiàn)出了類似的趨勢。在LUBM benchmark的14條標(biāo)準(zhǔn)查詢里，Q2和Q9是非常復(fù)雜的推理模式，分別包含了六條簡單推理模式，在折線圖中可以看出，這兩條查詢隨著數(shù)據(jù)規(guī)模變大，推理時間明顯增長。Q7和Q8屬于中等難度的推理模式，Q1和Q13都是包含兩條簡單推理模式的復(fù)合模式，復(fù)雜度較Q7和Q8低，所以Q1的推理時間隨數(shù)據(jù)規(guī)模變化最不明顯，而Q13的推理時間升高應(yīng)該是推理結(jié)果隨著數(shù)據(jù)規(guī)模變大而變化的原因。

由此可見，基于Spark的并行化語義后向鏈推理系統(tǒng)的推理時間隨著數(shù)據(jù)規(guī)模的擴大都是近線性上升，表現(xiàn)出了很好的數(shù)據(jù)可擴展性。

5.3.3 節(jié)點可擴展性測試

大規(guī)模語義推理使用分布式并行計算技術(shù)進行加速，一個擴展性好的系統(tǒng)，應(yīng)該在增加節(jié)點時能提高處理速度，而在減少節(jié)點時則會增加處理時間。本文實驗使用LUBM 1 000個大學(xué)數(shù)據(jù)集，在計算節(jié)點從一個增加到16個時觀察系統(tǒng)的推理性能，得到系統(tǒng)推理時間隨計算節(jié)點數(shù)的變化關(guān)系，實驗結(jié)果見圖12、圖13。

圖12 基于RDFS規(guī)則集的節(jié)點可擴展性

圖13 基于OWL規(guī)則集的節(jié)點可擴展性

由實驗數(shù)據(jù)可知，越是耗時的推理，增加計算節(jié)點獲得的性能提升越明顯。將實驗結(jié)果整理成相對加速比，如圖14和圖15所示。相對加速比(S)是指同一算法在單節(jié)點環(huán)境下的執(zhí)行時間(T1)和多節(jié)點(n個)環(huán)境下的執(zhí)行時間(Tn)的比值，即s=T1/Tn。

圖14 基于RDFS規(guī)則集的加速比

圖15 基于OWL規(guī)則集的加速比

加速比曲線顯示，多數(shù)推理模式隨著計算節(jié)點數(shù)的增加，表現(xiàn)出了明顯的加速趨勢，所以本文提出的基于Spark的并行化語義后向鏈推理系統(tǒng)具有較好的節(jié)點可擴展性。

6 總結(jié)

語義推理是語義網(wǎng)技術(shù)體系中的高級分析技術(shù)，得到了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注和研究，在輔助藥物開發(fā)、社交關(guān)系分析等領(lǐng)域已經(jīng)有成功應(yīng)用。雖然前向鏈和后向鏈語義推理的目的相同，但到目前為止，人們提到語義推理主要還是指前向鏈語義推理，對語義推理的研究也主要集中在前向鏈方法上，后向鏈語義推理的研究因為推理過程復(fù)雜而進展緩慢。如今的互聯(lián)網(wǎng)信息日新月異，前向鏈語義推理對于知識庫更新而帶來高昂代價的缺點逐漸顯露，后向鏈語義推理的準(zhǔn)實時推理查詢、對知識庫更新不敏感等特點恰好適用于知識快速更新的場景。因而設(shè)計實現(xiàn)高效的大規(guī)模后向鏈語義推理系統(tǒng)成為了新的研究課題。本文提出的基于Spark的大規(guī)模并行化語義規(guī)則后向鏈推理方法實現(xiàn)了并行化的后向鏈語義推理，并且在多方面進行了優(yōu)化，實現(xiàn)了較好的推理性能。

在將來的工作中，我們將繼續(xù)研究在更加復(fù)雜的規(guī)則集上進行后向鏈推理，并研究大規(guī)模RDF數(shù)據(jù)的快速編碼和解碼方法，進一步提高推理系統(tǒng)的表達能力和推理速度。

[1] Pelikánová Z. Google Knowledge Graph[DB/OL]. https: //www.google.com/intl/es419/insidesearch/features/search/knowledge.html[2014].

[2] Dean J, Ghemawat S.MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[3] Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[J]. HotCloud, 2010(10): 10-10.

[4] W3C. RDF vocabulary description language 1.0: RDF schema[S]. https: //www.w3.org/TR/2004/REC-rdf-schema-20040210/

[5] McGuinness D L, Van Harmelen F. OWL web ontology language overview[J]. W3C Recommendation, 2004, 10(10): 10-20.

[6] Urbani J, Oren E, Van Harmelen F. RDFS/OWL reasoning using the MapReduce framework[J]. Science, 2009: 1-87.

[7] Urbani J, Van Harmelen F, Schlobach S, et al. QueryPIE: Backward reasoning for OWL Horst over very large knowledge bases[J]. The Semantic Web-ISWC 2011, 2011: 730-745.

[8] 施惠俊.基于云計算的海量語義信息并行推理方法研究[D].上海: 上海交通大學(xué)碩士學(xué)位論文，2012.

[9] 瞿裕忠,胡偉,程龔. 語義網(wǎng)技術(shù)體系[M]. 北京： 科學(xué)出版社, 2015： 32-60.

[10] Carroll J J, Dickinson I, Dollin C, et al. Jena: Implementing the semantic web recommendations[C]//Proceedings of the 13th International World Wide Web Conference on alternate Track Papers & Posters. ACM, 2004: 74-83.

[11] Franz Inc. Allegro graph: RDF triple database. [DB/OL] https: //franz.com/agraph/allegrograph/

[12] Erling O. Virtuoso, a hybrid RDBMS/Graph column store[J]. IEEE Data Eng. Bull., 2012, 35(1): 3-8.

[13] Marriott K, Stuckey P J. Programming with constraints: An introduction[M].Cambridge： MIT press, 1998： 4-9.

[14] Santos J, Muggleton S. When does it pay off to use sophisticated entailment engines in ILP?[M]. Inductive Logic Programming. Berlin： Springer Berlin Heidelberg, 2010: 214-221.

[15] Tamaki H, Sato T. OLD resolution with tabulation[C]//Proceedings of the 3rd International Conference on Logic Programming.Berlin： Springer Berlin Heidelberg, 1986: 84-98.

[16] Shi H, Maly K, Zeil S. Optimized backward chaining reasoning system for a semantic web[C]//Proceedings of the 4th International Conference on Web Intelligence, Mining and Semantics(WIMS14). ACM, 2014: 34.

[17] Shi H, Maly K, Zeil S. Query optimization in cooperation with an ontological reasoning service[C]//Proceedings of the fifth International Conferences on Advanced Service Computing.Valencia： SERVICE COMPUTATION, 2013: 26-32.

[18] 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. ACM, 2012: 4.

[19] Jacopo Urbani. Proof of correctness of QueryPIE closure algorithm[DB/OL]. http: //citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.3998

[20] Armbrust M, Xin R S, Lian C, et al. Spark SQL: Relational data processing in spark[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015: 1383-1394.

[21] Guo Y, Pan Z, 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.

[22] Auer S, Bizer C, Kobilarov G, et al. Dbpedia: A nucleus for a web of open data[M].Berlin： Springer Berlin Heidelberg, 2007.

[23] Urbani J, Kotoulas S, Oren E, et al. Scalable distributed reasoning using mapreduce[M].Berlin： Springer Berlin Heidelberg, 2009.