{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:16:07Z","timestamp":1773886567772,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2023,6,7]]},"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 paper 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 generalize the semi-na\u00a8ve evaluation algorithm to compute their minimal fixpoints.<\/jats:p>","DOI":"10.1145\/3604437.3604454","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T22:22:01Z","timestamp":1686262921000},"page":"75-82","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Convergence of Datalog over (Pre-) Semirings"],"prefix":"10.1145","volume":"52","author":[{"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"relationalAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"relationalAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yisu","family":"Remy Wang","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"265","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Abadi M.","year":"2016","unstructured":"Abadi , M. , Barham , P. , Chen , J. , Chen , Z. , Davis , A. , Dean , J. , Devin , M. , Ghemawat , S. , Irving , G. , Isard , M. , Kudlur , M. , Levenberg , J. , Monga , R. , Moore , S. , Murray , D. G. , Steiner , B. , Tucker , P. A. , Vasudevan , V. , Warden , P. , Wicke , M. , Yu , Y. , and Zheng , X . Tensorflow: A system for large-scale machine learning . In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016 , Savannah, GA, USA, November 2--4 , 2016 (2016), K. Keeton and T. Roscoe, Eds., USENIX Association, pp. 265 -- 283 . Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., Kudlur, M., Levenberg, J., Monga, R., Moore, S., Murray, D. G., Steiner, B., Tucker, P. A., Vasudevan, V., Warden, P., Wicke, M., Yu, Y., and Zheng, X. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2--4, 2016 (2016), K. Keeton and T. Roscoe, Eds., USENIX Association, pp. 265--283."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_2_1_4_1","volume-title":"Graphs and networks","author":"Carr\u00b4e B.","year":"1979","unstructured":"Carr\u00b4e , B. Graphs and networks . The Clarendon Press, Oxford University Press , New York , 1979 . Oxford Applied Mathematics and Computing Science Series. Carr\u00b4e, B. Graphs and networks. The Clarendon Press, Oxford University Press, New York, 1979. Oxford Applied Mathematics and Computing Science Series."},{"key":"e_1_2_1_5_1","volume-title":"Introduction to algorithms","author":"Cormen T. H.","year":"2009","unstructured":"Cormen , T. H. , Leiserson , C. E. , Rivest , R. L. , and Stein , C . Introduction to algorithms , third ed. MIT Press , Cambridge, MA , 2009 . Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms, third ed. MIT Press, Cambridge, MA, 2009."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_7_1","volume-title":"29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference)","volume":"183","author":"Dannert K. M.","year":"2021","unstructured":"Dannert , K. M. , Gr\u00a8adel , E. , Naaf , M. , and Tannen , V . Semiring provenance for fixed-point logic . In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference) ( 2021 ), C. Baier and J. Goubault-Larrecq, Eds. , vol. 183 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, pp. 17:1--17:22. Dannert, K. M., Gr\u00a8adel, E., Naaf, M., and Tannen, V. Semiring provenance for fixed-point logic. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference) (2021), C. Baier and J. Goubault-Larrecq, Eds., vol. 183 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik, pp. 17:1--17:22."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796922698"},{"key":"e_1_2_1_9_1","volume-title":"Datalog Reloaded - First International Workshop, Datalog 2010","author":"Eisner J.","year":"2010","unstructured":"Eisner , J. , and Filardo , N. W . Dyna: Extending datalog for modern AI . In Datalog Reloaded - First International Workshop, Datalog 2010 , Oxford, UK, March 16--19 , 2010 . Revised Selected Papers (2010), Eisner, J., and Filardo, N. W. Dyna: Extending datalog for modern AI. In Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK, March 16--19, 2010. Revised Selected Papers (2010),"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(85)80005-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1386688"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_14_1","series-title":"Publ","first-page":"1","volume-title":"Idempotency (Bristol","author":"Gunawardena J.","year":"1994","unstructured":"Gunawardena , J. An introduction to idempotency . In Idempotency (Bristol , 1994 ), vol. 11 of Publ . Newton Inst. Cambridge Univ. Press , Cambridge, 1998, pp. 1 -- 49 . Gunawardena, J. An introduction to idempotency. In Idempotency (Bristol, 1994), vol. 11 of Publ. Newton Inst. Cambridge Univ. Press, Cambridge, 1998, pp. 1--49."},{"key":"e_1_2_1_15_1","volume-title":"Convergence of datalog over (pre-) semirings. CoRR abs\/2105.14435","author":"Khamis M. A.","year":"2021","unstructured":"Khamis , M. A. , Ngo , H. Q. , Pichler , R. , Suciu , D. , and Wang , Y. R . Convergence of datalog over (pre-) semirings. CoRR abs\/2105.14435 ( 2021 ). Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., and Wang, Y. R. Convergence of datalog over (pre-) semirings. CoRR abs\/2105.14435 (2021)."},{"key":"e_1_2_1_16_1","first-page":"105","volume-title":"PODS '22: International Conference on Management of Data","author":"Khamis M. A.","year":"2022","unstructured":"Khamis , M. A. , Ngo , H. Q. , Pichler , R. , Suciu , D. , and Wang , Y. R . Convergence of datalog over (pre-) semirings . In PODS '22: International Conference on Management of Data , Philadelphia, PA, USA, June 12 - 17 , 2022 (2022), L. Libkin and P. Barcel\u00b4o, Eds., ACM, pp. 105 -- 117 . Khamis, M. A., Ngo, H. Q., Pichler, R., Suciu, D., and Wang, Y. R. Convergence of datalog over (pre-) semirings. In PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (2022), L. Libkin and P. Barcel\u00b4o, Eds., ACM, pp. 105--117."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_18_1","volume-title":"Information algebras - generic structures for inference. Discrete mathematics and theoretical computer science","author":"Kohlas J.","year":"2003","unstructured":"Kohlas , J. Information algebras - generic structures for inference. Discrete mathematics and theoretical computer science . Springer , 2003 . Kohlas, J. Information algebras - generic structures for inference. Discrete mathematics and theoretical computer science. Springer, 2003."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.03.003"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90056-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exaa056"},{"key":"e_1_2_1_25_1","volume-title":"Recursive rules with aggregation: A simple unified semantics","author":"Liu Y. A.","year":"2020","unstructured":"Liu , Y. A. , and Stoller , S. D . Recursive rules with aggregation: A simple unified semantics , 2020 . Liu, Y. A., and Stoller, S. D. Recursive rules with aggregation: A simple unified semantics, 2020."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/555142"},{"key":"e_1_2_1_27_1","unstructured":"Rockt\u00a8aschel T. Einsum is all you need - Einstein summation in deep learning. https:\/\/rockt.github.io\/2018\/04\/30\/einsum.  Rockt\u00a8aschel T. Einsum is all you need - Einstein summation in deep learning. https:\/\/rockt.github.io\/2018\/04\/30\/einsum."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9076-0_9"},{"key":"e_1_2_1_29_1","volume-title":"Toward a mathematical semantics for computer languages","author":"Scott D.","year":"1971","unstructured":"Scott , D. , and Strachey , C . Toward a mathematical semantics for computer languages , 1971 . Scott, D., and Strachey, C. Toward a mathematical semantics for computer languages, 1971."},{"key":"e_1_2_1_30_1","first-page":"169","volume-title":"UAI '88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence","author":"Shenoy P. P.","year":"1988","unstructured":"Shenoy , P. P. , and Shafer , G . Axioms for probability and belief-function proagation . In UAI '88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence , Minneapolis, MN, USA, July 10--12 , 1988 (1988), R. D. Shachter, T. S. Levitt, L. N. Kanal, and J. F. Lemmer, Eds., North-Holland, pp. 169 -- 198 . Shenoy, P. P., and Shafer, G. Axioms for probability and belief-function proagation. In UAI '88: Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence, Minneapolis, MN, USA, July 10--12, 1988 (1988), R. D. Shachter, T. S. Levitt, L. N. Kanal, and J. F. Lemmer, Eds., North-Holland, pp. 169--198."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_32_1","first-page":"79","volume-title":"SIGMOD '22: International Conference on Management of Data","author":"Wang Y. R.","year":"2022","unstructured":"Wang , Y. R. , Khamis , M. A. , Ngo , H. Q. , Pichler , R. , and Suciu , D . Optimizing recursive queries with progam synthesis . In SIGMOD '22: International Conference on Management of Data , Philadelphia, PA, USA, June 12 - 17 , 2022 (2022), Z. Ives, A. Bonifati, and A. E. Abbadi, Eds., ACM, pp. 79 -- 93 . Wang, Y. R., Khamis, M. A., Ngo, H. Q., Pichler, R., and Suciu, D. Optimizing recursive queries with progam synthesis. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 (2022), Z. Ives, A. Bonifati, and A. E. Abbadi, Eds., ACM, pp. 79--93."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_2_1_34_1","series-title":"CEUR Workshop Proceedings","volume-title":"Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25","author":"Zaniolo C.","year":"2018","unstructured":"Zaniolo , C. , Yang , M. , Interlandi , M. , Das , A. , Shkapsky , A. , and Condie , T . Declarative bigdata algorithms via aggregates and relational database dependencies . In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25 , 2018 (2018), D. Olteanu and B. Poblete, Eds ., vol. 2100 of CEUR Workshop Proceedings , CEUR-WS. org. Zaniolo, C., Yang, M., Interlandi, M., Das, A., Shkapsky, A., and Condie, T. Declarative bigdata algorithms via aggregates and relational database dependencies. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25, 2018 (2018), D. Olteanu and B. Poblete, Eds., vol. 2100 of CEUR Workshop Proceedings, CEUR-WS.org."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604454","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604437.3604454","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604437.3604454"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6,7]]}},"alternative-id":["10.1145\/3604437.3604454"],"URL":"https:\/\/doi.org\/10.1145\/3604437.3604454","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"2023-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}