Modern information systems may exploit numerous XML formats for communication. Each message may have its own XML format for data representation which causes problems with integration and evolution of their schemas. Manual integration and management of evolution of the XML formats may be very hard. We tackled this problem in our previous work, however, for simplicity reasons, we omitted the possibility of exploiting reusable schema parts. In this paper, we complement our previous work with additional methods for schema integration which exploit reusable schema parts that quite often appear in XML schemas. This further helps a domain expert to get a precise mapping to a conceptual diagram, which then integrates the XML formats and facilitates their evolution - a change that is made once in the conceptual diagram is propagated to the XML formats.
Today, XML is a standard for communication in various information systems like web services, etc. A web service provides an interface composed of several operations. The structure of incoming and outgoing messages is described in a form of XML schemas. If the XML schemas of communicating web services differ, the problem of their integration comes to the scene. When the XML schemas are integrated, another problem arises. Since the business evolves in time the XML schemas need to be adapted too.
We aim at the problem of integration of XML schemas by mapping them to a
common conceptual schema. In our previous work [
P202/11/P455 and in part by the grant SVV-2011-263312.
change occurs. Simply speaking, the change is made only once at the conceptual level
and then propagated to the affected XML schemas. It is also possible to exploit the
mappings to derive interfaces of semantic web services described in SAWSDL as we show
in [
Contributions In practice, a conceptual diagram and XML schemas exist separately,
i.e. there are no mappings between both levels. This disallows to exploit the integration
and evolution capabilities of our framework. In our work [
Our aim is not to develop new methods for measuring schema similarities. These
methods have been already intensively studied in the literature. Instead, we exploit the
existing ones and combine them together. For this, we provide an algorithm skeleton
that can be supplemented by various similarity methods. An important contribution of
the method, not considered by existing similarity methods, is an active participation of
a domain expert. This is necessary, since we need to achieve exact mapping.
Outline The rest of the paper is organized as follows. In Section 2, we present related
work. In Section 3, we briefly present a simplified version of our conceptual model for
XML. Section 4 briefly describes the algorithm from [
Recent literature (surveyed in [
In this section, we will introduce our conceptual model for XML. We follow the ModelDriven Architecture (MDA) principle which is based on modeling data at several levels of abstraction. The most abstract level contains a conceptual schema of the problem domain. The language applied to express the conceptual schema is called platformindependent model (PIM). The level below is the platform-specific level which specifies how the whole or a part of the PIM schema is represented in a particular platform. In our case, the platform is XML. 3.1
A PIM schema is based on UML class diagrams and models real-world concepts and relationships between them. It contains three types of components: classes, attributes and associations.
Definition 1. Let L be a set of string labels and D be a set of datatypes. A schema in the platform independent model (PIM schema) is a 9-tuple S = (Sc, Sa, Sr, Se, name, type, class, participant , card ), where: – Sc and Sa are sets of classes and attributes in S, respectively. – Sr is a set of binary associations in S. Se is a set of association ends in S. A binary association is a set R = {E1, E2}, where E1, E2 ∈ Se and E1 6= E2. For any two associations R1, R2 ∈ Sr it must hold that R1 ∩ R2 6= ∅ ⇒ R1 = R2. In other words, no two associations share the same end. – name : Sc ∪ Sa → L resp. name : Sr → L ∪ {λ} assigns a name to each class, attribute and association. name(R) = λ means that R ∈ Sr does not have a name. – type : Sa → D assigns a data type to each attribute. – class : Sa → Sc assigns a class to each attribute. For A ∈ Sa, we will say that A is an attribute of class(A) or A belongs to class(A). – participant : Se → Sc assigns a class to each association end. For R = {E1, E2} ∈ Sr, we will say that participant (E1) and participant (E2) are participants of R or that they are connected by R.
– card : (Sa ∪ Se) → C assigns a cardinality to each attribute and association end. The members of Sc, Sa, and Sr are called components of S.
We display PIM schemas as UML class diagrams. A class is displayed as a box with its name at the top and attributes at the bottom. An attribute is displayed as a pair comprising the attribute name and cardinality. The data type is omitted to make the diagram easy to read. An association is displayed as a line connecting participating classes with the association name and cardinalities.
For a given association R = (E1, E2), we will often use notation (C1, C2) as an equivalent of (participant (E1), participant (E2) if there are no more associations connecting C1 and C2. We will also need a construct called a PIM path.
Definition 2. A PIM path P is an ordered sequence hR1, . . . , Rni of associations from Sr, where (∀i ∈ {1, n})((Ri) = (Ci−1, Ci)). C0 and Cn are called start and end of P . Functions start and end return for P the start and end of P , respectively.
An example of a PIM path in our sample PIM depicted in Figure 1(a) is Path = h(Purchase, Item), (Item, Product ), (Product , Supply )i. Purchase and Supply are start and end of the PIM path, respectively. 3.2
The platform-specific model (PSM) enables to specify how a part of the reality is represented in a particular XML schema in a UML-style way. We introduce it formally in Definition 3. We view a PSM schema in two perspectives. From the grammatical perspective, it models XML elements and attributes. From the conceptual perspective, it delimits the represented part of the reality. Its advantage is clear – the designer works in a UML-style way which is more comfortable then editing the XML schema. Definition 3. Let L be a set of string labels and D be a set of datatypes. A PSM schema is a 16-tuple S0 = (Sc0 , Sa0, Sr0 , Se0 , Sm0, CS00 , name0, type0, class0, xf orm0, participant0, card0, cmtype0, attributes0, content0, repr0), where – Sc0 , Sa0, and Sm0 are sets of classes, attributes, and content models in S0, respectively. – Sr0 is a set of directed binary associations in S0. Se0 is a set of association ends in S0. A directed binary association is a pair R0 = (E10, E20), where E10, E20 ∈ Se0 and E10 6= E20. For any two associations R10, R20 ∈ Sr0 it must hold that R10 ∩ R20 6= ∅ ⇒ R10 = R20. – CS00 ∈ Sc0 is a class called schema class of S0. – name0 : Sc0 ∪ Sa0 → L resp. name0 : Sr0 → L ∪ {λ} assigns a name to each class, attribute and association. – type0 : Sa0 → D assigns a data type to each attribute. – class0 : Sa0 → Sc0 assigns a class to each attribute. For A0 ∈ Sa0, we will say that
A0 is an attribute of class0(A0) or A0 belongs to class0(A0). – participant0 : Se → Sc0 ∪ Sm0 assigns a class or content model to each as0 sociation end. For R0 = (E10, E20), where X10 = participant0(E10) and X20 = participant0(E20), we call X10 and X20 parent and child of R0, respectively. We will also sometimes call both X10 and X20 participants of R0 and say that X10 is the parent of X20 and X20 is a child of X10, denoted parent0(R0) and child0(R0), respectively. – xf orm0 : Sa0 → {e, a} assigns an XML form to each attribute. It specifies the XML representation of an attribute using an XML element declaration with a simple content or an XML attribute declaration, respectively. – card0 : Sa0 ∪ Se0 → C assigns a cardinality to each attribute and association end. – cmtype0 : Sm0 → {sequence, choice, set} assigns a content model type to each content model. We distinguish 3 types: sequence, choice and set, respectively. – attributes0 : Sc0 → 2(Sa0) assigns an ordered sequence of distinct attributes to each class C0. It must hold that A0 ∈ attributes0(C0) ⇔ C0 = class0(A0). – content0 : Sc0 ∪ Sm0 → 2(Sr0) assigns an ordered sequence of distinct associations to each class or content model X0. It must hold that R0 ∈ content0(X0) ⇔ X0is the parent of R0. – repr0 : Sc0 \ {CS00 } → Sc0 \ {CS00 } assigns a class C0 to another class C0. C0 is called structural representative of C0. It must hold that C0 6∈ repr0(C0). Neither C0, nor C0 can be the schema class.
The graph (Sc0 ∪ Sm
0 , Sr0 ) with classes and content models as nodes and associations as directed edges must be a directed forest with one of its trees rooted in the schema class CS00 . Members of Sc0 , Sa0, Sr0 , and Sm0 are called components of S0.
A sample PSM schema is depicted in Figure 1(b). As can be seen from the definition, PSM introduces similar constructs to PIM: classes, attributes and associations.
The PSM-specific constructs have precisely defined semantics. Briefly, a class models a complex content. The complex content is specified by the attributes of the class and associations in its content (their ordering is given by functions attributes0 and content0). An attribute models an XML element declaration with a simple content or Customer - login - name - phone - email [1,*] - code - price - color 0..*
Supplier - name - phone - email provides
1..*
Supply - date - price - amount Address - street - city - country
Items
item
Item
1..*
|
ItemAmount
- amount
- price
Address
- street
- city
- country
- gps [
- code - date - status 0..1
Address ShipAddr - gps
Address BillAddr contains 1..*
Item - amount - price - tester
(a) Sample PIM schema PurchRQSchema purchaseRQ Purchase @ code @ date @ version billto cdetail shipto
items (b) Sample PSM schema XML attribute declaration depending on its XML form (function xf orm0). An association models an XML element declaration with a complex content if it has a name. Otherwise, it models only that the complex content modeled by its child is nested in the complex content modeled by its parent. If a class C0 is a structural representative of another class repr0(C0), the complex content modeled by C0 extends the complex content modeled by repr0(C0). This is exactly our definition of areusable schema part as multiple PSM classes can be structural representatives of another target PSM class, meaning that all of them reuse the definition of the target PSM class.
The PSM schema represents a part of a PIM schema. A class, attribute or association in the PSM schema may be mapped to a class, attribute or association in the PIM schema. In other words, there is a mapping which specifies the semantics of classes, attributes and associations of the PSM schema in terms of the PIM schema. The mapping must meet certain conditions to ensure consistency between PIM schemas and the specified semantics of the PSM schema. This mapping is called interpretation of the PSM schema against the PIM schema.
Definition 4. Let R = {E1, E2} ∈ Sr be an association. An ordered image of R is a pair RE1 = (E1, E2) (or RE2 = (E1, E2)).
We will use S−→r to denote the set of all ordered images of associations of S0, i.e. S−→r = SR∈Sr0 {RE1 , RE2 }. We need these definitions to be able to distinguish direction of PIM association, which is normally not needed in PIM.
Definition 5. An interpretation of a PSM schema S0 against a PIM schema S is a partial function I : (Sc0 ∪ Sa0 ∪ Sr0 ) → (Sc ∪ Sa ∪ S−→r) which maps a class, attribute or association from S0 to a class, attribute or ordered image of an association from S, respectively. For X0 ∈ (Sc0 ∪ Sa0 ∪ Sr0 ), we call I(X0) interpretation of X0. I(X0) = λ denotes that I is not defined for X0. In that case, we will also say that X0 does not have an interpretation.
Let a function context 0I : Sc0 ∪ Sa0 ∪ Sr0 ∪ Sm0 → Sc0 return for a given component X0 of S0 the closest ancestor class to X0 on path0(X0) so that I(context 0I (X0)) 6= λ. The following conditions must be satisfied:
I(CS00 ) = λ (∀C0 ∈ Sc0 s.t. repr 0(C0) 6= λ)(I(C0) = I(repr 0(C0))) (∀A0 ∈ Sa0 s.t. I(A0) 6= λ)(class(I(A0)) = I(context 0I (A0))) (∀R0 ∈ Sr0 s.t. I(child 0(R0)) = λ)(I(R0) = λ) (1) (2) (3) (4) (∀R0 ∈ Sr0 s.t. I(child 0(R0)) 6= λ)(I(R0) = (I(context 0I (R0)), I(child 0(R0))) (5) Each PSM class, attribute or association can have an interpretation against a component of the PIM schema. This mapping means that in the PSM schema the particular PSM component models the concept represented by the target PIM component in the PIM schema.
Note that in the context of mapping of a PSM schema to a PIM schema (interpretation construction), the content models present in a PSM schema are irrelevant as they do not influence the semantics of PSM classes, attributes nor associations.
In this section we will enhance our interpretation reconstruction algorithm first
introduced in [
The algorithm builds an interpretation I of a PSM schema against a PIM schema. I must be correct, it must fulfil Definition 5. Moreover, it must be correct in the conceptual sense, i.e. a PSM component and its PIM interpretation must conceptually correspond to the same real-world concept. We ensure the formal correctness. The conceptual correctness is ensured by a domain expert. 4.1
The basic algorithm works in three phases. Firstly, it measures initial similarities between PSM and PIM attributes and classes. Secondly, it creates an initial interpretation of PSM classes, whose initial similarity to some PIM class is higher than a given threshold. Becasue this is done automatically, there is a possibility that this initial interpretation is not correct. Therefore, it has to be verified by a domain expert. Nevertheless, the initial interpretation usually helps to avoid confirming lots of obvious mapping matches because the domain expert just needs to confirm a list of pre-mapped classes (or uncheck the incorrect ones). The confirmed initial interpretation now becomes a final interpretation and the algorithm moves to its third phase. It builds interpretation of the unmapped PSM classes with an assistance of a domain expert.
We will suppose a PSM schema S0 and a PIM schema S on the input. The output of the algorithm is an interpretation I of S0 against S. We will enhance parts of the algorithm where the knowledge of reusable schema parts (structural representants) can help. But first, let us motivate a definiton. LetC0 be a structural representant of C00. Due to condition 2 of Definition 5, the following must hold: I(C0) = I(C00). This means that both C0 and C00 need to have the same interpretation in the PIM schema (or both must remain uninterpreted). This also means (from condition 3 of Definition 5 and from the definition of context 0(C0)), that PSM attributes of C0 and C00 can only have attributes of the same PIM class as interpretation. Intuitively, C0 and C00 represent the same concept in the PSM schema and we can suppose that their names also refer to the same concept. Note that the same goes for every PSM class C000, that would be a structural representant of C0. This justifies the follwing definition.
Definition 6. Let a function ss0 : Sc0 → 2(Sc0) return for each PSM class C0 a set of PSM classes, which are (transitively) related to C0 by the structural representative (repr 0) relation.
For example, let C10, C20, C30 and C40 be PSM classes. Let repr 0(C10) = λ, repr 0(C20) = C10, repr 0(C30) = C10 and repr 0(C40) = λ. Then ss0(C10) = ss0(C20) = ss0(C30) = {C10, C20, C30} and ss0(C40) = ∅. 4.2
Attributes. Firstly, the algorithm measures a similarity for each pair of one PIM and one PSM attribute. This is based on their names and datatypes. This phase is not affected by the structural representants and we can skip the detailed description. Suffice to say that results of initial attribute similarity are used in function Sinit−attrs(C0, C) below, which gives us similarity of a PSM class and a PIM class based on their attributes. Classes. Let (C0, C) ∈ C0 × C. The similarity between C0 and C is customizable, in this paper it is a weighted sum
Sinit−class (C0, C) = winit−class ∗ Sinit−attrs (C0, C)
+ (1 − winit−class ) ∗ max{Sstr (name0(C0), name(C)), Sstr (xml 0(C0), name(C))} where winit−class ∈ (0, 1) is a weighting factor and xml0(C0) is a name of the parent association of C0 if any exists. Sinit−attrs (C0, C) is defined as Sinit−attrs (C0, C) = PA0∈attributes0(C0) max A∈attributes(C) (Sinit−attr (A0, A)), i.e. it finds for each PSM attribute A0 ∈ attributes 0(C0) the most similar PIM attribute A of C and summarizes these similarities.
This is the first place where we can exploit structural representants. For a PSM class C0, we can take attibutes of every C00 ∈ ss 0(C0), because if those classes have an interpretation, it is the same PIM class for all of them (and similarly for the attributes). Therefore, we define functionattrssr : Sc0 → 2(Sa0) = ∪Ci0∈ss0(C0)attributes 0(Ci0) and we can redefine:
Sinit−attrs (C0, C) = PA0∈attrssr (C 0) max A∈attributes(C) (Sinit−attr (A0, A)) 4.3
The initial class interpretations are set according to the initial class similarities precomputed in the previous step. It is a simple procedure that takes the most similar pairs of PSM and PIM classes (with similarity greater than a given threshold) and sets these pairs as initial interpretations. Here is another place were we exploit structural representants. Because of the fact that all PSM classes of ss 0(C0) need to have the same interpretaion (or none at all), when we initially interpret one of them, we can as well initially interpret all of them and the interpretation will be the same PIM class. And, of course, due to the possibility that this interpretation is incorrect, we can provide the user with the comfort of accepting/rejecting the whole group at once. If the domain expert chose to consider structural representatives in both the attribute similarity and the name similarity, this is an effect of the previous modification. The reason for this is that all of the classes from the group will have the same initial similarities, because when we computed the initial similarities for one class from the group, we included all the other classes as well. If, however, the domain expert chose to ignore structural representants at some stage, the similarities will be different and this adjustment may come in handy. 4.4
The third part of the algorithm iteratively traverses the PSM classes in Sc0 in pre-order and helps the domain expert to build the final interpretation. Individual steps are shown in Algorithm 1. For an actual PSM class C0 ∈ Sc0 , the algorithm firstly constructs I (C0) (lines 2 - 6) and also sets the interpretation for all the PSM classes of ss 0(C0) (lines 7 - 9). This is because all of them must have the same interpretation. Secondly, the algorithm constructs I (A0) for each A0 ∈ attributes(C0) (lines 10 - 22). Finally, it constructs I (R0) for each R0 ∈ content(C0) (lines 23 - 25). It can be shown that this algorithm runs in O(N 3) where N is the number of PSM classes and in O(n × log(n)) where n is the number of PIM classes.
Algorithm 1 Interpretation Construction Algorithm 1: for all C0 ∈ Sc0 in post-order do 2: for all C ∈ Sc do 3: Sclass(C0, C) ← wclass ∗ Sinit−class(C0, C) + (1 − wclass) ∗ Sadj−class(C0,C) 1 4: 5: 6: 7: 8: 9: 10: 11: 12: end for Offer the list of PIM classes sorted by Sclass to the domain expert.
I(C0) ← C where C ∈ Sc is the PIM class selected by the domain expert. for all C00 ∈ ss0(C0) do
I(C00) ← C {here we set the interpretation for the whole group of PSM classes} end for for all A0 ∈ attributes (C0) do for all A ∈ Sa do
Sattr(A0, A) ← wattr ∗ Sinit−attr(A0, A) + (1 − wattr) ∗ μ(I(C0),class(A))+1 1 Class Interpretation To construct I (C0), the algorithm firstly computesSclass (C0, C) for each C ∈ Sc0 at line 3. It is a weighted sum of two similarities. The former is the initial similarity Sinit−class (C0, C). The other is a reversed class similarity adjustment Sadj −class (C0, C) which we discuss in a while. The algorithm then sorts the PIM classes by their similarity with C0 and offers the sorted list to the domain expert at line 5. The expert selects a PIM class from the list and the algorithm sets I (C0) to this selected class at line 6. Class similarity adjustment Sadj −class (C0, C) is computed on the base of the completed part of I, which includes confirmed initial interpretation.Sadj −class (C0, C) is a combination of distances between C and PIM classes Di which are interpretations of the interpreted neighbors of C0. μ(C, D) is the distance between PIM classes C and D.
Note that Algorithm 1 is a skeleton which needs to be supplemented with methods for (1) measuring distances between PIM classes, (2) combining distances, and (3) selecting candidates for C0 structural similarity adjustment. In this paper, we use basic methods to show that the general idea works. For measuring the distance between two PIM classes C and D, we use the length of the shortest PIM path connecting C and D. As the distance combination method, which results in the aimed Sadj −class (C0, C), we can also choose from various possibilities. In this paper, we use n Sadj−class(C0, C) = (X μ(C, I(Di0)) ) + 1
n i=1 where D10, . . ., Dn0 are the selected interpreted neighbors of C0. Sadj−class(C0, C) is the average of the lengths of the shortest PIM paths between C and each I(Di0).
Finally, we need to decide which mapped neighbors of C0 will be selected to
compute Sadj −class (C0, C). We can choose among children of C0 or previous siblings of
C0, as these were already interpreted by the domain expert in this part of the algorithm.
Because we have some PSM classes interpreted via the initial interpretation, we can
use them as another candidates for structural similarity adjustment, if they are close
enough. Therefore, we can also select interpreted following siblings, interpreted parent
or interpreted ancestors as candidates for structural similarity adjustment. These options
are described and experimented with in [
Here is another moment where we can exploit reusable schema parts in a form of structural representants. As we choose which interpreted neighbors of C0 to use for the structural similarity adjustment, we can also work with the same type of interpreted neighbors of all classes of the group ss0(C0). The reasons are the same, because the interpretation of all classes of the group must be the same PIM class.
The rest of the algorithm remains unaffected by the structural representatives, so
we describe it only briefly. For details, see [
In this section, we briefly evaluate the effect of structural representants on building
interpretations of PSM classes. For more detailed experiments with the overall method
see [
Let us suppose an actual PSM class C0. Let the domain expert set I(C0) to a PIM class C either when asked or when confirming the initial interpretation. We measure the precision of the algorithm from two points of view. Firstly, we measure the position of C in the list of PIM classes offered to the expert sorted by their Sclass . We call this precision a global precision PG:
PG = (( X 1 −
C0∈Sc0 order (C) − 1 n where n denotes the size of Sc, n0 denotes the size of Sc0 , and order (C) denotes the order of C in the list. If there are more PIM classes with the same similarity to C0, order (C) is the order of the last one. PG = 0 (resp. 1) if for each PSM class C0, the selected PIM class was the last (resp. first).
The global precision is not sufficient. When C is the first class, there can be other PIM classes before C which have their similarity to C0 close to Sclass (C0, C) and make it harder to distinguish whether C is or is not a good match for C0. We therefore propose another metric called local precision which measures the amount of PIM classes with their similarity to C0 close to Sclass (C0, I(C0)). It is defined as
PL = (( X 1 −
C0∈Sc0 close(C) − 1 n )/n0) ∗ 100 where close(C) denotes the number of PIM classes with their similarity to C0 close to Sclass (C0, C). The term close similarity can be defined in various ways. In this paper, we say that y is close to x if y ∈ (x − 0.1, x + 0.1).
Intuitively, the effect of using structural representants is a reduction of the number of mapping offers the domain expert needs to go through. This is because when an interpretation of a PSM class C0 is constructed, it is automatically constructed for all PSM classes ss0(C0) and the domain expert no longer needs to create the interpretation for each one of them.
Additionally, the use of structural representants for class similarity computations may help with global and local precisions. This is, however, dependent on the texts present in the source PSM schema, its structure and selected methods of similarity measurements, which so far can not be determined automatically. Therefore, the experimental results are very complex and their description would not fit into this article. 6
In this paper, we studied the effect of exploiting reusable schema parts on techniques
used for mapping of XML formats to a conceptual diagram. We briefly described our
basic algorithm from [