PDoS - Pinnacles DSSSL-O Stylesheet   Table of contents   Indexes   Introducing SGML into the RAF Flight Manuals World or Throttle to Bottle in Two Extraordinary Years
  Mφller  Henning 
 

Towards an SGML Diff Using Temporal Documents

 

Abstract:

 A method to develop an SGMLdiff is presented. The extendible approach is based on a change-oriented model for structured documents containing e.g. objects of type `data', `element', `attribute', or `link'. The difference between two documents A and B is computed and expressed as a sequence of changes that must be incrementally performed on the objects in A in order to obtain the state B.
 

Introduction

 

Equivalence and changes in SGML documents

 Companies that must handle huge amounts of technical documentation can use SGML to mark up their documents in order to process, interchange, and archive them independently of any particular proprietary format. An author often faces different versions and variants of a document. In case these are two SGML document instances that are similar, but where the relation between them is not clear, he needs a meaningful description of their differences.
 As SGML is used to encode additional information about thestructure of a document an SGMLdiff should reflect the data structure of the documents it compares. It is not enough to get a description of differences between two SGML document instances on the basis of their unstructured textual contents.
 The question of expressing differences is closely connected to the notion of identity for the components of an SGML-document. As state, the SGML standard has little to say about change management. The reason for this is that documents are traditionally perceived as static entities that do not change – on the contrary, a document is used tofix a certain state of the documented information. From this point of view, concepts to express what remains `the same' as the document is changed are not needed.
 Nowadays, more and more documents are put online and can therefore easily be updated. This raises important questions about consistency, redundancy, and correctness of the information, and the effectiveness of the underlying work processes : how can different versions of a document be compared? Is it possible to trace the evolution of the information encoded in an SGML document? And since most documents contain a multitude of copied parts, how can I guarantee that my change does not affect the correctness of the document? Is it necessary to perform a similar change on each copy or is some other editing needed to restore the consistency of the document?
 The aim of this paper is to propose a method to build an SGMLdiff that computes the difference between two SGML document instances A and B as the sequence of changes that would produce B if incrementally performed on A. The task of developing such an SGMLdiff is threefold: first, the object types of an SGML document must be determined, and second the possible changes for those objects have to be specified. Finally an algorithm is needed to compute the delta between two documents.
 
 

Related work

 The traditionaldiff utility is not appropriate for the task of comparing two SGML instances, mainly because it operates on plain text files and computes a list of deleted, modified or new lines. Though SGML documents are also encoded in one or more files using the ASCII character set, a comparison of therepresentation of two SGML documents is quite different from the differences between the documents themselves and not at all useful for an author to understand what has changed.
 The Palimpsest data model described in is much more sophisticated. Not only does it define a variety of basic data types for a document such as sequences, sets, or tables, it also addresses the problems of flexible merging and tracking of individual changes to a shared hypertext or multimedia document.
 Palimpsest describes documents entirely in terms ofdeltas ; any manipulation of a document affects only the set of deltas, not the data objects in the document state. However, the deltas that determine a document state are not ordered as a sequence of editing changes, so the information about any intermediate state during the creation process is lost.
  discuss four algorithms to determine the minimal editing distance between two ordered labelled trees and propose a new algorithm that not only usesinsert ,delete , andchange as primitive operations, but alsoswap ,merge ,split , andmove . The goal of the algorithm is to determine aminimal editing sequence, but not a difference between the documents that reflects the semantics of a change sequence performed by the author. To illustrate the difference, consider two adjacent nodes (`INTRO' left of `SECT' written as `INTRO,SECT') in a document. The author first permutes the nodes and gets `SECT,INTRO'. Then he changes the label of `INTRO' into `SECT'. The minimal editing sequence from `INTRO,SECT' to the final state `SECT,SECT' would be to just rename the `INTRO' on the left into `SECT' without performing any swapping. In case of empty nodes the transposition may not be important, but if `INTRO' or `SECT' have any content objects in their subtree, the equivalence between these unchanged content objects gets lost.
 
 

