基于圖的不一致容忍語義下的查詢應答方法

付雪峰 漆桂林 張 勇

（東南大學計算機科學與工程學院 南京 210096）（fxf＠seu．edu．cn）

基于圖的不一致容忍語義下的查詢應答方法

付雪峰 漆桂林 張 勇

（東南大學計算機科學與工程學院 南京 210096）（fxf＠seu．edu．cn）

本體在演變的過程中常出現不一致性問題，這將導致經典的推理模式失效．不一致容忍語義能有效地解決推理失效的問題，但各類不一致容忍語義或者需要耗費大量計算，或者丟棄了本體中有效的信息．為此，一種針對IAR－語義和ICAR－語義的變種被用以解決上述的缺陷．新定義的IPAR－語義能夠避免計算整個ABox關于TBox的封閉，在減少計算量的同時盡可能地保留了本體中的信息．在IPAR－語義下實現了基于圖的查詢應答方法，新方法將本體和查詢以不同的規則構建成圖，避免了傳統重寫導致的查詢冗余的問題．最后，通過實驗對比新的查詢應答方法與ICAR－語義下的查詢應答方法，實驗結果表明：基于圖的一致性查詢方法執行效率要優于ICAR－語義下的查詢方法；在本體規模不斷增加的情況下，新方法具有更好的穩定性．

本體；不一致容忍；DL－Lite；圖；查詢應答

本體作為共享概念模型的形式化規范，提供了組成論域詞匯表中的基本概念和關系［1］，廣泛應用于不同的領域，如萬長林等人借助本體技術來描述和發現Web服務［2］、賈存鑫等人實現了基于語義的關系數據庫模式到本體的映射方法［3］．本體在應用中常處于演變的狀態，這可能引起本體的不一致［4］，并因此導致本體推理的失敗［5］．對于本體中出現的不一致問題，通常有2種處理方法，一種是診斷并且修復本體中出現的不一致［6］；另一種是應用非標準的推理方法，在不一致存在的情況下完成推理任務［7］．本文主要考慮非標準的推理方法，特別是不一致本體下的查詢應答方法．當前存在多種非標準推理方法，如張小旺等人提出一種非經典描述邏輯QCDL來實現非標準推理［8］．此外，有些方法則借助于特定的語義來實現對不一致信息的容忍，如Bertossi等人利用不一致本體的一致子集來實現有效的推理［9］，Lembo等人則針對DL－Lite本體提出了4種不一致容忍語義［10］．就DL－Lite而言，它能支持易處理的查詢應答，Calvanese等人在文獻［11］中提出的PerfectRef算法實現了在TBox層對合取查詢的重寫操作，重寫后的查詢僅在ABox層就能完成，這樣就可將ABox部署到關系數據庫上來完成查詢．然而算法PerfectRef可能導致重寫后的查詢過于龐大和復雜，且由于關系數據庫存儲ABox的缺陷，導致實際查詢效率并不高［12］．為此，文獻［13］對查詢重寫做了優化工作來減少重寫后的查詢項；文獻［14］則通過抽取原始查詢項中的模式，應用增量式的方法來優化重寫．此外，基于圖的方法也常用以優化查詢，如文獻［15］中就提出了基于圖的關系數據庫查詢重寫方法，Qin等人提出了一種基于圖的本體查詢重寫方法［16］；在圖上建立模式與本體的映射，提高了重寫算法的效率．

本文關注不一致本體下的一致性查詢應答問題，對此問題Lembo等人在文獻［17］中提出了IAR－語義和ICAR－語義下的一致性查詢應答算法，Rosati等人在LUBM數據集上實現對上述算法效率的評測實驗［18］．但在IAR－語義下的查詢丟棄了所有有疑問的公理，導致有效信息的丟失；而ICAR－語義雖然能夠盡可能多地保留有效的信息，但需要計算本體中ABox在TBox約束下的封閉，而在大規模數據下的封閉計算是一項非常耗時的任務，這些特征限制了它們在實踐中的應用．為此，我們新定義了一種不一致容忍語義——IPAR－語義，在盡可能保留有效數據的基礎上，減少對封閉的計算量．在IPAR－語義的基礎上，我們考慮應用圖來改進DL－Lite中的查詢應答方法，受文獻［19－21］工作的啟發，我們提出了一種基于圖的一致性查詢應答方法，新方法將DL－Lite本體轉換成圖，同時應用不同的規則將查詢也轉換成圖，對于不一致的處理則考慮IPAR－語義下的限定，從而實現在不一致的本體中獲取一致的查詢答集．

1 理論基礎

描述邏輯是一種基于對象的知識表示的形式化方法，它建立在概念和角色之上，其中概念解釋為對象的集合，角色解釋為對象之間的二元關系．本文的研究對象是一類輕量級的描述邏輯——DL－Lite，它能夠捕獲數據庫中的實體關系模型以及統一建模語言中類的知識，同時又能保證易處理的推理和高效率的查詢應答［11］．本文主要考慮DL－Lite家族的3個子語言，分別是DL－Litecore，DL－LiteF，DL－LiteR．DL－Litecore是DL－Lite家族的核心，其概念和角色的語法的形式化定義如下［11］：B→A｜ R，R→P｜P－，C→B｜瓙B，E→R｜瓙R．

