CN107247725B - Structural Integrity Detection Optimization Method Based on Metadata Logically Independent Fragmentation - Google Patents

Abstract

The invention relates to a structural integrity detection optimization method based on metadata logic irrelevant fragmentation, which is technically characterized by comprising the following steps of: formalizing repository metadata and data into a description logic SHIQ knowledge base; carrying out logic-independent fragmentation on the SHIQ metadata knowledge base; structural integrity checking is performed on top of the logically unrelated slices. The invention completely reserves all relevant information of given metadata, so that detection for partial metadata can be carried out on a smaller data set and does not need to be carried out on the whole storage library; and the detection of the whole storage library can be decomposed to different metadata fragments, and the experimental result shows that the size of the metadata fragment generated by the method is obviously smaller than the original size on average, so that the efficiency of structural integrity detection performed on the basis of the method can be obviously improved.

Description

Structural Integrity Detection Optimization Method Based on Metadata Logically Independent Fragmentation

technical field

The invention belongs to the technical field of storage library systems, in particular to a structural integrity detection and optimization method based on logically irrelevant fragmentation of metadata.

Background technique

The organization of the metadata in the repository system, that is, the structure of the metadata presents a complex structure that is multi-level, hierarchical and dynamically changing. Therefore, maintaining the consistency of the system is an important task. Consistency in the repository system includes: (1) Operational consistency: it involves the interaction between repository applications and is closely related to the concept of repository transactions. It is further divided into cooperative atomicity and concurrent multi-user access. (2) Metadata integrity: including structural integrity and good format. Well-formed ensures the syntactic correctness of element definitions in a meta-level, while structural integrity ensures that elements in one level conform to type definitions in an adjacent, higher meta-level.

Structural integrity is an important part of repository system consistency. If structural integrity is not guaranteed, repository system applications may modify or create metadata elements in the _Mn layer to conflict with their metaclasses in the Mn ₊₁ layer. For example, an operation that might read a property of an element whose metaclass does not exist is invalid. A database system includes M ₀ to M ₂ layers, where the content of M ₂ layer is fixed. In order to provide a customizable and extensible system framework, the repository system introduces the M _{3 layer that allows users to define the M 2 layer} . At runtime, the M ₀ , M ₁ and M ₂ layers can be dynamically modified. Therefore, It may lead to conflict problems between adjacent layers, that is, structural integrity problems. Other systems do not face this problem because they assume that the system framework is static at runtime.

However, the high computational overhead makes the automatic detection of structural integrity increasingly a thorny problem. There are four main reasons for this: (1) The amount of metadata has grown rapidly in recent years; (2) The update frequency of metadata is very high; (3) The set of constraints is getting bigger and bigger; (4) The internal complexity of constraints Therefore, how to optimize the structural integrity detection method to improve its efficiency has gradually become a research hotspot in the field of repository system consistency.

At present, the meta-object facility MOF has become the mainstream metadata repository specification in the world. However, a detection method for the structural integrity detection of the MOF storage system is to convert the structural integrity constraints into logical expressions, and then solve the constraint detection problem. Translated into logical reasoning problems, such as Duboisset et al. (Duboisset M, et al. Integrating the calculus-based method into OCL: Study of expressiveness and codegeneration, Proc of the 18th Int Workshop on Database and Expert Systems Applications. Piscataway, NJ: IEEE, 2007 : 502-506), Donald et al. (Donald C, et al. Using first-order logic to query heterogeneous internet data sources, Proc of the 2015 Int Conf on Soft Computing and Software Engineering. Holand: AcademicPress, Elsevier, 2015: 1-8) and Demuth et al. (Demuth B, et al. OCL as a specificationlanguage for business rules in database applications, LNCS 2185: Proc of the 4th Conf on UML. Berlin: Springer, 2006: 104-117). However, since structural integrity constraints include many complex mechanisms such as recursion, negation, and packet semantics, it is difficult for the proposed transformation algorithm to cover all the above mechanisms, although some algorithms have improved this defect to support as many constraint mechanisms as possible. However, the high complexity of the processing method makes the algorithm inefficient.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the deficiencies of the prior art, and to provide a structural integrity detection and optimization method based on logically unrelated fragments of metadata with reasonable design, simple method and high efficiency.

The present invention solves the existing technical problems and adopts the following technical solutions to realize:

A structural integrity detection and optimization method based on metadata logically irrelevant fragmentation, comprising the following steps:

Step 1. Form the repository metadata and data into a description logic SHIQ metadata knowledge base;

