基于约束推演的MOF存储库冲突操作的发现方法

摘要

本发明涉及一种基于约束推演的MOF存储库冲突操作的发现方法，其技术特点是包括以下步骤：定义影响良格式约束的内部活动并建立它们与MOF构造活动的对应关系；对良格式约束进行化简；建立发现图；对发现图进行标记；获取内部活动；确定违背约束的潜在操作。本发明通过推断可能违背约束条件的内部活动，进而推断出违背约束条件的潜在操作，最终能够推断出与给定操作无关的约束条件。将这些与给定操作无关的约束条件从该操作执行以后的约束检测过程中剔除，可以显著提高这一过程的效率，本发明可广泛用于约束检测领域。

说明书

技术领域

本发明属于存储库系统技术领域，尤其是一种基于约束推演的MOF存储库冲突操作的发现方法。

背景技术

如今，元对象设施MOF已经成为国际上普遍接受和采用的元数据存储库系统标准。作为MOF存储库系统的重要组成部分，基于对象约束语言OCL定义的良格式约束规定了系统所有状态都必须遵从的条件。存储库系统的内容会由于操作的执行而被改变，因此必须确保操作执行后存储库系统的状态不违背元层次中的良格式约束。

然而由于下面两个原因的存在使得这一任务变得相当困难：一方面，存储库系统中元数据的组织方式呈现出分层、多级并且动态变化的复杂结构。不同于数据库系统，存储库系统引入M3层允许用户对M2层进行定义。在运行时刻 M2，M1和，M0层都可以被动态修改；另一方面，MOF标准对确保良格式约束规定得并不充分。MOF提供了几种机制用于保证存储库系统一致性，包括：首先， MOF定义了一组模型约束；其次，MOF为抽象映射定义了一组闭包规则和计算语义，JAVA元数据接口JMI为Jave映射定义了计算语义；再次，MOF为描述领域规则提供了constraint模型元素；最后，MOF和JMI定义了一组存储库界面。然而上述措施都是针对语法正确性的确保，而不是良格式约束。

经检索发现如下相关文献：Petrov等人(Petrov I,et al.On the notion ofconsistency in metadata repository systems,LNCS 3520:Proc of the 16th IntConf on Advanced Information Systems Engineering.Berlin: Springer,2004:90-104)论述了基于MOF的元数据存储库系统中各种一致性的概念并提出了策略和算法用于增强操作执行以后的系统状态和良格式约束之间的一致性。然而在此过程中他们对所有约束条件进行检测，从而使得检测过程效率不高。相比之下，由于在检测过程中只需考虑实际可能被违背的约束，不相关的约束将被略去，我们的方法可以显著提高该过程的效率。Takeshi等人(Takeshi A,et al.Metabolonote:A wiki-based database for managinghierarchical metadata of metabolome analyses.Frontiers in Bioinformatics andComputational Biology,2015,15(38):1-12)在解决元数据交换问题时也将元数据组织到不同的层次中，其元数据层次不是按照元数据的语义级别而是按照不同的元数据的内容及相关程度进行组织的，各层次之间并无语义关联。其操作对存储库内容的修改不会影响到下面的层次使得约束的确保相对简单，但该框架难以适用于动态变化的复杂元数据结构。文献 (Metadata based management and sharing of distributed biomedical data.International Journal of Metadata,Semantics and Ontologies,2014,9(1): 42-57)中所提出的元数据框架也具有类似问题。

