基于元数据逻辑无关片断的结构完整性检测方法

1(天津工业大学计算机科学与技术学院天津 300387) 2(江苏省计算机信息处理技术重点实验室(苏州大学) 江苏苏州 215006) 3(中国科学院计算技术研究所智能信息处理重点实验室北京 100190)zhaoxiaofei1978@hotmail.com)

Structural Integrity Checking Based on Logically Independent Fragment of Metadata

1(School of Computer Science and Technology, Tiangong University, Tianjin 300387)2(Provincial Key Laboratory for Computer Information Processing Technology(Soochow University), Suzhou, Jiangsu 215006)3(Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)

Abstract Checking the structural integrity efficiently is one of the research hotspots in the field of MOF(meta object facility) repository system consistency. In this paper, we propose an efficient and automatic approach for checking the structural integrity by means of description logics. Firstly, according to the characteristics of MOF architecture, we study how to transform different levels of metadata into

knowledge base. Then we study how to extract metadata to improve the efficiency of the checking process. We propose the concept of logically independent fragment of metadata. By extracting property deductive fragment and classification deductive fragment respectively, we present the algorithm to generate the minimum logically independent fragment. Since this kind of fragment is the closure of logical implication for a given metadata element, all relevant information about the given metadata element is completely preserved, thus the checking process can be performed on a smaller set of metadata rather than on the entire repository. Finally, we study how to perform checking based on logically independent fragment. The experimental results show that the average size of the metadata fragment generated by our approach is significantly smaller than its original size, and the efficiency improvement of the checking on the metadata fragment ranges from 1.47 times to 3.31 times. The time performance comparison with the related approaches also shows the effectiveness of our approach.

Key words logically independent fragment; structural integrity; repository system; meta object facility (MOF); metadata

摘要高效地执行结构完整性检测是基于元对象设施(meta object facility, MOF)的存储库系统一致性领域的研究热点之一.借助逻辑学手段，提出了一种高效、自动地检测结构完整性的方法.首先针对MOF存储库框架的特点研究了如何将元数据的不同层次转换进描述逻辑

知识库，在此基础上研究了如何对元数据进行抽取以提高检测过程的效率.提出了元数据逻辑无关片断的概念，通过分别抽取属性演绎片断和类属演绎片断，给出了生成最小逻辑无关片断的方法.由于该种片断是给定的元数据元素逻辑蕴含的闭包，因此完整地保留了给定元数据元素的相关全部信息从而使得检测可以在较小的元数据集上进行，而不必针对整个存储库，最后给出了基于逻辑无关片断的结构完整性检测方法.实验结果表明所产生的元数据片断的平均规模显著地小于其原始规模，在此基础上执行的检测的效率提升从1.47～3.31倍不等，与相关方法的时间性能对比亦展示了所提出方法的有效性.

关键词逻辑无关片断；结构完整性；存储库系统；元对象设施；元数据

基金项目：国家自然科学基金项目(61035003,61972456)；江苏省计算机信息处理技术重点实验室开放基金项目(KJS1737)

This work was supported by the National Natural Science Foundation of China (61035003, 61972456) and 0m. .the Open Foundation of Jiangsu Provinci.0al Key Laboratory for Computer Information Processing Technology (KJS1737).

作为对象管理组织(object management group, OMG)提出的主要标准之一，元对象设施(meta object facility, MOF)[1]已经成为国际主流的元数据存储库标准.MOF存储库系统中元数据的组织方式，即元数据的结构呈现出一种分层的、多级的并且动态变化的复杂结构，因此保持该种系统的一致性是一项重要任务.MOF存储库系统中的一致性包括：1)操作一致性.涉及存储库应用间的交互，与存储库事务的概念密切相关，它又分为协作原子性和并发多用户访问.2)元数据完整性.包括结构完整性和良格式.良格式确保单一层次中元素的语法正确性，而结构完整性确保1个层次中的元素符合与该层相邻的、更高的元层次中的类型定义[1].