Step 2. Perform logically independent sharding of the SHIQ metadata knowledge base;

Step 3: Perform structural integrity checks on logically unrelated shards;

The specific implementation method of the step 2 includes the following steps:

为SHIQ元数据知识库；(1) Calculate the attribute deduction fragment of the element a given by the SHIQ metadata knowledge base according to the criteria 1 and 2

for SHIQ metadata knowledge base;

(2) Add all class assertions of element a into

中的每个R₀(a，b)以及满足

的每个R，判断

是否满足，如果是，则将R₀(a，b)、论据

中的断言以及

中的断言添加进

⑶ for

for each R ₀ (a, b) in and satisfying

for each R, judging

Whether it is satisfied, if so, then R ₀ (a, b), the argument

assertions in and

The assertion in the add in

⑷Calculation

The criterion 1 is: attribute assertion with element a as the first element or the second element in the SHIQ metadata knowledge base;

Said criterion 2 is: attribute assertions in the role path from element a to element b in the SHIQ metadata knowledge base, these assertions have the same transitive parent role.

The step 1 includes: respectively formalizing the meta-level M _n+1 level and the instance level M _n level in the repository, where n is 0 or 1.

The formalized method of the meta-level M _n+1 layer is:

(1) Convert each metaclass in the meta hierarchy into a SHIQ concept, and enable two different metaclasses to have attributes of different types but the same name;

(2) Formalize a class C and a type C' in the meta-level into concepts and two reciprocal roles r ₁ and r ₂ ;

一个元类C₁的每个属性以及与元类C₁相关的每个聚合关联和一般关联都被元类C₂继承下来了，并适用于元类之间的多重继承关系。(3) Generalization relationship: If a metaclass C1 is a generalization of metaclass C2, it can be formalized as

Every attribute of a metaclass _C1 and every aggregate association and general association related to metaclass _C1 is inherited by metaclass _C2 and applies to multiple inheritance relationships between metaclasses.

The formalized method of the example _Mn layer is:

(1) If the element c of the _Mn layer is an instance of the metaclass C in its meta-level, it is formalized as: C(c);

(2) If the element c ₁ of the _Mn layer is associated with the element c ₂ , the corresponding metaclass C ₁ aggregates C ₂ through the aggregation association A, and the aggregation association A is formalized as the role in the Tbox, then it is formalized as: A(c ₁ , c ₂ );

(3) If the element c ₁ of the _Mn layer is associated with the element c ₂ , the corresponding metaclass C ₁ is related to the meta class C ₂ through a general association, and the general association between the meta class C ₁ and the meta class C ₂ is formalized as the concept and Roles r ₁ , r ₂ , then the relationship between c ₁ and c ₂ can be formalized as three assertions: A(a); r ₁ (a, c ₁ ); r ₂ (a, c ₂ ).

The method of the step 3 is: detecting the generic relationship of a single metadata element a and detecting the attribute relationship of the metadata element a and the metadata element b are carried out on the fragment containing the metadata element a and the metadata element b; All instance elements of a metaclass or checking all instance elements associated by an attribute is to execute the same query on fragments in parallel and then combine the results.

The advantages and positive effects of the present invention are:

Aiming at the characteristics of the MOF repository, the present invention converts different levels of metadata into the description logic SHIQ knowledge base. On this basis, it proposes a formal definition of logically irrelevant pieces of metadata and gives a method for how to extract them. The method is complete Preserving all relevant information about a given metadata brings two benefits: on the one hand, detection for partial metadata can be performed on smaller datasets and not necessarily for the entire repository; The detection of the entire repository can be broken down into different pieces of metadata. Experimental results show that, on average, the size of metadata fragments generated by the present method is significantly smaller than its original size, and the efficiency of structural integrity detection performed on this basis can be significantly improved.

Description of drawings

Fig. 1 is the experimental result of the validity evaluation of the present invention;

Figure 2 is an example of a general association in the Mn ₊₁ layer in a MOF repository system;

Figure 3 is an example of an aggregate association in the Mn ₊₁ layer in the MOF repository system;

FIG. 4 is an example diagram of attribute type conflict.

Detailed ways

Embodiments of the present invention are described in further detail below in conjunction with the accompanying drawings:

A structural integrity detection and optimization method based on metadata logically irrelevant fragmentation, comprising the following steps:

Step 1: Form the repository metadata and data into a description logic SHIQ knowledge base.

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

