{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:35Z","timestamp":1750307735973,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.508"],"award-info":[{"award-number":["639.021.508"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST-2005-7603"],"award-info":[{"award-number":["IST-2005-7603"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1568318.1568321","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["The complexity of query containment in expressive fragments of XPath 2.0"],"prefix":"10.1145","volume":"56","author":[{"given":"Balder ten","family":"Cate","sequence":"first","affiliation":[{"name":"INRIA and ENS Cachan, Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646895"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.030"},{"key":"e_1_2_1_4_1","volume-title":"Eds","author":"Berglund A.","year":"2007","unstructured":"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\/. 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\/."},{"key":"e_1_2_1_5_1","volume-title":"Eds","author":"Boag S.","year":"2007","unstructured":"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\/. 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\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018432.1021539"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_8_1","unstructured":"Clark J. and DeRose S. J. eds. 1999. XML Path Language (XPath) Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/xpath.  Clark J. and DeRose S. J. eds. 1999. XML Path Language (XPath) Version 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/xpath."},{"key":"e_1_2_1_9_1","unstructured":"Clark J. and Murata M. 2001. RELAX NG specification. http:\/\/relaxng.org\/spec-20011203.html.  Clark J. and Murata M. 2001. RELAX NG specification. http:\/\/relaxng.org\/spec-20011203.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.032"},{"key":"e_1_2_1_11_1","first-page":"2","article-title":"Regular expressions: New results and open problems","volume":"9","author":"Ellul K.","year":"2004","unstructured":"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. 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.","journal-title":"J. Automata, Lang. Combin."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2953"},{"volume-title":"Proceedings of the 23rd International Conference on Data Engineering (ICDE'07)","author":"Fan W.","key":"e_1_2_1_13_1","unstructured":"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. 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."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646234.682559"},{"key":"e_1_2_1_15_1","volume-title":"Eds","author":"Gao S.","year":"2007","unstructured":"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\/. 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\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8"},{"volume-title":"Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS'08)","author":"Gelade W.","key":"e_1_2_1_17_1","unstructured":"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\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany, 325--336. 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\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany, 325--336."},{"volume-title":"Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS'02)","author":"Gottlob G.","key":"e_1_2_1_18_1","unstructured":"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. 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."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059520"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_2_1_21_1","volume-title":"Eds","author":"Gr\u00e4del E.","year":"2002","unstructured":"Gr\u00e4del , E. , Thomas , W. , and Wilke , T. , Eds . 2002 . Automata, Logics and Infinite Games. Lecture Notes in Computer Science, vol. 2500 . Springer-Verlag , Berlin, Germany. Gr\u00e4del, E., Thomas, W., and Wilke, T., Eds. 2002. Automata, Logics and Infinite Games. Lecture Notes in Computer Science, vol. 2500. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2004.46"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IDEAS.2005.39"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 9th International Workshop on Data Base Programming Languages (DBPL'03)","volume":"2921","author":"Hidders J.","year":"2003","unstructured":"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. 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."},{"key":"e_1_2_1_25_1","unstructured":"Kay M. Ed. 2007. XSL Transformations (XSLT) Version 2.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xslt20-20070123\/.  Kay M. Ed. 2007. XSL Transformations (XSLT) Version 2.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xslt20-20070123\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016376608070"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"volume-title":"Proceedings of the 30th International Conference on Very Large Databases (VLDB'04)","author":"Lakshmanan L. V. S.","key":"e_1_2_1_28_1","unstructured":"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. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan-Kaufmann, San Francisco, CA, 120--131. 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. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan-Kaufmann, San Francisco, CA, 120--131."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1129642115"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166076"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_28"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114247"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083792"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111627.1111631"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Workshop on XML-Based Data Management (XMLDM'02)","volume":"2490","author":"Olteanu D.","unstructured":"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. 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."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974140"},{"volume-title":"Proceedings of the 30th International Conference on Very Large Databases (VLDB'04)","author":"Tajima K.","key":"e_1_2_1_42_1","unstructured":"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. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 48--59. 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. \u00d6zsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 48--59."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142398"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_10"},{"key":"e_1_2_1_45_1","volume-title":"eds","author":"Thompson H. S.","year":"2004","unstructured":"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\/. 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\/."},{"key":"e_1_2_1_46_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP'98)","author":"Vardi M.","unstructured":"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. 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."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1568318.1568321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:49Z","timestamp":1750253929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1568318.1568321"],"URL":"https:\/\/doi.org\/10.1145\/1568318.1568321","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}