定義中A是指原子概念，P是指原子角色，P－是原子角色的逆，B是基本概念，B的語法形式為原子概念或者為 R，R是基本角色，R的語法形式為原子角色或者原子角色的逆，C為一般概念，C的語法形式為基本概念或者基本概念的否定，E為一般角色，E的語法形式為基本角色或者基本角色的否定．DL－Lite本體由術語斷言集合（TBox）與實例斷言集合（ABox）組成，記為!＝?"，#?．"是術語斷言的集合，其語法形式為BC；#是實例斷言的集合，包括概念實例斷言和角色實例斷言，語法形式為A（a）或P（a，b）．DL－LiteR和DL－LiteF都對DLLitecore做了擴充．DL－LiteR擴充了角色包含公理，其語法形式為RE；DL－LiteF擴充了函數約束公理，其語法形式為funct R．

在本體中，形如B1B2或R1R2的公理稱為肯定包含公理，形如B1瓙B2或R1瓙R2的公理稱為否定包含公理．否定包含公理的演繹閉包記為cln（"），肯定包含公理的演繹閉包記為clp（"）［11］，文中使用cl（"）＝cln（"）∪clp（"）來表示整個TBox的演繹閉包．DL－Lite通過解釋來描述語義，一個解釋I＝?ΔI，·I?，其中ΔI為非空的解釋域，·I為解釋域上的解釋函數．解釋函數將一個概念A解釋為一個集合，將一個原子角色P解釋為一個關系，其形式化描述如表1所示．對于一個DLLite公理 和一個解釋I，如果滿足I ，則表明解釋I為公理 的一個模型；如果一個解釋I滿足本體!中的所有公理，則該解釋為本體!的一個模型；如果本體!的所有模型也是公理 的模型，則稱本體!蘊含 ，記為! ．一個可滿足的本體最少有一個模型，否則該本體就是不可滿足的．

Table 1 The Semantics of DL－Lite表1 DL－Lite中的語義描述

在DL－Lite本體中查詢源于一階邏輯中的查詢，一階邏輯中的查詢是一個包含自由變量的公式，它有很多種類別，本文主要考慮合取查詢（conjunctive query，CQ）以及合取查詢的并（union of conjunctive queries，UCQ）．合取查詢q的一階邏輯的形式化定義為：

合取查詢的并Q是一個復雜的查詢．Q的一階邏輯的形式化定義為：

其中，conji（x，yi）是一個合取查詢，x為顯著性變量（distinguished variables），yi為非顯著性變量（nondistinguished variables）．變量x的大小代表查詢中參數的個數，如果參數的個數為0，則稱這個查詢為布爾查詢．在描述邏輯的知識庫中，UCQ的形式為｛q1，q2，…qn｝，其中qi為一個CQ，由形如A（a）或R（b，c）的公理組成，這里A表示原子概念，R表示原子角色，a，b，c是個體常量或者變量．對于一個查詢q（CQ或UCQ）和一個知識庫$，查詢q在$上的答集（answer）記為ans（q，$），它是常量元組的集合．

2 不一致容忍語義及其變種

在文獻［10］中提出了4種不一致容忍語義，分別是AR－語義、IAR－語義、CAR－語義、ICAR－語義．這4個不一致容忍語義旨在獲取不一致本體的最大一致子集，其核心是源于不一致數據庫查詢中的數據修復的概念［22］．對于一個不一致的本體!＝?"，#?，它的修復為一個一致的本體?"，#′?，其中#′是指定規則下獲取的本體ABox部分的最大一致子集．本文主要考慮IAR－語義和ICAR－語義，這是由于在這2個不一致容忍語義下的查詢為多項式時間的復雜度，能提供易處理的推理支持［10］．下面首先引用IAR－語義的定義．

定義1．給定一個描述邏輯本體!＝?"，#?，本體!的ABox修復的交（intersection ABox repair），記為IAR－Rep（!），其中ABox#的修復記為ARRep，#′滿足下述條件：

1）#′ #；

2）Mod（?"，#′?）≠ ；

3）不存在#的子集#″，滿足Mod（?T，#″?）≠ ，其中#′ #″ #．

對于一個解釋I，記#R＝IAR－Rep（!），如果滿足I ?T，#R?，稱解釋I為IAR－修復的一個模型，本體!在IAR－修復下的模型的集合記為IAR－Mod（!）；對于一個公理 和任意一個解釋I∈IAR－Mod（!），如果I ，則稱本體!IAR－蘊含（IAR－entailed） ，記為!IAR．

IAR－修復與本體的語法形式密切相關，假設存在2個本體!＝?"，#?和!′＝?T，#′?，# #′且｛#′＼#｝中的公理能被#中的一致部分與TBox T的并邏輯蘊含，從語法上看!和!′的修復應該是一致的，但是在IAR－語義下對這樣的2個本體的修復可能產生不一樣的結果．為此，文獻［10］中接著提出了ICAR－語義，它們基于ABox關于TBox的一致邏輯封閉，其相關的定義如下：

