{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:03Z","timestamp":1755900603313,"version":"3.44.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>Query optimizers have a limited arsenal of techniques for optimizing nested queries. In this paper, we develop a new approach for query optimization based on quantifier elimination. Quantifier elimination is a well-established tool for proving the decidability of logical theories. Here, however, we show that it can be turned into an effective query optimization technique that may yield asymptotic improvements in query processing efficiency. In addition, the technique establishes a foundation for certain well-known but previously little-understood aggregation based techniques for optimizing nested queries.<\/jats:p>","DOI":"10.1145\/3651607","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Query Optimization by Quantifier Elimination"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9130-7205","authenticated-orcid":false,"given":"Christoph","family":"Koch","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, VD, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-7201","authenticated-orcid":false,"given":"Peter","family":"Lindner","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, VD, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley, Reading, MA, USA."},{"key":"e_1_2_1_2_1","volume-title":"VLDB '87: Proceedings of the 13th International Conference on Very Large Data Bases. Morgan Kaufmann","author":"Dayal Umeshwar","year":"1987","unstructured":"Umeshwar Dayal. 1987. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. In VLDB '87: Proceedings of the 13th International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, CA, USA, 197--208."},{"volume-title":"A Mathematical Introduction to Logic","author":"Enderton Herbert B.","key":"e_1_2_1_3_1","unstructured":"Herbert B. Enderton. 2001. A Mathematical Introduction to Logic second ed.). Elsevier, San Diego, CA, USA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38723"},{"volume-title":"Model Theory","author":"Hodges Wilfrid","key":"e_1_2_1_5_1","unstructured":"Wilfrid Hodges. 1993. Model Theory. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSA.2009.5404288"},{"key":"e_1_2_1_7_1","unstructured":"W. Kiessling. 1984. SQL-Like and QUEL-Like Correlation Queries with Aggregates Revisited. Technical Report UCB\/ERL M84\/75. EECS Department University of California Berkeley. http:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/1984\/377.html"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319745"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2003.1210049"},{"key":"e_1_2_1_10_1","volume-title":"Rinard","author":"Kuncak Viktor","year":"2004","unstructured":"Viktor Kuncak and Martin C. Rinard. 2004. The First-Order Theory of Sets with Cardinality Constraints is Decidable. MIT CSAIL Technical Report 958. Massachusetts Institute of Technology, Cambridge, MA, USA. arxiv: 0407045 [cs.LO]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-010-9183-0"},{"volume-title":"\u00dcber die Vollst\"andigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Comptes Rendus du I Congres de Mathematiciens des Pays Slaves","year":"1929","key":"e_1_2_1_12_1","unstructured":"Moj.zesz Presburger. 1929. \u00dcber die Vollst\"andigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Comptes Rendus du I Congres de Mathematiciens des Pays Slaves (1929), 92--101."},{"volume-title":"Database Management Systems","author":"Ramakrishnan Raghu","key":"e_1_2_1_13_1","unstructured":"Raghu Ramakrishnan and Johannes Gehrke. 2002. Database Management Systems third ed.). McGraw-Hill, New York, NY, USA."},{"volume-title":"ICDE '96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society, Washington, D.C., USA.","author":"Seshadri P.","key":"e_1_2_1_14_1","unstructured":"P. Seshadri, H. Pirahesh, and T. Leung. 1996. Complex query decorrelation. In ICDE '96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society, Washington, D.C., USA."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-017-0319-z"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-41-2-203-271"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:08Z","timestamp":1755898748000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651607"],"URL":"https:\/\/doi.org\/10.1145\/3651607","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}