The transformation language ELaX (Evolution Language for XML-Schema [16]) is a domain-speci c language for modifying existing XML Schemas. ELaX was developed to express complex modi cations by using add, delete and update statements. Additionally, it is used to consistently log all change operations speci ed by a user. In this paper we present the rule-based optimization algorithm ROfEL (Rule-based Optimizer for ELaX) for reducing the number of logged operations by identifying and removing unnecessary, redundant and also invalid modi cations. This is an essential prerequisite for the co-evolution of XML Schemas and corresponding XML documents.
The eXtensible Markup Language (XML) [2] is one of the most popular formats for exchanging and storing structured and semi-structured information in heterogeneous environments. To assure that well-de ned XML documents are valid it is necessary to introduce a document description, which contains information about allowed structures, constraints, data types and so on. XML Schema [4] is one commonly used standard for dealing with this problem. After using an XML Schema a period of time, the requirements can change; for example if additional elements are needed, data types change or integrity constraints are introduced. This may result in the adaptation of the XML Schema definition.
In [16] we presented the transformation language ELaX (Evolution Language for XML-Schema) to describe and formulate these XML Schema modi cations. Furthermore, we mentioned brie y that ELaX is also useful to log information about modi cations consistently, an essential prerequisite for the co-evolution process of XML Schema and corresponding XML documents [14].
One problem of storing information over a long period of time is, that there can be di erent unnecessary or redundant modi cations. Consider modi cations which rstly add an element and shortly afterwards delete the same element. In the overall context of an e cient realization of modi cation steps, such operations have to be removed. Further issues are incorrect information (possibly caused by network problems), for example if the same element is deleted twice or the order of modi cations is invalid (e.g. update before add).
The new rule-based optimizer for ELaX (ROfEL - Rulebased Optimizer for ELaX) had been developed for solving the above mentioned problems. With ROfEL it is possible to identify unnecessary or redundant operations by using di erent straightforward optimization rules. Furthermore, the underlying algorithm is capable to correct invalid modication steps. All in all, ROfEL could reduce the number of modi cation steps by removing or even correcting the logged ELaX operations.
This paper is organized as follows. Section 2 gives the necessary background of XML Schema, ELaX and corresponding concepts. Section 3 and section 4 present our approach, by rst specifying our ruled-based algorithm ROfEL and then showing how our approach can be applied for an example. Related work is shown in section 5. Finally, in section 6 we draw our conclusions. 2.
In this section we present a common notation used in the remainder of this paper. At rst, we will shortly introduce the XSD (XML Schema De nition [4]), before details concerning ELaX (Evolution Language for XML-Schema [16]) and the logging of ELaX are given.
The XML Schema abstract data model consists of di erent components (simple and complex type de nitions, element and attribute declarations, etc.). Additionally, the element information item serves as an XML representation of these components and de nes which content and attributes can be used in an XML Schema. The possibility of specifying declarations and de nitions in a local or global scope leads to four di erent modeling styles [13]. One of them is the Garden of Eden style, in which all above mentioned components are globally de ned. This results in a high re-usability of declarations and de ned data types and in uences the exibility of an XML Schema in general.
The transformation language ELaX1 was developed to handle modi cations on an XML Schema and to express such modi cations formally. The abstract data model, element information item and Garden of Eden style were important through the development process and in uence 1The whole transformation language ELaX is available at: www.ls-dbis.de/elax the EBNF (Extended Backus-Naur Form) like notation of ELaX.
An ELaX statement always starts with "add", "delete" or "update" followed by one of the alternative components (simple type, element declaration, etc.), an identi er of the current component and completed with optional tuples of attributes and values (examples follow on, e.g. see gure 1). The identi er is a unique EID (emxid)2, a QNAME (quali ed name) or a subset of XPath expressions. In the remaining parts we will use the EID as the identi er, but a transformation would be easily possible.
ELaX statements are logged for further analyses and also as a prerequisite for the rule-base optimizer (see section 3). Figure 1 illustrates the relational schema of the log. The file-ID time EID Toypp-e Tmyspge- content 1 1 1 add 0 add element name 'name' type 'xs:decimal' id 'EID1' ; 1 2 1 upd 0 update element name 'name' change type 'xs:string' ; 1 3 2 add 0 add element name 'count' type 'xs:decimal' id 'EID2' ; … … … … … … chosen values are simple ones (especially the length). The attributes le-ID and time are the composite key for the logging relation, the EID represents the unique identi er for a component of the XSD. The op-Type is a short form for add, delete (del) or update (upd) operations, the msg-Type is for the di erent message types (ELaX (0), etc.). Lastly, the content contains the logged ELaX statements. The leID and msg-Type are management information, which are not covered in this paper. 3.
The algorithm ROfEL (Rule-based Optimizer for ELaX) was developed to reduce the number of logged ELaX operations. This is possible by combining given operations and/or removing unnecessary or even redundant operations. Furthermore, the algorithm could identify invalid operations in a given log and correct these to a certain degree.
ROfEL is a rule-based algorithm. Provided that a log of ELaX operations is given (see section 2), the following rules are essential to reduce the number of operations. In compliance with ELaX these operations are delete (del), add or update (upd). If a certain distinction is not necessary a general operation (op) or variable ( ) are used, empty denotes a not given operation. Additionally, the rules are classi ed by their purpose to handle redundant (R), unnecessary (U) or invalid (I) operations. ROfEL stops (S) if no other rules are applicable, for example no other operation with the same EID is given.
// # most recent operation: delete (del) # R: del(EID) ! del(EID) ) del(EID)
U: upd(EID; content) ! del(EID) ) del(EID)
with time(del(EID)) := TIME(del(EID), upd(EID, content))
(
) add(EID; content) ) upd(EID; content) // # most recent operation: update (upd) # I: op(EID) ! del(EID) ! upd(EID, content) ) op(EID) ! upd(EID, content) U: add(EID; content) ! upd(EID, content)
) add(EID; content) U: add(EID; content) ! upd(EID, content') ) add(EID; MERGE(content0; content)) R: upd(EID; content) ! upd(EID, content)
) upd(EID; content) U: upd(EID; content) ! upd(EID, content') ) upd(EID; MERGE(content0; content)) The rules have to be sequentially analyzed from left to right (!), whereas the left operation comes temporally before the right one (i.e., time(left) < time(right). To warrant that the operations are working on the same component, the EID of both operations is equal. If two operations exist and a rule applies to them, then the result can be found on the right side of ). The time of the result is the time of the prior (left) operation, except further investigations are explicit necessary or the time is unknown (e.g. empty).
Another point of view illustrates, that the introduced rules
are complete concerning the given operations add, delete
and update. Figure 2 represents an operation matrix, in
which every possible combination is covered with at least one
rule. On the x-axis the prior operation and on the y-axis the
(
add
add (
Rule (
(op.EID in opx.content))
then return t;
return t';
end.
ters and returns a time value, dependent on the existence of
an operation, which references the EID in its content. If no
such operation exists, the time of the result in rule (
The rules (
The rules (
All mentioned rules, as well as the functions TIME() and
MERGE() are essential parts of the main function
ROFEL(); the pseudocode is presented in gure 5. ROFEL()
ROFEL(log):
// log = ((t1,op1), (t2,op2), ...); t1 < t2 < ...;
begin
for (i := log.size(); i >= 2; i := i - 1)
for (k := i - 1; k >= 1 ; k := k - 1)
if(!(log.get(i).EID == log.get(k).EID AND
log.get(i).time != log.get(k).time))
then continue;
// R: del(EID) -> del(EID) => del(EID) (
log.get(k).op-Type == 1)
then
log.remove(i);
return ROFEL(log);
// U: upd(EID, content) -> del(EID)
// => del(EID) (
log.get(k).op-Type == 2)
then
temp := TIME(log.get(i), log.get(k));
if (temp == log.get(i).time)
then
log.remove(k);
return ROFEL(log);
log.get(k) := log.get(i);
log.remove(i);
return ROFEL(log); [...]
// U: upd(EID,con) -> upd(EID,con')
// => upd(EID, MERGE(con',con)) (
log.get(k).op-Type == 2) then temp := MERGE(log.get(i).content,
log.get(k).content); log.get(k).content := temp; log.remove(i); return ROFEL(log); return log; end. has one input parameter, the log of ELaX operations. This log is a sequence sorted according to time, it is analyzed reversely. In general, one operation is pinned (log.get(i)) and compared with the next, prior operation (log.get(k)). If log.get(k) modi es the same component as log.get(i) (i.e., EID is equal) and the time is di erent, then an applying rule is searched, otherwise the next operation (log.get(k - 1)) is analyzed. The algorithm terminates, if the outer loop completes successfully (i.e., no further optimization is possible).
Three rules are presented in gure 5; the missing ones
are skipped ([...]). The rst rule is (
The second rule is (
The last rule is (
After introducing detailed information about the concept of the ROfEL algorithm, we want to use it to optimize an example in the next section.
In the last section we speci ed the rule-based algorithm ROfEL (Rule-based Optimizer for ELaX), now we want to explain the use with an example: we want to store some information about a conference. We assume the XML Schema of gure 6 is given, a corresponding XML document is also presented. The XML Schema is in the Garden of Eden style and contains four element declarations (conf, name, count, start ) and one complex type de nition (confType) with a group model (sequence). The group model has three element references, which reference one of the simple type element declarations mentioned above. The identi cation of all components is simpli ed by using an EID, it is visualized as a unique ID attribute (id = "..").
The log of modi cation steps to create this XML Schema is presented in gure 7. The relational schema is reduced in comparison to gure 1. The time, the component EID, the op-Type and the content of the modi cation steps are given. The log contains di erent modi cation steps, which are not time given in the XML Schema (EID > 9). Additionally, some entries are connected within the new introduced column ROfEL. The red lines and numbers represent the involved log entries and applying ROfEL rule.
The sorted log is analyzed reversely, the operation with
time stamp 14 is pinned and compared with time entry 13.
Because the modi ed component is not the same (EID not
equal), the next operation with time 12 is taken. Both
operations delete the same component (op-Type == 1 ).
According to rule (
Rule (
Afterwards, ROFEL restarts again and rule (
The last applying rule is (
The modi cation log of gure 7 is optimized with rules
(
Comparable to the object lifecycle, we create new types or elements, use (e.g. modify, move or rename) and delete them. The common optimization rules to reduce the number of operations are originally introduced in [10] and are available in other application in the same way. In [11], rules for reducing a list of user actions (e.g. move, replace, delete, ...) are introduced. In [9], pre and postconditions of operations are used for deciding which optimizations can be executed. Additional applications can easily be found in further scienti c disquisitions.
Regarding other transformation languages, the most commonly used are XQuery [3] and XSLT (Extensible Stylesheet Language Transformations [1]), there are also approaches to reduce the number of unnecessary or redundant operations. Moreover, di erent transformations to improve e ciency are mentioned.
In [12] di erent "high-level transformations to prune and merge the stream data ow graph" [12] are applied. "Such techniques not only simplify the later analyses, but most importantly, they can rewrite some queries" [12], an essential prerequisite for the e cient evaluation of XQuery over streaming data.
In [5] packages are introduced because of e ciency bene ts. A package is a collection of stylesheet modules "to avoid compiling libraries repeatedly when they are used in multiple stylesheets, and to avoid holding multiple copies of the same library in memory simultaneously" [5]. Furthermore, XSLT works with templates and matching rules for identifying structures in general. If di erent templates could be applied, automatic or user given priorities manage which template is chosen. To avoid unexpected behaviour and improve the e ciency of analyses, it is a good practise to remove unnecessary or redundant templates.
Another XML Schema modi cation language is XSchemaUpdate [6], which is used in the co-evolution prototype EXup [7]. Especially the auto adaptation guidelines are similar to the ROfEL purpose of reducing the number of modi cation steps. "Automatic adaptation will insert or remove the minimum allowed number of elements for instance" [6], i.e., "a minimal set of updates will be applied to the documents" [6].
In [8] an approach is presented, which deals with four operations (insert, delete, update, move) on a tree representation of XML. It is similar to our algorithm, but we use ELaX as basis and EIDs instead of update-intensive labelling mechanisms. Moreover the distinction between property and node, the "deletion always wins" view, as well as the limitation that "reduced sequence might still be reducible" [8] are drawbacks. The optimized reduction algorithm eliminates the last drawback, but needs another complex structure, an operation hyper-graph. 6.
The rule-based algorithm ROfEL (Rule-based Optimizer for ELaX) was developed to reduce the number of logged ELaX (Evolution Language for XML-Schema [16]) operations. In general ELaX statements are add, delete and update operations on the components of XML Schema, specied by a user.
ROfEL allows the identi cation and deletion of unnecessary and redundant modi cations by applying di erent heuristic rules. Additionally, invalid operations are also corrected or removed. In general if the preconditions and conditions for an adaptation of two ELaX log entries are satis ed (e.g. EID equivalent, op-Type correct, etc.), one rule is applied and the modi ed, reduced log is returned.
We are con dent, that even if ROfEL is domain speci c and the underlying log is specialized for our needs, the above speci ed rules are applicable in other scenarios or applications, in which the common modi cation operations add, delete and update are used (minor adaptations preconditioned).
Future work. The integration of a cost-based component
in ROfEL could be very interesting. It is possible, that under
consideration of further analyses the combination of di erent
operations (e.g. rule (
Feasibility of the approach. At the University of Rostock we implemented the prototype CodeX (Conceptual design and evolution for XML Schema) for dealing with the co-evolution [14] of XML Schema and XML documents; ROfEL and corresponding concepts are fully integrated. As we plan to report in combination with the rst release of CodeX, the signi cantly reduced number of logged operations proves that the whole algorithm is de nitely feasible. 7.