吳 剛， 閆智宣， 邱煜晶， 盧海強， 李 洋

(東北大學(xué) 計算機科學(xué)與工程學(xué)院 遼寧 沈陽 100619)

0 引言

隨著語義Web的規(guī)模和重要性的不斷增長，越來越多的知識以機器可讀的格式存儲，如RDFS和OWL.對于許多應(yīng)用，知識的提取和推理是核心要求之一.通過推理，知識可以有邏輯地導(dǎo)出，而不僅是明確存在于數(shù)據(jù)中[1].然而，大規(guī)模本體數(shù)據(jù)的推理可能導(dǎo)致產(chǎn)生大量邏輯沖突，為了定位和解釋這些邏輯沖突，通常使用本體調(diào)試的方法[2].近年來，已經(jīng)有一些程序以有效的方式實現(xiàn)了本體推理[3-5]，本體調(diào)試領(lǐng)域也有了長足進(jìn)展，提出了很多RDFS和OWL[6]本體上的調(diào)試方法.這些方法及相應(yīng)的原型系統(tǒng)主要應(yīng)用于特定的且規(guī)模較小的本體數(shù)據(jù)集，可以分為兩類：一是基于修改描述邏輯推理引擎的白盒方法；二是將描述邏輯推理引擎作為外部信息源用于檢查本體可滿足性的黑盒方法[7].針對百萬數(shù)量級的本體數(shù)據(jù)，傳統(tǒng)的本體調(diào)試方法求取計算的時間長，不能滿足大規(guī)模、大數(shù)據(jù)量的本體數(shù)據(jù)求取最小沖突公理集合的需求.

已有的分布式本體調(diào)試方法[8]存在耗時較長的問題，其原因是基于分布式文件系統(tǒng)HDFS的存儲結(jié)構(gòu)不能滿足日益增多的本體調(diào)試的需求.本文提出了一種良好的存儲結(jié)構(gòu)和更有效的存儲模式存儲調(diào)試信息，以提高本體調(diào)試的速度.此外，考慮到普遍存在本體自身演化和本體間鏈接更新的情況，已存在的RDFS和OWL分布式推理與調(diào)試的靜態(tài)算法是不夠合理的，缺乏對已經(jīng)推理的蘊含及調(diào)試信息的有效利用.本體的更新包括增加和刪除本體數(shù)據(jù)，這些更新必然會導(dǎo)致已經(jīng)推導(dǎo)出的蘊含及其調(diào)試信息失效，重新對所有本體數(shù)據(jù)進(jìn)行推理和調(diào)試信息的收集耗時、耗力.因此，本文提出一種增量更新算法，以應(yīng)對本體數(shù)據(jù)不斷更新的情況，實現(xiàn)了本體數(shù)據(jù)的動態(tài)更新，LUBM數(shù)據(jù)集的實驗結(jié)果表明該算法是有效的.

1 系統(tǒng)結(jié)構(gòu)

分布式環(huán)境下RDFS和OWL pD*本體推理與調(diào)試系統(tǒng)主要由以下3個部分組成：

第1部分，數(shù)據(jù)預(yù)處理部分.將原始三元組中的資源數(shù)據(jù)以數(shù)字id的方式編碼壓縮，以減少數(shù)據(jù)的讀寫量，將盡量多的數(shù)據(jù)讀入內(nèi)存，達(dá)到加速的效果.需要存儲的數(shù)據(jù)包括編碼后的三元組，以及資源與id的對應(yīng)關(guān)系.這些數(shù)據(jù)主要用于推理和辯解信息解碼.

第2部分，本體推理部分.包括RDFS推理和OWL pD*推理，應(yīng)用RDFS和OWL pD*規(guī)則進(jìn)行推理，將推理出的三元組存儲于數(shù)據(jù)庫，循環(huán)執(zhí)行兩種推理機直到?jīng)]有新的三元組產(chǎn)生.主要存儲信息包括以七元組形式表示的蘊含及其調(diào)試信息.