給定一個本體!＝?"，#?，用HB（!）表示!中的字母構造的基本原子集合，本體!的一致邏輯推論集合記為clc（!），clc（!）＝｛ ｜ ∈HB（!），并且存在公理S #，使得Mod（?T，S?）≠ 且?T，S? ｝．clc（!）是HB（!）的一個子集，由所有HB（!）中與!一致的子集蘊含的公理組成，ICAR－語義的定義構建在clc（!）的基礎上．

定義2．給定一個描述邏輯本體!＝?"，#?，本體!的封閉ABox修復的并（closed intersection ABox repair），記為ICAR－Rep（!），其中!的封閉的ABox修復，記為CAR－Rep，#′滿足下述條件：

1）#′ clc（#）；

2）Mod（?T，#′?）≠ ；

3）不存在#的子集#″，滿足Mod（?T，#″?）≠ ，其中#′ #″ clc（#）．

ICAR－語義下的修復首先計算了ABox中的一致邏輯推理集合，這樣能減少對本體修復時信息的丟失，但是ICAR－語義需要計算本體中整個ABox關于TBox的封閉，在ABox規模很大的情況下，這需要耗費大量的計算．為了盡可能保持本體中的有效信息并減少封閉的計算量，我們提出基于IAR－語義和ICAR－語義的變種來改進這2類不一致容忍語義．

定義3．給定一個DL－LiteFR本體!＝?"，#?，假定#R＝IAR－Rep（!），S＝CAR－Rep（T，#＼#R）．本體!的實用的ABox修復的交（intersection practical ABox repair），記為IPAR－Rep（!）．其中實用的ABox修復（記為PAR－Rep）是成員斷言的一個子集#′，滿足#′＝#R∪S．

定義4．給定一個DL－LiteFR本體!＝?"，#?，解釋I是本體!的IPAR修復模型（IPAR－model），如果存在#′∈IPAR－Rep（!），有I ?T，#′?．本體的IPAR修復模型的集合記為IPAR－Mod（!）．

在定義3和定義4的基礎上，我們將泛化經典的邏輯蘊含概念，定義IPAR語義下的一致蘊含．

定義5．給定一個DL－LiteFR本體!＝?"，#?和一個公理 ，公理 被本體!IPAR一致蘊含（IPAR－entailed，簡稱IPAR－蘊含），如果對于任意一個解釋I∈IPAR－Mod（!）有I ，記為!IPAR．

從定義3可以得到IPAR－Rep（!）＝IAR－Rep（!）∪ICAR－Rep（T，#＼IAR－Rep（!）），IPAR－修復考慮了ABox關于TBox的封閉，能盡可能保留有效的信息且減少了封閉的計算量．

例1．考慮一個軟件項目的組織結構，主要概念有職員（Staff）、項目經理（project management，PM）、程序員（Programmer）、實習生（Trainee）、實習生導師（Trainee－Tutor）．主要角色有管理關系（manages）以及指導關系（hasTutor）．下面給出基于該組織機構的一個簡單的DL－LiteFR本體!＝?"，#?．

根據定義4可以得到IPAR－Rep（!）＝PARRep1∩PAR－Rep2＝｛PM（Li）， manages－（Zhang）｝．

（一）用愛教育學生。得到老師的關愛是每個學生最基本的心理要求，老師要用真摯的愛對待單親家庭學生。在學校里，離異家庭的孩子會用警惕的目光注視周圍的一切，尤其對老師的態度極為敏感，只要稍不注意就可能挫傷他們的自尊心，使他們產生逆反心理或敵對情緒。老師要與學生建立親密信任關系，以平等、信任、尊重的心態，同他們談心，在思想和情感上交流，盡力幫他們解決實際困難，用愛和行動來感化教育學生。

IPAR－語義減少了封閉的計算，但與ICAR－語義相比，兩者的表達能力是相同的，下面我們將討論兩者之間的關系．

定理1．假定!是一個DL－LiteFR的本體，如果#1＝IPAR－Rep（!），#2＝ICAR－Rep（!），那么cl"（#1）＝#2．

證明．假設#1＝#R∪S，這里#R＝IARRep（!），S＝ICAR－Rep（T，#＼#R）．對于任意一個ABox中的斷言α∈cl"（#），如果在ABox中不存在另外一個斷言β導致T∪｛α，β｝是不可滿足的，稱這樣的α為非沖突斷言（non－contradiction assertions）．#2是ICAR－修復語義下的封閉，因此#2是cl"（#）的所有非沖突斷言的集合，從前面的假設可以得到#R則是#的所有非沖突斷言的集合，S是cl"（#＼#R）中的所有非沖突斷言的集合，由于# cl"（#），cl"（#＼#R） cl"（#），因而能得到cl"（#1） #2，即cl"（#1） #2或cl"（#1）＝#2．

假設cl"（#1） cl"（#2），則在ABox中存在一個斷言 ，滿足 ∈#2且 cl"（#R∪S），即是 ∈cl"（#＼#R）但 S．由于S是cl"（#＼#R）中所有的非沖突斷言的集合，從 S中可以得出 不是cl"（#＼#R）中的一個非沖突斷言，但這與 ∈#2矛盾．從上面的分析，可以得出結論cl"（#1）＝#2．證畢．

