Balisage Paper: Ariadne's thread

Arras

In 1980, an associate professor of English at Pennsylvania State University published a book about James Joyce's Portait of the Artist as a Young Man (Smith 1980). In order to identify, trace, and visualize the appearance, repetition, and recurrence of various complexes of images in the work, the author, John B. Smith, had created what might be called an interactive concordance system. Like a printed concordance, his tool allowed him to look for all occurrences of a given word and see them in context. Unlike a printed concordance, Smith's tool was interactive. It allowed the user to specify how much context to give when displaying a word: three words on either side? One word before and five after? The full sentence? The typographic line? Three lines? It also allowed the user to search for multiple words occurring in proximity: fire and ice in the same paragraph, for example.

Smith's system was initially called Rats (Random-Accessible Text System), but he later changed the name to Arras, for which the retronym ARchival Retrieval and Analysis System was formed.^[2] The Arras reference manual is available on the web site of the computer science department at the University of North Carolina at Chapel Hill, to which Smith moved from Penn State in the mid-1980s, and interested readers are encouraged to consult it (Smith 1985). A few sample queries, mostly drawn from the manual, will suffice to illustrate some of the program's salient capabilities.

The core functionality is to display occurrences of words, in context. The following command displays occurrences of the word fire in the default context of one sentence.

display concordance: fire.

In an attempt to make the system easier to use, Smith allows noise words, which are ignored, and allows keywords to be abbreviated. So the command just given could also be given in these and other alternative forms

please display a concordance for the word: fire.

disp conc: fire.

A different amount of context can also be specified, for example five words on either side:

display concordance: fire; context: -5 to 5 words.

To allow the user to identify images like those of fire or water, Arras allows the user to define categories, which in the simple case are just sets of word forms. To find all images of fire, a user might specify a number of word forms related by etymology or only by meaning:

define category: enflaming, fire, fireconsumed,
  fires, flame, flamed, flames, flaming,
  heat, heated, hot, hotly;
  name: firecat.

Another facility is the ability to define a configuration, which matches a word occurring within a specified proximity of another word.

configuration:  fire & water; name: ffww.

configuration:  fire &~ water; name:  ff.

configuration: fire | water; name: fw.

Names of categories and configurations can be used wherever word forms are called for in a command. This allows definitions of complex constellations of words to be built up step by step.

configuration: firecat & watercat;
  context: -50 to +50 words;
  name: fwcat.

The Arras scanner relied on simple markup in the input to know where volume, chapter, and paragraph boundaries fall. Line and sentence boundaries it recognized by itself using simple rules, with markup available for overriding the default decisions.

The text model exposed by Arras is essentially that of a text as a sequence of words, with the sequence partitioned into sentences, paragraphs, chapters, lines, and volumes. As may be seen, these units form both a logical hierarchy (chapters, paragraphs, sentences) and a physical hierarchy (volumes, pages, lines). The ability to specify proximity using any of these structural units makes Arras very useful for those interested in the close study of a text.

It may be noted in passing that while Arras provides ways of looking for passages in a text which meet certain criteria, it does not provide any mechanism for creating new textual objects.

DynaText query language

The second major influence of Ariadne is the textual query language which formed part of DynaText. I won't rehearse in detail the history of that product in detail here, since many others who attend Balisage know it as well as I, and some know it better. I will only observe that DynaText was a system for publishing SGML documents in electronic form, which allowed users to switch among multiple stylesheets for different views of the data, provided good hypertext linking, and offered a simple and convenient textual search interface. The query language was used both as part of the end-user interface and as part of the infrastructure: as part of the creation of an electronic book, DynaText publishers could also provide simple search forms, to elicit values which could be plugged into a complex search expression as parameters. So power users could use the query language to create complicated queries which others could use without learning the query language.^[3]

I won't attempt a full account of the DynaText query language (which for brevity I'll call DTQL from now on), but some examples will illustrate key points.

A search can consist of a word or phrase. To search for a word which is also a keyword in the language, it may be enclosed in quotation marks:

programming language

"containing"

Equally important, since DynaText is designed to allow the exploitation of markup, a search can consist of an element type's generic identifier, distinguished from a word to be sought in the text by being enclosed in angle brackets:

<title>

Context can be specified using the keyword inside or in, optionally modified by directly:

programming language inside <title>

<title> directly inside <book>

Conversely, content can be specified using the keyword containing, also optionally modified by directly:

<chapter> directly containing <title>
  containing syntax

All operators in DTQL are right-associative, so the search just given is equivalent to the following:

<chapter> directly containing
  (<title> containing syntax)

Note that while

<title> containing programming language

programming language in <title>

Boolean operators are also allowed:

<bibl> not containing <title>

(<element-citation> or <mixed-citation>)
  containing <publisher-name> not containing
  "Elsevier"

<title> containing theory and practice

<title> containing practice
  and not theory

The last two examples illustrate a slightly curious aspect of DTQL's boolean operators: the one search finds title elements containing both the word theory and the word practice, the other finds title elements containing one word but not the other. The right-hand argument of the and is not interpreted as a full query, but as a second operand for the containing operator. This feels natural to native speakers of English (and perhaps other languages), but it is trickier to implement than a naive approach might expect. In particular the query

<title> containing practice and not theory

DTQL also has a proximity operator, for which distance is specified in words:

proximity within 5 words of search

markup within 10 words of descriptive or prescriptive

The samples do not exhaust the DynaText query language, although they come close: it is a useful language but gets its power from a very small number of constructs.

Why not XQuery? Or even just XPath?

An obvious reaction to the announcement of yet another query language for documents, especially at Balisage, is to ask why. Why do we need another language for document queries? Doesn't XQuery exist? Or if XQuery is deemed too complicated, why not just use XPath? There are two reasons one might want to design a new query language, even though XPath and XQuery exist.

The first is ease of acquisition by users.

Like many Balisage attendees, I often work with domain experts who are less technically inclined than I am and less tolerant of the pernickety syntax often characteristic of languages designed to be parsed by machine. The XML community is justly proud of the number of domain experts who do not self-identify as programmers but who are able to learn and use XPath and XSLT. But many domain experts never do learn XSLT, or even XPath.

When I build a web interface for a collection of XML documents, one of the first things I like to do is to provide a simple search interface that allows a user to type in a simple XPath expression and see a list of the XDM nodes matched by the expression.^[5] But often, my hopes that the domain experts with whom I work will learn enough about XML and XPath to be able to use it are dashed. As far as I know, when I have made XPath interfaces for collaborative projects, I am the only project participant who ever uses them. From time to time, others in a project have attempted to learn XML, and XPath, and XQuery. But often, domain experts find it unnerving to venture from a field in which they are experts into a field in which they are novices, and since they typically have achieved a full and rewarding professional life without knowledge of any computer languages, it is understandable both that they don't have a lot of time to focus on learning new languages and that the frustrations known to anyone learning something new and very different will often lead busy people to abandon the attempt.

It is unlikely that Ariadne is a silver bullet for this problem.

It is quite possible that some users will resist any query interface involving anything recognizable as syntax or keywords. The logical consequence of such syntax phobia among users is a search interface with a single box in which to type a query, and no visible rules for how to type it, such as is now familiar to any user of Google, Bing, DuckDuckGo, or almost any other web search engine.

But anyone who has used a single-box search interface to look for structural patterns in documents will remember how disappointing the results usually are. A search for a chapter whose title includes the word syntax, in a book whose title includes the phrase programming language, is one thing. A search for a chapter whose title includes the words programming language, in a book whose title includes the word syntax, is something rather different.^[6] A query interface based on a bag-of-words document model, with no knowledge of chapters, books, or titles, cannot comfortably capture the difference.

One of Ariadne's goals is to serve users who don't feel comfortable with most artificial languages but who do understand how their documents are tagged, and who have some interest in being able to use structural information in queries.

The second reason for not just using XQuery or XPath is: trees.

XPath and XQuery and XSLT are designed to work on XML documents, and specifically on XML documents viewed through the XPath Data Model (XDM), or more generally any information that can be viewed through that model, whether its serialized form is XML or something else. Since I was not involved in the initial design of any of those languages, I can say without immodesty that they do a good job.

But it is well known that documents often exhibit structural patterns that are not tree-shaped, or at least not shaped like a single tree. A bewildering number of alternate proposals have been made, for an equally bewildering variety of text models. (The number of models is slightly lower than the number of proposals, since in some proposals appear on closer examination to be variations on the same basic idea.)