具体来说，当n＝1时，我们分别将M₂层和M₁层形式化进Tbox和Abox，检测的是M₂层和M₁层之间的一致性；当n＝0时，我们分别将M₁层和M₀层形式化进Tbox和Abox，检测的是M₁层和M₀层之间的一致性。下面分别进行介绍。The relationship between adjacent levels in the MOF framework is a type-instance relationship, so we formalize the information in the meta-level, that is, the M _n+1 (n is 0 or 1) layer as SHIQ Tbox

The concept definition in , and the elements in the _Mn layer as instances are formalized into SHIQAbox

Specifically, when n= ₁ , we formalize the _M2 and M1 layers into Tbox and Abox, respectively, and detect the consistency between the _M2 and M1 layers; when n ₌ 0, we _The M1 layer and the M0 layer are formalized into _Tbox and _Abox respectively, and the consistency between the M1 layer and the _M0 layer is detected. They are introduced separately below.

1. Formalization of the Mn ₊₁ layer

(1) Meta class and meta attribute

In the meta hierarchy, a metaclass is also a class, so we do not distinguish between metaclasses and classes. Since both metaclasses and SHIQ concepts are used to describe collections of instances, we convert each metaclass into a SHIQ concept.

C＇。若a存在多重性i..j，则将该多重性形式化为：

上述断言精确地指明了对于概念C的每个实例c，所有通过a关联到c的对象都是C＇的实例，并且精确反映了属性名在整个元层次中的不唯一性，即两个不同的元类可以拥有类型不同但名字相同的属性。Since an attribute a of class C of type C' associates each instance of C to an instance of C', the attribute a is a binary relationship between an instance of C and an instance of C', so we put the attribute a in the form into a SHIQ role, which can be represented by the following assertion:

C'. If a has multiplicity i..j, then the multiplicity is formalized as:

The above assertion precisely specifies that for each instance c of concept C, all objects related to c through a are instances of C', and accurately reflects the non-uniqueness of attribute names in the entire meta-level, that is, two different 's metaclass can have properties of different types but the same name.

(2) General association

A general association in the meta-level is shown in Figure 2. Used to indicate a binary relationship between instances of two metaclasses. Each general association contains two association ends and corresponds to a corresponding association class. A multiplicity constraint exists at each association end. Unlike properties, generally associated names are unique within the MOF framework.

We formalize the general association between classes C and C' (the association ends are r ₁ and r ₂ , respectively) as a concept A and two reciprocal roles r ₁ and r ₂ , where r ₁ is used to describe the association end r ₁ , which takes C and C' as the first and second elements, respectively. Therefore, the value constraints of the elements of r ₁ are formalized as:

The relationship between r ₁ and r ₂ is formalized as r ₂ ≡ r ₁ ˉ. The multiplicity i ₁ ..j ₁ of r ₁ and the multiplicity i ₂ .. j _{2 of r 2 are} respectively formalized as:

(3) Aggregate association

The aggregation association in the meta-level is shown in Figure 3, which is used to indicate the part-whole relationship between instances of two metaclasses, which is a binary relationship. For example, an aggregate association between LevelBasedHierachy and HierarchyLevelAssociation indicates that each instance of LevelBasedHierachy consists of a set of instances of HierarchyLevelAssociation.

Since an aggregate association is essentially a form of a general association, the method of transforming an aggregate association is the same as that of a general association, and the distinction between the containing class and the contained class in the aggregation is not lost. The first element of our agreement on the role is the containing class.

(4) Generalization

The generalization relation in the MOF framework states that every instance of a subclass is also an instance of the superclass. So instances of subclasses inherit the properties of the parent class, in addition they can define their own properties.

由于

的语义是基于子集理论的，因此在SHIQ中如果给定断言

把C₁作为第i个要素的角色的每个元组也可以把C₂的实例作为第i个要素，因为它也是C₁的实例。因此在形式化中，C₁的每个属性以及与C₁相关的每个聚合关联和一般关联都被C₂继承下来了。此外这种形式化方式也完全适用于元类之间的多重继承关系。The generalization relation is supported by SHIQ. If a metaclass _C1 is a generalization of metaclass _C2 , we can formalize it as

because

The semantics of is based on subset theory, so in SHIQ if an assertion is given

Each tuple that has _C1 as the role of the ith element can also have an instance of _C2 as the ith element, since it is also an instance of _C1 . So in the formalization, every property of _C1 and every aggregate association and general association related to _C1 is inherited by _C2 . In addition, this formalization is also fully applicable to the multiple inheritance relationship between metaclasses.

