Conditional XPath, the first order complete XPath dialect

ABSTRACT

XPath is the W3C -- standard node addressing language for XML documents. XPath is still under development and its technical aspects are intensively studied. What is missing at present is a clear characterization of the expressive power of XPath, be it either semantical or with reference to some well established existing (logical) formalism. Core XPath (the logical core of XPath 1.0 defined by Gottlob et al.) cannot express queries with conditional paths as exemplified by "do a child step, while test is true at the resulting node." In a first-order complete extension of Core XPath, such queries are expressible, We add conditional axis relations to Core XPath and show that the resulting language, called conditional XPath, is equally expressive as first-order logic when interpreted on ordered trees. Both the result, the extended XPath language, and the proof are closely related to temporal logic. Specifically, while Core XPath may be viewed as a simple temporal logic, conditional XPath extends this with (counterparts of) the since and until operators.

REFERENCES

• 1: Michael Benedikt , Wenfei Fan , Gabriel M. Kuper, Structural Properties of XPath Fragments, Proceedings of the 9th International Conference on Database Theory, p.79-95, January 08-10, 2003
• 2: P. Blackburn and W. Meyer-Viol. Linguistics, logic, and finite trees. Logic J. of the IGPL, 2:3--29, 1994.
• 3: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 4: Markus Frick , Martin Grohe, The Complexity of First-Order and Monadic Second-Order Logic Revisited, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.215-224, July 22-25, 2002
• 5: Dov M. Gabbay , Ian Hodkinson , Mark Reynolds, Temporal logic (vol. 1): mathematical foundations and computational aspects, Oxford University Press, Inc., New York, NY, 1994
• 6: Dov Gabbay , Amir Pnueli , Saharon Shelah , Jonathan Stavi, On the temporal analysis of fairness, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567462]
• 7: G. Gottlob, C. Koch, and R. Pichler. Efficient algorithms for processing XPath queries. In Proc. VLDB'02, 2002.
• 8: Georg Gottlob , Christoph Koch , Reinhard Pichler, The complexity of XPath query evaluation, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.179-190, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773171]
• 9: Georg Gottlob , Christoph Koch, Monadic Queries over Tree-Structured Data, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.189-202, July 22-25, 2002
• 10: N. Immerman. Upper and lower bounds for first order expressibility. J. Comput. Syst. Sci., 25:76--98, 1982.
• 11: N. Immerman and D. Kozen. Definability with bounded number of bound variables. In Proc. LICS, pages 236--244, Washington, 1987. Computer Society Press.
• 12: J.A.W. Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, U. of California, LA, 1968.
• 13: C. Koch. Efficient processing of expressive node-selecting queries on XML data in secondary storage: A tree automata-based approach. In VLDB 2003, pages 249--260, 2003.
• 14: Marcus Kracht, Inessential Features, Selected papers from the First International Conference on Logical Aspects of Computational Linguistics, p.43-62, September 23-25, 1996
• 15: M. Marx. XPath with conditional axis relations. In Proc. EDBT'04, pages 477--494. 2004.
• 16: Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
• 17: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 18: A. Palm. Transforming tree constraints into formal grammars. PhD thesis, Universität Passau, 1997.
• 19: Alexander Moshe Rabinovich, Expressive Power of Temporal Logics, Proceedings of the 13th International Conference on Concurrency Theory, p.57-75, August 20-23, 2002
• 20: James Rogers, Descriptive Approach to Language - Theoretic Complexity, CSLI Publications, Stanford, CA, 1998
• 21: B-H. Schlingloff. Expressive completeness of temporal logic of trees. Journal of Applied Non -- Classical Logics, 2(2):157--180, 1992.
• 22: A. Tarski and S. Givant. A Formalization of Set Theory without Variables, volume 41. AMS Colloquium publications, Providence, Rhode Island, 1987.
• 23: Wolfgang Thomas, Ehrenfeucht Games, the Composition Method, and the Monadic Theory of Ordinal Words, Structures in Logic and Computer Science, A Selection of Essays in Honor of Andrzej Ehrenfeucht, p.118-143, January 1997
• 24: Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]
• 25: W3C. XML path language (XPath): Version 1.0. http://www.w3.org/TR/xpath.html.
• 26: W3C. XML path language (XPath): Version 2.0. http://www.w3.org/TR/xpath20/.
• 27: W3C. XML schema part 1: Structures. http://www.w3.org/TR/xmlschema-1.
• 28: W3C. Xquery 1.0: A query language for XML. http://www.w3.org/TR//xquery/.
• 29: W3C. XSL transformations language (XSLT): Version 2.0. http://www.w3.org/TR/xslt20/.
• 30: P. Wadler. Two semantics for XPath. Technical report. Bell Labs, 2000.