第3部分，本體調(diào)試部分.利用調(diào)試信息遞歸求取最小沖突公理集合，然后對辯解集合中的資源進(jìn)行解碼，同時對辯解集合進(jìn)行緩存.主要存儲信息為最終的調(diào)試結(jié)果.

系統(tǒng)的3個部分都涉及密集的數(shù)據(jù)讀寫，需要對3個部分分別進(jìn)行存儲設(shè)計和優(yōu)化.對相關(guān)算法進(jìn)行優(yōu)化以適應(yīng)分布式數(shù)據(jù)的讀寫，并保證算法的正確性和完備性.系統(tǒng)采用Hadoop提供的MapReduce模型作為計算模型，采用Cassandra數(shù)據(jù)庫作為分布式存儲模型.系統(tǒng)的整體結(jié)構(gòu)如圖1所示.

圖1 系統(tǒng)整體結(jié)構(gòu)Fig.1 The overall structure of system

2 數(shù)據(jù)預(yù)處理及其存儲結(jié)構(gòu)

2.1 字典編碼

采用被廣泛應(yīng)用于數(shù)據(jù)壓縮問題的字典編碼技術(shù)，把以文本表達(dá)的三元組中的元素轉(zhuǎn)換成數(shù)值id存儲數(shù)據(jù).將三元組進(jìn)行壓縮，能夠減少空間的占用.使用的壓縮方案是用3個數(shù)字代替三元組的3個元素，數(shù)據(jù)編碼并不影響推理過程.使用MapReduce進(jìn)行字典編碼處理[9]，編碼后的字典和數(shù)值形式的三元組存儲于分布式數(shù)據(jù)庫中.

2.2 存儲結(jié)構(gòu)

對于分布式數(shù)據(jù)庫的配置，由于系統(tǒng)的Cassandra數(shù)據(jù)庫部署在一個高可用的集群上，因此采用單數(shù)據(jù)中心模式.Keyspace作為Cassandra中最大的組織單元，包含了一系列的Column family. 設(shè)計Keyspace采用的備份策略為SimpleStrategy，設(shè)置副本數(shù)為2，即同一份數(shù)據(jù)保存在兩個不同的節(jié)點.設(shè)計數(shù)據(jù)庫的寫一致性為ANY，讀一致性為ONE，即寫數(shù)據(jù)庫時寫入任一個副本即標(biāo)記為寫成功；讀數(shù)據(jù)庫時讀取最近的副本成功即可.

從數(shù)據(jù)庫讀取數(shù)據(jù)采用分頁讀取的方式.由于大數(shù)據(jù)量的三元組不能一次性完全讀入內(nèi)存，需采用分頁讀取的方式.Cassandra數(shù)據(jù)分頁的數(shù)量直接影響MapReduce中的Map數(shù)量，每個分頁對應(yīng)一個節(jié)點的一個Map，因此，需要設(shè)置合適的分頁大小.當(dāng)分頁較小時，產(chǎn)生的頁數(shù)很多，會啟動大量的Map，導(dǎo)致大量的時間用于job的啟動和結(jié)束，用于處理數(shù)據(jù)的時間變少；當(dāng)分頁較大時，啟動的Map數(shù)量較少，每個job承擔(dān)的數(shù)據(jù)量變大，可能存在著job執(zhí)行失敗的情況，重啟job需要重新進(jìn)行推理，同樣較為耗時.

3 本體推理調(diào)試及其存儲結(jié)構(gòu)

3.1 本體推理與調(diào)試

推理包含RDFS推理和OWL pD*推理兩部分.規(guī)則的執(zhí)行順序存在著一定的特點，通過調(diào)整規(guī)則的應(yīng)用順序，能夠有效地加快推理過程[9].對于整個系統(tǒng)的推理過程，需要循環(huán)執(zhí)行RDFS推理機和OWL pD*推理機，直到?jīng)]有新的三元組產(chǎn)生.

