Balisage Paper: It’s more than just overlap: Text As Graph^[1]

Overview

The Text As Graph (TAG) data model consists of a directed property hypergraph for modeling text, markup (roughly comparable to XML elements), and annotations (roughly comparable to what XML attributes would be like if they could contain markup, including attributes on attributes). A hypergraph consists of a set of nodes and a set of edges and hyperedges. Nodes and (hyper)edges may have properties, including type (see, for example, the four types of nodes listed below).

Graph models for text and markup have been proposed before (GODDAG [see, e.g., Sperberg-McQueen and Huitfeldt 2000], GrAF [see, e.g., Ide and Suderman 2007]), but the model advanced in this paper differs from those because it incorporates a hypergraph [Hypergraph: Wikipedia]. Hypergraphs are especially valuable for text modeling because they can be implemented using sets, and methods for reasoning over and operating on sets are proven and well known [Set: Wikipedia]. Hypergraphs differ from traditional graphs, the edges of which can connect only two nodes with each other, because the edges in a hypergraph can connect more than two nodes with one another, and for that reason they are called hyperedges. Hypergraphs can have directed and undirected hyperedges, and TAG uses only directed hyperedges, which assert a directed relationship between two non-empty sets of nodes, one for the source (called the head) and one for the target (called the tail). As we explain below, in the TAG model, the directionality of a hyperedge may be used for purposes other than modeling an order or a hierarchy of the nodes.

Like LMNL and GODDAG, both of which are discussed in more detail below, and unlike XML, TAG is defined as a data model, rather than by its syntax. At present TAG does not have its own syntactic representation.

TAG example

Figure 1: William Shakespeare, Sonnet 71

The Document node is beige, the Text nodes are pink, and the Markup nodes are green (those with the name property value of quatrain or couplet) and cyan (those with the name property value of line). A chain of regular (one-to-one) edges, represented by solid black arrowheads, begins at the Document node and connects the Text nodes in order. Text nodes in this case are entire lines of text, but they could also be smaller units; see the discussion of Overlap, below. There are additional whitespace-only Text nodes between the lines, but these have been omitted here to reduce the complexity of the diagram.

The illustration of a TAG hypergraph of William Shakespearea’s Sonnet 71 (Appendix A), above, includes a Document node, fourteen Text nodes (as noted above, there are also white-space-only Text nodes between the lines, but these have been omitted here to reduce the complexity of the diagram), and eighteen Markup nodes (fourteen with their name property value equal to line, three to quatrain, and one to couplet). Regular (one-to-one) edges start at the Document node and chain all Text nodes in textual order. Hyperedges point from the Markup nodes into sets of Text nodes. In this case, hyperedges that start in Markup nodes with the name property of line happen to point to a set that consists of a single Text node, and those with name property values of quatrain and couplet happen to point to sets of four and two Text nodes, respectively. Note that in TAG, in contrast to XML, a Markup node corresponding to the XML root element, although permitted, is not required, and we’ve omitted it here. Also in contrast to XML, the quatrain and couplet Markup nodes point directly to the Text nodes, and not to line Markup nodes (although that, too, is possible; see the discussion of hierarchy below).

How TAG represents selected structural properties of text

This section describes in an introductory way how TAG represents order, textual content, markup, overlap, and discontinuity. Some of these issues are taken up in more detail later, after we introduce the types of nodes, edges, and hyperedges that make up the TAG model of text.

TAG components

Overlap

The challenge to text modeling in XML that has attracted the most attention is overlap. For example, notice in the image below how the phrase Two vast and trunkless legs of stone Stand in the desart begins in the middle of line 2 and ends in the middle of line 3, an absence of synchronicity between verse lines and sentences that is called enjambment.^[22] :

Figure 2: Percy Bysshe Shelley, Ozymandias