為了實現在IPAR－語義下的查詢應答，下面將討論在該語義下查詢應答的數據復雜度．

定理2．假定!是一個DL－LiteFR的本體，Q是一個合取查詢的并（UCQ），判定是否滿足!IPARQ的數據復雜度是PTIME．

證明．根據文獻［10］中的定理可以得到在ICAR－修復語義下的UCQ蘊含是易處理的推理任務，即!ICARQ的數據復雜度是PTIME．從定理1能得到IPAR－語義下的封閉與ICAR－語義等價，因此!IPARQ的數據復雜度是PTIME．證畢．

3 本體到圖的轉換

為了實現在圖上完成查詢應答，本節將討論如何將本體轉換成有向圖．給定一個DL－LiteFR的本體!＝?"，#?以及!上的符號集Σ；一個與本體!對應的有向圖記為G＝?V，E?，V是圖上頂點的集合，E是圖上邊的集合，可以通過如下的規則構造：

1）對于Σ中的任意的概念A，V中包含節點A；

2）對于Σ中的任意的角色P，V中包含節點P，P—， P， P—；

5）如果在"中存在公理R1R2，則在有向圖G中有｛R1→R2｝∈E，｛ R1→ R2｝∈E，｛ R－1→ R－2｝∈E并且 R1， R2， R－1， R－2∈V；

6）如果在#中存在公理A（a），則在有向圖G中有｛a→A｝∈E并且a，A∈V；

7）如果在#中存在公理P（a，b），則在有向圖G中有｛a→ P｝∈E，｛b→ P－｝∈E，｛（a，b）→P｝∈E并且a，b，（a，b）， P， P－∈V．

上述構造規則將本體!轉化成了有向圖，圖中的結點對應于本體中的概念、角色或者個體，圖中的有向邊對應到TBox中的包含公理或ABox中的實例斷言．為了便于討論，本文將圖G的傳遞閉包記為G＊＝?V，E＊?．對于圖G上的2個節點X，Y∈V，如果在G上存在X的后續節點X1，X2，…，Xn，并且在G上存在邊?X，X1?，?X1，X2?，…，?Xn－1，Xn?，?Xn，Y?∈E，則稱節點X可達節點Y，記為X｜→GY，這里節點X1，X2，…，Xn，Y都是節點X的子孫節點，節點X的所有子孫節點記為Des（X）．對于任意節點Y∈Des（X），如果Des（Y）＝ ，則稱Y為X的葉子子孫節點，節點X的所有葉子子孫節點記為leafDes（X）．從圖的構建規則可得，本體中的實例個體對應圖上的葉子子孫節點，節點X的實例葉子子孫節點記為iLeafDes（X）．

在本體到圖的轉換中，由于在TBox中可能存在等價關系或相互包含的關系，這導致有向圖中存在強連通分支，增加了計算的復雜性，因而有必要對強連通的有向圖做進一步的處理，圖1所示為本文處理圖中環路的一個示例．

Fig．1 The processing of circuits on the directed graph．圖1 有向圖上環路的處理

圖1的左邊部分為原始的有向圖，強連通分支的計算可以通過Kosaraju－Sharir算法調用2次深度優先遍歷來實現［23］．在獲取了強連通分支后，使用一個節點來代替該強連通分支，最后使用新節點連接原來與強連通分支相連的節點實現對強連通分支的消除．

3．2 推理的等價性

考慮如下一個TBox"＝｛A1A2，A2A3｝，根據推理規則，" A1A3．根據有向圖的構造規則，

4 基于圖的查詢應答方法

4．1 查詢到圖的轉換

DL－Lite下的查詢具有一階邏輯可重寫性的特征，這意味著一個合取查詢q能在TBox下重寫成另外形式的查詢qr且重寫的過程不涉及ABox，而重寫后查詢的執行與TBox無關，但重寫后的查詢往往很復雜，降低了查詢的性能，為此我們考慮在圖上實現對DL－Lite本體的查詢應答．

文獻［11］中通過函數gr（g，I）定義了查詢重寫的規則，算法perfectRef（q，"）則通過函數gr（g，I）完成對查詢q的重寫，限于篇幅，這里不詳細引用．從重寫的規則可以發現，重寫規則就是不斷地將目標概念（角色）的子概念（角色）添加到查詢項中．而概念或角色的包含關系可轉換成圖上節點間的可達性關系，這樣查詢的重寫就可以轉成對圖上子節點的查詢．由于對于知識庫K上的UCQQ而言，查詢應答的結果，因此在討論對UCQ的查詢應答中，我們只考慮對CQ的查詢應答．

為了實現在圖上完成查詢應答的過程，我們將查詢也轉換成圖的形式，查詢在圖上的形式稱為查詢路徑（query path），其構建規則如下：

1）變量和概念名表示為查詢路徑上的一個節點，其中在顯著性變量前置一個問號以示強調；

2）如果查詢項為A（x），則在查詢路徑上添加邊｛x→A｝，邊的屬性值記為ISA，表明x是A的實例；

