Balisage Paper: Stand-alone Encoding of Document History

Introduction

XML being recognized today as the lingua franca of computerized information, some key basic functionalities become of universal interest and will predictably gain momentum in the upcoming XML related economy.

One of these functionalities is the computation of differences between two XML documents, and more generally, the management of the history of a given document. In particular, this functions as a cornerstone of any system aiming at offering long term preservation.

Today, such functionality is achieved through content management systems or databases. Models and operations are therefore hidden inside a black box, and up to the author's knowledge, no standard mechanism makes this information explicit and accessible to human users neither to external algorithms and processors.

Our proposal addresses this issue by associating a target document instance together with its history inside a standalone and consistent document, thus gaining strong potential for current or future interoperability.

The notion of history, when applied to a document, calls for a deeper understanding of the global context, intents and social processes underpinning the creation, evolution and maintenance of documents (see pédauque03). Hence, the relevant structure of a meaningful document history highly depends on the document typology and usages.

In addition, the criterion that founds any document history is the permanence of some key deep invariants (for a general, ontological, reflection around this line, see pédauque05). Those invariants define the identity of the document itself and their loss inevitably ends the versioning process and calls for a new creation cycle.

The method we describe in this paper takes into consideration the key points above, especially through a flexible calculus of difference descriptors, and through offering high level transformation operations that preserve the consistency of both the document instance and its whole history.

Overview

The target document (also called body hereafter), i.e. any XML document using any namespace, is encapsulated inside a dedicated packaging XML document. The body always consistently relates to a given state of its history (not necessarily the most recent one) thanks to a dedicated attribute that refers to a version label and makes this relation explicit.

The history itself is encoded as interrelated nodes (XML elements) and has the structure of a directed acyclic graph (DAG); each node of this graph models a versioning point, i.e. a particular significant state that the document reached during its lifetime and for which a version has been recorded. The meaning of any versioning point with respect to the document life cycle is application dependent, as discussed above, and the proposed approach abstracts over application semantics, just considering that a new version is built when some actor in the document life cycle decided it makes sense to do so. Arcs that connect the nodes are decorated with deltas, and these arcs model the transformation that allows changing the document from one versioning point to the other. Thus arcs are oriented. Deltas descriptors are combinations of low level operations on the document tree, mainly based on deletion and insertion of subtrees.

Thanks to a set of transformations qualitatively described in this paper, it is possible to navigate inside the history of the document and to consistently extract any version of the document captured in the history graph. It is also possible to create new versioning points, new branches or to merge existing branches, all these operations producing novel consistent encapsulations of the target document.

Modelling Abstract Differencing Operations

Fundamental Operations over Encapsulated Documents

Encoding Graphs of Deltas in XML

Each versioning point is captured using a dedicated element (e.g. version) associated with an id attribute that uniquely identifies it. Our convention uses a naming scheme of the form v0… v3 for instance. Names for diverging branches use a dot, e.g. v1.1, v1.2.

Each version element contains a sequence of delta elements which capture the transition from this versioning point to another versioning point. This information is conveyed by an attribute (e.g. fwd for forward links and bwd for backward links). Moreover, a delta contains a non order-significant sequence of delta operations, which captures the so-called snapshot. Several delta elements are interpreted as sequences of snapshots (corresponds to the Δ₁ ; Δ₂ syntactic form, where Δ_i= {…}).

Each delta operation is described using a dedicated element name according to its semantics (insert, insert-attr …). The path information may be concisely encoded, e.g. through an “ipath” attribute. Copies of subtrees may be expressed through a “copy” attribute attached to the delta element. When such an attribute is not defined, an extensive definition of the subtree is expected as the content of the operation.

The example 1 below is a target document we want to track

        <html xmlns="http://www.w3c.org/1999/xhtml">
            <!-- XHTML 1.0 -->
            <head>
                <title>New Testament (Matthew, chapter 2)</title>
            </head>
            <body>
                <p class="verse" number="1">
                Now when Jesus was born in Bethlehem of Judaea in the days of Herod the king,
                behold, there came wise men from the east to Jerusalem,
                </p>
            </body>
        </html>
           