[Image from http://piez.org/wendell/papers/dh2010/clix-sonnets/ozymandias-map.svg, which is part of Piez 2010. The overlap is easier to see in the original SVG, which is animated, and highlights portions of the document in response to mouse events.]

Piez’s illustration is actually of LMNL ranges, rather than of XML element trees. The same structure might be visualized as independent overlapping trees as follows, where cyan represents the tree of metrical lines and green represents the tree of linguistic phrases:

Figure 3: Percy Bysshe Shelley, Ozymandias

Projecting two independent trees over a common set of words. In XML the individual words would not be children of <line> and <phrase> elements, and would instead be grouped inside Text node children of those elements.

Because it is not possible to represent the preceding structure in XML markup, the following pseudo-XML is not well-formed:

<line><phrase>Who said —</phrase> <phrase>“Two vast and trunkless legs of stone</line>
<line>Stand in the desart….</phrase> <phrase>Near them,</phrase> <phrase>on the sand</phrase></line>

New XML users often misunderstand the prohibition against overlap as a prohibition against overlapping tags, but if that were the entire issue, it could be remedied by simply removing the syntactic prohibition. But the rule about tags exists because tags must represent a tree, hierarchy in a tree prohibits multiple parentage, and overlap would permit a node to have more than one parent. Overlap is possible in GODDAG only incidentally because TexMECS permits overlapping tags; at a higher level it is because GODDAG permits Text nodes to have multiple parents and TexMECS serializes the GODDAG model. LMNL sawtooth syntax may look like XML syntax with the prohibition against overlapping tags removed, but the real difference is at the level of the data model: LMNL ranges can overlap and XML elements cannot because the content between XML start and end tags is a sequence of descendant nodes in a tree, and not a range of textual atoms.

TAG represents overlap naturally because the TAG counterpart to an XML element is a directed hyperedge that associates a head Markup node with a set of tail Text nodes. To tag a line of poetry in the example above, TAG would create a hyperedge from a Markup node with the name property value of line (comparable to a <line> element in XML) to a set of Text nodes (comparable to Text nodes in XML). Sets are unordered, but because the TAG model requires sequence edges between Text nodes, which record the continuous order of the text stream (comparable to the sequence of atoms in the LMNL model), the textual content of the line is fully specified by (= can be retrieved by examining) the membership of the set of tail Text nodes and the sequence edges between them. In the illustration below, the black arrows represent regular edges that connect Text nodes in order, the irregular colored bounding lines demarcate the sets of tail Text nodes, and a similarly colored arrow points into them from their Markup node heads:

Figure 4: Percy Bysshe Shelley, Ozymandias

A hypergraph representing overlap of phrases and metrical lines.

Additional use cases involving overlap challenges in XML include pages vs paragraphs in publications of novels, folios vs texts in medieval manuscripts, and speeches vs metrical lines in drama. Overlap in poetic structures has been explored in detail in Piez 2014, which also discusses an unusual structural paradox involving Chapter 24 of Mary Shelley’s Frankenstein. Overlap involving word and metrical foot boundaries in poetry is discussed below.

Discontinuity

Sperberg-McQueen and Huitfeldt 2008b offer the following paragraph from Lewis Carroll’s Alice in Wonderland as an example of discontinuity:

There is no way to mark up this passage in XML without fragmenting the quotation into two elements (and relying on semantics to stitch together the pieces in the application layer), yet our human intuition is that there is a single quotation, and that the model, therefore, should represent it as a single object.^[23] As Sperberg-McQueen and Huitfeldt 2008b also observe, there is a sense in which book and without are adjacent and a different sense in which book and thought are adjacent. XML syntax and the XML tree cannot represent both of these realities simultaneously, which means that at least one of them must be handed off to the application layer.

Sperberg-McQueen and Huitfeldt 2008b situate this type of structure in a GODDAG context, where it intersects with the distinction between containment and dominance. Concerning LMNL, they write that

Piez 2008 describes discontinuity in LMNL as modeled by the limen, where the example provided (http://piez.org/wendell/LMNL/Amsterdam2008/presentation-slides.html#page23) records it through coindexed annotations. That dependency seems to locate discontinuity in an application layer, since whether coindexed annotations represent discontinuity is not an inherent property of the coindexing. As was noted earlier, TexMECS is capable of modeling discontinuity directly with suspend-tags and resume-tags, but if a TexMECS document is to be parsed into GODDAG, the fragments are then modeled as separate structural components

TAG prioritizes the representation of text structures, including discontinuity, in the model, without dependency on application-layer semantics. The example from Alice in Wonderland described above would have the following form in TAG:

Figure 5: Lewis Carroll, Alice in Wonderland

Each hyperedge points from a Markup node head (identifying the type of text structure) to a tail set of Text nodes. Normal edges connect the Text nodes in order. In the TAG model, then, a discontinuous textual object is represented the same way as a continuous one, as an ordered set of Text nodes that form the tail of a Markup-to-Text hyperedge.^[24]

Other examples of discontinuity involve stage directions in dramatic text, such as the following example from George Bernard Shaw’s Mrs. Warren’s profession:

Here the last four stage directions interrupt not just the speech, but the sentences in which they occur.

Hierarchy, containment and dominance

The challenges that have emerged from our experience of XML as a model of text involve not only the limitations of OHCO, but also its tyranny. If text is understood as an Ordered Hierarchy of Content Objects, are there aspects of text that are not ordered (O), are there aspects that are not hierarchical (H, by which we mean not just that they are not mono-hierarchical, but that they are not hierarchical at all), and does the model create content objects artifactually, that is, where they are not perceived as inherent properties of the text being modeled (CO)? XML requires us to model all content as both ordered and hierarchical, and it represents content objects as elements (at least as content objects are described in DeRose et al. 1990). GODDAG and LMNL both grew out of a recognition that not all properties of text can be modeled effectively as a single hierarchy, and their focus is not limited to that issue, but they differ in the extent to which they interrogate features of text that may not be hierarchical at all, that may not be ordered, and that may not involve what a human would consider a content object.

As was mentioned earlier, the XML data model does not distinguish containment from dominance, which Tennison explains and illustrates in LMNL terms as follows:

In XML, an ancestor element both contains (starts before and ends after in the serialization) its descendants and dominates them (is connected to them by a path that travels only downward in the tree). In the XML view below of the Shakespearean sonnet the we used as a TAG example above, the <poem> element both contains and dominates three <quatrain> elements and one <couplet> element, and the <quatrain> and <couplet> elements both contain and dominate <line> elements:

<poem>
    <quatrain>
        <line>No longer mourn for me when I am dead</line>
        <line>Than you shall hear the surly sullen bell</line>
        <line>Give warning to the world that I am fled</line>
        <line>From this vile world with vilest worms to dwell:</line>
    </quatrain>
    <quatrain>
        <line>Nay, if you read this line, remember not</line>
        <line>The hand that writ it, for I love you so,</line>
        <line>That I in your sweet thoughts would be forgot,</line>
        <line>If thinking on me then should make you woe.</line>
    </quatrain>
    <quatrain>
        <line>O! if,—I say you look upon this verse,</line>
        <line>When I perhaps compounded am with clay,</line>
        <line>Do not so much as my poor name rehearse;</line>
        <line>But let your love even with my life decay;</line>
    </quatrain>
    <couplet>
        <line>Lest the wise world should look into your moan,</line>
        <line>And mock you with me after I am gone.</line>
    </couplet>
</poem>

Figure 6: William Shakespeare, Sonnet 71

The XML tree encodes containment and dominance in the same way.

In the earlier TAG example of this sonnet, a Markup-to-Text hyperedge defines the tail as a set of Text nodes and labels (datatypes) it. In the TAG version of this example, all quatrain, couplet, and line Markup-to-Text hyperedges point to sets of Text nodes, and containment is modeled by subset relations among the Text-node tails of those hyperedges. Where the Text nodes that constitute the tail of a Markup-to-Text hyperedge with the name property (on the Markup node) of line form a proper subset of the Text nodes that constitute the tail of a Markup-to-Text hyperedge with the name property (on the Markup node) of quatrain, the quatrain contains the line, and the same is true of the relationship between couplets and lines.^[26] In this emphasis on containment, rather than dominance, TAG is similar to flat LMNL, except that LMNL ranges must be continuous (LMNL handles discontinuity separately), while contiguity is not relevant in defining the set of Text nodes that may serve as the tail of a hyperedge in TAG (see the discussion of Discontinuity, above). In the TAG version we have chosen not to make the three quatrains and the couplet what in XML terms would be children of a root <poem> element, but we could, should we wish, create a Markup-to-Text hyperedge with a name property value (on the Markup node) of poem. This could point, through a hyperedge, to the set of all Text nodes in the poem, which would let us model containment. It could also serve as the head of a Markup-to-Markup hyperedge from it to the Markup nodes with quatrain and couplet name property values, which would let us model dominance.^[27] In other words, Markup-to-Text nodes model containment, rather than dominance (indirectly, through subset properties of the Text nodes to which they point), and where it is important to distinguish dominance from containment, the TAG model supports this through Markup-to-Markup hyperedges.

One final consequence of the XML conflation of containment and dominance is that when exactly the same text must be tagged in two ways simultaneously, XML requires one of the elements to contain the other. But, as was noted above, if a Markup node with the name property value of paragraph and a Markup node with the name property value of quotation both point to exactly the same set of Text nodes, in TAG it does not make sense to ask whether the paragraph contains the quotation or the quotation contains the paragraph because containment in TAG is defined as a proper subset relationship among sets of Text nodes. Whether a paragraph consists of a quotation or a quotation consists of a paragraph is a reasonable question, but in TAG it is a question of dominance, expressed through Markup-to-Markup hyperedges, and not of containment, expressed (indirectly) through Markup-to-Text hyperedges.

Artifactual hierarchy

As we described above, markup in XML is (among other things) a form of datatyping, and the XML spec uses the word type explicitly in this meaning:

<title><name>Romeo</name> and <name>Juliet</name></title>

Figure 7: Romeo and Juliet (XML)

In XML, the three words of the title are spread over two levels of the hierarchy. Cyan ellipses are element nodes and pink rectangles are Text nodes.

If we wish to specify in XML that the first and third words of the title are of type name, we can tag them as elements of that type, with the result that the Text nodes they contain wind up on a different level of the hierarchy than the conjunction between them.^[28] This contradicts our intuition that the title contains three words, two of which have the type name, replacing it with a model in which the title contains two objects of type name with a word between them, and it is the name objects that contain the first and third words.

Because TAG separates the use of markup in hierarchy and its use for datatyping, it is possible to assign a type to text without distorting the hierarchy. Here is the TAG representation of the same content:

Figure 8: Romeo and Juliet (TAG)

In this TAG example, the markup on names specifies their type and content without imposing a hierarchy. The title contains three text nodes, represented by pink ellipses. Markup nodes are green (for names) and cyan (for titles), and the document node is beige.

As illustrated in the example above, markup of Text nodes in the TAG model, unlike in XML, does not create a hierarchical layer as a side effect of datatyping. As we have seen earlier, it is possible to represent hierarchy in TAG, but it is not an inescapable consequence of all markup, as it is in XML.

White space as crypto-overlap

In natural language processing, tokenization is the process of breaking up a string of plain text characters into substrings (typically words and punctuation, which may be adjacent or separated by white space), often while removing token separators in the process. Tokenization of plain text when processing XML is commonly performed using regular expressions and the tokenize() function, but tokenize() atomizes its first argument, which means that it cannot be used on tagged text without losing the markup in the process. Even tokenization that would not create overlap-based well-formedness violations, such as splitting and tagging the words of a line of poetry in which the stressed vowels are tagged as <stress> (see the illustration below), requires intermediary temporary manipulations, such as converting the markup to text, tokenizing with tokenize(), and then converting the temporary text back into markup, or adding additional markup, tokenizing with <xsl:for-each-group>, and then removing the temporary markup.

The reason tokenizing tagged text is awkward in XML even where overlap is not a risk has one explanation in terms of the syntax and another in terms of the data model. In terms of the syntax, the markup and text are intertwined in a way that makes it impossible to ignore markup during tokenization while retaining access to it after the process is complete. In terms of the data model, as noted above, tagging the stressed vowels in a line of verse pushes their textual content down a level in the hierarchy, so the line no longer forms a string. Furthermore, although it is not usually described this way, the use of white space to separate words may be understood as pseudo-markup, which means that the words in tagged text potentially represent overlapping hierarchies in plain-text disguise.^[29]

In TAG, however, Markup nodes on one layer point to Text nodes on another layer, one that contains nothing but Text nodes, which makes it possible to tokenize the text without interference from the markup. The tokenization splits larger Text nodes into smaller ones, but they remain in the tail of their old Markup-to-Text hyperedges, while new Markup-to-Text hyperedges are added to tag the new individual words. In the simplified illustrations below, we have created a poem that consists entirely of a single three-word line (No longer mourn). In the first of these illustrations, the stressed vowels are tagged but the words are not:

Figure 9: A simplified poem without word tokenization

Without word tokenization, there are five Text nodes, three of which are not marked up individually and two of which form the tails of Markup-to-Text hyperedges with a name property of stress on the Markup node, indicating that these are stressed vowels.

Because stress is marked on a single vowel sound, XML would be capable of tagging the individual words while retaining the stress markup, since no overlap would result. For that reason, the following XML representation, which tags both words and stressed vowels, is well formed:

<line>
  <word>No</word>
  <word>l<stress>o</stress>nger</word>
  <word>m<stress>ou</stress>rn</word>
</line>

Yet if we try to use tokenize() in a transformation to add the <word> markup to a line that already contains the <stress> markup, the <stress> markup will be lost during atomization.

This situation is not a challenge for TAG. In the example below, we have added Markup-to-Text nodes to tag the words, which can be determined by tokenizing the text on white space. Tokenization is possible because the Text nodes are not interrupted by the markup, which points to them without being inserted between them (syntactically) and without pushing them to different levels of the hierarchy (in the tree structure):

Figure 10: A simplified poem with word tokenization

With word tokenization, there are now seven Text nodes. Two of them still form the tails of Markup-to-Text hyperedges with a name property of stress on the Markup node, indicating that these are stressed vowels. There are now also three Markup-to-Text hyperedges with a name property of word on the Markup node (in orange); the first points to a single Text node, and the others each point to three Text nodes.

The additional markup requires additional division of Text nodes, but all modifications are local, and the only part of the graph that has to be updated is the part to which the markup is being added.^[30]

The preceding example does not create overlap because the Text nodes that are marked up for stress are subsets of those that are marked up as words. But if we also want to tag poetic feet, which are needed to identify caesura (a regular coincidence of word and foot boundaries in the lines of a poem), overlap would become an issue in XML. One work-around in an XML environment has turned out to involve, surprisingly, tagging neither the feet nor the words (see Birnbaum and Thorsen 2015), deriving both from other properties of the line during processing, but the fact that we can use white-space pseudo-markup to escape the consequences of syntactic overlap doesn’t mean that the the overlap isn’t there. A data model that can represent both feet and words explicitly, and that could identify caesura as a relationship between those two types of structural components, would represent explicitly the human understanding of caesura, and the explicit representation of structure is much of what markup is all about. In the illustration below, we have added foot markup to the previous example:

Figure 11: A simplified poem with word and foot markup

When we tag the feet by adding Markup-to-Text hyperedges with a name property value of foot on the Markup node (in violet), we create overlap between feet and words, since the word longer is split between the ictic second syllable of the first iamb and the non-ictic first syllable of the second.

A corresponding XML-like structure that tags words and feet would not be well formed because the <foot> elements would overlap with the <word> elements:

<line><foot><word>no</word><word>lon</foot><foot>ger</word><word>mourn</word></foot></line>

In XML, [t]he identification of caesura requires the identification of both feet and words, which are not coextensive and which frequently overlap. The challenge, then, is to locate where foot and line boundaries coincide without employing markup in a way that would violate well-formedness overlap constraints. [Birnbaum and Thorsen 2015] In TAG, where overlap is not an issue, caesura is possible when two adjacent Text nodes are in the tails of different Markup-to-Text word hyperedges and different Markup-to-Text foot hyperedges. Caesura is typically 1) at or near the middle of the line, and 2) implemented consistently, so not every coincidence of word and foot boundaries proclaims a caesura; that coincidence is necessary, but not sufficient.

