Balisage Paper: Overlapproaches in documents: a definitive classification (in OWL, 2!)

Introduction

At the Balisage 2009 Conference we presented for the first time a new approach to overlapping markup called EARMARK, or "Extremely Annotational RDF Markup". It provided a point of view over something that is quintessentially Balisagean, overlapping markup, by using a number of suspicious techniques for this community, such as standoff markup, RDF, OWL, reasoners.

In brief, an EARMARK document is a collection of RDF statements about fragments of a text (a plain text or even an XML document), that describe the fragments' characteristics and features regardless of whether the fragments contain, are disjoint, or overlap with each other. Each fragment is associated to a formal concept called Range, which can (but does not have to) be associated to one or more Markup Items, which in turn may, or may not, refer to each other in some form. Since these annotations (and the objects they represent) are never embedded in the text, there are no implicit properties to consider, in particular no properties indirectly provided by the fragments' position in the text, relative to each other, according to document's order, etc. Thus in an EARMARK document a property exists (e.g., A contains B) if and only if it has been explicitly stated in the ontology, and not just because they happen to refer to the same text fragment. ^[1]

In doing so, EARMARK manages not only to be the only overlapping approach that fully expresses and makes use of unrestricted GODDAG, the formal model introduced in [34] by Sperberg-McQueen and Huitfeldt, but actually corresponds to a non-trivial extension of it, e-GODDAG, that supports repetitions of the same node in different contexts, in addition to self-overlap, discontinuous overlap, anonymous nodes, decoupling of containment and dominance, etc.

The conjunction of stand-off as a referencing approach, and RDF as the assertion syntax, allows EARMARK to bypass completely the usual dichothomy of embedded markup, that of either hiding overlapping situations inside a traditional, hierarchical XML markup, tricky but conservatively transparent with respect to the most common XML tools and services, or inventing a completely new syntax and having to deal with the lack of the usual validation tools, transformation tools, storage systems, etc. On the contrary, an EARMARK document is just a collection of RDF statements, and plain and usual RDF and OWL tools can be used to manage it: inference engines, rule-based systems, query languages, and triple stores work transparently with overlapping data, and any existing and future tool for RDF and OWL will be available for use transparently when managing EARMARK documents, too ^[2].

But in our 2009 paper, we actually and quite conventienly avoided to discuss a rather relevant issue: EARMARK, then, did not really allow to describe overlapping markup situations, but rather it allowed to describe traditional markup situations that could refer to overlapping content. Since each markup statement is independent of the others, it can refer to partially or totally overlapping ranges and children with no need (and no possibility) to determine that such overlap has actually happened.

But if you really want to be able to determine whether and where overlapping has happened in an EARMARK document, you need a few more tools, that luckily can and have been realized using standard and well-known RDF and OWL tools. In this paper, we present the EARMARK Overlapping Ontology (EOO), an ontology that uses OWL 2 and SWRL to provide a complete characterization of overlapping situations in EARMARK documents, allowing queries and representations that discovers and manages explicitly (instead of simply allowing and ignoring) all overlaps in the markup. This characterization takes the form of definitions of the overlapping patterns of the basic EARMARK ontology, and is therefore a definitive classification ^[3]of the overlapping approaches of EARMARK documents.

Of particular relevance for the EOO ontology is being able to distinguish between different aspects/manifestations of the overlap phenomenom, such as, for example:

The paper is organized as follows: in the next section, we present a brief overview of the topics, results and languages that have been proposed to handle overlaps in markup documents. In section “EARMARK”, EARMARK is (re-)introduced with its main classes and concepts. In section “Characterizing overlaps by way of an ontology”, the EARMARK Overlapping Ontology is presented and described, as well as how it can be used to identify and characterize the overlapping situations of an EARMARK document. The following section contains our conclusions and hints at future works.

Overlapping markup: a summary for the absent and the distracted

When marking up text documents it might be necessary to represent features that do not fit into the tree structure conveyed by an XML document. In fact, there are many situations in which authors may need to annotate the same piece of text with different markup descriptors (e.g. when a page spans from the middle of one paragraph to the middle of another, or when speeches span multiple verses, etc.): in such cases, the markup descriptors sometimes nest correctly into a single tree-hierarchy, sometimes not. In general, this issue may arises whenever an author wants to maintain two or more views of a document (e.g. metrical, syntactical, layout, etc.), and consequently multiple and incompatible hierarchies insists on the same textual content. This problem is referred to in the literature as the overlapping problem.