approach

 The discussion above has shown that the equivalence of components in an SGML document cannot be recognized from a simple comparison of two document states. The proposed approach therefore does not compare two states to determine their differences. It rather compares a change-oriented representation of each document. Such atemporal document reflects the evolution of its contents as it contains – in form of a sequentialchange history – a description of those changes that are needed to create the document.
 Three problems for the development of an SGMLdiff based on temporal documents will be addressed in this paper: what are the objects in an SGML document instance, how can we appropriately describe the changes, and how can the change history of a document be created? Last, a method is needed to compute the difference of two temporal documents. The rest of the paper is organized as follows: first the underlying model of temporal documents is introduced (section ). Section shows how temporal documents can be used to compute a meaningful set or – if needed – sequence of differences and which requirements must be fulfilled. In section , a realized prototype is described that operates on a simplified SGML document model. Section summarizes the results and shows the direction of improvements and further development.
 

Temporal documents

 
 

Change-oriented view of documents

 The change-oriented view of a document focusses on the evolution of a document: instead of describing the actualstate of the document it describes itschange history .
 If all changes described in a temporal document can be automatically executed, its final state can always be reconstructed by an appropriate tool. The change-oriented approach of representing a document therefore leads to the same result as the traditional state-oriented concept of documents. Additionally, if a temporal document contains the description of all changes performed on it, each intermediate state, e.g. a specific version of the document's history or creation can be rebuilt.
 
 

Elementary changes

 The components of a temporal document are descriptions of elementary changes that have been performed on an SGML document. These sequentially orderedchanges describe the complete generation of the document out of an initially empty state. The changes must be elementary to guarantee an unambiguous way to describe the actions actually performed on the document.
 At least three types of changes exist for each type of object that may constitute an SGML document: insertion, modification, and deletion. Other elementary change types may exist that depend on the object type under consideration. As section will show, e.g. nodes in the SGML tree that contain character data – HyTimepseudo-elements – can be split in two new ones, or adjacent pseudo-elements may be joined to form a single one. Another change type may describe that an SGML element has been moved in the document from one location to another. Yet another may be defined to encode the equivalence between two SGML elements where one is a copy of the other as described in section .
 The change types that constitute a temporal document must fulfil two requirements: reversibility and independence from any information in previous descriptions. Only if changes are reversible, previous states of the document can be reconstructed from its final state by performing the inverted changes of its history in reverse order. The independence of the change descriptions from any other description is required, because computing an SGMLdiff requires a reordering and manipulation of the changes in the document's history (see ). This reordering is omly allowed if two adjacent changes in the history can be analysed and manipulated locally without any side-effects on some other change description.
 As a consequence, each change description must describe the component
  NOTE:
 Or the location, in case the change describes an insertion.
 that will be changed, relative to the document state just before that change.
 

Creating temporal documents

 As discussed in , the equivalence of objects in the documents to be compared cannot be determined by simply analysing their states. In contrast to state-oriented document models, temporal documents provide this information by descriptions of every change made to the document, particularly whether elements have been moved. Temporal documents must therefore reflect the authentic creation process of the actual document state. This can only be achieved if the used editing system protocols all editing steps actually made by the author. In addition, in order to record a useful change history of the document, the author must always use the `move' operation provided by the editing system if she actually intends to move an element. If she manually inserts an element with the same contents at the new location and then deletes the old one, the system cannot detect the `moving' of the element.
 If no special editing system was used and a correct tracking of equivalent elements is not a critical requirement, a temporal document may also be computed from the actual state of a document. The temporal document then contains one change of type `insert' for each component of the document's contents.
 

Using temporal documents to build an SGMLdiff

 
 

Computing the difference between two temporal documents

 Temporal documents describe the evolution of their contents in an already meaningful notation. Besides, their change history is invertible, and their change history always begins with an empty document state. Therefore the difference between two temporal documents can in theory be described as the sequence of changes that would delete the first document completely, followed by all changes needed to create the second. However, as a document's history may contain as much changes as there are objects in the actual document state
  NOTE:
 At least one change of type `insert' per component is needed to generate the actual state of the document.
 or more, such a delta would be much too long and of no practical use.
 Nevertheless, such a sequence of changes contains all the information necessary for a sensible delta. What is still needed is a way to remove all irrelevant changes. With the techniques of merging and rearranging change sequences discussed in the next subsections it is possible to reduce such a delta to its minimal length, i.e. to the minimal number of changes needed to produce the second document if performed on the first one – in other words the result that an SGMLdiff shall produce.
 The technique to reduce a change history to its minimal length not only is needed in the context of producing an SGMLdiff . It may also be used to reduce the length of a recorded editing session and thus the length of the temporal document which could otherwise get very big .
 
 

