{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T07:57:37Z","timestamp":1768118257682,"version":"3.49.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We show that XPath can be processed much more efficiently, and propose main-memory algorithms for this problem with polynomial-time combined query evaluation complexity. Moreover, we show how the main ideas of our algorithm can be profitably integrated into existing XPath processors. Finally, we present two fragments of XPath for which linear-time query processing algorithms exist and another fragment with linear-space\/quadratic-time query processing.<\/jats:p>","DOI":"10.1145\/1071610.1071614","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"444-491","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":147,"title":["Efficient algorithms for processing XPath queries"],"prefix":"10.1145","volume":"30","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02)","author":"Al-Khalifa S.","unstructured":"Al-Khalifa , S. , Srivastava , D. , Jagadish , H. V. , Koudas , N. , Patel , J. M. , and Wu , Y . 2002. Structural joins: A primitive for efficient XML query pattern matching . In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02) (San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif. Al-Khalifa, S., Srivastava, D., Jagadish, H. V., Koudas, N., Patel, J. M., and Wu, Y. 2002. Structural joins: A primitive for efficient XML query pattern matching. In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02) (San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'2000)","author":"Altinel M.","unstructured":"Altinel , M. and Franklin , M . 2000. Efficient filtering of XML documents for selective dissemination of information . In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'2000) (Cairo, Egypt). 53--64. Altinel, M. and Franklin, M. 2000. Efficient filtering of XML documents for selective dissemination of information. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'2000) (Cairo, Egypt). 53--64."},{"key":"e_1_2_1_3_1","volume-title":"Xalan-Java version 2.2.D11","author":"Apache Foundation","unstructured":"Apache Foundation . 2004. Xalan-Java version 2.2.D11 . http:\/\/xml.apache.org\/xalan-j\/. Apache Foundation. 2004. Xalan-Java version 2.2.D11. http:\/\/xml.apache.org\/xalan-j\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055584"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02)","author":"Chan C. Y.","unstructured":"Chan , C. Y. , Fan , W. , Felber , P. , Garofalakis , M. N. , and Rastogi , R . 2002a. Tree pattern aggregation for scalable XML data dissemination . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02) (Hong Kong, China). 826--837. Chan, C. Y., Fan, W., Felber, P., Garofalakis, M. N., and Rastogi, R. 2002a. Tree pattern aggregation for scalable XML data dissemination. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB'02) (Hong Kong, China). 826--837."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02)","author":"Chan C. Y.","unstructured":"Chan , C. Y. , Felber , P. , Garofalakis , M. N. , and Rastogi , R . 2002b. Efficient filtering of XML documents with XPath expressions . In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02) (San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif. Chan, C. Y., Felber, P., Garofalakis, M. N., and Rastogi, R. 2002b. Efficient filtering of XML documents with XPath expressions. In Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE'02) (San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif."},{"key":"e_1_2_1_8_1","unstructured":"Clark J. 1999. XT---A Java implementation of XSLT. http:\/\/www.jclark.com\/xml\/xt.html\/.  Clark J. 1999. XT---A Java implementation of XSLT. http:\/\/www.jclark.com\/xml\/xt.html\/."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02)","author":"Gottlob G.","unstructured":"Gottlob , G. and Koch , C . 2002. Monadic queries over tree-structured data . In Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02) (Copenhagen, Denmark). IEEE Computer Society Press, Los Alamitos, Calif. 189--202. Gottlob, G. and Koch, C. 2002. Monadic queries over tree-structured data. In Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02) (Copenhagen, Denmark). IEEE Computer Society Press, Los Alamitos, Calif. 189--202."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT'03)","author":"Green T. J.","unstructured":"Green , T. J. , Miklau , G. , Onizuka , M. , and Suciu , D . 2003. Processing XML streams with deterministic automata . In Proceedings of the 9th International Conference on Database Theory (ICDT'03) . 173--189. Green, T. J., Miklau, G., Onizuka, M., and Suciu, D. 2003. Processing XML streams with deterministic automata. In Proceedings of the 9th International Conference on Database Theory (ICDT'03). 173--189."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974754"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"e_1_2_1_14_1","unstructured":"Kay M. 2003. Saxon version 6.5.2. http:\/\/saxon.sourceforge.net\/.  Kay M. 2003. Saxon version 6.5.2. http:\/\/saxon.sourceforge.net\/."},{"key":"e_1_2_1_16_1","unstructured":"Microsoft Corporation. 2001. Internet Explorer IE6. http:\/\/www.microsoft.com\/windows\/ie\/default.asp.  Microsoft Corporation. 2001. Internet Explorer IE6. http:\/\/www.microsoft.com\/windows\/ie\/default.asp."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872810"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773170"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1162\/10996620052104302"},{"key":"e_1_2_1_22_1","unstructured":"Wadler P. 2000. Two semantics for XPath. Draft paper available at http:\/\/www.research.avayalabs. com\/user\/wadler\/.  Wadler P. 2000. Two semantics for XPath. Draft paper available at http:\/\/www.research.avayalabs. com\/user\/wadler\/."},{"key":"e_1_2_1_23_1","unstructured":"World Wide Web Consortium. 1998. XSL working draft http:\/\/www.w3.org\/TR\/1998\/WD-xsl-19981216.  World Wide Web Consortium. 1998. XSL working draft http:\/\/www.w3.org\/TR\/1998\/WD-xsl-19981216."},{"key":"e_1_2_1_24_1","unstructured":"World Wide Web Consortium. 1999. XML Path Language (XPath) Recommendation. http:\/\/www.w3c.org\/TR\/xpath\/.  World Wide Web Consortium. 1999. XML Path Language (XPath) Recommendation. http:\/\/www.w3c.org\/TR\/xpath\/."},{"key":"e_1_2_1_25_1","volume-title":"Extensible Markup Language (XML) 1.0","author":"World Wide Web Consortium","unstructured":"World Wide Web Consortium . 2000. Extensible Markup Language (XML) 1.0 ( second edition). http:\/\/www.w3.org\/TR\/REC-xml. World Wide Web Consortium. 2000. Extensible Markup Language (XML) 1.0 (second edition). http:\/\/www.w3.org\/TR\/REC-xml."},{"key":"e_1_2_1_26_1","volume-title":"W3C working draft (Aug. 16th","author":"World Wide Web Consortium","year":"2002","unstructured":"World Wide Web Consortium . 2002. X Query 1. 0 and X Path 2.0 formal semantics. W3C working draft (Aug. 16th 2002 ). http:\/\/www.w3.org\/TR\/query-algebra\/. World Wide Web Consortium. 2002. XQuery 1.0 and XPath 2.0 formal semantics. W3C working draft (Aug. 16th 2002). http:\/\/www.w3.org\/TR\/query-algebra\/."},{"key":"e_1_2_1_27_1","unstructured":"World Wide Web Consortium. 2004a. DOM Specification http:\/\/www.w3c.org\/DOM\/.  World Wide Web Consortium. 2004a. DOM Specification http:\/\/www.w3c.org\/DOM\/."},{"key":"e_1_2_1_28_1","unstructured":"World Wide Web Consortium. 2004b. XML Path Language (XPath) 2.0 working draft. http:\/\/www.w3.org\/TR\/2004\/WD-xpath20-20040723\/.  World Wide Web Consortium. 2004b. XML Path Language (XPath) 2.0 working draft. http:\/\/www.w3.org\/TR\/2004\/WD-xpath20-20040723\/."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81)","author":"Yannakakis M.","year":"1981","unstructured":"Yannakakis , M. 1981 . Algorithms for acyclic database schemes . In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81) . 82--94. Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases (VLDB'81). 82--94."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:27:38Z","timestamp":1672244858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071614"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071614","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}