Maarten Marx
Maarten de Rijke
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.
- L. Afanasiev, M. Francheschet, M. Marx, and M. de Rijke. CTL Model Checking for Processing Simple XPath Queries. In Proc. TIME 2004, 2004. Google Scholar
Digital Library
- M. Benedikt, W. Fan, and G. Kuper. Structural properties of XPath fragments. In Proceedings. ICDT 2003, 2003. Google ScholarDigital Library
- G. Bex, S. Maneth, and F. Neven. A formal model for an expressive fragment of XSLT. Information Systems, 27(1):21--39, 2002. Google ScholarDigital Library
- P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001. Google ScholarDigital Library
- P. Blackburn, W. Meyer-Viol, and M. de Rijke. A proof system for finite trees. In CSL'96, pages 86--105, 1996. Google ScholarDigital Library
- K. Etessami, M. Vardi, and Th. Wilke. First-order logic with two variables and unary temporal logic.Google Scholar
- G. Gottlob and C. Koch. Monadic queries over tree-structured data. In Proc. LICS, Copenhagen, 2002. Google ScholarDigital Library
- G. Gottlob, C. Koch, and R. Pichler. The complexity of XPath query evaluation. In PODS'03, pages 179--190, 2003. Google ScholarDigital Library
- G. Gottlob, C. Koch, and K. Schulz. Conjunctive queries over trees. In Proc. PODS, pages 189--200, 2004. Google ScholarDigital Library
- M. Marx. Conditional XPath, the first order complete XPath dialect. In Proc. PODS'04, pages 13--22, 2004. Google ScholarDigital Library
- M. Marx. First order paths in ordered trees. In T. Eiter and L. Libkin, editors, Proc. ICDT 2005, volume 3363 of LNCS, pages 114--128, 2005. Google ScholarDigital Library
- G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. PODS'02, pages 65--76, 2002. Google ScholarDigital Library
- T. Milo, D. Suciu, and V. Vianu. Typechecking for XML transformers. In Proc. PODS, pages 11--22. ACM, 2000. Google ScholarDigital Library
- M. Murata. Extended path expressions for XML. In Proc. PODS, 2001. Google ScholarDigital Library
- F. Neven and T. Schwentick. Expressive and efficient pattern languages for tree-structured data. In Proc. PODS, pages 145--156. ACM, 2000. Google ScholarDigital Library
- V. Vianu. A Web odyssey: from Codd to XML. In Proc. PODS, pages 1--15. ACM Press, 2001. Google ScholarDigital Library
- W3C. XML path language (XPath): Version 1.0. http://www.w3.org/TR/xpath.html.Google Scholar
- W3C. XML path language (XPath): Version 2.0. http://www.w3.org/TR/xpath20/.Google Scholar
- W3C. XML schema part 1: Structures. http://www.w3.org/TR/xmlschema-1.Google Scholar
- W3C. XQuery 1.0: A query language for XML. http://www.w3.org/TR//xquery/.Google Scholar
- W3C. XSL transformations language (XSLT): Version 2.0. http://www.w3.org/TR/xslt20/.Google Scholar
- P. Wadler. Two semantics for XPath. Technical report, Bell Labs, 2000.Google Scholar
Index Terms
- Semantic characterizations of navigational XPath
Recommendations
Conditional XPath
Special Issue: SIGMOD/PODS 2004XPath 1.0 is a variable free language designed to specify paths between nodes in XML documents. Such paths can alternatively be specified in first-order logic. The logical abstraction of XPath 1.0, usually called Navigational or Core XPath, is not ...
Characterizations for
Logic, Language, Information, and ComputationAbstractOver the semantic universe of trees augmented with arbitrary sets of relations between nodes, we study model-theoretic properties of the extension of the downward fragment of XPath, equipped with a finite set of relation symbols. We ...
Comments