3）如果查詢項為P（x，y），則在路徑上添加邊｛x→y｝，邊的屬性值為關系名P，表示這2個節點具有關系P，同時添加邊｛x→ P｝和｛y→ P－｝，這2條邊的屬性值為ISA；

4）如果查詢項為P（x，－）或P（－，y），即查詢中存在自由變量，則添加邊｛x→ P｝或｛y→ P－｝，這2條邊的屬性值為ISA．

下面，我們給出基于圖的查詢應答算法（graph based query answering，GBQA）．

例2．已知一個DL－Lite本體!＝?"，#?，其中"＝｛ProfessorTeachersTo，StudentHasTutor， HasTutor－Professor， TeachersTo－Student，Porfessor瓙Student｝．#＝｛Student（John），HasTutor（John，Mary），TeachersTo（Mary，Bill）｝，在此本體上，考慮查詢q（a）←TeachersTo（a，b），HasTutor（b，－）．

首先考慮算法perfectRef，查詢重寫算法perfectRef（q，"）將查詢q（a）重寫成qr（a）＝｛TeachersTo（a，b），HasTutor（b，－）｝∪｛TeachersTo（a，b），Student（b）｝∪｛TeachersTo（a，－）｝∪｛Professor（a）｝∪｛HasTutor（－，a）｝，這樣在對q在本體!上的查詢就可以轉換成qr在#上的查詢，查詢結果為qr中每個查詢項上答集的并，最終查詢答集為ans（qr，#）＝｛Mary｝．

下面考慮基于圖的查詢算法GBQA，算法第①行根據圖的構建規則，將本體轉換成圖，例中的本體!將轉換成如圖2所示的有向圖；算法第②行根據查詢到路徑圖的轉換規則，例中的查詢Q轉換成如圖3所示的查詢路徑圖．

在例2中，算法GBQA行③～⑤獲取查詢路徑圖PQ中的變量節點，獲取與節點關聯屬性值為ISA的概念節點；行⑦～⑧調用函數GetiLeafDes在圖G上計算各概念節點的實例葉子子孫節點，如果某個變量節點關聯多個概念節點，則該變量節點對應的實例節點為這些概念節點的實例葉子子孫節點的交，例2中與變量x關聯屬性為ISA的節點為 TeachersTo，在圖G上其實例葉子子孫節點集合為｛Mary｝，與變量y關聯屬性為ISA的節點為 TeachersTo－和 HasTutor，它們的葉子節點集合分別是｛John，Bill｝和｛Bill｝，它們的交為｛Bill｝；行⑨～⑩處理變量之間通過角色（Role）建立的聯系，在圖G上獲取對應的角色節點的實例葉子子孫節點集合，角色TeachersTo關聯了查詢變量a和b，在圖G中角色TeachersTo的實例葉子子孫節點集合為｛（Mary，Bill）｝；從行 瑏瑡～ 瑐瑡開始處理查詢變量對應的實例集合與2個變量通過角色關聯的實例對集合的關系，計算對應角色的domain和range與對應變量的葉子節點集合的交集，去除不相交部分，ABoX中角色TeachersTo的實例為｛（Mary，Bill）｝，其domain和range與a，b對應的實例葉子子孫節點集合（分別是｛Mary｝，｛Bill｝）存在交集，即查詢結果不為空，算法最后返回顯著變量節點a關聯的集合｛Mary｝．

4．2 不一致容忍語義下的查詢

4．1節將查詢轉換成圖的形式并在圖上完成了整個的查詢應答的過程，本節將考慮在不一致的本體上展開查詢應答，由于不一致的本體能推導出任意的信息，為此，必須解決本體中的不一致性問題．DLLiteFR本體!＝?"，#?不一致的可能原因如下［17］：

1）存在一個不可滿足概念A（或者一個不可滿足角色R）和一個實例d（或者一對實例d1，d2），使得A（d）∈#（或者R（d1，d2）∈#）；

4）存在一個原子角色P和對象實例d1，d2，d3，滿足（funct P）∈"（或者funct P－∈"），而且｛P（d1，d2），P（d1，d3）｝ #（或者｛P（d2，d1），P（d3，d1）｝ #）．

Fig．2 The directed graph Gof ontology!in example 2．圖2 例2中的本體!對應的有向圖G

Fig．3 The query path graph PQof Q．圖3 查詢Q對應的查詢路徑圖PQ

從上面分析可以發現不一致的產生與實例斷言相關，在原因1，2中涉及一個實例斷言．本文假定TBox是協調的，即在TBox中不存在不可滿足概念，故第1個原因后續將不涉及；原因3是存在一個實例同時屬于不相交的概念或角色而導致的不一致；原因4則是違背的函數斷言的約束．結合上述原因，在不一致本體上的查詢應答可以有2種的處理方法，一種是應用非標準的推理方法獲取不一致的本體上的查詢答集，之后去除答集中導致不一致的實例；另一種方法則是增加對查詢項的限制，使得在答集中避免出現不一致以獲取一致的查詢答集．本文將遵循后一種方法的思路，應用不一致容忍語義來避開答集中的不一致．為此，先給出定義來描述圖上的不一致性．