据我们所知，在MOF存储库系统中推断给定约束的确切的潜在冲突构造活动PEA集合的问题在国际上还未有相关研究。类似的研究存在于演绎数据库和关系数据库领域，所采用的解决方法主要是将OCL约束转换为逻辑表达式或SQL 表达式，而后在此基础上设计算法用以推断给定约束的确切PEA集合，比如 Duboisset等人(Duboisset M,etal.Integrating the calculus-based method into OCL:Study of expressiveness andcode generation,Proc of the 18th Int Workshop on Database and Expert SystemsApplications.Piscataway, NJ:IEEE,2007:502-506)、Pinet等人(Pinet F,Duboisset M,Demuth B,et al.Constraints modeling in agricultural databases,Advances inModeling Agricultural Systems.Berlin:Springer,2009:1-11)、Donald等人(Donald C,Narayanaswamy K.Using first-order logic to query heterogeneous internet datasources,Proc of the 2015Int Conf on Soft Computing and SoftwareEngineering.Holand:Academic Press,Elsevier,2015:1-8)、 Demuth等人(Demuth B,Hussmann H,Loecher S.OCL as a specification language for business rules indatabase applications,LNCS 2185:Proc of the 4th Conf on UML.Berlin:Springer,2006:104-117)、陈等人(陈良刚等.区间约束数据库查询语言:ISQL.计算机研究与发展,2000,37(6): 677-683)的工作，但是，由于OCL约束包括了诸如否定、递归、包语义、聚合操作等很多复杂结构，所提出的算法的处理能力很难涵盖OCL约束的所有机制。尽管有的算法对此进行了改进以支持OCL约束的所有机制，但处理逻辑的高复杂性又导致了算法的效率不高(关于它们的局限性可以参考Siva等人的论述 (Siva S,et al.Constraintprocessing in relational database systems: From theory to implementation,Procof the 25th ACM Symp on Applied Computing.New York:ACM,2010:2066-2070))。

发明内容

本发明的目的在于克服现有技术的不足，提供一种设计合理、性能稳定且效率高的基于约束推演的MOF存储库冲突操作的发现方法。

本发明解决现有的技术问题是采取以下技术方案实现的：

一种基于约束推演的MOF存储库冲突操作的发现方法，包括以下步骤：

步骤1：定义影响良格式约束的内部活动并建立它们与MOF构造活动的对应关系；

步骤2：对良格式约束进行化简；

步骤3：建立发现图；

步骤4：对发现图进行标记；

步骤5：获取内部活动；

步骤6：确定违背约束的潜在操作。

所述内部活动是根据实体类型和关系类型定义的包括建立实例和删除实例的八种内部活动关系。

所述步骤2的具体实现方法为：首先使用定义在OCL标准库中的等价操作对出现在表达式中的操作数目进行约减；然后将表达式转换为等价的合取范式，转换的结果是每个约束被表示为析取项的合取；所得到的析取项的字面量包括 forAll迭代子、算术比较、对象/集合等价比较、布尔属性、not操作符、 oclIsTypeOf操作符以及oclIsKindOf操作符。

所述步骤3是根据良格式约束与OCL元模型之间的内容——实例关系建立的发现图。

所述步骤4对发现图进行标记的方法为：为每个节点所作的标记指示出该节点与它的后继节点之间相互影响的信息，包括四种不同类型的标记信息：“+”表示表达式的值的增加或项目数量的增加可能导致约束的违背；“-”表示表达式的值的减少或项目数量的减少可能导致约束的违背；“m”表示表达式的值的改变或项目数量的改变可能导致约束的违背；“nr”表示该节点与其后继节点并无相互影响。

所述步骤5的具体方法为：按自下而上逐级推断并汇总的过程进行获取，推断出每个约束条件的PIA集合。

所述步骤6的具体方法为：根据每个约束的PIA集合，转换为MOF标准的构造活动并得到PEA集合，最后检查每个操作是否存在违背的约束。。

本发明的优点和积极效果是：

本发明通过定义一组比MOF的构造活动更精确和灵活的MOF内部活动并建立了二者之间的对应关系；推断可能违背约束条件的内部活动；最后通过比对与这些内部活动相对应的构造活动是否在操作规范中出现，能够推断违背约束条件的潜在操作。其原理是每个约束条件找到可能违背它的构造活动的集合，然后与操作规范进行对比，若其中的一个或多个构造活动与操作规范相关，则可断定该操作的执行可能会违背该约束条件。通过推断出与给定操作无关的约束条件并将之从该操作执行以后的约束检测过程中剔除，本发明可以显著提高这一过程的效率。本发明可广泛用于约束检测领域。

