Generalising XPath for Directed Graphs

1.1 Annotated Corpora

Annotated corpora have been an essential component of research and development in language-related technologies for some years. Text corpora have been used for developing information retrieval and summarisation software (e.g. MUC [MUC-7], TREC [Voorhees 98]), automatic taggers and parsers and machine translation systems [Church & Mercer 93]. In a similar way, annotated speech corpora have proliferated and have found uses across a rapidly expanding set of languages, disciplines and technologies (see
www.ldc.upenn.edu/annotation/ for a review).

Typically, such databases are specified at the level of file formats. Linguistic content is annotated with a variety of tags, attributes and values, with a specified syntax and semantics. Tools are developed for each new format and linguistic domain on an ad hoc basis. These systems are akin to the databases of the 1960s. There is a physical representation along with a hand-crafted program offering a single view on the data. Recent work [Bird & Liberman 01], [Cassidy 01] has developed an abstract data model aimed at being able to store all known annotation types; one outcome of this work is the development of toolsets which abstract away from file format details and present a uniform data model to applications.

One of these tools, the Emu system [Cassidy 01], views annotations as directed graphs where each node represents a token in the corpus and may be labelled with various attributes including a type (phoneme, word, paragraph), start and end times and one or more labels. The edges in this graph can have one of three types: a parent/child relationship defining one or more hierarchies, an explicit sequence relationship and a general associative relationship. A particular feature of linguistic annotations is that they often involve more than one hierarchy over the same set of nodes. For example, Figure shows part of a sentence which has been annotated syntactically and intonationally resulting in two hierarchies dominating a single set of word nodes.

While progress has been made on implementing tools for creation and manipulation of annotation data, no suitable query language has yet been defined. While the Emu system contains a query language implementation, it is based on an earlier version of the data model and is know not to be able to express some important queries. As part of the effort to develop a new query language for annotation data, we have begun to collect use cases for annotation query and have evaluated some query language proposals against these [Cassidy 02] [Cassidy et al 00].

1.2 Relation to XML

Clearly the annotation data model shows a close resemblance to XML and indeed if only one hierarchy needs to be encoded in an annotation, it can be naturally serialised as XML. Many existing Linguistic text corpora are encoded in XML and there have been large scale efforts to develop standardised DTDs for corpus encoding []. The problem of intersecting hierarchies has been addressed using, for example, standoff markup [Thompson & McKelvie 97] where each hierarchy is stored in a seperate XML document each referring to regions in the original text using XPointer references.

XML has been less frequently used for annotation of speech data. It is used as an interchange format in some tools such as the Annotation Graph toolkit; however, in these cases the structure of the XML document does not reflect the hierarchical structure of the annotations.

Given this close relationship, an obvious question is whether the various XML query languages are appropriate for the task of querying annotations.

1.3 Annotation Query Use Cases

In an earlier paper [Cassidy 02] we presented a number of annotation query use cases were evaluated them with respect to XQuery. This showed that while a number of the queries could be evaluated within XQuery, some interesting cases were very difficult to express. Here we present two examples which illustrate differences between this application and the XML query use-cases.