After a first period in which the deficiencies of markup languages that concerns the overlapping problem were overlooked [3]^[4] or even suppressed [9]^[5], the digital humanities community started to put an increasing effort in trying to define and develop solution to this issue. The essence of the problem can be summarized as follows: “overlap can be presented by graphs that are very like trees, but in which nodes may have multiple parents. Overlap is multiple parentage” [34]. While trying to represent non-hierarchical structures using a markup language whose model is a tree, such as SGML or XML, authors run into different manifestations of the problem, referred to using different terminology in the literature:

Since the document model of XML is inherently a tree, there is no simple way to cover such complex situations when handling multiple hierarchies. In order to overcome these limitations, many different solutions have been proposed. In general, we can identify two different approaches to the problem. The first consists in devising techniques to encode the information about overlapping situations by using specific XML features (e.g. empty elements to specify the boundary of overlapping elements, attributes to link elements that don't nest properly, etc.) or technologies (e.g. XPath [4], XQuery [5], etc.). The second approach is to abandon XML altogether and with it the benefits of its tree-based data model, and devise a new formalism and notation based on a more general and expressive abstract structure, such as a directed graph.

EARMARK

The Extremely Annotational RDF Markup, or EARMARK [12], is an OWL 2 DL ontology^[7]that defines document meta-markup. It is an ontologically precise definition of markup that instantiates the markup of a text document as an independent OWL document outside of the text strings it annotates, and through appropriate OWL and SWRL characterisations it can define structures such as trees or graphs (in particular, extended GODDAGs [11]) and can be used to generate validity constraints (including co-constraints) [13], to make explicit the semantics of markup [30], to annotate text or other markup documents [1], to keep track of changes in markup [31], and as interchange format to enable conversions between different kinds of XML vocabularies embedding overlap [2]. The whole ontological description of EARMARK is summarised in the Graffoo diagram^[8] [16] shown in Figure 1.

Figure 1:

Figure 1: a Graffoo diagram summarising the EARMARK Ontology.

The core classes of our model describe three disjoint base concepts: docuverses, ranges and markup items.

The textual content of an EARMARK document is conceptually separated from its annotations, and is referred to through the earmark:Docuverse class. The individuals of this class represent the objects of discourse, i.e. all the containers of text from an EARMARK document. Any individual of the earmark:Docuverse class – commonly called a docuverse (lowercase to distinguish it from the class) – specifies its actual content through the property earmark:hasContent. There exist two different kinds of docuverses, those that specify all its content in form of a string (defined through the class earmark:StringDocuverse) and those that refer to a document containing the string to be marked up (defined through the class earmark:URIDocuverse).

We define the class earmark:Range for any text lying between two locations of a docuverse. A range, i.e, an individual of the class earmark:Range, is defined by a starting and an ending location (any literal) of a specific docuverse through the functional properties earmark:begins, eamark:ends and earmark:refersTo respectively. There exist two main types of ranges: those (i.e., earmark:PointerRange) that refer to text lying between two non-negative integer locations that identify precise positions within a docuverse, and those (defined through the class earmark:XPathPointerRange) that refer to any text, obtained from a particular XPath context (specified through the property earmark:hasXPathContext) starting from a docuverse content, lying between two non-negative integer locations that identify precise positions.

The class earmark:MarkupItem is the superclass defining artefacts to be interpreted as markup such as elements (i.e., the class earmark:Element), attributes (i.e., the class earmark:Attribute) and comments (i.e., the class earmark:Comment). A markupitem individual is a collection^[9] (co:Set, co:Bag and co:List, where the latter is a subclass of the second one and all of them are subclasses of co:Collection) of individuals belonging to the classes earmark:MarkupItem and earmark:Range. Through these collections it is possible:

A markupitem might also have a name, specified in the functional property earmark:hasGeneralIdentifier^[10], and a namespace specified using the functional property earmark:hasNamespace.

In order to understand how EARMARK is used to describe markup hierarchies, let us consider the markup structures shown in Figure 2.

Figure 2:

Figure 2: an example of three different markup hierarchies (light-blue rectangles with solid border, light-green rectangles with dashed border, and pink rectangles with dotted borders) involving six different ranges (the five empty rhomboids with solid red border and the one with blue dashed border).

First of all, we define the whole textual content of the document – i.e., the first three lines of the Paradise Lost by John Milton – by creating an instance of the class earmark:StringDocuverse^[11]:

@prefix : <http://www.essepuntato.it/2014/balisage/example/>
:doc a earmark:StringDocuverse ;
  earmark:hasContent 
    "Of Mans First Disobedience, and the Fruit
    Of that Forbidden Tree, whose mortal tast
    Brought Death into the World" .

Then, we can define all the six different ranges (as individuals of earmark:PointerRange) that are introduced in the figure, i.e.:

# The string 'Of Mans First Disobedience, and the Fruit'
:r1 a earmark:PointerRange ;
  earmark:refersTo :doc ;
  earmark:begins "0"^^xsd:nonNegativeInteger ;
  earmark:ends "41"^^xsd:nonNegativeInteger .

# The string 'the Fruit Of that Forbidden Tree,'
:r2 a earmark:PointerRange ;
  earmark:refersTo :doc ;
  earmark:begins "32"^^xsd:nonNegativeInteger ;
  earmark:ends "65"^^xsd:nonNegativeInteger .

# The string 'Of that Forbidden Tree,'
:r3 a earmark:PointerRange ;
  earmark:refersTo :doc ;
  earmark:begins "42"^^xsd:nonNegativeInteger ;
  earmark:ends "65"^^xsd:nonNegativeInteger .

… 

Finally, we can built the three markup hierarchies shown in upon these ranges, as shown in the follwing excerpt:

:lg a earmark:MarkupItem , co:List ;
  earmark:hasGeneralIdentifier "lg" ;
  co:firstItem [
    a co:ListItem ;
    co:itemContent :l1 ;
  co:nextItem [ 
    a co:ListItem ;
    co:itemContent :l2 ;
  co:nextItem [ 
    a co:ListItem ;
    co:itemContent :l3 ] ] ] .

:q a earmark:MarkupItem , co:List ;
  earmark:hasGeneralIdentifier "q" ;
  co:firstItem [
    a co:ListItem ;
    co:itemContent :l1 ] .

:l1 a earmark:MarkupItem , co:List ;
  earmark:hasGeneralIdentifier "l" ;
  co:firstItem [
    a co:ListItem ;
    co:itemContent :r1 ] .

… 

Characterizing overlaps by way of an ontology

Different types of overlap exist – according to the subset of EARMARK nodes involved (i.e., ranges or markup items) – and different strategies are needed to detect them. In particular, there is a clear distinction between overlapping ranges and overlapping markup items, and in the ways these overlapping scenarios affect the dominance and containment relations between nodes – as shown in figure Figure 2, that will be used to illustrate the different kinds of overlapping scenarios.

In this section, we introduce the EARMARK Overlapping Ontology (EOO)^[12], which is an OWL 2 DL ontology [MotikOWL2] that extends the EARMARK Ontology by adding support for overlapping scenarios and for inferences relative to them. In particular, in the following subsections we describe how the ontology models all possible overlapping scenarios between nodes by means of description logic formulas^[13] and SWRL rules [21] (if needed)^[14]. A summary of the taxonomy of possible overlapping scenarios is provided in figure Figure 3.

Figure 3:

Figure 3: the taxonomy of all the different kinds of overlapping scenarios that are introduced in this paper.

# Declaration as an object property
eoo:overlapsWith ⊑ ⊤op

# Domain
∃eoo:overlapsWith.⊤ ⊑ 
  (earmark:Range ⊓ ∀eoo:overlapsWith.Range) ⊔ 
  (earmark:MarkupItem ⊓ ∀eoo:overlapsWith.MarkupItem)

# Range
⊤ ⊑ ∀eoo:overlapsWith.(
  (earmark:Range ⊓ ∀eoo:overlapsWith.Range) ⊔ 
  (earmark:MarkupItem ⊓ ∀eoo:overlapsWith.MarkupItem))

# Symmetry
eoo:overlapsWith ≡ eoo:overlapsWith-

# Irreflexivity 
⊤ ⊑ ¬∃eoo:overlapsWith.Self

# Sub-property declaration
eoo:overlapsWithRange ⊑ eoo:overlapsWith

# Domain
∃eoo:overlapsWithRange.⊤ ⊑ earmark:Range

# Range
⊤ ⊑ ∀eoo:overlapsWithRange.earmark:Range

# Symmetry
eoo:overlapsWithRange ≡ eoo:overlapsWithRange-

# Sub-property declarations
eoo:overlapsTotallyWithRange ⊑ eoo:overlapsWithRange
eoo:overlapsPartiallyWithRange ⊑ eoo:overlapsWithRange

# Disjointness
eoo:overlapsTotallyWithRange ⊓ eoo:overlapsPartialelyWithRange ⊑ ⊥

# Symmetry
eoo: overlapsTotallyWithRange ≡ eoo:overlapsTotallyWithRange-
eoo: overlapsPartiallyWithRange ≡ eoo:overlapsPartiallyWithRange-

# Overlaps partially with range
RANGE_IDENTIFICATION ^
earmark:refersTo(?x,?d) ^ earmark:refersTo(?y,?d) ^ 
earmark:begins(?x,?b1) ^ earmark:begins(?y,?b2) ^
earmark:ends(?x,?e1) ^ earmark:ends(?y,?e2) ^ 
(?b1 < ?b2 < ?e1 < ?e2) or (?b1 < ?e2 < ?e1 < ?b2) or
(?e1 < ?b2 < ?b1 < ?e2) or (?e1 < ?e2 < ?b1 < ?b2) or
(?b1 = ?b2 and ?e1 = ?e2) or (?b1 = ?e2 and ?e1 = ?b2) ^
?x != ?y
  ⇒ eoo:overlapsPartiallyWithRange(?x,?y)

# Overlaps totally with range
RANGE_IDENTIFICATION ^
earmark:refersTo(?x,?d) ^ earmark:refersTo(?y,?d) ^ 
earmark:begins(?x,?b1) ^ earmark:begins(?y,?b2) ^
earmark:ends(?x,?e1) ^ earmark:ends(?y,?e2) ^ 
(?b1 <= ?b2 < ?e2 < ?e1) or (?e1 <= ?b2 < ?e2 < ?b1) ^
(?b1 < ?b2 < ?e2 <= ?e1) or (?e1 < ?b2 < ?e2 <= ?b1) ^
(?b1 <= ?e2 < ?b2 < ?e1) or (?e1 <= ?e2 < ?b2 < ?b1) ^
(?b1 < ?e2 < ?b2 <= ?e1) or (?e1 < ?e2 < ?b2 <= ?b1) ^
?x != ?y
  ⇒ eoo:overlapsTotallyWithRange(?x,?y)

earmark:PointerRange(?x) ^ earmark:PointerRange(?y)

earmark:XPathPointerRange(?x) ^ earmark:XPathPointerRange(?y) ^
earmark:hasXPathContext(?x,?c) ^ earmark:hasXPathContext(?y,?c) 

# Declaration as an object property
eoo:dominatesDirectly ⊑ ⊤op

# Domain
∃eoo:dominatesDirectly.⊤ ⊑ earmark:MarkupItem

# Range
⊤ ⊑ ∀eoo:dominatesDirectly.(earmark:Range ⊔ earmark:MarkupItem)

earmark:MarkupItem(?x) ^ co:element(?x,?y) 
  ⇒ eoo:dominatesDirectly(?x,?y)

# Declaration as an object property
eoo:dominates ⊑ ⊤op

# Sub-property declaration
eoo:dominatesDirectly ⊑ eoo:dominates

# Transitivity
eoo:dominates o eoo:dominates ⊑ eoo:dominates

# Declaration as an object property
eoo:contains ⊑ ⊤op

# Domain
∃eoo:contains.⊤ ⊑ earmark:Range ⊔ earmark:MarkupItem

# Range
⊤ ⊑ ∀eoo:contains.(earmark:Range ⊔ earmark:MarkupItem)

# Transitivity
eoo:contains o eoo:contains ⊑ eoo:contains

# Sub-property declaration
eoo:dominates ⊑ eoo:contains

eoo:overlapsTotallyWithRange(?x,?y) ^ 
earmark:begins(?x,?b1) ^ earmark:begins(?y,?b2) ^ 
earmark:ends(?x,?e1) ^ earmark:ends(?y,?e2) ^ 
(?b1 < ?b2 < ?e1) or (?b1 < ?e2 < ?e1) or
(?e1 < ?b2 < ?b1) or (?e1 < ?e2 < ?b1)
  ⇒ eoo:contains(?x,?y)

# Sub-property declaration
eoo:overlapsWithMarkupItem ⊑ eoo:overlapsWith

# Domain
∃eoo:overlapsWithMarkupItem.⊤ ⊑ earmark:MarkupItem

# Range
⊤ ⊑ ∀eoo:overlapsWithMarkupItem.earmark:MarkupItem

# Symmetry
eoo:overlapsWithMarkupItem ≡ eoo:overlapsWithMarkupItem-

# Sub-property declaration
eoo:overlapsByRange ⊑ eoo:overlapsWithWithMarkupItem

# Domain
∃eoo:overlapsByRange.⊤ ⊑ 
  earmark:MarkupItem ⊓
  ∃eoo:dominatesDirectly.(∃eoo:overlapsWithRange.earmark:Range)

# Range
⊤ ⊑ ∀eoo:overlapsByRange.(
  earmark:MarkupItem ⊓
  ∃eoo:dominatesDirectly.(∃eoo:overlapsWithRange.earmark:Range))

# Symmetry
eoo:overlapsByRange ≡ eoo:overlapsByRange-

# Sub-property declaration
eoo:overlapsByContentHierarchy ⊑ eoo:overlapsWithWithMarkupItem

# Domain
∃eoo:overlapsByContentHierarchy.⊤ ⊑ 
  earmark:MarkupItem ⊓ ∃eoo:dominatesDirectly.earmark:Range

# Range
⊤ ⊑ ∀eoo:overlapsByContentHierarchy.(
  earmark:MarkupItem ⊓ ∃eoo:dominatesDirectly.earmark:Range)

# Symmetry
eoo:overlapsByContentHierarchy ≡ eoo:overlapsByContentHierarchy-

# Sub-property declaration
eoo:overlapsByMarkupHierarchy ⊑ eoo:overlapsWithWithMarkupItem

# Domain
∃eoo:overlapsByMarkupHierarchy.⊤ ⊑ 
  earmark:MarkupItem ⊓ ∃eoo:dominatesDirectly.earmark:MarkupItem

# Range
⊤ ⊑ ∀eoo:overlapsByMarkupHierarchy.(
  earmark:MarkupItem ⊓ ∃eoo:dominatesDirectly.earmark:MarkupItem)

# Symmetry
eoo:overlapsByMarkupHierarchy ≡ eoo:overlapsByMarkupHierarchy-

# overlaps by range
earmark:MarkupItem(?a) ^ earmark:MarkupItem(?b) ^ 
earmark:Range(?r1) ^ earmark:Range(?r2) ^ 
eoo:dominatesDirectly(?a,?r1) ^ eoo:dominatesDirectly(?b,?r2) ^ 
eoo:overlapsWithRange(?r1,?r2) ^ 
?a != ?b ^ ?r1 != ?r2
  ⇒ eoo:overlapsByRange(?a,?b)

# overlaps by content hierarchy
earmark:MarkupItem(?a) ^ earmark:MarkupItem(?b) ^ earmark:Range(?r) ^ 
eoo:dominatesDirectly(?a,?r) ^ eoo:dominatesDirectly(?b,?r) ^ 
?a != ?b
  ⇒ eoo:overlapsByContentHierarchy(?a,?b)

# overlaps by markup hierarchy
earmark:MarkupItem(?a) ^ earmark:MarkupItem(?b) ^ earmark:MarkupItem(?x) ^ 
eoo:dominatesDirectly(?a,?x) ^ eoo:dominatesDirectly(?b,?x) ^ 
?a != ?b != ?x
  ⇒ eoo:overlapsByMarkupHierarchy(?a,?b)

# Rule 'overlaps by markup hierarchy' in SPARQL
CONSTRUCT { ?a eoo:overlapsByMarkupHierarchy ?b }
WHERE {
  ?a a earmark:MarkupItem ;
    eoo:dominatesDirectly ?x .
  ?b a earmark:MarkupItem ;
    eoo:dominatesDirectly ?x .
  ?x a earmark:MarkupItem .
}

Conclusions

For EARMARK to be able to claim to be a one-stop answer to overlapping needs of markup authors, we still needed a way to identify when, indeed, ranges and markup items actually overlap. EARMARK per se, in fact, does not have a way to identify overlapping situations, simply allowing them to exist and each overlapping item to ignore the others. With the EARMARK Overlapping Ontology, on the other hand, it is now possible to identify and qualify explicitly every overlapping situation we encounter. For instance in [1] we provide a brief overview of situations and contexts where EARMARK can and has been used, especially in the domain of Digital Humanities.

Also, technically, EARMARK is a stand-off notation, and as such it suffers from the same limitations that all stand-off notations suffer: namely, whenever the source document (the docuverse) is modified outside of the control of the author of the EARMARK annotations, they may (and often will) have the pointers become outdated and wrong. Also in [1] we provide some mechanisms through which EARMARK pointers can be resynchronized with a modified source, that should be able to handle some of the possible situations.

EARMARK still has not finished evolving. The FRETTA parser [2], that provides a way for converting EARMARK documents into XML, and expressing overlapping situations choosing parametrically one of the many existing XML tricks such as fragmentation, milestones or twin documents, is working and complete, but the opposite converter, the one that generates an EARMARK document from an XML file that uses XML tricks to express overlaps, is still to be completed. Once this is finished, we will have a complete solution to the problem of expressing any markup document with Semantic Web technologies, and we will be able to cover all possible situations of conversion of overlapping documents.