Comparing Orderless Elements

This section describes the concepts behind the comparison of orderless elements. For the resources associated with this sample, see Bitbucket.

Any element in an XML file can be declared as a container for orderless elements. DeltaNova Compare will match up and compare the child elements of such a container regardless of the order in which they appear. What counts about orderless elements is membership in a set, not relative position. Arbitrary rearrangement leaves the meaning of the set unaffected.

To summarise, for comparing orderless elements, we are concerned with two types of element:

Orderless Container - This is an element that has child elements arranged in an order that is not considered significant.

Orderless Element - This is an element whose position relative to its siblings is not regarded as significant because its parent element is an orderless container.

In the example below the addressList element is the 'orderless container', whereas the person elements within addressList are 'orderless elements'.

Using Keys

To detect changes in sets or orderless elements, DeltaNova Compare must align corresponding elements in spite of rearrangements. Keys help DeltaNova Compare perform this correlation. Keys remove any need for sorting.

The special-purpose attributes called keys simplify comparisons in many situations. XML permits both ordered and orderless data. Keys help DeltaNova Compare track changes in both categories. Keys increase both the quality of the matches made and the runtime speed of the comparisons. For orderless data keys should be provided whenever possible to get the best results. But keys can also be provided with ordered data to improve the alignment; see Using Keys with Ordered Data.

Key attributes impose no requirements on data formats. XSLT scripts can generate keys on the fly, whenever needed, and discard them in post-processing. The original XML remains unaffected by their use.

Three practical solutions are presented below, with each using a different comparator and method for customising a comparison:

Pipelined Comparator (DXP) — Uses a filter pipeline defined by an XML file called a 'DXP' to customise the comparison.
Document Comparator — Uses Java API calls to customise a pre-existing pipeline with a number of extension points.
Document Comparator (API and DCP) — Uses either Java API calls to customise a pre-existing pipeline with a number of extension points, or through a parameter in a DCP file.

Removing Ignorable Whitespace

One point that should be noted, before reading further, is that it is very important to remove whitespace only PCDATA nodes during orderless comparison (for example using the com.deltaxml.pipe.filters.NormalizeSpace Java XML Filter). Also, note that an orderless container must not contain PCDATA as an immediate child: it will cause an exception (com.deltaxml.api.UnorderedElementContainingPCDATAException). The reason is that while elements are separated unambiguously by tags, if two PCDATA items are put next to each other they are in effect merged into one PCDATA item, so orderless PCDATA makes no sense.

How to Declare an Orderless Container

Ordering is often unimportant during data capture or storage. For example, entries in an electronic address book can be stored in any order. Assume that we have the following entries stored as our address data and wish to track any modifications using DeltaNova Compare:

Example 1: an address book XML document (documentA.xml)

XML

<addressList>
  <person customerid="15">
    <name>Joe Bloggs</name>
    <email>jblogs@msn.com</email>
    <address>
      <line>1234 Green Lane</line>
      <line>London</line>
      <zip>SW1 7WJ</zip>
    </address>
  </person>
  <person customerid="14">
    <name>John Doe</name>
    <email>jdoe@hotmail.com</email>
    <address>
      <line>1234 East Beverley Drive</line>
      <line>Phoenix</line>
      <zip>AZ 12345</zip>
    </address>
  </person>
</addressList>

The first step is to tell DeltaNova Compare that child elements of <addressList> are orderless elements. Or, to put it differently: to identify <addressList> elements as orderless containers.

Example 2: Adding the orderless attribute using an XSLT template (address-key.xsl)

XML

<xsl:template match="addressList">
  <xsl:copy>
    <xsl:attribute name="deltaxml:ordered" select="'false'"/>
    <xsl:apply-templates select="@*, node()"/>
  </xsl:copy>
</xsl:template>

The attribute deltaxml:ordered="false" is the signal. This tells DeltaNova Compare that the order of child elements of <addressList> can be ignored, i.e. they can appear in any order.

Adding the Orderless Attribute Using Java API or DCP

To add the orderless attribute using the Java API or DCP instead of an XSLT template see the Subtree Processing Mode documentation.
The second step is to provide DeltaNova Compare with a means of matching elements across the two input files. In our example the customerid attribute can serve as a matching key.

Example 3: Adding keys using an XSLT template

XML

<xsl:template match="person">
  <xsl:copy>
    <xsl:attribute name="deltaxml:key" select="@customerid"/>
    <xsl:apply-templates select="@*, node()"/>
  </xsl:copy>
</xsl:template>

Comparing Orderless Elements With Keys

Rules for Keys in Orderless Comparisons

The following rules apply to the use of key attributes in the orderless case:

Orderless containers must be assigned a deltaxml:ordered="false" attribute.
XML elements are considered ordered by default (in the absence of this attribute on their parent).
Two elements that are identical in all respects except the deltaxml:ordered attribute are considered distinct and will not be compared with each other.
Orderless containers may not contain parsed character data.
Any element may be designated as an orderless container, regardless of the ordering status of its parent or child elements.

Rules for Orderless Elements Lacking Keys

Generally, elements that are members of an orderless set of elements should all have a key attribute. Orderless sets with a mixture of keyed and unkeyed elements may yield obscure results during comparisons.

Using no keys at all is preferable to a mixed case. DeltaNova Compare's rules for the mixed case are:

Elements of the same type with the same key are matched, and any changes within them are shown.
If the comparison file contains an identical element (perfect match, but neither element has a key attribute) DeltaNova Compare assumes these are actually the same. No change is recorded.
If no identical element exists, the keyless element is considered a delta change - recorded as an addition or deletion.

Orderless Presentation

When presenting the results of an orderless comparison, we have choices about whether to favour the order of elements in the A document or the B document, and also whether additions should be shown before or after deletions. The OrderlessPresentation comparator property is used to control this presentation order:

XML

<comparatorProperties>
  <property name="http://deltaxml.com/api/property/orderlessPresentation"
            literalValue="a_matches_deletes_adds"/>
</comparatorProperties>

The DocumentComparator allows control through the OutputFormatConfiguration class:

Java

DocumentComparator dc = new DocumentComparator();
dc.getOutputFormatConfiguration().setOrderlessPresentationMode(
    OrderlessPresentationMode.B_DELETES);

Running the Sample

The sample code illustrates two methods of performing orderless element comparison. The first method uses the Pipelined Comparator, and specifies input and output filters with a DXP file. The second method uses the API exposed by the Document Comparator.

Download the sample from https://bitbucket.org/deltaxml/orderless-comparison. Details of how to run the sample are given in README.md.