{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T15:44:49Z","timestamp":1775058289467,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p>XPath 1.0 is a variable free language designed to specify paths between nodes in XML documents. Such paths can alternatively be specified in first-order logic. The logical abstraction of XPath 1.0, usually called Navigational or Core XPath, is not powerful enough to express every first-order definable path. In this article, we show that there exists a natural expansion of Core XPath in which every first-order definable path in XML document trees is expressible. This expansion is called Conditional XPath. It contains additional axis relations of the form (child::n[F])+, denoting the transitive closure of the path expressed by child::n[F]. The difference with XPath's descendant::n[F] is that the path (child::n[F])+ is conditional on the fact that all nodes in between the start and end node of the path should also be labeled by n and should make the predicate F true. This result can be viewed as the XPath analogue of the expressive completeness of the relational algebra with respect to first-order logic.<\/jats:p>","DOI":"10.1145\/1114244.1114247","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"929-959","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":83,"title":["Conditional XPath"],"prefix":"10.1145","volume":"30","author":[{"given":"Maarten","family":"Marx","sequence":"first","affiliation":[{"name":"ISLA, Universiteit van Amsterdam, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2005,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.6.939"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.3.325"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.51"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 10th International Conference on Database Theory (ICDT","author":"Benedikt M.","year":"2003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Blackburn P. de Rijke M. and Venema Y. 2001. Modal Logic. Cambridge University Press.]] Blackburn P. de Rijke M. and Venema Y. 2001. Modal Logic. Cambridge University Press.]]","DOI":"10.1017\/CBO9781107050884"},{"key":"e_1_2_1_6_1","volume-title":"Ed. Lecture Notes in Computer Science","volume":"1092","author":"Blackburn P.","year":"1996"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/9.3.295"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_9_1","unstructured":"Codd E. 1972. Relational completeness of data base sublanguages. In Database Systems R. Rustin Ed. Prentice-Hall Englewood Cliffs NJ 33--64.]] Codd E. 1972. Relational completeness of data base sublanguages. In Database Systems R. Rustin Ed. Prentice-Hall Englewood Cliffs NJ 33--64.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Ebbinghaus H.-D. and Flum J. 1995. Finite model theory. Perspectives in Mathematical Logic. Springer-Verlag New York.]] Ebbinghaus H.-D. and Flum J. 1995. Finite model theory. Perspectives in Mathematical Logic. Springer-Verlag New York.]]","DOI":"10.1007\/978-3-662-03182-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/788019.788879"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02)","author":"Frick M."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Gabbay D. Hodkinson I. and Reynolds M. 1994. Temporal Logic. Volume 1: Mathematical Foundations and Computational Aspects. Oxford Science Publications.]] Gabbay D. Hodkinson I. and Reynolds M. 1994. Temporal Logic. Volume 1: Mathematical Foundations and Computational Aspects. Oxford Science Publications.]]","DOI":"10.1093\/oso\/9780198537694.003.0001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/567446.567462"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02)","author":"Gottlob G."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Very Large Databases.]]","author":"Gottlob G."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055585"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Harel D. Kozen D. and Tiuryn J. 2000. Dynamic Logic. MIT Press Cambridge MA.]] Harel D. Kozen D. and Tiuryn J. 2000. Dynamic Logic. MIT Press Cambridge MA.]]","DOI":"10.7551\/mitpress\/2516.001.0001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Symposium of Logic in Computer Science. Computer Society Press, Washington, 236--244","author":"Immerman N."},{"key":"e_1_2_1_23_1","unstructured":"Kamp J. 1968. Tense logic and the theory of linear order. Ph.D. dissertation University of California Los Angeles Los Angeles CA.]] Kamp J. 1968. Tense logic and the theory of linear order. Ph.D. dissertation University of California Los Angeles Los Angeles CA.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_1_25_1","volume-title":"Logical Aspects of Computational Linguistics","author":"Kracht M."},{"key":"e_1_2_1_26_1","unstructured":"Kracht M. 1999. Tools and Techniques in Modal Logic. Number 142 in Studies in Logic. Elsevier Amsterdam The Netherlands.]] Kracht M. 1999. Tools and Techniques in Modal Logic. Number 142 in Studies in Logic. Elsevier Amsterdam The Netherlands.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055562"},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Marx M."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083792"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543623"},{"key":"e_1_2_1_32_1","unstructured":"Neven F. 1999. Design and analysis of query languages for structured documents. Ph.D. thesis Limburgs Universitair Centrum Belgium.]] Neven F. 1999. Design and analysis of query languages for structured documents. Ph.D. thesis Limburgs Universitair Centrum Belgium.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335217"},{"key":"e_1_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"Xpath: Looking forward. In EDBT Workshops","author":"Olteanu D.","year":"2002"},{"key":"e_1_2_1_35_1","unstructured":"Palm A. 1997. Transforming tree constraints into formal grammars. Ph.D. dissertation. Universit\u00e4t Passau.]] Palm A. 1997. Transforming tree constraints into formal grammars. Ph.D. dissertation. Universit\u00e4t Passau.]]"},{"key":"e_1_2_1_36_1","volume-title":"Sixth Meeting on Mathematics of Language","author":"Palm A.","year":"1999"},{"key":"e_1_2_1_37_1","volume-title":"CONCUR","author":"Rabinovich A.","year":"2002"},{"key":"e_1_2_1_38_1","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Logics, and Infinite Games","author":"Reinhardt K."},{"key":"e_1_2_1_39_1","unstructured":"Rogers J. 1998. A Descriptive Approach to Language Theoretic Complexity. CSLI Press.]] Rogers J. 1998. A Descriptive Approach to Language Theoretic Complexity. CSLI Press.]]"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.1992.10510780"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/645729.667843"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Tarski A. and Givant S. 1987. A Formalization of Set Theory without Variables. Vol. 41. AMS Colloquium publications Providence R.I.]] Tarski A. and Givant S. 1987. A Formalization of Set Theory without Variables. Vol. 41. AMS Colloquium publications Providence R.I.]]","DOI":"10.1090\/coll\/041"},{"key":"e_1_2_1_43_1","volume-title":"Structures in Logic and Computer Science, A Selection of Essays in Honor of Andrzej Ehrenfeucht","author":"Thomas W."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Vardi M. 1997. Why is modal logic so robustly decidable? In DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31. American Math. Society 149--184.]] Vardi M. 1997. Why is modal logic so robustly decidable? In DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31. American Math. Society 149--184.]]","DOI":"10.1090\/dimacs\/031\/05"},{"key":"e_1_2_1_46_1","unstructured":"W3C XPath 1.0. XML path language (XPath): Version 1.0. http:\/\/www.w3.org\/TR\/xpath.html.]] W3C XPath 1.0. XML path language (XPath): Version 1.0. http:\/\/www.w3.org\/TR\/xpath.html.]]"},{"key":"e_1_2_1_47_1","unstructured":"W3C XQuery. XQuery 1.0: A query language for XML. http:\/\/www.w3.org\/TR\/\/xquery\/.]] W3C XQuery. XQuery 1.0: A query language for XML. http:\/\/www.w3.org\/TR\/\/xquery\/.]]"},{"key":"e_1_2_1_48_1","unstructured":"W3C XSLT. XSL transformations language (XSLT): Version 2.0. http:\/\/www.w3.org\/TR\/xslt20\/.]] W3C XSLT. XSL transformations language (XSLT): Version 2.0. http:\/\/www.w3.org\/TR\/xslt20\/.]]"},{"key":"e_1_2_1_49_1","unstructured":"Wadler P. 2000. Two semantics for XPath. Tech. rep. Bell Labs.]] Wadler P. 2000. Two semantics for XPath. Tech. rep. Bell Labs.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114247","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1114244.1114247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:37Z","timestamp":1750262917000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1145\/1114244.1114247"],"URL":"https:\/\/doi.org\/10.1145\/1114244.1114247","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]},"assertion":[{"value":"2005-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}