{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:50Z","timestamp":1773481910632,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["GR\/S63205\/01GR\/T27433\/01"],"award-info":[{"award-number":["GR\/S63205\/01GR\/T27433\/01"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60228006"],"award-info":[{"award-number":["60228006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>\n            We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query\n            <jats:italic>p<\/jats:italic>\n            in an XPath fragment and a DTD\n            <jats:italic>D<\/jats:italic>\n            , whether or not there exists an XML document\n            <jats:italic>T<\/jats:italic>\n            such that\n            <jats:italic>T<\/jats:italic>\n            conforms to\n            <jats:italic>D<\/jats:italic>\n            and the answer of\n            <jats:italic>p<\/jats:italic>\n            on\n            <jats:italic>T<\/jats:italic>\n            is nonempty. We consider a variety of XPath fragments widely used in practice, and investigate the impact of different XPath operators on the satisfiability analysis. We first study the problem for negation-free XPath fragments with and without upward axes, recursion and data-value joins, identifying which factors lead to tractability and which to NP-completeness. We then turn to fragments with negation but without data values, establishing lower and upper bounds in the absence and in the presence of upward modalities and recursion. We show that with negation the complexity ranges from PSPACE to EXPTIME. Moreover, when both data values and negation are in place, we find that the complexity ranges from NEXPTIME to undecidable. Furthermore, we give a finer analysis of the problem for particular classes of DTDs, exploring the impact of various DTD constructs, identifying tractable cases, as well as providing the complexity in the query size alone. Finally, we investigate the problem for XPath fragments with sibling axes, exploring the impact of horizontal modalities on the satisfiability analysis.\n          <\/jats:p>","DOI":"10.1145\/1346330.1346333","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":103,"title":["XPath satisfiability in the presence of DTDs"],"prefix":"10.1145","volume":"55","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[{"name":"Oxford University, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK, and Bell Laboratories, Murray Hill, New Jersey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK, and Hasselt University, and Transnational University of Limburg, Limburg, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.15.115-135"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0076-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.030"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer-Verlag New York.  B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_1_6_1","unstructured":"Bray T. Paoli J. and Sperberg-McQueen C. M. 1998. Extensible markup language (XML) 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/REC-xml.  Bray T. Paoli J. and Sperberg-McQueen C. M. 1998. Extensible markup language (XML) 1.0. W3C Recommendation. http:\/\/www.w3.org\/TR\/REC-xml."},{"key":"e_1_2_1_7_1","volume-title":"Revised Papers of the 8th International Workshop on Database Programming Languages (DBPL","volume":"2397","author":"Calvanese D.","year":"2001","unstructured":"Calvanese , D. , De Giacomo , G. , Lenzerini , M. , and Vardi , M. Y . 2001. View-based query answering and query containment over semistructured data . In Revised Papers of the 8th International Workshop on Database Programming Languages (DBPL 2001 ), G. Ghelli and G. Grahne, Eds. Lecture Notes in Computer Science , vol. 2397 . Springer-Verlag. New York, 40--61. Calvanese, D., De Giacomo, G., Lenzerini, M., and Vardi, M. Y. 2001. View-based query answering and query containment over semistructured data. In Revised Papers of the 8th International Workshop on Database Programming Languages (DBPL 2001), G. Ghelli and G. Grahne, Eds. Lecture Notes in Computer Science, vol. 2397. Springer-Verlag. New York, 40--61."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Chamberlin D. Boag S. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2001. XQuery 1.0: An XML query language. W3C Working Draft.  Chamberlin D. Boag S. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2001. XQuery 1.0: An XML query language. W3C Working Draft.","DOI":"10.1007\/3-540-45271-0_1"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press","author":"Chan C.","unstructured":"Chan , C. , Felber , P. , Garofalakis , M. , and Rastogi , R . 2002. Efficient filtering of XML documents with XPath expressions . In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press , Los Alamitos, CA, 235--244. Chan, C., Felber, P., Garofalakis, M., and Rastogi, R. 2002. Efficient filtering of XML documents with XPath expressions. In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 235--244."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90036-X"},{"key":"e_1_2_1_11_1","unstructured":"Clark J. and DeRose S. 1999. XML Path Language (XPath). W3C Recommendation.  Clark J. and DeRose S. 1999. XML Path Language (XPath). W3C Recommendation."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.032"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007634"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th International Workshop on Database Programming Languages (DBPL)","author":"Hidders J.","unstructured":"Hidders , J. 2004. Satisfiability of XPath expressions . In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL) . Lecture Notes in Computer Science , vol. 2921 . Springer-Verlag , New York , 21--36. Hidders, J. 2004. Satisfiability of XPath expressions. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 2921. Springer-Verlag, New York, 21--36."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Hopcroft J. E. and Ullman J. D. 2000. Introduction to Automata Theory Languages and Computation (2nd Edition). Addison Wesley. Reading MA.   Hopcroft J. E. and Ullman J. D. 2000. Introduction to Automata Theory Languages and Computation (2nd Edition). Addison Wesley. Reading MA.","DOI":"10.1145\/568438.568455"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"TAX: A tree algebra for XML. In Proceedings of the 8th International Workshop on Database Programming Languages (DBPL)","author":"Jagadish H.","year":"2002","unstructured":"Jagadish , H. , Lakshmanan , L. , Srivastava , D. , and Thompson , K . 2002 . TAX: A tree algebra for XML. In Proceedings of the 8th International Workshop on Database Programming Languages (DBPL) . Lecture Notes in Computer Science , vol. 2397 . Springer-Verlag , New York , 149--164. Jagadish, H., Lakshmanan, L., Srivastava, D., and Thompson, K. 2002. TAX: A tree algebra for XML. In Proceedings of the 8th International Workshop on Database Programming Languages (DBPL). Lecture Notes in Computer Science, vol. 2397. Springer-Verlag, New York, 149--164."},{"key":"e_1_2_1_20_1","volume-title":"Lecture Notes in Computer Science","volume":"2154","author":"Kuperferman O.","unstructured":"Kuperferman , O. , Piterman , N. , and Vardi , M. Y . 2001. Extended temporal logic revisited . Lecture Notes in Computer Science , vol. 2154 . Springer-Verlag, New York, 519--535. Kuperferman, O., Piterman, N., and Vardi, M. Y. 2001. Extended temporal logic revisited. Lecture Notes in Computer Science, vol. 2154. Springer-Verlag, New York, 519--535."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Lakshmanan L.","unstructured":"Lakshmanan , L. , Ramesh , G. , Wang , H. , and Zhao , Z . 2004. On testing satisfiability of tree pattern queries . In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 120--131. Lakshmanan, L., Ramesh, G., Wang, H., and Zhao, Z. 2004. On testing satisfiability of tree pattern queries. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 120--131."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055563"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.035"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th International Conference on Extending Database Technology (EDBT)","author":"Marx M.","unstructured":"Marx , M. 2004. XPath with conditional axis relations . In Proceedings of the 9th International Conference on Extending Database Technology (EDBT) . Lecture Notes in Computer Science , vol. 2992 . Springer-Verlag , New York , 477--494. Marx, M. 2004. XPath with conditional axis relations. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT). Lecture Notes in Computer Science, vol. 2992. Springer-Verlag, New York, 477--494."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083792"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00030-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375569"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335217"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of Workshop on XML-Based Data Management and Multimedia Engineering (XMLDM). Lecture Notes in Computer Science","volume":"2490","author":"Olteanu D.","unstructured":"Olteanu , D. , Meuss , H. , Furche , T. , and Bry , F . 2002. XPath: Looking forward . In Proceedings of Workshop on XML-Based Data Management and Multimedia Engineering (XMLDM). Lecture Notes in Computer Science , vol. 2490 . Springer-Verlag, New York, 109--127. Olteanu, D., Meuss, H., Furche, T., and Bry, F. 2002. XPath: Looking forward. In Proceedings of Workshop on XML-Based Data Management and Multimedia Engineering (XMLDM). Lecture Notes in Computer Science, vol. 2490. Springer-Verlag, New York, 109--127."},{"key":"e_1_2_1_32_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison-Wesley , Reading, MA . Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007579"},{"key":"e_1_2_1_34_1","volume-title":"The complexity of decision problems in automata theory and logic. Tech. rep","author":"Stockmeyer L.","unstructured":"Stockmeyer , L. 1974. The complexity of decision problems in automata theory and logic. Tech. rep . MIT , Cambridge, MA . Stockmeyer, L. 1974. The complexity of decision problems in automata theory and logic. Tech. rep. MIT, Cambridge, MA."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of Workshop on Programming Language Technologies for XML (Plan-X). 40--53","author":"Sur G.","unstructured":"Sur , G. , Hammer , J. , and Sim\u00e9on , J . 2004. An XQuery-based language for processing updates in XML . In Proceedings of Workshop on Programming Language Technologies for XML (Plan-X). 40--53 . Sur, G., Hammer, J., and Sim\u00e9on, J. 2004. An XQuery-based language for processing updates in XML. In Proceedings of Workshop on Programming Language Technologies for XML (Plan-X). 40--53."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90026-7"},{"key":"e_1_2_1_38_1","unstructured":"W3C. 2006. XML Path Language (XPath) 2.0. W3C Recommendation.  W3C. 2006. XML Path Language (XPath) 2.0. W3C Recommendation."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 4th International Workshop on the Web and Databases (WebDB). 13--18","author":"Wood P.","year":"2001","unstructured":"Wood , P. 2001 . Minimising simple XPath expressions . In Proceedings of the 4th International Workshop on the Web and Databases (WebDB). 13--18 . Wood, P. 2001. Minimising simple XPath expressions. In Proceedings of the 4th International Workshop on the Web and Databases (WebDB). 13--18."},{"key":"e_1_2_1_40_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th International Conference (ICDT)","author":"Wood P.","unstructured":"Wood , P. 2002. Containment for XPath fragments under DTD constraints . In Proceedings of the 9th International Conference (ICDT) . Lecture Notes in Computer Science , vol. 2572 . Springer-Verlag , New York , 300--314. Wood, P. 2002. Containment for XPath fragments under DTD constraints. In Proceedings of the 9th International Conference (ICDT). Lecture Notes in Computer Science, vol. 2572. Springer-Verlag, New York, 300--314."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1346330.1346333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1346330.1346333"],"URL":"https:\/\/doi.org\/10.1145\/1346330.1346333","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2007-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}