基于图的不一致容忍语义下的查询应答方法

付雪峰 漆桂林 张 勇

（东南大学计算机科学与工程学院 南京 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）．