XML Document Versioning and Revalidation?? XML Document Versioning and Revalidation Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský Jakub Malý, Jakub Klı́mek, Irena Mlýnková, and Martin Nečaský XML Research Group, Department of Software Engineering Faculty XMLofResearch Mathematics and Group, Physics, Charles Department University of Software in Prague Engineering Malostranské Faculty of Mathematics andnáměstı́ Physics,25,Charles 118 00 Praha 1 in Prague University Thenáměstı́ Malostranské Czech Republic 25, 118 00 Praha 1 {klimek,maly,mlynkova,necasky}@ksi.mff.cuni.cz The Czech Republic {klimek,maly,mlynkova,necasky}@ksi.mff.cuni.cz Abstract. One of the prominent characteristics of XML applications is their dynamic nature. When a system grows and evolves, old user require- ments 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 ex- tension, 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. Keywords: XML, schema, schema evolution 1 Introduction Recently, XML [12] has become a corner stone of many information systems. It is a de facto standard for data exchange (i.e. Web services [4]) and it is also a popular data model in databases [3]. XML schemas are utilized in two scenarios: 1) to describe structure and check validity of internal documents, and 2) to define the interface of a component of the system for other components or of the system to the outer world. 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 up- dated. 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ČR), grant number P202/10/0573, and by the grant SVV-2011-263312. V. Snášel, J. Pokorný, K. Richta (Eds.): Dateso 2011, pp. 49–60, ISBN 978-80-248-2391-1. 50 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský 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 evolu- tion and make the transition to the new version semi-automatic using our con- ceptual 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 nec- essary and if it is the case, we generate a script that revalidates existing XML documents against the new version. 1.1 Outline 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 Related Work 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 [10]: – in XML schemas (in one of the XML schema languages), so-called logical level. At the logical level, changes are detected directly in the evolved schema. – in diagrams visualizing the XML schema (diagrams directly visualizing con- structs of a specific XML schema language). – in a UML diagram used to model an XML format (usually annotated using comments or stereotypes to specify the translation to an XML schema). X-Evolution, proposed in [5], is an example of a system built upon a graphical editor for creating schemas in the XML Schema language [14]. At first, the authors defined a set of evolution primitives, i.e. basic operations that modify the evolved schema (e.g. insert local element, remove type). Impact of each primitive on the validity of the existing XML documents is examined. The presented Adapt algorithm takes as an input an evolution primitive, an XML schema and an XML document valid against the schema and returns an evolved document valid against the schema on which the evolution primitive is applied. X-Evolution system provides the user with a narrow set of evolution prim- itives 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 XML Document Versioning and Revalidation 51 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 evolu- tion 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 [6] is an approach to manage schema evolution where DTD is used as a schema language. It deals both with changes in DTD and XML documents (instance documents). 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 [7], allows the user to perform a sequence of evolution operation before the documents are revalidated. Each user’s single action is recorded by the logging component. When the user is satisfied with the new version of the model, the recorded design steps are minimized and normalized. The proposed conceptual model is closer to a visualization of the XML Schema language than to a platform-independent model and the lack of a conceptual model is directly responsible for problems declared as in-built (e.g. the algorithm can not detect such a change where the same structural element acquires different semantics). 3 XSEM Conceptual Model 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 Architec- ture (MDA) [8]. A prototype implementation of XSEM in a CASE1 tool called XCase [1] is available. The model has two interconnected layers – platform- independent model (PIM) which utilizes UML [11] class diagrams and platform- specific model (PSM) which again utilizes UML class diagrams but extended with so-called XSEM profile. In the rest of this paper, we will use the formal definitions of PIM (Definition 1) and PSM (Definition 2) levels. 1 Computer-aided software engineering 52 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský 3.1 PIM Level 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 [2] standard for exchanging diagrams between them. Therefore, it is natural to use UML in our approach as well. We introduce PIM schemas formally in Definition 1. Definition 1. A platform-independent schema (PIM schema) is a triple S = (Sc , Sa , Sr ) of disjoint sets of classes, attributes, and associations, respectively. In addition, PIM schema defines functions name, card, type, class and partici- pant: – Class C ∈ Sc has a name name(C). – Attribute A ∈ Sa has a name, data type and cardinality name(A), type(A) and card(A), respectively. A is associated with a class from Sc class(A). – Association R ∈ Sr is a set R = {E1 , E2 } where E1 and E2 are called asso- ciation ends of R. R has a name name(R). E ∈ R has a cardinality card(E) and is associated with a class from Sc participant(E). For R, participant(E1 ) and participant(E2 ) are called participants of R. 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 ac- cepting 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 PSM Level 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 rep- resentation 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. XML Document Versioning and Revalidation 53 1..* Address bill-to Purchase ordered Customer Supplier - street - code - login - name - city - date - name - phone ship-to - country 0..1 - status - phone - email - gps [0,1] - email [1,*] contains provides 1..* 1..* 1..* 0..* Item Product delivers Supply 0..* - amount - code - date - price - price - price - tester - color - amount Fig. 1. Sample PIM schema Definition 2. A platform-specific schema (PSM schema) is a 5-tuple S 0 = (Sc0 , Sa0 , Sr0 , Sm 0 , CS0 0 ) of disjoint sets of classes, attributes, associations, and con- tent models, respectively, and one specific class CS0 0 ∈ Sc0 called schema class. S 0 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 C 0 ∈ Sc0 has a name denoted name0 (C 0 ). – 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. More- over, it is associated with a class from Sc0 denoted class0 (A0 ) and has a posi- tion 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 . E 0 ∈ R0 has a cardinality denoted card0 (E 0 ) and is associated with a class from Sc0 denoted participant0 (E 0 ). 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 ∈ Sm 0 has a content model type cmtype’0 (M 0 ) ∈ {sequence, choice, set}. For simplicity, we will also use the notation attributes (C 0 ) to denote the se- quence (A0i ∈ Sa0 : class(A0 ) = C 0 ∧ i = indexOf(A0 )) for each class C ∈ Sc . Let us denote N 0 = Sc0 ∪ Sm 0 . 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 CS0 0 . Members of Sc0 , Sa0 , Sr0 , and Sm 0 are called components of S 0 . The set of all PSM schemas will be denoted S . Finally ∗0 S we define the set of all constructs (PIM and PSM): M = Sc ∪ Sr ∪ Sa ∪ ( S 0 ∈S ∗0 (Sc0 ∪ Sr0 ∪ Sa0 )). 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 docu- ment with a purchase. Again, classes, associations and attributes are depicted 54 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský purchaseRQ - street # Purchase - city # - country @ code # @ date @ version shipto # 0..1 items # Address # ShipAddr billto Items - gps cdetail item 1..* # Address Item BillAddr | Customer # @ login # - name Product ItemAmount ItemTester - email[0..1] @ code - amount @ tester - price (a) PSM schema (b) XML document Fig. 2. Sample PSM schema of a purchase order request with a sample 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 start- ing 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). Struc- tural 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 [9]. 4 Evolution For the goal of determining whether XML documents were invalidated due to schema evolution, the system must recognize and analyze the differences be- tween the old (S 0 ) 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. XML Document Versioning and Revalidation 55 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 re- would 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 detec- manually 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 PurchaseSchema PurchaseSchema price was moved from Item to Purchase or 2) purchase purchase the attribute was removed from Item and a new Purchase Purchase attribute was added to Purchase, coincidentally item - price having the same name. Revalidation of the doc- 1..* item Item 1..* uments is even more difficult to decide. In the Item - name second case, a correct value must be assigned to - price - name the new attribute3 . In the first case, the value version v version ~ v of attribute price should be set to the sum of the values of price in all the items in the first version. Fig. 3. Evolved PSM Schema To achieve correct identification of “addition/removal” from “move” (as op- posed to existing approaches), we need to extend the XSEM framework with a support for having multiple version in the model and possibility to link con- structs 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 S 0 to belong to the same version, i.e. (∀S 0 ∈ S ∗0 )(x ∈ Sall 0 ↔ ver(x) = ver(S )). An equivalence relation of version links VL ⊂ M × M 0 3 This is an open problem for our future work, see Section 7. 56 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský 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) = ẽ ↔ ∃ ẽ ∈ M : (e, ẽ) ∈ VL ∧ ver(ẽ) = 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 other- wise (i.e. we expect that there are two versions in the system - an old version (v ∈ V) and a new version (ṽ ∈ 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 Changes 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 cer- tain 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 C fn0 (and the new index of Ã0 is i˜0 ). Formally attributeMoved is defined as a ternary predicate: fn0 , i˜0 ) ↔ Ã0 ∈ S attributeMoved(Ã0 , C fa0 ∧ C fc0 ∧ i˜0 ∈ N0 ∧ getInVer(Ã0 , v) 6= null∧ fn0 ∈ S fn0 ∧ (∃Co0 ∈ Sc0 )(class’(getInVer(Ã0 , v)) = Co0 ∧ getInVer(C class’(Ã0 ) = C fn0 , v) 6= Co0 ) XML Document Versioning and Revalidation 57 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 doc- ument 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 [6] and [5]) – is not suitable, be- cause the value of the attribute is lost. The most general approach is to couple fn0 , i˜0 ) of attributeMoved change with a revalidation function each instance (Ã0 , C attMoveÃ0 (oldLocations, newLocation): XSEMPath × XSEMPath → type’(Ã0 )4 where oldLocations is an expression returning all existing instances of A0 and newLocation is an expression containing the path to one instance in the new document. The result of the function is the new value for the instance of Ã0 in the new document. In the general case the function attMoveÃ0 is defined by the user, but the system can give the user a suggestion in certain cases – several types of the most common scenarios can be distinguished. a The figure on the left shows an example of tree function, b c d the result of tree(f, g, i) is the set {a, b, d, f, g, i, a−b, b− e f g f, f −i, a−d, d−g}, a is the root of the common subtree h i and a − b the edge from a to b. Fig. 4. Example for tree function In the following text we expect that the attribute was moved between classes Co0 and C fn0 , A0 ∈ attributes’(Co0 ), Ã0 ∈ attributes’(C fn0 ). Let Cfo0 = getInVer(Co0 , ṽ) and Cn = getInVer(C 0 fn0 , v), be the new version of class Co and the old version 0 f of class Cn respectively, both can be null. In the situation depicted in Figure 0 3 A0 = price1 , Ã0 = price2 , Co0 = Item1 , Cn0 = Purchase1 , C fo0 = Item2 , C fn0 = Purchase2 (we use subscripts to distinguish constructs in version v and ṽ). Let tree(X 0 ) return the subgraph of the smallest common subtree for a set X ⊆ N 0 containing the root B 0 of the common subtree, members of X 0 and for 0 each X 0 ∈ X 0 path between X 0 and the root B 0 (see Figure 4 for an example). We define predicate stable(X 0 ) ↔ X 0 ⊆ {Sall 0 \ Sa0 } ∧ {∀X 0 ∈ X 0 : X 0 is present in the new version, it was not moved, added or deleted and cardinality was not changed (if X 0 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 [15], only the XSEMPath expressions refer to the constructs from a PSM schema instead of the names of XML elements and attributes in the document. When executed upon a document T ∈ T (S 0 ), XSEMPath query is translated to XPath query and the result of this query upon T is returned. 58 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský 1. ∀ association R0 ∈ T 0 : card’(R0 ) = mR0 ..1 (only cardinalities 0..1 and 1..1 are allowed in the affected part of the schema). In this simplest case the at- tribute Ã0 will have 0 or 1 instance in the old schema. Then this instance can be copied to the only one new location (attMoveÃ0 will be identity function). 2. Co0 is a descendant of Cn0 in the PSM tree (the attribute is moved upwards, but the associations between Co0 and Cn0 can have arbitrary cardinalities). Then all instances of A0 under each instance of Cn0 should be “aggregated” to one instance of Ã0 (this is the case depicted in Figure 3). Several aggre- gation functions can be offered (e.g. sum, count, avg, max, min known from relational databases or concat inlining the respective values). 3. Co0 is a descendant of Cn0 in the PSM tree, card’(A0 ) = m0 ..1 and card’(Ã0 ) = f0 ..∗. Then this case is similar as the case above, but the cardinality of m attribute Ã0 is adjusted, so all the values from existing instances can be used as values of Ã0 , no aggregation is needed (attMoveÃ0 can be called toList). 4. Co0 is an ancestor of Cn0 in the PSM tree, card’(A0 ) = m0 ..∗ and card’(Ã0 ) = f0 ..1. Then this is an inverse case to the one above. The respective values m of A0 can be distributed to the new locations. Nonetheless, a user may have to specify the distribution precisely (attMoveÃ0 can be called distribute). When none of the conditions above is satisfied, a possible general approach is to use the function attMoveÃ0 = identityN which returns the value of the n-th instance of A0 when required on the n-th location in the revalidated document. Other attMoveÃ0 functions must be entered by the user. 6 Revalidation 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 trans- lated 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 revalida- tion 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 revali- dating 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, XML Document Versioning and Revalidation 59 The XSL revalidation script consists of four templates. The first template processes purchase element – it cre-

