School of Informatics and Computing

Technical Report TR660:
A Study of Positive XPath with Parent/Child Navigation

Abstract:

We study the expressiveness of Positive XPath with parent/child navigation, denoted XPath+, from two angles. First, we establish that XPath+ is equivalent in expressive power to some of its sub-fragments as well as to the class of tree queries, a sub-class of the first-order conjunctive queries defined over label, parent, and child predicates. The translation algorithm from tree queries to XPath+ yields a simple normal form for XPath+ queries. Using this normal form, we can effectively partition an XPath+ query into sub-queries that can be expressed in a very small sub-fragment of XPath+ for which efficient evaluation strategies are available. Second, we characterize the expressiveness of XPath+ in terms of its ability to distinguish nodes in a document. We show that two such nodes cannot be distinguished if and only if the paths from the root of the documents to these nodes have equal length and corresponding nodes on these paths are bisimilar.

Available as:

• PDF (154 KBytes)

There is help available if you want further information about the available file formats and software to display and print these files.