定義6．給定一個DL－Lite本體!＝?"，#?構建的有向圖G＝?V，E?，如果存在一個實例節點a或（a，b）到2個不相交的概念節點?A，瓙A?或不相交的角色節點?R，瓙R?之間的路徑對，稱這樣的路徑對為不一致路徑對（inconsistency path－pair），記為IPP（a，A，瓙A）或IPP（（a，b），R，瓙R）．

受文獻［17］工作的啟發，結合本體不一致的原因，我們在圖上定義一系列函數來描述可能查詢到的不一致的信息．

假設A是本體!＝?"，#?構建的圖G＝?V，E?中的一個概念節點，t為查詢中的一個常量或者變量，我們定義如下函數來判斷t與A在圖G上的一致性關系：

在此2個函數的基礎上，我們增加對查詢項的限制來避免查詢答集中返回不一致的信息，這里對查詢項的限制通過擴展查詢項來實現．對于一個原子概念B，如果它出現在查詢項中，為避免與B不相交的概念在實例部分可能產生的不一致，我們定義如下函數：

NotDisjClashGB（t）＝∧瓙（A（t）∧ConsAtomGA（t）），

A∈｛A｜B∈Des（瓙A）＼iLeafDes（瓙A）｝．

對于一個原子角色P，如果它出現在查詢項中，為了避免與P不相交的角色引起答集的不一致，我們定義如下函數：

從第2節的介紹中可知，不一致容忍語義下本體的TBox部分均是保持不變，但ABox部分則有變換在ICAR－語義下要計算ABox關于TBox的封閉，對應于圖則是計算所有的實例葉子節點在圖上的傳遞閉包；而IPAR－語義具有和它一樣的表達能力，但該語義下只需計算沖突部分的閉包．因此在ICAR－語義和IPAR－語義下的查詢，兩者對查詢的限定性擴展并沒有不同，不同在于ABox在TBox約束下的封閉的計算．G（，）

5 實驗評估

實驗將比較基于ICAR－語義的一致性查詢方法［17］與本文基于圖的IPAR－語義下的一致性查詢應答的效率，對比在不同的本體規模下各查詢的執行效率．實驗的實現引用了多個開源的軟件包，其中，對本體的解析引用了OWLAPI，轉換后的圖的存儲引用了neo4j圖數據庫．neo4j是一個開源的、高效的NOSQL圖數據庫系統．實驗的軟硬件環境如下：處理器為Intel Core i5－2400 3．1GHz，Java的堆的大小為6GB，Java虛擬機的版本為1．7．0＿55，OWLAPI的版本為3．4．3①，neo4j的版本為2．1②．

實驗使用UOBM［24］大學本體數據生成工具（UOBM Generator③）來生成實驗所需的本體數據，由于UOBM的基準本體中沒有否定包含的公理且生成的是一致性的數據，為了獲取實驗所需的不一致本體數據，預處理時對UOBM的基準本體做了適度的處理，在保證本體的TBox一致的前提下，向TBox中插入不相交公理，之后使用UOBM數據生成器生成大學本體的ABox部分，同時生成不相交公理中的概念對或角色對的實例斷言集合，將這些實例斷言添加到ABox中，這樣能生成不一致的本體．最終將修改后的本體存儲到neo4j圖數據庫中．本文的實驗中使用UOBM generator生成4組大學本體，本體的基本信息如表2所示：

Table 2 Experimental Ontologies表2 實驗中本體的基本信息

對于基準查詢的選擇，我們根據文獻［24］附錄所提供的備選查詢以及文獻［25］中的做法，選用了如下8個合取查詢：

①http：??owlapi．sourceforge．net

②http：??neo4j．com

③http：??www．cs．ox．ac．uk?isg?tools?UOBMGenerator

實驗結果如表3所示，可以發現，ICAR－語義下的查詢應答方法的執行效率要低于基于圖的IPAR－語義下的查詢應答方法．總體看來，查詢越復雜，查詢耗費的時間就越多；目標本體的規模越大，查詢耗費的時間也越多．

Table 3 Time Required to Execute Query Answering Under ICAR－Semantic and IPAR－Semantic表3 ICAR－語義和IPAR－語義下一致性查詢方法的執行時間ms

Fig．4 Time required to execute query answering under different scales．圖4 在不同規模的本體下查詢的執行時間

為了更加直觀地對比，我們將表3中的實驗結果以圖的形式表現，各查詢在不同規模的本體下的執行對比結果如圖4所示．從圖4可以看到，在較復雜的查詢中，如Q7，Q8兩個查詢方法的差異比較明顯，這主要由于在ICAR－語義下復雜查詢的重寫規模也更復雜，而基于圖的方法并不需要做查詢的重寫；對于比較簡單的查詢，如Q5，由于涉及的查詢空間比較小，因而兩者之間的差異并不明顯，且隨ABox規模的增加，對應答集中的實例斷言并沒有線性的增加，這樣查詢的執行時間并沒有隨規模的增加而顯著的變化．

為了更好地呈現隨規模對變化查詢的變化情況，我們繪制同一查詢在不同規模下執行時間的變化，如圖5所示：

