Recently XML has achieved the leading role among languages for data representation and, thus, the amount of related technologies and applications exploiting them grows fast. However, only a small percentage of applications is static and remains unchanged since its first deployment. Most of the applications change with newly coming user requirements and changing environment. In this paper we describe a tool for evolution and change propagation of XML applications called eXolutio, which has been developed and improved in our research group during last few years. The text should help the reader to get acquainted with the tool and its theoretical background.
other. Such evolution brings a challenge for research, so that the user interaction and, hence, the expensive and error-prone work can be minimized. We cannot leave the user out completely, there still remain cases when user decision is unavoidable; however, automatic management of evolution enables to identify all the affected parts of the application and perform the user-selected changes correctly and efficiently and, possibly, exploit them in further automatic processing.
In our research group we have focused on the area of efficient and correct
management of a family of XML formats for several recent years. Starting with a simple idea
of propagation of changes among related XML formats, we have gradually extended
our effort towards a robust framework and its implementation in a tool called eXolutio.
It currently supports the original idea of designing XML formats using the principles of
Model Driven Architecture (MDA) [
Contributions The aim of this paper is to provide a covering overview of our research in the area of XML evolution, to describe architecture and implementation of the eXolutio tool, to present results of our experiments with the tool proving the concept and efficiency and a comparison of the tool with similar tools.
Outline The rest of the paper is structured as follows: In Section 2 we focus on the background theoretical aspects – our conceptual model for XML. In Section 3 we introduce eXolutio, our tool in which we implement our research results. In Section 4 we provide the proof of the concept using a set of experiments. In Section 5 we discuss the related work. Finally, in Section 6 we conclude. 2
In this section, we introduce our conceptual model for XML and its inheritance extension. It has two levels, PIM and PSM, which is inspired by MDA.
A PIM schema is based on UML class diagrams and models real-world concepts and relationships among them. It contains three types of components: classes, attributes and associations. A sample PIM schema is depicted in Figure 1. Where association cardinality is not explicitly stated, default cardinality 1..1 applies. A part of the PIM are also integrity constraints which we are currently working on, but which are not in the scope of this paper.
Definition 1. A platform-independent (PIM) schema is a triple S = (Sc, Sa, Sr) of disjoint sets of classes, attributes, and associations, respectively.
– Class C ∈ Sc has a name assigned by function name. For inheritance purposes, function isa assigns a parent class to a child class (UML generalization) and must not form a cycle. Furthermore, functions abstract and final determine whether the class can have instances in data and whether this class can be inherited from, respectively. – Attribute A ∈ Sa has a name, data type and cardinality assigned by functions name, type, and card, respectively. Moreover, A is associated with a class from Sc by function class.
Supply amount supply-price date
0..*
Association R ∈ Sr is a set R = {E1, E2}, where E1 and E2 are called association ends of R. R has a name assigned by function name. Both E1 and E2 have a cardinality assigned by function card and are associated with a class from Sc by function participant. We will call participant(E1) and participant(E2) participants of R. name(R) may be undefined, denoted by name(R) = λ.
For a class C ∈ Sc, we will use attributes (C ) to denote the set of all attributes of C, i.e. attributes (C ) = {A ∈ Sa : class(A) = C}. Similarly, associations (C ) will denote the set of all associations with C as a participant, i.e. associations (C ) = {R ∈ Sr : (∃E ∈ R)(participant(E) = C)}. For a given association R = (E1, E2), we will use notation (C1, C2) as an equivalent of (participant(E1), participant(E2)) if there are no more associations connecting C1 and C2.
The platform-specific model (PSM) specifies how a part of the reality is represented in a particular XML schema in a UML-style way. We introduce it formally in Definition 2. 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 that the designer works in a UMLstyle way which is more comfortable then editing the XML schema. Formally, there is a mapping from each PSM schema to the PIM schema.
Definition 2. A platform-specific (PSM) schemais a tuple S 0 = (Sc0 , S a0, Sr0 , S m0, CS00 ) of disjoint sets of classes, attributes, associations, and content models, respectively, and one specific class CS00 ∈ Sc0 called schema class.
Class C0 ∈ Sc0 has a name assigned by function name. For inheritance purposes, function isa assigns a parent class to a child class and the relation must not form a cycle. Furthermore, functions abstract and finaldetermine whether the class can have instances in data and whether this class can be inherited from, respectively. Attribute A0 ∈ S a0 has a name, data type, cardinality and XML form (whether it models an XML attribute or an XML element) assigned by functions name, type, card and xform, respectively. xform(A0) ∈ {e, a}. Moreover, it is associated with a class from Sc0 by function class and has a position assigned by function position within the all attributes associated with class(A0). cust
items |
ItemPricing price amount
PurRSSchema purchaseRS Purchase @code create-date @version status cust Customer name
addr GlobalAddress street city country (b) items
Items 1..* item
Item ProductBase Product
CommonSchema
ProductBase code title (c) – Association R0 ∈ Sr0 is a pair R0 = (E10, E20), where E10 and E20 are called association ends of R0. Both E10 and E20 have a cardinality assigned by function card and each is associated with a class from Sc0 or content model from Sm0 assigned by function participant, respectively. We will call participant(E10) and participant(E20) parent and child and will denote them by parent(R0) and child(R0), respectively. Moreover, R0 has a name assigned by function name and has a position assigned by function position within the all associations with the same parent(R0). name(R0) may be undefined, denoted by name(R0) = λ. – Content model M 0 ∈ Sm0 has a content model type assigned by function cmtype. cmtype(M 0) ∈ {sequence, choice, set}.
0 , Sr0 ) must be a forest1 of rooted trees with one of its trees rooted in The graph (Sc0 ∪ Sm CS00 . For C0 ∈ Sc0 , attributes (C0 ) will denote the sequence of all attributes of C0 ordered by position, i.e. attributes (C0 ) = (A0i ∈ Sa0 : class(A0i) = C0 ∧ i = position(A0i)). Similarly, content (C0 ) will denote the sequence of all associations with C0 as a parent ordered by position, i.e. content (C0 ) = (Ri0 ∈ Sr0 : parent(Ri0) = C0 ∧ i = position(Ri0)). We will call content (C0 ) content of C0.
A sample PSM schema is depicted in Figure 2. PSM uses similar constructs to PIM: classes, attributes and associations. The PSM-specific constructs have precisely defined semantics. 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 attributes and content). An attribute models an XML element declaration with a simple content or XML attribute declaration depending on its XML form (function xform). 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. Type of the modeled content (set, 1 Note that since S0 is a forest, we could model R0 directly as a pair of connected components.
However, we use association ends to unify the formalism of PSM with the formalism of PIM.
choice, sequence) can be specified by a special construct that can be, for example, seen
in Figure 2(a) under the Item class.
2.1 Interpretation of PSM schema against PIM schema
A 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. The interpretation of a PSM schema against a PIM
schema is what we call the mapping. It is the core feature of our conceptual model.
It interconnects constructs on the platform-specific level with those on the
platformindependent level and allows for interesting use cases for the conceptual model like
XML schema evolution and integration [
eXolutio architecture
The implementation of our research results is a tool called eXolutio [
View
Updates user
Input
Controller
Model Operations
CommandBase * +CommandOperation() +UndoOperation() +PrePropagation() +PostPropagation() ComposedCommand SubCommands AtomicCommand +CommandOperation() 1 * foreach c in SubCommands c.PrePropagation() c.CommandOperation() c.PostPropagation() 1 CommandStack +Push(in c : CommandBase) +Pop() : CommandBase
UndoStack RedoStack
1 1 Control er +Undo() +Redo() c = UndoStack.Pop() c.UndoOperation() RedoStack.Push(c) (a) Overall architecture (b) Controller
The architecture of eXolutio is based on the Model–View–Controller (MVC) design
pattern (Figure 4(a)). This means that we hold all the project data in the model part,
neither mixing it with operations, nor visualization. Whenever a user issues a command,
it is handled by the controller part. The controller makes all the necessary changes in the
model. The view part observes that the model has changed and updates the visualization.
The connections between individual parts are loose enough so it is possible to, e.g., use
multiple visualizations. In particular, we have a Windows Presentation Foundation [
Model The model part of the tool based on our conceptual model [
Controller The controller is the core of the tool. It contains all the operations and
algorithms that make the tool unique. Also, it contains the usual command and undo/redo
management. Whenever a user issues a command from view, it is handled by the
controller. The controller (depicted in Figure 4(b)) gets all the necessary parameters from
view such as what command is requested, the currently selected components, the new
name for a component, etc. The controller creates the appropriate command, which in
most cases will be one of our composite operations (described later in this section) and
passes all the required parameters. The operation executes and updates the model
accordingly. Then it places the command on the undo stack. The command itself contains
all the information it needs to change the model back to the state it was in before the
command was executed. In other words, we can simply call undo and the command
knows what it needs to do and whether it is possible. This way, we can stack the
executed commands and perform undo and redo operations as needed and as usual. In [
So far we have described how to compose atomic and composite operations. However, these worked on their respective levels of abstraction. Now we have to make sure that when there is an interpretation of a PSM schema against a PIM schema, we keep the model in a consistent state and save the user’s time by propagating the changes between the levels. This is achieved by the propagation. Before each atomic operation is executed, a method implementing its propagation to the other level is called. It determines whether there is an interpretation and therefore the need to propagate. If so, it creates a (possibly) composite operation on the other level of abstraction and integrates it to the currently running operation. Only when the propagation succeeds, the original atomic operation that caused it is executed. This way, the propagation actually becomes a part of the currently running operation. This is convenient because when it finishes, it can be undone and redone like any other operation. 4
To provide the proof of the whole concept and show the advantages of our tool, we evaluate our approaches using experiments based on a real-world family of XML schemas. We experiment with the National Register for Public Procurement System (NRPP)2. It is a governmental information system where public authorities in the Czech Republic publish data about their public contracts. Authorities send contract information to the information system formatted in one of the 17 XML formats accepted by the NRPP. This includes, e.g. XML format for contract notifications, supplier selection notifications, etc. The information is then published by the system in the form of HTML pages. The goal of the experiment is to show how our approach would save time if the authors of the NRPP XML formats used eXolutio to design the XML formats and evolve them according to changing legislation instead of their manual editing and adaptation.
Currently, the NRPP only provides a textual documentation for the XML formats and a set of sample XML documents. Therefore, our first goal is to design a conceptual schema in a form of a PIM schema which models the domain of public contracts and design PSM schemas of the XML formats mapped to the PIM schema.
The PIM schema contains classes which model public contracts and their procurers and suppliers. There are also some additional concepts modeled – i.e. prices and contact information. A supplier is associated with a contract, a procurer is associated with a contract by a path of associations has contact and main. Each contract has additional contact information – where documentation for the contract is provided and where bids to the contract are collected. Finally, there are four different prices – expected price, the best offered price, price agreed by a selected supplier and procurer, and a final real price known after finishing the contract. The PSM schema depicted in Figure 5 (a) models an XML format which a public authority uses to send a notification about a new public contract to NRPP. The PSM schema depicted in Figure 5 (b) models an XML format for notifications about the supplier selected for the contract. 2 http://www.isvz.cz (in Czech only)
We can measure the amount of manual work required to design the PIM and PSM schemas in terms of numbers of executed atomic operations. The numbers of atomic operations executed to create the PIM and PSM schemas are depicted in Figure 6 (a). It shows that only creation and update operations were used. Here, manual creation of the schemas is necessary so there is no direct advantage in comparison to writing the XML schemas of the XML formats directly. However, eXolutio saves time because for each performed atomic operation it checks whether it does not break the consistency between the XML formats. When the designer codes the XML schemas of the XML formats directly no such control is performed automatically and (s)he must do it manually in each step during coding.
Having the PIM schema and a set of PSM schemas of the XML formats used by NRPP we set ourselves three goals. The first goal is to show how eXolutio facilitates creating new XML formats on the basis of an existing PIM schema. A PSM schema of a new XML format for public procurer details is depicted in Figure 5 (c). The numbers of the atomic operations executed at this step are depicted in Figure 6 (b). Again, only the creation and update operations were performed. Even though the designer needs to design the PSM schemas for the new XML formats manually, the experiment shows that our approach saves him/her a great deal of work and prevents him/her from making unnecessary errors. This is because our technique enables us to create the PSM schemas on the basis of the PIM schema (which is faster than creating PSM schemas separately) and ensures that the designer creates the PSM schemas coherently with the PIM schema (as it preserves the consistency of the interpretation).
The second goal is to improve the quality of the NRPP XML formats, which is low. The designers of the XML formats did not follow basic XML design principles (e.g. exploiting the hierarchical nature of XML). For example, contact information is modeled by XML elements with names prefixed with cont , docs , etc. It would have been better to remove the prefixes and enclose the semantically related XML elements into separate XML elements (e.g. enclose contact XML elements to XML element contact structured to main, doc, etc. or enclose all information related to the supplier into XML element supplier). We have made these adaptations in the present XML formats. The numbers of the executed atomic operations are depicted in Figure 6 (c). In this step, synchronization and removal operations were also used, because some of the old parts of the PSM schemas were replaced by new ones. Again, the experiment demonstrated that our approach saves a lot of work as it preserves the consistency of PSM schemas against the PIM schema when changes are performed.
The third goal was to show how the set of schemas can be evolved coherently. We implemented various changes which resulted from new requirements on the NRPP functionality and from new legislation. In both cases, changes to the PIM schema needed to be done.
The new legislation required to report not only the number of bids received for each contract, but also particular bids including the bidding supplier and offered price.
Finally, there was a requirement to update the XML format for contract notifications (Figure 5 (a)) so that it is possible to give notification not only on the expected months and days in which the contract should be finished, but also on the exact date. This change was correctly propagated to the PIM schema, because it is a conceptual change. From here, it was propagated to the other PSM schemas.
The numbers of the atomic operations executed during the last two steps are
depicted in Figure 6 (d). The darker part shows the numbers of manually executed
operations. The lighter part shows the numbers of operations executed automatically by
the propagation mechanism. α are additions, υ are changes, δ are deletions and σ are
synchronizations - statements that two modeled sets of attributes or associations are
semantically equivalent. The synchronizations are very useful in our change propagation
mechanism, for details refer to [
The current approaches towards evolution management can be classified according to
distinct aspects [
XML View We can divide the current approaches to XML schema evolution and change
management into several groups. Approaches in the first group consider changes at
the schema level and differ in the selected XML schema language, i.e. DTD [
In all the papers cited the authors consider only a single XML schema. In [
In this paper, we introduced eXolutio, our tool for XML schema and data management. We surveyed related work and we showed the theoretical background behind our tool and evaluated it on real-world XML schemas.