How to cite this paper
La Fontaine, Robin. “Divide and Conquer: can we handle complex markup simply?” Presented at Symposium on Cultural Heritage Markup, Washington, DC, August 10, 2015. In Proceedings of the Symposium on Cultural Heritage Markup. Balisage Series on Markup Technologies, vol. 16 (2015). https://doi.org/10.4242/BalisageVol16.LaFontaine01.
Symposium on Cultural Heritage Markup
August 10, 2015
Balisage Paper: Divide and Conquer: can we handle complex markup simply?
Robin La Fontaine
Robin is the founder and CEO of DeltaXML. He holds an Engineering Science
degree from Oxford University and an MSc in Computer Science. His background
includes computer aided design software and he has been addressing the
challenges and opportunities associated with information change for many
Copyright © 2015 DeltaXML Limited. All rights reserved.
Cultural Heritage markup can quickly become complex because of the need to
represent multiple, and even overlapping, hierarchical structures. It can therefore
become very difficult to maintain correctly. This talk suggests that a better
approach is now possible: markup that is designed to represent different aspects of
a text could be handled separately from the point of view of checking and
maintenance, and then only combined into a single document when needed, e.g. for
some kind of analysis. Advances in comparison and merge tools for XML make this a
Table of Contents
- Introduction and Background
- An example of Divide and Conquer
- Application to Cultural Heritage Markup
- Developments in XML-aware Comparison and Delta Representation
Introduction and Background
Our cultural heritage is important, and we can learn from it. In looking at better
ways of handling cultural heritage documents using structured markup, there is an
opportunity also to learn from computer science ‘heritage’. Although many things in
computer science are changing very rapidly, lessons can be learned from past mistakes
experiences and it is often the case that what is deemed to be a new approach, is
fact an old approach revisited.
One of the purposes of cultural heritage markup is to have a representation of many
variants of a document all in one document. The variation may be in how it is marked
or in the text itself. This can lead to very complex markup, and it can become extremely
difficult to manage without very good tools. Indeed, as the information content becomes
richer, so the difficulty of handling the complexity increases. This is very well
described by Schmidt  and  and he
proposes that one way to solve this is to keep separate variants and merge them as
needed. He points out, however, that this is not a simple task.
The purpose of this short paper is twofold. Firstly, to note that this approach of
divide and conquer has been used in similar situations very successfully. Secondly,
summarize developments in the area of XML comparison and merge, developed primarily
other purposes, that relate to and may help in this area.
An example of Divide and Conquer
The cultural heritage markup problem has similarities to the handling of multiple
versions in other areas of computer science. An example of this is a project for
handling the documentation of a complex data model, using a version controlled
relational database. Although this work was done some twenty-five years ago, the lessons
learned remain pertinent.
The purpose of this project was to document a complex data model, and have this
reviewed by subject matter experts. The problem was that these experts were, as they
always are, short of time, and therefore we wanted to ensure that their time was well
spent in review. However, the model had to be developed and reviewed over many different
versions in order to make sure that it was correct, and therefore we needed to present
the subject matter experts with successive versions as these were developed. The experts
clearly wanted to know what had changed, rather than reviewing the whole document
This was in an era when tracked changes had not even been thought about, and certainly
good word-processing technology was not widely available.
The documentation was therefore put into a relational database, which was versioned
so that each successive version was recorded and identified. Using what was called
fourth-generation language, it was possible to write a
report that generated the full documentation with an indication of which parts of
have been updated since the previous version. (As an aside, it turned out to be
impossible to parameterize the 4GL reports sufficiently, and therefore large sections
had to be duplicated and slightly modified, resulting in a very large number of lines
code, which eventually became impossible to maintain.) In terms of the result that
produced, the project was very successful and the subject matter experts were pleased
because they were able to review only the changes.
As more versions of the document were added to this database, it became more and more
difficult to maintain the integrity of the database. It was extremely difficult, for
example, to remove a particular version from the database, or even to make updates
the latest version. This was partly due to inadequate tools, but it was fundamentally
difficult because whenever something was changed, it had to be duplicated first and
the versioning information set up correctly.
To get round this problem, a new approach was adopted. Rather than working directly
on the versioned database, a new version of the documentation was created independently
from the versioned database. It was then possible to write an automated script that
could add this new version back into the versioned database as a new version. This
be automated and so correctness could be guaranteed. Using this approach, it became
easier to create a new version of the document while at the same time being able to
maintain the versioned documentation that was required by the subject matter experts.
It was quite a simple idea, but it made an increasingly complex situation much easier
to handle. There are some parallels with cultural heritage markup, so this approach
worth persuing based on this similar past experience.
Application to Cultural Heritage Markup
We will now consider how this approach applies to cultural heritage markup. If we
could work on the representation of a particular variant of the document, this would
have relatively simple markup, which could be validated using conventional XML tools.
There would not be a need for overlapping hierarchy, and possibly not even text
variations. If we could then combine these simpler variants into a single document,
using markup to show structural and text variations, we would still be able to publish
the rich information that cultural heritage markup provides.
One of the advantages of this approach would be that we would not need to keep all
the variants together in a single document all the time, but rather we would combine
only those variants that were relevant to a particular publishing scenario. In addition,
we can combine two related variants together in order to check their integrity with
respect to each other.
In order to achieve this simplification, there are some significant challenges in
performing the merge, as noted by Schmidt. This would need to be based on comparison,
but it would be important to align the text independently of the structural markup.
said, some of the markup may be important for alignment and therefore a flexible
comparison approach is needed. Traditional text comparison tools are line based, and
not understand the markup and are therefore unsuitable for this work. XML comparison
traditionally guided by the document structure and again this is not suitable unless
can be made more flexible. A prerequisite is therefore the ability to be able to
distinguish between structurally significant markup, i.e. markup that is an important
divider in terms of alignment, and structurally insignificant markup, i.e. markup
should be ignored for alignment.
Once the text has been aligned, it is then necessary to have a suitable
representation of the overlapping structural hierarchy in a form that is suitable
conversion into cultural markup, e.g. TEI. The representation of
overlapping hierarchies is a difficult problem, and quite a number of papers have
presented at this conference and others about it .
Developments in XML-aware Comparison and Delta Representation
XML aware comparison understands the structure of the XML, and therefore uses this
when aligning two documents. Where the XML elements represent structure that is
significant to the alignment process, this approach is appropriate. However, XML element
tags are also used to markup formatting information and it is usually desirable not
show text changes when only formatting changes have been made. We therefore end up
a mixture of XML structure, some of which is significant and needs to be considered
the alignment process, and other elements that are not significant and need to be
ignored in the alignment process. The ignored elements need to be represented in the
final result and not lost. This, of course, typically leads to overlapping hierarchy.
Ignoring for a moment cultural heritage markup, for regular structured documents in
formats such as DITA or DocBook, it
is not generally necessary to be able to represent overlapping hierarchy. However,
often desirable to be able to distinguish between textual changes and formatting
changes, and a good representation of overlapping hierarchy enables such a distinction
to be made in a delta file.
Another requirement of conventional structured document comparison is the need to
control the alignment of specific elements within the document. This can be achieved
assigning keys to these elements, and ensuring that these keyed elements are aligned
preference to the alignment of any other elements. The use of keys enables a very
reproducible and controllable merge.
We are therefore moving to a situation where generic XML delta formats are able to
represent not only changes to textual information, and the simple addition or deletion
of complete elements, but also the presence or absence of XML tags around portions
text. We are getting close to the ability to take multiple variants of the document,
where the text is similar but not necessarily the same, and where markup may be
completely different, and merge these into a single document where the variants are
represented in XML in a generic form, without loss of information. To validate that
information is lost, it should be possible to generate all of the original documents
from the merged document.
The original purpose of this generic delta format was to be able to generate
derivatives for a variety of different purposes. For example, it would be possible
show where text has been changed, and distinguish this from where formatting has been
changed so that those who are interested in the one are not confused by the other.
also possible to ignore certain types of change in an intelligent way.
These advances may have applications useful to the cultural heritage markup community.
This short paper has described how a divide-and-conquer approach was adopted for a
complex version-controlled relational database, designed to support documentation
data model. The version-controlled database became too complex to manage but success
achieved by working on each version and only adding this to the versioned database.
useful results were achieved from this – results that were simply not possible at
time with any other approach.
The paper has explored parallels between this and the management of cultural heritage
markup and shown that advances in techniques to compare and merge structured XML
documents mean that a similar approach could be applied.
A purpose of these short talks is to explore different approaches to existing
problems. The question for discussion and feedback from the audience is how useful
approach would be to the Cultural Heritage markup community.
 Schmidt, Desmond. “The role of markup in the
digital humanities.” Historical Social Research 37 (2012), 3, pp. 125-146. URN:
 Schmidt, Desmond. “Merging Multi-Version Texts:
a Generic Solution to the Overlap Problem.” Balisage Series on Markup Technologies,
vol. 3 (2009),
 Informix 4GL:
 TEI: Text Encoding Initiative,
 Marcoux, Yves, Michael Sperberg-McQueen, Claus Huitfeldt. “Modeling overlapping structures.”
Balisage Series on Markup Technologies, vol. 10 (2013),
 OASIS Darwin Information Typing Architecture (DITA)
 OASIS DocBook TC,
 Overlapping Hierarchies in DeltaV2