It would, I think, be helpful for users of the text-as-graph model, the LMNL model, the Goddag model, the concurrent-hierarchies model, if it were possible to formulate queries against those models. Of course, if as sometimes happens the actual documents are stored in XML, the documents can be queried in their XML form using XPath and XQuery. But models are not just guides for implementors; they are tools for thinking about things. It would be better, when we are using a non-tree-shaped model of text, if we could formulate queries against the model we want to use, instead of translating our queries into some sort of slightly awkward XPath.

One possible caveat to this line of reasoning should be addressed. XPath is indeed defined in terms of the XPath Data Model, but nothing in its syntax requires that the parent axis return a single node. If we were to allow nodes to have multiple parents, we could apply XPath to any document model involving a directed acyclic graph. And if we relaxed other constraints like the rule that no node is its own ancestor, we could apply XPath to cyclic as well as to acyclic graphs. So if we wished to apply XPath to Goddag structures, or to concurrent hierarchies, or to text-as-graph instances, we could do so, at least in principle. And indeed there have been proposals in the past, some of them presented at Balisage or Extreme Markup Languages, to use XPath as an expression language for navigating arbitrary directed graphs.

To anyone who can easily implement the whole of XPath over a non-XDM model, there is clearly no pressing need for a different language. The problem for others is that even in its version 1.0, XPath was large enough to require non-trivial implementation effort. Now, in XPath 3.0 and 3.1, the language has become Turing-complete and implementing it from scratch looks rather daunting. Ariadne's advantage in this context is that in comparison with XPath, it's tiny, and it's possible to imagine a relatively straightforward implementation that does not require programmer-years of effort.

Origins of Ariadne

The project that has turned into the design and specification of Ariadne began life as a pair of low-priority free-time projects to re-implement both Arras and the DynaText query language, as an exercise in nostalgic retro-computing.^[7]

The feasibility of re-implementing Arras became clear to me when I reflected that its text model could be implemented as a single SQL table in which each row contains a token, a word form (the token, stripped of punctuation), a word number, a sentence number, a chapter number, a line number, a page number, and a volume number. Arras commands could in principle be translated into SQL queries. John B. Smith implemented his own inverted-file index, but I was willing to farm all of those details out to a SQL database.

Once the key idea of letting a database management system handle the boring bits like storage details became clear, it immediately became obvious that the Arras text model could also be implemented quite simply in an XQuery database, using either element containment or milestone elements to handle the structural units. Since in Arras all structural units partition the entire text, simple milestones suffice and the more complex mechanisms of Trojan-Horse markup are not needed.

Since DynaText is designed for search and retrieval in SGML documents, it seems self-evident that it should be relatively straightforward to implement a DynaText front end which passes queries to an XQuery back end for evaluation. Since DTQL seems very accessible even to non-technical users, the idea of re-implementing DTQL sometimes seemed more than an exercise in nostalgia: it could be useful to real projects I have been engaged with. But the idea never had high priority, so it never got beyond a few sketches.

Recently, however, whiling away an idle hour with an attempt to figure out a way to describe the behavior of and and or in DTQL cleanly enough to guide an implementation, I realized that DTQL requires a model of text in which two nodes can be in a parent/child relation (or not), or more generally an ancestor/descendant relation, but does not require that the model form a tree. Nothing breaks in the semantics of the query if an element (or a word) can have more than one parent.

At this point I began to think that an implementation might have more practical use than I had first imagined, and that a new query language inspired by Arras and DynaText should have a higher priority than historically accurate re-implementations of the two languages.

Design decisions

The basic design approach of Ariadne was summarized by Steven J. DeRose, the designer of the DynaText query language, thus:^[8]

DynaText has four query operators, not counting Booleans, which require special treatment:

Ariadne extends this set of operators modestly to allow searching based on document order among siblings or among all nodes and to allow proximity to be measured, Arras-style, in any structural unit, not just words.

It should be noted that the only basic relations required to support these operators are parent-child, prec-next, and element-attribute-value. No assumption is made that a child can have only one parent, so essentially any binary relation on structures in a document can be used as the parent-child relation. If the relation is cyclic, some results may of course puzzle users used to thinking of the parent-child relation as acyclic.

Like Arras and DTQL, Ariadne lacks any means of constructing new values of any kind: all Ariadne expressions denote sets of locations within texts, where from the user's point of view a location is either a tagged element in the text (e.g. a paragraph, title, or chapter) or a word. From the implementation point of view, at document ingestion time the document is tokenized and all words are wrapped in w elements, so for the implementation, all values are sets of locations, and all locations are elements in the input document. This provides a simple uniform model and makes implementation on top of XSLT or XQuery or XPath itself conceptually very simple.

