The complexity of query containment in expressive fragments of XPath 2.0

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of query containment in expressive fragments of XPath 2.0

Full text

Pdf (675 KB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 6 (September 2009) table of contents

Article No. 31

Year of Publication: 2009

ISSN:0004-5411

Authors

Balder ten Cate	INRIA and ENS Cachan, Cedex, France
Carsten Lutz	Universität Bremen, Bremen, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 75, Downloads (12 Months): 75, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1568318.1568321 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Benedikt, M., Fan, W. and Geerts, F. 2008. XPath satisfiability in the presence of DTDs. J. ACM 55, 2, 1--79.
	3	Benedikt, M., Fan, W., and Kuper, G. M. 2005. Structural properties of XPath fragments. Theoret. Comput. Sci. 336, 1, 3--31.
	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	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.
	7	Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J. 1981. Alternation. J. ACM 28, 1, 114-- 133.
	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	Deutsch, A. and Tannen, V. 2005. XML queries and constraints, containment and reformulation. Theoret. Comput. Sci. 336, 1, 57--87.
	11	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.
	12	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.
	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	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.
	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	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.
	19	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.
	20	Gottlob, G., Koch, C., and Schulz, K. U. 2006. Conjunctive queries over trees. J. ACM 53, 2, 238--272.
	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	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.
	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	Klarlund, N., Møller, A., and Schwartzbach, M. I. 2002. The DSD schema language. Automat. Softw. Eng. 9, 3, 285--319.
	27	Ladner, R. E. 1977. The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6, 3, 467--480.
	28	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.
	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	Martens, W., Neven, F., Schwentick, T., and Bex, G. 2006. Expressiveness and complexity of XML schema. ACM Trans. Datab. Syst. 31, 3, 770--813.
	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	Marx, M. 2005. Conditional XPath. ACM Trans. Datab. Syst. 30, 4, 929--959.
	33	Marx, M., and de Rijke, M. 2005. Semantic characterizations of navigational XPath. ACM SIGMOD Rec. 34, 2, 41--46.
	34	McNaughton, R., and Yamada, H. 1960. Regular expressions and state graphs for automata. IEEE Trans. Electron. Comput. 9, 39--47.
	35	Miklau, G., and Suciu, D. 2004. Containment and equivalence for a fragment of XPath. J. ACM 51, 1, 2--45.
	36	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.
	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	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.
	39	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.
	40	Schwentick, T. 2004. XPath query containment. SIGMOD Rec. 33, 1, 101--109.
	41	Stockmeyer, L. J. 1974. The complexity of decision problems in automata theory. Ph.D. dissertation. Department of Electrical Engineering, MIT, Cambridge, MA.
	42	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.
	43	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.
	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	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.
	47	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.