附图说明

图1是元数据模型的层次结构示例图；

图2是MOF存储库系统M1层中的良格式约束示例图；

图3是修改存储库系统内容的操作示例图；

图4是约束OldTeacher对应的发现图；

图5是约束OldTeacher对应的发现图标记后的结果图；

图6是推断约束OldTeacher的潜在冲突内部活动PIA的过程示意图。

具体实施方式

以下结合附图对本发明实施例做进一步详述：

一种基于约束推演的MOF存储库冲突操作的发现方法，包括以下步骤：

步骤1：定义影响良格式约束的内部活动并建立它们与MOF构造活动的对应关系。

为了推断OCL良格式约束的潜在冲突构造活动PEA的集合，我们需要研究哪些构造活动的执行可能违背约束条件。因此本步骤主要是定义内部活动并建立它们与MOF构造活动的对应关系。在推理过程中实际参与推断的是内部活动。之所以选择在内部活动而不是构造活动之上进行推理是基于以下二方面原因：首先，我们的方法是借助良格式约束是OCL元模型的实例这一特性，通过建立发现图实例并在其上进行推理从而实现PEA的推断，因而针对可能影响OCL元模型实例的活动进行推断是较方便的选择，相反，构造活动是面向MOF模型机制的，直接在其上进行推理(尽管理论上可实现)会带来诸多不便之处；其次，目前国际上现存的元数据存储库标准有MOF，IRDS，PCTE等多种，每种标准都定义了自己框架内的构造活动。而我们则希望提出一种推断PEA的通用方法，因为一旦建立了本发明提出的内部活动和其他存储库框架的构造活动之间的对应关系，就可以调整本发明的方法以适用于其他存储库框架。这将极大地提高我们所提出的方法的适用性。

下面对OCL元模型元素种类及特性进行分析。约束元模型元素包括实体类型和关系类型二类，其上分别有建立实例和删除实例二种活动可能导致约束的违背。此外对实体类型的泛化和特化以及修改实例属性及关联端的活动均可能导致约束的违背，因此共有8种内部活动。表1列出了这些内部活动及其与MOF 构造活动的对应关系。尽管内部活动与MOF的构造活动之间并不一一对应，但它们较MOF构造活动更便于PEA的推断并且可以通过表2的简单映射转换为构造活动。例如，如果推断出某个实例之上的内部活动AssignObject可能违背约束条件，而该实例既不是关联类也不是由其他实例调整所得，则需将其转化为该实例之上的构造活动CreateObjectAction，若该AssignObject是关联端的变化所导致的，则还需加上该实例之上的构造活动AddStructuralFeatureAction。其他内部活动的转换与之类似，此处不再赘述。

表1内部活动及其与MOF构造活动的对应关系

步骤2：对良格式约束进行化简

对定义良格式约束的OCL表达式进行等价化简。首先使用定义在OCL标准库中的等价操作对出现在表达式中的操作数目进行约减，接着将表达式转换为等价的合取范式。转换的结果是每个约束被表示为析取项的合取。所得到的析取项的字面量包括forAll迭代子、算术比较、对象/集合等价比较、布尔属性、 not操作符、oclIsTypeOf操作符以及oclIsKindOf操作符等。显然要满足约束条件，存储库系统必须满足每个析取项。一个析取项被满足需要至少它的字面量之一被满足。

对图2中的4个约束进行操作数目的约减之后，约束OldTeacher和 UniqueName变为(其他约束保持不变)：

context School inv OldTeacher:

self.teacher->select(t|t.age>60)->size()>0

context Teacher inv UniqueName:

Teacher.allInstances()->forAll(t₁,t₂|not>1＝t₂implies not>1.name＝t₂.name)

进一步转换为合取范式之后，约束UniqueName变为(其他约束保持不变)：

context Teacher inv UniqueName:

Teacher.allInstances()->forAll(t₁,t₂|t₁＝t₂or not>1.name＝t₂.name)

步骤3：根据良格式约束与OCL元模型之间的内容——实例关系建立发现图。

在本步骤中，发现图的每个节点作为OCL元模型中元类的实例，表示OCL 表达式的一个原子子集。节点的第1个后继是OCL表达式位于该节点之前的部分。若该节点表示2元操作(如“>”，“+”等)，则节点的第2个后继是操作的参数；若节点表示loop表达式(如forAll，select等)，则节点的第2个后继是迭代子的体。

图4给出了根据约束OldTeacher (self.teacher->select(t|t.age>60)->size()>0)建立的发现图。与操作“>”相应的元类OperationCallExp的实例是初始节点，其第1个后继是位于“>”之前的表达式(self.teacher->select(t|t.age>60)->size())而下1个后继是操作的参数(整型常量0)。初始结点的第1个后继节点的第1个后继节点是操作size，它只有1个孩子select。节点select的第1个后继节点是关联端 teacher而第2个后继节点是位于属性age和整型常量60之间的操作“>”。

步骤4：对发现图进行标记

为了推断给定约束的PEA集合，仅单独考虑OCL表达式的每个部分是不够的。例如为了推断约束OldTeacher是否可能被分配教师到学校或解除教学关系 2种活动所违背，不能只考虑子表达式 self.teacher->select(t|t.age>60)->size()。实际上这2种活动都可能改变该子表达式的值，然而由于size操作之后是“>”操作，因此只有解除教学关系才可能导致约束的违背，相反，如果size之后是“<＝”操作，则只有分配教室到学校才可能导致约束的违背。上述分析表明只有综合考虑每个OCL原子子集的上下文信息才能正确推断出给定约束的PEA集合，因此需要利用发现图中每个节点的上下文信息对其进行标记。

为每个节点所作的标记指示出该节点与它的后继节点之间相互影响的信息。在全面分析OCL各种结构的基础上我们归纳出4种不同类型的标记信息：1) “+”表示表达式的值的增加或项目数量的增加可能导致约束的违背；2)“-”表示表达式的值的减少或项目数量的减少可能导致约束的违背；3)“m”表示表达式的值的改变或项目数量的改变可能导致约束的违背；4)“nr”表示该节点与其后继节点并无相互影响。

下面对每种标记进行举例说明。对于“+”和“-”，考虑“>”操作，要违背约束A>B有2种情况：A值的减少或B值的增加，因此节点“>”的第1个后继节点之上应该标记为“-”，而第2个后继节点之上应该标记为“+”。对于标记“m”，考虑select操作，不仅向待选集合增加对象或删除对象可能影响select 的结果，甚至等数量替换待选集合的某些对象也可能影响select的结果，因此节点select的后继节点之上应该标记为“m”。对于标记“nr”，考虑and操作，由于违背A and B的活动与单独违背A和违背B的活动相同，也就是说节点and 与它的后继节点之间不存在相互影响，因此节点and的后继节点之上均应标记为“nr”。

由于标记发现图的过程需要首先考虑当前节点之上的标记信息以及节点的类型从而确定其后继节点之上的标记信息，因此标记的过程需要对发现图进行广度优先遍历。表2对各种节点类型的标记方法进行了汇总。表2的单元格中如果某个节点上的标记符号超过1个，则应分别应用每种标记以确定其后继节点上的标记。单元格的内容“×”表示不存在这种组合情况的约束条件。

表2发现图的标记信息汇总

对约束OldTeacher对应的发现图进行标记的结果见图5。为了简明起见，我们略去了图4中与标记无关的内容.另外为每个节点添加了标记该节点所用到的表2单元格的信息，其中(X，Y)表示第X行第Y列的单元格.