The absence of constructors makes Ariadne strictly weaker than XQuery or XSLT. It cannot be used to perform arithmetic: an expression like 2 + 3 is not an Ariadne query or expression. It cannot be used to make a list of all word forms: Ariadne has no equivalent to the XPath distinct-values() function, and indeed no user-callable functions at all. Its intended users are not programmers who need to be able to specify and perform arbitrary computations, but readers who want to be able to describe and find locations in texts.

For some situations, it is convenient to have some notion of a location which is an appropriate size to return in a list of search results. I'll call such locations chunks. In most modern prose, a sentence, a list item, a heading, or a line of verse will be a reasonably good chunk. Sometimes it might be better to use a larger chunk, for example a paragraph. The only constraint on chunks is that every word in the document must be in some chunk; it may sometimes be desirable to specify further that no chunk contains any other chunk, i.e. chunks must partition the document.

To simplify the use of Ariadne for document owners, an implementation of Ariadne is expected to define some notion of chunk without intervention by the document owner; a simple default is to accept any element containing at least two words as a chunk. Another possible default (up to the implementor) is to break the input document up into sentences or sentence-like objects based on punctuation and capitalization and use them as chunks. A document owner should however be able to specify explicitly which elements are to be treated as chunks. And of course, a document owner can explicitly mark sentences (or sentence-like objects) with an element such as the TEI s element, and thus override the default behavior of the implementation. The same goes for tokenization into words: if the default behavior is suitable, the user need do nothing special, but if the user wants another behavior, they can control the behavior of an Ariadne search engine by using markup to identify what should be treated as words.

The design principles of Ariadne are thus:

One topic which has been ruled out of scope for this version of Ariadne is the ability to qualify searches by a particular hierarchy, analogous to the qualification of XPath axes with colors in Colored XML. It may be helpful, but I do not currently understand the requirements well enough to design it. It is hoped that experience with Ariadne will help to indicate whether extension in this direction is needed and what kind of extension would be helpful.

Basic expressions

Like DTQL, Ariadne has two fundamental forms of expression, one for words (or strings) and one for (structural) elements:

<author>

Heinlein

The first of these finds all author elements in the text; the second finds all occurrences of the token Heinlein.

Expressions using filters

ward inside <heading>

<head> directly inside <div> directly inside <body>

<p> inside <subsection>

//text()[contains(., 'ward')][ancestor::heading]

//head[parent::div[parent::body]]

//p[ancestor::subsection]

<chapter> directly containing
  <title> containing syntax

//chapter[title[contains(., 'syntax')]]

programming language in <title> directly inside
  <chapter> inside <book> directly containing
  <title> containing syntax

syntax in <title> directly inside <chapter>
  inside <book> directly containing <title>
  containing programming language

<theorem> not preceded by <axiom>

<speech> directly followed
  by sibling <stage-direction>

<section> with n = 2

<section> with n > 2

<div> with id null

challenge within 10 words of election

challenge followed within 10 words by election

challenge preceded within 10 words by election

challenge within 10 <w> elements of election

challenge followed within 10 <w> elements by election

challenge preceded within 5 <w> elements by election

fire within 5 <l> elements of ice

fire within 0 <l> elements of ice

Borges within 4 <footnote> elements of Barthes

(<p> inside <subsection>) containing appointed

(<p> containing appointed) inside <subsection>

<p> containing appointed inside <subsection>

Expressions with Boolean operators

(<p> inside <subsection>) containing
  appointed or appoint or appointment

(<p> inside <subsection>) containing appointed

(<p> inside <subsection>) containing appoint

(<p> inside <subsection>) containing appointment

<p> containing fire and water and not ice

<p> containing fire

<p> containing water

<p> not containing ice

<p> inside <subsection> and containing appointed

(<p> inside <subsection>) containing appointed

(<p> inside <subsection>) containing appointed
  or containing appoint or containing appointment

Heinlein and Robert

Heinlein or Bradbury

Heinlein and not Bradbury

(<p> or <q> or <bibl>) containing
  Heinlein and Robert

(<p> or <q> or <bibl>) containing
  Heinlein or Bradbury

(<p> or <q> or <bibl>) containing
  Heinlein and not Bradbury

Basic searches

<title> containing fire and ice

fire and ice

Filtered searches