结构完整性是MOF存储库系统一致性的重要组成部分.如果结构完整性得不到保证，存储库应用就可能修改或建立Mn层中的元数据元素而与Mn+1层中它们的元类相冲突.例如，1个操作可能会读取某个元素的属性，而该元素的元类并不存在，则该操作是无效的.1个数据库系统包含M0层到M2层.而为了提供可自定义、可扩展的系统框架，MOF标准引入了允许用户对M2层进行定义的M3层，在运行时刻M0，M1，M2层均可以被动态修改，因而就可能导致相邻层次之间的冲突问题，即结构完整性问题.其他系统并不面临这类问题，因为它们假定系统框架在运行时刻是静止的.

为了自动地执行结构完整性检测，不同的方法被相继提出，其中影响比较大的有3种:1)Muzaffar等人[2-3]为MOF存储库系统的形式化、查询和结构完整性检测提出了一种统一的框架OMLM.该框架采用F逻辑作为形式化机制.在文献[2]中他们利用F逻辑的开源实现Flora-2对各层次元数据进行描述并利用推理机MULLER执行结构完整性检测.他们在文献[3]进一步提出了Realization维度的概念并据此建立了MOF框架与Flora-2之间的映射，随后采用模型转换技术(MTT)开发了到Flora-2的转换工具，从而实现了形式化描述的自动生成.利用F逻辑形式化MOF框架并进行推理检测的还有Bernd等人[4]的工作.2)Liliana等人[5]采用了基于代数的形式化机制，他们首先针对MOF的层次结构提出了一种基于代数演算的形式化元建模语言NEREUS并为之开发了推理接口.NEREUS利用Instantiation-算子来建模相邻层次之间的类型-实例关系.NEREUS不仅可以实现结构完整性检测，也可以实现良格式约束的检测.3)Esther等人[6-7]提出了一种对MOF框架的相邻层次进行压扁(flattening)处理以检测结构完整性的方法并实现了原型工具metaDepth.他们提取出元层次中与结构完整性约束有关的特性(如元素之间的引用关系、属性的类型以及多重性等)，然后与相邻的下层元数据进行合并从而得到单层的元数据知识库，而后采用良设计的算法实现检测.

尽管上述工作在自动执行MOF存储库系统的结构完整性检测方面取得了不同程度的进展，由于元数据的规模以及更新频度的不断增加，如何高效地执行该检测成为一个亟待解决的问题.本文提出了一种基于抽取出的元数据片断进行结构完整性检测的方法.作为一阶谓词逻辑的可判定子集，描述逻辑已经在形式化建模和推理方面取得了广泛的应用，特别是作为主流本体语言OWL2 DL[8]的逻辑基础，描述逻辑

不仅具备较强的描述能力，而且配备了已实现的推理机如HermiT[9]，FaCT++[10]，Konclude[11]等，成为我们首选的形式化机制.

本文首先针对MOF存储库框架的特点，研究了将其不同层次转化为

知识库的方法.为了提高检测的效率，接着我们定义了元数据的逻辑无关片断并将其区分为属性演绎片断和类属演绎片断.由于元数据元素的概念断言既依赖于概念断言也依赖于角色断言，相反不同元素之间的角色断言仅受角色断言的影响而与概念断言无关，因此我们研究了属性演绎片断的计算方法，在此基础上提出了类属演绎片断的计算方法，并给出了最小逻辑无关片断的生成算法.为了证明算法的正确性，我们给出了严格的形式化证明.该种片断完整地保留了给定元数据的全部逻辑结论，从而使得检测可以在较小的元数据集上进行，而不必针对整个存储库.最后我们给出了在元数据片断上执行查询推理以检测结构完整性的方法，并通过实验讨论了逻辑无关片断的抽取对检测效率的提升以及本方法与相关方法的时间性能对比.

1 存储库元数据的形式化

MOF框架中相邻层次之间的关系是类型-实例的关系，因此我们将元层次，即Mn+1(n为0或1)层中的信息形式化为

中的概念定义，而将作为实例的Mn层中的元素形式化进

具体来说，当n=1时，我们分别将M2层和M1层形式化进Tbox和Abox，检测的是M2层和M1层之间的一致性；当n=0时，我们分别将M1层和M0层形式化进Tbox和Abox，检测的是M1层和M0层之间的一致性.

1.1 Mn+1层的形式化

1) 元类及元属性

由于元类和