Scope of reference

Footnotes can be understood as annotations on text, but in XML they are typically represented by elements at the location where the note reference should occur in a reading text, as with the <footnote> element in DocBook or the <note> element in TEI. Anchoring a footnote at a point in the text stream, instead of as an annotation on a string of (possibly tagged) text with a beginning and an end, is problematic because it does not mark explicitly the scope of the note, such as whether a footnote reference at the end of a paragraph points to the preceding sentence or the preceding two sentences or more, or to the entire paragraph. The TEI <note> element avoids this limitation because it can point to an arbitrary target with XPointer, but this stand-off strategy is an indirect way of specifying what might have been represented more immediately as an attribute if XML attributes were able 1) to model rich content, and 2) to annotate something without being forced to give it a generic identifier that specifies its type.^[31]

TAG avoids the XML prohibition against markup in attribute values because in TAG the Text nodes of an annotation can be a target of markup, just like those of the main text. TAG avoids the scope of reference problem because the annotation can point to a Markup node with a name if an appropriate one exists (such as paragraph in a document that marks up paragraphs). In the example below, because TAG permits anonymous Markup nodes (that is, because the name property of Markup nodes is optional), we annotate arbitrary text without giving it the equivalent of an XML generic identifier, although in a revision currently under development, we are exploring pointing directly from the annotation to the Text nodes, which would obviate the need for the anonymous Markup node. With either of these approaches, footnote-like relationships can be modeled in TAG as what they are: rich-text annotations on text regardless of whether the target of the annotation corresponds to a Content Object with an identifiable type. TAG is similar to LMNL in this respect, except that in TAG text being footnoted that is discontinuous is no different from continuous text; it is a set of Text nodes that constitute the tail of a Markup-to-Text hyperedge.

