{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:39Z","timestamp":1778807859765,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/G055114\/1"],"award-info":[{"award-number":["EP\/G055114\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            This article provides new worst-case bounds for the size and treewith of the result\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) of a conjunctive query\n            <jats:italic>Q<\/jats:italic>\n            applied to a database\n            <jats:italic>D<\/jats:italic>\n            . We derive bounds for the result size |\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            )| in terms of structural properties of\n            <jats:italic>Q<\/jats:italic>\n            , both in the absence and in the presence of keys and functional dependencies. These bounds are based on a novel \u201ccoloring\u201d of the query variables that associates a\n            <jats:italic>coloring number C<\/jats:italic>\n            (\n            <jats:italic>Q<\/jats:italic>\n            ) to each query\n            <jats:italic>Q<\/jats:italic>\n            . Intuitively, each color used represents some possible entropy of that variable. Using this coloring number, we derive tight bounds for the size of\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) in case (i) no functional dependencies or keys are specified, and (ii) simple functional dependencies (keys) are given. These results generalize recent size-bounds for join queries obtained by Atserias et al. [2008]. In the case of arbitrary (compound) functional dependencies, we use tools from information theory to provide lower and upper bounds, establishing a close connection between size bounds and a basic question in information theory. Our new coloring scheme also allows us to precisely characterize (both in the absence of keys and with simple keys) the treewidth-preserving queries---the queries for which the treewidth of the output relation is bounded by a function of the treewidth of the input database. Finally, we give some results on the computational complexity of determining the size bounds, and of deciding whether the treewidth is preserved.\n          <\/jats:p>","DOI":"10.1145\/2220357.2220363","type":"journal-article","created":{"date-parts":[[2012,7,10]],"date-time":"2012-07-10T16:40:44Z","timestamp":1341938444000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["Size and Treewidth Bounds for Conjunctive Queries"],"prefix":"10.1145","volume":"59","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephanie Tien","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Valiant","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Valiant","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_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_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1121995.1122010"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896862"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT).","author":"Fagin R.","unstructured":"Fagin , R. , Kolaitis , P. G. , Miller , R. J. , and Popa , L . 2003. Data exchange: Semantics and query answering . In Proceedings of the 9th International Conference on Database Theory (ICDT). Fagin, R., Kolaitis, P. G., Miller, R. J., and Popa, L. 2003. Data exchange: Semantics and query answering. In Proceedings of the 9th International Conference on Database Theory (ICDT)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.03.005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559804"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence. AAAI Press, 1626--1631","author":"Gottlob G.","unstructured":"Gottlob , G. , Pichler , R. , and Wei , F . 2007. Efficient datalog abduction through bounded treewidth . In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. AAAI Press, 1626--1631 . Gottlob, G., Pichler, R., and Wei, F. 2007. Efficient datalog abduction through bounded treewidth. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. AAAI Press, 1626--1631."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/356924.356928"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2007.4557201"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.887090"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 5th International Workshop on Statistical and Scientific Data Management.","author":"Olken F.","unstructured":"Olken , F. and Rotem , D . 1990. Random sampling from database files: A survey . In Proceedings of the 5th International Workshop on Statistical and Scientific Data Management. Olken, F. and Rotem, D. 1990. Random sampling from database files: A survey. In Proceedings of the 5th International Workshop on Statistical and Scientific Data Management."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Special Problems on Communication and Computation Conference.","author":"Pippenger N.","year":"1986","unstructured":"Pippenger , N. 1986 . What are the laws of information theory? In Proceedings of the Special Problems on Communication and Computation Conference. Pippenger, N. 1986. What are the laws of information theory? In Proceedings of the Special Problems on Communication and Computation Conference."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 4th International Conference on Extending Database Technology - Advances in Database Technology (EDBT\u201994)","author":"Swami A. N.","unstructured":"Swami , A. N. and Schiefer , K. B . 1994. On the estimation of join result sizes . In Proceedings of the 4th International Conference on Extending Database Technology - Advances in Database Technology (EDBT\u201994) . Swami, A. N. and Schiefer, K. B. 1994. On the estimation of join result sizes. In Proceedings of the 4th International Conference on Extending Database Technology - Advances in Database Technology (EDBT\u201994)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_2_1_34_1","unstructured":"Valiant G. and Valiant P. 2009. Size bounds for conjunctive queries with general functional dependencies. http:\/\/arxiv.org\/abs\/0909.2030. Valiant G. and Valiant P. 2009. Size bounds for conjunctive queries with general functional dependencies. http:\/\/arxiv.org\/abs\/0909.2030."},{"key":"e_1_2_1_35_1","volume-title":"Information Theory and Network Coding","author":"Yeung R. W.","unstructured":"Yeung , R. W. 2008. Information Theory and Network Coding . Springer Publishing Company, Inc orporated. Yeung, R. W. 2008. Information Theory and Network Coding. Springer Publishing Company, Incorporated."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.641561"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.681320"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220357.2220363","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2220357.2220363","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:46Z","timestamp":1750276846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220357.2220363"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2220357.2220363"],"URL":"https:\/\/doi.org\/10.1145\/2220357.2220363","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}