{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T17:23:42Z","timestamp":1778520222473,"version":"3.51.4"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T00:00:00Z","timestamp":1712707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF IIS","award":["1907997"],"award-info":[{"award-number":["1907997"]}]},{"name":"NSF IIS","award":["1954222"],"award-info":[{"award-number":["1954222"]}]},{"name":"Austrian Science Fund","award":["P30930"],"award-info":[{"award-number":["P30930"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["10.47379\/ICT2201"],"award-info":[{"award-number":["10.47379\/ICT2201"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this article, we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-na\u00efve evaluation algorithm on any datalog program.<\/jats:p>","DOI":"10.1145\/3643027","type":"journal-article","created":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T12:15:22Z","timestamp":1706616922000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Convergence of datalog over (Pre-) Semirings"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"Relational AI, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3498-4744","authenticated-orcid":false,"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"Relational AI, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1760-122X","authenticated-orcid":false,"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6887-9395","authenticated-orcid":false,"given":"Yisu Remy","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,10]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"265","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916)","author":"Abadi Mart\u00edn","year":"2016","unstructured":"Mart\u00edn Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016. TensorFlow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916), Kimberly Keeton and Timothy Roscoe (Eds.). USENIX Association, 265\u2013283. Retrieved from: https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/abadi"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524140"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371090"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/15.2.161"},{"key":"e_1_3_3_9_2","article-title":"Ehrenfeucht-Fra\u00efss\u00e9 games in semiring semantics","volume":"2308","author":"Brinke Sophie","year":"2023","unstructured":"Sophie Brinke, Erich Gr\u00e4del, and Lovro Mrkonjic. 2023. Ehrenfeucht-Fra\u00efss\u00e9 games in semiring semantics. CoRR abs\/2308.04910 (2023).","journal-title":"CoRR"},{"key":"e_1_3_3_10_2","volume-title":"Graphs and Networks","author":"Carr\u00e9 Bernard","year":"1979","unstructured":"Bernard Carr\u00e9. 1979. Graphs and Networks. The Clarendon Press, Oxford University Press, New York. xvi+277 pages."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068418000418"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55844-6_142"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CSL.2021.17"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.306.32"},{"key":"e_1_3_3_18_2","volume-title":"Introduction to Lattices and Order","author":"Davey Brian A.","year":"1990","unstructured":"Brian A. Davey and Hilary A. Priestley. 1990. Introduction to Lattices and Order. Cambridge University Press, Cambridge. Retrieved from: http:\/\/www.worldcat.org\/search?qt=worldcat_org_all&q=0521367662"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796922698"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857917"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(85)80005-4"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90014-G"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/1.6.797"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90031-B"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00330-3"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/113413.113427"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1064"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73722"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116838"},{"key":"e_1_3_3_31_2","first-page":"1070","volume-title":"5th International Conference and Symposium on Logic Programming","author":"Gelfond Michael","year":"1988","unstructured":"Michael Gelfond and Vladimir Lifschitz. 1988. The stable model semantics for logic programming. In 5th International Conference and Symposium on Logic Programming, Robert A. Kowalski and Kenneth A. Bowen (Eds.). MIT Press, 1070\u20131080."},{"issue":"1","key":"e_1_3_3_32_2","first-page":"77","article-title":"Alg\u00e8bre lin\u00e9aire et cheminement dans un graphe","volume":"9","author":"Gondran M.","year":"1975","unstructured":"M. Gondran. 1975. Alg\u00e8bre lin\u00e9aire et cheminement dans un graphe. Rev. Fran\u00e7aise Automat. Informat. Recherche Op\u00e9rationnelle S\u00e9r. Verte 9, V-1 (1975), 77\u201399.","journal-title":"Rev. Fran\u00e7aise Automat. Informat. Recherche Op\u00e9rationnelle S\u00e9r. Verte"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90150-X"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/1386688"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58907-4_8"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068401001090"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137836"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1561\/1900000017"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324959"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662508.003"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782634"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_23"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321938"},{"key":"e_1_3_3_45_2","first-page":"3","volume-title":"Automata Studies","author":"Kleene S. C.","year":"1956","unstructured":"S. C. Kleene. 1956. Representation of events in nerve nets and finite automata. In Automata Studies. Princeton University Press, Princeton, NJ, 3\u201341."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_3_3_47_2","volume-title":"Information Algebras\u2014Generic Structures for Inference","author":"Kohlas J\u00fcrg","year":"2003","unstructured":"J\u00fcrg Kohlas. 2003. Information Algebras\u2014Generic Structures for Inference. Springer."},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.03.003"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90059-B"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90033-2"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18088-5_17"},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/978-3-642-59136-5_9","volume-title":"Handbook of Formal Languages, Vol. 1","author":"Kuich Werner","year":"1997","unstructured":"Werner Kuich. 1997. Semirings and formal power series: their relevance to formal languages and automata. In Handbook of Formal Languages, Vol. 1. Springer, Berlin, 609\u2013677."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90056-1"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exaa056"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1093\/LOGCOM\/EXAC072"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.11.008"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3191315.3191317"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0299-1"},{"key":"e_1_3_3_63_2","unstructured":"Frank McSherry. 2022. Recursion in Materialize. Retrieved from https:\/\/github.com\/frankmcsherry\/blog\/blob\/master\/posts\/2022-12-25.md"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03811-6"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/b98874"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-6.4.663"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73723"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.5555\/107720.107722"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837659"},{"key":"e_1_3_3_71_2","unstructured":"Tim Rockt\u00e4schel. 2018. Einsum is all you need\u2014Einstein summation in deep learning. Retrieved from https:\/\/rockt.github.io\/2018\/04\/30\/einsum"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137852"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9076-0_9"},{"key":"e_1_3_3_74_2","first-page":"169","volume-title":"4th Annual Conference on Uncertainty in Artificial Intelligence (UAI\u201988)","author":"Shenoy Prakash P.","year":"1988","unstructured":"Prakash P. Shenoy and Glenn Shafer. 1988. Axioms for probability and belief-function proagation. In 4th Annual Conference on Uncertainty in Artificial Intelligence (UAI\u201988), Ross D. Shachter, Tod S. Levitt, Laveen N. Kanal, and John F. Lemmer (Eds.). North-Holland, 169\u2013198."},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915229"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113340"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589"},{"key":"e_1_3_3_78_2","doi-asserted-by":"crossref","unstructured":"Robert E. Tarjan. 1976. Graph theory and Gaussian elimination. J. R. Bunch and D. J. Rose (Eds.). 3\u201322.","DOI":"10.1016\/B978-0-12-141050-6.50006-4"},{"key":"e_1_3_3_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322272"},{"key":"e_1_3_3_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_3_3_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458815"},{"key":"e_1_3_3_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517827"},{"key":"e_1_3_3_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_3_3_84_2","article-title":"Monotonic properties of completed aggregates in recursive queries","volume":"1910","author":"Zaniolo Carlo","year":"2019","unstructured":"Carlo Zaniolo, Ariyam Das, Jiaqi Gu, Youfu Li, Mingda Li, and Jin Wang. 2019. Monotonic properties of completed aggregates in recursive queries. CoRR abs\/1910.08888 (2019).","journal-title":"CoRR"},{"issue":"2","key":"e_1_3_3_85_2","first-page":"3","article-title":"Developing big-data Application as queries: An aggregate-based approach","volume":"44","author":"Zaniolo Carlo","year":"2021","unstructured":"Carlo Zaniolo, Ariyam Das, Jiaqi Gu, Youfu Li, Mingda Li, and Jin Wang. 2021. Developing big-data Application as queries: An aggregate-based approach. IEEE Data Eng. Bull. 44, 2 (2021), 3\u201313. Retrieved from: http:\/\/sites.computer.org\/debull\/A21june\/p3.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_3_86_2","volume-title":"10th Alberto Mendelzon International Workshop on Foundations of Data Management (CEUR Workshop Proceedings","volume":"1644","author":"Zaniolo Carlo","year":"2016","unstructured":"Carlo Zaniolo, Mohan Yang, Ariyam Das, and Matteo Interlandi. 2016. The magic of pushing extrema into recursion: Simple, powerful Datalog programs. In 10th Alberto Mendelzon International Workshop on Foundations of Data Management (CEUR Workshop Proceedings, Vol. 1644), Reinhard Pichler and Altigran Soares da Silva (Eds.). CEUR-WS.org. Retrieved from: http:\/\/ceur-ws.org\/Vol-1644\/paper16.pdf"},{"key":"e_1_3_3_87_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000436"},{"key":"e_1_3_3_88_2","unstructured":"Carlo Zaniolo Mohan Yang Matteo Interlandi Ariyam Das Alexander Shkapsky and Tyson Condie. 2018. Declarative BigData algorithms via aggregates and relational database dependencies. In 12th Alberto Mendelzon International Workshop on Foundations of Data Management(CEUR Workshop Proceedings Vol. 2100) Dan Olteanu and Barbara Poblete (Eds.). CEUR-WS.org. Retrieved from: http:\/\/ceur-ws.org\/Vol-2100\/paper2.pdf"},{"key":"e_1_3_3_89_2","first-page":"viii+380","article-title":"Linear and combinatorial optimization in ordered algebraic structures","volume":"10","author":"Zimmermann U.","year":"1981","unstructured":"U. Zimmermann. 1981. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380.","journal-title":"Ann. Discrete Math."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3643027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:21Z","timestamp":1750264281000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3643027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,10]]},"references-count":88,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3643027"],"URL":"https:\/\/doi.org\/10.1145\/3643027","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,10]]},"assertion":[{"value":"2023-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}