Balisage Paper: Modeling overlapping structures

1. Motivation and related work

<div xmlns="http://www.tei-c.org/ns/1.0">
  <p>
    <verse xml:id="Jer.2.1"/>
    Moreover the word of the LORD 
    came to me, saying,
    <verse eID="#Jer.2.1"/>
    <q n="Q-Jer.2.2-A">
      <verse xml:id="Jer.2.2"/>
      Go and cry in the
      hearing of Jerusalem, saying,
      <q n="Q-Jer.2.2-B">
	Thus says the LORD:
	<q n="Q-Jer.2.2-C">
	  I remember you, 
	  The kindness of your youth, 
	  The love of your betrothal, 
	  When you went after Me in the wilderness, 
	  In a land not sown.
	  <verse eID="#Jer.2.2"/>
	  <verse xml:id="Jer.2.3"/>
	  Israel [was] holiness to the LORD, 
	  The firstfruits of His increase.  
	  All that devour him will offend; 
	  Disaster will come upon them,
	</q>
	<!--True Close Q-Jer.2.2-C-->
      says the LORD.</q>
      <verse eID="#Jer.2.3"/>
      <!--* ... *-->
    </q>
  </p>
</div>

<div|
  <p|
    <verse@Jer.2.1|Moreover the word 
    of the LORD came to me, saying,|verse>
    <q n="Q-Jer.2.2-A"|
      <verse@Jer.2.2|
	Go and cry in the
	hearing of Jerusalem, saying, 
        <~@Jer.2.2b|
          Thus says the LORD:|~>
        <~@Jer.2.2c|
	    I remember you, 
	    The kindness of your youth, 
	    The love of your betrothal, 
	    When you went after Me in the wilderness, 
	    In a land not sown.|~>
      |verse>	
      <q n="Q-Jer.2.2-B"|
        <=@Jer.2.2b=>
	  <q n="Q-Jer.2.2-C"|
            <=Jer.2.2c=>
            <~@Jer.2.3a|
	    Israel [was] holiness to the LORD, 
	    The firstfruits of His increase.  
	    All that devour him will offend; 
	    Disaster will come upon them,
            |~>
          |q>
      |q>
      <verse@Jer.2.3|
        <=Jer.2.3a=>
        says the LORD.
    |verse>
    <* ... *>
    |q>
  |p>
|div>

<div|
  <p|
    <verse@Jer.2.1|
    Moreover the word of the LORD 
    came to me, saying,
    |verse>
    <q n="Q-Jer.2.2-A"|
      <verse@Jer.2.2|
      Go and cry in the
      hearing of Jerusalem, saying,
      <q n="Q-Jer.2.2-B"|
	Thus says the LORD:
	<q n="Q-Jer.2.2-C"|
	  I remember you, 
	  The kindness of your youth, 
	  The love of your betrothal, 
	  When you went after Me in the wilderness, 
	  In a land not sown.
	  |verse>
	  <verse@Jer.2.3|
	  Israel [was] holiness to the LORD, 
	  The firstfruits of His increase.  
	  All that devour him will offend; 
	  Disaster will come upon them,
	|q>
	  says the LORD.
	|verse>
      |q>
      <* ... etc. ... *>
    |q>
  |p>
|div>

2. Child-arc-ordered directed graphs

2.1 Definition A child-arc-ordered directed graph (CODG for short) G = (V, ch) is a directed graph over a finite non-empty set of vertices (or nodes) V, where ch (for children) is a total mapping from V to finite (and possibly empty) sequences of nodes from V. The set of arcs (or edges) of G, noted E(G), comprises exactly those ordered pairs (v, w) for which

where N represents the set of non-negative integers. The notation ch(v, n) is used as a shorthand for (ch(v))(n), that is, for the element with index n in the sequence ch(v). We use 0-origin indexing; thus, for all v ∈ V, ch(v, 0) denotes the first child of v (or is undefined, if v has no child).

Note: Throughout this paper, the “parent” relation must be understood to be the exact inverse of the “child” relation (we bother to make this explicit because it is not the case in some other models, such as the XPath 1.0 data model).