Find L- Intermediate phrases containing words which form an NP Syntax phrase. An example answer to this query is the NP containing the words "your dark suit" in . This query highlights the need to be able to cope with multiple hierarchies since it requires looking at both Intermediate and Syntax parents of the Word nodes. While XML won't allow multiple parents, there's nothing in XQuery (or in particular, XPath) which precludes a traversal from parent to child to a different parent. If we allow this, the query can be written in XQuery as shown in Figure (of course the result here would be an XML fragment which might not be what is required, we'll ignore this factor for the moment).

FOR $np in //syntax[@label="NP"]
LET $iparent ::= $np//word[1]/parent::inter
WHERE
    EVERY $int IN 
      $np//word/parent::inter
    SATISFIES ($int == $iparent) AND 
              ($int/@label = "L-")
RETURN
    $iparent

Find sequences of any number of consonant phonemes followed by a single vowel followed by any number of consonants: C+VC+. This is a significant use case since it illustrates an important class of query for language corpora -- finding non-annotated patterns based on `grammatical' structure. At the same time, this kind of query is very difficult to express in XQuery (although not impossible, see [Cassidy 02] for a solution using functions).

The evaluation of XQuery with respect to these and other use-cases provides two interesting insights. Firstly, the document or data centric views provided for by XQuery (and other XML query languages) are almost but not quite appropriate for annotation query. Secondly, XPath is a very clear and natural way to specify locations of elements within annotations but would need to be extended to achieve completeness.

1.4 Outline

This paper reports on some work which attempts to explore the idea of extending XPath in directions which make it more useful for annotation query. In particular, an attempt to generalise XPath to address queries like the second one presented above (C+VC+). The result of this exercise is a generalised path based query language which applies not only to annotations but to generalised directed graphs and which reduces to XPath as a special case.

For the purposes of this paper I'll talk about a particular kind of directed graph which is a generalisation of the graphs described for annotations. These graphs can be described as edge labelled directed graphs. An example is the XML graph structure which contains edges labelled 'child' and 'attribute'. The nodes in these graphs have two labels: a type (cf. the XML element name) and a textual label. This is an interesting class of graphs which subsumes for example, XML, RDF and our annotation data.

The remainder of this paper reviews the literature on path based query languages and then describes the generalisation of XPath and evaluates this in the annotation domain and in more general graph based data.

2.1 Annotation Query

For the most part the query languages proposed and developed for annotation data have been of ad-hoc design and are able to cope only with a subset of the kinds of annotation data seen in practice. For example, the Emu query language [Cassidy 01] provides a means of finding nodes based on sequential and hierarchical relations but lacks many basic query language features such as disjunction and compositionality. Most other annotation query tools have made use of general purpose structural pattern matching tools such as Sgrep
www.cs.helsinki.fi/u/jjaakkol/sgrep.html which allow for regular expression like searches in structured textual data.

One important proposal that has been made recently follows from the work on annotation structures by Bird and his colleagues [Bird & Liberman 01]. [Bird et al 00] propose a query language based on path expressions in an Annotation Graph (AG). An AG is a directed graph representation of an annotation which foregrounds the sequential structure of annotations; nodes in the graph are anchor points and edges represent linguistic elements. Hierarchical structure is implicit in AG when a dominating edge spans more than one subordinate edge. While this might seem very different to the hierarchical view of annotations described above, it can be shown [Cassidy 01] that they are able to represent the same structures.

Queries in the proposed AG query language are made up of a set of path expressions which describe paths through the annotation graph. For example in the query term X.[:word, label: cat].Y, X and Y are query variables and stand for nodes in the AG and the terms in brackets specify the type (:utt) and attribute values associated with the edge between these nodes.

While this query language proposal has a number of interesting features, it is awkward to express queries in. Since it focuses on traversing the sequential AG relations only, expressing hierarchical queries is very unnatural. Evaluation against a number of Annotation use cases has shown [Cassidy et al 00] that while it is capable of expressing all of the use cases, the constructs needed to do so are highly complex and would be difficult for naive users to work with. Part of the effort in this paper is to work with a very natural query language component (XPath) and see if it can be extended for annotation query wile retaining the naturalness of expression.

2.2 Path Based Query Languages

This will be a review of the DB literature relating to path queries. In particular looking at things like Graphlog [Consens & Mendelzon] and the G+ language described in [Mendelzon & Wood]. The general conclusion is that there is a good deal of prior work on these kind of languages but that none of them seem to quite fit the problem expressed here. For example, G+ provides a query language where regular expressions can be used to match sequences of edges in the graph but does not enable constraints to be placed on the nodes traversed. In addition to this point, the underlying goal of this paper is not to derive a new formal query language but to explore the generalisation of the existing XPath language. It may become clear during this exercise that the underlying principles are those of an already described QL; this is a good thing since we can then take advantage of the results relating to that QL in implementing our annotation QL.

3.1 Returning Path Sets

While locating nodes in a graph is the sole use of XPath, there are cases in annotation query and perhaps in other applications where selecting paths through the graph is important. The prototypical example from annotation query is find sequences of phonemes with property X. Note that no changes to the path language are needed to achieve this, but that the query processor needs to be augmented to maintain path sets rather than node sets.

3.2 Defining Axes

The set of axes defined in XPath is clearly designed to allow the set of graph traversal operations that are seen to be atomic in XML document trees. In a more general graph structure, it is clearly more difficult to foresee what axes will be needed and in general it is more useful to define what an axis is than a particular set of axes being prescribed.

An XPath axis is fundamentally a mapping from nodes to nodesets and defines a way of traversing the underlying graph. Each axis encapsulates two things: a type of edge to follow (eg. child vs. attribute) and whether to follow it transitively (eg. child vs. descendant).

One approach to extending the axis set is to allow arbitrary definitions of axes which are simply mappings from nodes to node sets. If we assume that the graph structure being searched is the edge labelled directed graph described earlier, then any edge label might be associated with an axis; in addition, axes might be defined for more complex traversal -- an example might be an uncle axis which returns siblings of a node's parent using a combination of parent and child edges. Similarly, for an XML document one might define an idref axis which followed idref links.

This approach would allow the inclusion of transitivity in the axis definition as is the case with the descendant axis in XPath. However, a more general solution is to factor this out as a modifiable parameter in a path expression. The current binary single step/transitive distinction can be generalised to a how many steps parameter which controls how many steps along an axis are allowable. For example, I could find my grandparents by stepping along the parent axis exactly twice; I could find all of my children and grandchildren by stepping along the child axis up to two times.

The proposal here is to define an axis as a function mapping nodes to pathsets; the function takes a parameter denoting how many steps to take along the axis in generating new paths.

3.3 Path Conditions

In XPath, conditions apply only to the last node on the path extended from the context node; for example, the expression /descendant:para[@style='important'] traverses along the child axis any number of steps to find paragraphs with a particular attribute. No condition is placed on any of the intermediate nodes along the axis.

Rather than limiting conditions to the final element of a path, the approach taken here is to allow conditions on any subset of the nodes traversed while extending the path. For example, a condition might apply to all nodes, the first node or the last two nodes.

Introducing this generalisation allows the use-case described earlier to be addressed. A sequence of nodes labelled C can be located by walking along the following axis an unlimited number of steps applying the condition to every node.

3.4 Extend Programs

The generalisations described above can be implemented in a new path language where a query consists of a series of calls to a single extend function which maps pathsets to pathsets. The signature of extend is as follows:

extend [axis] [step] [condition] [where]

where [axis] is the name of the axis to traverse, [step] is a restriction on the number of steps taken along the axis, [condition] is a boolean condition on nodes and [where] is a restriction on where the condition must hold. These are discussed in detail below.