2. Formalization of the _Mn layer

转换分三种情况：Each element in the _Mn layer is an instance of the corresponding metaclass in the Mn ₊₁ layer, and the relationship between the elements is an instance of the corresponding association between the metaclasses, so the _Mn layer element should be transformed into the Abox of the SHIQ knowledge base

There are three cases of conversion:

(1) If the element c of the _Mn layer is an instance of the metaclass C in its meta-level, it is formalized as: C(c);

(2) If the element c ₁ of the _Mn layer is associated with c ₂ , the corresponding metaclass C ₁ (or its ancestor) aggregates C ₂ (or its ancestor) through the aggregation association A, and the aggregation association A is formalized as the role in the Tbox A, then formalize it as: A(c ₁ , c ₂ );

(3) If the _Mn layer element c ₁ is associated with c ₂ , the corresponding metaclass C ₁ (or its ancestor) is associated with the metaclass C ₂ (or its ancestor) through a general association, and the general association is formalized as Concept A and roles r ₁ , r ₂ , the relationship between c ₁ and c ₂ can be formalized as three assertions: A(a); r ₁ (a, c ₁ ); r ₂ (a, c ₂ ) .

Step 2: sharding the SHIQ metadata knowledge base logically irrelevant.

1. The basic idea of logically irrelevant sharding

下面讨论如何对元数据进行逻辑无关分片。首先给出一些定义。Through the transformation of step 1, we obtain the metadata knowledge base

The following discusses how to shard the metadata logically independently. First some definitions are given.

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

中所有元数据元素的签名记为 Definition 1 (Signature): Given Abox

Assert γ, the set of metadata elements appearing in γ is called the signature of γ, denoted as Sig(γ).

The signature of all metadata elements in

中或者存在角色R_i(a_i，a_i+1)，或者存在角色R_iˉ(a_i+1，a_i)，则称元数据元素a₁和a_n之间存在角色路径。Definition 2 (role path): if for i=1,...,n-1,

There is either a role R _i (a _i , a _i+1 ), or a role R _i ˉ(a _{i +1} , a _i ), then there is a role path between the metadata elements a ₁ and an.

Role paths can contain inverse roles. For example, given R ₁ (a ₁ , a ₂ ), R ₂ (a ₃ , a ₂ ), R ₃ (a ₃ , a ₄ ), the character path from a ₁ to a ₄ is {R ₁ , R ₂ ˉ , R ₃ }, conversely the role path from a ₄ to a ₁ is {R ₃ ˉ, R ₂ , R ₁ ˉ}.

A complete query on the metadata knowledge base will lead to inefficiency and unruly reasoning. Considering that the metadata in the metadata knowledge base can be decomposed into different logically unrelated pieces, we can decompose the query into different metadata pieces. This reduces the amount of metadata to be queried and queries can be executed in parallel. For example, to query information related to an instance of the metadata element Dimension, we only need to perform a query on the metadata fragment containing the instance of Dimension. In order to maintain the completeness of the query results, the metadata fragment must be logically independent, that is, the fragment must be a closure of the logical implication of a given metadata element. Based on the above analysis, we give the formal definition of the metadata logically independent fragment:

是元数据知识库，集合S是签名。

的子集

称为签名S的逻辑无关片断当且仅当对于满足Sig(γ)

的任意断言γ(类断言或者属性断言)，有

等价于

Definition 3 (Metadata logically irrelevant fragment): Let

is the metadata repository, and the set S is the signature.

subset of

A logically independent segment called a signature S if and only if Sig(γ) is satisfied for

For any assertion γ (class assertion or attribute assertion), there are

Equivalent to

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

总是S的逻辑无关片断)，因此定义3并没有确保签名S的逻辑无关片断的唯一性。Definition 3 specifies the necessary and sufficient conditions for becoming a logically irrelevant piece of metadata, which ensures the completeness of the logical implication of metadata elements in the signature S. However, according to Definition 3 and the monotonicity of SHIQ,

Any superset of is also a logically unrelated fragment of S (such as the entire Abox

is always a logically irrelevant fragment of S), so definition 3 does not ensure the uniqueness of the logically irrelevant fragment of signature S.

Our goal is to carve out precise pieces of metadata that contain only the assertions that are essential for a given signature, so that the resulting shards have minimal size while maintaining information integrity. Simply put, for assertions to be necessary for a given signature S, they must be able to affect the logical conclusion of any metadata element in S. To distinguish such assertions, we give the following definitions:

