2:Buy-Vehicle等，包含复合元素的异构桥规则如1:∃WorkAt.University2:Staff，1:PlayBall
2:PlayBasketball
PlayFootball，1:Carnivore
Canidae2:HouseDog，1:Professor2:∃WorkAt.University等还没有涉及过，如图1所示.考虑到现实世界中语义映射的多样性，该问题的研究具有重要的理论价值和实用价值.赵晓非1,2,3史忠植2冯志勇3
1(天津工业大学计算机科学与软件学院 天津 300387)2(中国科学院计算技术研究所智能信息处理重点实验室 北京 100190)3(天津大学计算机科学与技术学院 天津 300072)
摘要桥规则为分布式动态描述逻辑(distributed dynamic description logics, D3L)提供了描述语义映射和知识传播的重要机制.现有的研究仅针对包含原子元素的同构桥规则.将研究扩展到了被包含端存在复合元素的异构桥规则的D3L推理问题.定义了分布式知识库的正则性.通过对桥规则进行形式变换并针对不同情形转换为已有的语言机制，提出了将动态描述逻辑DSROIQ作为局部本体语言的D3L知识库转换为单一DSROIQ知识库的算法，接着研究了该转换的性质，证明了该算法可以在多项式时间内终止、算法的目标知识库与原始知识库在可满足性上是等价的，进而证明了在上述桥规则存在的情况下正则D3L知识库的集中式推理具有与单一DSROIQ知识库推理相同的最坏时间复杂度.该算法使得D3L推理可以获得与现有的分布式推理方法相同的最坏时间复杂度并且解决了后者难以处理异构复合桥规则的问题.
关键词分布式动态描述逻辑;异构桥规则;正则性;集中式推理;计算复杂度
在信息集成、服务集成以及语义Web等大量的分布式应用中，人们常希望本体是分块的或分布式的，而不是单一的本体；大规模本体的模块化具有更强的针对性、更高的推理效率[1].上述2个原因使得分布式、模块化本体[2-3]成为近几年的研究热点之一.多种的逻辑基础被相继提出，如ε-连接框架[4]、保守扩展的分布式本体框架[5]、分布式一阶逻辑[6]以及基于包的描述逻辑等.作为其中的一个重要的研究分支，分布式动态描述逻辑(distributed dynamic description logics, D3L)[7]引入了语义映射的描述机制、本体间知识的传播机制以及面向分布式环境的推理机制.D3L很好地满足了每个局部信息系统希望保持一定程度的自治及自己的用户界面而从其他局部信息系统导入和重用知识的需求，因而为上述应用提供了较完备的逻辑基础.
本体间元素的映射和推理是模块化本体要解决的核心问题.由于现实世界中语义映射的多样性，其逻辑基础必须能够建模异构元素之间的映射并进行推理.不幸的是，现有的研究对此均没有提供足够的支持.以ε-连接框架为例，尽管该框架提供了基于消解的分布式推理算法，但通过ε-连接构造的映射仅限于不同本体的概念之间，因而无法实现异构元素之间的映射和推理.保守扩展的分布式本体框架所提供的推理仅适用于本体之间具有签名依赖性的情形，不符合改约束条件的映射均无法被描述和推理，并且该框架仅从理论上证明了签名依赖性问题是可判定的，并没有提供推理算法.
D3L的桥规则机制为解决异构语义映射的描述和推理问题提供了可能.针对映射关系的多样性，D3L不仅提供了描述同构元素语义映射(如概念间的相互映射、动作间的相互映射和角色间的相互映射)的同构桥规则，而且提供了异构桥规则用以描述异构元素之间的语义映射，比如可以将1个概念映射到动作或将1个动作映射到概念.在先前的工作中，我们对同构桥规则的推理问题进行了初步研究，其中仅涉及了原子元素，如1:BuyCar2:Buy-Vehicle等，包含复合元素的异构桥规则如1:∃WorkAt.University2:Staff，1:PlayBall2:PlayBasketballPlayFootball，1:CarnivoreCanidae2:HouseDog，1:Professor2:∃WorkAt.University等还没有涉及过，如图1所示.考虑到现实世界中语义映射的多样性，该问题的研究具有重要的理论价值和实用价值.
鉴于此，本文将研究扩展到了被包含端存在复合元素的异构桥规则情况下的D3L推理问题.由于分布式Tbox是D3L知识库最基本的形式，为了获得分布式Tbox的可判定性，首先给出了其正则性的定义.而后针对将动态描述逻辑DSROIQ作为局部本体语言的D3L知识库，通过对桥规则进行必要的形式变换以及区分不同情形转换为已有的语言机制，提出了将分布式知识库转换为单一DSROIQ知识库的算法.接着我们对转换算法的性质进行了研究.证明了算法可以在多项式时间内终止、算法的目标知识库与原始知识库在可满足性上是等价的，进而证明了在上述桥规则存在的情况下正则D3L知识库的集中式推理具有与单一DSROIQ知识库推理相同的最坏时间复杂度.本文的算法使得D3L推理可以获得与现有的分布式推理算法相同的最坏时间复杂度并且解决了后者难以处理异构复合桥规则的问题.
Fig. 1 Sample for heterogeneous composite bridge rules
图1 异构复合桥规则示例
限于篇幅，在此仅对与本文联系密切的D3L 相关部分进行简要阐述，更详细的信息请参考文献[8].首先介绍动态描述逻辑DSROIQ中的概念、角色和动作，然后介绍DSROIQ之上的分布式知识库及其解释的相关知识.
定义1. DSROIQ的概念是下述情形之一的表达式：
⊥|
|A|
C|CD|CD|{a}|∀R.C|
∃R.C|∃S.Self|≤nS.C|≥nS.C，
其中,A表示原子概念;C，D表示普通概念;a表示个体;R，S表示角色;n为正整数.
DSROIQ允许角色之间进行2种运算：连接运算和逆运算.R∘S表示角色R和S的连接;而S-表示角色S的逆.DSROIQ的角色包含公理(RIA)是形如S1∘S2∘…∘Sn
R的表达式.RIA的集合可以构成角色层次.给定局部TboxTB以及个体t，u，从t到u的路径是角色的1个非空序列R1(x1，x2)，R2(x2，x3)，…，Rn(xn，xn+1)∈TB，其中x1=t，xn+1=u且xi≠xi+1，1≤i≤n.如果不存在起始于个体t的路径，则称t为终端;如果不存在终止于个体t的路径，则称t为始端.
定义2. 如果1个角色层次中的角色之间存在满足2个条件的偏序关系
：
1)SR当且仅当S-R；
2) 每个RIA是满足SiR，i=1，2，…，n的下列表达式之一：R∘RR，R-R，S1∘S2∘…∘SnR，R∘S1∘S2∘…∘SnR，S1∘S2∘…∘Sn∘RR,则称该角色层次是正则的.
定义3. DSROIQ的原子动作α=(P，E)定义如下：
1)α为原子动作名；
2)P是由公理组成的有限集合，表示动作执行前必须满足的前提条件；
3)E是由公理组成的有限集合，表示执行该动作后将会发生的影响.
D3L知识库[9]的最基本形式——分布式Tbox由局部Tbox的集合和提供局部Tbox之间映射的桥规则的集合构成，每个局部Tbox建立在独立的动态描述逻辑语言之上.DSROIQ之上的分布式Tbox的定义如下：
定义4. 给定非空的标号集合I，概念名的集合
角色名的集合
以及动作名的集合
之上的1个分布式Tbox是1个2元式
{Ti}i∈I，BR
，其中每个局部TboxTi建立在DSROIQ之上，并且由NCi，NRi，NAi之上的包含公理构成，
每个BRij是从Ti到Tj且属于下列情况之一的桥规则的集合：
i：Cj：D(into-概念(或动作)桥规则)；
i：Cj：D(onto-概念(或动作)桥规则)；
i：Rj：S(into-角色桥规则)；
i：Rj：S(onto-角色桥规则).
分布式TboxDTB的1个解释I={Ii}i∈I，{rij}i，j∈I，i≠j，其中{Ii}i∈I是局部解释的集合，{rij}i，j∈I，i≠j是领域关系的集合.对于每个i∈I，有
每个领域关系rij是
的子集且有rij(d)={d′|d，d′∈rij}.
定义5. 解释I满足分布式TboxDTB中的元素或公理(记为I
·)，当且仅当I满足11种情形(i，j∈I)：
1) Ii：Cj：D，如果
⊆
成立；
2) Ii：Cj：D，如果⊇成立；
3) Ii：Rj：S，如果
⊆
成立；
4) Ii：Rj：S，如果⊇成立；
5) Ii：CD，如果IiCD成立；
6) Ii：RS，如果IiRS成立；
7) ITi，如果IiTi成立；
8) IBR，如果对任意br∈BR，Ibr；
9) IDTB，如果对任意i∈I，ITi并且IBR；
10)DTBi：CD，如果对任意解释I，IDTB成立蕴含Ii：CD成立；
11)DTBi：RS，如果对任意解释I，IDTB成立蕴含Ii：RS成立.
如果IDTB，则称I是DTB的1个模型.
Fig. 2 Sample for the regularity of distributed Tbox
图2 分布式Tbox的正则性示例
Horrocks等人[10]对SROIQ进行了系统的研究，发现SROIQ的正则Tbox——即仅允许存在正则角色层次的Tbox——的基本推理问题是可判定的.引入动作理论之后，Chang等人[11]的研究表明动作理论的引入并不改变原有描述逻辑推理问题的可判定性.为了获得以DSROIQ作为局部本体语言的DTB的可判定性，我们对定义2进行扩展，得到分布式Tbox正则性的定义.
定义6. 如果1个分布式TboxDTB的角色层次中的角色之间存在满足3个条件的偏序关系：
1)SR当且仅当S-R；
2) 每个RIA是满足SiR，i=1，2，…，n的下列表达式之一：R∘RR，R-R，S1∘S2∘…∘SnR，R∘S1∘S2∘…∘SnR，S1∘S2∘…∘Sn∘RR；
3) 对于形为BR(x，y)或R(x，y)B(B为复合元素)的任意桥规则，令S(z，v)是B中的任意1个角色，S(z，v)属于3种情形之一：
①v到y不存在路径；
②SR；
③S=R(即B中存在R(z，v))，但不存在R(z′，v′)满足v′到y之间有路径，且若x=z则B中不存在C(x)，若y=v则B中不存在C(y)，
则称该分布式TboxDTB是正则的.
简言之，分布式Tbox的正则性是对分布式Tbox角色层次的一种限定.前2个条件限定了局部Tbox角色之间的关系.其中条件1规定了角色的逆运算不改变其在角色层次中的位置次序;条件2规定了角色的连接运算和逆运算的结果范围，由于DSROIQ仅支持上述2种角色运算，因此该条件实际上确保了角色层次的封闭性;条件3对桥规则的形式进行了限定，桥规则两端的角色除非位于角色层次的不同分支上(由情形①指定)，否则必存在1条从包含端到被包含端且无重复状态的路径(由情形②③指定)，从而将正则性推广到了分布式本体.以图2为例进行说明.图2(a)给定桥规则ProfessorOfTeaches及2条断言，角色ProfessorOf和角色Teaches位于角色层次的不同分支(由于从Stu1到Stu2不存在路径)，因此满足定义6的情形①.给定图2(b)中的桥规则及断言，由于从Stu1到Stu2存在由角色Classmate构成的路径而且ProfessorOf在层次中先序于Teaches的关系已明确，因此满足情形②的限制.相反，图2(c)中桥规则的两端具有相同的角色并且存在从Stu1到Stu2的角色路径Classmate(Stu1，Stu2)，由于同时存在Teaches(Prof2，Stu3)以及从Stu3到Stu2的角色路径Classmate-(Stu3，Stu1)∘Classmate(Stu1，Stu2)，因而图2(c)违背了正则性的要求，但删除断言Classmate(Stu1，Stu3)的结果将使正则性将得以保持.
有关正则性更详细的信息请参阅形式语言与自动机的相关知识.
定理1. 任意将DSROIQ作为局部本体语言的D3L桥规则BH都可以转化为语义等价的桥规则
且满足：1)若H=R(x，y)，则B′中的所有路径均被包含于1个单一的最大路径中并且y是该最大路径的终端；2)若H=C(x)，则B′中不存在路径.
证明. 仅需证明通过有限步骤可以构造出语义等价的桥规则B′H即可.将B转换为B′：
步骤1. 初始化B′=B；
步骤2. 对于B′中每个变元x，令{C1(x)，C2(x)，…，Cn(x)}代表B′中所有引用x的概念公理的集合，迭代计算B′=B′\{C1(x)，C2(x)，…，Cn(x)}∪{(C1C2…Cn)(x)}；
步骤3. 对于B′中的每个角色公理R(x，y)，若y是B中路径的终端且H不是将y作为第2个个体变元的角色公理，则迭代计算B′=B′\{R(x，y)，D(y)}∪{∃R.D(x)}，其中D代表B中所有以y作为个体变元的概念，若B中不存在这样的概念则令D=.
步骤1～3在每次迭代过程中对B′中的角色公理的数目进行约简，显然会在有限步骤内结束，而且迭代过程结束后，B′中所有路径的终端个体只能是作为H中角色公理的第2个参数出现的个体，因此所有路径都终止于该终端个体.如果H=C(x)则按照上述步骤，所有路径都已被约简去除，因此B′中不存在任何路径.
步骤1概念合并是语义等价的转换.对于步骤2的转换，在迭代计算过程中，被消除的终端个体变元y是至多在1个概念公理中出现但不在H中出现的变元(因为它既不是H中角色的第2个变元也不是B中的始端变元)，因此每1次迭代的结果与之前的规则语义上是也是等价的，最终可知和BH在语义上是等价的.
证毕.
以桥规则worksAt(x，y)University(y)supervises(x，z)PhDStudent(z)profOf(x，z)为例，其中B=worksAt(x，y)University(y)supervises(x，z)PhDStudent(z)经过转换，得到的B′=∃worksAt.University(x)supervises(x，z)PhDStudent(z)，其中z为单一的最大路径的终端.
由于桥规则本质上描述的是跨本体的包含关系，因此尽管定理1针对的是into-桥规则的情形，对于onto-桥规则同样有类似的结果，可对被包含端进行同样的转换，其证明思路与定理1类似，此处不再赘述.
根据定理1可知，复合桥规则的角色路径均可等价转换为单一的线性路径，其中每个个体变元均属于该最大路径的一部分.文中我们假定所处理的桥规则均具有定理1等价变换后的形式.
在定理1的基础上，通过全面考虑构成异构复合桥规则的不同形式，我们研究了异构复合桥规则的转换语义并给出了分布式知识库的转换算法.该算法可以将DSROIQ作为局部本体语言的D3L知识库转换为单一的DSROIQ知识库.
算法1. D3L知识库的转换算法.
输入：以DSROIQ作为局部本体语言的分布式知识库DTB：{Ti}i∈I，BR；
输出：单一的DSROIQ知识库TBBR.
步骤1. 初始化TBBR=∅，初始化剩余桥规则的集合BR′=BR；
步骤2. 若BR′=∅，则令TBBR=TBBR∪{Ti}i∈I，输出TBBR，算法结束；
步骤3. 在BR′中取出1条桥规则BH(或HB)；
步骤4. 分5种情形判断：
1) 若B中存在引用同1个体变元z的2个概念公理D(z)和D′(z)，则将两者从B中删除并将(DD′)(z)加入B中；
2) 若H=C(x)且B=D(x)，则将该桥规则从BR′中删除并将DC加入TBBR；
3) 若H=R(x，y)且B形如{R1(x，x2)，R2(x2，x3)，…，Rn(xn，y)}，则将该桥规则从BR′中删除并将R1∘R2∘…∘RnR加入TBBR；
4) 若H=R(x，y)且B中存在D(z)满足z出现在B或H的角色公理(第1参数或第2参数均可)中，则执行3步骤：
① 引入新角色S，将D=∃S.Self加入TBBR；
② 引入新变元z′，将角色公理S(z，z′)加入B，将每个角色公理T(x′，z)∈B替换为T(x′，z′)，将每个角色公理T(z，y′)∈B替换为T(z′，y′)；
③ 将D(z)从B中删除，若z=y则将H替换为R(x，z′)；
5) 若H=C(x)或H=R(x，y)且B中存在D(z)满足z既不出现在H中也不出现在B的任意角色公理中，则执行2步骤：
① 引入新变元u，若存在R(x，t)∈B则令u=y，否则令u=x；
② 将B中D(z)替换为∃U.D(u)，其中U为全局角色；
步骤5. 跳转到步骤2.
算法1从剩余桥规则的集合BR′中依次取出桥规则进行处理，直至BR′为空，算法1终止.在处理每条桥规则的过程中，分5种情形处理.其中桥规则经过情形1、情形4和情形5进行转换和约简，直到满足情形2或情形3时被最终从BR′中删除.下面我们分析一下这5种情形是否涵盖了所有可能的情况.我们可以通过桥规则的形式若不满足情形1～4,则必然满足情形5的思路来进行证明.假定情形1～4的前提条件均不满足，由于桥规则的包含端为非复合元素，因此H无外乎2种情况：H=C(x)或H=R(x，y).如果H=C(x)，根据定理1可知B中不存在角色公理，即B中只能是概念公理.由于情形2的前提条件不满足，即B不是D(x)的形式，则必有D(z)∈B存在，且z既不出现在H中也不出现在B的任意角色公理中，情形5的前提得以满足.如果H=R(x，y)，根据定理1可知B中的所有路径均被包含于1个单一的最大路径中且y是该最大路径的终端.由于情形3的前提条件不满足，即B不具备R1(x，o1)，R2(o1，o2)，…，Rn-1(on-2，on-1)，Rn(on-1，y)的形式，因此必有概念公理D(z)∈B存在.再根据假设，情形4的前提条件不满足，也就是z不出现在B和H的角色公理中，因此情形5的前提条件得以满足.通过上述分析可知，无论H=C(x)或H=R(x，y)，如果桥规则的形式不满足情形1～4，则必然满足情形5，因此算法所区分的5种情形涵盖了所有可能的情况.
下面通过实例对算法的执行加以说明.以2.2节中的桥规则为例，详细的中间结果列于表1中.经过算法1的转换，最终可得3条DSROIQ公理(其中S1，S2为新引入的辅助角色)：S1∘supervises∘S2profOf;∃worksAt.University≡∃S1.Self;PhDStudent≡∃S2.Self.
Table1SamplefortheTransformationofBridgeRules
表1桥规则转换示例
OperationBridge RuleTBBROperation DescriptionInitial state∃worksAt.University(x)supervises(x,z)PhDStudent(z)→profOf(x,z)∅Preconditions of cases 1～3, and case 5 are not satisfied, only case 4 can be applied.After applyingcase 4S1(x,x′)supervises(x′,z)PhDStudent(z)→profOf(x,z)∃worksAt.University≡∃S1.SelfPreconditions of cases 1～3, and case 5 are not satisfied, only case 4 can be applied.After applyingcase 4S1(x,x′)S2(z,z′)supervises(x′,z)→profOf(x,z′)∃worksAt.University≡∃S1.SelfPhDStudent≡∃S2.SelfPreconditions of cases 1～2, and ca-ses 4～5 are not satisfied, only case 3 can be applied.After applyingcase 3∅∃worksAt.University≡∃S1.SelfPhDStudent≡∃S2.SelfS1supervisesS2profOfFinal state
下面我们对算法1的性质以及复杂桥规则情况下D3L集中式推理的计算复杂度问题进行研究.定理2阐述了算法1的时间复杂度问题.定理3阐述了算法1输出的目标知识库TBBR与原始知识库DTB在可满足性上是等价的.定理4阐述了DTB的正则性与TBBR正则性的关系,进而证明了复合桥规则存在的情况下D3L的集中式推理具有与单一DSROIQ知识库推理相同的最坏时间复杂度.
定理2. 算法1将在多项式时间内终止.
证明. 显然算法1的单个步骤均可在线性时间内完成，因此对算法总体时间复杂度有影响的只有每个步骤执行的次数.下面对每步所执行的次数进行分析.步骤1～3可以在多项式数目步骤内完成，我们主要分析步骤4.情形1和情形4约简了桥规则中概念公理的个数.由于在约简过程中并不引入新的概念公理，因此对于每个概念公理，无论是情形1或情形4至多执行1次.情形2～3约简了桥规则的个数，同样可以在多项式步骤数内结束.情形5约简了概念公理的个数，这些公理不存在出现在桥规则的包含端中的个体变元.由于在情形5的执行过程中并不引入此种概念公理因此可以在多项式步骤数内结束.
综上所述，算法1将在多项式时间内终止.
证毕.
定理3. 算法1输出的知识库TBBR与DTB具有相同的可满足性.
证明. 要证明TBBR与DTB具有相同的可满足性，可以归纳地证明算法的每步转换都不改变可满足性即可.令TB0
BR0和TB1BR1分别代表1个转换步骤执行之前和之后的TBBRBR′，我们需要证明TB∪TB0∪BR0和TB∪TB1∪BR1具有相同的可满足性.
情形1～3均为等价替换，不会改变转换前后的知识库可满足性.
对于情形4，由于TB1=TB0∪{D≡∃S.Self}，而S为新引入的角色(不存在不可满足的问题)，因此TB∪TB0∪BR0与TB∪TB1∪BR0具有相同的可满足性.下面分析TB∪TB1∪BR0与TB∪TB1∪BR1是否具有相同的可满足性.令B0H0和B1H1分别表示转换之前和之后的桥规则，我们从2个方向进行证明.先证明若TB∪TB1∪BR0是可满足的(即存在解释ITB∪TB1∪BR0)，则TB∪TB1∪BR1也是可满足的.根据假设可知对于任意变元赋值π均有(B0H0)I，π为真.若π(z)∉DI或π(z)≠π(z′)，即
为假，则显然(B1H1)I，π为真，因此我们只需要考虑为真的情况就可以了.通过B1的构造过程可知若为真则
也为真，考虑到假设(B0H0)I，π为真，可知
为真，从而可得
为真，进而可得(B1H1)I，π为真.由于TB∪TB1∪BR0中其他所有公理与TB∪TB1∪BR1中的均相同，因此有ITB∪TB1∪BR1成立，即TB∪TB1∪BR1是可满足的.
反过来，若TB∪TB1∪BR1是可满足的(即存在解释ITB∪TB1∪BR1)，我们来证明TB∪TB1∪BR0也是可满足的.根据假设可知对于任意变元赋值π均有(B1H1)I，π为真.与前面类似，我们只需考虑为真的情况即可.令π′表示π′(z′)=π(z)，π′(x)=π(x)(当x≠z′时)的变元赋值，很显然
为真，考虑到假设条件(B1H1)I，π′为真可知
为真，因此有
为真.对于在H0中出现的所有变元，π′与π均相同，因此为真，进而IB0H0.最终可得ITB∪TB1∪BR0成立，即TB∪TB1∪BR0是可满足的.
综上，情形4不改变转换前后的知识库可满足性.
对于情形5，令B0H和B1H分别表示转换之前和之后的桥规则，我们同样从2个方向来证明.先证明若B0H是可满足的，则B1H也是可满足的.根据假设有IB0H，对于任意变元赋值π，如果为假，则(B1H)I，π必为真，因此我们只需考虑为真的情况就可以了.由于为真，即∃U.D(u)I，π为真，因此ΔI中必存在δ满足δ∈DI.令π′表示π′(z)=δ，π′(x)=π(x)(当x≠z时)的变元赋值，则有D(z)I，π′为真.再考虑到z不出现在任意其他公理中(由于满足情形5的前提条件而情形1的前提条件不满足)，可得
为真，根据假设B0H是可满足的，可知HI，π′=HI，π为真，从而最终可得IB1H.
再证明若B1H是可满足的(即有IB1H)，则B0H也是可满足的.对于任意变元赋值π，如果为假，则(B0H)I，π必为真，因此只需考虑为真的情况即可.为真意味着D(z)I，π为真且π(z)∈DI，因此对于任意变元u有∃U.D(u)I，π为真，进而可知为真.考虑到假设B1H是可满足的，可知HI，π为真，从而最终可得IB0H.
由于情形5仅将桥规则B0H转换为B1H 而所有公理保持不变，因此TB∪TB0∪BR0和TB∪TB1∪BR1具有相同的可满足性.
通过上述分析可知，算法1的每步转换均不改变知识库的可满足性，因此TBBR与DTB具有相同的可满足性.
证毕.
定理4. 若DTB是正则的，则算法1输出的知识库TBBR也是正则的.
证明. 我们只需证明算法1的每步转换都不改变知识库的正则性即可.
由于情形1～2均是对桥规则涉及的的概念公理(而非角色公理)进行的等价变换，而正则性只是对角色层次进行的限定，根据定义6可知它们不会对知识库的正则性造成任何影响.对于情形3，只要被转换的桥规则(无论是BH或HB)满足定义6的条件，由于仅有公理R1∘R2∘…∘RnR被添加到TBBR中而其中的角色顺序与B中的原始角色序列R1(x，x2)，R2(x2，x3)，…，Rn(xn，y)的顺序相同，因此情形3也不改变知识库的正则性.
对于情形4，若新引入的角色S先序于H中的角色R(x，y)且S为B中的单一最大路径带来新的始端元素替换了先前作为路径起始的R(s，t)中的始端s，或者S为B中的单一最大路径带来新的终端元素替换了先前作为路径终点的R(s，t)中的终端t，只有这2种情况下知识库的正则性才有可能被改变，然而根据情形4的前提条件可知，在上述情况下被约简的概念公理D(z)只能是D(x)或D(y)两者之一，因此S的引入都不会改变正则性.
情形5与情形4类似，仅当R中的第1个个体变元构成B的单一最大路径的始端或第2个个体变元构成单一最大路径的终端时，∃U.D(u)的引入才有可能改变知识库的正则性.在第1种情况下，我们令u=y(参见情形5的步骤①)，此时u并没有替换先前的最大路径的始端，因此正则性并没有被改变；在第2种情况下，我们令u=x，此时u并没有替换先前的最大路径的终端，正则性仍然得以保持.
证毕.
如2.1节所述，检测正则DSROIQ知识库的可满足性问题是可判定的，因此根据定理4可知，若DTB是正则的，则TBBR也是正则的，即检测TBBR的可满足性问题是可判定的.再考虑定理3TBBR与DTB具有相同的可满足性可知检测DTB的可满足性问题是可判定的.考虑到桥规则集合可以在多项式时间内转换为DSROIQ公理(定理2)，可得该问题的最坏时间复杂度与检测TBBR的可满足性问题的最坏时间复杂度相同.最终我们可以得到定理5.
定理5. 给定DSROIQ作为局部本体语言的分布式TboxDTB，必存在单一的DSROIQ TboxTBBR满足TBBR可以在BR规模的多项式时间内被计算出来且TBBR与DTB具有相同的可满足性.若DTB是正则的，则检测DTB的可满足性问题是可判定的，且其最坏时间复杂度与检测TBBR的相同.
针对复杂的分布式本体系统逻辑基础的研究，国内外研究人员提出了不同的思路和方法，包括基于ε-连接的描述逻辑、分布式动态描述逻辑、基于保守扩展的分布式本体框架、分布式一阶逻辑等.下面对这些研究进行对比分析.
Grau等人[4]和Mossakowski等人[12]提出了一种分布式本体框架，该框架使用ε-连接对各个本体进行组合.利用连接来描述本体间的外化关系，随后将连接应用于存在性限定和值限定可以构造跨越本体的复杂概念(例如利用连接E∈εij和Tj中的概念C可以构造Ti中的概念∃E.C，其中εij是Ti和Tj之间有向连接的集合).文献[13]对该框架进行了模态化扩展并引入了一系列消解推理规则，为其提出了基于消解的分布式推理算法.ε-连接框架仅对复杂概念之间的语义映射提供了一定的支持，并且其前提条件要求局部领域必须是互不相交的，而此特点就决定了它并不适合于作为语义Web这样的局部异构而又部分交叠的系统的逻辑基础.此外，为了满足局部领域的互不相交性还需要对该框架的表达能力进行多种限制，比如1个本体中的元素不能声明为其他本体中元素的子元素超元素，因而该框架无法实现包含关系在不同本体之间的传播.尽管在局部本体组合和推理方面该框架解决得较好，与D3L相比，ε-连接框架的描述能力和知识传播能力较有限.
文献[14]对D3L中桥规则的属性及其导致的知识传播进行了研究.通过在D3L解释中的领域关系之上引入组合一致性语义解决了包含关系无法在局部本体间正确传播的问题.证明了该语义不改变D3L的原始属性.为扩展后的D3L提出了分布式Tableaux推理算法并证明了该算法是可终止的、可靠的和完备的.文献[7]引入了合取映射桥规则，解决了桥规则包含合取元素时包含关系无法正确传播的问题，在此基础上提出了合取映射桥规则到普通桥规则的转换方法并证明了方法的正确性，从而可将带上述桥规则的D3L的推理问题转化为传统的推理问题.然而上述研究仅针对包含原子元素的同构桥规则，对于包含复合元素的异构桥规则的更一般情形则并没有涉及到，而且所提出的分布式Tableaux推理算法是采用局部本体推理加消息传递的机制实现的，其时间复杂度与单一本体的推理相比并没有明显的优势.
Lutz等人[5]提出的分布式本体框架使用保守扩展来描述本体之间的联系.本体T1∪T2是本体T1关于签名Σ的1个保守扩展当且仅当T1∪T2关于Σ的每个逻辑结论也是T1的逻辑结论.他们针对多种主流描述逻辑(ALC，ALCQI，ALCQIO，EL)研究了判定该问题以及2个本体之间的签名依赖性问题的可判定性及其推理复杂度.文献[15-16]进一步为该框架引入了模型论语义并研究了相关的推理问题.基于保守扩展的框架不仅可用于分布式本体的集成，也可用于将单个本体分解为不同的模块.然而与D3L相比，该框架的适用性局限于分布式本体之间具有签名依赖性的情形，不符合该约束条件的复合元素之间的映射均不被支持.我们认为过于严格的限制条件降低了该框架对分布式特性的描述和推理能力，并且该框架仅从理论上证明了签名依赖性问题是可判定的，并没有提供本体推理算法.
此外，基于对传统分布式一阶逻辑(DFOL)的语义映射机制进行扩展，Chiara等人[6]提出了修订版的分布式一阶逻辑.尽管具有较强的描述能力并证明了定理证明方法是完备的和可靠的，然而该框架仅提供的是自然演绎推理的定理证明方式，因此距实际问题中的高效应用尚有一定距离.
本文研究了被包含端存在复合元素的异构桥规则情况下的D3L推理问题.通过扩展角色层次正则性的定义，我们定义了DTB的正则性，提出了将描述逻辑DSROIQ作为局部本体语言的D3L知识库转换为单一DSROIQ知识库的算法,接着研究了算法的性质以及基于该转换的D3L集中式推理的复杂度的相关问题.本文的研究能够有效处理异构复合桥规则，并且表明支持此种桥规则的D3L集中式推理可以获得与现有D3L分布式推理算法相同的最坏时间复杂度.
未来的工作包括将该研究推广到EL，EL++作为局部本体语言的D3L，研究桥规则转换的可能性及方法、分析其复杂度并开发相应的推理机等.
参考文献
[1]Santipantakis G, Vouros G A. Distributed reasoning with coupled ontologies[J]. Knowledge and Information Systems, 2015, 45(2): 491-534
[2]Heiner S, Christine P, Stefano S. Modular Ontologies-Concepts, Theories and Techniques for Knowledge Modulariza-tion[M]. Berlin: Springer, 2009
[3]Sarra B A, Andreas S, Thomas M. Characterizing modular ontologies[C] //Proc of the 6th Int Workshop on Modular Ontologie. Amsterdam: IOS Press, 2012: 13-25
[4]Grau B C, Parsia B, Sirin E. Ontology integration usingε-connections[G] //LNCS 5445: Modular Ontologies. Berlin: Springer, 2009: 293-320
[5]Lutz C, Wolter F. Deciding inseparability and conservative extensions in the description logic EL[J]. Journal of Symbolic Computing, 2010, 45(2): 194-228
[6]Chiara G, Luciano S. Distributed first order logic[J]. Artificial Intelligence, 2017, 253(12): 1-39
[7]Zhao Xiaofei, Tian Dongping, Shi Yinghuan, et al. Knowledge propagation and reasoning induced by bridge rule chains in D3L[J]. Chinese Journal of Computers, 2014, 37(12): 2419-2426 (in Chinese)(赵晓非, 田东平, 史颖欢, 等. 链式桥规则导致的D3L知识传播及推理[J]. 计算机学报, 2014, 37(12): 2419-2426)
[8]Wang Zhuxiao. Distributed information retrieval oriented automatic reasoning[D]. Beijing: Institute of Computing Technology, Chinese Academy of Sciences, 2010
[9]Steffen S, Rudi S. Handbook on Ontologies[M]. 2nd ed. Berlin: Springer, 2009
[10]Horrocks I, Kutz O, Sattler U. The even more irresistible SROIQ[C] //Proc of the 10th Int Conf on Principles of Knowledge Representation and Reasoning. Menlo Park, CA: AAAI, 2006: 57-67
[11]Chang Lin, Shi Zhongzhi, Gu Tianlong, et al. A family of dynamic description logics for representing and reasoning about actions[J]. Journal of Automated Reasoning, 2012, 49(1): 9-60
[12]Mossakowski T, Kutz O, Codescu M. The distributed ontology, modeling and specification Language[C] //Proc of the 7th Int Workshop on Modular Ontologies. Amsterdam: IOS Press, 2013: 11-31
[13]Claudia N, Oliver K. Towards resolution-based reasoning for connected logics[J]. Electronic Notes in Theoretical Computer Science, 2014, 305(7): 85-102
[14]Zhao Xiaofei, Tian Dongping, Zhang Wenbo, et al. Properties and distributed tableaux reasoning algorithm for D3L(ccy)[J]. Journal of Computer Research and Development, 2014, 51(3): 570-579 (in Chinese)(赵晓非, 田东平, 张文波, 等. D3L(ccy)的属性及分布式Tableaux推理算法的研究[J]. 计算机研究与发展, 2014, 51(3): 570-579)
[15]Konev B, Lutz C, Walther D, et al. Model-theoretic inseparability and modularity of description logic ontologies[J]. Artificial Intelligence, 2013, 203(5): 66-103
[16]Lutz C, Piro R, Wolter F. Description logic TBoxes: Model-theoretic characterizations and rewritability[C] //Proc of the 22nd Int Joint Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2011: 983-988
Zhao Xiaofei1,2,3, Shi Zhongzhi2, and Feng Zhiyong3
1(SchoolofComputerScienceandSoftwareEngineering,TianjinPolytechnicUniversity,Tianjin300387)2(KeyLaboratoryofIntelligentInformationProcessing,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190)3(SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300072)
AbstractBridge rules provide an important mechanism describing semantic mapping and propagating knowledge for D3L (distributed dynamic description logics). The current research focuses on the homogeneous bridge rules which only contain atomic elements. In this paper, the research is extended to the D3L reasoning problem with the heterogeneous bridge rules which contain composite elements in the contained end. The regularity of distributed knowledge base is defined. Through the alternation of the bridge rules and transforming different forms into existing language mechanism, we present a algorithm which can convert the D3L knowledge base with dynamic description logic DSROIQ as local ontology language into a single DSROIQ knowledge base. Then we study the properties of the algorithm. We prove that the algorithm will terminate in polynomial time and the satisfiability of the target knowledge base is equivalent to the satisfiability of the original knowledge base. Thus, we prove that the worst-case time complexity of the centralized reasoning on regular D3L knowledge base with such bridge rules is the same as that on single DSROIQ knowledge base. The method proposed in this paper makes the reasoning for D3L to obtain the same worst-case time complexity as the existing distributed reasoning methods and solves the problem that the latter can not handle heterogeneous composite bridge rules.
Keywordsdistributed dynamic description logics (D3L); heterogeneous bridge rules; regularity; centralized reasoning; computation complexity
This work was supported by the National Basic Research Program of China (973 Program) (2013CB329502), the National Natural Science Foundation of China (61035003), the Open Foundation of Jiangsu Provincial Key Laboratory for Computer Information Processing Technology (KJS1737), and the China Postdoctoral Science Foundation (2018M631740).
基金项目：国家“九七三”重点基础研究发展计划基金项目(2013CB329502)；国家自然科学基金项目(61035003)；江苏省计算机信息处理技术重点实验室开放基金项目(KJS1737);中国博士后科学基金项目(2018M631740)
修回日期：2018-06-11
收稿日期：2017-10-15；
中图法分类号TP18
(zhaoxiaofei1978@hotmail.com)
ZhaoXiaofei, born in 1978. PhD, associate professor. His main research interests include distributed intelligence, description logics and semantic Web.
ShiZhongzhi, born in 1941. Professor and PhD supervisor. Senior member of CCF. His main research interests include artificial intelligence, machine learning and data mining (shizz@ics.ict.ac.cn)
FengZhiyong, born in 1965. Professor and PhD supervisor. His main research interests include knowledge engineering and service technology (zyfeng@tju.edu.cn).