It is possible for the same child to show up at more than one place in a sequence of children; that is, ch(v, n) = ch(v, m) with m ≠ n is possible. Loops are allowed; that is, ch(v, n) = v for a given n is possible.

Note that (v, w) ∈ E(G) for given v and w tells only part of the story: There could be many distinct values of n for which ch(v, n) = w. Also note that the length of ch(v), i.e., the smallest value of n (≥ 0) for which ch(v, n) is undefined, is greater than or equal to the number of distinct children of v (if v has no child, ch(v) = ∅, which, as a sequence, is of length 0).

CODGs are very loose structures: they can be “multi-graphs,” in that more than one arc can link any given pair of nodes. They can have cycles and loops (i.e., cycles of length one). There can be both a direct (length one) and indirect path between any two given nodes.

The rationale for the adjective child-arc-ordered is that for all v ∈ V, ch(v) can be seen as inducing an ordering on the arcs going out of v (the child-arcs of v).

Examples We present examples of CODGs illustrating some of their features.

Example 2.1

Example 2.1 illustrates that CODGs can be disconnected, and that, in a CODG:

Note that the order of the outgoing arcs is usually not shown explicitly in the visual representation of a CODG. We adopt the convention of drawing the arcs going out of any node in order from left to right (even if the arcs must cross each other further down, in order to reach the child node they point to). So the leftmost arc leaving any parent is pointing to that parent's first child, and the rightmost arc points to that parent's last child.^[5] Thus, in Example 1, ch(a) = (b, c, d, c).

On the rare occasions that this convention is not practical, we use explicit green arrows between the outgoing arcs to indicate their order, as in the next example.

Example 2.2

In Example 2.2, ch(a) = (b, c) and ch(d) = (e, c). Right-pointing arrows, though superfluous, are sometimes shown as a reminder of the implicit convention.

Sibling precedence For all v, ch(v) induces a sibling-precedence relation sp(v) among the children of v, defined by:

Example 2.3

Example 2.3 illustrates that parents may order the same nodes differently as children. Thus, note that ch(a) = (b, c), which induces the strict order relation b < c, and ch(d) = (c, b), which induces the strict order relation c < b.

In examples in which no pair of nodes is ordered differently by different parents, we will usually place the green arrows between nodes, rather than between arcs:

Example 2.4

Auxiliary concepts We now define a number of auxiliary concepts useful in discussions of CODGs. All of them are secondary concepts in the sense that they are entirely and uniquely determined by the set of vertices and the sequences of children of the graph.

2.2 Definition Let G = (V, ch) be a CODG. Then:

2.3 Notation Let G = (V, ch) be a CODG. Unless otherwise stated:

3. Overlap-only documents

The phenomenon we wish to study in this paper is how the structural properties of a CODG relate to the fact that it mimics the containment and precedence relationships among elements in some marked-up document. More specifically, we want to consider documents expressed in markup languages that allow overlapping elements, such as TexMecs HS2003. Thus, we need to define a model for such documents.

TexMecs allows many more constructs than element embedding and overlap. However, in this paper, we concentrate on those two, ignoring the others, such as virtual elements, interrupted elements, empty elements, attribute specifications, entity references, generic identifier co-indexing (for handling self-overlap), unordered contents, and comments. This is why we speak of “overlap-only” (or “oo”) documents. When the structure of a CODG corresponds to the containment and precedence relationships of some oo-document (to be defined precisely in a moment), we say the CODG is “oo-serializable,” because the oo-document can be viewed as a serialization (a representation in serial form) of the CODG.

Instead of defining documents as character strings with syntactic constraints, we use a more abstract approach that avoids some complications and leads to results that are simpler to formulate. More constraints on the definition of document could later be added to suit specific markup languages if and when desired.

Intuitively, we adopt a tokenized view of the document, where tokens are tags and leaves. Tokens are represented by their (integer) position in the sequence of tokens that make up the document.

The tags in our model of oo-documents correspond, in the XML world, to start- and end-tags for non-empty elements.

