Balder ten Cate
Carsten Lutz
Skip Abstract Section
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.
- Arenas, M., Fan, W., and Libkin, L. 2008. On verifying consistency of XML specifications. In SIAM J. Comput. 38, 3, 259--270.Google Scholar
Digital Library
- Benedikt, M., Fan, W. and Geerts, F. 2008. XPath satisfiability in the presence of DTDs. J. ACM 55, 2, 1--79. Google ScholarDigital Library
- Benedikt, M., Fan, W., and Kuper, G. M. 2005. Structural properties of XPath fragments. Theoret. Comput. Sci. 336, 1, 3--31. Google ScholarDigital Library
- 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/.Google Scholar
- 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/.Google Scholar
- Böttcher, S. 2004. Testing intersection of XPath expressions under DTDs. In Proceedings of the 8th International Database Engineering and Applications Symposium (IDEAS'04). IEEE Computer Society Press, Los Alamitos, CA, 401--406. Google ScholarDigital Library
- Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J. 1981. Alternation. J. ACM 28, 1, 114-- 133. Google ScholarDigital Library
- Clark, J., and DeRose, S. J., eds. 1999. XML Path Language (XPath) Version 1.0. W3C Recommendation. http://www.w3.org/TR/xpath.Google Scholar
- Clark, J., and Murata, M. 2001. RELAX NG specification. http://relaxng.org/spec-20011203.html.Google Scholar
- Deutsch, A. and Tannen, V. 2005. XML queries and constraints, containment and reformulation. Theoret. Comput. Sci. 336, 1, 57--87. Google ScholarDigital Library
- Ellul, K., Krawetz, B., Shallit, J., and wei Wang, M. 2004. Regular expressions: New results and open problems. J. Automata, Lang. Combin. 9, 2-3, 233--256. Google ScholarDigital Library
- Etessami, K., Vardi, M. Y., and Wilke, T. 2002. First order logic with two variables and unary temporal logic. Info. Computat. 179, 2, 279--295. Google ScholarDigital Library
- 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.Google Scholar
- Fürer, M. 1980. The complexity of the inequivalence problem for regular expressions with intersection. In Proceedings of the 7th Colloquium on Automata, Languages and Programming (ICALP'80), J. W. de Bakker and J. van Leeuwen, Eds. Lecture Notes in Computer Science, vol. 85. Springer-Verlag, Berlin, Germany, 234--245. Google ScholarDigital Library
- 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/.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Gottlob, G., and Koch, C. 2002. Monadic queries over tree-structured data. In Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02), G. Plotkin, Ed. IEEE Computer Society, 189--202. Google ScholarDigital Library
- Gottlob, G., Koch, C., Pichler, R., and Segoufin, L. 2005. The complexity of XPath query evaluation and XML typing. J. ACM 52, 2, 284--335. Google ScholarDigital Library
- Gottlob, G., Koch, C., and Schulz, K. U. 2006. Conjunctive queries over trees. J. ACM 53, 2, 238--272. Google ScholarDigital Library
- 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.Google Scholar
- Grohe, M., and Schweikardt, N. 2005. The succinctness of first-order logic on linear orders. Logical Methods in Computer Science 1, 1, 1--25. Google ScholarDigital Library
- Hammerschmidt, B. C., Kempa, M., and Linnemann, V. 2005. On the intersection of XPath expressions. In Proceedings of the 9th International Database Engineering and Applications Symposium (IDEAS'05). IEEE Computer Society Press, Los Alamitos, CA, 49--57. Google ScholarDigital Library
- 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.Google Scholar
- Kay, M., Ed. 2007. XSL Transformations (XSLT) Version 2.0. W3C Recommendation. http://www.w3.org/TR/2007/REC-xslt20-20070123/.Google Scholar
- Klarlund, N., Møller, A., and Schwartzbach, M. I. 2002. The DSD schema language. Automat. Softw. Eng. 9, 3, 285--319. Google ScholarDigital Library
- Ladner, R. E. 1977. The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6, 3, 467--480.Google ScholarDigital Library
- Lakshmanan, L. V. S., Ramesh, G., Wang, H., and Zhao, Z. J. 2004. On testing satisfiability of tree pattern queries. In Proceedings of the 30th International Conference on Very Large Databases (VLDB'04), M. A. Nascimento, M. T. Özsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan-Kaufmann, San Francisco, CA, 120--131. Google ScholarDigital Library
- Lange, M., and Lutz, C. 2005. 2-ExpTime lower bounds for propositional dynamic logics with intersection. J. Symb. Logic 70, 5, 1072--1086.Google ScholarCross Ref
- Martens, W., Neven, F., Schwentick, T., and Bex, G. 2006. Expressiveness and complexity of XML schema. ACM Trans. Datab. Syst. 31, 3, 770--813. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Marx, M. 2005. Conditional XPath. ACM Trans. Datab. Syst. 30, 4, 929--959. Google ScholarDigital Library
- Marx, M., and de Rijke, M. 2005. Semantic characterizations of navigational XPath. ACM SIGMOD Rec. 34, 2, 41--46. Google ScholarDigital Library
- McNaughton, R., and Yamada, H. 1960. Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9, 39--47.Google ScholarCross Ref
- Miklau, G., and Suciu, D. 2004. Containment and equivalence for a fragment of XPath. J. ACM 51, 1, 2--45. Google ScholarDigital Library
- Murata, M., Lee, D., Mani, M., and Kawaguchi, K. 2005. Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Tech. 5, 4, 660--704. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Olteanu, D., Meuss, H., Furche, T., and Bry, F. 2002. XPath: Looking forward. In Proceedings of the Workshop on XML-Based Data Management (XMLDM'02), A. B. Chaudhri, R. Unland, C. Djeraba, and W. Lindner, Eds. Lecture Notes in Computer Science, vol. 2490. Springer-Verlag, Berlin, Germany, 109--127. Google ScholarDigital Library
- Papakonstantinou, Y., and Vianu, V. 2000. DTD inference for views of XML data. In Proceedings of the 19th Symposium on Principles of Database Systems (PODS'00). ACM, New York, 35--46. Google ScholarDigital Library
- Schwentick, T. 2004. XPath query containment. SIGMOD Rec. 33, 1, 101--109. Google ScholarDigital Library
- Stockmeyer, L. J. 1974. The complexity of decision problems in automata theory. Ph.D. dissertation. Department of Electrical Engineering, MIT, Cambridge, MA.Google Scholar
- Tajima, K., and Fukui, Y. 2004. Answering XPath queries over networks by sending minimal views. In Proceedings of the 30th International Conference on Very Large Databases (VLDB'04), M. A. Nascimento, M. T. Özsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 48--59. Google ScholarDigital Library
- ten Cate, B. 2006. The expressivity of XPath with transitive closure. In Proceedings of the 25th Symposium on Principles of Database Systems (PODS'06), S. Vansummeren, Ed. ACM, New York, 328--337. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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/.Google Scholar
- Vardi, M. 1998. Reasoning about the past with two-way automata. In Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP'98). Lecture Notes in Computer Science, vol. 1443. Springer-Verlag, Berlin, Germany, 628--641. Google ScholarDigital Library
- Wood, P. T. 2003. Containment for XPath fragments under DTD constraints. In Proceedings of the 9th International Conference on Database Technology (ICDT'03). Lecture Notes in Computer Science, vol. 2572. Springer-Verlag, Berlin, Germany, 300--314. Google ScholarDigital Library
Index Terms
- The complexity of query containment in expressive fragments of XPath 2.0
Recommendations
The complexity of query containment in expressive fragments of XPath 2.0
PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsQuery containment has been studied extensively for fragments of XPath 1.0. For instance, the problem is known to be ExpTime-complete for CoreXPath, the navigational core of XPath 1.0. Much less is known about query containment in (fragments of) the ...
Decidability of Downward XPath
We investigate the satisfiability problem for downward-XPath, the fragment of XPath that includes the child and descendant axes, and tests for (in)equality of attributes’ values. We prove that this problem is decidable, EXPTIME-complete. These bounds ...
Satisfiability of simple xpath fragments in the presence of dtds
WIDM '09: Proceedings of the eleventh international workshop on Web information and data managementFor an XPath expression q and a DTD D, q is satisfiable under D if there exists an XML document t such that t is valid against D and that the answer of q on t is nonempty. Evaluating an unsatisfiable XPath expression is meaningless, since such an ...
Comments