Fig．5 Time required to execute query answering over variation of ontology scales．圖5 查詢的執行時間隨本體規模變化圖

圖5中選擇了查詢Q5～Q8，其中Q5，Q6是簡單的查詢，只包括顯著性變量；而Q7，Q8是復雜的查詢，包括非顯著性變量．從圖5可以看出，簡單的查詢隨本體規模的增加，在2個方法下執行時間的增量都比較類似；但在復雜的查詢下，隨本體規模的增加，ICAR－語義下的查詢執行時間的增量曲線要比IPAR－語義下的查詢增量曲線陡，說明IPAR－語義下的方法要比ICAR－語義下的方法更加穩定、有更好的伸縮性、更加適合于大規模的本體環境．

6 總結與展望

本文介紹了2種經典的不一致容忍語義，IAR－語義和ICAR－語義，在這2種語言的基礎上，我們定義一種新的不一致容忍語義——IPAR－語義，并考慮基于新的語義來實現不一致本體上的一致性查詢應答．由于對查詢重寫可能導致查詢變得又大又復雜，為此，我們基于圖實現了一種針對DL－Lite查詢應答方法．首先，DL－Lite本體和查詢根據不同的規則被轉換成圖；之后應用IPAR－語義增加對查詢項的限制來避免導致不一致的原因，實現一致性的查詢應答任務；最后通過實驗對比基于ICAR－語義的一致性查詢方法與基于圖的IPAR－語義下的一致性查詢方法的效率．實驗結果表明，本文基于圖的查詢應答方法在效率上要優于對比方法，特別是在本體規模較大的情況下，2類查詢應答算法的運行效率的差異尤為明顯．

下一步的工作，我們考慮將本文查詢應答方法推廣到表達力更強的描述邏輯語言；同時為了提供查詢的效率，將來考慮應用并行的、分布式的技術來實現增量式的查詢應答任務．

［1］Gruber T R．A translation approach to portable ontology specifications［J］．Knowledge Acquisition，1993，5（2）：199 220

［2］Wan Changlin，Shi Zhongzhi，Hu Hong，et al．QoS－Aware semantic Web service modeling and discovery［J］．Journal of Computer Research and Development，2011，48（6）：1059 1066（in Chinese）（萬長林，史忠值，胡宏，等．基于本體的語義Web服務QoS描述和發現［J］．計算機研究與發展，2011，48（6）：1059 1066）

［3］Jia Cunxin，Hu Wei，Bo Wenyang，et al．SMap：Semantically mapping relational database schemas to OWL ontologies［J］．Journal of Computer Research and Development，2012，49（10）：2241 2250（in Chinese）（賈存鑫，胡偉，柏文陽，等．SMap：基于語義的關系數據庫模式與OWL本體間映射方法［J］．計算機研究與發展，2012，49（10）：2241 2250）

［4］Console M，Lenzerini M．Data quality in ontology－based data access：The case of consistency［C］??Proc of the 28th AAAI Conf on Artificial Intelligence（AAAI）．Menlo Park，CA：AAAI，2014：1020 1026

［5］Carnielli W A，Marcos J．Ex contradictione non sequitur quodlibet［J］．Bulletin of Advanced Reasoning and Knowledge，2001，1：89 109

［6］Zhou Liping，Huang Houkuan，Qi Guilin，et al．An algorithm for calculating minimal unsatisfiablility－preserving subsets of ontology in DL－Lite［J］．Journal of Computer Research and Development，2011，48（12）：2334 2342（in Chinese）（周麗平，黃厚寬，漆桂林，等．一種在DL－Lite中計算本體最小不可滿足保持子集的算法［J］．計算機研究與發展，2011，48（12）：2334 2342）

［7］Schlobach S，Cornet R．Non－standard reasoning services for the debugging of description logic terminologies［C］??Proc of the 18th Int Joint Conf on Artificial Intelligence（IJCAI）．San Francisco，CA：Morgan Kaufmann，2003：355 362

［8］Zhang Xiaowang，Xiao Guohui，Lin Zuoquan，et al．Inconsistency－tolerant reasoning with OWL DL［J］．Int Journal of Approximate Reasoning，2014，55（2）：557 584

［9］Bertossi L E，Hunter A，Schaub T．Introduction to inconsistency tolerance［G］??LNCS3300：Inconsistency Tolerance 2005．Heidelberg：Springer，2005：1 14

［10］Lembo D，Lenzerini M，Rosati R，et al．Inconsistencytolerant semantics for description logics［C］??Proc of the 4th Int Conf on Web Reasoning and Rule System．Heidelberg：Springer，2010：103 117

［11］Calvanese D，De Giacomo G，Lembo D，et al．Tractable reasoning and efficient query answering in description logics：The DL－Lite family［J］．Journal of Automated Reasoning，2007，39（3）：385 429

［12］Muro M R，Calvanese D．High performance query answering over DL－Lite ontologies［C］??Proc of the 13th Int Conf on Principles of Knowledge Representation and Reasoning（KR）．Menlo Park，CA：AAAI，2012：308 318

［13］Chortaras A，Trivela D，Stamou G B．Optimized query rewriting for OWL 2QL［C］??Proc of the 23rd Int Conf on Automated Deduction．Heidelberg：Spring，2011：192 206