The leaves in our model of oo-documents correspond, in the XML world, to text nodes (#PCDATA) and empty elements. Note that our model abstracts away from the actual textual content of elements and documents, and also ignores the differences among different element types. We claim, however, that our abstraction captures the essential structural aspects of marked-up documents with possible element overlap.

3.1 Definition An oo-document is a finite set of pairs of the form (x, y), where x, y ∈ N (the set of non-negative natural numbers) and x ≤ y, additionally satisfying a number of “well-formedness” constraints (stated below).

The pairs in a document are called ranges. If r = (x, y) is a range, then r₁ and r₂ denote respectively x and y.

Intuitively, a range gives the position of a start-tag and of the corresponding end-tag, or the position of a leaf, in which case, x = y. Formally, if D is an oo-document:

Note that, as usual:

Oo-documents are subject to the following well-formedness constraints.

It must also be remembered that (as stated at the beginning of the definition) for all range r, r₁ ≤ r₂, which corresponds to the normal rule of syntax that start-tag must precede its matching end-tag.

Note that we do not require the numbering of token positions to be gap-free, nor do we forbid consecutive leaves without intervening tags. There is also no requirement of an element spanning the whole document: this is of course crucial for oo-documents to be able to correspond to graphs with multiple roots.

3.2 Definition Let D be an oo-document, and r, s ∈ D:

Note that in the latter case, r and s may or may not overlap. Also note that r cannot both contain and precede s.

4. Correspondence between a graph and a document

Intuitively, a CODG and an oo-document correspond to each other when the nodes of the graph and the ranges of the document can be put in correspondence in such a way that node reachability corresponds to range containment, and gsp corresponds to range precedence.

4.1 Definition A CODG G and an oo-document D correspond to each other iff there exists a bijective mapping g from V(G) to D, such that all of the following conditions hold:

We then say that G and D correspond to each other through g.

4.2 Definition A CODG G is said to be oo-serializable iff there exists an oo-document that corresponds to G.

It is clear that every oo-document has a corresponding CODG: use ranges as nodes, and the transitive reduction of range containment as parent-child relation. Then, order all sets of siblings in range precedence order.

It is also clear that some CODGs are not oo-serializable: for example, a CODG with cycles would imply (by transitivity) a range containing itself, which is impossible. But are all acyclic CODGs oo-serializable? The following examples, inspired from M2008, show that the question is at best not trivial:

Example 4

Example 5

Both graphs are acyclic and they differ by just the presence/absence of one arc. Yet, only the first one is oo-serializable M2008.^[6]

In M2008, Marcoux defined noDAGs, or node-ordered DAGs, as (essentially) directed acyclic graphs (DAGs) in which the nodes are partially ordered in such a way that siblings (children of a common parent), as well as distinct roots, are totally ordered. He then defined the property of completion-acyclicity for noDAGs, and showed that oo-serializable noDAGs are exactly the completion-acyclic ones.

In order to investigate whether the same is true of CODGs, we must define an analogous property for CODGs. The following definition is the natural adaptation of completion-acyclicity to CODGs.

4.3 Definition Let G = (V, ch) be a CODG. Then:

4.4 Notation Let G = (V, ch) be a CODG. Unless otherwise stated:

The relations ssb and sea can be understood as meaning: “should <something> in any oo-serialization of the CODG,” for example “should end after in any oo-serialization of the CODG.” Thus, “(v, w) ∈ ssb” can be read out as: “v should start before w in any oo-serialization of the CODG.” In other words, ssb (respectively, sea) represents the start- (respectively, end-) tag-precedence relations that can be deduced from the topology of the CODG, supposing parent-child relations are interpreted as element containment, and sibling-precedence relations as start- and end-tag-precedence.

The relations ssba and seaa represent the “additional” arcs (over and above those in E and gsp or gsp^-1) that must be considered to compute all the possible ssb and sea pairs that can be deduced from the CODG topology.

4.5 Definition A CODG G = (V, ch) is said to be completion-acyclic (CA) iff each of ssb(G) and sea(G) is acyclic.

5. Main results

Things are not as simple with CODGs as with noDAGs. There are, it turns out, CODGs that are completion-acyclic, yet not oo-serializable. Our first result is to show that Example 2.2 above, as well as the following CODG, are in that situation:

Example 6

Since the number of structurally distinct documents that can possibly correspond to a 5-node graph is finite, we could exhaustively enumerate them and verify that none of them correspond to either Example 2.2 or to Example 6. However, that would not be very insightful.^[7] We will thus rather proceed by way of a lemma (5.9) that provides a general characterization of oo-serializable CODGs, and will be useful for our second main result.

5.1 Definition Let G = (V, ch) be a CODG. The ancestral precedence relation of G, denoted ap(G), is defined as:

It is easy to show that ap(G) is always a strict partial-order on V. Informally, we could say that ap(G) gets rid of the cycles in G by contracting its (maximal) strongly-connected components, then re-expanding them to an equal number of disconnected vertices.

5.2 Definition Let G = (V, ch) be a CODG. A root in G is a vertex r ∈ V for which:

5.3 Notation Let G = (V, ch) be a CODG. Unless otherwise stated, ap denotes ap(G).

The next result establishes that for any distinct roots v and w, either v and w are in the same strongly-connected component, or else v and w are unordered in each of ssb and sea.

5.4 Lemma Let G = (V, ch) be a CODG, and v and w two distinct roots in G. Then, either:

or

Note: For space consideration, most proofs are omitted.

Thus, an important difference between noDAGs and CODGs is that the latter can have unordered root pairs, whereas noDAGs have (by definition) their roots totally-ordered.

5.5 Definition A CODG G = (V, ch) is said to be sp-consistent iff gsp is an acyclic relation, i.e., iff:

Note that if G is truly a multi-graph, i.e., if some node occurs more than once as a child of the same parent, then G is certainly not sp-consistent. However, G could fail to be sp-consistent without being a true multi-graph, for example if two siblings are ordered differently by two distinct parents.

5.6 Definition A CODG G = (V, ch) is said to be reduced iff no node is both directly and indirectly reachable from some other node, i.e., iff:

Note that if there is a cycle in G, then it is not reduced.

5.7 Lemma If a CODG is sp-consistent, is reduced, and has a single root, then it is isomorphic to a noDAG; thus, by M2008, it is oo-serializable iff it is completion-acyclic.

5.8 Definition Let G be a CODG. A single-rooted extension (sre) of a G, is identical to G with an added root that has as children the roots of the original CODG, in some ordering, without repetition.

Note that, in general, a CODG has more than one sre (in effect, n!, where n is the number of roots in the original CODG, i.e., one for each possible ordering of the original roots).

5.9 Lemma A CODG is oo-serializable iff it has an sre that is oo-serializable.

Proof sketch. (←): Let G be a CODG, and H an oo-serializable sre of G. Let D be any serialization of H. Because H has only one root, and D corresponds to H, there must be a range in D that contains all the others. Thus, the first and last tag of H must be matching tags. By “removing” those tags from D, we obtain an oo-serialization of G.

(→): Let G be an oo-serializable CODG, and D any serialization of G. By “adding” a start-tag and a matching end- tag at (respectively) the beginning and end of D, we obtain a document that can be shown to correspond to some sre of G.

We are now ready to state our first main result:

5.10 Theorem There exist CODGs that are completion-acyclic but not oo-serializable.

Proof sketch. The theorem follows from the observations that:

By Lemma 5.7, none of Examples 2.2 and 6 has an sre that is oo-serializable. Thus, by Lemma 5.9, none of Examples 2.2 and 6 is oo-serializable.

Our second main result is easiest seen as a corollary to the proof of the preceding theorem. First, we define:

5.11 Definition A CODG is said to be fully-completion-acyclic (FCA) iff it has an sre that is completion-acyclic.

5.12 Theorem A CODG is oo-serializable iff it is fully-completion-acyclic.

Proof sketch. The theorem follows from the proof of the preceding theorem and the following lemma:

5.13 Lemma If a CODG is not sp-consistent or is not reduced, then it is not completion-acyclic.

6. Checking full-completion-acyclicity

An obvious way to check whether a CODG is fully-completion-acyclic is to try out all possible sres and see if at least one is completion-acyclic. From a completion-acyclic sre, it would be easy to derive an oo-serialization of the CODG. However, since there are n! different sres to check (where n is the number of roots in the CODG), this can be very inefficient. It would be nice to be able to check whether a CODG is fully-completion-acyclic without having to generate all possible sres.

It turns out it suffices to check each pair of roots for a particular condition which is verifiable in polynomial time. Since there are n × (n - 1) / 2 root-pairs and checking the condition can be done in polynomial time, it follows that full-completion-acyclicity can in fact be checked in polynomial time.

The condition to be checked is as follows.

6.1 Definition Let r and s be two roots of some CODG G = (V, ch) that are unordered with respect to ssb(G). We say that r must precede s, noted r ↝ s, iff there exist vertices x and y standing in either (or both) of the following configurations with respect to r and s:

Root-pair configuration 1

Root-pair configuration 2

Here, the double-arrows represent the reachability (⇒) relation, not just parent-child relationships. The red double-arrow (with a stroke through it) means the complement of ⇒ (thus, in Configuration 1, s ⇏ x). It does not matter whether or not r ⇒ y (resp. s ⇒ x) in Configuration 1 (resp. Configuration 2). In other words, at least one of r ⇏ y and s ⇏ x must be the case. The dotted green arrow means that (x, y) ∈ (ssb − ⇒), in other words, that x precedes y without being an ancestor of it.

An instance of at least one of those configurations is found in each of the following CODGs:

Example 7

Example 8

Example 9

6.2 Lemma Let G be a CODG, and r and s be two roots in G such that r ↝ s. Then, for each H that is a CA sre of G, (r, s) ∈ gsp(H).

Proof sketch. If there exists no CA sre of G, or if there are no two roots r and s in G such that r ↝ s, then the lemma is vacuously verified. Let thus H be any CA sre of G and, for the sake of contradiction, suppose r and s are two G-roots such that r ↝ s and such that (r, s) ∉ gsp(H). Suppose x and y are two vertices as in Configuration 1 above (we prove only the case of Configuration 1; that of Configuration 2 is proved similarly).

By the definition of sre, if (r, s) ∉ gsp(H), then it must be the case that (s, r) ∈ gsp(H), and thus, by construction of ssb(H) (Definition 4.3-2), that (s, r) ∈ ssb(H). Hence, it follows by Lemma 4 of M2008 and the fact that r and s do not stand in ancestor-descendant relationship (being both G-roots, they are ⇒-incomparable), that (r, s) ∈ sea(H). Similarly, from (x, y) ∈ ssb(H) and x ⇏ y, and y ⇏ x (because (x, y) ∈ ssb(H)), we conclude that (y, x) ∈ sea(H).

Now, by construction of sea(H) (Definition 4.3-4), and from the facts that r ⇒ x, that (r, s) ∈ gsp^-1(H), and that s ⇏ x, we conclude that (x, s) ∈ sea(H). So, we have (y, x) ∈ sea(H) (established earlier), and (x, s) ∈ sea(H), and (s, y) ∈ sea(H) (because s ⇒ y). Thus, sea(H) is cyclic, contrary to our hypothesis that H is CA, and so we must reject the hypothesis that (r, s) ∉ gsp(H), and conclude that (r, s) ∈ gsp(H).

QED

6.3 Theorem A CODG is FCA iff it is CA and it does not have any two roots r and s such that r ↝ s and s ↝ r.

Proof sketch.

(⇒) Any FCA CODG is CA. If a CODG had roots r and s such that r ↝ s and s ↝ r, then by Lemma 6.2, it would have a cycle in ssb, and thus could not be CA.

(⇐) Let G be a CA CODG in which no two roots r and s are such that r ↝ s and s ↝ r. Note that by Lemma 5.13 and the fact that G is CA, we know that G is sp-consistent and reduced, and will thus take this for granted.

We give an algorithm for constructing an ordering of the roots of G that can be used as the root-order in a sre H of G which will be shown to be FCA. In the algorithm, ssb(G, ROR) denotes the result of building ssb as per Definitions 4.3-1 and 4.3-2, but using gsp(G) ∪ ROR instead of gsp(G)

Algorithm:

The intuition behind the algorithm is best conveyed with examples. Essentially, the algorithm goes like this: start with the root-orderings that are imposed by the topology of the CODG, i.e., those pairs of roots (r, s) for which r ↝ s. Then, for the other root-pairs, they can basically be ordered randomly, as long as no silly decision is taken.

To see what silly decisions would be, consider Example 10. A silly decision would be to stick root r between s and t. To avoid such decisions, the root-ordering must be built gradually, considering one by one (the order does not matter) the unordered pairs of parents of the same children. For each such pair (x, y), decide of an arbitrary order, then, make sure all roots reachable upwards from x come before all those reachable upwards from y (there can be no root reachable both ways, otherwise, x and y would have been ordered to start with).

Each time such root-orderings are added, the consequences on the global ordering of the CODG are recomputed and propagated down from the roots.

Example 11 provides a more intricate example, in which eight possible pairs of unordered parents of the same children exist: (u, w), (u, x), (v, w), and (v, x), and their inverse. Whichever pair is chosen, it will result in roots r and s being ordered at step 3b, and then, in all eight pairs being ordered at step 3c.

Examples 12 and 13 show that the addition of a leaf can cause some root-pairs to be ordered from the start: (r ↝ s) and (r ↝ t) in Example 12; (r ↝ s) in Example 13.

Example 10

Example 11

Example 12

Example 13

Proof sketch of termination: At each turn, at least one pair of the kind sought for in (3) is ordered. Indeed, it can be shown that the chosen pair (x, y) causes arcs to be added to ROR that will necessarily order the pair (x, y) itself. Thus, eventually, no pair satisfying the WHILE clause will remain.

Proof sketch that ROR orders all pairs of roots: The existence of an unordered root-pair implies that there is a pair satisfying the WHILE clause. Thus, when no more such pair exists, all the roots have been ordered.

Proof sketch that ssb(G, ROR) is acyclic: Any condition that might cause a cycle would also cause a cycle in { (r, s) | r and s are roots in G and r ↝ s }, a contradiction.

A rough analysis of the algorithm shows that its running time is polynomial (probably with degree at most 3 or 4). Obviously, it could be used to actually build a CA sre of any FCA CODG, and thus an oo-serialization of the CODG. This establishes a polynomial upper-bound on the task of verifying full-completion-acyclicity and of generating an oo-serialization of a FCA CODG. While interesting, we do not believe these upper-bounds to be tight, and hence consider the exact complexity of these tasks to be open questions.

7. Conclusion and future work

In this paper, we defined a class of graphs, child-arc-ordered directed graphs (CODGs), that includes multi-graphs and non-acyclic graphs, and investigated the conditions under which a CODG is “oo-serializable”, i.e., has a structure which corresponds to that of an overlap-only marked-up document. We found that the property of completion-acyclicity does not guarantee oo-serializability in general for CODGs, by showing that there exist completion-acyclic CODGs that are not oo-serializable. By contrast, Marcoux has shown that for the less general class of node-ordered-DAGs (noDAGs), completion-acyclicity does guarantee oo-serializability M2008.

We then defined a condition strictly stronger than completion-acyclicity, full-completion-acyclicity, and showed that it does guarantee oo-serializability for all CODGs.

Finally, we presented polynomial-time algorithms for checking full-completion-acyclicity and for computing an oo-serialization of fully-completion-acyclic CODGs. However, we do not believe these algorithms to be optimal. Thus, open questions include determining the exact complexity of — and finding optimal algorithms for — checking completion-acyclicity, full-completion-acyclicity, and of actually computing an oo-serialization of a CODG once it is found to be serializable.

Another area of research we hope to pursue in the near future is investigating whether and how some forms of interrupted and virtual elements, as found in TexMecs, can be characterized in terms of graphs.