{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:26Z","timestamp":1778807906650,"version":"3.51.4"},"reference-count":29,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>In this paper, we ask the following question: given a Boolean Conjunctive Query (CQ), what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. Notably, it is shown that any circuit F that computes a CQ over the tropical semiring must have size log |F| \u2265 (1-\u03b5) \u00b7 da-entw for any \u03b5 &gt;0, where da-entw is the degree-aware entropic width of the query. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas (i.e., circuits where each gate has outdegree one), and to bounds for non-Boolean CQs.<\/jats:p>","DOI":"10.1145\/3651588","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-20","source":"Crossref","is-referenced-by-count":2,"title":["Tight Bounds of Circuits for Sum-Product Queries"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7714-2195","authenticated-orcid":false,"given":"Austen Z.","family":"Fan","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6309-1702","authenticated-orcid":false,"given":"Paraschos","family":"Koutris","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7636-0831","authenticated-orcid":false,"given":"Hangdong","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ICALP (2) (Lecture Notes in Computer Science","author":"Amarilli Antoine","unstructured":"Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. 2015. Provenance Circuits for Trees and Treelike Instances. In ICALP (2) (Lecture Notes in Computer Science, Vol. 9135). Springer, 56--68."},{"key":"e_1_2_1_2_1","volume-title":"Uniform Reliability of Self-Join-Free Conjunctive Queries. Log. Methods Comput. Sci. 18, 4","author":"Amarilli Antoine","year":"2022","unstructured":"Antoine Amarilli and Benny Kimelfeld. 2022. Uniform Reliability of Self-Join-Free Conjunctive Queries. Log. Methods Comput. Sci. 18, 4 (2022)."},{"key":"e_1_2_1_3_1","volume-title":"Size Bounds and Query Plans for Relational Joins","author":"Atserias Albert","unstructured":"Albert Atserias, Martin Grohe, and D\u00e1niel Marx. 2008. Size Bounds and Query Plans for Relational Joins. In FOCS. IEEE Computer Society, 739--748."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90110-X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2013.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Karl Bringmann Nofar Carmeli and Stefan Mengel. 2022. Tight Fine-Grained Bounds for Direct Access on Join Queries. In PODS. ACM 427--436.","DOI":"10.1145\/3517804.3526234"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Nofar Carmeli and Luc Segoufin. 2023. Conjunctive Queries With Self-Joins Towards a Fine-Grained Enumeration Complexity Analysis. In PODS. ACM 277--289.","DOI":"10.1145\/3584372.3588667"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1013138"},{"key":"e_1_2_1_9_1","unstructured":"Daniel Deutch Tova Milo Sudeepa Roy and Val Tannen. 2014. Circuits for Datalog Provenance. In ICDT. OpenProceedings. org 201--212."},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Entropy Bounds for Conjunctive Queries with Functional Dependencies. In ICDT (LIPIcs, Vol. 68)","volume":"15","author":"Gogacz Tomasz","year":"2017","unstructured":"Tomasz Gogacz and Szymon Torunczyk. 2017. Entropy Bounds for Conjunctive Queries with Functional Dependencies. In ICDT (LIPIcs, Vol. 68). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1--15:17.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Todd J. Green Gregory Karvounarakis and Val Tannen. 2007. Provenance semirings. In PODS. ACM 31--40.","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9574-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In ICDT (LIPIcs, Vol. 255)","volume":"23","author":"El Khalfioui Aziz Amezian","year":"2023","unstructured":"Aziz Amezian El Khalfioui and Jef Wijsen. 2023. Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In ICDT (LIPIcs, Vol. 255). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 23:1--23:19.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472391"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo XuanLong Nguyen Dan Olteanu and Maximilian Schleich. 2018. In-Database Learning with Sparse Tensors. In PODS. ACM 325--340.","DOI":"10.1145\/3196959.3196960"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375661"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_19_1","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2023. What do Shannon-type Inequalities Submodular Width and Disjunctive Datalog have to do with one another? arXiv:1612.02503"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. In ICALP (LIPIcs, Vol. 229)","volume":"83","author":"Komarath Balagopal","year":"2022","unstructured":"Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. 2022. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. In ICALP (LIPIcs, Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 83:1--83:20.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.736561"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415572"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_26_1","volume-title":"Models of computation - exploring the power of computing","author":"Savage John E.","unstructured":"John E. Savage. 1998. Models of computation - exploring the power of computing. Addison-Wesley."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90083-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476356"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Yilei Wang and Ke Yi. 2022. Query Evaluation by Circuits. In PODS. ACM 67--78.","DOI":"10.1145\/3517804.3524142"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:36Z","timestamp":1755898776000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651588"],"URL":"https:\/\/doi.org\/10.1145\/3651588","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}