［14］Venetis T，Stoilos G，Stamou G B．Incremental query rewriting for OWL 2QL［C］??Proc of the 25th Int Workshop on Description Logics．North Rhine－Westphalia：CEUR－WS，2012：356 366

［15］Konstantinidis G，Ambite J L．Scalable query rewriting：A graph－based approach［C］??Proc of the ACM SIGMOD Int Conf on Management of Data．New York：ACM，2011：97 108

［16］Qin Biao，Wang Shan，Du Xiaoyong，et al．Graph－based query rewriting for knowledge sharing between peer ontologies［J］．Information Sciences，2008，178（18）：3525 3542

［17］Lembo D，Lenzerini M，Rosati R，et al．Query rewriting for inconsistent DL－Lite ontologies［C］??Proc of the 5th Int Conf on Web Reasoning and Rule Systems（RR）．Heidelberg：Spring，2011：155 169

［18］Rosati R，Ruzzi M，Graziosi M，et al．Evaluation of techniques for inconsistency handling in OWL 2QL ontologies［C］??Proc of the 11th Int Semantic Web Conference（ISWC）．Heidelberg：Spring，2012：337 349

［19］Lembo D，Santarelli V，Savo D F．Graph－based ontology classification in OWL 2QL［C］??Proc of the 26th Int Workshop on Description Logics．North Rhine－Westphalia：CEUR－WS，2013：747 759

［20］Gao Sibei，Qi Guilin，Wang Haofen．A new operator for ABox revision in DL－Lite［C］??Proc of the 26th AAAI Conf on Artificial Intelligence．Menlo Park，CA：AAAI，2012：2413 2424

［21］Fu Xuefeng，Zhang Yong，Qi Guilin．A graph－based approach to ontology debugging in DL－Lite［C］??Proc of the 4th Joint Int Conf on Semantic Technology．Heidelberg：Spring，2014：33 46

［22］Arenas M，Bertossi L E，Chomicki J．Consistent query answers in inconsistent databases［C］??Proc of the 18th ACM SIGACT－SIGMOD－SIGART Symp on Principles of Database Systems．New York：ACM，1999：68 79

［23］Sharir M．A strong－connectivity algorithm and its applications in data flow analysis［J］．Computers and Mathematics with Applications，1981，7（1）：67 72

［24］Ma Li，Yang Yang，Qiu Zhaoming，et al．Towards a complete OWL ontology benchmark［C］??Proc of the 3rd European Semantic Web Conf（ESWC）．Heidelberg：Spring，2006：125 139

［25］Du Jianfeng，Qi Guilin，Shen Yidong．Weight－based consistent query answering over inconsistent SHIQ knowledge bases［J］．Knowledge Information System，2013，34（2）：335 371

Fu Xuefeng，born in 1978．PhD candidate．Student member of China Computer Federation．His main research interests include semantic Web，ontology debugging，ontology revision，and inconsistency handling．

Qi Guilin，born in 1977．Professor and PhD supervisor．Member of China Computer Federation．His main research interests include knowledge representation，semantic Web，reasoning under uncertainty，inconsistency handling，etc．

Zhang Yong，born in 1989．Master in the School of Computer Science and Engineering，Southeast University．His main research interests include ontology mapping and ontology debugging．

A Graph－Based Approach for Query Answering Under Inconsistency－Tolerant Semantics

Fu Xuefeng，Qi Guilin，and Zhang Yong
（School of Computer Science and Engineering，Southeast University，Nanjing210096）

Inconsistency often occurs during ontology evolution，and leads to the invalidity of standard reasoning．To tackle this problem，inconsistency－tolerant semantics can be provided for the target language．However，ill－defined inconsistency－tolerant semantics may cost massive calculation and result in losing valuable information．In this paper，a variant of classical inconsistency－tolerant semantics is proposed，named IPAR－semantics．The newly defined inconsistency－tolerant semantics can avoid computing the closure of an ABox w．r．t．the corresponding TBox，thus can reduce the computation time and reserve as much information as possible．Based on the newly defined inconsistency－tolerant semantics，we further propose an approach for consistent query answering based on graph．In our approach，the given ontology and the target query are both transformed into graphs by different rules and stored into graph database．The IPAR－semantics ensure that the inconsistent instances cannot be included in the answering of query and the new approach can avoid redundant rewritings of a user query．Finally，We conduct comparative experiments on the ontologies generated by UOBM generator．In the experiments，we implement the query answering system under IPAR－semantics using our graph－based approach and compare it with the query answering approach under ICAR－semantics．The experimental results show that our approach outperforms in both efficiency and scalability．

ontology；inconsistency－tolerant；DL－Lite；graph；query answering

TP391

2015－09－21；

2015－11－06

國家“八六三”高技術研究發展計劃基金項目（2015AA015406）；國家自然科學基金項目（61272378）；江西省教育廳科研項目（GJJ12643）

This work was supported by the National High Technology Research Program of China（863Program）（2015AA015406），the National Natural Science Foundation of China（61272378），and the Foundation of Jiangxi Educational Committee（GJJ12643）．