In the simplified example below, we add a footnote to the second and third lines of a poem by using an Annotation node (orange) to point to a Markup node (violet) that is the head of an anonymous Markup-to-Text hyperedge, and the text of the annotation also has markup (a sky blue Markup node with a name property of emphasis points to a single Text node). Neither of these features is available with attribute markup in XML because elements must have generic identifiers (= cannot be anonymous) and attribute values cannot contain markup. And if the footnote target happens to be something that would create overlap in XML (e.g., if it runs from the middle of one line to the middle of another and the lines have been tagged explicitly), XML is further encumbered by the prohibition against overlap.

Figure 12: A poem with an annotation (footnote) on lines 2 and 3

The violet ellipse is an anonymous Markup node that serves as the head of a Markup-to-Text hyperedge and points to the Text nodes for lines 2 and 3 of the poem. The orange ellipse is an annotation on the anonymous Markup node. Annotations have their own textual content, which is represented by a chain of Text nodes that begins with the Annotation node, much as the main text is represented by a chain of Text nodes that begins with the Document node. The text of an annotation may be the target of markup, and in this example a Markup-to-Text hyperedge with a name property of emphasis on the Markup node points to a single Text node.

Insofar as a footnote can be considered metadata about text, the structure illustrated above represents it as an annotation, but it does not require us to assign a type to the target of the annotation as a side effect of referring to it, and it allows us to add markup to the footnote text itself.

