XML-relational systems with well de ned XML and relational schemas are widely used in industry. In the presence of rapidly changing requirements both schemas of such a model need continuous evolution, which can be performed by a formal framework that describes the evolution of the mutually dependent schema pairs of the system as sequences of elementary schema transformations. There are a number of common tasks, like relational schema performance tuning, XML syntax clean-up, etc that stand apart from changes of semantics of the schemas. We discuss a framework with three layers of operations: the changes in XML schema only, the semantic changes that affect both schemas, and the changes that affect relational schema only. We show how the layered framework allows to formalize and address the above mentioned tasks. We consider the formal quality of the solutions of the tasks that may be achieved inside the framework.
A practice of storing XML data in relational databases is widely employed because of the capabilities of the highly-developed RDBMS technologies. Provided that XML documents comply with a particular schema designed for the application domain, a more ef cient utilization of these technologies can be achieved. In that case a relational database can use the metadata to organize effective storage, which includes selection of appropriate relational schema. On the other hand, if a choice between possible XML document schemas exists, the schema that is best t for storing data in relational database should be chosen. Thereby these XML and relational schemas become mutually dependent.
If the product that uses the schemas exists in the environment of rapidly changing requirements, both schemas need to exhibit agile evolution in time. A major part of software products storing XML in relational databases are actually in this situation because they often need to change schemas with every new version of the product. Continuous redesign requires repetitive evolution of data access and data storage algorithms. A formal framework that presents schema changes as a sequence of elementary transformations and ensures invariance of selected properties of the schema and data complying with the schema is an alternative to ad-hoc solutions. Such a model is referred to as a schema evolution model.
Schema changes may be caused by changes in functionality of the product, by system performance requirements, compatibility issues, and other reasons. While it is preferable that performance problems are resolved on the relational schema level, functional requirements in the presence of compatibility issues are better expressed in terms of changes in XML schema only.
General XML document evolution models (for example, those found in [
We also add another task, richness: the changes available in the model should allow to transform a given XML schema complying with a given set of semantic constraints to any XML schema complying with the same constraints. This task is usually solved by general XML evolution models. Resolving it in a speci c XML-relational evolution model ensures that it is not less expressive about XML schema, than general XML evolution model.
We present an evolution model that explicitly contains the knowledge of the mutual dependency of XML and relational schemas. The outline of the model is given on Figure 2. S and S' are original and new states of intermediate layer that represents common 1 We use DTD as XML document schema description throughout the rest of the paper, though most of the reasoning applies to other schema descriptions as well part of the schemas; intermediate layer contains semantic constraints and is represented in both schemas. Elementary operations of type 2 affect the intermediate layer; operations of type 1 affect only DTD; operations of type 3 affect only relational schema. In this paper we show how the above tasks can be solved in the model by considering the sequences of operations of the 1st, 2nd and 3d types respectively. We demonstrate that operations of the 1st and 2nd types are rich enough to solve the 4th task. We also discuss the quality of the answers to these issues.
The rest of the paper is organized as follows. Section 2 gives an overview of related work. Section 3 gives a brief description of the XML-relational evolution model we employ. The subsequent sections contain operations de nitions and discuss how the operations address the listed above tasks. 2
The issue of storing XML documents in relational databases is a well explored area
of research. The main trends are structure-driven approach, for example, [
Extensive research is done recently in the eld of effective querying XML stored in
relational database. [
<lastname>Date</lastname> </name> <address>NA</address> </author> <editor name=Homet> </editor> </monograph>
Various database schema evolution models were proposed for object-oriented [
In consequent discussion we use as a sample a XML document schema taken from [
The essential part of the evolution model is the intermediate schema S. S has a xed mapping from DTD. Figure 4 shows the schema S for the sample DTD. Dashed rectangles are used to outline the factorized vertices. Filled circles mark the vertices that are NB = fbooktitleg ybooktitle yauthorID iarticle ibook
HHHjH ? icontactauthor
yid yaddress
NN = ff irstname; lastnameg ylastname imonograph
?ieditor ytitle iauthor
NM = fg 9? iname
? y rstname included into attribute sets of the factorized vertices. Factorized vertices not shown on the gure: A (NA = fauthorI Dg), U (NU = fid; addressg), T (NT = ftitleg).
First, the DTD graph is built. The DTD is simpli ed by replacing attributes with
leaf tags, inlining entities, replacing regular expressions in tag de nitions. After that the
tags become the vertices of the DTD graph. If one tag contains another an edge exists
between corresponding DTD graph vertices. Each vertex is labeled with the name of
the tag. An edge may be optionally marked by an asterisk (*). In that case it is a
staredge. Figure 4 contains a sample DTD graph. A formal de nition of the DTD graph
and the process of obtaining it from the DTD can be found in [
Figure 4 also shows a factorization of the DTD graph. Each factorized vertex, i.e., a vertex of the factorized DTD graph2 has its own start-vertex. Each vertex in a factorized vertex can be reached by a single path from its start-vertex. The path does not contain star-edges.
Some of the leaf vertices of the DTD graph are attributes of the factorized vertex, which contains them. The choice of the attributes is up to the schema designer with a condition that it does not violate the semantic invariants of the schema S (semantic constraints are explained below). Each factorized vertex can contain another auxiliary attribute. Its value denotes element types of the beginnings of the edges that start from the vertices of the given factorized vertex and end in the start-vertices of other factorized vertices. For example, book, monograph or article are the values of the auxiliary attribute for the factorized vertex U. The auxiliary attribute is needed for add/remove upper edge operation (see Xml-only operations) only and can be omitted if the operation is not used. Thereinafter we omit explicit mention of this attribute.
The factorized DTD graph maps original DTD into intermediate schema S. [
The mapping of the relational schema to S is represented by a set of views. Each view is a projection of a composition of equi-joins: Vi = Fi(X1; X2; ::; XN ), where Xi is the relation of the schema. In the naive case Vi = V i(Xi). Figure 5 represents a fragment of the script that generates a relational schema for the sample DTD in the 2 The same term is used to refer to the fragment of the original graph that includes vertices comprising the factorized vertex and edges between them CREATE TABLE U ( id INT NOT NULL, address VARCHAR(50) ); CREATE TABLE N ( id INT NOT NULL, rstname VARCHAR(50), lastname VARCHAR(50) ); CREATE TABLE T ( id INT NOT NULL, title VARCHAR(50) ); CREATE TABLE B ( id INT NOT NULL, booktitle VARCHAR(50), id U INT NOT NULL ); CREATE TABLE A ( id INT NOT NULL, authorId VARCHAR(50), id N INT NOT NULL ); CREATE TABLE M ( id INT NOT NULL, id U INT NOT NULL, id N INT NOT NULL, id T INT NOT NULL, id M INT NOT NULL); ALTER TABLE B ADD CONTRAINT fk U FOREIGN KEY ( id U ) REFERENCES U (id); ... 1. Closure: 8t 2 V 0 Pe(t); De(t) V 0 2. Rootedness: 9T 2 V 0 8t 2 V 0 T 2 P L(t) ^ Pe(T ) = ; 3. Pointedness: 9 ? V 0 8t 2 V 0 t 2 P L(?) 4. Immediate predecessors: 8t 2 V 0 P (t) = Pe(t) [ x(P L(x) \ Pe(t) \ (P L(t) DL(t)) [ x(P L(x)\Pe(t)\(P L(t)\DL(t)) fxg; Pe(t)) [ x((P L(x)
DL(t)) \ Pe(t); P L(x) \ DL(x) fxg) 5. Predecessors graph: 8t 2 V 0 P L(t) = [ x(P L(x); P (t)) [ ftg 6. Immediate descendants: 8t 2 V 0 D(t) = De(t) [ x(DL(x) \ De(t) \ (DL(t) P L(t)) [ x(DL(x)\De(t)\(DL(t)\P L(t)) fxg; De(t)) [ x((DL(x)
P L(t)) \ De(t); DL(x) \ P L(x) fxg) 7. Descendants graph: 8t 2 V 0 DL(t) = [ x(DL(x); D(t)) [ ftg 8. Interface: 8t 2 V 0 I(t) = N (t) [ H(t) 9. Nativeness: 8t 2 V 0 N (t) = Ne(t) H(t) 10. Inheritance: 8t 2 V 0 H(t) = [ x(I(x); P (t)) fxg; Pe(t)) P (x))\(P L(t)
fxg; De(t))
D(x))\(DL(t) naive case. Edges are represented by integrity constraints on the view representing the end vertex. 3.2
The semantic invariants for the evolution of S are de ned as a set of axioms similar
to the axiom sets used for the type lattices in OO databases in [
The evolution model sets are de ned as follows. The hierarchy on the factorized vertices is de ned by the sets of immediate predecessors P (t) for each vertex t. Immediate predecessors are vertices that explicitly include vertex t. Essential predecessors Pe(t) are explicitly speci ed by the schema designer sets of vertices. It is required that P (t) Pe(t). Vertex subhierarchy P L(t) is a sub-graph of a factorized DTD graph, which vertex set consists of vertices, from which t is reachable. Native attributes N (t) are a set of attributes de ned in vertex t. Inherited attributes H (t) are the union of attributes of all its predecessors. Essential attributes Ne(t) are explicitly speci ed. It is required that N (t) Ne(t). Interface I (t) is the union of its inherited and native attributes. The reverse hierarchy is de ned by the sets of immediate descendants D(t) for each vertex t. Immediate descendants are vertices that explicitly are included into vertex t. Vertex reverse subhierarchy DL(t) is a sub-graph of a factorized DTD graph, which vertex set consists of vertices reachable from t. Essential descendants De(t) are explicitly speci ed sets of vertices. It is required that D(t) De(t). 4
In the following sections the operations of the evolution model are discussed. Each operation over the schemas belongs to one of the following classes: Xml-only operations (represented by the arrow marked with 1 on Figure 2) the operations that are applied to and affect only XML schema. S-operations (represented by the arrow marked with 2 on Figure 2) the operations over the common part. Relational-only operations (represented by the arrow marked with 3 on Figure 2) the operations that are applied to and affect only relational schema. 4.1
Xml-only operations are divided into two groups: a) affecting DTD graph and b) not affecting DTD graph.
The operations of type 1a, i.e., those affecting DTD graph, are the following: move the vertex up/down; replaces a pair of elements <!ELEM EN T A(B; ::) > and <!ELEM EN T B(C; ::) > from one factorized vertex with a pair <!ELEM EN T A(B; C; ::) > and <!ELEM EN T B(::) > where B is not an attribute3, and vice versa (see Figure 7a); add/remove leaf vertex; replaces an element <!ELEM EN T A(::) > where A is not an attribute with a pair <!ELEM EN T A(B) > and <!ELEM EN T B > where new element B is not an attribute, and vice versa (see Figure 7b); 3 of a factorized vertex of the model S; the same applies to other uses of attribute in the operations de nitions gA gB
gC gA ? (*)gB (*) gC gC gB (*) gA ? gB gB gA gA ? gB (*) gC b) d)
gA gB
gA (*) g?B gC
add/remove upper edge; replaces a pair of elements <!ELEM EN T A(B; C ; ::) > and <!ELEM EN T B(C ; ::) > where C is a start vertex and both stars are optional with a pair <!ELEM EN T A(B; ::) > and <!ELEM EN T B(C ; ::) >, and vice versa (see Figure 7c)4; move edge; replaces a pair of elements <!ELEM EN T A(B; ::) > and <!ELEM EN T B(C ; ::) > where C is a start vertex and a star after C is optional with a pair <!ELEM EN T A(B; C ; ::) > and <!ELEM EN T B(::) > where B is not an attribute, and vice versa (see Figure 7d); mark/unmark edge; replaces a an element <!ELEM EN T A(C ; ::) > with an element <!ELEM EN T A(C; ::) > if exists element <!ELEM EN T B(C ; ::) > from another factorized vertex with an optional star after C, and vice versa (see Figure 7e). In this section it will be shown that it is possible to convert a given DTD that maps to a schema S into any arbitrary DTD that maps into the same schema S by applying a sequence of Xml-only operations. This would mean that the solution provided by the model is a complete solution: the model allows to obtain any XML with the given intermediate schema S, any other changes would necessarily lead to changes in relational schema5.
A fragment of the DTD graph contained in one factorized vertex is a tree, e.g. name, firstname and lastname and edges between them from the sample DTD (see 4 Note that semantics are not violated if the auxiliary attribute that was mentioned in Section 3 is present 5 Consequent changes in relational schema may compensate each other, but the model allows to obtain the same resulting schema without changing relational schema at all. + gN
- g PPPqP g ...
g + AQsQ gN A g
A UA g ... a) b)
g + AQsQ gN A g
A UA g ...
c) gN g Q A sQ A g
A UA g ...
Statement 4.1. The move vertex up/down operation allows that any given set of vertices
of a factorized vertex with a xed start-vertex can be organized into any tree.
The proof can be done by induction by the number of vertices in a factorized vertex.
Provided that vertices are organized into some tree we try to evolve to the target tree.
Figure 8 shows the operations sequence. The full proof of this and subsequent
statements of this subsection can be found in [
Statement 4.2. The move vertex up/down and add/remove leaf vertex allow to organize vertices of a factorized vertex with the given start-vertex and attribute set into any tree6. Statement 4.3. Add/remove upper edge, move edge, and mark/unmark edge allow to obtain any set of outgoing edges that connect the vertices of a given factorized vertex with a xed set of start-vertices.
The above three statements have the following obvious corollary, which forms the next statement.
Statement 4.4. The operations of the type 1a enable to transform a given DTD graph to any other DTD graph that maps to the same schema S.
Statement 4 implies that, as soon as there is a list of operations of type 1b that allow to transform a DTD having a given DTD graph to any other DTD with the same DTD graph, are available the compatibility task can be completely solved within the model. The following operations compose the necessary operations of the type 1b list: inline/de-inline entity; convert leaf tag to attribute and vice versa; simplify/de-simplify regular expression; change processing instruction node; add/remove comment or namespace node. 6 Note that add/remove leaf vertex operation alone is not enough because of the presence of attributes 4.3
There are eight operations de ned for the S-model. They are similar to operations used
in OO databases evolution model in [
AddAttribute. Attribute a (the one being added) of vertex t is included into Ne(t). The sets Ne, N , H are recalculated for the vertex t and vertices reachable from t. Schema designer (or an external algorithm) may include this attribute into Ne sets of some successors of vertex t.
RemoveAttribute. Attribute a (the one being deleted) of vertex t is excluded from Ne(t), the sets Ne , N , H are recalculated for the vertex t and vertices reachable from t. Note, if t is in P (s) or a is in Ne(s), according to the axiom set, attribute a is included into N (s).
AddEdge. Let edge (t; s) is added. s is added into Pe(t) and t is added into De(s). Expressions dependent on Pe(t) and De(s) are recalculated. Note, that s is added into P (t) if there is no other path from s to t (same for D(s)).
RemoveEdge. This operation is complex, it may cause generation of new edges in the schema in order to keep from violating the axiom set. New edges will start in predecessors of the end vertex of a deleted edge and will end in its successors. Provided that we remove edge (t; s), s is deleted from Pe(t). All expressions dependent on Pe(t) are recalculated. If axioms are violated then the operation is rejected by the system. (Alternatively, the vertex t may be included into root vertex T , the change can be achieved in two stages: adding T into Pe(t), RemoveEdge for the edge (s; t), and if s is in Pe(t) s is added into the graph. The same may apply to vertex s and the stop vertex of the hierarchy). Analogous operations are performed with De(s).
AddVertex. Provided vertex t is added. t is included into hierarchy. The sets Pe(t) and De(s) are to be de ned by schema designer (or an external algorithm) to generate incoming edges of t. t is added into Pe(s) to satisfy axioms. In the simplest case, Pe(t) = T .
RemoveVertex. It is a complex modi cation. First, the vertex t is to be removed with the edges starting and ending in it. Second, a number of edges from its predecessors to its successors may be added. Third, attributes of vertex t, that are essential for its successors should migrate properly. The operation is implemented in three stages: applying RemoveAttribute to all attributes of t, applying RemoveEdge to all outgoing edges, and applying RemoveEdge to all incoming edges.
MergeVertex. Vertices being merged must be connected by an edge. Merged vertex Pe , De and Ne sets are unions of Pe , De and Ne sets of vertices being merged with exclusion of themselves. In Pe sets of reachable and De set of reaching vertices occurrences of the vertices being merged are replaced with occurrence of the merged one.
SplitVertex. Pe , De and Ne sets of split vertex are separated into two disjoint sets each. In Pe and Ne sets of reachable vertices occurrences of split vertex are replaced with one or both of the created without violating inclusion of P (t) in Pe(t) and D(t) in De(t) properties. wid create table U(id, address) <element author(id,address,.)> gauthor ? waddress alter table add(postalCode,town) <element authorAddress(address, postalCode,town,.)> wid b) waddress <element author(id,authorAddress,.)> <element authorAddress(address,.)> gauthor @ R@gauthorAddress alter table drop address <element authorAddress(postalCode,town,.)> wid d)
? w wtown
postalCode
In the sample we consider a revision of author address information. First, the authoraddress tag is added through the add leaf vertex Xml-only operation. Next, the move vertex down Xml-only operation is used. Then attributes with postal code, town and local address are added, and the old attribute with address information is removed. Changes in schemas in the process of transformation are shown on Figure 9. The functionality task obviously has a complete solution, which is enforced by the design of the model. That is, since the schema S is expressed in both, relational and XML, terms and only schema S contains semantics, necessarily, all semantics is contained in well de ned way in relational schema and can be queried directly through SQL.
The complete solution for the richness task means that any XML schema satisfying given semantic requirements may be obtained in the model. That enables solutions of schema transformation and other common problems inside the model. Statement 4.5. The operations of the 2nd type allow to transform any given schema S to any other schema S having the same Pe, De and Ne sets.
It is trivial corollary of completeness of the schema S model. The proof of the latter can
be found in [
Statement 5 enables us to provide a complete solution for the richness task. Indeed, an arbitrary XML schema complying with a given set of semantic constraints can be obtained from the given one complying with the constraints by consequent application of operations of the 2nd and 1st types. Statement 5 ensures that the schema S of the new a) CREATE TABLE U(id INT NOT NULL, postalCode NUMBER, town VARCHAR(50)); Vu := U b) CREATE TABLE U1(postalCode NUMBER); INSERT INTO U1 (SELECT postalCode from Vu GROUP BY postalCode); Vu := SELECT id, postalCode, town, localAddress FROM U JOIN U1 ON U.postalCode = U1.postalCode c) ALTER TABLE U1 ADD(town VARCHAR(50)); UPDATE U1 SET U1.town = U.town FROM Vu WHERE U1.postalCode = U.postalCode; Vu := SELECT id, postalCode, town, localAddress FROM U JOIN U1 ON U.postalCode = U1.postalCode AND U.town = U1.town d) ALTER TABLE U DROP town; Vu := SELECT id, postalCode, town, localAddress FROM U JOIN U1 ON U.postalCode = U1.postalCode
XML schema is obtained. The solution of compatibility problem enables to transform the intermediate result into the target XML schema. The relational-only operations consist of one operation: remove/add duplicate attribute in another relation. It replaces a pair of relations X1(A; ::) and X2(A; ::) with a pair of relations X1(::) (X1 may be dropped if empty; in the reverse operation X1 may be created) and X2(A; ::) where A is an attribute of one of the factorized vertices, and vice versa. The operation also affects the formulae of the mapping to schema S. Namely, the equi-joins of X1 and X2 (if any) used in the de nitions of Vi receive additional attribute A to the joined attributes set. Thus, the operation changes but does not break the form of the formulae that de ne the views.
In the sample we normalize the relations supposing that a town can be derived from a postal code. First, the postal code is duplicated in a new relation U1. Then the town information is moved from the relation U, which represents author information, to U1. Changes in S and relational schema in the process of transformation are shown on Figure 10. 4.6
The complete solution of the performance task ensures that we are able to perform arbitrary relational schema transformations as far as we do not need to change the XML schema. This task is similar to compatibility task with the schemas exchanging places. The following statement ensures that performance task is completely solved. Statement 4.6. Operations of the 3d type allow to transform a set of relations with the given sets of attributes and views values to any other set of relations with the same set of attributes and views values, if each attribute is used in the de nition of at least one view.
Proof. Provided we have an initial set of relations we try to evolve this set to a target
set of relations. Each relation includes a set of attributes as its header (which is part of
its relational type [
If we have one attribute (the same works for none attributes but the case of none attributes can be omitted) there is at least one view with the header that includes all (that is, one) attributes. All relations are necessarily projections of this view and since the view value does not change, the relations have the same values.
Now suppose we have N attributes in relations. Consider the selections on a xed value of Nth attribute of all relations and views. In the formulae that de ne the views selection commutes7 with other operations and the formulae may be transformed to make them have the form as required by the statement. The induction proposition can be applied to these selections. Since the selections on every value of the Nth attribute are equal, the original relations are equal (we use the fact that the real attribute domains that are really used are all nite).
We have shown that relation headers set determines the relations values, on the other hand, target schema headers set can be obtained by the operations of the 3rd type. That means that the target relations set can be obtained, QED. 5
We considered evolution model as a way to design XML-relational systems in the environment with rapidly changing requirements. We de ned compatibility, functionality, performance, and richness tasks that an XML-relational model should be able to solve. XML-only schema evolution models are not expressive enough to address all these tasks. The tasks need simultaneous consideration of both mutually dependent schemas.
We have suggested an XML-relational evolution model that allows to perform XMLor relational-only changes. We have shown that it ensures that semantic constraints can be obtained from relational schema, consequently, the model does not require obtaining an original XML document to evaluate an XML query. The model is rich enough to evolve a schema to any given XML schema. Thus, the employed model, contrary to XML-only models, is able to answer the stated requirements.
Several directions for future research exist. Intermediate schemas of the employed
XML-relational model may be enriched with entities that will represent regular
expressions and namespaces of the XML schema, or indices of the relational schema. Another
7 The proof could avoid using this fact as well as the niteness of domains, but it would require
more space.
interesting direction of research is to modify the model to allow a larger range of
mappings from XML to S-schemas. For example, the model can be enlarged to allow an
edge-table approach [