After applying the create-history operation, the document of figure Figure 27 below is created.

      <x-version id="xhtml-1.0" xmlns="XEROX::XRCE::DS:X-Version">
        <x-body version=”v0”>
            <html xmlns="http://www.w3c.org/1999/xhtml">
            <!-- XHTML 1.0 -->
            <head>
                <title>New Testament (Matthew, chapter 2)</title>
            </head>
            <body>
                <p class="verse" number="1">
                Now when Jesus was born in Bethlehem of Judaea in the days of Herod the king,
                behold, there came wise men from the east to Jerusalem,
                </p>                
            </body>
            </html>
         </x-body>
       <x-history >
         <version id=”v0”/>
       </x-history>
     </x-version>

            

In the following example, we assume three distinct versioning points have been created.

                <x-version id="xhtml-1.0" xmlns="XEROX::XRCE::DS:X-Version">
                    <x-body version=”v1”>
                        <html xmlns="http://www.w3c.org/1999/xhtml">
                            <!-- XHTML 1.0 -->
                            <head>
                                <title>New Testament (Matthew, chapter 2)</title>
                            </head>
                            <body>
                                <p class="verse" number="1">
                                Now when Jesus was born in Bethlehem of Judaea in the days of Herod the king,
                                behold, there came wise men from the east to Jerusalem,
                                </p>
                                <p class="verse" number="2">
                                Saying, Where is he that is born King of the Jews? For we have seen his star in 
                                the east, and are come to worship him.
                                </p>
                            </body>
                        </html>
                    </x-body>
                    <x-history start=”v0” end=”v2”>
                        <version id=”v0” />
                        <version id=”v1”>
                            <delta bwd=”v0”>
                                <delete ipath=”1/2/2”/>
                            </delta >
                            <delta fwd=”v2”>
                                <insert ipath=”1/2/3”>
                                    <p class="verse" number="3">
                                    When Herod the king had heard these things, he was troubled, and all 
                                    Jerusalem with him.
                                    </p>
                                </insert >
                            </delta >
                        </version >
                        <version id=”v2” />
                    </x-history>
                </x-version>
                
            

The following example illustrate how the same information can be encoded differently, featuring different properties.

    <x-version id="xhtml-1.0" xmlns="XEROX::XRCE::DS:X-Version">
        <x-body version=”v1”>
            <html xmlns="http://www.w3c.org/1999/xhtml">
            <!-- XHTML 1.0 -->
            <head>
                <title>New Testament (Matthew, chapter 2)</title>
            </head>
            <body>
                <p class="verse" number="1">
                Now when Jesus was born in Bethlehem of Judaea in the days of Herod the king,
                behold, there came wise men from the east to Jerusalem,
                </p>
                <p class="verse" number="2">
                Saying, Where is he that is born King of the Jews? For we have seen his star in 
                the east, and are come to worship him.
                </p>
            </body>
            </html>
        </x-body>
        <x-history start=”v0” end=”v2”>
            <version id=”v0” >
                <delta fwd=”v1”>
                    <insert ipath=”1/2/2”>
                    <p class="verse" number="2">
                    Saying, Where is he that is born King of the Jews? For we have seen his star in 
                    the east, and are come to worship him.
                    </p>
                    </insert >
                </delta >
            </version >
            <version id=”v1”>
                <delta fwd=”v2”>
                    <insert ipath=”1/2/3”>
                        <p class="verse" number="3">
                        When Herod the king had heard these things, he was troubled, and all 
                        Jerusalem with him.
                        </p>
                    </insert >
                </delta >
            </version >
            <version id=”v2” />
        </x-history>
    </x-version>                

            

We propose a particular optimisation that could be applied in linear mode: redundant trees are eliminated tanks to an explicit copy instruction using an XPath expression to designate the subtree (thus the XPath selection refers to the focused version).

                <delta fwd="v1">
                    <insert ipath=”1/2/2”>
                        <p class="verse" number="2">
                        Saying, Where is he that is born King of the Jews? For we have seen his star 
                        in the east, and are come to worship him.
                        </p>
                    </insert >                
                </delta>                 
            

                <delta fwd="v1">
                    <insert ipath=”1/2/2” copy=”/html[1]/body[1]/p[2]”/>    
                </delta>                 
            

This optimization applies only to versions belonging to past history, but makes a lot of sense when the evolution of document instances is best captured through using linear mode and comprises many incremental additions.

State of the Art

XML diff operations are basically used to realize two fundamental operations on tree structured documents: comparison and merging. Therefore tree based diff algorithms are central to solve various important problems related to XML document management and editing processes (Chawathe96), among which:

An abundant literature exists on this topic, including recent and excellent synthetic work on an old topic, linear differencing (Khanna07). Most work covers :

A recent paper Rönnau08 proposes reversible deltas using a straightforward mechanism as deletion operation conveys explicitly the deleted subtree (this could quickly lead to enormous overhead, especially in the perspective of storing the whole history). The authors focus on algorithmic and speed performance issues of a novel diff algorithm using a bottom-up approach (and also precomputed hash codes on a sliding window of adjacent nodes.)

Most work conducted on this area focused on related algorithm performance, time and space complexity of the diff operation and also optimality of generated deltas, but little attention has been paid to tools and models to make use of these in efficient ways. From the practical point of view, no work considered the necessity and applicative interest of abstracting over deltas and related operation models.

Recently, the XQuery Update working group from W3C (see XQueryUp) published a candidate recommendation proposing to enrich XQuery with mechanisms intended to modify XML documents. This impressive work largely focused on expressive power and consistent integration of the new constructs to the existing language. The patching operations rely on "insert", "delete", "rename" and "replace" , using XPath to designate the locations in the XML tree ; an innovative "transform" operator allows for combining copy with on-the-fly modifications. One major difficulty was to deal with the extra power raised by the selection semantic model of XPath, i.e sequences of nodes. As a consequence, many runtime error may occur depending on the evaluation of selectors and the semantics of the delta operation. Additionally the insert operator of the language is particularly powerful since it can make explicit positional constraints ("first/last position", "before/after A") whereas when implicit, positional constraints are interpreted so that global ordering constraint are optimally satisfied (this remain a bit unclear how far this can be hard).

The transformation model of XQUpdate relies on a kind of transactional framework, where changes are stored in a list of "pending modifications" only applied after calling a dedicated primitive upd:applyUpdates. This is a pragmatic solution to the problem of path relocation (and variable scope validity!), but is a nightmare regarding static analysis. Therefore it will be much more realistic to use the XQUpdate interpreter as a patch engine (i.e generating XQUpdate code from our descriptions), than considering an XQUpdate program as a description of differences.

Conclusion

The main contribution of this work is to propose a universal XML data structure and related transformations which allow abstracting from underlying storage systems and from any execution model associated with the computation of XML versioning information.

This is in favor of long term preservation of XML documents, infrastructure and vendor independence, and open the way to interoperable processing of XML versioning information.

The method targets generic XML documents, and makes use of a particular namespace to embed any XML document (whatever vocabulary it may use) without any change in its content and tag/attribute set. The history is encoded using a specific vocabulary that captures change operations in a formal and universal way, so that any XML diff enabled processor can generate suitable deltas. Based on the properties of this change description language, we propose a set of high level operators which allows exploiting the historical information in order to navigate inside the history, compute new version in the current branch, create new branches or suppress intermediate versioning points.

Various information may be attached to the versioning points, such as user meta information, universal date/time of the creation of the versioning point, additional data required to optimize or ameliorate the computation (hash code, digest number,...), which are not central to this contribution but could substantially enhance any of its application.

The problem with existing diff related approaches is that the description model and the transformation model are identical. In other words, they use the same objects both to describe operationally and declaratively the differences between trees. We outline in our proposal a calculus that formally allows making a distinction between modification descriptors and modification operations. This calculus allows modeling "standard" processing of deltas and allows transforming descriptions in order to gain compactness or efficiency. We are not aware of any equivalent proposal.

The two transformation structures we described can lead to two broad classes of delta interpretations:

The delta model we propose as foundational for history encoding integrates those two transformation models, in the sense that both can be expressed explicitly. The first one is captured by sequences of singleton snapshots whereas the second may involve snapshots including several deltas.

We identified 4 key issues when addressing the challenge of encapsulating document history into a stand alone XML instance: mastering the potentially big data volume, usability of the history model (human vs machine), flexibility of the history representation and abstracting over diff operations (i.e. not being dependent of a particular diff algorithm/engine behavior). The method described in this paper addresses these four issues at various levels. We believe our approach therefore constitutes a significant contribution having a realistic applicability level, though the data volume issue would still require large scale experiments.

Acknowledgment

This work is supported by the European project SHAMAN (FP7- ICT-216736, http://shaman-ip.eu/shaman/ ). The author also would like to thanks Jean-Pierre Chanod for his continuous support and helpful comments