概念都是用于描述实例的集合，因此我们将每个元类转换为一个

概念.

由于元类C的1个类型为C′的元属性a将C的每个实例关联到C′的实例，因此元属性a是C的实例与C′的实例之间的2元关系，所以我们将元属性a形式化为1个

角色，该角色可以通过断言C width=13,height=13,dpi=110

∀a.C′来表示.若a存在多重性i..j，则将该多重性形式化为C width=13,height=13,dpi=110

(≥i a.C′)

(≤j a.C′).上述断言精确地指明了对于概念C的每个实例c，所有通过a关联到c的对象都是C′的实例，并且精确反映了属性名在整个元层次中的不唯一性，即2个不同的元类可以拥有类型不同但名字相同的属性.

元层次中的元-关联类如图1所示.每个元-关联类都包含2个存在多重性约束的关联端.与元属性不同的是，在MOF框架中元-关联类的名字是唯一的.

由于每个关联端表示相应端的元类与元-关联类之间的2元关系(即该元类以何种身份参与元-关联类)，我们将元类C和C′之间的元-关联类A(关联端分别为r1和r2)形式化为1个概念A和2个角色r1和r2，其中r1和r2分别对应于关联端r1和r2，r1以C和A作为第1和第2个要素，而r2以C′和A作为第1和第2个要素，因此r1端和r2端的取值限定被形式化为

上述第1个断言精确地指定了任何1个元类C的实例通过r1只能关联到A的实例，第2个断言精确地指定了任何1个元类C′的实例通过r2只能关联到A的实例，而第3个断言精确地指定了任何A的实例通过

和

只能关联到C的实例和C′的实例.由于

概念的唯一性，元-关联类的唯一性在上述断言中也得以精确地反映.r1的多重性i1..j1和r2的多重性i2..j2则分别被形式化为

元关联如图2所示，用于表明2个元类的实例之间的2元关系.例如元关联R描述了元类StructuralFeature和UniqueKey之间2元关系.R的多重性描述了每个UniqueKey的实例至少和1个StructuralFeature的实例相关联.

由于元关联本质上是一种2元关系，因此我们将元类C和C′之间的元关联R形式化为1个角色R并用下述断言描述R的取值限定：

C的多重性i1..j1和C′的多重性i2..j2则分别被形式化为

MOF框架中的泛化关系表明子类的每个实例也是父类的实例.因此子类的实例继承了父类的属性，此外它们还可以定义自己的属性.

泛化关系是被

所支持的，如果1个元类C1是元类C2的泛化，我们可以将之形式化为C2 width=13,height=13,dpi=110

C1.由于“

”的语义是基于子集理论的，因此C1的每个元属性以及与C1相关的每个元关联都被C2继承下来.此外这种形式化方式也完全适用于元类之间的多重继承关系.

1.2 Mn层的形式化

Mn层中的每个元素是Mn+1层中相应元类的实例，元素之间的关系是元类之间相应元关联的实例，因此Mn层元素应被转化为

知识库的

分3种情况：

1) 若Mn层元素c是其元层次中元类C的实例，则将其形式化为C(c)；

2) 若Mn层元素c关联了c′，相应的元类C(或其祖先)通过元关联R与元类C′(或其祖先)相联系，元关联R被形式化为Tbox中的角色R，则将c和c′之间的关系形式化为R(c，c′)；

3) 若Mn层元素c关联了c′，相应的元类C(或其祖先)通过元-关联类A与元类C′(或其祖先)相联系，而元-关联类被形式化为概念A和角色r1，r2，则将c和c′之间的关系形式化为3个断言A(a)，r1(c，a)，r2(c′，a).

2 元数据逻辑无关片断的抽取

2.1 基本思路

通过第1节的转换，我们获得了元数据知识库

进而将存储库的结构完整性检测问题转化为元数据知识库的查询推理问题.下面研究如何针对给定的部分元数据元素，抽取的子集而不改变检测的结果.首先给出下述定义.

定义1. 签名.给定

断言γ，γ中出现的元数据元素的集合称为γ的签名，记为Sig(γ).中所有元数据元素的签名记为

定义2. 角色路径.若对于i=1,2,…,n-1，中或者存在角色Ri(ai，ai+1)，或者存在角色