最小沖突公理集合的求取方法與真值維護(hù)系統(tǒng)(TMS)求解過程[10]有一定相似之處.TMS主要通過TMS依賴圖實現(xiàn)[11]，通過在推理引擎前向推理過程中記錄調(diào)試信息來構(gòu)建TMS依賴圖.當(dāng)推理引擎每應(yīng)用一次推理規(guī)則產(chǎn)生新的推理結(jié)果，就在依賴圖中添加相應(yīng)的節(jié)點和有向超邊[12].調(diào)試過程參照文獻(xiàn)[8]，使用JTMS(justification-based TMS)求取OWL pD*語義下推理結(jié)果的所有調(diào)試信息.

3.2 蘊含及其調(diào)試信息的壓縮

為了實現(xiàn)本體調(diào)試，求取已經(jīng)推理出的蘊含調(diào)試信息集合，需要保存推理過程中的相關(guān)調(diào)試信息.由于調(diào)試信息中有冗余信息，直接全部存儲會造成存儲空間的浪費，同時降低寫速度，從而降低系統(tǒng)整體的運行速度.

假設(shè)本體中有兩個三元組T1：〈QiE, type, Bird〉，T2：〈Bird, rdfs: subClassOf, Animals〉.根據(jù)推理規(guī)則可以推出一個新的三元組T3：〈QiE, type, Animals〉.對于T3只有一條調(diào)試信息〈T1,T2〉，可以表示為J(T3)={{T1,T2}}. 因此,需要存儲的信息為T3: 〈QiE, type, Animals, QiE, type, Bird, Bird, rdfs: subClassOf, Animals〉. 可見RDF詞匯“QiE”、“Bird”、“Animals”都被重復(fù)存儲了.分析推理規(guī)則和結(jié)果發(fā)現(xiàn)，對于任何subClassOf規(guī)則的實例中，前提subClassOf和結(jié)論type均為已知且保持不變.因此,對于上述存儲方案存在的冗余，提出標(biāo)簽壓縮方案作為調(diào)試信息的表示方式.

調(diào)試信息的存儲模式使用一個固定長度的標(biāo)簽方案來表示綁定的規(guī)則.規(guī)則綁定標(biāo)簽是一個七元組(Con-Sub，Con-Pre，Con-Obj，RuleName，Binding1，Binding2，Binding3)，其中Con-Sub、Con-Pre和Con-Obj對應(yīng)主語、謂語和賓語，是推理出的結(jié)果三元組的RDF術(shù)語；RuleName表示規(guī)則集合中的規(guī)則模式，即應(yīng)用哪些規(guī)則得出新的三元組；Binding1、Binding2和Binding3的值表示RDF術(shù)語的來歷和前提，即推導(dǎo)出該三元組的相關(guān)的三元組信息.具體的綁定標(biāo)簽的規(guī)則壓縮方案見文獻(xiàn)[8].

本體推理階段，即調(diào)試信息的收集階段，采用簡化的JTMS依賴圖與推理機的前向推理過程一起構(gòu)建，方式是在前向推理過程中增加存儲相關(guān)調(diào)試信息的步驟.對相同的三元組應(yīng)用不同的推理規(guī)則會有不同的綁定標(biāo)簽.存儲簡化后的綁定標(biāo)簽的數(shù)量等于JTMS依賴圖中的邊數(shù).因此，使用綁定標(biāo)簽對推理過程和依賴圖不會產(chǎn)生太大的影響.

3.3 調(diào)試信息存儲模式

推理機執(zhí)行的每一步都需要讀取全部三元組，包括公理和之前步驟推理出的結(jié)果.Cassandra數(shù)據(jù)庫同時讀取兩個表的數(shù)據(jù)或同時向兩個表寫數(shù)據(jù)的速度遠(yuǎn)低于向同一個表讀寫數(shù)據(jù). 因此，最佳存儲方法是將公理與推理出的結(jié)果保存在同一個表中，以相同的格式存儲.

通過對RDFS和OWL pD*推理過程的分析，以及調(diào)試信息綁定標(biāo)簽的存儲方式可知，需要存儲的信息包括綁定標(biāo)簽的七元組，justifications表結(jié)構(gòu)如圖2所示.

