A Generalized Grammar for Three-way XML Synchronization

Table of Contents

In this scenario, we can consider A, B and C as three documents as follows: A is a base file and B and C are two derivatives, each edited in a different way. Our task is then to generate a synchronized document where any common edits are propagated, because there is no conflict. This would typically be defined loosely in a rule set as follows:

In this scenario, we have an original English document and a translation into Japanese, and an updated English document. These relate as follows: A is the base file, i.e. the original English, B is the translation of this file, with the same structure but different text, and C is the modified English document.

Our task is then to generate a synchronized document which will be a template for the revised translated document. This means that only those parts of the document that have been changed need to be re-translated. In this result file, any unchanged English is represented as the unchanged translation. For changed text we need the details of the changes in the result file so that the translation can be manually updated. This would typically be defined loosely in a rule set as follows:

This translation problem is more fully described in [BABEL]. This introduces the concept of a 'unit of translation' which is an element that we treat as a whole and do not sub-divide. For example, a paragraph is a unit of translation and we do not track changes below this level - this is simply because trying to automate word-by-word translation is unlikely to result in anything useful. A translator would rather work at the paragraph level.

What Combinations of Elements are Possible?

We can see that a pattern is emerging as we look at the different applications and how they resolve the different situations. The first step to formalizing this is to enumerate all the possible situations. Then we can review how these can be handled.

Given three initial data sets, A, B and C, we have the following possible combinations to describe whether an element is present in each of the data sets:

This is a total of seven combinations. But we need to go one step further because the informal rules above also consider whether, for a given combination, the data is the same in all the files or not. In other words, if an element is present we need to know if it is unchanged or changed in the different data sets. This clearly does not apply if there is only one element present, so there are only another seven combinations. This gives us a combination set as follows:

When we say, for example, we have an element with a 'version set' of [A, B] and that A == B, we mean that the subtree corresponding to the A input is (deep)equal to the subtree corresponding to the B input. Another way of looking at this is that the subtree corresponding to this element and all nodes underneath it also have a version set of [A, B].

We have introduced a set of 'patterns' or 'matches' which describes all possible combinations of inputs. Each node in the input tree must correspond to one of the patterns above. However, we need to define how the synchronization result is produced. Our technique is to define a number of actions that can be performed when each of the patterns is matched. At this point we will also introduce fragments of our syntax used to represent the patterns described above.

For the first three simple patterns, [A], [B] or [C], the actions which can be performed are very simple. It is possible to either include or exclude the appropriate subtree in the result at that point. More generally, it is also possible to include the current element we are considering and then recurse and apply rules to all the child nodes (elements, attributes etc.) at this point. In this case ([A], [B] or [C]), as there is only a simple single-input subtree it may seem that there is little difference between recursion and subtree inclusion. However, other examples will demonstrate more obvious uses of recursion and we will also see how recursion will be useful when controlling the 'granularity' of synchronization.

For the pattern [A], [B] or [C], given that our version set corresponds to a single input tree, there is only one subtree which can be included when one of these three patterns match. Our pattern and action grammar will therefore follow the following form, described here for pattern [A]:

<versionset-a>
  <a-subtree include="yes"/>
  <include-and-recurse include="no"/>
</versionset-a>

The a-subtree element indicates whether or not to include the subtree from the A data set, according to the value of the include attribute. The include-and-recurse element indicates whether or not we are to include this element and then recurse through its children.

We can now consider the six patterns with two input version sets. There are three patterns where the descendent subtrees are not equal, for example for an element with versionset [A, B] we also have A != B (subtree inequality). In this case we could include the subtree corresponding to the A input, and/or that corresponding to the B input. Our final option is to include the currently matched element and apply rules to the child nodes. An example of the patterns is shown below:

<versionset-ab-a-ne-b>
  <a-subtree include="yes"/>
  <b-subtree include="no"/>
  <include-and-recurse include="no"/>
</versionset-ab-a-ne-b>

There are three other patterns for the two element version sets, the cases with subtree equality. In these cases, choosing the a-subtree is no different from the b-subtree (because they are equal) and so we merge these possible actions into one:

<versionset-ab-a-eq-b>
  <ab-subtree include="yes"/>
  <include-and-recurse include="no"/>
</versionset-ab-a-ne-b>