Data model versus syntax

Syntax is not necessarily the same as a data model. A data model could, at least in principle, be serialized in multiple ways, and syntax developed to represent one data model could be coopted to represent a different one. TAG does not at present have its own serialization syntax, and the Alexandria Markup implementation described below can read and write LMNL sawtooth syntax and TexMECS (parsing the results as a representation of the TAG data model, rather than of LMNL or GODDAG), and it is intended to be able to do the same with XML syntax.

One challenge of comparing TAG to XML, LMNL, GODDAG, and TexMECS is that TAG, like LMNL and GODDAG, is a data model, while XML and TexMECS are defined by their syntax. Perhaps a bit surprisingly in the context of Balisage, which describes itself as the markup conference, our focus here is not on markup (that is, on syntax and serialization), but on the data models that may be expressed through markup, which means that for comparative purposes we may sometimes need to infer a data model from a syntactic specification.

The situation is especially complicated in the case of XML because although it does not have a data model, it also has three almost-data-models: XML DOM [W3C DOM], which is an object model and API; the XML InfoSet [W3C XML InfoSet], which is an information model; and XDM [W3C XDM], which is a data model for processing XML. Our inferred data model for XML for comparative purposes here includes the seven node types specified in XDM (not the twelve of XML DOM or the eleven types of information items of the XML InfoSet), along with the structural properties of the ordered tree that are relevant for understanding (but not necessarily adequate for processing) well-formed XML (e.g., attribute nodes on an element are unordered). Our aim is not to create a data model for XML, which lies far outside the scope of this paper, but to identify features of the way XML models text that can be used comparatively to help elucidate features of TAG.