圖2 Justifications表結(jié)構(gòu)Fig.2 Justifications table structure

由于justifications表存儲了所有的公理和推理結(jié)果及其辯解信息，存儲的數(shù)據(jù)量巨大，并且在本體推理和調(diào)試過程中都需要大量讀寫該表. 因此，需要盡量優(yōu)化該表的組織結(jié)構(gòu).在Cassandra數(shù)據(jù)庫中，Partition Key作為Primary Key的一部分，主要作用是決定該行數(shù)據(jù)是存儲于哪個節(jié)點，或者應(yīng)從哪個節(jié)點讀取.在本系統(tǒng)中Partition Key的設(shè)計選擇主要有(sub, pre, obj)和(isliteral, rule, sub)兩種方式，其中后一種設(shè)計能使集群的數(shù)據(jù)負(fù)載更加均衡.因此，設(shè)置justifications表的Partition Key為(isliteral, rule, sub).Primary Key其余的屬性作為Clustering Key，主要作用是以此為依據(jù)對分區(qū)內(nèi)的行進(jìn)行排序. 由于推理過程中需要對tripletype屬性進(jìn)行條件查詢，而Cassandra數(shù)據(jù)庫不支持Partition Key或Clustering Key屬性的跳躍選擇查詢. 因此，需要將tripletype排在Clustering Key的第1位，同時在tripletype列創(chuàng)建索引.

3.4 本體數(shù)據(jù)蘊含集緩存設(shè)計

為了避免重復(fù)求取所推理的蘊含集，尤其對于在本文后續(xù)的本體刪除算法中會經(jīng)常出現(xiàn)求取相同三元組的蘊含信息情況，對全部三元組推理的蘊含集進(jìn)行了緩存.設(shè)計表entailments存儲全部本體數(shù)據(jù)推理的蘊含信息，分布式求取過程如下：首先讀取justifications表中能得到新推理結(jié)果的七元組，然后根據(jù)七元組找出推理結(jié)果并求出其所需的全部前提三元組[8].再遍歷前提三元組，將每條三元組作為entailments表的主鍵，推理結(jié)果三元組作為表的Value值，更新到蘊含集.

4 增量更新算法

4.1 本體增加算法

當(dāng)本體數(shù)據(jù)中有新的公理加入時，調(diào)試信息也會隨之增加，此時完全地重新進(jìn)行本體信息的推理與存儲的開銷較大.由于新增的公理與增加前已有的公理之間沒有必然的聯(lián)系，與已儲存的推理結(jié)果也沒有直接關(guān)系，因而當(dāng)本體數(shù)據(jù)增加后，已有的調(diào)試信息不需要更改.通過JTMS依賴圖亦可發(fā)現(xiàn)，依賴圖中增加新的節(jié)點，不影響圖中已存儲的節(jié)點和邊.據(jù)此提出以下算法：新增公理的情況下，當(dāng)應(yīng)用一條規(guī)則時，如果前置條件均為已有的公理或已有推理結(jié)果，則該蘊含的推理結(jié)果實際已存儲，可直接跳過這個推理過程.只有前置條件中至少包含一條三元組為新增三元組才會產(chǎn)生新的推理結(jié)果.為此，當(dāng)新增公理時，為推理機所有規(guī)則的執(zhí)行設(shè)計了一個前提，即將規(guī)則應(yīng)用到數(shù)據(jù)集合時，如果規(guī)則的前置條件至少存在一條公理是新增公理，就執(zhí)行推理機；如果前置條件包含的三元組均為原始三元組，則直接跳過.添加該前提約束，以避免對已存儲過的調(diào)試信息進(jìn)行推理.

對于新增加的公理，經(jīng)過本體推理可能會產(chǎn)生新的推理結(jié)果，并且可能會將其繼續(xù)用于后續(xù)的推理規(guī)則.因此，需要將新增的推理結(jié)果同樣標(biāo)記為新三元組，加入到新增三元組的集合，與新增公理以相同形式存儲.

