{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:30Z","timestamp":1778807910190,"version":"3.51.4"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2025,4,28]]},"abstract":"<jats:p>Estimating the cardinality of the output of a query is a fundamental problem in database query processing.<\/jats:p>\n          <jats:p>In this article, we overview a recently published contribution that casts the cardinality estimation problem as linear optimization and computes guaranteed upper bounds on the cardinality of the output for any full conjunctive query. The objective of the linear program is to maximize the joint entropy of the query variables and its constraints are the Shannon information inequalities and new information inequalities involving \u2113p-norms of the degree sequences of the join attributes.<\/jats:p>\n          <jats:p>The bounds based on arbitrary norms can be asymptotically lower than those based on the \u21131 and \u2113\u221e norms, which capture the cardinalities and respectively the max-degrees of the input relations. They come with a matching query evaluation algorithm, are computable in exponential time in the query size, and are provably tight when each degree sequence is on one join attribute.<\/jats:p>","DOI":"10.1145\/3733620.3733623","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:20:07Z","timestamp":1745943607000},"page":"7-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation"],"prefix":"10.1145","volume":"54","author":[{"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"Relational AI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasileios","family":"Nakos","sequence":"additional","affiliation":[{"name":"National University of Athens"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_4_1","first-page":"1214","volume-title":"Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. Learned cardinality estimation: An in-depth study. In SIGMOD","author":"Kim Kyoungmin","year":"2022","unstructured":"Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. Learned cardinality estimation: An in-depth study. In SIGMOD, pages 1214--1227, 2022."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_10_1","volume-title":"CIDR","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. Simplicity done right for join ordering. In CIDR, 2021."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529339"},{"issue":"2","key":"e_1_2_1_12_1","first-page":"96","article-title":"Join size bounds using lp-norms on degree sequences","volume":"2","author":"Khamis Mahmoud Abo","year":"2024","unstructured":"Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu, and Dan Suciu. Join size bounds using lp-norms on degree sequences. Proc. ACM Manag. Data, 2(2):96, 2024.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_13_1","volume-title":"ACM Manag. Data (SIGMOD)","author":"Zhang Haozhe","year":"2025","unstructured":"Haozhe Zhang, Christoph Mayer, Mahmoud Abo Khamis, Dan Olteanu, and Dan Suciu. LpBound: Pessimistic cardinality estimation using lp-norms of degree sequences. To appear in Proc. ACM Manag. Data (SIGMOD), 2025."},{"key":"e_1_2_1_14_1","volume-title":"Efficient algorithms for cardinality estimation and conjunctive query evaluation with simple degree constraints","author":"Im S.","year":"2025","unstructured":"S. Im, B. Moseley, H. Ngo, and K. Pruhs. Efficient algorithms for cardinality estimation and conjunctive query evaluation with simple degree constraints, 2025. To appear in Proc. ACM Manag. Data (PODS)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3712311.3712313"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000082"},{"key":"e_1_2_1_17_1","volume-title":"Extensible query optimizers in practice. Found. Trends Databases, 14(3--4):186--402","author":"Ding Bailu","year":"2024","unstructured":"Bailu Ding, Vivek R. Narasayya, and Surajit Chaudhuri. Extensible query optimizers in practice. Found. Trends Databases, 14(3--4):186--402, 2024."},{"key":"e_1_2_1_18_1","volume-title":"Database management systems (3. ed.)","author":"Ramakrishnan Raghu","year":"2003","unstructured":"Raghu Ramakrishnan and Johannes Gehrke. Database management systems (3. ed.). McGraw-Hill, 2003."},{"key":"e_1_2_1_19_1","volume-title":"February","author":"Khamis Mahmoud Abo","year":"2024","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. PANDA: Query Evaluation in Submodular Width. arXiv e-prints, page arXiv:2402.02001, February 2024."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"issue":"1","key":"e_1_2_1_21_1","first-page":"1","article-title":"A new cardinality estimation framework for join queries","volume":"1","author":"Wu Ziniu","year":"2023","unstructured":"Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, and Samuel Madden. Factorjoin: A new cardinality estimation framework for join queries. Proc. ACM Manag. Data, 1(1):41:1--41:27, 2023.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_22_1","unstructured":"Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733623","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733620.3733623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:55Z","timestamp":1750298215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,4,28]]}},"alternative-id":["10.1145\/3733620.3733623"],"URL":"https:\/\/doi.org\/10.1145\/3733620.3733623","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"2025-04-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}