及断言α，且

称

的片断

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

有

且

成立。α的论据记作

Definition 4 (Argument): Given Metadata Repository

and assert α, and

say

piece of

is an argument for α if and only if for any

Have

and

established. The argument for α is written as

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

成立。Definition 5 (Key Assertion): Given Metadata Knowledge Base

Metadata element a and assertion γ, called γ the key assertion of {a}, if and only if any assertion α (class assertion or attribute assertion) for a, has

established.

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

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

不仅保持了S中元素的类断言和属性断言的全部信息而且最小的规模。因此下面我们的任务就变成了如何为给定签名S计算仅包含关键断言的逻辑无关片断，即最小逻辑无关片断，除非特别指明，下文的逻辑无关片断均指最小逻辑无关片断。可以证明签名S中每个元素的逻辑无关片断的并集即为S的逻辑无关片断，因此我们仅需为S中单个元数据元素的逻辑无关片断的计算提出算法即可。According to the above definition, the argument for asserting α

is essentially the smallest fragment of the metadata knowledge base containing α, namely

Each assertion in is a key assertion of α. An assertion γ can affect the logical derivation of a metadata element in a signature S if and only if it appears in the argument of any attribute assertion or class assertion of that element, where γ is the key assertion of S. A logically irrelevant fragment constructed using all key assertions of S

Not only maintains all the information of class assertion and attribute assertion of elements in S but also the minimum size. Therefore, our task below becomes how to calculate a logically irrelevant fragment containing only key assertions for a given signature S, that is, the minimum logically irrelevant fragment. Unless otherwise specified, the following logically irrelevant fragment refers to the minimum logically irrelevant fragment. It can be proved that the union of the logically independent fragments of each element in the signature S is the logically independent fragment of S, so we only need to propose an algorithm for the calculation of the logically independent fragments of a single metadata element in S.

中的每个断言是否为a的关键断言，即必须测试每个断言是否与a的属性断言或类断言的推导有关。根据SHIQ的推理方法可知，元数据元素的类断言既依赖于类断言也依赖于属性断言，相反不同元数据元素之间的属性断言仅受属性断言的影响而与类断言无关，因此单个元数据元素a的逻辑无关分片可以通过三步实现：首先计算断言的集合

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

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

与

合并即得a的逻辑无关片断。To compute the logically unrelated shard given a single metadata element a, we need to decide

Whether each assertion in a is a key assertion of a, i.e., must test whether each assertion is related to the derivation of a property assertion or class assertion. According to SHIQ's reasoning method, the class assertion of metadata elements depends on both the class assertion and the attribute assertion. On the contrary, the attribute assertion between different metadata elements is only affected by the attribute assertion and has nothing to do with the class assertion. Therefore, a single metadata Logically independent sharding of element a can be achieved in three steps: first compute the set of assertions

where each assertion is related to the derivation of an arbitrary attribute assertion R(a,b) of a, we call this set an attribute deduction fragment, and then compute the set of assertions

where each assertion is related to the derivation of an arbitrary class assertion C(a) of a, we call this set a class deduction fragment, and finally the set

and

Merge to get the logically unrelated pieces of a.

的计算2,

calculation

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

其中γ是Abox断言而

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

的计算需要考虑两种断言：第一种断言形如

或

第二种断言是从a到b的角色层次中的断言，这些断言均有传递的父角色R₀且

例如R₁(a，a₁)，R₂(a₂，a₁)，

而R₁，R₂ˉ，

且R₀是传递角色。由第一种断言我们得到准则1：

中以a作为第一个要素或第二个要素的属性断言，由第二种断言我们得到准则2：

中从a到b的角色路径中的属性断言，这些断言具有同一个传递父角色。因此同时满足准则1和准则2的属性断言的集合即为元数据元素a的属性演绎片断

Attribute deduction fragment of metadata element a

Each assertion in is related to the derivation of an arbitrary property assertion R(a,b) of a, so

where γ is the Abox assertion and

is the argument for R(a,b). Since both role hierarchies and passing roles have an impact on attribute assertions, so

There are two kinds of assertions that need to be considered for the computation of : the first assertion has the form

or

The second type of assertion is an assertion in the role hierarchy from a to b, which all have a passed parent role R ₀ and

For example R ₁ (a, a ₁ ), R ₂ (a ₂ , a ₁ ),

And R ₁ , R ₂ ˉ,

And R ₀ is the transfer role. From the first assertion we get criterion 1:

