{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T17:17:34Z","timestamp":1792948654501,"version":"4.5.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>\n            This article studies the complexity of evaluating functional query languages for complex values such as monad algebra and the recursion-free fragment of XQuery. We show that monad algebra, with equality restricted to atomic values, is complete for the class TA[2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )] of problems solvable in linear exponential time with a linear number of alternations if the query is assumed to be part of the input. The monotone fragment of monad algebra with atomic value equality but without negation is NEXPTIME-complete. For monad algebra with deep value equality, that is, equality of complex values, we establish TA[2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )] lower and exponential-space upper bounds. We also study a fragment of XQuery, Core XQuery, that seems to incorporate all the features of a query language on complex values that are traditionally deemed essential. A close connection between monad algebra on lists and Core XQuery (with \u201cchild\u201d as the only axis) is exhibited. The two languages are shown expressively equivalent up to representation issues. We show that Core XQuery is just as hard as monad algebra with respect to query and combined complexity. As Core XQuery is NEXPTIME-hard, the best-known techniques for processing such problems require exponential amounts of working memory and doubly exponential time in the worst case. We present a property of queries---the lack of a certain form of composition---that virtually all real-world XQueries have and that allows for query evaluation in PSPACE and thus singly exponential time. Still, we are able to show for an important special case---Core XQuery with equality testing restricted to atomic values---that the composition-free language is just as expressive as the language with composition. Thus, under widely-held complexity-theoretic assumptions, the language with composition is an exponentially more succinct version of the composition-free language.\n          <\/jats:p>","DOI":"10.1145\/1189769.1189771","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"1215-1256","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["On the complexity of nonrecursive XQuery and functional query languages on complex values"],"prefix":"10.1145","volume":"31","author":[{"given":"Christoph","family":"Koch","sequence":"first","affiliation":[{"name":"Saarland University, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01354881"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 5th International Conference on Database Theory (ICDT). 439--454","author":"Abiteboul S."},{"key":"e_1_2_2_3_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_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_47"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90037-7"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00024-Q"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645682.664439"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335218"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of FSTTCS","volume":"1974","author":"Fernandez M.","year":"2000"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of XML Database Symposium (XSYM'04)","author":"Fernandez M. F."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of Very Large Data Bases. 997--1008","author":"Florescu D."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059520"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/203244"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/235767.235770"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0042"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1058"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logical Design. 179--190","author":"Hartmanis J."},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of XML Database Symposium (XSYM). 5--20","author":"Hidders J."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66940"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90022-O"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588133"},{"key":"e_1_2_2_29_1","first-page":"67","article-title":"A catalog of complexity classes. In Handbook of Theoretical Computer Science, Vol. 1. J. van Leeuwen, Ed. Elsevier Science Publishers B.V","volume":"2","author":"Johnson D. S.","year":"1990","journal-title":"Chapter"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065179"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of WebDB","author":"Koch C.","year":"2005"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Koch C."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90219-J"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/155271.155274"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1523"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases","author":"Lud\u00e4scher B."},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 213--224","author":"Marian A."},{"key":"e_1_2_2_38_1","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley.]]  Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley.]]"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/308386.308402"},{"key":"e_1_2_2_40_1","unstructured":"Stockmeyer L. J. 1974. The complexity of decision problems in automata theory. Ph.D. thesis Department of Electrical Engineering MIT Cambridge MA.]]  Stockmeyer L. J. 1974. The complexity of decision problems in automata theory. Ph.D. thesis Department of Electrical Engineering MIT Cambridge MA.]]"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1525"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of the 4th International Conference on Database Theory (ICDT). 140--154","author":"Tannen V."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275515"},{"key":"e_1_2_2_45_1","unstructured":"Voronkov A. 2004. Personal communication.]]  Voronkov A. 2004. Personal communication.]]"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0037"},{"key":"e_1_2_2_47_1","unstructured":"World Wide Web Consortium. 2005. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Candidate Recommendation (Nov.). http:\/\/www.w3.org\/TR\/xquery-semantics\/.]]  World Wide Web Consortium. 2005. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Candidate Recommendation (Nov.). http:\/\/www.w3.org\/TR\/xquery-semantics\/.]]"},{"key":"e_1_2_2_48_1","unstructured":"XQueryUseCases 2005. XML query use cases. W3C Working Draft (Sept.). http:\/\/www.w3.org\/TR\/xquery-use-cases\/.]]  XQueryUseCases 2005. XML query use cases. W3C Working Draft (Sept.). http:\/\/www.w3.org\/TR\/xquery-use-cases\/.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1189769.1189771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:10:07Z","timestamp":1672261807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1189769.1189771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1145\/1189769.1189771"],"URL":"https:\/\/doi.org\/10.1145\/1189769.1189771","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"assertion":[{"value":"2006-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}