Merging changes

 An author editing a document often has to correct typing mistakes or to reformulate what she just wrote. Therefore, if every editing step is recorded in a temporal document, some changes may be followed by others that are inverse to them. Such groups of changes that are inverse to each other do not describe any useful information about the evolution of the document. Because of the required independence of changes they may be removed from the temporal document without any side-effects to other parts of the change history.
 There are other cases where two consecutive changes can be merged: if a component has been inserted and immediately afterwards modified, it may just as well have been inserted in its modified state – the two changes can be replaced by only one. Similarly, modifying or moving a document object in two successive steps can be replaced by one single change describing the entire modification or movement. The same holds for modifying an object that gets deleted afterwards: the two changes can be summarized in one that deletes the unmodified object.
 
 

Rearranging changes

 With merging, only two consecutive changes can be removed from a change sequence or replaced by a new change describing the same effect on the document. However, this situation will be found only in rare cases. Usually, two changes in the change history that affect the same object and that could be merged if next to each other are separated by some other changes. To merge them, the change history must be rearranged in such a way.
 The way to move a change in a history is to transpose it with its neighbour as often as needed to get it into the right place , . Transposing two consecutive changes in a history alters their order of execution. Obviously, not every pair of consecutive changes may be transposed. If the first change creates an element that is filled with some text by the following change, reversing the order of execution does not make sense. Nor is it possible to attach an attribute to a non-existing element.
 The transposition technique first requires a list of all the conditions that changes must fulfil to be commutative. The second task is to determine the effects of transposing commutative changes. Transposing two changes may require that the references they contain have to be modified, because these references depend on the document state affected by the change. A suitable and universal method to locate nodes in a tree is defined by the HyTimetreeloc architectural form that basically references nodes by their path in the document tree
  NOTE:
 A path `(1 3 2)' for example references `the second child of the third child of the root'.
 . So if a node is inserted by a change A, some paths in the following change B may have to be altered during transposition: after exchanging them, change B applies to the document state that existed before change A. And change A now applies to a document state that has already been modified by change B.
 