则称元数据元素a1和an之间存在角色路径.

角色路径可以包含逆角色.例如给定R1(a1，a2)，R2(a3，a2)，R3(a3，a4)，从a1到a4的角色路径是

相反从a4到a1的角色路径是

给定如上获得的元数据知识库，由于知识库的查询推理可以分解为多个针对单个元素的原子查询，而原子查询的结果由2部分构成：包含该元素的断言以及基于这些断言推导出的隐含断言，因此我们可以针对待查询的元素，抽取出元数据知识库的片断，从而可以在小规模的元数据集上执行查询推理进而提高结构完整性检测的效率.例如要查询和元素Dimension的实例相关的信息，我们仅需在包含Dimension的实例的元数据片断上执行查询即可.为了保持查询结果的完备性，元数据片断必须包含给定元素的全部断言(包括隐含断言)，再考虑

知识库的推理问题均可转化为判定逻辑蕴含的问题，因此抽取出的片断必须是给定元数据元素逻辑蕴含的闭包.基于上述分析，我们给出元数据逻辑无关片断的形式定义：

定义3. 逻辑无关片断.令

是元数据知识库，集合S是签名.的子集

称为签名S的逻辑无关片断当且仅当对于满足Sig(γ)∩S≠∅的任意断言γ(概念断言或者角色断言)，有

等价于

定义3规定了成为元数据逻辑无关片断的充要条件，它确保了签名S的

是给定元数据元素的逻辑蕴含的闭包，然而根据定义3以及

的单调属性[12]可知，

的任意超集也是S的逻辑无关片断(比如整个

总是S的逻辑无关片断)，因此定义3并没有确保签名S的逻辑无关片断的唯一性.

我们的目标是划分出精确的元数据片断，该片断仅包含对给定签名必不可少的断言，从而使得产生的片断在保持信息完备性的同时具有最小的规模.简单地说，要使得断言对于给定签名S必不可少，它们必须能够影响S中任意元数据元素的逻辑结论，为了区分这种断言，我们给出定义4：

定义4. 论据.给定元数据知识库及断言α，且

称的片断

是α的论据，当且仅当对于任意

有

且

α成立.α的论据记作

定义5. 关键断言.给定元数据知识库

元数据元素a及断言γ，称γ为{a}的关键断言，当且仅当对于a的任意断言α(概念断言或者角色断言)，有

成立.

根据上述定义，断言α的论据

实质上是蕴含α的元数据知识库的最小片断，即Just(α，

中每个断言都是α的关键断言.断言γ能够影响签名S中某个元素的逻辑推导当且仅当它出现在该元素的任意角色断言或概念断言的论据中，此时γ是S的关键断言.利用S的全部关键断言构造出的逻辑无关片断

不仅保留了S中元素的概念断言和角色断言的全部逻辑结论而且具有最小的规模.因此下面我们的任务就变成了如何为给定签名S计算仅包含关键断言的逻辑无关片断，即最小逻辑无关片断，除非特别指明，下文的逻辑无关片断均指最小逻辑无关片断.

定理1. 给定签名S以及S中每个元数据元素i的逻辑无关片断

令

则

是签名S的逻辑无关片断.

证明. 用反证法.假定

不是S的逻辑无关片断，则按照定义3，满足Sig(γ)∩S≠∅的断言γ必属于2种情况之一：

且

γ且

情况1)违背了

的单调属性，因此不成立.如果是情况2)，令元素a∈Sig(γ)∩S，

的子集

是a的逻辑无关片断，则有

而这再次违背了

的单调属性.由于

是被

包含的，因此定理1得证.

通过定理1可知，由于签名S中每个元素的逻辑无关片断的并集即为S的逻辑无关片断，因此我们仅需为S中单个元数据元素的逻辑无关片断的计算提出算法即可.

要计算给定的单个元数据元素a的逻辑无关片断，我们需要判断中的每个断言是否为a的关键断言，即必须测试每个断言是否与a的角色断言或概念断言的推导有关.根据文献[13]中