The fact that some of our objects of comparison are serializations and others are data models matters because, as the etymology of the term implies, serialization is an ordered linear expression, which is not a requirement of data models. If, for example, a paragraph is exactly coextensive with a quotation, in XML syntax, LMNL sawtooth syntax, and TexMECS syntax, the start tag of either the paragraph or the quotation must come first in linear order. But in LMNL the relative order of the ranges defined by the tags is not an obligatory part of the model, which permits two ranges to begin at the same location in the text, and the same is true of TAG. In XML, however, one element must be the parent of the other, and the order of the start tags reflects both containment and hierarchy. TexMECS negotiates this issue by using different start- and end-tag delimiters to distinguish when the relative order of the tags is informational and when it is not.^[32]

Semantics versus application level

Another challenge for text modeling involves distinguishing properties that inhere in the structure of the text being modeled from those that depend on semantics that must be interpreted at a higher (application) level. A failure to make this distinction may have two types of consequences (which are really aspects of the same thing, the delegation of information that should be part of the model to the application layer): either the application must know that some properties of the model are not informational and are to be ignored, or the application must know that there is information that is not represented entirely by the model and must therefore be added during processing. If, however, the model explicitly represents the structural properties of the text and nothing else, the application level is freed from having to supplement the model, and can concentrate on features that are truly application-specific.