With a as the attribute assertion of the first element or the second element, we get criterion 2 from the second assertion:

Attribute assertions in the role path from a to b that have the same transitive parent role. Therefore, the set of attribute assertions that satisfy both criterion 1 and criterion 2 is the attribute deduction fragment of metadata element a

的计算3.

calculation

的基础上进一步计算

由于

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

其中γ是Abox断言而

是C(a)的论据。To calculate the logically unrelated fragment of metadata element a, it is necessary to

on the basis of further calculation

because

Each assertion in is related to the derivation of an arbitrary class assertion C(a) of a, so

where γ is the Abox assertion and

is the argument for C(a).

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

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

仅当元素a的断言的支撑概念被C所包含，才会有C(a)成立，因此为了识别与a的类断言的推导有关的断言，必须确定该断言的支撑概念被某个概念所包含。例如令

若要识别R₀(a，b)是否与a的类断言推导有关，必须确定R₀(a，b)的支撑概念被某个概念所包含，即是否有As mentioned earlier, the derivation of class assertions for metadata elements in SHIQ depends on both class assertions and attribute assertions, so the class assertion for a is

essential component. To identify property assertions affecting C(a), it is also necessary to

Each assertion in is authenticated. Given metadata knowledge base

C(a) holds only if the supporting concept of the assertion of element a is contained by C, so in order to identify an assertion related to the derivation of the class assertion of a, it must be determined that the supporting concept of the assertion is contained by a concept . e.g. order

To identify whether R ₀ (a, b) is related to the class assertion derivation of a, it must be determined that the supporting concept of R ₀ (a, b) is contained by a concept, that is, whether there is

且b∈C₁。不难看出通过将C₁替换为B、C₂替换为A后上式是可满足的，因此可知R₀(a，b)与C₂(a)的推导有关，即R₀(a，b)在C₂(a)的论据中因而应该被加入

不仅如此，由于C₁(b)也是推导出C₂(a)的要素，

中的断言也应该被加入

in

And b∈C ₁ . It is not difficult to see that the above formula can be satisfied by replacing C ₁ with B and C ₂ with A, so it can be seen that R ₀ (a, b) is related to the derivation of C ₂ (a), that is, R ₀ (a, b ) should therefore be added to the argument for C ₂ (a)

Not only that, since C ₁ (b) is also an element for deriving C ₂ (a),

Assertions in should also be added

此时R₀(a，b)仍然与A(a)的推导有关，但是按照公式(1)判断R₀(a，b)的支撑概念是否被某个概念所包含时却发现它是不可满足的，因此为了包含关于元数据元素a的全部信息，应将公式(1)扩展为：The above example only considers a single property assertion that affects the deduction of a class assertion, in fact the latter can sometimes be affected by multiple assertions, e.g.

At this time, R ₀ (a, b) is still related to the derivation of A (a), but according to formula (1), when judging whether the supporting concept of R ₀ (a, b) is contained by a certain concept, it is found that it is unsatisfiable , so in order to include all the information about the metadata element a, formula (1) should be extended to:

如果把SHIQ的数量限定考虑在内，公式(2)应进一步扩展为：where C3 is the integration _of all other information for element a and

If the quantitative limitation of SHIQ is taken into account, Equation (2) should be further extended to:

且

公式(2)中

的仅是≥nR.C₁的特例并且

代表C₁元素a的R-邻居。公式(3)是识别影响C(a)的属性断言的最一般形式，它表明在元数据知识库中，对于影响元数据元素a的类断言的任意属性断言R(a，b)，相应的支撑概念必被某个概念所包含并且对于任意的数量限定，a的R-邻居的数目应不少于限定的数目。in

and

In formula (2)

is only a special case of ≥nR.C ₁ and

represents the R-neighbors of _C1 element a. Equation (3) is the most general form of identifying attribute assertions affecting C(a), it shows that in the metadata knowledge base, for any attribute assertion R(a, b) affecting the class assertion of metadata element a, the corresponding The supporting concept must be contained by a concept and for any number of constraints, the number of R-neighbors of a should be no less than the number of constraints.

4. Execute metadata logic independent sharding algorithm

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

其中每个断言都与a的任意类断言C(a)的推导有关，最后求二者的并集即得a的逻辑无关片断。据此思路得到如下算法。Since the class assertion of a metadata element depends on both the class assertion and the attribute assertion, on the contrary, the attribute assertion between different elements is only affected by the attribute assertion and has nothing to do with the class assertion, so the logically irrelevant fragmentation of a single metadata element a should be First compute the property deduction snippet

