Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

XPath is a prominent W3C standard for navigating XML documents that has stimulated a lot of research into query answering and static analysis. In particular, query containment has been studied extensively for fragments of the 1.0 version of this standard, whereas little is known about query containment in (fragments of) the richer language XPath 2.0. In this article, we consider extensions of CoreXPath, the navigational core of XPath 1.0, with operators that are part of or inspired by XPath 2.0: path intersection, path equality, path complementation, for-loops, and transitive closure. For each combination of these operators, we determine the complexity of query containment, both with and without DTDs. It turns out to range from ExpTime (for extensions with path equality) and 2-ExpTime (for extensions with path intersection) to non-elementary (for extensions with path complementation or for-loops). In almost all cases, adding transitive closure on top has no further impact on the complexity. We also investigate the effect of dropping the upward and/or sibling axes, and show that this sometimes leads to a reduction in complexity. Since the languages we study include negation and conjunction in filters, our complexity results can equivalently be stated in terms of satisfiability. We also analyze the above languages in terms of succinctness.

REFERENCES

• 1: Arenas, M., Fan, W., and Libkin, L. 2008. On verifying consistency of XML specifications. In SIAM J. Comput. 38, 3, 259--270.
• 2: Michael Benedikt , Wenfei Fan , Floris Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM (JACM), v.55 n.2, p.1-79, May 2008 [doi>10.1145/1346330.1346333]
• 3: Michael Benedikt , Wenfei Fan , Gabriel Kuper, Structural properties of XPath fragments, Theoretical Computer Science, v.336 n.1, p.3-31, 25 May 2005 [doi>10.1016/j.tcs.2004.10.030]
• 4: Berglund, A., Boag, S., Chamberlin, D., Fernandez, M. F., Kay, M., Robie, J., and Simeon, J., Eds. 2007. XML Path Language (XPath) Version 2.0. W3C Recommendation. http://www.w3.org/TR/2007/REC-xpath20-20070123/.
• 5: Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Simeon, J., Eds. 2007. XQuery 1.0: an XML Query Language. W3C Recommendation. http://www.w3.org/TR/2007/REC-xquery-20070123/.
• 6: Stefan Bottcher, Testing Intersection of XPath Expressions under DTDs, Proceedings of the International Database Engineering and Applications Symposium, p.401-406, July 07-09, 2004 [doi>10.1109/IDEAS.2004.61]
• 7: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 8: Clark, J., and DeRose, S. J., eds. 1999. XML Path Language (XPath) Version 1.0. W3C Recommendation. http://www.w3.org/TR/xpath.
• 9: Clark, J., and Murata, M. 2001. RELAX NG specification. http://relaxng.org/spec-20011203.html.
• 10: Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005 [doi>10.1016/j.tcs.2004.10.032]
• 11: Keith Ellul , Bryan Krawetz , Jeffrey Shallit , Ming-wei Wang, Regular expressions: new results and open problems, Journal of Automata, Languages and Combinatorics, v.9 n.2-3, p.233-256, September 2004
• 12: Kousha Etessami , Moshe Y. Vardi , Thomas Wilke, First-order logic with two variables and unary temporal logic, Information and Computation, v.179 n.2, p.279-295, December 15, 2002 [doi>10.1006/inco.2001.2953]
• 13: Fan, W., Geerts, F., Jia, X., and Kementsietsidis, A. 2007. Rewriting regular XPath queries on XML views. In Proceedings of the 23rd International Conference on Data Engineering (ICDE'07). IEEE Computer Society Press, Los Alamitos, CA, 666--675.
• 14: Martin Fürer, The Complexity of the Inequivalence Problem for Regular Expressions with Intersection, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.234-245, July 14-18, 1980
• 15: Gao, S., Sperberg-McQueen, C. M., and Thompson, H. S., Eds. 2007. XML Schema Definition Language (XSDL) 1.1, Part 1: Structures. W3C Working Draft. http://www.w3.org/TR/2007/WD-xmlschema11-1-20070830/.
• 16: Geerts, F., and Fan, W. 2005. Satisfiability of XPath queries with sibling axes. In Proceedings of the 10th International Symposium on Database Programming Languages (DBPL'05), G. M. Bierman and C. Koch, Eds. Lecture Notes in Computer Science, vol. 3774. Springer-Verlag, Berlin, Germany, 122--137.
• 17: Gelade, W., and Neven, F. 2008. Succinctness of the complement and intersection of regular expressions. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS'08), S. Albers and P. Weil, Eds. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 325--336.
• 18: 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
• 19: Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005 [doi>10.1145/1059513.1059520]
• 20: Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006 [doi>10.1145/1131342.1131345]
• 21: Grädel, E., Thomas, W., and Wilke, T., Eds. 2002. Automata, Logics and Infinite Games. Lecture Notes in Computer Science, vol. 2500. Springer-Verlag, Berlin, Germany.
• 22: Grohe, M., and Schweikardt, N. 2005. The succinctness of first-order logic on linear orders. Logical Methods in Computer Science 1, 1, 1--25.
• 23: Beda Christoph Hammerschmidt , Martin Kempa , Volker Linnemann, On the Intersection of XPath Expressions, Proceedings of the 9th International Database Engineering & Application Symposium, p.49-57, July 25-27, 2005 [doi>10.1109/IDEAS.2005.39]
• 24: Hidders, J. 2003. Satisfiability of XPath expressions. In Proceedings of the 9th International Workshop on Data Base Programming Languages (DBPL'03), G. Lausen and D. Suciu, Eds. Lecture Notes in Computer Science, vol. 2921. Springer-Verlag, Berlin, Germany, 21--36.
• 25: Kay, M., Ed. 2007. XSL Transformations (XSLT) Version 2.0. W3C Recommendation. http://www.w3.org/TR/2007/REC-xslt20-20070123/.
• 26: Nils Klarlund , Anders Møller , Michael I. Schwartzbach, The DSD Schema Language, Automated Software Engineering, v.9 n.3, p.285-319, August 2002 [doi>10.1023/A:1016376608070]
• 27: Ladner, R. E. 1977. The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6, 3, 467--480.
• 28: Laks V. S. Lakshmanan , Ganesh Ramesh , Hui Wang , Zheng Zhao, On testing satisfiability of tree pattern queries, Proceedings of the Thirtieth international conference on Very large data bases, p.120-131, August 31-September 03, 2004, Toronto, Canada
• 29: Lange, M., and Lutz, C. 2005. 2-ExpTime lower bounds for propositional dynamic logics with intersection. J. Symb. Logic 70, 5, 1072--1086.
• 30: Wim Martens , Frank Neven , Thomas Schwentick , Geert Jan Bex, Expressiveness and complexity of XML Schema, ACM Transactions on Database Systems (TODS), v.31 n.3, p.770-813, September 2006 [doi>10.1145/1166074.1166076]
• 31: Marx, M. 2004. XPath with conditional axis relations. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04), E. Bertino, S. Christodoulakis, D. Plexousakis, V. Christophides, M. Koubarakis, K. Böhm, and E. Ferrari, Eds. Lecture Notes in Computer Science, vol. 2992. Springer-Verlag, Berlin, Germany.
• 32: Maarten Marx, Conditional XPath, ACM Transactions on Database Systems (TODS), v.30 n.4, p.929-959, December 2005 [doi>10.1145/1114244.1114247]
• 33: Maarten Marx , Maarten de Rijke, Semantic characterizations of navigational XPath, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083792]
• 34: McNaughton, R., and Yamada, H. 1960. Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9, 39--47.
• 35: 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]
• 36: Makoto Murata , Dongwon Lee , Murali Mani , Kohsuke Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology (TOIT), v.5 n.4, p.660-704, November 2005 [doi>10.1145/1111627.1111631]
• 37: Neven, F., and Schwentick, T. 2006. On the complexity of XPath containment in the presence of disjunction, DTDs and variables. Logical Meth. Comput. Sci. 2, 1--30.
• 38: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 39: Yannis Papakonstantinou , Victor Vianu, DTD inference for views of XML data, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.35-46, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335173]
• 40: Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974140]
• 41: Stockmeyer, L. J. 1974. The complexity of decision problems in automata theory. Ph.D. dissertation. Department of Electrical Engineering, MIT, Cambridge, MA.
• 42: Keishi Tajima , Yoshiki Fukui, Answering xpath queries over networks by sending minimal views, Proceedings of the Thirtieth international conference on Very large data bases, p.48-59, August 31-September 03, 2004, Toronto, Canada
• 43: Balder ten Cate, The expressivity of XPath with transitive closure, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142398]
• 44: ten Cate, B., and Marx, M. 2009. Axiomatizing the logical core of XPath 2.0. In Proceedings of ICDT 2007. LNCS, vol. 4353. Springer, 134--148.
• 45: Thompson, H. S., Beech, D., Malloney, M., and Mendelsohn, N., eds. 2004. XML Schema Part 1: Structures, Second Edition. W3C Recommendation. http://www.w3.org/TR/2004/REC-xmlschema-1-20041028/.
• 46: Moshe Y. Vardi, Reasoning about The Past with Two-Way Automata, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, p.628-641, July 13-17, 1998
• 47: Peter T. Wood, Containment for XPath Fragments under DTD Constraints, Proceedings of the 9th International Conference on Database Theory, p.300-314, January 08-10, 2003

INDEX TERMS

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

General Terms:
Algorithms, Languages

Keywords:
XML, XPath, complexity, containment, satisfiability