{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T15:17:38Z","timestamp":1787757458605,"version":"build-2784847793"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"National Science Foundation grants NSF IIS","award":["1907997"],"award-info":[{"award-number":["1907997"]}]},{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Recent work has demonstrated the catastrophic effects of poor cardinality estimates on query processing time. In particular, underestimating query cardinality can result in overly optimistic query plans which take orders of magnitude longer to complete than one generated with the true cardinality. Cardinality bounding avoids this pitfall by computing an upper bound on the query\u2019s output size using statistics about the database such as table sizes and degrees, i.e., value frequencies. In this article, we extend this line of work by proving a novel bound called the Degree Sequence Bound, which takes into account the full degree sequences and the max tuple multiplicity. This work focuses on the important class of Berge-Acyclic queries for which the Degree Sequence Bound is tight and provably improves on prior work. We further describe how to practically compute this bound using a functional approximation of the true degree sequences and prove that even this functional form improves upon previous bounds. Lastly, we outline the challenges of implementing this in a real system and some techniques for overcoming these challenges.<\/jats:p>\n                  <jats:p\/>","DOI":"10.1145\/3716378","type":"journal-article","created":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T07:18:55Z","timestamp":1748503135000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Degree Sequence Bounds"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2267-3276","authenticated-orcid":false,"given":"Kyle","family":"Deeds","sequence":"first","affiliation":[{"name":"CSE, University of Washington - Seattle Campus","place":["Seattle, US"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"Computer Science & Engineering, University of Washington","place":["Seattle, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6805-0325","authenticated-orcid":false,"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, University of Washington","place":["Seattle, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8492-5017","authenticated-orcid":false,"given":"Walter","family":"Cai","sequence":"additional","affiliation":[{"name":"CSE, University of Washington - Seattle Campus","place":["Seattle, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,25]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1465-6"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.8"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457242"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109590"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070380"},{"key":"e_1_3_3_12_2","unstructured":"Yuxing Han Ziniu Wu Peizhi Wu Rong Zhu Jingyi Yang Liang Wei Tan Kai Zeng Gao Cong Yanzhao Qin Andreas Pfadler Zhengping Qian Jingren Zhou Jiangneng Li and Bin Cui. 2021. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. arXiv:2109.05877. Retrieved from https:\/\/arxiv.org\/abs\/2109.05877 (2021)."},{"key":"e_1_3_3_13_2","volume-title":"Proceedings of the 11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11\u201315, 2021, Online Proceedings","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity done right for join ordering. In Proceedings of the 11th Conference on Innovative Data Systems Research, CIDR 2021, Virtual Event, January 11\u201315, 2021, Online Proceedings. www.cidrdb.org. Retrieved from http:\/\/cidrdb.org\/cidr2021\/papers\/cidr2021_paper01.pdf"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2306.14075"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476254"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452790"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452830"},{"key":"e_1_3_3_26_2","unstructured":"Ziniu Wu Amir Shaikhha Rong Zhu Kai Zeng Yuxing Han and Jingren Zhou. 2020. BayesCard: Revitilizing bayesian frameworks for cardinality estimation. arXiv:2012.14743. Retrieved from https:\/\/arxiv.org\/abs\/2012.14743 (2020)."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_3_3_28_2","unstructured":"Zongheng Yang Amog Kamsetty Sifei Luan Eric Liang Yan Duan Xi Chen and Ion Stoica. 2020. NeuroCard: One cardinality estimator for all tables. arXiv:2006.08109. Retrieved from https:\/\/arxiv.org\/abs\/2006.08109 (2020)."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:14:21Z","timestamp":1761401661000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,25]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3716378"],"URL":"https:\/\/doi.org\/10.1145\/3716378","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,25]]},"assertion":[{"value":"2024-05-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}