的Tableaux扩展过程可知，新的概念分支的生成由原始概念分支以及角色分支共同决定，而新的角色分支则仅由原始角色分支决定，因此元数据元素的概念断言既依赖于概念断言也依赖于角色断言，相反不同元素之间的角色断言仅受角色断言的影响而与概念断言无关.基于此，单个元素a的逻辑无关片断可以通过3步获得：首先计算断言的集合

其中每个断言都与a的任意角色断言R(a，b)的推导有关，我们将该集合称为属性演绎片断;接着计算断言的集合

其中每个断言都与a的任意概念断言C(a)的推导有关，我们将该集合称为类属演绎片断;最后将集合

与

合并即得a的逻辑无关片断.

的计算

元数据元素a的属性演绎片断

中的每个断言都与a的任意角色断言R(a，b)的推导有关，因此

其中γ是Abox断言,而

是R(a，b)的论据.由于角色层次和传递角色都会对角色断言产生影响，因此

的计算需要考虑2种断言：第1种断言形如

或

R；第2种断言是从a到b的角色路径中的断言，这些断言均有传递的父角色R0且R0 width=13,height=13,dpi=110

R，例如

其中a1=a，a4=b,而

R0且R0是传递角色.由第1种断言我们得到:

条件

中以a作为第1个要素或第2个要素的角色断言.

由第2种断言我们得到:

条件

中从a到b的角色路径中的角色断言，这些断言具有同一个传递父角色.

因此满足条件1或条件2的角色断言的集合即为元数据元素a的属性演绎片断

的计算

要计算元数据元素a的逻辑无关片断，需要在获得的

的基础上进一步计算

由于

中的每个断言都与a的任意概念断言C(a)的推导有关，因此

其中γ是Abox断言,而

是C(a)的论据.

如2.1节所述，在

中元数据元素的概念断言的推导既依赖于概念断言也依赖于角色断言，因此a的概念断言是

必不可少的组成部分.为了识别影响C(a)的角色断言，还需要对

中的每个断言进行鉴别.给定元数据知识库

仅当元素a的角色断言的限定性概念(值限定或数量限定)被C所包含，才会有C(a)成立，因此为了识别与a的概念断言的推导有关的断言，必须确定该断言的限定性概念被某个概念所包含.例如令

A}，{R0(a，b)，B(b)})，若要识别R0(a，b)是否与a的概念断言的推导有关，必须确定R0(a，b)的限定性概念被某个概念所包含，即是否满足：

其中C1是b的类属概念.

不难看出通过将C1替换为B且C2替换为A后条件3是可满足的，因此可知R0(a，b)与C2(a)(即A(a))的推导有关，即R0(a，b)在C2(a)的论据中因而应该被加入

不仅如此，由于C1(b)也是推导出C2(a)的要素，

中的断言也应该被加入

条件3仅考虑了影响概念断言推导的单个角色断言，实际上后者有时会被多个角色断言所影响，例如令

(∃R1.C)

A}，{R0(a，b)，R1(a，c)，B(b)，C(c)})，此时角色断言R0(a，b)仍然与A(a)的推导有关，但是根据条件3来判断R0(a，b)的限定性概念是否被某个概念所包含时却发现它并不满足，究其原因是仅当R0(a，b)成立并且R1(a，c)也同时成立时才会影响A(a)的推导，而后者并没有被包含进

因此条件3并不全面.为了将上述角色断言添加进

应将条件3扩展为：

其中C3是将元素a作为要素的所有其他角色断言的限定性概念的合取.

如果把

的数量限定考虑在内，条件4应进一步扩展为：

其中

是a的全部R0-邻居(即通过R0与a相关联的全部C1的实例)构成的集合.

与条件4相对比可以看出，实际上条件4中的∃R0.C1仅是条件5中≥nR0.C1的特例.条件5是识别影响C(a)的角色断言的最一般形式，它表明在元数据知识库中，若元素a的全部R0-邻居(即C1的实例)的数目大于等于n，则所有具备限定性概念≥nR0.C1的角色断言R0均会对a的概念断言的推导造成影响，因而应该被加入

中.

2.4 逻辑无关片断的抽取算法

如2.1节所述，为了获得元数据元素a的逻辑无关片断，应首先计算属性演绎片断

