One of the prominent characteristics of XML applications is their dynamic nature. When a system grows and evolves, old user requirements change and/or new requirements accumulate. Apart from changes in the interface, it is also necessary to modify the existing documents with each new version, so they are valid against the new specification. The approach presented in this work extends an existing conceptual model with the support for multiple versions of the model. Thanks to this extension, it is possible to define a set of changes between two versions of a schema. This work contains an outline of an algorithm that compares two versions of a schema and produces a revalidation script in XSL.
Recently, XML [
Requirements change during the life cycle of the system and so do the XML schemas. Without any tools to help, the old and new schema need to be examined by a domain expert. Each change must be identified, analyzed and all the relevant parts of the system modified and the existing documents updated. This can be a time-consuming and error-prone process, but, in fact, a significant portion of the operations could be performed automatically.
The existing approaches work directly at the level of XML schemas, which leads to problems with recognizing the semantics of each change. Our approach utilizes the conceptual model for understanding the semantics. Also, most of the existing approaches require the user to either revalidate the documents after ? This work was supported in part by the Czech Science Foundation (GA CˇR), grant number P202/10/0573, and by the grant SVV-2011-263312. every performed evolution operation, other require at least all the operations to be performed in one session and directly modify the old version (effectively replacing it with the new version). Our approach imposes no limits on the amount of operations performed between the versions and the amount of versions present in the systems.
The main aim of this paper is to simplify the whole process of system evolution and make the transition to the new version semi-automatic using our conceptual XML modeling framework with the support for multiple versions. We carry on by formally defining possible changes between versions. When changes are detected, we use this information to decide, whether the revalidation is necessary and if it is the case, we generate a script that revalidates existing XML documents against the new version. 1.1
The rest of this paper is organized as follows: in Section 2, we analyze the existing approaches. In Section 3, we introduce the XSEM conceptual model. In Section 4, we extend the model with versioning support. In Section 5, we formally define changes between versions. In Section 6, we outline how a revalidation script is generated. Section 7 concludes and lists the open problems and areas of future research. 2
Approaches can be categorized on the basis of the level where the changes are
made by the designer and detected by the algorithm as suggested in [
X-Evolution, proposed in [
X-Evolution system provides the user with a narrow set of evolution primitives that can be performed upon XML schemas of a certain format. There are no links to the conceptual model which could be utilized when new content needs to be added during document revalidation; thus, it is up to the user to write the adaptation clauses or update the documents after revalidation. Some very common real-world evolution operations are not considered in the evolution primitives, e.g. moving content, adding a wrapping element for elements or transforming attributes to subelements and vice versa. All algorithms and operations expect a single evolution primitive as an input. And only a single change is supported in each evolution cycle, evolution with multiple changes is not elaborated.
XML Evolution Management, XEM [
The proposed primitives are divided into two categories: 1) changes in DTD 2) changes in instance documents. It is proven that the proposed set of primitives is complete, in the sense that any possible change in DTD can be expressed as a sequence of application of the primitives. However, the method used in the proof in many common cases degenerates in removing a large part of the tree and creating it from scratch (e.g. when an element is renamed, it must be removed and then added under new name; if the root element is removed, the whole XML document is first deleted and its structure recreated again). In this process, the structure is created properly by the algorithm, but the data is lost. Again, as in the case of X-Evolution, the conceptual model is not considered and thus cannot be utilized when new content is added in the instance documents.
Unlike the previous approaches, CoDEX, Conceptual Design and Evolution
of XML schemas [
Conceptual modeling is a top-down approach to system and data design, which concentrates on correct depicting the problem domain – defining the particular concepts comprising the system and relationships between these concepts.
XSEM is an approach to modeling XML data using Model Driven
Architecture (MDA) [
A schema in a platform-independent model (PIM) models real-world concepts
and relationships between them without any details of their representation in a
specific data model (XML in our case). As a PIM, we use the classical model
of UML class diagrams in our work. This model is widely supported by the
majority of tools for data engineering and there exists the XMI [
For simplicity, we will also use the notation attributes (C ) to denote the set {A ∈ Sa : class(A) = C} and associations (C ) to denote the set {R ∈ Sr : (∃E ∈ R)(participant(E) = C)} for each class C ∈ Sc.
PIM schema components have a usual semantics. A class models a real-world concept. An attribute of that class models a property of the concept. And, an association models a kind of relationships between two concepts modeled by the connected classes. We display each PIM schema as a UML class diagram. Example 1. Figure 1 shows a sample PIM in XSEM modeling a component accepting purchases. Classes (Address, Purchase, . . .) are depicted as boxes with the list of attributes (street, city, . . .), associations as labeled lines connecting classes (bill-to, ordered, . . .). 3.2
A schema in a platform-specific model (PSM) models how a part of the reality modeled by the PIM schema is represented in a particular data model. In our case, we consider XML as the data model and our PSM schema specifies representation in a particular XML format. Our PSM allows for specifying more different XML formats on the base of the same PIM schema. As a PSM we also use UML class diagrams extended for the purposes of XML data modeling. We introduce PSM formally in Definition 2. Purchase 1..*ordered - code - date - status 1..* contains - amIteomunt 0..* - price - tester
Customer - login - name - phone - email [1,*]
Product 1..*delivers0..* - code - price - color
Supplier - name - phone - email provides 1..*
Supply - date - price - amount Definition 2. A platform-specific schema (PSM schema) is a 5-tuple S0 = (Sc0 , Sa0, Sr0 , Sm0, CS00 ) of disjoint sets of classes, attributes, associations, and content models, respectively, and one specific class CS00 ∈ Sc0 called schema class. S0 must be a forest with one of its trees rooted in CS0 0 . In addition, PSM schema defines functions name’, card’, type’, xform’, cmtype’ class’ and participant’: – Class C0 ∈ Sc0 has a name denoted name0(C0). – Attribute A0 ∈ Sa0 has a name, data type, cardinality and XML form denoted name0(A0), type0(A0), card0(A0) and xform’0(A0) ∈ {e, a}, respectively. Moreover, it is associated with a class from Sc0 denoted class0(A0) and has a position denoted indexOf(A0) within the all attributes associated with class0(A0). – Association R0 ∈ Sr0 is a pair R0 = (E10, E20) where E10 and E20 are called association ends of R0. E0 ∈ R0 has a cardinality denoted card0(E0) and is associated with a class from Sc0 denoted participant0(E0). participant0(E10) and participant0(E20) are called parent and child of R and denoted parent’0(R0) and child’0(R0), respectively. R0 has a name denoted name0(R0) and has a position denoted indexOf(R0) among associations with the same parent. – Content model M 0 ∈ Sm0 has a content model type cmtype’0(M 0) ∈ {sequence, choice, set}.
Sc ∪ Sr ∪ Sa ∪ (SS0∈S∗0 (Sc0 ∪ Sr0 ∪ Sa0)).
For simplicity, we will also use the notation attributes (C0 ) to denote the sequence (A0i ∈ Sa0 : class(A0) = C0 ∧ i = indexOf(A0)) for each class C ∈ Sc.
Let us denote N 0 = Sc0 ∪ Sm0. The graph Sb0 = (N 0, Sr0 ) with classes and content models as nodes and associations as ordered 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. The set of all PSM schemas will be denoted S∗0. Finally we define the set of all constructs (PIM and PSM): M =
The PSM constructs in a concrete PSM schema are linked to the PIM schema constructs (we will say that the PSM schema is derived from the PIM schema and the PSM constructs have an interpretation in the PIM). We will not include formal definition of interpretation in this paper and use these terms intuitively instead.
Example 2. Figure 2(a) shows a sample PSM schema modeling an XML document with a purchase. Again, classes, associations and attributes are depicted 0..1 shipto billto cdetail
PurchRQSchema purchaseRQ Purchase @ code @ date @ version items Items item Item 1..*
|
ItemAmount - amount - price (a) PSM schema
Address - street - city - country <purchaseRQ code="#" date="#" version="#"> <shipto gps="#"> <street>#</street> <city>#</city> <country>#</country> </shipto> <billto> <street>#</street> <city>#</city> <country>#</country> </billto> <cdetail login="#">
<name>#</name>
</cdetail>
<items>
<item code="#" tester="#"/>
<item code="#">
<amount>#</amount>
<price>#</price>
</item>
</items>
</purchaseRQ>
(b) XML document
similarly as in PIM schemas, the difference is in associations, which are now
directed. The diagram also contains one content model of type choice (parent
node of classes ItemAmount and ItemTester). The XML document depicted in
Figure 2(b) illustrates how PSM schema models XML documents. Briefly, named
associations model element-subelement nesting, unnamed association inline the
content to the element above (see association Item-Product), associations
starting at the schema class model allowed root elements. Attributes model XML
attributes or elements with simple content (depending on the value of xform’ for
the attribute, value a is depicted by @ before the name of the attribute).
Structural representatives are used for content reuse (see ShipAddr and BillAddr
reusing content of Address). The in-depth description of the relation of PSM
schemas and modeled documents can be found in [
For the goal of determining whether XML documents were invalidated due to schema evolution, the system must recognize and analyze the differences between the old (S0) and new (Se0) version of the schema. There are two possible approaches: 1) recording the changes as they are conducted during the design process or 2) comparing the two versions of the diagram. Table 1 compares both approaches, for the stated reasons we chose the second approach for our work.
As a motivation for our further progress, take a look at Figure 3. It contains two versions of a fragment of a PSM schema. In the old version, class Item has an attribute price, in the new version, class Purchase has an attribute price. recording changes schema comparison the recorded set should be normalized to eliminate re- No redundancies; the set of dundancies (repeated changes in the same place etc.). changes is always minimal. Once the evolution process is started, the old version Both versions and new can be can not be easily changed. edited without limitations. Possibility to interrupt the work and continue in an- The process of evolution can other session later. The sequence of recorded changes be arbitrarily stopped and rewould have to be stored and recording resumed later. sumed.
To retrieve the sequence for reverse process, the user The reverse operation can be will have to either start with the new version and record easily handled by the same the operations needed to go back to the old version algorithm, only with the two again, or the system will have to be able to create in- schemas on the input swapped. verse sequence for each sequence of operations.
For a schema from an outer source, the sequence of A schema from an outer source operation changes can not be retrieved directly; the can be imported2 and serve as user must start with the old version of the schema and an input to the change detecmanually adjust it to match the new schema. tion algorithm.
Table 1. Approaches to Evolution: Recording Changes vs. Schema Comparison Without any further information, there can be two interpretations of the change: 1) attribute price was moved from Item to Purchase or 2) the attribute was removed from Item and a new attribute was added to Purchase, coincidentally having the same name. Revalidation of the documents is even more difficult to decide. In the second case, a correct value must be assigned to the new attribute3. In the first case, the value of attribute price should be set to the sum of the values of price in all the items in the first version.
PurchaseSchema
purchase Purchase item 1..*
Item - name - price version v
PurchaseSchema
purchase Purchase - price item 1..*
Item - name
version ~v Fig. 3. Evolved PSM Schema
To achieve correct identification of “addition/removal” from “move” (as opposed to existing approaches), we need to extend the XSEM framework with a support for having multiple version in the model and possibility to link constructs in different versions.
Definition 3 (ver, version link, getInVer ). Let V be the set of versions for the model M. Function ver : M ∪ S∗0 → V returns the version a given construct belongs to. We require a natural condition of all the constructs of a PSM schema S0 to belong to the same version, i.e. (∀S0 ∈ S∗0)(x ∈ Sa0ll ↔ ver(x) = ver(S0)). An equivalence relation of version links VL ⊂ M × M 3 This is an open problem for our future work, see Section 7. change description classAdded new class was added to the schema classRemoved class was removed from the schema classRenamed existing class was renamed classMoved class is moved to the PSM tree attributeAdded/Removed/Renamed attribute was added/removed/renamed attributeTypeChanged attribute type changed attributeIndexChanged attributes were reordered in the class attributeCardinalityChanged cardinality of an attribute was changed attributeMoved attribute was moved from one class to another associationAdded/Removed/Renamed association was added/removed/renamed associationIndexChanged associations were reordered in the class associationCardinalityChanged cardinality of an attribute was changed associationMoved association is moved in the PSM tree Table 2. Changes Identified in XSEM-Evo between two Versions of the same Schema contains pairs of constructs that are different versions of the same construct. Partial function getInVer : (M × V) → M , getInVer(e, v) = e˜ ↔ ∃ e˜ ∈ M : (e, e˜) ∈ VL ∧ ver(e˜) = v returns a construct in a desired version (if e does not exist in version v, getInVer(e, v) is undefined). If (x, x˜) ∈ VL, x and x˜ must both be constructs of the same kind (e.g. both classes, attributes, PSM associations...).
In the following text, we will assume |V| = 2, unless explicitly stated otherwise (i.e. we expect that there are two versions in the system - an old version (v ∈ V) and a new version (v˜ ∈ V)). Values of ver function form the input of the change detection algorithm (and so does the relation VL). In XCase, values of ver are assigned automatically by the system during and maintained As the user edits the schema (either the old or the new version). 5
Based on Definitions 1 and 2, we can identify all possible changes that can occur between two versions. Each change is formally defined as a predicate with certain amount of parameters characterizing the change. Detecting changes means finding the constructs that match each respective predicate. Table 2 lists all recognized changes.
Describing each change and it’s revalidation is beyond the scope of this paper. Therefore we will describe only attributeMoved change in detail (an example of this change is depictend in Figure 3), other changes are treated in a similar manner. Change attributeMoved means that the value of class’(A0) is changed i.e. an attribute is moved from class Co0 to another PSM class Cfn0 (and the new index of A˜0 is i˜0). Formally attributeMoved is defined as a ternary predicate: attributeMoved(A˜0, Cfn0, i˜0) ↔ A˜0 ∈ Sfa0 ∧ Cfn0 ∈ Sfc0 ∧ i˜0 ∈ N0 ∧ getInVer(A˜0, v) 6= null∧ class’(A˜0) = Cfn0 ∧ (∃Co0 ∈ Sc0 )(class’(getInVer(A˜0, v)) = Co0 ∧ getInVer(Cfn0, v) 6= Co0)
Moving an attribute is an evolution operation that requires more in-depth
enquiry. The aim of our approach is to keep the semantics of the revalidated
document and not to lose the existing data during revalidation. The trivial solution
– deleting the attribute from its former location in the document and creating
a new attribute in the new location (as used in [
e b h a c f i
The figure on the left shows an example of tree function, d the result of tree(f, g, i) is the set {a, b, d, f, g, i, a−b, b− g f, f −i, a−d, d−g}, a is the root of the common subtree and a − b the edge from a to b.
In the following text we expect that the attribute was moved between classes Co0 and Cfn0, A0 ∈ attributes’(Co0), A˜0 ∈ attributes’(Cfn0). Let Cfo0 = getInVer(Co0, v˜) and Cn0 = getInVer(Cfn0, v), be the new version of class Co0 and the old version of class Cfn0 respectively, both can be null. In the situation depicted in Figure 3 A0 = price1, A˜0 = price2, Co0 = Item1, Cn0 = Purchase1, Cfo0 = Item2, Cfn0 = Purchase2 (we use subscripts to distinguish constructs in version v and v˜).
Let tree(X 0) return the subgraph of the smallest common subtree for a set X 0 ⊆ N 0 containing the root B0 of the common subtree, members of X 0 and for each X0 ∈ X 0 path between X0 and the root B0 (see Figure 4 for an example). We define predicate stable(X 0) ↔ X 0 ⊆ {Sa0ll \ Sa0} ∧ {∀X0 ∈ X 0 : X0 is present in the new version, it was not moved, added or deleted and cardinality was not changed (if X0 is an association)}. The intuitive meaning of predicate stable(X 0) is that there were no radical changes in the structure for the members of X 0. If Cn0 6= null, T 0 = tree({Co0, Cn0}) and stable(T 0) holds, than if: 4 The formal definition of XSEMPath expressions is beyond the scope of this paper.
Intuitively, the notation and usage is similar to XPath [
In the first step, the revalidation algorithm detects all changes between two versions of the model. If changes that require revalidation occur, a revalidation script is generated. Applying the script on a document valid against the old version produces a document valid against the new version. Since changes are defined as changes in the XSEM model, similarly as XSEM model can be translated to an XML schema in any XML schema language, the set of changes can be used to generate a revalidation script in any kind of implementation language. Example 3. The in-depth description of the process of generating the revalidation script is beyond the scope of this paper. As an example, we will show the revalidation script in XSL for the schema depicted in Figure 3, concretely if the first interpretation from Example 4. In that case, we have to revalidate the attributeMoved change. In this example, we will use the subscript 1 for constructs from the old version and 2 for constructs from the new version. We are revalidating attributeMoved(price2, Purchase2, 0). Since there are no other changes, stable({Purchase1, Item1}) also holds and since the association Purchase-Item has cardinality 1..∗ and Purchase is a parent of Item, this case belongs to the second group mentioned on page 9 during the description of the revalidation of attributeMoved change (aggregation upwards). Before generating the script, The XSL revalidation script consists of four templates. The first template processes purchase element – it creates the wrapping tag and calls a template for the moved PSM attribute pur-price and for item elements.
The second template processes item elements (the template is necessary, because we need to remove the price subelement from item elements).
The fourth template copies the content of each name element to the output.
The third, named, template purprice calls the attMoveprice1 function (the XSEMPath expressions are converted to regular XPath expressions – oldLocations to ‘item/price’ and newLocation to ‘price’). The user selected the function sum as attMoveprice1 , a generic function built in the system. If none of the built-in function is suitable for the situation, the user can extend the system with a custom set of functions (having the same header as sum). <xsl : stylesheet> <xsl : template match=‘/ purchase ’> <purchase> <xsl : call −template
name=”pur−p r i c e ’ /> <xsl : apply−templates
s e l e c t =‘item ’ /> </purchase> </xsl : template> <xsl : template match=‘/ purchase / item ’> <item>
<xsl : copy−of s e l e c t =‘name’ /> </item> </xsl : template> <xsl : template name=‘pur−p r i c e ’> <p r i c e > <xsl : value−of s e l e c t= ‘ xc : sum( item / p r i c e ,
p r i c e ) ’/ > </p r i c e > </xsl : template> <xsl : template match=‘/ purchase / item /name’> <xsl : copy−of s e l e c t = ‘. ’ /> </xsl : template> <xsl : function name=‘xc : sum ’ > <xsl : param
name=‘ ol d Lo c at i o ns ’ /> <xsl : param
name=‘ newLocation ’ /> <xsl : value−of s e l e c t=
‘sum($ o l d L o c a t i o n s ) ’ /> </xsl : function> </xsl : stylesheet> the user selects the function sum to be used as attMoveprice1 . The resulting revalidation script in XSL is depicted and explained in Figure 5. 7
In this paper we proposed a formal model for schema evolution. We formally defined changes that can be detected between two versions of a schema. We sketched an implementation of an algorithm that produces revalidation script on the basis of the detected set of changes.
The set of the detected changes is useful not only for the revalidation algorithm, but it is also possible to immediately decide, whether revalidation is needed or not and help the user to locate the changes in the schema.
The revalidation script can deal with structural modifications and with a significant part of the content modifications automatically, user input is required only where necessary (e.g. when a new content must be added during revalidation). We plan to extend its capabilities in adding content in our future work.
The algorithm in its current version deals mainly with revalidation of 1)
structure and 2) data already present in the document. Because new data are
often required for new versions, we will focus our future work on obtaining this
data for the revalidated documents. For this purpose, we will utilize the existing
connection between PIM and PSM and and a new similar connection between
PIM and the model of a data storage (e.g. an ER schema [
The change detection algorithm requires semantic links between the two compared versions of the schema, which are not available for schemas were imported and not created with an XSEM-enabled tool. Existing approaches to schema comparison and matching can be utilized as heuristics for creating these links.
Type inheritance is a fundamental part of large specifications, but support for inheritance is limited in the current version of XSEM. We intend to extend both PIM and PSM levels with inheritance support.