整個更新過程使用的推理算法不變.具體的處理過程根據(jù)規(guī)則可以分為兩類：一類是新增公理相對原有公理的推理沒有受到影響，對應(yīng)的規(guī)則如文獻(xiàn)[8]中p1、p2、p3、D2等，可只進(jìn)行針對新增公理的推理，由于相對簡單就不再詳述；另一類是在新增公理上使用具有傳遞閉包屬性的規(guī)則，如規(guī)則D5、D7、D11、p4、p7、p12c、p13c等.這種情況下推理算法的輸入數(shù)據(jù)為全部的本體信息，但是新增公理集的閉包關(guān)系只與新增本體有關(guān)，算法時間復(fù)雜度為O(n).

4.2 本體刪除算法

當(dāng)從本體數(shù)據(jù)中刪除數(shù)據(jù)時，刪除已有的公理可能會導(dǎo)致存儲的調(diào)試信息失效.失效的調(diào)試信息是指從本體數(shù)據(jù)集合去除刪除公理后無法通過剩余的公理推理得到的信息.

當(dāng)刪除本體數(shù)據(jù)時，除了要刪除公理本身，還要刪除失效的調(diào)試信息，即包含該公理的調(diào)試信息.因此,需要考察由此公理推理得到的各三元組，可分為兩種情況：若某三元組對應(yīng)的調(diào)試信息集合中刪除與此公理相關(guān)的調(diào)試信息后，調(diào)試信息集合不空，則可以刪除與該公理相關(guān)的調(diào)試信息，保留該三元組及其調(diào)試信息集合中的其他調(diào)試信息；若當(dāng)一個三元組的調(diào)試信息集合中全部調(diào)試信息都與該公理有關(guān)，在刪除與此公理相關(guān)的調(diào)試信息后，調(diào)試信息集合為空，則應(yīng)該同時刪除該三元組，同時將該三元組添加到刪除集合，迭代執(zhí)行刪除算法，算法時間復(fù)雜度為O(n2).

刪除算法的執(zhí)行步驟如下：

1) 查找resources表，對需刪除的本體數(shù)據(jù)進(jìn)行數(shù)據(jù)編碼，然后將其添加到集合D.

2) 刪除由此公理推理出來的相關(guān)辯解信息.由于保存的調(diào)試信息都以綁定標(biāo)簽的形式進(jìn)行，從存儲的數(shù)據(jù)上不能直接判斷一個蘊含辯解是否包含刪除的三元組.因此,根據(jù)保存的調(diào)試信息一次性求取全部的蘊含信息并保存到數(shù)據(jù)庫entailments表.

3) 對集合D中所有三元組Ti進(jìn)行本體調(diào)試，查詢蘊含表，找出D中三元組對應(yīng)的蘊含信息，循環(huán)遍歷所有蘊含，求取對應(yīng)的辯解集合Ji.

4) 遍歷所有辯解集合Ji，判斷其中的每一個辯解集合中的每一條辯解信息是否包含刪除三元組：對于不包含刪除三元組的辯解信息保持不變；對于包含刪除三元組的辯解信息，將該條辯解信息刪除.

5) 刪除所有包含刪除三元組的辯解信息后，清空集合D.同時遍歷所有辯解集合Ji，判斷是否存在空集合：如果辯解集合為空的蘊含，將其添加到刪除三元組集合D，重新從1)開始.如果刪除集合D為空，刪除過程完成.

5 實驗

5.1 實驗環(huán)境與系統(tǒng)部署

實驗數(shù)據(jù)取自LUBM(Lehigh University Benchmark)標(biāo)準(zhǔn)測試數(shù)據(jù)集，分別為LUBM-1、LUBM-10、LUBM-100.系統(tǒng)部署在集群服務(wù)器上，集群共有9個節(jié)點.集群使用Hadoop-0.20.2，Cassandra-2.1.10，內(nèi)存64G，硬盤50G，CPU雙核單線程.

5.2 本體調(diào)試實驗