Reducing change histories

 The algorithm to reduce arbitrary change histories to their minimal length is based on
 
  1. rearranging the order of execution in the history to get pairs of adjacent changes and
  2. merging these changes, i.e. deleting them if they are inverse to each other or replacing them by a single change that describes the same effect.
 A change history has been successfully reduced to its minimal length if no change is left that – by repeated transpositions – may be moved next to a change with which it can merge.
 One possible way to reduce a change history is to shift every change – starting at the end of the history – as far to the beginning as possible. The shifting ends either if the change cannot transpose with its new predecessor or if they merge.
 If the logical order of dependency that determines the rules of transposition is transitive, and if merging some changes does not influence this order
  NOTE:
 The order may be affected if the merging produces a new change for which other dependencies are defined as for the merged changes.
 , the history can be reduced just by analysing each change in the way described above. On the other hand, if the merging of changes produces a new dependency order, the algorithm must be refined as follows.
 If the shifted change does not merge with its new neighbour, both are connected to each other by references that document their logical dependency. If no merging is possible at all, the algorithm has provided each change with references to all those previous and subsequent changes with which it cannot transpose.
 If the changes merge, the ordering may have become locally invalid. Therefore all changes previously referenced as logically required (respectively depending) have to find their new `partners' by a repeated shifting to the beginning (respectively to the end) of the history until no further transposition is possible or until they merge.
 

A simple SGMLdiff

 
 

A simplified SGML document model

 The approach described above to build an SGMLdiff has been implemented as part of a prototype system that demonstrates the feasibility of document engineering based on the concept of temporal documents . Up to now four types of document objects are supported by the prototype:elements ,attributes , HyTimepseudo-elements – in the following also calleddata objects , and(hypertext) links encoded as HyTime `ilinks' . Other types like e.g. `entities' may be added.
 The prototype only handles document instances; it even totally ignores any information contained in the corresponding DTD
  NOTE:
 Therefore in the following the term `document' will be used in the sense of `state of an SGML document instance'.
 . This design decision has been made as DTDs should be designed to define the same structure for a large number of documents that may have to be compared to each other on their own without reference to the DTD they all comply to.
 SGML elements are regarded as labelled nodes in a hierarchical document tree. Each element carries information about its position in the tree (thereby defining the extent of the tagged textual contents) and its generic identifier.
 Pseudo-elements are the leaves of the document tree that contain only sequences of characters. In the prototype, entity references or the difference between e.g.CDATA and#PCDATA are ignored. Pseudo-elements carry information about their data content and their position in the tree (and thereby in the data stream of the document).
 The location of elements or pseudo-elements is described by a combination of a HyTime `treeloc' expression – identifying the node in the document tree – and the unambiguous name of the document encoded as a HyTime `nameloc' expression .
 Attributes contain additional information – the named attribute's value – assigned to an element and identified by combining the identifier of the element with its unambiguous attribute name. Using the DSSSL terminology, a document with attributes thus forms a grove rather than a tree.
 Finally, links are stand-alone information units that describe hypertext links from a referenced source element to a specified destination element. Links are represented as HyTime `ilinks' with a unique link name
  NOTE:
 The link name must be unique in the scope of a document's state.
 . Nevertheless an additional identifier is needed for a link since its name can change during the document's evolution and since this link may be referenced from another document yet unaware of the name modification. In the prototype, this ID reflects the time of creation of the link.
 

Types of changes

 The following list discusses each of the 15 change types implemented in the prototype. The examples use the SGML notation for change histories defined in . Each change type is denoted by an empty element with several attributes. The meaning of the attributes is explained in the description part of the element types.
 
  • Insert ,Delete ,Modify Element . Elements having children cannot be deleted, nor canInsert Element be used to wrap existing elements or data objects. To modify an element means to change its generic identifier (gi). 
    • <ie p="(1 4 3 5 1)" gi="information"  > ... <me p="(1 4 3 3 1)" ogi="information" ngi="warning"  > ... <de p="(1 5 3 3 1)" gi="warning">
     
  • Split ,Join Data . Before inserting an element within a pseudo-element (`mixed content'), the latter must be split into two parts. Conversely, after deleting an element surrounded by data, the remaining two adjacent pseudo-elements have to be joined to form a single data node in the document tree. To describe this change completely the length (l1, l2) of each fragment must be given next to its path (p1, p2). 
    • <join p1="(1 4 5 3 1)" l1="40" p2="(1 4 5 3 2)" l2="30"> ... <split p1="(1 4 3 3 1)" l1="6" p2="(1 4 3 3 2)" l2="63">
     
  • Insert ,Delete Data . In contrast to elements, the contents of a data object cannot be modified, as pseudo-elements may lose their identity in the document tree when split or joined. 
    • <id p="(1 4 3 5 1 1 1)">CONF:CR, OPSTAT=INACT;</id> ... <dd p="(1 4 5 7 2 1 1)">CONF:CR, OPSTAT=INACT;</dd>
     
  • Insert ,Delete ,Modify Attribute . As each change description must be invertible, aModify Attribute must not only contain the new name and value (nan, nav), but also their old values (oan, oav). NOTE: The same holds for the generic identifier inModify Element as illustrated in the example above. 
    • <ia p="(1 1 4 1 1)" an="entity" av="tab-4.2.gif"> ... <ma p="(1 10 4 4 2)" oan="entity" nan="entity"      oav="tab-4.2.gif" nav="tab-4.1.gif"> ... <da p="(1 8 4 10 1)" an="entity" av="tab-4.1.gif">
     
  • Insert ,Delete ,Modify Link . If a link is created, the information about this change is documented in all affected documents, i.e. in the documents which contain the source (lsd), the destination (ldd), and the link itself (ld). The link is referenced by its name (ln) and its time of creation (lt). A link must be modified if e.g. a path to one of the referenced elements (lsp, ldp) has changed in a different document than the one which contains the link. 
    • <il ld="linkbase.sgml"      lt="(12923 53988 40215)" ln="Mark2Tabchap4-1"      lsd="ewsd.sgml" lsp= "(1 8 4 4 6 2 4 2 2)"      ldd="d900.sgml" ldp="(1 10 4)"> ... <ml ld="linkbase.sgml" lt="(12923 53988 40215)"      oln="Mark2Tabchap4-1" nln="Mark2Tabchap4-1"      olsd="ewsd.sgml" olsp= "(1 8 4 4 6 2 4 2 2)"      nlsd="ewsd.sgml" nlsp= "(1 8 4 4 6 2 10 2 2)"      oldd="d900.sgml" oldp="(1 10 4)"     nldd="d900.sgml" nldp="(1 10 4)"> ... <dl ld="linkbase.sgml"      lt="(12923 53988 40215)" ln="SeeTabChap4-1"     lsd="ewsd.sgml" lsp= "(1 5 3 4 9 2 2 2 2)"        ldd="d900.sgml" ldp="(1 5 4)">
     
  • Equal ,Diff . A change of typeEqual documents an equivalence relation between the element that it applies to and another one that has also been `touched' by anEqual with the same ID (t).Equal does not actually change the document state, it only freezes the element touched (with path p in the document d) in its actual state. Finally,Diff is needed as the inverse type ofEqual . 
    • <equal t="(12090 33686 399015)" p="(1 4 3)" d="ewsd.sgml"> ... <diff t="(12090 33686 399015)" p="(1 4 5)" d="ewsd.sgml">
     
  • This change type is used for three complex changes:Copy ,Move , andFreeze (as a version). Copying an element is actually a sequence of elementary changes: first, the element is copied in a buffer (documented by anEqual ), then the copy is inserted at the intended location, possibly after some other changes have been executed in between. Because changes have to be independent of any information connected to previous changes (see ), the copy cannot be inserteden bloc . Instead, each single step that built up the first element must also be performed to build up the copy. Only then, a secondEqual applied to the new copy documents the equivalence between both elements. Moving an element is documented in much the same way, only followed by a sequence of changes that delete the copied element. The third usage forEqual is to freeze an element (usually the root element) in its actual state and give this new version a name. A change of typeDiff can later be used to delete this version.
    •  The change types described above fulfil the requirement of invertibility: anInsert is the inverse of aDelete , inverting aModify implies exchanging the old and the new values,Diff is the opposite ofEqual , and a change of typeSplit may be used to eliminate the effect of aJoin . The inverse of asequence of changes is obtained by aligning the inverse of each change in reverse order.
     
     

    Rules for merging changes

     Section already described most of the rules for merging adjacent changes implemented in the prototype. As an example, consider the following situation. First an element `information' is inserted as the second child of an element with the path `(1 3 2)'. Thereafter its generic identifier is changed into `warning':
    ... <ie p="(1 3 2 1)" gi="information"> <me p="(1 3 2 1)" ogi="information" ngi="warning"> ...
     The single change<ie p="(1 3 2 1)" gi="warning"> describes the same effect. It can replace the two changes above, because any other change of the history is independent of them (as required in section ) and because the states of the document before and after them remain the same, so that all references in subsequent changes are not affected by an exchange.
     In addition to the general rule that inverse changes may be taken out of the history, other merging rules hold for changes likeJoin ,Split , orEqual . For example. it is useless to freeze an element twice with two changes of typeEqual that use the same name; freezing it once has the same effect.
     Changes of typeSplit (Join ) produce (require) a document state with two adjacent data objects, a situation that is in conflict to the HyTime definition of a pseudo-element. However, in some cases these changes are needed to prepare (finish) a subsequent (previous) change. The following merging rules involvingthree consecutive changes reflect this close relationship between aSplit orJoin and some connected change:
     
  • Inserting two data objects that are joined in a third step like in 
    <id p="(1 4 3 5 1)">CONF:CR, </id> <id p="(1 4 3 5 2)">OPSTAT=INACT;</id> <join p1="(1 4 3 5 1)" l1="9" p2="(1 4 3 5 2)" l2="13">
    is the same as inserting the concatenated string in one single change:
    <id p="(1 4 3 5 1)">CONF:CR, OPSTAT=INACT;</id>
    •  
  • Similarly, splitting a data object in two parts that are deleted afterwards 
    <split p1="(1 4 3 5 1)" l1="9" p2="(1 4 3 5 2)" l2="13"> <dd p="(1 4 3 5 1)">CONF:CR, </dd> <dd p="(1 4 3 5 1)">OPSTAT=INACT;</dd>
    is the same as deleting it in only one step:
    <dd p="(1 4 3 5 1)">CONF:CR, OPSTAT=INACT;</id>
    •  
     

    Rules for transposing changes

     As discussed in , not every tuple of changes may be transposed. In the prototype, a logical dependency between two changes is given if the second change in a particular document state `touches' an object or a location, that is the result of the first change. An example for this is an element that is first inserted and then deleted.
     Less intuitive is the situation where the first change deletes an element and thereby `creates' a `location' which is then touched by the second change that inserts an object at exactly the same place. In this situation, it is not possible to transpose the changes in an unambiguous way: no information is given to determine if the object that is deleted after the insertion shall be a righthand or a lefthand neighbour of the object that has been created first.
     If two changes are not logically dependent they can be transposed. To do so, all references in the changes must be appropriately adjusted as in the following example. Transposing 
    <de p="(1 4 3 5 2)" gi="notice"> <dd p="(1 4 3 5 1)">OPSTAT=INACT;</dd>
    results in
    <dd p="(1 4 3 5 1)">OPSTAT=INACT;</dd> <de p="(1 4 3 5 1)" gi="notice">
     There are special rules for transposing changes of typeSplit andJoin , because they also specify the length of the fragments involved. For example, a succeedingSplit depends logically on a preceedingJoin only if the string shall be split at the same point where it has been joined before, i.e. if they are inverse to each other. If not, they may very well be transposed, as a closer look at the next example shows: 
    ... <id p="(1 4 3 5 1)">CONF:CR, </id> <id p="(1 4 3 5 2)">OPSTAT=INACT;</id> <join p1="(1 4 3 5 1)" l1="9" p2="(1 4 3 5 2)" l2="13"> <split p1="(1 4 3 5 1)" l1="16" p2="(1 4 3 5 2)" l2="6"> <dd p="(1 4 3 5 1)">CONF:CR, OPSTAT=</dd> <dd p="(1 4 3 5 1)">INACT;</dd> ...
    Transposing the third and fourth change results in:
    ... <id p="(1 4 3 5 1)">CONF:CR, </id> <id p="(1 4 3 5 2)">OPSTAT=INACT;</id> <split p1="(1 4 3 5 2)" l1="7" p2="(1 4 3 5 3)" l2="6"> <join p1="(1 4 3 5 1)" l1="9" p2="(1 4 3 5 2)" l2="7"> <dd p="(1 4 3 5 1)">CONF:CR, OPSTAT=</dd> <dd p="(1 4 3 5 1)">INACT;</dd> ...
    Finally, if an element's state is fixed by a change of typeEqual , no change that affects this state can be transposed with theEqual . Consider e.g. anEqual that freezes the root element followed by a change that inserts a new child of the root. If these changes are transposed, the child would be inserted first and then a new anddifferent state of the root would be fixed.
     
     

    Generating the delta

     Given two temporal documents, the SGMLdiff is basically computed as described in section . First, the change history of the first document is inverted. Then the history of the second document is appended to it, resulting in a long change history that transforms the last state of the first document into the final state of the second. This delta history is then reduced to its minimal length. In a first step though, all existing pairs of inverse changes with typeEqual andDiff are taken out of the delta, as it is usually not possible to bring them next to each other by repeated transpositions. Afterwards the delta is reduced following the algorithm described in .
     

    Summary and future work

     This contribution has presented an approach to build an SGMLdiff . It is based on a change-oriented model for structured documents. Contrary to the traditional approach of storing thestate of a document, temporal documents contain achange history that describes how to create the actual document state out of an initially empty state.
     The basic idea for building an SGMLdiff is to use the information already contained in temporal documents. To compute a meaningful delta, first a long delta history is created by concatenating the inverted change history of the first document – resulting in the empty state – and the history of the second document – starting with the empty state. This delta history then is reduced to a minimal length by merging subsequent changes that are brought together by repeated transpositions.
     The feasibility of the proposed method has been demonstrated by a prototype based on a very simple model for structured documents that defines the types `element', `attribute', `pseudo-element', and `link' for the objects forming a document state. Though the prototype does not support the full complexity of the SGML document model, the method described is not restricted to the object types chosen for the prototype. New object types may be added together with appropriate change types. These new change types must be invertible, and conditions and rules have to be defined that describe their merging and transposing with consecutive changes.
     Finally, the delta obtained by such an SGMLdiff must be visualized. Just listing the sequence of change descriptions in some particular notation is not the appropriate way. One possibility (realized in ) is to display two states of the document for comparison that may be randomly chosen from the delta. As the change history between the displayed states contains all necessary information about the evolution of each object in the document, the differences between the two states can be visualized as desired.
     

    BIBLIOGRAPHY

     
  • [BCD95] Barnard, D.T., Clarke, G., Duncan, N.Tree-to-tree Correction for Document Trees. Technical Report 95-372, Dep. of Computing and Information Science, Queen's University, Kingston, Ontario, Canada (1/1995), http:// www.qucis.queensu.ca/ TechReports/ Reports/ 95-372.ps.
    •  
  • [DD94] S. J. DeRose, D. G. Durand.Making Hypermedia Work – A User's Guide to HyTime Kluwer Academic Publishers (1994).
    •  
  • [Dur94] D. G. Durand.Palimpsest: A Data Model for Revision Control. Proc. of the CSCW 94 Workshop on Collaborative Hypermedia Systems, GMD, (1994) GMD Studien Nr. 239.
    •  
  • [ISO96] DIS 10179: Information technology – Text and office systems – Document Style Semantics and Specifikation Language (DSSSL) , ISO/IEC (1996).
    •  
  • [RTW96] D. Raymond, F. Tompa, D. Wood.From data representation to data model: Meta-semantic issues in the evolution of SGML. Computer Standars & Interfaces 18 (1996) 25-36.
    •  
  • [Mφl97] H. Mφller.Konsistentes Dokumentenengineering mit temporalen Dokumenten. PhD-Thesis (1997), forthcoming.
    •  
  • [PKa92] A. Prakash, M.J. Knister.Undoing Actions in Collaborative Work. Proc. CSCW 92, ACM (1992).
    •  
  • [PKb92] A. Prakash, M.J. Knister.Undoing Actions in Collaborative Work. Report CSE-TR-125-92, Dep. of Electr. Engin. and Comp. Sci., Univ. of Michigan (1992).
    • PDoS - Pinnacles DSSSL-O Stylesheet   Table of contents   Indexes   Introducing SGML into the RAF Flight Manuals World or Throttle to Bottle in Two Extraordinary Years