Semantic characterizations of navigational XPath
- 1 June 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 34 (2) , 41-46
- https://doi.org/10.1145/1083784.1083792
Abstract
We give semantic characterizations of the expressive power of navigational XPath (a.k.a. Core XPath) in terms of first order logic. XPath can be used to specify sets of nodes and sets of paths in an XML document tree. We consider both uses. For sets of nodes, XPath is equally expressive as first order logic in two variables. For paths, XPath can be defined using four simple connectives, which together yield the class of first order definable relations which are safe for bisimulation. Furthermore, we give a characterization of the XPath expressible paths in terms of conjunctive queries.Keywords
This publication has 10 references indexed in Scilit:
- Conjunctive queries over treesPublished by Association for Computing Machinery (ACM) ,2004
- Conditional XPath, the first order complete XPath dialectPublished by Association for Computing Machinery (ACM) ,2004
- First Order Paths in Ordered TreesPublished by Springer Nature ,2004
- The complexity of XPath query evaluationPublished by Association for Computing Machinery (ACM) ,2003
- Containment and equivalence for an XPath fragmentPublished by Association for Computing Machinery (ACM) ,2002
- A formal model for an expressive fragment of XSLTInformation Systems, 2002
- A Web OdysseyPublished by Association for Computing Machinery (ACM) ,2001
- Extended path expressions of XMLPublished by Association for Computing Machinery (ACM) ,2001
- Typechecking for XML transformersPublished by Association for Computing Machinery (ACM) ,2000
- Expressive and efficient pattern languages for tree-structured data (extended abstract)Published by Association for Computing Machinery (ACM) ,2000