For the three element version set there are five combinations of subtree equality/inequality we need to consider. The form of these follows those introduced previously with actions for subtree inclusion and recursion. To save space we have not included examples here, instead please consult the DTD or complete examples included in Section 4.1, “Rule Set DTD”.

Note that the above list is not mutually exclusive, we can conceive of cases where including both subtrees is a possibility, and perhaps they would both appear in sequence in the result. In this case it may be useful to distinguish the two included subtrees, perhaps using comments or 'wrapper elements'. These possibilities will be discussed later, in Section 5.3, “Synchronization Annotations”.

Consider the following example of element content:

A:   <x><a/></x>
B:   <x><a/><b/></x>
C:   <x><a/><c/></x>

The a child element is consistent through all three inputs (and therefore has versionset [A, B, C]). However, in two of the inputs something 'different' has happened. In some synchronization scenarios this could be regarded as a conflict - the second child of x is different. However, consider the case where the b and c are for example Docbook elements. One author may have tried to expand/clarify a topic by adding a diagram, the other by adding a paragraph of explanatory text. In this scenario these are two distinct additions, both equally valid; it seems sensible that the result should be: <x><a/><b/><c/></x>.

If we say the addition of distinct elements is not a conflict, is it possible to have an element conflict? Perhaps, if the same element is added but with different content:

A:   <x><a/></x>
B:   <x><a/><y><y1/></y></x>
C:   <x><a/><y><y2/></y></x>

Here we could say two conflicting y elements have been added. But we decided not to take this approach. The element y is common to both B and C input trees, and therefore has a version set of [B, C]. In the merged or unified tree the y element has two children: a y1 with versionset [B] and a y2 with versionset [C]. We can recurse into the children and apply rules to process them at that level of the tree. The same is true even if element y contained PCDATA, although it is more complex to represent this because we need to wrap the two distinct PCDATA strings.

Recursion is often the preferred option and should be applied where possible/appropriate in order to report changes and/or conflicts at the finest granularity. In an extreme case, given the first Axiom, it would be generally unhelpful to present a number of subtrees at the root level when the actual differences appear several levels further down.

So far we have only provided examples of elements, but XML is slightly more complex! While we believe that the patterns we have introduced can be used to describe other types of tree nodes such as attributes or text, the actions required will be slightly different.

Consider the following example of an element with some attributes:

A:   <x a='2'/>
B:   <x a='3' b='42'/>
C:   <x a='4' b='hello'/>

In our merged or unified representation of the three inputs we follow the XML model and have a single attribute node in our tree. However, unlike the InfoSet/XPath tree model, we have the concept of attribute value nodes as children of attribute nodes:

        Node            Type            VersionSet
        
      x-+               element         [A, B, C]
        +--a--+         attribute       [A, B, C]
        |     +--2      attributevalue  [A]
        |     +--3      attributevalue  [B]
        |     +--4      attributevalue  [C]
        |
        +--b--+         attribute       [B, C]
              +--42     attributevalue  [B]
              +--hello  attributevalue  [C]
      

In this example, the attributes are in conflict between the different input trees, but unlike the example with elements (Section 3.4, “Recursive actions”) we cannot add multiple a or b attributes to the result and still have valid XML. For this reason, we cannot apply our usual rules recursively: we need to know about the set of attribute value nodes in order to identify a conflict. For example, in the case of attribute a above, the presence of distinct attribute value nodes implies a conflict which we cannot deal with using recursion. We must decide at this point which value or values to output in the result tree.

This difference means that for processing attributes we need to consider both the leaf, or attribute value, version sets, together with the version set of the immediate parent node in the tree. Lack of space prevents expanding the rules in the paper, but they follow a similar style to those for elements.

The handling of PCDATA strings is analogous to handling attribute values, and again is not detailed in the paper.

Robin La Fontaine is CEO of DeltaXML, a company providing change management for XML including a method for representing changes to XML documents and data in XML. Robin has contributed to various ISO standards and has been project manager of several European research projects including the XML/EDI European Pilot Project. His background is in CAD data exchange and Lisp programming. Robin has a degree in Engineering Science from the University of Oxford and a Masters degree in Computer Science.

Nigel Whitaker is a Software Architect at DeltaXML and leads the research and development of the company's Java products. He started his career working with discrete event simulation and EDA, moved into compiler engineering and data format work, and is now heavily involved with Java, XML and XSLT technologies. Nigel has a Ph.D. in Computer Science from the University of Manchester.