{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T20:38:59Z","timestamp":1791059939628,"version":"4.1.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>Queries formulated in a nested way are very common in XQuery. Unfortunately, their evaluation is usually very inefficient when done in a straightforward fashion. We present a framework for handling nested queries that is based on unnesting the queries after having translated them into an algebra. We not only present a collection of algebraic equivalences, but also supply a strategy on how to use them effectively. The full potential of the approach is demonstrated by applying our rewrites to actual queries and showing that performance gains of several orders of magnitude are possible.<\/jats:p>","DOI":"10.1145\/1166074.1166081","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"968-1013","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Strategies for query unnesting in XML databases"],"prefix":"10.1145","volume":"31","author":[{"given":"Norman","family":"May","sequence":"first","affiliation":[{"name":"University of Mannheim, Mannheim, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Helmer","sequence":"additional","affiliation":[{"name":"University of London, U.K."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guido","family":"Moerkotte","sequence":"additional","affiliation":[{"name":"University of Mannheim, Mannheim, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/361020.361215"},{"key":"e_1_2_2_2_1","volume-title":"Informal Proceedings of the International Workshop on the Web and Databases (WebDB '99)","author":"Beeri C.","unstructured":"Beeri , C. and Tzaban , Y . 1999. SAL: An algebra for semistructured data and XML . In Informal Proceedings of the International Workshop on the Web and Databases (WebDB '99) , Philadelphia, PA. 37--42. Beeri, C. and Tzaban, Y. 1999. SAL: An algebra for semistructured data and XML. In Informal Proceedings of the International Workshop on the Web and Databases (WebDB '99), Philadelphia, PA. 37--42."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066215"},{"key":"e_1_2_2_4_1","volume-title":"Informal Proceedings of the &lt;XIME-P\/&gt;","author":"Beyer K. S.","unstructured":"Beyer , K. S. , Cochrane , R. , Colby , L. S. , Ozcan , F. , and Pirahesh , H . 2004. XQuery for analytics: Challenges and requirements . In Informal Proceedings of the &lt;XIME-P\/&gt; . Paris, France, 3--8. Beyer, K. S., Cochrane, R., Colby, L. S., Ozcan, F., and Pirahesh, H. 2004. XQuery for analytics: Challenges and requirements. In Informal Proceedings of the &lt;XIME-P\/&gt;. Paris, France, 3--8."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223847"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of XML","author":"Borkar V.","year":"2004","unstructured":"Borkar , V. and Carey , M . 2004. Extending XQuery for grouping, duplicate elimination, and outer joins . In Proceedings of XML 2004 . Borkar, V. and Carey, M. 2004. Extending XQuery for grouping, duplicate elimination, and outer joins. In Proceedings of XML 2004."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.69"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66944"},{"key":"e_1_2_2_9_1","volume-title":"The MD-Join: An Operator for Complex OLAP. In ICDE '01: Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society Press","author":"Chatziantoniou D.","unstructured":"Chatziantoniou , D. , Akinde , M. , Johnson , T. , and Kim , S . 2001 . The MD-Join: An Operator for Complex OLAP. In ICDE '01: Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 524--533. Chatziantoniou, D., Akinde, M., Johnson, T., and Kim, S. 2001. The MD-Join: An Operator for Complex OLAP. In ICDE '01: Proceedings of the 17th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 524--533."},{"key":"e_1_2_2_10_1","unstructured":"Claussen J. Kemper A. and Kossmann D. 1998. Order-preserving hash joins: Sorting (almost) for free. Technical rep. MIP-9810. University of Passau Passau Germany.  Claussen J. Kemper A. and Kossmann D. 1998. Order-preserving hash joins: Sorting (almost) for free. Technical rep. MIP-9810. University of Passau Passau Germany."},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Claussen J.","unstructured":"Claussen , J. , Kemper , A. , Moerkotte , G. , and Peithner , K . 1997. Optimizing queries with universal quantification in object-oriented and object-relational databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 286--295. Claussen, J., Kemper, A., Moerkotte, G., and Peithner, K. 1997. Optimizing queries with universal quantification in object-oriented and object-relational databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 286--295."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130341"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Cluet S. and Moerkotte G. 1994. Nested queries in object bases. In DBLP-4: Proceedings of the Fourth International Workshop on Database Programming Languages---Object Models and Languages. Springer-Verlag London U.K 226--242.   Cluet S. and Moerkotte G. 1994. Nested queries in object bases. In DBLP-4: Proceedings of the Fourth International Workshop on Database Programming Languages---Object Models and Languages. Springer-Verlag London U.K 226--242.","DOI":"10.1007\/978-1-4471-3564-7_13"},{"key":"e_1_2_2_14_1","unstructured":"Cluet S. and Moerkotte G. 1995. Classification and optimization of nested queries in object bases. Technical rep. 95-6. RWTH Aachen Aachen Germany.  Cluet S. and Moerkotte G. 1995. Classification and optimization of nested queries in object bases. Technical rep. 95-6. RWTH Aachen Aachen Germany."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Cluet S. and Moerkotte G. 1996. Efficient evaluation of aggregates on bulk types. In DBLP-5: Proceedings of the Fifth International Workshop on Database Programming Languages. Springer-Verlag London U.K. 8.   Cluet S. and Moerkotte G. 1996. Efficient evaluation of aggregates on bulk types. In DBLP-5: Proceedings of the Fifth International Workshop on Database Programming Languages. Springer-Verlag London U.K. 8.","DOI":"10.14236\/ewic\/DBPL1995.6"},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Dayal U.","year":"1987","unstructured":"Dayal , U. 1987 . Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 197--208. Dayal, U. 1987. Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 197--208."},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Deutsch A.","unstructured":"Deutsch , A. , Papakonstantinou , Y. , and Xu , Y . 2004. The NEXT logical framework for XQuery . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA 94022, 168--179. Deutsch, A., Papakonstantinou, Y., and Xu, Y. 2004. The NEXT logical framework for XQuery. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA 94022, 168--179."},{"key":"e_1_2_2_18_1","unstructured":"Draper D. Frankhauser P. Fernandez M. Malhotra A. Rose K. Rys M. Simeon J. and Wadler P. 2005. XQuery 1.0 and XPath 2.0 formal semantics. W3C Candidate Recommendation. Nov. Go online to www.w3c.org.  Draper D. Frankhauser P. Fernandez M. Malhotra A. Rose K. Rys M. Simeon J. and Wadler P. 2005. XQuery 1.0 and XPath 2.0 formal semantics. W3C Candidate Recommendation. Nov. Go online to www.w3c.org."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276310"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584816"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/377674.377676"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013831700817"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Fushimi S.","unstructured":"Fushimi , S. , Kitsuregawa , M. , and Tanaka , H . 1986. An overview of the systems software of a parallel relational database machine: GRACE . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 209--219. Fushimi, S., Kitsuregawa, M., and Tanaka, H. 1986. An overview of the systems software of a parallel relational database machine: GRACE. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 209--219."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375748"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/244810.244812"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38723"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment","author":"Gottlob G.","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2002. Efficient algorithms for processing XPath queries . In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment , Hong Kong, China, 95--106. Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment, Hong Kong, China, 95--106."},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of the IEEE Conference on Data Engineering. IEEE Computer Society Press","author":"Gottlob G.","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2003. XPath query evaluation: Improving time and space efficiency . In Proceedings of the IEEE Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 379--390. Gottlob, G., Koch, C., and Pichler, R. 2003. XPath query evaluation: Improving time and space efficiency. In Proceedings of the IEEE Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 379--390."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of BTW","author":"Graefe G.","year":"2003","unstructured":"Graefe , G. 2003 . Executing nested queries . In Proceedings of BTW 2003. GI, Leipzig, Germany, 58--77. Graefe, G. 2003. Executing nested queries. In Proceedings of BTW 2003. GI, Leipzig, Germany, 58--77."},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 252--263","author":"Grust T.","unstructured":"Grust , T. , Sakr , S. , and Teubner , J . 2004. XQuery on SQL hosts . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 252--263 . Grust, T., Sakr, S., and Teubner, J. 2004. XQuery on SQL hosts. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 252--263."},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment","author":"Guravannavar R.","unstructured":"Guravannavar , R. , Ramanujam , H. S. , and Sudarshan , S . 2005. Optimizing nested queries with parameter sort orders . In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment , Trondheim, Norway, 481--492. Guravannavar, R., Ramanujam, H. S., and Sudarshan, S. 2005. Optimizing nested queries with parameter sort orders. In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment, Trondheim, Norway, 481--492."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356928"},{"key":"e_1_2_2_34_1","volume-title":"SQL-like and Quel-like correlation queries with aggregates revisited. ERL\/UCB Memo 84\/75","author":"Kiessling W.","unstructured":"Kiessling , W. 1984. SQL-like and Quel-like correlation queries with aggregates revisited. ERL\/UCB Memo 84\/75 , University of California , Berkeley, Berkeley, CA . Kiessling, W. 1984. SQL-like and Quel-like correlation queries with aggregates revisited. ERL\/UCB Memo 84\/75, University of California, Berkeley, Berkeley, CA."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319745"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322332"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066259"},{"key":"e_1_2_2_38_1","volume-title":"Informal Proceedings of the First International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '04","author":"May N.","unstructured":"May , N. , Helmer , S. , Kanne , C.-C. , and Moerkotte , G . 2004a. XQuery processing in Natix with an emphasis on join ordering . In Informal Proceedings of the First International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '04 , Paris, France). 49--54. May, N., Helmer, S., Kanne, C.-C., and Moerkotte, G. 2004a. XQuery processing in Natix with an emphasis on join ordering. In Informal Proceedings of the First International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '04, Paris, France). 49--54."},{"key":"e_1_2_2_39_1","unstructured":"May N. Helmer S. and Moerkotte G. 2003. Nested queries and quantifiers in an ordered context. Tech. rep. TR-03-002. Department for Mathematics and Computer Science University of Mannheim Mannheim Germany.  May N. Helmer S. and Moerkotte G. 2003. Nested queries and quantifiers in an ordered context. Tech. rep. TR-03-002. Department for Mathematics and Computer Science University of Mannheim Mannheim Germany."},{"key":"e_1_2_2_40_1","volume-title":"ICDE '04: Proceedings of the 20th International Conference on Data Engineering. IEEE Computer Society Press","author":"May N.","unstructured":"May , N. , Helmer , S. , and Moerkotte , G . 2004b. Nested queries and quantifiers in an ordered context . In ICDE '04: Proceedings of the 20th International Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 239. May, N., Helmer, S., and Moerkotte, G. 2004b. Nested queries and quantifiers in an ordered context. In ICDE '04: Proceedings of the 20th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 239."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11547273_12"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98734"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Muralikrishna M.","year":"1989","unstructured":"Muralikrishna , M. 1989 . Optimization and dataflow algorithms for nested tree queries . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 77--85. Muralikrishna, M. 1989. Optimization and dataflow algorithms for nested tree queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 77--85."},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Muralikrishna M.","year":"1992","unstructured":"Muralikrishna , M. 1992 . Improved unnesting algorithms for join aggregate SQL queries . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 91--102. Muralikrishna, M. 1992. Improved unnesting algorithms for join aggregate SQL queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 91--102."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99943"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment","author":"Pal S.","unstructured":"Pal , S. , Cseri , I. , Seeliger , O. , Rys , M. , Schaller , G. , Yu , W. , Tomic , D. , Baras , A. , Berg , B. , Churin , D. , and Kogan , E . 2005. XQuery implementation in a relational database system . In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment , Trondheim, Norway, 1175--1186. Pal, S., Cseri, I., Seeliger, O., Rys, M., Schaller, G., Yu, W., Tomic, D., Baras, A., Berg, B., Churin, D., and Kogan, E. 2005. XQuery implementation in a relational database system. In Proceedings of the International Conference on Very Large Data Bases (VLDB). VLDB Endowment, Trondheim, Norway, 1175--1186."},{"key":"e_1_2_2_47_1","volume-title":"Grouping in XML. In EDBT '02: Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers. Springer-Verlag","author":"Paparizos S.","unstructured":"Paparizos , S. , Al-Khalifa , S. , Jagadish , H. V. , Lakshmanan , L. V. S. , Nierman , A. , Srivastava , D. , and Wu , Y . 2002 . Grouping in XML. In EDBT '02: Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers. Springer-Verlag , London, U.K., 128--147. Paparizos, S., Al-Khalifa, S., Jagadish, H. V., Lakshmanan, L. V. S., Nierman, A., Srivastava, D., and Wu, Y. 2002. Grouping in XML. In EDBT '02: Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers. Springer-Verlag, London, U.K., 128--147."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130294"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98738"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233360"},{"key":"e_1_2_2_51_1","volume-title":"ICDE'96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society Press","author":"Seshadri P.","unstructured":"Seshadri , P. , Pirahesh , H. , and Leung , T. Y. C. 1996b. Complex query decorrelation . In ICDE'96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 450--458. Seshadri, P., Pirahesh, H., and Leung, T. Y. C. 1996b. Complex query decorrelation. In ICDE'96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 450--458."},{"key":"e_1_2_2_53_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann","author":"Steenhagen H. J.","year":"1994","unstructured":"Steenhagen , H. J. , Apers , P. M. G. , Blanken , H. M. , and de By , R. A. 1994 . From nested-loop to join queries in OODB . In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann , San Francisco, CA, 618--629. Steenhagen, H. J., Apers, P. M. G., Blanken, H. M., and de By, R. A. 1994. From nested-loop to join queries in OODB. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, San Francisco, CA, 618--629."},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society Press","author":"Yan W. P.","unstructured":"Yan , W. P. and Larson , P . -\u00c5. 1994. Performing group-by before join . In Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 89--100. Yan, W. P. and Larson, P.-\u00c5. 1994. Performing group-by before join. In Proceedings of the Tenth International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 89--100."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1166074.1166081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:20:54Z","timestamp":1672262454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1166074.1166081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1166074.1166081"],"URL":"https:\/\/doi.org\/10.1145\/1166074.1166081","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}