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

赵晓非 史忠植 刘建伟

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

作为对象管理组织(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.他们提取出元层次中与结构完整性约束有关的特性(如元素之间的引用关系、属性的类型以及多重性等)，然后与相邻的下层元数据进行合并从而得到单层的元数据知识库，而后采用良设计的算法实现检测.

1 存储库元数据的形式化

1.1 Mn+1层的形式化

1) 元类及元属性

2) 元-关联类

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

Fig. 1 Meta-association class in level Mn+1图1 Mn+1层中的元-关联类

由于每个关联端表示相应端的元类与元-关联类之间的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端的取值限定被形式化为

C∀r1.A；
C′∀r2.A；
A

C(≥i1r1.A)(≤j1r1.A)；
C′(≥i2r2.A)(≤j2r2.A).

3) 元关联

Fig. 2 Meta-association in level Mn+1图2 Mn+1层中的元关联

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

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

C∀R.C′；
C′∀R-.C.

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

C(≥i1R.C′)(≤j1R.C′)；
C′(≥i2R.C)(≤j2R.C).

4) 泛化

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

1.2 Mn层的形式化

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 基本思路

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

证毕.

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

由第2种断言我们得到:

其中C1是b的类属概念.

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

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

证毕.

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

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

Fig. 3 An example for property type inconsistency图3 属性类型冲突示例

if (count1>count2)

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

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

count1=|ans(associationEnd)←body

association,associationEnd))|;

count2=get-min-cardinality((get-conceptAssociation)(get-relationAssociation-AssociationEnd));

if (count1

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

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所示.

从实验结果来看，无论采用何种推理机，本文的方法在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方法的结果.

Table 1 Experimental Results for Extracting Logically Independent Fragment表1 抽取逻辑无关片断的实验结果

Fig. 4 Time performance comparison with related approaches图4 与相关方法的时间性能比较

5 结 论

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