{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:02Z","timestamp":1755906002219,"version":"3.44.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100017637","name":"Simons Institute for the Theory of Computing","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100017637","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["IIS-2147061, IIS-2008107"],"award-info":[{"award-number":["IIS-2147061, IIS-2008107"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            In this paper, we study circuits and formulas for provenance polynomials of Datalog programs. We ask the following question: given an absorptive semiring and a fact of a Datalog program, what is the optimal depth and size of a circuit\/formula that computes its provenance polynomial? We focus on absorptive semirings as these guarantee the existence of a polynomial-size circuit. Our main result is a dichotomy for several classes of Datalog programs on whether they admit a formula of polynomial size or not. We achieve this result by showing that for these Datalog programs the optimal circuit depth is either \u0398(log\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            ) or \u0398(log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            ), where\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            is the input size. We also show that for Datalog programs with the polynomial fringe property, we can always construct low-depth circuits of size O(log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic toggle=\"yes\">m<\/jats:italic>\n            ). Finally, we give characterizations of when Datalog programs are bounded over more general semirings.\n          <\/jats:p>","DOI":"10.1145\/3725230","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-22","source":"Crossref","is-referenced-by-count":0,"title":["Circuits and Formulas for Datalog over Semirings"],"prefix":"10.1145","volume":"3","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-0002-8300-7891","authenticated-orcid":false,"given":"Sudeepa","family":"Roy","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"volume-title":"Regular Path Queries with Constraints","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul and Victor Vianu. 1997. Regular Path Queries with Constraints. In PODS. ACM Press, 122--133."},{"key":"e_1_2_1_2_1","volume-title":"Description Logics (CEUR Workshop Proceedings","author":"Artale Alessandro","year":"2024","unstructured":"Alessandro Artale, Anton R. Gnatenko, Vladislav Ryzhikov, and Michael Zakharyaschev. 2024. On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators (Extended Abstract). In Description Logics (CEUR Workshop Proceedings, Vol. 3739). CEUR-WS.org."},{"key":"e_1_2_1_3_1","volume-title":"Vishnoi","author":"Barak Boaz","year":"2023","unstructured":"Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, and Nisheeth K. Vishnoi. 2023. On the works of Avi Wigderson. CoRR abs\/2307.09524 (2023)."},{"key":"e_1_2_1_4_1","volume-title":"On a routing problem. Quarterly of applied mathematics 16, 1","author":"Bellman Richard","year":"1958","unstructured":"Richard Bellman. 1958. On a routing problem. Quarterly of applied mathematics 16, 1 (1958), 87--90."},{"key":"e_1_2_1_5_1","first-page":"83","article-title":"The Complexity of Why-Provenance for Datalog Queries","volume":"2","author":"Calautti Marco","year":"2024","unstructured":"Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. 2024. The Complexity of Why-Provenance for Datalog Queries. Proc. ACM Manag. Data 2, 2 (2024), 83.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_6_1","volume-title":"Merlin","author":"Chandra Ashok K.","year":"1977","unstructured":"Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In STOC. ACM, 77--90."},{"key":"e_1_2_1_7_1","volume-title":"Vardi","author":"Cosmadakis Stavros S.","year":"1988","unstructured":"Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi. 1988. Decidable Optimization Problems for Database Logic Programs (Preliminary Report). In STOC. ACM, 477--490."},{"key":"e_1_2_1_8_1","volume-title":"Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic. CoRR abs\/1910.07910","author":"Dannert Katrin M.","year":"2019","unstructured":"Katrin M. Dannert, Erich Gr\u00e4del, Matthias Naaf, and Val Tannen. 2019. Generalized Absorptive Polynomials and Provenance Semantics for Fixed-Point Logic. CoRR abs\/1910.07910 (2019)."},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Semiring Provenance for Fixed-Point Logic. In CSL (LIPIcs, Vol. 183)","volume":"17","author":"Dannert Katrin M.","year":"2021","unstructured":"Katrin M. Dannert, Erich Gr\u00e4del, Matthias Naaf, and Val Tannen. 2021. Semiring Provenance for Fixed-Point Logic. In CSL (LIPIcs, Vol. 183). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1--17:22.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_10_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_11_1","volume-title":"Network flow theory","author":"Ford Lester Randolph","year":"1956","unstructured":"Lester Randolph Ford. 1956. Network flow theory. Rand Corporation Paper, Santa Monica, 1956 (1956)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174142"},{"key":"e_1_2_1_13_1","volume-title":"Provenance Analysis and Semiring Semantics for First-Order Logic. CoRR abs\/2412.07986","author":"Gr\u00e4del Erich","year":"2024","unstructured":"Erich Gr\u00e4del and Val Tannen. 2024. Provenance Analysis and Semiring Semantics for First-Order Logic. CoRR abs\/2412.07986 (2024)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_15_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_16_1","volume-title":"Vardi","author":"Hillebrand Gerd G.","year":"1991","unstructured":"Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, and Moshe Y. Vardi. 1991. Tools for Datalog Boundedness. In PODS. ACM Press, 1--12."},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"On the Convergence Rate of Linear Datalog over Stable Semirings. In ICDT (LIPIcs, Vol. 290)","volume":"11","author":"Im Sungjin","year":"2024","unstructured":"Sungjin Im, Benjamin Moseley, Hung Q. Ngo, and Kirk Pruhs. 2024. On the Convergence Rate of Linear Datalog over Stable Semirings. In ICDT (LIPIcs, Vol. 290). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 11:1--11:20.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9574-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_2_1_20_1","article-title":"Convergence of datalog over (Pre-) Semirings","volume":"71","author":"Khamis Mahmoud Abo","year":"2024","unstructured":"Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. 2024. Convergence of datalog over (Pre-) Semirings. J. ACM 71, 2 (2024), 8:1--8:55.","journal-title":"J. ACM"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556524"},{"key":"e_1_2_1_22_1","volume-title":"Logic, semirings, and fixed points. Ph. D. Dissertation. Dissertation","author":"Naaf Matthias Ferdinand","year":"2024","unstructured":"Matthias Ferdinand Naaf. 2024. Logic, semirings, and fixed points. Ph. D. Dissertation. Dissertation, RWTH Aachen University, 2024."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Jeffrey F. Naughton. 1986. Data Independent Recursion in Deductive Databases. In PODS. ACM 267--279.","DOI":"10.1145\/6012.15420"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/58562.59303"},{"key":"e_1_2_1_25_1","volume-title":"Naughton and Yehoshua Sagiv","author":"Jeffrey","year":"1987","unstructured":"Jeffrey F. Naughton and Yehoshua Sagiv. 1987. A Decidable Class of Bounded Recursions. In PODS. ACM, 227--236."},{"key":"e_1_2_1_26_1","unstructured":"Yann Ramusat Silviu Maniu and Pierre Senellart. 2021. Provenance-Based Algorithms for Rich Queries over Graph Databases. In EDBT. OpenProceedings.org 73--84."},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"Efficient provenance-aware querying of graph databases with datalog. In GRADES-NDA@SIGMOD","volume":"4","author":"Ramusat Yann","year":"2022","unstructured":"Yann Ramusat, Silviu Maniu, and Pierre Senellart. 2022. Efficient provenance-aware querying of graph databases with datalog. In GRADES-NDA@SIGMOD. ACM, 4:1--4:9.","journal-title":"ACM"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_2_1_29_1","first-page":"354","article-title":"Lower bounds on the monotone complexity of some Boolean function","volume":"31","author":"Razborov Alexander","year":"1985","unstructured":"Alexander Razborov. 1985. Lower bounds on the monotone complexity of some Boolean function. In Soviet Math. Dokl., Vol. 31. 354--357.","journal-title":"Soviet Math. Dokl."},{"volume-title":"Introduction to the theory of computation","author":"Sipser Michael","key":"e_1_2_1_30_1","unstructured":"Michael Sipser. 1997. Introduction to the theory of computation. PWS Publishing Company."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762108"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Moshe Y. Vardi. 1988. Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. In PODS. ACM 341--351.","DOI":"10.1145\/308386.308470"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90011-X"},{"volume-title":"Graph-Theoretic Methods in Database Theory","author":"Yannakakis Mihalis","key":"e_1_2_1_34_1","unstructured":"Mihalis Yannakakis. 1990. Graph-Theoretic Methods in Database Theory. In PODS. ACM Press, 230--242."},{"key":"e_1_2_1_35_1","first-page":"90","article-title":"Evaluating Datalog over Semirings","volume":"2","author":"Zhao Hangdong","year":"2024","unstructured":"Hangdong Zhao, Shaleen Deep, Paraschos Koutris, Sudeepa Roy, and Val Tannen. 2024. Evaluating Datalog over Semirings: A Grounding-based Approach. Proc. ACM Manag. Data 2, 2 (2024), 90.","journal-title":"A Grounding-based Approach. Proc. ACM Manag. Data"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:59Z","timestamp":1755904739000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725230"],"URL":"https:\/\/doi.org\/10.1145\/3725230","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}