Moving structural information out of the application layer and into the model is a priority in the design of TAG, and here are two illustrations of the issue:

Concerning the first of these issues, matching up pseudo-start-tags with pseudo-end-tags during processing does not arise in TAG not only because TAG does not at present have its own syntactic expression (although we can represent some features of TAG by borrowing LMNL sawtooth syntax or TexMECS), but also because the fact that TAG permits overlap makes such workarounds unnecessary. The second issue is more challenging, and because TAG currently models text as a single chain of Text nodes, it does not yet distinguish situations where order is not informational. But because that is a feature of what text is (that is, because the first O of OHCO is as much an issue as the H that follows it), it is a design requirement that we intend to address as development continues (see Appendix B).

Importing documents into Alexandria

Exporting from Alexandria Markup in sawtooth syntax

As an example of exporting a simple document from Alexandria Markup, a serialization of the TAG data model into LMNL sawtooth syntax involves traversal over an instance. The traversal begins with the Document node, which must have a single directed regular edge that points to the first Text node. We then follow the Markup-to-Text hyperedges that are connected to this Text node.^[33] There can be zero or more Markup-to-Text hyperedges on a Text node, each of which is headed by one Markup node. The traversal collects all the Markup nodes that point to the Text node, and for each of them it writes a start tag, where the order of multiple start tags is not part of the TAG model, and is therefore at the discretion of the implementation. We then proceed to the next Text node by following the outgoing regular Text-to-Text edge, which connects all Text nodes (except those on annotations) in a single chain. As before, we collect all Markup nodes connected to the new Text node, and we then calculate the differences between the sets of Markup nodes that point to the two Text nodes under consideration. For the intersection we do nothing; for the set of Markup nodes that are only on the previous Text node we write end tags; and for the set of Markup nodes that are only on the new Text node we write start tags. At the conclusion of the traversal (which can be recognized because only the final Text node does not have an outgoing regular edge), we write end tags for all associated Markup-to-Text hyperedges.

TAGQL: A query language for TAG in Alexandria Markup

The Alexandria Markup query language for TAG, which is currently in an early stage of design and implementation, uses an SQL-like syntax. For example:

The query language operates on sets of nodes and edges. Below are some concise examples of how such queries might operate in terms of the model, which at that level involves a traversal of the Text nodes, since those are the only ordered part of the model. This naïve approach would not be performative and would not be implemented directly; a TAG application, like any database of any type, would employ indices, alternative data structures, caching, and other features that are not part of the model, but that can be used to maximalize performance.^[34]

The Alexandria Markup server API

The Alexandria Markup server has a REST API, which includes the following:

Java/Python clients

There are clients in Java and Python that, given the URL of an Alexandria Markup server, can connect to it in a way that hides the details of the REST protocol. The client code handles the setting of the required HTTP headers, the formatting of the input and the interpreting of the results.