LPath+: A First-Order Complete Language for Linguistic Tree Query

Proceedings of PACLIC 19, the 19th Asia-Pacific Conference on Language, Information and Computation LPath+: A First-Order Complete Language for Linguistic Tree Query Catherine Lai and Steven Bird Department of Computer Science and Software Engineering University of Melbourne, Victoria 3010, AUSTRALIA Department of Linguistics and Linguistic Data Consortium University of Pennsylvania, Philadelphia PA 19104, USA laic@ling.upenn.edu, sb@csse.unimelb.edu.au Abstract Annotated linguistic databases are widely used in linguistic research and in language technology development. These annotations are typically hierarchical, and represent the nested structure of syntactic and prosodic constituents. Recently, the LPath language has been proposed as a convenient path-based language for querying linguistic trees. We establish the formal expressiveness of LPath relative to the XPath family of languages. We also extend LPath to permit simple clo- sures, resulting in a first-order complete language which we believe is sufficiently expressive for the majority of linguistic tree query needs. 1. Introduction In recent years, a great variety of linguistic query languages have been proposed, most of them specialised for linguistic trees (Lai and Bird, 2004), and applied to corpora such as the Penn Treebank (Marcus et al., 1993). Despite this considerable effort, relatively little is known about the formal expressiveness of these languages, or the computational resources required to process them as the size of the data grows. One reason for this is that much of the work in this area has taken place in isolation from well-understood database query languages such as SQL and XPath (Clark and DeRose, 1999). Recently, the LPath language has been proposed as a convenient path-based language for querying linguistic trees (Bird et al., 2006). It augments the navigational axes of XPath with three additional tree operators, and it can be translation into SQL for efficient execution. In this paper we investigate the expressiveness of LPath with respect to Core XPath and to a first-order complete language called Conditional XPath. We also extend LPath to permit simple closures, and argue that this new language supports all the navigational and closure requirements of linguistic tree query. This paper is organised as follows. Section 2 reviews LPath, XPath, and Conditional XPath, and Section 3 examines the LPath operators to see which of them can be expressed in XPath or Conditional XPath. Section 4 presents an extended language, Conditional LPath, or LPath+, and discusses its merits as a linguistic tree query language. S2 VP4 NP6 PP11 NP7 NP13 NP3 V5 Det8 Adj9 N10 Prep12 Det14 N15 N17 lex: lex: lex: lex: lex: lex: lex: lex: lex: I saw the old man with a dog today Figure 1: Tree Representation 2. Background: LPath and XPath 2.1. LPath LPath was developed to be expressive enough for linguistic query but also to take advantage of relational database technology. As the name suggests, LPath is an extension of XPath. Bird et al. (2006) present three linguistically motivated syntactic additions. These are the immediate following axis (and its converse), tree edge alignment, and a scoping operator. They also present an efficient interpreter for LPath which converts LPath …

Content truncated to 500 words