{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T02:54:44Z","timestamp":1792032884119,"version":"4.4.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T00:00:00Z","timestamp":1183248000000},"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":["J. ACM"],"published-print":{"date-parts":[[2007,7]]},"abstract":"<jats:p>The well-definedness problem for a database query language consists of checking, given an expression and an input type, that the expression never yields a runtime error on any input adhering to the input type. In this article, we study the well-definedness problem for query languages on trees that are built from a finite set of partially defined base operations by adding variables, constants, conditionals, let bindings, and iteration. We identify properties of base operations that can make the problem undecidable and give restrictions that are sufficient to ensure decidability. As a direct result, we obtain a large fragment of XQuery for which well-definedness is decidable.<\/jats:p>","DOI":"10.1145\/1255443.1255447","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["On deciding well-definedness for query languages on trees"],"prefix":"10.1145","volume":"54","author":[{"given":"Stijn","family":"Vansummeren","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/772062.772065"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00032-1"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. ACM","author":"Bancilhon F.","unstructured":"Bancilhon , F. , and Khoshafian , S . 1986. A calculus for complex objects . In Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. ACM , New York, 53--60. 10.1145\/6012.15404 Bancilhon, F., and Khoshafian, S. 1986. A calculus for complex objects. In Proceedings of the 5th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. ACM, New York, 53--60. 10.1145\/6012.15404"},{"key":"e_1_2_1_5_1","unstructured":"Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2007. XQuery 1.0: An XML Query Language. W3C Recommendation.  Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2007. XQuery 1.0: An XML Query Language. W3C Recommendation."},{"key":"e_1_2_1_6_1","volume-title":"PODS '06: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM","author":"Boja\u0144czyk M.","unstructured":"Boja\u0144czyk , M. , David , C. , Muscholl , A. , Schwentick , T. , and Segoufin , L . 2006. Two-variable logic on data trees and xml reasoning . In PODS '06: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM , New York, 10--19. 10.1145\/1142351.1142354 Boja\u0144czyk, M., David, C., Muscholl, A., Schwentick, T., and Segoufin, L. 2006. Two-variable logic on data trees and xml reasoning. In PODS '06: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, New York, 10--19. 10.1145\/1142351.1142354"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050084"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00024-Q"},{"key":"e_1_2_1_9_1","unstructured":"Chamberlin D. Fankhauser P. Florescu D. Marchiori M. and Robie J. 2007. XML Query Use Cases. W3C Group Note.  Chamberlin D. Fankhauser P. Florescu D. Marchiori M. and Robie J. 2007. XML Query Use Cases. W3C Group Note."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 9th ACM SIGPLAN International Conference on Functional Programming (ICFP","author":"Colazzo D.","year":"2004","unstructured":"Colazzo , D. , Ghelli , G. , Manghi , P. , and Sartiani , C . 2004. Types for path correctness of XML queries . In Proceedings of the 9th ACM SIGPLAN International Conference on Functional Programming (ICFP 2004 ). ACM, New York, 126--137. 10.1145\/1016850.1016869 Colazzo, D., Ghelli, G., Manghi, P., and Sartiani, C. 2004. Types for path correctness of XML queries. In Proceedings of the 9th ACM SIGPLAN International Conference on Functional Programming (ICFP 2004). ACM, New York, 126--137. 10.1145\/1016850.1016869"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th VLDB Conference. Morgan-Kaufmann","author":"Dong X.","unstructured":"Dong , X. , Halevy , A. , and Tatarinov , I . 2004. Containment of nested XML queries . In Proceedings of the 30th VLDB Conference. Morgan-Kaufmann , San Francisco, CA, 132--143. Dong, X., Halevy, A., and Tatarinov, I. 2004. Containment of nested XML queries. In Proceedings of the 30th VLDB Conference. Morgan-Kaufmann, San Francisco, CA, 132--143."},{"key":"e_1_2_1_12_1","unstructured":"Draper D. Fankhauser P. Fern\u00e1ndez M. F. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2007. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation.  Draper D. Fankhauser P. Fern\u00e1ndez M. F. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2007. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation."},{"key":"e_1_2_1_13_1","unstructured":"Fern\u00e1ndez M. F. Malhotra A. Marsh J. Nagy M. and Walsh N. 2007. XQuery 1.0 and XPath 2.0 Data Model. W3C Recommendation.  Fern\u00e1ndez M. F. Malhotra A. Marsh J. Nagy M. and Walsh N. 2007. XQuery 1.0 and XPath 2.0 Data Model. W3C Recommendation."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming. ACM","author":"Frisch A.","unstructured":"Frisch , A. , Castagna , G. , and Benzaken , V . 2003. CDuce: An XML-centric general-purpose language . In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming. ACM , New York, 51--63. 10.1145\/944705.944711 Frisch, A., Castagna, G., and Benzaken, V. 2003. CDuce: An XML-centric general-purpose language. In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming. ACM, New York, 51--63. 10.1145\/944705.944711"},{"key":"e_1_2_1_15_1","volume-title":"Database Programming Languages---DBPL","author":"Hidders J.","year":"2003","unstructured":"Hidders , J. 2004. Satisfiability of XPath expressions . In Database Programming Languages---DBPL 2003 . Revised Papers. Lecture Notes in Computer Science, vol. 2921 . Springer-Verlag , New York, 21-- 36. Hidders, J. 2004. Satisfiability of XPath expressions. In Database Programming Languages---DBPL 2003. Revised Papers. Lecture Notes in Computer Science, vol. 2921. Springer-Verlag, New York, 21-- 36."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053468.1053470"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 30th VLDB Conference. Morgan-Kaufmann","author":"Lakshmanan L.","unstructured":"Lakshmanan , L. , Ramesh , G. , Wang , H. , and Zhao , Z. J . 2004. On testing satisfiability of tree pattern queries . In Proceedings of the 30th VLDB Conference. Morgan-Kaufmann , San Francisco, CA, 120--131. Lakshmanan, L., Ramesh, G., Wang, H., and Zhao, Z. J. 2004. On testing satisfiability of tree pattern queries. In Proceedings of the 30th VLDB Conference. Morgan-Kaufmann, San Francisco, CA, 120--131."},{"key":"e_1_2_1_20_1","unstructured":"Malhotra A. Melton J. and Walsh N. 2005. XQuery 1.0 and XPath 2.0 Functions and Operators. W3C Recommendation.  Malhotra A. Melton J. and Walsh N. 2005. XQuery 1.0 and XPath 2.0 Functions and Operators. W3C Recommendation."},{"key":"e_1_2_1_21_1","volume-title":"Lecture Notes in Computer Science","volume":"2572","author":"Martens W.","unstructured":"Martens , W. , and Neven , F . 2003. Typechecking top-down uniform unranked tree transducers. In Database Theory---ICDT 2003 . Lecture Notes in Computer Science , vol. 2572 . Springer-Verlag, New York, 64--78. Martens, W., and Neven, F. 2003. Typechecking top-down uniform unranked tree transducers. In Database Theory---ICDT 2003. Lecture Notes in Computer Science, vol. 2572. Springer-Verlag, New York, 64--78."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM","author":"Martens W.","unstructured":"Martens , W. , and Neven , F . 2004. Frontiers of tractability for typechecking simple XML transformations . In Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM , New York, 23--34. 10.1145\/1055558.1055563 Martens, W., and Neven, F. 2004. Frontiers of tractability for typechecking simple XML transformations. In Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, 23--34. 10.1145\/1055558.1055563"},{"key":"e_1_2_1_23_1","unstructured":"Matiyasevich Y. 1993. Hilbert's 10th Problem. MIT Press Cambridge MA.   Matiyasevich Y. 1993. Hilbert's 10th Problem. MIT Press Cambridge MA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM","author":"Milo T.","unstructured":"Milo , T. , Suciu , D. , and Vianu , V . 2000. Typechecking for XML transformers . In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM , New York, 11--22. 10.1145\/335168.335171 Milo, T., Suciu, D., and Vianu, V. 2000. Typechecking for XML transformers. In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, New York, 11--22. 10.1145\/335168.335171"},{"key":"e_1_2_1_26_1","volume-title":"Foundations for Programming Languages","author":"Mitchell J. C.","unstructured":"Mitchell , J. C. 1996. Foundations for Programming Languages . MIT Press , Cambridge, MA . Mitchell, J. C. 1996. Foundations for Programming Languages. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_27_1","volume-title":"Lecture Notes in Computer Science","volume":"2572","author":"Neven F.","unstructured":"Neven , F. , and Schwentick , T . 2003. XPath containment in the presence of disjunction, DTDs, and variables. In Database Theory---ICDT 2003 . Lecture Notes in Computer Science , vol. 2572 . Springer-Verlag, New York, 315--329. Neven, F., and Schwentick, T. 2003. XPath containment in the presence of disjunction, DTDs, and variables. In Database Theory---ICDT 2003. Lecture Notes in Computer Science, vol. 2572. Springer-Verlag, New York, 315--329."},{"key":"e_1_2_1_28_1","volume-title":"Types and Programming Languages","author":"Pierce B. C.","unstructured":"Pierce , B. C. 2002. Types and Programming Languages . MIT Press , Cambridge, MA . Pierce, B. C. 2002. Types and Programming Languages. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_29_1","volume-title":"8th International Workshop, DBPL","volume":"2397","author":"Suciu D.","year":"2001","unstructured":"Suciu , D. 2001 . Typechecking for semistructured data. In Database Programming Languages , 8th International Workshop, DBPL 2001, Revised Papers. Lecture Notes in Computer Science , vol. 2397 . Springer-Verlag, New York, 1--20. Suciu, D. 2001. Typechecking for semistructured data. In Database Programming Languages, 8th International Workshop, DBPL 2001, Revised Papers. Lecture Notes in Computer Science, vol. 2397. Springer-Verlag, New York, 1--20."},{"key":"e_1_2_1_30_1","first-page":"389","article-title":"Languages, Automata, and Logic. Handbook of Formal Languages, vol. 3. Springer-Verlag, New York","volume":"7","author":"Thomas W.","year":"1997","unstructured":"Thomas , W. 1997 . Languages, Automata, and Logic. Handbook of Formal Languages, vol. 3. Springer-Verlag, New York , Chapter 7 , 389 -- 456 . Thomas, W. 1997. Languages, Automata, and Logic. Handbook of Formal Languages, vol. 3. Springer-Verlag, New York, Chapter 7, 389--456.","journal-title":"Chapter"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.007"},{"key":"e_1_2_1_33_1","unstructured":"Yergeau F. Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2004. Extensible Markup Language (XML) 1.0 (Third Edition). W3C Recommendation.  Yergeau F. Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2004. Extensible Markup Language (XML) 1.0 (Third Edition). W3C Recommendation."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255443.1255447","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1255443.1255447","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255443.1255447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["10.1145\/1255443.1255447"],"URL":"https:\/\/doi.org\/10.1145\/1255443.1255447","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7]]},"assertion":[{"value":"2007-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}