其中每个断言都与a的任意角色断言R(a，b)的推导有关；然后在此基础上计算类属演绎片断

其中每个断言都与a的任意概念断言C(a)的推导有关；最后求二者的并集，即可求得a的逻辑无关片断.据此思路得到算法1.

定理2. 给定元数据知识库

及元数据元素a，算法1的输出

是a的最小逻辑无关片断.

证明. 要证明

是a的最小逻辑无关片断，只需证明

中的每个断言γ均为{a}的关键断言即可，即对于a的任意断言α(概念断言或者角色断言)，若

则必有

成立.由于算法1中只有步骤②～⑤向

中添加元素，因此我们分别对其进行讨论.

步骤②将γ=R0(a，b)以及

添加进

用反证法，以γ=R0(a，b)为例，假设

且

显然

而

R0(a，b)，根据定义4可得

是R0(a，b)的论据，这与

是α的论据相矛盾，假设不成立，因此R0(a，b)必是

中的断言；

的情况与之类似，此处略.

步骤③将γ1=R1(a1，a2)，γ2=R2(a2，a3)，…，γn-1=Rn-1(an-1，an)，γn=Rn(an，an+1)添加进

其中a1=a.用反证法，假设

且Rk(ak，ak+1)(1≤k≤n)不是{a}的关键断言，即

根据Ri(1≤i≤n)拥有共同的传递父角色R0可知必存在角色Rm width=13,height=13,dpi=110

R0使得

再根据

Rm(a1，ak+1)以及定义4可得

是Rm(a1，ak+1)即Rm(a，ak+1)的论据，这与假设

是a的任意断言α的论据)相矛盾，假设不成立，因此Rk(ak，ak+1)(1≤k≤n)必为{a}的关键断言；

步骤④将γ=C0(a)添加进

同样假设

且

由于

而

C0(a)，因此可得

是C0(a)的论据，这与

是α的论据相矛盾，假设不成立，所以C0(a)必然属于

步骤⑤将所有符合条件的R0(a，b)、论据

以及C3中的限定性概念添加进

下面分别讨论.对于R0(a，b)，由于其已在步骤②中被添加进

因此显然R0(a，b)是{a}的关键断言；对于

根据步骤⑤的前提条件可知存在b的类属概念C1以及概念C2满足(≥nR0.C1) width=13,height=13,dpi=110

C2，令

假设

此时必存在断言γ使得

并且

根据定义4可知

C2(a)，因此

C2(a)，从而可得(≥nR0.C1) width=13,height=13,dpi=110

C2，这与前提条件(≥nR0.C1) width=13,height=13,dpi=110

C2相矛盾，因此

中的断言必为{a}的关键断言.对于C3是限定性概念的合取的情况，令Cm是C3中的任一限定性概念且C3=Cm width=13,height=13,dpi=110

根据前提条件可知存在b的类属概念C1以及概念C2满足(≥nR0.C1) width=13,height=13,dpi=110

