{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:38Z","timestamp":1750307198081,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA8750-09-C-0181"],"award-info":[{"award-number":["FA8750-09-C-0181"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141210041"],"award-info":[{"award-number":["N000141210041"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0915054, IIS-1115188, IIS-1064505, IIS-0911036, IIS-1054009"],"award-info":[{"award-number":["IIS-0915054, IIS-1115188, IIS-1064505, IIS-0911036, IIS-1054009"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>Cardinality estimation is the problem of estimating the number of tuples returned by a query; it is a fundamentally important task in data management, used in query optimization, progress estimation, and resource provisioning. We study cardinality estimation in a principled framework: given a set of statistical assertions about the number of tuples returned by a fixed set of queries, predict the number of tuples returned by a new query. We model this problem using the probability space, over possible worlds, that satisfies all provided statistical assertions and maximizes entropy. We call this the Entropy Maximization model for statistics (MaxEnt). In this article we develop the mathematical techniques needed to use the MaxEnt model for predicting the cardinality of conjunctive queries.<\/jats:p>","DOI":"10.1145\/2109196.2109202","type":"journal-article","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T13:18:22Z","timestamp":1331039902000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Understanding cardinality estimation using entropy maximization"],"prefix":"10.1145","volume":"37","author":[{"given":"Christopher","family":"R\u00e9","sequence":"first","affiliation":[{"name":"University of Wisconsin--Madison"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"key":"e_1_2_2_1_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_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_2_4_1","unstructured":"Alon N. and Spencer J. 1992. The Probabilistic Method. John Wiley.  Alon N. and Spencer J. 1992. The Probabilistic Method. John Wiley."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_14"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press.   Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497510"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258783"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_20"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242527"},{"volume-title":"Proceedings of the ICML Workshop on Statistical Relational Learning. 49--54","author":"Domingos P.","key":"e_1_2_2_12_1","unstructured":"Domingos , P. and Richardson , M . 2004. Markov logic: A unifying framework for statistical relational learning . In Proceedings of the ICML Workshop on Statistical Relational Learning. 49--54 . Domingos, P. and Richardson, M. 2004. Markov logic: A unifying framework for statistical relational learning. In Proceedings of the ICML Workshop on Statistical Relational Learning. 49--54."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115835"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790423"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1996.10477003"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03793-1_6"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687723"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453894"},{"volume-title":"Proceedings of the VLDB Conference. 373--384","author":"Markl V.","key":"e_1_2_2_22_1","unstructured":"Markl , V. , Megiddo , N. , Kutsch , M. , Tran , T. M. , Haas , P. J. , and Srivastava , U . 2005. Consistently estimating the selectivity of conjuncts of predicates . In Proceedings of the VLDB Conference. 373--384 . Markl, V., Megiddo, N., Kutsch, M., Tran, T. M., Haas, P. J., and Srivastava, U. 2005. Consistently estimating the selectivity of conjuncts of predicates. In Proceedings of the VLDB Conference. 373--384."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511813603"},{"volume-title":"Computational Complexity","author":"Papadimitriou C.","key":"e_1_2_2_25_1","unstructured":"Papadimitriou , C. 1994. Computational Complexity . Addison Wesley . Papadimitriou, C. 1994. Computational Complexity. Addison Wesley."},{"volume-title":"Proceedings of the VLDB Conference. 486--495","author":"Poosala V.","key":"e_1_2_2_26_1","unstructured":"Poosala , V. and Ioannidis , Y. E . 1997. Selectivity estimation without the attribute value independence assumption . In Proceedings of the VLDB Conference. 486--495 . Poosala, V. and Ioannidis, Y. E. 1997. Selectivity estimation without the attribute value independence assumption. In Proceedings of the VLDB Conference. 486--495."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807095"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_2_29_1","volume-title":"Principles of Mathematical Analysis","author":"Rudin W.","unstructured":"Rudin , W. 1976. Principles of Mathematical Analysis , 3 rd ed. McGraw-Hill Science\/Engineering\/Math . Rudin, W. 1976. Principles of Mathematical Analysis, 3rd ed. McGraw-Hill Science\/Engineering\/Math.","edition":"3"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386121"},{"volume-title":"Proceedings of the ICDE Conference. 596--605","author":"Sen P.","key":"e_1_2_2_31_1","unstructured":"Sen , P. and Deshpande , A . 2007. Representing and querying correlated tuples in probabilistic databases . In Proceedings of the ICDE Conference. 596--605 . Sen, P. and Deshpande, A. 2007. Representing and querying correlated tuples in probabilistic databases. In Proceedings of the ICDE Conference. 596--605."},{"key":"e_1_2_2_32_1","volume-title":"Mathematical Statistics","author":"Shao J.","unstructured":"Shao , J. 2003. Mathematical Statistics 2 nd ed. Springer . Shao, J. 2003. Mathematical Statistics 2nd ed. Springer.","edition":"2"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.84"},{"volume-title":"Proceedings of the VLDB Conference. 19--28","author":"Stillger M.","key":"e_1_2_2_34_1","unstructured":"Stillger , M. , Lohman , G. M. , Markl , V. , and Kandil , M . 2001. Leo\u2014db2's learning optimizer . In Proceedings of the VLDB Conference. 19--28 . Stillger, M., Lohman, G. M., Markl, V., and Kandil, M. 2001. Leo\u2014db2's learning optimizer. In Proceedings of the VLDB Conference. 19--28."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the CIDR Conference. 262--276","author":"Widom J.","year":"2005","unstructured":"Widom , J. 2005 . Trio: A system for integrated management of data, accuracy, and lineage . In Proceedings of the CIDR Conference. 262--276 . Widom, J. 2005. Trio: A system for integrated management of data, accuracy, and lineage. In Proceedings of the CIDR Conference. 262--276."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2109196.2109202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2109196.2109202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:09Z","timestamp":1750241169000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2109196.2109202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2109196.2109202"],"URL":"https:\/\/doi.org\/10.1145\/2109196.2109202","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}