where each assertion is related to the derivation of an arbitrary property assertion R(a,b) of a, and then computes the class deduction piece based on that

Each of these assertions is related to the derivation of an arbitrary class assertion C(a) of a, and finally the union of the two is obtained to obtain a logically irrelevant fragment of a. According to this idea, the following algorithm is obtained.

Step 3: Perform structural integrity checks on top of logically unrelated shards.

Since the fragments obtained by step 2 are closures of the logical implications of a given metadata element, logically independent fragmentation makes it possible to perform structural integrity checks on smaller sets of metadata or to perform the checks in parallel. According to the initial size of the metadata knowledge base, we can divide it into disjoint subsets of suitable size, and then generate the same number of logically unrelated fragments through Algorithm 1. Detecting the generic relationship of a single metadata element a and detecting the attribute relationship of two metadata elements a and b can be performed on the fragment containing a and b without necessarily targeting the entire metadata knowledge base; on the other hand, detecting a certain metadata All instance elements of a class or checking all instance elements associated by a property can execute the same query in parallel on each fragment and combine the results.

According to structural integrity constraints, if an operation modifies the type of an attribute in the meta-hierarchy, and the new type is not a superclass of the original type and the original type is a meta-class that already exists in the meta-hierarchy, if the element in the following hierarchy Structural integrity violations occur if they are not modified. This type of conflict can be detected by the following statement (assuming that the type of the attribute referencedType of the metaclass Property is changed from StructuredType to SimpleType, not a supertype such as DataType, as shown in Figure 4):

In the query of this example, the query atom referencedType(property, datatype) needs to be executed when calculating count1 and count2. This atom retrieves the entire metadata knowledge base according to the known property to determine all the datatypes referenced by the property. The computation additionally executes the query atom SimpleType(datatype), which retrieves the entire metadata repository to determine all datatypes belonging to SimpleType. Based on the logically unrelated sharding in step 2, both query atoms can be executed in parallel to improve detection efficiency.

The following example is the detection of aggregated multiplicity collisions. According to the structural integrity constraints, if an operation modifies the multiplicity of the aggregate end in the meta hierarchy, and the lower element is not modified accordingly, it will cause the corresponding instance number to conflict with the modified multiplicity. This type of conflict can be detected by the following statement (assuming that the multiplicity of the aggregation between Aggregation and AggregationEnd at AggregationEnd is changed from 1 to 2):

In this example, the calculation of count1 requires the execution of the query atom Aggregation-AggregationEnd(aggregation,aggregationEnd), which retrieves the entire metadata repository to determine all aggregationEnds associated with known aggregations through Aggregation-AggregationEnd, based on step 2 For logically independent sharding, the query atom can be optimized in parallel to improve detection efficiency.

In order to evaluate the effectiveness of the present invention, we conducted a large number of experiments, focusing on testing the improvement of the time performance of structural integrity detection by the optimization method. The set of instances for the experiment was taken from the MOF metadata repository system MBRS. The structure of the system consists of repository client, repository management module and data storage. The repository client is used to build repository applications on the system; the repository management module is used to process metadata and provide services for the repository client, which implements metadata logic-independent sharding and parallel processing; data storage It is composed of M ₀ layer and the metadata of each layer above it. The repository management module also includes: a set of well-defined MBRS interface APIs, the implementation of which is based on the extension of JMI reflection; the metadata manager, which organizes metadata into a hierarchical structure and manages the query of metadata at each layer and storage. MBRS uses Oracle11g database to store M ₀ layer data and metadata. Structural Integrity Conflicts are implemented in both system instances and artificially implanted. They cover all aspects of Structural Integrity, including conflicts related to the deletion and creation of packages, conflicts related to changing the multiplicity of association ends and attributes, Conflicts related to modifying references, etc. The experimental results show that the optimization method improves the detection efficiency of various structural integrity conflicts to varying degrees.