ates the wrapping tag and calls a tem- plate for the moved PSM attribute

The second template processes item el- ements (the template is necessary, be- cause 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 pur- tion (the XSEMPath expressions are converted to regular XPath expres- 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 a custom set of functions (having the same header as sum). Fig. 5. Example of a Revalidation Script in XSL 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 Conclusion and Future Work 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 al- gorithm, 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 sig- nificant part of the content modifications automatically, user input is required 60 Jakub Malý, Jakub Klı́mek, Irena Mlýnková, Martin Nečaský only where necessary (e.g. when a new content must be added during revalida- tion). 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 [13]). The change detection algorithm requires semantic links between the two com- pared 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. References 1. XCase – tool for XML data modeling. http://xcase.codeplex.com/. 2. MOF 2.0 / XMI Mapping Specification, v2.1.1. OMG, 2009. 3. R. Bourret. XML and Databases. September 2005. http://www.rpbourret.com/ xml/XMLAndDatabases.htm. 4. D. Booth, C. K. Liu. Web Services Description Language (WSDL) Version 2.0 Part 0: Primer. W3C, June 2007. http://www.w3.org/TR/wsdl20-primer/. 5. G. Guerrini, M. Mesiti, and M. A. Sorrenti. Xml schema evolution: Incremental validation and efficient document adaptation. In XSym, volume 4704 of Lecture Notes in Computer Science, pages 92–106. Springer, 2007. 6. Hong Su, D. K. Kramer, E. A. Rundensteiner. XEM: XML Evolution Management, Technical Report WPI-CS-TR-02-09. 2002. 7. M. Klettke. Conceptual xml schema evolution — the codex approach for design and redesign. In Workshop Proceedings Datenbanksysteme in Business, Technologie und Web (BTW 2007), pages 53–63, Aachen, Germany, March 2007. 8. J. Miller and J. Mukerji. MDA Guide Version 1.0.1. Object Management Group, 2003. http://www.omg.org/docs/omg/03-06-01.pdf. 9. M. Necasky. Conceptual Modeling for XML, volume 99 of Dissertations in Database and Information Systems Series. IOS Press/AKA Verlag, January 2009. 10. M. Necaský and I. Mlýnková. Five-level multi-application schema evolution. In DATESO, pages 90–104, 2009. 11. Object Management Group. UML 2.1.2 Specification, nov 2007. http://www.omg. org/spec/UML/2.1.2/. 12. T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, F. Yergeau. Extensible Markup Language (XML) 1.0 (Fifth Edition). W3C, November 2008. http:// www.w3.org/TR/2008/REC-xml-20081126/. 13. B. Thalheim. Entity-Relationship Modeling: Foundations of Database Technology. Springer Verlag, Berlin, Germany, 2000. 14. H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1: Structures (Second Edition). W3C, October 2004. http://www.w3.org/TR/ xmlschema-1/. 15. W3C. XML Path Language (XPath) 2.0. http://www.w3.org/TR/xpath20/.