對三元組進(jìn)行數(shù)據(jù)編碼，圖3展示了壓縮前后存儲對比效果.實驗中通過多次隨機選擇數(shù)據(jù)庫justifications表中一行，即隨機選取一條三元組，進(jìn)行本體調(diào)試.

在經(jīng)過多次隨機求取調(diào)試信息集合后發(fā)現(xiàn)，影響求解過程用時的主要因素是MapReduce求解過程啟動job的數(shù)量.當(dāng)求解需要啟動的job數(shù)量越多時，其耗時越長.存儲優(yōu)化前的系統(tǒng)基于HDFS調(diào)試信息存儲，圖4展示了對于相同job數(shù)的存儲優(yōu)化前后的本體調(diào)試用時對比效果.容易發(fā)現(xiàn)，對于使用分布式數(shù)據(jù)庫作為存儲的本體調(diào)試系統(tǒng)，即使啟動較多數(shù)量的job，其調(diào)試時間較原系統(tǒng)中較少數(shù)量的job依然具有很大的優(yōu)勢，是優(yōu)化前用時的15%～25%.

圖3 壓縮前后存儲對比Fig.3 Storage comparison before and after compression

5.3 增量更新算法實驗結(jié)果

測試增加的數(shù)據(jù)量為10條公理，增加新的公理后完全重新推理用時與使用本體增加算法用時的對比如圖5所示.另外在LUBM-10數(shù)據(jù)集上進(jìn)行了3組對比實驗，分別增加原數(shù)據(jù)集的5%、10%、20%，實驗結(jié)果如圖6所示.這兩個實驗表明動態(tài)更新算法比重新推理更為有效.

刪除算法需要一次緩存調(diào)試信息的過程，刪除算法所用時間與重新推理所用時間對比如圖7所示.結(jié)果表明，使用刪除算法比完全重新推理具有明顯的速度優(yōu)勢，并且隨著數(shù)據(jù)量的增加，優(yōu)勢在慢慢變大.但是緩存全部調(diào)試信息的時間會隨數(shù)據(jù)量的增大明顯增加.另外在LUBM-10數(shù)據(jù)集上進(jìn)行了3組對比實驗，如圖8所示，分別刪除原數(shù)據(jù)集的5%、10%、20%，和重新推理用時進(jìn)行比較，發(fā)現(xiàn)在刪除本體數(shù)量超過原數(shù)據(jù)集的20%時，重新推理的速度便優(yōu)于刪除算法了，因而在少量本體數(shù)據(jù)刪除時使用該算法會更加有效.

圖4 本體調(diào)試用時對比Fig.4 Ontology debugging time comparison

圖5 不同數(shù)據(jù)集上增加算法對比Fig.5 Increase algorithm comparison on different datasets

圖6 LUBM-10數(shù)據(jù)集上增加算法對比Fig.6 Increase algorithm comparison on LUBM-10 dataset

圖7 不同數(shù)據(jù)集上刪除算法對比Fig.7 Delete algorithm comparison on different datasets

圖8 LUBM-10數(shù)據(jù)集上刪除算法對比Fig.8 Delete algorithm comparison on LUBM-10 dataset

6 小結(jié)

通過設(shè)計分布式數(shù)據(jù)庫作為存儲模式來提高本體調(diào)試的速度，本體修改后對本體數(shù)據(jù)進(jìn)行了增量式更新，LUBM數(shù)據(jù)集的實驗結(jié)果表明該增量更新算法是有效的. 針對本體調(diào)試信息呈現(xiàn)給用戶的方式仍有不足，對辯解集合進(jìn)行求解后，返回的結(jié)果是以三元組集合的形式呈現(xiàn)，當(dāng)調(diào)試信息較多時，用戶無法判斷哪些調(diào)試信息更重要.因此，可進(jìn)一步通過設(shè)計衡量調(diào)試信息重要性或相關(guān)性的算法，對調(diào)試信息進(jìn)行度量，同時實現(xiàn)Top-k算法，返回經(jīng)過排序的調(diào)試信息，從而改善用戶體驗.