Validity tests are performed under the operating environment of an Intel Xeon E7-4830 eight-core CPU and 6GB of memory. The elapsed time of the classification test is measured in milliseconds, and the test results are shown in Figure 1. The figure shows the execution time of structural integrity detection for different scales of M ₀ , M ₁ , and M ₂ layers of metadata. The upper part is the time it takes to detect consistency when the _{number of} elements in the corresponding M1 and M0 layers is changed when the size of the _M2 layer metadata is small (24 classes). The black curve reflects the execution time without optimization measures, and the blue, orange, and purple curves represent the time spent on structural integrity testing when the M ₂ layer is divided into 2, 4, and 8 slices, respectively. _The lower part reflects the execution time when the _M2 level metadata is larger, and the corresponding M1 and _M0 level metadata is larger. It can be seen that the time spent performing structural integrity detection is linearly related to the metadata size when no optimization measures are adopted and the number of divided segments is 2, 4, and 8, which is in line with expectations. When the number of fragments is doubled, the detection time is not reduced to half of the original time. The reason should be that the fragmentation process itself takes a certain time. Nonetheless, an increase in the number of fragments resulted in a significant reduction in the time to perform the detection. It can also be seen from the experimental results that, on average, the optimization method improves the time efficiency significantly on medium and small-scale metadata sets.

It should be emphasized that the embodiments described in the present invention are illustrative rather than restrictive, so the present invention includes but is not limited to the embodiments described in the specific implementation manner. Other embodiments derived from the scheme also belong to the protection scope of the present invention.

Claims (5)

1. a structural integrity detection optimization method based on metadata logic irrelevant fragmentation, is characterized in that comprising the following steps: Step 1. Form the repository metadata and data into a description logic SHIQ metadata knowledge base; Step 2. Perform logically independent sharding of the SHIQ metadata knowledge base; Step 3: Perform structural integrity checks on logically unrelated shards; The specific implementation method of the step 2 includes the following steps: (1) Calculate the attribute deduction fragment of the element a given by the SHIQ metadata knowledge base according to the criteria 1 and 2

for SHIQ metadata knowledge base; (2) Add all class assertions of element a into

⑶ for

for each R ₀ (a, b) in and satisfying

for each R, judging

Whether it is satisfied, if so, then R ₀ (a, b), the argument

assertions in and

The assertion in the add in

⑷Calculation

The criterion 1 is: attribute assertion with element a as the first element or the second element in the SHIQ metadata knowledge base; Said criterion 2 is: attribute assertions in the role path from element a to element b in the SHIQ metadata knowledge base, these assertions have the same transitive parent role. 2. the structural integrity detection and optimization method based on metadata logically irrelevant fragmentation according to claim 1, is characterized in that: described step 1 comprises: meta-level M _n+1 level and instance level M in the storage repository _n layers are formalized separately, where n is 0 or 1. 3. the structural integrity detection optimization method based on metadata logically irrelevant fragmentation according to claim 2, is characterized in that: the formalized method of described meta-level M _n+1 layer is: (1) Convert each metaclass in the meta hierarchy into a SHIQ concept, and enable two different metaclasses to have attributes of different types but the same name; (2) Formalize a class C and a type C' in the meta-level into concepts and two reciprocal roles r ₁ and r ₂ ; (3) Generalization relationship: If a metaclass C1 is a generalization of metaclass C2, it can be formalized as

Every attribute of a metaclass _C1 and every aggregate association and general association related to metaclass _C1 is inherited by metaclass _C2 and applies to multiple inheritance relationships between metaclasses. 4. the structural integrity detection optimization method based on metadata logically irrelevant fragmentation according to claim 2, is characterized in that: the formalized method of described instance M _n layer is: (1) If the element c of the _Mn layer is an instance of the metaclass C in its meta-level, it is formalized as: C(c); (2) If the element c ₁ of the _Mn layer is associated with the element c ₂ , the corresponding metaclass C ₁ aggregates C ₂ through the aggregation association A, and the aggregation association A is formalized as the role in the Tbox, then it is formalized as: A(c ₁ , c ₂ ); (3) If the element c ₁ of the _Mn layer is associated with the element c ₂ , the corresponding metaclass C ₁ is related to the meta class C ₂ through a general association, and the general association between the meta class C ₁ and the meta class C ₂ is formalized as the concept and Roles r ₁ , r ₂ , then the relationship between c ₁ and c ₂ can be formalized as three assertions: A(a); r ₁ (a, c ₁ ); r ₂ (a, c ₂ ). 5. the structural integrity detection optimization method based on metadata logic irrelevant fragmentation according to claim 1, is characterized in that: the method of described step 3 is: detect the generic relationship of single metadata element a and detect metadata The attribute relationship of element a and metadata element b is performed on the fragment containing metadata element a and metadata element b; detecting all instance elements of a metaclass or detecting all instance elements associated with an attribute is the same. The query is executed in parallel on each fragment and the results are merged.

Images