标记的过程首先从初始节点开始.由于“>”无前驱节点，因此其上无须标记.根据单元格(2，1)，初始节点的第1个后继应标记为“-”而第2个后继应标记为“+”，因此节点size之上为“-”.再根据单元格(11，3)，我们将节点 size的后继(节点select)标记为“-”.按照单元格(10，3)，节点select 的第1个后继节点之上的标记是“-m”而第2个后继节点之上的标记是“nr”. 再参考单元格(9，3)和(9，4)，节点teacher的后继节点self应标记为“-m”。其他部分的标注以此类推，限于篇幅，此处不再赘述。

步骤5：获取内部活动

发现图标记好以后，下一步就可以据此推断出给定约束的潜在冲突内部活动PIA。由于标记图已明确标示出OCL原子子集表达式的类型以及该表达式如何变化能够违背整个约束，因此推断PIA的过程就是自下而上逐级推断并汇总的过程，也就是对图进行广度优先遍历的逆过程。

表3汇总了不同节点类型和标记信息的组合所对应的PIA的集合。c1+c2 表示该节点的PIA集合是其后继节点的PIA集合的并集。c1适用于该节点只有1 个后继节点的情形。空单元格意味着该节点并不影响PIA的推断汇总。需要特别说明的是c₁+X和opp(X)。c₁+X表示该节点向PIA集合中添加活动X。举例来说，如果关联端被标记为“+”，则其从属关联的链接实例的建立可能导致约束的违背，因此该节点应向PIA集合中添加AssignLink活动，即c₁+AssignLink。>

表3节点类型及标记信息所对应的PIA集合

将表3应用于约束OldTeacher，得到的结果如图6所示。首先处理节点self。由于节点self之上的标记是“-”和“m”，按照表3的单元格(17，3)，(17，4) 可知该节点不添加任何PIA。然后参考单元格(9，3)，(9，4)处理关联端teacher，向PIA的集合中添加活动AssignObject(School)，RemoveLink(TeachesIn)， ModifyEnd(TeachesIn-Teacher)。接着处理节点select的第2个后继(t.age>60)，它添加了活动ModifyProperty(age)。在此之后处理节点select，参考单元格(10， 3)，节点select的PIA集合是它的后继节点的PIA集合的并集。随后处理节点 size、整型常量节点0并以初始节点“>”结束，它们均不添加任何活动。最终由初始节点“>”返回的PIA集合即是整个约束表达式的PIA的集合。通过这一步骤，我们可知可能违背约束OldTeacher的内部活动有ModifyProperty(age)， ModifyEnd(TeachesIn-Teacher)，RemoveLink(TeachesIn)，AssignObject(School)。

步骤6：确定违背约束的潜在操作

按照步骤5推断出每个约束条件的PIA集合以后，需要将其转换为对应的 PEA的集合，并检查它们是否在操作规范中出现。以OldTeacher为例， ModifyEnd(TeachesIn-Teacher)直接转化为关联端teacher之上的 AddStructuralFeatureAction，ModifyProperty(age)直接转化为属性age之上的 AddStructuralFeatureAction，RemoveLink(TeachesIn)转化为关联TeachesIn之上的DestroyLinkAction，对于AssighObject(School)，由于School既不是关联类也不是由其他实例调整所得，而且AssignObject不是由关联端的变化所导致，因此只需将其转化为School之上的CreateObjectAction。

因此我们得到如下结果：

(1)每个约束的PIA集合：

①OldTeacher—ModifyProperty(age)，ModifyEnd(TeachesIn-Teacher)，RemoveLink(TeachesIn)，AssignObject(School)；

②NotHeadmasterParttimeteacher—SubReclassify(Parttimeteacher)，AssignLink(Manages)，ModifyEnd(Manages-Headmaster)；