(Cm

C2，即必存在a∈Cm且

满足(≥nR0.C1) width=13,height=13,dpi=110

(Cm

而(≥nR0.C1) width=13,height=13,dpi=110

C2(a).如果

则将Cm从C3中去除并不影响a的断言的推导，因此可得(≥nR0.C1) width=13,height=13,dpi=110

与前提条件相矛盾，因此Cm必为{a}的关键断言.

3 基于逻辑无关片断的结构完整性检测

由于通过算法1求得的片断是给定元数据元素逻辑蕴含的闭包，因此逻辑无关片断的抽取使得结构完整性检测中的原子查询可以在较小的元数据集合上执行而不影响查询的结果，即给定元数据知识库及元素a，与a有关的原子查询可以仅在

上进行而不必针对整个元数据知识库.

我们通过

推理机的查询推理来实现结构完整性检测.下面以HermiT为例，通过2个实例来阐述如何在逻辑无关片断的基础上执行检测.

根据结构完整性约束，如果某个操作修改了元层次中某元属性的类型，若新类型不是原有类型的超类且原有类型是元层次中已存在的元类，而下级层次中该元属性的相应实例没有被修改则会产生结构完整性冲突之一——属性类型冲突.该类冲突可以通过定义函数1来检测(假定元类Property的元属性referencedType的类型由StructuredType变为SimpleType，而非DataType等超类型，如图3所示)：

(…

*省略部分通过查询元数据知识库确定referencedType的元类Property及其类型的元类SimpleType，确定Property的实例property* width=5,height=17,dpi=110

count1=|ans(datatype)←body(referencedType

count2=|ans(datatype)←body(referencedType

print(“Property type inconsistency: some fillers do not belong to the type #.”,referencedType).)

函数1根据给定的元属性referencedType检索

获得作为该元属性的类型的元类并与检索

的结果进行比较，如果存在不属于该属性类型的实例，则结构完整性被违背，向用户输出冲突信息.在本函数中，计算count1和count2时均需查询referencedType(property,datatype)，该查询根据已知的property检索用以确定所有被property引用的datatype，而count2的计算另需查询SimpleType(datatype)，该查询检索用以确定所有属于SimpleType的datatype.通过抽取property和datatype逻辑无关片断，这2个原子查询均可以在较小的元数据集上执行,从而提高检测效率.

下例是多重性冲突的检测.根据结构完整性约束，如果某个操作修改了元层次中的关联端的多重性，而下级层次中的元素没有被相应修改,则可能会导致相应实例数目与修改后的多重性发生冲突.可以通过定义函数2来检测该类冲突(假定Association和AssociationEnd间的元关联在AssociationEnd端的多重性由1改为2)：

(…

*省略部分查询元数据知识库，确定association的元类Association，以及Association与AssociationEnd之间存在元关联Association-AssociationEnd* width=5,height=17,dpi=110

count1=|ans(associationEnd)←body

association,associationEnd))|;

count2=get-min-cardinality((get-concept Association)(get-relation Association-AssociationEnd));

print(“AssociationEnd multiplicity inconsistency:#associates#elements,at least # is needed.”,association,count1,count2).)

函数2根据给定的关联association，通过查询

获取元层次中规定的与该关联相关的多重性下限，然后与

中元素实例的数目相比较，如果约束被违背，则向用户输出相关信息.在本函数中，count1的计算需查询Association-AssociationEnd (association,associationEnd)，该查询用以确定所有与已知的association通过Association-AssociationEnd相关联的associationEnd，通过抽取给定的元素association的逻辑无关片断，该原子查询可以在较小的元数据集上进行从而使检测过程得以优化.

4 方法有效性评测

为了评测本文方法的有效性，我们进行了大量实验，重点测试了抽取元数据片断对结构完整性检测效率的提升，并对本方法与前述3种主要方法(OMLM，NEREUS，metaDepth)的检测时间性能进行对比.所有实验是在Intel i5-8265U、8 GB内存和Windows 10操作系统的环境下执行的.实验采用基于MOF 2.5.1框架的元数据集ReMoDD[14]作为测试集，我们随机地选择4个检测任务：ColumnSet的属性类型冲突、Dimension的属性类型冲突、TableOwning的多重性冲突以及SchemaOwning的多重性冲突并分别使用2种推理机HermiT和FaCT++执行检测.测试结果如表1和图4所示.

表1列出了逻辑无关片断的抽取对检测时间的影响，包括抽取所耗费的时间、抽取前后

中的元素个数以及2种推理机在抽取前后的元数据集上的检测时间.可以看出抽取的片断平均含有63.33个元素，显著小于312个元素的原始规模.从执行时间来看，抽取过程所耗费的平均时间25.89 s与HermiT的平均检测时间509.45 s以及FaCT++的平均检测时间520.88 s相比几乎可以忽略，而获得的效率提升则从1.47～3.31倍不等.本文的方法与相关方法的时间性能对比展示于图4.

从实验结果来看，无论采用何种推理机，本文的方法在4种检测任务上的表现均大幅优于NEREUS方法.值得注意的是，在采用HermiT推理机时，我们的方法执行2个多重性冲突检测任务的平均时间508.20 s不如OMLM方法的444.67 s，这一差距在FaCT++的情况下(596.66 s)甚至更大，即便如此，由于本方法在属性类型冲突检测中的优势，4种任务的平均执行时间509.45 s(HermiT)和520.88 s(FaCT++)仍略优于OMLM方法的531.16 s.这一结果在与metaDepth方法(611.60 s)的对比中同样得以反应.综合来看，在实验元数据集上，我们的方法取得了显著优于NEREUS方法但略优于OMLM和metaDepth方法的结果.

5 结论

通过在抽取出的元数据片断上进行查询推理，本文提出了一种高效、自动地检测MOF存储库系统的结构完整性的方法.我们研究了将层次化的元数据转化为描述逻辑知识库的方法；最小逻辑无关片断的获取方法以及基于该片断的结构完整性检测方法.为了证明方法的正确性，我们给出了严格的形式化证明.由于抽取出的元数据子集是原始集合的逻辑蕴含的闭包，因此待查询元素的所有逻辑结论均得以保留从而使得本方法在不改变检测结果的前提下具有较高的效率.实验过程组合了不同的推理机和检测任务，结果表明逻辑无关片断的抽取可以显著地提高检测的效率以及本方法具有优于相关方法的时间性能.

[1] Object Management Group. Meta Object Facility, Version 2.5.1[S]. Needham: Object Management Group, 2016

[2] Muzaffar I, Georg G, Markus S. An implementation of multi-level modelling in F-logic[C] //Proc of the 2014 Int Workshop on Multi-Level Modelling. Aachen, Germany: CEUR-WS.org, 2014: 33-42

[3] Muzaffar I, Georg G, Matt S, et al. An integrated multi-level modeling approach for industrial-scale data interoperability[J]. Software & Systems Modeling, 2018, 17(1): 269-294

[4] Bernd N, Christoph G, Manfred A, et al. Dual deep modeling: Multi-level modeling with dual potencies and its formalization in F-Logic[J]. Software & Systems Modeling, 2018, 17(1): 233-268

[5] Liliana F, Daniel D. Formal MOF metamodeling and tool support[C] //Proc of the 4th Int Conf on Model-Driven Engineering and Software Development. Setubal, Portugal: SciTe Press, 2016: 99-110

[6] Esther G, Juan D. Towards automating the analysis of integrity constraints in multi-level models[C] //Proc of the 2014 Int Workshop on Multi-Level Modeling. Aachen, Germany: CEUR-WS.org, 2014: 63-72

[7] Esther G, Juan D. Automated analysis of integrity constraints in multi-level models[J]. Data & Knowledge Engineering, 2017, 107(1): 1-23

[8] Horrocks I, Parsia B, Sattler U. OWL 2 Web Ontology Language Direct Semantics[OL]. 2nd ed. [2018-09-28]. https://www.w3.org/TR/owl2-direct-semantics

[9] Glimm B, Horrocks I, Motik B, et al. HermiT: An OWL 2 reasoner[J]. Journal of Automated Reasoning, 2017, 53(3): 245-269

[10] Dmitry T. Incremental and persistent reasoning in FaCT++[C] //Proc of the 3rd Int Workshop on OWL Reasoner Evaluation. Aachen, Germany: CEUR-WS.org, 2014: 69-75

[11] Andreas S, Thorsten L, Birte G. Konclude: System description[J]. Journal of Web Semantics, 2014, 27: 78-85

[12] Giordano L, Gliozzi V, Olivetti N, et al. Semantic charac-terization of rational closure: From propositional logic to description logics[J]. Artificial Intelligence, 2015, 226: 1-33

[13] Matentzoglu N, Parsia B, Sattler U. OWL reasoning: Subsumption test hardness and modularity[J]. Journal of Automated Reasoning, 2018, 60(4): 385-419

[14] ReMoDD Team. Repository for model driven development(ReMoDD)[OL].[2018-01-20]. http://www.cs.colostate.edu/remodd/v1/content/repository-model-driven-development-remodd-overview

Zhao Xiaofei, born in 1978. PhD, associate professor. His main research interests include distributed intelligence and semantic Web.

Shi Zhongzhi, born in 1941. Professor and PhD supervisor. Senior member of CCF. His main research interests include artificial intelligence, machine learning, and data mining. (shizz@ict.ac.cn)

Liu Jianwei, born in 1979. Lecturer. Her main research interests include data engineering, ontology engineering, and semantic Web.