Technical Report TR660:
A Study of Positive XPath with Parent/Child Navigation
Yuqing Wu, Dirk Van Gucht, Marc Gyssens, Jan Paredaens
(Mar 2008), 8 pages pages
- 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:
-
|