③UniqueName—AssignObject(Teacher)，ModifyProperty(Name-Teacher)；

④ValidWorkinghours—AssignObject(Parttimeteacher)，ModifyProperty(Workinghours)；

(2)转换为MOF标准的构造活动，所得的PEA集合：

①OldTeacher—属性age之上的AddStructuralFeatureAction，关联端teacher之上的AddStructuralFeatureAction，关联TeachesIn之上的DestroyLinkAction， School之上的CreateObjectAction；

②NotHeadmasterParttimeteacher—将全职教师所属类元修改为Parttimeteacher的ReclassifyObjectAction，Manages之上的CreateLinkAction，关联端headmaster之上的AddStructuralFeatureAction；

③UniqueName—Teacher之上的CreateObjectAction，Parttimeteacher之上的CreateObjectAction，属性name之上的AddStructuralFeatureAction；

④ValidWorkinghours—Parttimeteacher之上的CreateObjectAction，属性workinghours之上的AddStructuralFeatureAction；

(3)每个操作可能违背的约束：

①EmployParttimeteacher可能违背ValidWorkinghours和UniqueName，其他 2个约束则不会违背；

②DismissTeacher只可能违背OldTeacher；

③DeleteAssociation只可能违背OldTeacher。

利用上述推断出的知识，在每个操作执行完以后就无需检测所有4个约束条件了，执行EmployParttimeteacher以后只需检测2个约束而执行 DismissTeacher和DeleteAssociation以后只需检测1个约束。可以看到通过缩小待检测的约束的集合，我们的方法可以显著提高良格式约束检测的效率。

为了评测本发明的有效性，以本发明所处理的元数据模型为例进行说明，它包括元数据的模型结构、位于M1层的4个OCL良格式约束以及修改存储库系统内容的3个操作。为了简明起见，我们忽略其他层中的约束。模型结构如图1 所示。作为M2层元数据实例的M1层元数据描述了学校和教师的信息。教师分为全职教师和兼职教师。M1层中的4个约束条件如图2所示，分别用于确保：每个学校至少有1个60岁以上的教师(OldTeacher约束)；校长不能是兼职教师(NotHeadmasterParttimeteacher约束)；2个教师的名字不能相同(UniqueName约束)；兼职教师的周工作时间必须介于10h和40h之间 (ValidWorkinghours约束)。3个操作如图3所示。每个具体活动之后我们附加了等价的MOF构造活动。操作EmployPartimeteacher为给定的学校聘用1个新兼职教师。它建立类元Parttimeteacher的1个新对象实例，对其进行初始化赋值并将其关联到学校。操作DismissTeacher解聘1个教师(全职或兼职) 并删除其与学校的关联。操作DeleteAssociation删除1个关联，同时删除它的关联端、关联与关联端之间的关系以及关联端与类之间的关系。EmployPartimeteacher和DismissTeacher仅修改M0层中的内容，而 DeleteAssociation修改M1层中内容的同时将改变传播到M0层，即M0层中的内容也将被修改。(因为高层次中内容的改变必须传播到它下面的所有层次，例如删除1个类的同时必须删除下面所有层次中该类的所有实例。)

通过应用本方法，我们可以推断出EmployParttimeteacher只可能违背约束ValidWorkinghours和UniqueName，其它两个约束则不可能违背，而 DismissTeacher和DeleteAssociation只可能违背约束OldTeacher，其它三个约束则不可能违背。因此在每个操作执行完以后就无需检测所有4个约束条件了，执行EmployParttimeteacher以后只需检测2个约束而执行DismissTeacher 和DeleteAssociation以后只需检测1个约束即可。可以看到我们的方法可以大大提高良格式约束检测的效率。

需要强调的是，本发明所述的实施例是说明性的，而不是限定性的，因此本发明包括并不限于具体实施方式中所述的实施例，凡是由本领域技术人员根据本发明的技术方案得出的其他实施方式，同样属于本发明保护的范围。