{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T17:15:20Z","timestamp":1712423720995},"reference-count":109,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2009,1,15]]},"abstract":"This survey gives an overview of formal results on the XML query language XPath. We identify several important fragments of XPath, focusing on subsets of XPath 1.0. We then give results on the expressiveness of XPath and its fragments compared to other formalisms for querying trees, algorithms, and complexity bounds for evaluation of XPath queries, as well as static analysis of XPath queries.<\/jats:p>","DOI":"10.1145\/1456650.1456653","type":"journal-article","created":{"date-parts":[[2009,1,13]],"date-time":"2009-01-13T13:15:48Z","timestamp":1231852548000},"page":"1-54","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["XPath leashed"],"prefix":"10.1145","volume":"41","author":[{"given":"Michael","family":"Benedikt","sequence":"first","affiliation":[{"name":"Oxford University Computing Laboratory, Oxford, UK"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2009,1,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.15.115-135"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018445.1022179"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584817"},{"key":"e_1_2_1_5_1","volume-title":"the 18th International Conference on Data Engineering (ICDE).","author":"Al-Khalifa S."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases (VLDB), 53--64","author":"Altinel M."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375730"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065195"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.51"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 63--79","author":"Beauquier D."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_37"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT), 79--95","author":"Benedikt M."},{"key":"e_1_2_1_15_1","unstructured":"Bird S. Chen Y. Davidson S. Lee H. and Zheng Y. 2005. Extending XPath to support linguistic queries. In PLAN-X. Bird S. Chen Y. Davidson S. Lee H. and Zheng Y. 2005. Extending XPath to support linguistic queries. In PLAN-X."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer. B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.69"},{"key":"e_1_2_1_18_1","volume-title":"Tech. Rep. HKUST-TCSC-2001-05","author":"Br\u00fcggemann-Klein A.","year":"2001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Annual IEEE Symposium on Logic in Computer Science (LICS).","author":"Burch J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Carme J. Niehren J. and Tommasi M. 2004. Querying unranked trees with stepwise tree automata. In Rewriting Techniques and Applications. Carme J. Niehren J. and Tommasi M. 2004. Querying unranked trees with stepwise tree automata. In Rewriting Techniques and Applications.","DOI":"10.1007\/978-3-540-25979-4_8"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE).","author":"Chan C. Y."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 6th International Conference on Database Theory (ICDT), 56--70","author":"Chekuri C."},{"key":"e_1_2_1_24_1","unstructured":"Clarke E. M. Grumberg O. and Peled D. 2000. Model Checking. MIT Press. Clarke E. M. Grumberg O. and Peled D. 2000. Model Checking. MIT Press."},{"key":"e_1_2_1_25_1","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Workshop on Knowledge Representation Meets Databases (KRDB). CEUR Workshop Proceedings 45","author":"Deutsch A."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering (ICDE).","author":"Diao Y."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2953"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2846"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007634"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Workshop on Web and Databases (WebDB).","author":"Fiebig T."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science (LICS).","author":"Frick M."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS), 189--202","author":"Gottlob G."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), 95--106","author":"Gottlob G."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059520"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055585"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 11th International Symposium on Database Programming Languages (DBPL).","author":"G\u00f6tz M."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247512"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.2307\/421196"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT).","author":"Green T. J."},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Greenlaw R. Hoover H. J. and Ruzzo W. L. 1995. Limits to parallel computation: P-completeness theory. Oxford University Press. Greenlaw R. Hoover H. J. and Ruzzo W. L. 1995. Limits to parallel computation: P-completeness theory. Oxford University Press.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.062"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 524--525","author":"Grust T."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974754"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 9th International Conference on Database Programming Language (DBPL).","author":"Hidders J.","year":"2003"},{"key":"e_1_2_1_55_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA. Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addison-Wesley Reading MA."},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Immerman N. 1999. Descriptive Complexity. Springer Graduate Texts in Computer Science. Immerman N. 1999. Descriptive Complexity. Springer Graduate Texts in Computer Science.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_57_1","volume-title":"Handbook of Theoretical Computer Science","author":"Johnson D. S."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0123-7"},{"key":"e_1_2_1_59_1","unstructured":"Kamp H. 1968. Tense logic and the theory of linear order. Ph.D. thesis University of California Los Angeles. Kamp H. 1968. Tense logic and the theory of linear order. Ph.D. thesis University of California Los Angeles."},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), 249--260","author":"Koch C.","year":"2003"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 30th International Conference on Very Large Databases (VLDB), 120--131","author":"Lakshmanan L. V. S."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1129642115"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Libkin L. 2004. Elements of Finite Model Theory. Springer. Libkin L. 2004. Elements of Finite Model Theory. Springer.","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055562"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_28"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_8"},{"key":"e_1_2_1_68_1","volume-title":"the TDM Workshop on XML Databases and Information Retrieval.","author":"Marx M."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841920_2"},{"key":"e_1_2_1_70_1","series-title":"Lecture Notes in Mathematics","volume-title":"Proceedings of the Logic Colloquium","author":"Meyer A. R."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543623"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Neumann A. and Seidl H . 1998 . Locating matches of tree patterns in forests. In Proceedings of the 18th Conference on Foundations on Software Technology and Theoretical Computer Science (FSTTCS) Lecture Notes in Computer Science vol. 1530 . 134--145. Neumann A. and Seidl H. 1998. Locating matches of tree patterns in forests. In Proceedings of the 18th Conference on Foundations on Software Technology and Theoretical Computer Science (FSTTCS) Lecture Notes in Computer Science vol. 1530. 134--145.","DOI":"10.1007\/978-3-540-49382-2_12"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT). 315--329","author":"Neven F."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505245"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1063"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering (ICDE). Full version in Tech. Rep. PMS-FB-2002-12","author":"Olteanu D.","year":"2002"},{"key":"e_1_2_1_79_1","volume-title":"Proceedings of the EDBT Workshop on XML Data Management. Lecture Notes in Computer Science","volume":"2490","author":"Olteanu D."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007686"},{"key":"e_1_2_1_81_1","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley. Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872810"},{"key":"e_1_2_1_83_1","volume-title":"Proceedings of the International Conference on Management of Data (COMAD), 41--52","author":"Ramanan P.","year":"2005"},{"key":"e_1_2_1_84_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games\u2014A Guide to Current Research, E. Gr\u00e4del et al., eds","author":"Reinhardt K."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974140"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.003"},{"key":"e_1_2_1_87_1","doi-asserted-by":"crossref","unstructured":"Schwentick T. The\u0155ien D. and Vollmer H. 2001. Partially-Ordered two-way automata: A new characterization of DA. In Developments in Language Theory 239--250. Schwentick T. The\u0155ien D. and Vollmer H. 2001. Partially-Ordered two-way automata: A new characterization of DA. In Developments in Language Theory 239--250.","DOI":"10.1007\/3-540-46011-X_20"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543622"},{"key":"e_1_2_1_89_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB), 302--314","author":"Shanmugasundaram J."},{"key":"e_1_2_1_90_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Conference on Mathematical Foundations of Computer Science (MFCS)","author":"Sudborough I."},{"key":"e_1_2_1_91_1","volume-title":"Proceedings of the ACM SIGPLAN Workshop on Programming Language Technologies for XML (PLAN-X).","author":"Sur G."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564715"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276749"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90026-7"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90020-6"},{"key":"e_1_2_1_99_1","unstructured":"Wadler P. 2000. Two semantics for XPath. http:\/\/www.research.avayalabs.com\/user\/wadler\/. Wadler P. 2000. Two semantics for XPath. http:\/\/www.research.avayalabs.com\/user\/wadler\/."},{"key":"e_1_2_1_100_1","volume-title":"MIT Press","author":"Wadler P.","year":"1999"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1007\/11547273_5"},{"key":"e_1_2_1_102_1","volume-title":"Proceedings of International Workshop on the Web and Databases (WebDB).","author":"Wood P. T.","year":"2001"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656434"},{"key":"e_1_2_1_104_1","unstructured":"World Wide Web Consortium. 1999a. XML path language (XPath) recommendation. http:\/\/www.w3c.org\/TR\/xpath\/. World Wide Web Consortium. 1999a. XML path language (XPath) recommendation. http:\/\/www.w3c.org\/TR\/xpath\/."},{"key":"e_1_2_1_105_1","unstructured":"World Wide Web Consortium. 1999b. XSL transformations (XSLT). W3C recommendation version 1.0. http:\/\/www.w3.org\/TR\/xslt. World Wide Web Consortium. 1999b. XSL transformations (XSLT). W3C recommendation version 1.0. http:\/\/www.w3.org\/TR\/xslt."},{"key":"e_1_2_1_106_1","unstructured":"World Wide Web Consortium. 2001. XML schema part 0: Primer. W3C recommendation. http:\/\/www.w3c.org\/XML\/Schema. World Wide Web Consortium. 2001. XML schema part 0: Primer. W3C recommendation. http:\/\/www.w3c.org\/XML\/Schema."},{"key":"e_1_2_1_107_1","unstructured":"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\/. 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_108_1","doi-asserted-by":"crossref","unstructured":"World Wide Web Consortium. 2007. XML path language (XPath) 2.0. World Wide Web Consortium. 2007. XML path language (XPath) 2.0.","DOI":"10.1145\/1242572.1242842"},{"key":"e_1_2_1_109_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases (VLDB), 82--94","author":"Yannakakis M.","year":"1981"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1456650.1456653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T15:40:26Z","timestamp":1684856426000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1456650.1456653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,15]]},"references-count":109,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1,15]]}},"alternative-id":["10.1145\/1456650.1456653"],"URL":"https:\/\/doi.org\/10.1145\/1456650.1456653","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,15]]},"assertion":[{"value":"2006-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}