Structural characterizations of the semantics of XPath as navigation tool on a document

ABSTRACT

Given a document D in the form of an unordered labeled tree, we study the expressibility on D of various fragments of XPath, the core navigational language on XML documents. We give characterizations, in terms of the structure of D, for when a binary relation on its nodes is definable by an XPath expression in these fragments. Since each pair of nodes in such a relation represents a unique path in D, our results therefore capture the sets of paths in D definable in XPath. We refer to this perspective on the semantics of XPath as the "global view." In contrast with this global view, there is also a "local view" where one is interested in the nodes to which one can navigate starting from a particular node in the document. In this view, we characterize when a set of nodes in D can be defined as the result of applying an XPath expression to a given node of D. All these definability results, both in the global and the local view, are obtained by using a robust two-step methodology, which consists of first characterizing when two nodes cannot be distinguished by an expression in the respective fragments of XPath, and then bootstrapping these characterizations to the desired results.

REFERENCES

• 1: F. Bancilhon. On the Completeness of Query Languages for Relational Data Bases. In MFCS, pages 112--123, Zakopane, Poland, 1978. Springer LNCS 64.
• 2: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065172]
• 3: 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
• 4: A. Berglund, S. Boag, D. Chamberlin, M. F. Fernández, M. Kay, J. Robie, and J. Siméon. XML Path Language (XPath) Version 2.0. Technical report, W3C, 2005.
• 5: Patrick Blackburn , Maarten de Rijke , Yde Venema, Modal logic, Cambridge University Press, New York, NY, 2001
• 6: P. Buneman, M. Grohe, and C. Koch. Path Queries on Compressed XML. In VLDB, pages 141--152, Berlin, Germany, 2003.
• 7: A. K. Chandra and D. Harel. Computable Queries for Relational Data Bases. J. Comp. Sys. Sci., 21(2):156--178, 1980.
• 8: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer Verlag, Berlin, 1995.
• 9: Irini Fundulaki , Maarten Marx, Specifying access control policies for XML documents with XPath, Proceedings of the ninth ACM symposium on Access control models and technologies, June 02-04, 2004, Yorktown Heights, New York, USA [doi>10.1145/990036.990046]
• 10: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 11: 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
• 12: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 13: M. Grohe. Equivalence in Finite-Variable Logics is Complete for Polynomial Time. Combinatorica, 19(4):507--532, 1999.
• 14: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 15: L. Krzeszczakowski. Pebble Games on Trees. In EACSL CSL, pages 359--371, Vienna, Austria, 2003. Springer LNCS 2803.
• 16: L. Libkin. Logics for Unranked Trees: An Overview. In EATCS ICALP, pages 35--50, Lisbon, Portugal, 2005. Springer LNCS 3580.
• 17: Maarten Marx, Conditional XPath, the first order complete XPath dialect, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055562]
• 18: Maarten Marx , Maarten de Rijke, Semantic characterizations of navigational XPath, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083792]
• 19: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 20: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 21: J. Paredaens. On the Expressive Power of the Relational Algebra. Inf. Process. Lett., 7(2):107--111, 1978.
• 22: P. Ramanan. Covering Indexes for XML Queries: Bisimulation - Simulation = Negation. In VLDB, pages 165--176, Berlin, Germany, 2003.
• 23: A. Tarski. On the Calculus of Relations. J. Symb. Log., 6(3):73--89, 1941.
• 24: A. Tarski and S. Givant. A Formalization of Set Theory Without Variables. American Mathematical Society, Providence, RI, USA, 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Theory

Keywords:
XPath, definability, expressibility