Dr Thuy-Linh Nguyen [HREF1], Lecturer, School of Computer Science and Information Technology [HREF2] , RMIT University [HREF3], GPO Box 2476v, Melbourne VIC 3001. tln@cs.rmit.edu.au
The advent of XML [XML98] has made it possible for a great variety of document types, or DTDs, to co-exist. Questions then arise about how developers can write DTDs and associated software and tools that are interoperable to one another, and how to maintain data integrity between documents and changing DTDs. These DTDs are typically versions of the same document type that evolves over time, or may even be those developed for different but overlapping domains. This paper reports our work done in this area. In this paper, we assume some knowledge of object-oriented technology from the reader.
These last few years have seen the emergence of numerous Document Type Definitions (DTD) as XML [XML98] brought the required expressive power. As with any systems, it is expected that a DTD will change and evolve over time into various versions of itself, or even forming branches of DTDs that support differing domains. DTD evolution typically involves such operations as addition or removal of an element type or attribute. These changes would impact all document instances, and software and tools that support a given DTD such as browsers, authoring tools, and XML database systems. DTD evolution raises two fundamental issues: (i) maintaining interoperability between software and tools that support differing DTDs, and (ii) maintaining data integrity between the changing DTDs and their document instances. Furthermore, support for dynamic DTD evolution (that is, allowing changes to be applied to document instances and DTDs in a consistent manner while their supporting software and tools are in operation) should also be considered.
This paper reports on LifeWeb [NGU01], our research project that takes an object-oriented [RUM91] approach towards the above issues. This approach has been taken mainly because of the proven benefit of system extensibility through generalisation/specialisation that object-oriented technology offers. Extensibility, as we shall see more clearly later, is a key feature towards interoperability and evolvability. The rest of this paper is structured as follows. The second section defines a mapping between DTD and object-orientation. The third section explains how our approach can maintain interoperability between differing DTDs and their associated software and tools. The fourth section explains how data integrity can be preserved. The fifth section explains how and to what level dynamic DTD evolution can be supported. The sixth section briefly goes through some scenarios in which our work may be used. Finally we conclude our paper with some future work.
Our object-oriented approach requires a mapping between DTD and object-orientation. In LifeWeb, a DTD is implemented as an object-oriented system where an element type (with its attributes) corresponds to a class (with its attributes and methods), and an element an object. Object-oriented relationships are mapped as follows. Nesting elements within one another represents a composition. Including the reference of one element in another (using IDREF or IDREFS) denotes an association. Generalisation/specialisation is not defined for DTD, but for experimental purposes, has been supported in our system by a special read-only attribute, superclass, whose value is the name of the element supertype (superclass) of the current element type. (For simplicity we do not consider other XML constructs such as entities, processing instructions, notation, and so on.)
Figure 1 shows the core LifeWeb model in UML (Unified Modeling Language) [UML98]
notation (an object-oriented notation). Figure 2 shows the same model in XML
notation (as a DTD). In both figures, attributes are not shown, except where
they represent object-oriented relationships. (Note: the element type
Figure 1. The LifeWeb core model in UML notation
<!ELEMENT lifeweb (document|struct|material|presentation)*>
<!ELEMENT document (struct|material)*>
<!ATTLIST document
present IDREFS #IMPLIED
<!ELEMENT struct (struct|material)*>
<!ATTLIST struct
superclass CDATA #FIXED "document"
<!ELEMENT material EMPTY >
<!ELEMENT presentation EMPTY >
|
Figure 2. The LifeWeb core model in XML notation
The following pairs of terms may be used interchangeably in this paper: DTD and class system, document and system instance, element type and class, and element and object. The term schema may also be used interchangeably with the term class system. Because of the object-oriented approach taken in this project, we will use mainly object-oriented terminology in this paper, sometimes with XML mapping in parentheses, unless otherwise specified.
The mapping of DTD to an object-oriented system permits evolution operations to be defined in terms of class and relationship. Using these terms, evolution operations for DTDs can be broadly categorised into three groups:
We observe that changes in the first 2 categories (i) and (ii) alter the internal definition of a class, which result in inconsistency among components in an object-oriented system. For instance, removing an attribute can affect all classes that use that attribute. Maintaining system consistency, which is necessary for preserving system interoperability, is complicated and expensive. The complication and costs involved in these operations are well-studied, in particular in Database Scheme Evolution (DBSE) [BAN87, PET97], a field closely related to DTD evolution. Direct system modifications that belong to the categories (i) and (ii) are thus prohibited in LifeWeb. (We will see later that these changes can still be done via the third category.)
Another observation is that while association and composition may be formed between objects or classes, generalisation/specialisation may be formed between classes only. The latter is really a taxonomical relationship that defines a mechanism to evolve the system. For instance, we may evolve the class Document in Figure 1 by subclassing it into classes Publication and Book. Graphically, generalisation/specialisation relationship can be seen as being elevated on another plane, separate from association and composition (see Figure 3).
Figure 3. Generalisation/specialisation as a taxnomical relationship and an evolution mechanism
Evolution via the generalisation/specialisation relationship by adding or removing a class through this relationship simply means extending or truncating, respectively, the inheritance tree. Clearly adding does not destroy system consistency, due to the extensibility characteristic of object-orientation. Consequently, system interoperability is preserved. For instance, with reference to Figure 3, any (object-oriented) software that supports class Publication also supports class Document. Likewise, any software that supports class Book also supports classes Document and Publication. Removing a class via the generalisation/specialisation relationship is more complicated, since we have to consider the classes and objects that depend on the class to be removed. This issue will be discussed in the next section (Dependency clearance).
Based on the above observations, we have allowed only direct addition and removal of an entire class via the generalisation/specialisation relationship. (This belongs to the third category of evolution operations mentioned previously). Evolution operations that belong to other categories must be carried out via operations in this category. To this end, in order to change the definition or superclass(es) of an existing class, a new class (with the desired features) must be developed and introduced into the system through an appropriate generalisation/specialisation relationship. As mentioned above, this operation does not violate the system consistency and interoperability, due to the extensibility characteristic of object-oriented design.
To summarise, DTD evolution using our approach means that new element types are introduced into the system by deriving them from existing types through the generalisation/specialisation relationship, and only through this relationship. Any changes to an existing element type such as adding, removing or modifying an attribute must be done by deriving a new type from an appropriate existing type, for instance an ancestor of the type to be changed. An existing element type that is no longer used in other element types and document instances may be removed by breaking its relationship with its parent type. In this case we need to consider the element types and elements that are dependent on the element type to be removed. This necessitates the introduction of dependency clearance constraint (see below). Software and tools supporting a DTD, implemented in object-oriented technology, can share the same data model and evolution path as the DTD, and remain interoperable with one another along this evolution path.
Dependency clearance is a constraint we impose on any class that is to be removed from the system. We observe that a class can be removed without destroying the system consistency if no other classes or objects are dependent on it. This means:
These two conditions constitute the dependency clearance constraint.
It is possible to satisfy dependency clearance, although this usually requires careful system design through all stages of system evolution. We will now look at how dependency clearance can be achieved in LifeWeb.
A class that is free of dependency at the class level is simply one that is not owned, used, contained, or inherited by any other class, such as the Book class in Figure 3. In addition, for the purpose of class removal, classes may have dependent class(es) but if all of them are to be removed together they are also considered free of dependency at the class level. (In this case we are removing one whole branch in the inheritance tree.)
Dependency clearance (at the class level) seems a rather strict constraint. On speculation however, this constraint appears sensible in most cases. When the class we are thinking of removing still finds its use in some other classes, perhaps we simply should not remove it. Or if it is really useless, perhaps we should remove it together with all the classes that use it, otherwise how can we say it is useless? We observe an interesting case that exemplifies the first option: the existence of an ancestor class that has no corresponding objects and may not even be used in any other relationship to other classes. Such a seemingly useless class has in fact been widely used in object-oriented technology: the abstract class. The second option (removing the class and all classes that depend on it) makes sense in its own right, although it involves a recursive operation and can be expensive. This underlines the importance of early design choices, especially a design that is generic enough to cope with future changes.
A class that is free of dependency at the object level is simply one that does not have any corresponding objects. Typically we want to achieve this when a class has evolved into a new class (via the generalisation/specialisation relationship, as explained above), and we need to migrate all objects of the old class to the new class. Occasionally we may also want to migrate objects between two sibling classes when one is meant to replace the other (i.e. the new class is derived from a common parent in order to replace the other, older, class).
In LifeWeb object migration is done in an incremental, decentralised, and asynchronous manner via a special property, expiration. This property is captured in two attributes defined for each system instance (document):
If a system instance (document) has not been accessed (used) for a relativeExpiration period of time, or if it is still accessed but has reached the absoluteExpiration time, it will be destroyed. In the first case, it will be destroyed forever. In the second case, it will be immediately recreated with any necessary updates to reflect the most recent evolutionary change in the class system (DTD). This way, objects can be migrated to new classes, and their original versions released (to be removed later). This process, which is repeated many times over the entire population of system instances (documents) of a given class system (DTD), eventually replaces all occurrences of the old version of the class system (DTD) with the new one. At this point of time, all the old classes become free of dependency at the object level.
In most cases object migration should be straightforward, since the new class is typically derived from the old class, and every feature in the old class is inherited in the new class. When this is not the case (for instance, the new class is a sibling of the old class) we may need to give some extra instructions, possibly in the code that defines or implements the new class. For instance, if the new class does not have some attributes defined in the old class, we may want to specify how to recapture these extra attributes or simply discard them.
When an element type is free of dependency at both the class and object levels, it can be safely removed. System consistency and data integrity are not affected. Consequently, software and tools that support the evolving DTD (and share the same data model and evolution path with the DTD) remain interoperable with one another along the evolution.
This section does not relate to many object-oriented concepts and we will mainly use XML terminology here to stay in the DTD context.
Dynamic DTD evolution refers to the ability to carry out evolution tasks for software and tools that supports the evolving DTD while they are in operation. It also involves automating these tasks where applicable. Using our approach described above, permissible evolution tasks include:
(i) Adding a new element type
(ii) Adding a new DTD
(iii) Removing an old element type
(iv) Removing an old DTD
(v) Migrating elements to a new element type
(vi) Migrating documents to a new DTD
Of the tasks above, (i) can only be partly automated and (ii) has to be done manually. Generally, this is because human intervention is needed to create and introduce something new into the system. If we think of DTD evolution as an analogy of natural evolution, humans just have to "play God" when they want to create and introduce new things. We will see more clearly below what can or cannot be automated.
This task can only be partly automated. Humans need to design and add the new
element type (declaratively) into the (evolving) DTD, and implement the corresponding
class associated with that element type. The integration of the new class into
the runtime system of the software supporting this DTD however, can be done
both automatically and dynamically with today's technology. In LifeWeb, this
was implemented by defining a special attribute behaviour for all element
types. (This is possible because we map all element types to classes in our
object-oriented approach.) The value of this attribute is the name of the class
that supports the type. For instance, the behaviour attribute of the
This task cannot be automated. It simply involves human (declaratively) modifying an existing DTD with new element type(s) included (as described above) and old element type(s) marked for removal (as described below).
An element type must be marked for removal (by a human) before it can be removed (by the system). This can be done by defining a special attribute replacedBy for all element types. The value of this attribute may be an empty string, which means the current element type is not being replaced. It may be the string "null", which means the current element type is to be removed without replacement. It may contain the name of another element type, which means the current element type is to be replaced by the other element type. Element types marked for removal will have their elements migrated to new element types. As the system moves these elements (see below), it keeps track of changes in the whole system. This allows the system to determine the interdependency amongst elements and element types for each migration. When migration has reached a point such that an element type marked for removal becomes free of dependency at both object and class levels, the system can simply remove it from the DTD (and possibly also its corresponding class from the file system if required).
Similar to an element type, a DTD must also be marked for removal before it can be removed. XML does not have any standard to support this, but there can be several non-standard ways. One way is to define a special comment <!-- Replaced by --> for the DTD, which holds the reference to the new DTD. The cons of this is that we are overloading the use of comment. Another way is to simply base on the timestamp of the various files representing the same DTD - the most recent one is to replace the older ones. The cons of this is the (likely small) overhead in checking the timestamps of various files. (We used the second way in our implementation.) The system moves documents from the DTD marked for removal to the new DTD. When all documents of the old DTD have been migrated to the new DTD, the old DTD has logically been removed. Its physical removal can also be automated if required, since the system can keep track of document changes during migration and can perform such removal safely without human intervention.
Element migration is required when an element type is marked for replacement by another (with the replacedBy attribute). As explained previously, element migration is straightforward when the new element type is simply derived from the old one. When this is not the case, we may need to specify, for instance in the class implementation or DTD definition of the new type, how to deal with the inconsistency between the two types.
Document migration is required when a DTD is marked for replacement by another. This process is straightforward since the new DTD either conforms to the old DTD or it does not matter if it does not conform. A new DTD conforms to an old DTD if element types are only added (through the generalisation/specialisation relationship) to the old one to form the new one (i.e. there is no removal). In this case all element types in the old DTD can simply be carried over to those in the new DTD. If an element type has been removed from the old DTD to form the new DTD, by dependency clearance constraint, that type must have no corresponding elements. This eliminates the need to map the element type that has been removed in the old DTD when document migration is performed. The migration process (for both element type and DTD) can be carried out in a low priority thread. The thread can quietly check for documents' expiry dates, move elements and documents, and remove element types and DTDs when applicable, while keeping track of changes in the whole system.
Support for dynamic DTD evolution described above is likely most useful to DTD-specific, standalone systems, such as some authoring tools, browsers, and XML database systems. It may also be beneficial to distributed systems such as the Web although more work needs to be done.
Toot-O-Matic, a free and open source XML authoring tool developed by Doug Tidwell at IBM Developers Works [TID01] is an example of a DTD-specific, standalone software system that may benefit from our approach. The tool is implemented for one specific, non-standard DTD to create online tutorials. Tutorial materials are manually tagged with the vocabulary defined by that DTD, and the tool can be used to produce output in various formats: HTML, PDF, and ZIP (an archive of HTML files for easy download). The tool is considered "standalone" in the sense that it is based on a non-standard DTD that is typically not referenced anywhere except by documents that are authored on the same machine with the tool and the DTD. Using our approach, the tool may be easily made adaptable to more customised DTDs, or an evolving DTD. As the DTD, documents and tool all reside on the same machine, the tool would have the required read and write permissions to perform evolution tasks on the DTD and documents. Browsers that support specific and non-standard DTDs would benefit from our approach in a similar way.
XML database systems may also benefit from our approach. Schema evolution is a traditional research topic in the database area, and is closely related to our work, so we will give a bit more detailed comparison here. Different from our approach, Database Schema Evolution (DBSE) permits all 3 categories of evolution operations (see the third section), including those that alter the internal definition of a class. For instance, it is possible to directly remove or add a superclass or an attribute of a class. This approach gives more freedom about what kind of schema changes are allowed, but can generate a ripple effect to all affected classes and instances. A set of invariants and rules have to be observed to maintain schema and data consistency. Banjeree et al. [BAN87] has defined a widely accepted set of 5 invariants and 12 rules. The invariants are to ensure system consistency and the rules dictate how to resolve arising conflicts. For instance, a rule can say which attribute should be inherited if adding a superclass to a class results in attribute name conflict. Clearly observation of these invariants and rules is complicated and costly. Our approach restrains from changing the internal definition of a class, thus has only the dependency clearance constraint to observe.
We also take a different approach in propagating changes from schema (DTD) to instances (documents). In DBSE, change propagation is done by techniques such as screening, conversion and filtering [PET97]. All of these techniques explicitly coerce instances to reflect changes of the schema. For instance, in screening objects are coerced when they are accessed by applying (possibly multiple) conversion program(s) on them. Screening suffers performance penalty during object access and can increase system overhead to keep track about which objects still need to be updated. The conversion technique converts affected objects immediately on each schema change. This causes processing delay during the schema modification phrase, but not during object access. The filtering approach does not propagate changes to objects, but creates a different version of a schema for each schema change, and the old objects remain with the old version while new objects are created for the new version. Filtering introduces overhead for maintaining and co-ordinating between different versions. Our approach incurs overhead in keeping track of document changes like screening does, but unlike this technique, it does not suffer performance penalty because conversion of document instances happens gradually and asynchronously over time.
Building an evolvable Web using our approach is possible but still a great challenge. The major issues here are that it is difficult to keep track of document changes over a distributed system, and that we do not have read and write permission on other machines to perform evolution tasks. What our technology may be able to do for the Web now is perhaps to facilitate maintaining interoperability between DTD-specific tools (such as browsers) that support different (versions of) standard, publicly used DTDs (such as XHTML or MathML at W3C [W3C]). This is because software interoperability can be preserved by following the evolution path that we have defined, and functional evolution of software can be done declaratively (by mapping DTD to object-oriented classes, recording this mapping and using technology such as Java reflection). Without the ability to automate the tracking of document changes and checking of data integrity however, we are yet unsure of the practical value of our technology to the current Web. Automating the evolution process for the Web as described above in the previous sections is still a great challenge for the future.
There has not been work done specifically for DTD evolution as far as we are aware of. As mentioned above, Database Schema Evolution is the field that is closest to ours, but is not done in the XML or Web context. Recently the issue of interoperability between metadata schemas has emerged and some work has been reported [HER00, HUN01]. This topic however, is about combining various standard metadata schemas such as RDF Schema and XML Schema in a single Web application profile. It does not concern about software interoperability or document type evolution. Apparently not much has been done in the area we are working on, the least for the Web.
Working out an answer for the Web thus, is one of our main future directions. As mentioned above, the two major issues in applying our technology to the Web are the ability to track document changes and to perform evolution tasks over a distributed system. If evolution tasks can be distributed, and document changes at distributed sites can be collated at one site, perhaps we could be able to make the Web evolvable. Here, each distributed site would take care of moving its own documents and elements, and report changes back to the DTD-hosting site. The DTD-hosting site would perform DTD and element type removals as appropriate, based on the reported information. Working out a reporting protocol is perhaps our next task.
[BAN87] Banerjee J., et al, 1987. Semantics and implementation of schema evolution in object-oriented databases. In: Proceedings of the ACM SIGMOD Annual Conference on Management of data, San Francisco, CA USA, 27-29 May 1987. ACM Press, 311 - 322
[HER00] Heery, R., Patel, M., 2000. Application Profiles: mixing and matching metadata schemas. Ariadne Issue 25, Sept 2000 [online]. Available online [HREF4]
[HUN01] Hunter, J., Logoze, C., 2001. Combining RDF and XML Schemas to enhance interoperability between metadata and application profiles. In: Proceedings of WWW10 International Conference, Hongkong, 1-5 May 2001
[JAR98] Jarke, M. et al, 1998. Meta Modeling: A Formal Basis for Interoperability and Adaptability. In: B Kramer, M Papazoglou, H-W Schmidt, eds., Information System Interoperability. Research Studies Press Ltd, John Wiley & Sons Co, 229-263
[JAV02] The JavaTM Tutorial. Trail: The Reflection API. Available online [HREF5]
[NGU01] Nguyen, T-L, 2001. An Object-Oriented Data Model for Evolvable Web Systems. PhD Thesis. Monash University
[PET97] An axiomatic model of dynamic schema evolution in objectbase systems;Randel J.Peters, and M. TamerÖzsu; ACM Trans. Database Syst. 22, 1 (Mar. 1997), Pages 75 - 114
[RUM91] Rumbaugh, J., 1991, Object-oriented Modeling And Design, Prentice Hall
[TID01] Tidwell, D, 2001. XML training wheel. An XSLT and Java-based tool for producing tutorials - custom-built for developerWorks but ready to adapt to your own use. Available online [HREF6]
[UML98] UML Reference. Available online [HREF7]
[XML98] Extensible Markup Language (XML) 1.0 (1998). World Wide Web Consortium. Available online [HREF8]
[W3C] World Wide Web Consortium. Available online [HREF9]