{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:13:31Z","timestamp":1775873611559,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS 1907997, IIS 1954222"],"award-info":[{"award-number":["IIS 1907997, IIS 1954222"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P30930"],"award-info":[{"award-number":["P30930"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3524140","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"105-117","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Convergence of Datalog over (Pre-) Semirings"],"prefix":"10.1145","author":[{"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"relationalAI, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hung Q.","family":"Ngo","sequence":"additional","affiliation":[{"name":"relationalAI, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yisu Remy","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_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_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_3_2_2_4_1","volume-title":"Proc. ACM Program. Lang. 4, POPL","author":"Arntzenius M.","year":"2020","unstructured":"Arntzenius , M. , and Krishnaswami , N . Semina\"i ve evaluation for a higher-order functional language . Proc. ACM Program. Lang. 4, POPL ( 2020 ), 22: 1--22:28. Arntzenius, M., and Krishnaswami, N. Semina\"i ve evaluation for a higher-order functional language. Proc. ACM Program. Lang. 4, POPL (2020), 22:1--22:28."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/15.2.161"},{"key":"e_1_3_2_2_6_1","volume-title":"Graphs and networks","author":"Carr\u00e9 B.","year":"1979","unstructured":"Carr\u00e9 , B. Graphs and networks . The Clarendon Press, Oxford University Press , New York , 1979 . Oxford Applied Mathematics and Computing Science Series. Carr\u00e9, B. Graphs and networks. The Clarendon Press, Oxford University Press, New York, 1979. Oxford Applied Mathematics and Computing Science Series."},{"key":"e_1_3_2_2_7_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_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55844-6_142"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3"},{"key":"e_1_3_2_2_11_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 \"a del, 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\u00fc r Informatik, pp. 17:1--17:22. Dannert, K. M., Gr\"a del, 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\u00fc r Informatik, pp. 17:1--17:22."},{"key":"e_1_3_2_2_12_1","volume-title":"Introduction to lattices and order","author":"Davey B. A.","year":"1990","unstructured":"Davey , B. A. , and Priestley , H. A . Introduction to lattices and order . Cambridge University Press , Cambridge , 1990 . Davey, B. A., and Priestley, H. A. Introduction to lattices and order. Cambridge University Press, Cambridge, 1990."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009796922698"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857917"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(85)80005-4"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(91)90014-G"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90031-B"},{"key":"e_1_3_2_2_18_1","volume-title":"Algorithm 97: Shortest path. Commun. ACM 5, 6","author":"Floyd R. W.","year":"1962","unstructured":"Floyd , R. W. Algorithm 97: Shortest path. Commun. ACM 5, 6 ( 1962 ), 345. Floyd, R. W. Algorithm 97: Shortest path. Commun. ACM 5, 6 (1962), 345."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_3_2_2_20_1","first-page":"3","article-title":"The well-founded semantics for general logic programs","volume":"38","author":"Gelder A. V.","year":"1991","unstructured":"Gelder , A. V. , Ross , K. A. , and Schlipf , J. S . The well-founded semantics for general logic programs . J. ACM 38 , 3 ( 1991 ), 620--650. Gelder, A. V., Ross, K. A., and Schlipf, J. S. The well-founded semantics for general logic programs. J. ACM 38, 3 (1991), 620--650.","journal-title":"J. ACM"},{"key":"e_1_3_2_2_21_1","volume-title":"Alg\u00e8bre lin\u00e9aire et cheminement dans un graphe. Rev. Franccaise Automat. Informat. Recherche Op\u00e9rationnelle S\u00e9r. Verte 9, rm V-1","author":"Gondran M.","year":"1975","unstructured":"Gondran , M. Alg\u00e8bre lin\u00e9aire et cheminement dans un graphe. Rev. Franccaise Automat. Informat. Recherche Op\u00e9rationnelle S\u00e9r. Verte 9, rm V-1 ( 1975 ), 77--99. Gondran, M. Alg\u00e8bre lin\u00e9aire et cheminement dans un graphe. Rev. Franccaise Automat. Informat. Recherche Op\u00e9rationnelle S\u00e9r. Verte 9, rm V-1 (1975), 77--99."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90150-X"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1386688"},{"key":"e_1_3_2_2_24_1","volume-title":"5th International Conference, Prague, Czech Republic, January 11--13, 1995, Proceedings","volume":"893","author":"Greco S.","year":"1995","unstructured":"Greco , S. , Sacc\u00e0 , D. , and Zaniolo , C . DATALOG queries with stratified negation and choice: from P to d(^mboxp ). In Database Theory - ICDT'95 , 5th International Conference, Prague, Czech Republic, January 11--13, 1995, Proceedings ( 1995 ), G. Gottlob and M. Y. Vardi, Eds. , vol. 893 of Lecture Notes in Computer Science, Springer, pp. 82--96. Greco, S., Sacc\u00e0, D., and Zaniolo, C. DATALOG queries with stratified negation and choice: from P to d(^mboxp ). In Database Theory - ICDT'95, 5th International Conference, Prague, Czech Republic, January 11--13, 1995, Proceedings (1995), G. Gottlob and M. Y. Vardi, Eds., vol. 893 of Lecture Notes in Computer Science, Springer, pp. 82--96."},{"key":"e_1_3_2_2_25_1","first-page":"4","article-title":"Greedy algorithms","volume":"1","author":"Greco S.","year":"2001","unstructured":"Greco , S. , and Zaniolo , C . Greedy algorithms in Datalog. Theory Pract. Log. Program. 1 , 4 ( 2001 ), 381--407. Greco, S., and Zaniolo, C. Greedy algorithms in Datalog. Theory Pract. Log. Program. 1, 4 (2001), 381--407.","journal-title":"Datalog. Theory Pract. Log. Program."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137836"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_2_2_28_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_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782634"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321938"},{"key":"e_1_3_2_2_31_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_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-002"},{"key":"e_1_3_2_2_34_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_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.03.003"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18088-5_17"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90056-1"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exaa056"},{"key":"e_1_3_2_2_42_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_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/555142"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-6.4.663"},{"key":"e_1_3_2_2_46_1","unstructured":"Rockt\"aschel T. Einsum is all you need - Einstein summation in deep learning. https:\/\/rockt.github.io\/2018\/04\/30\/einsum.  Rockt\"aschel T. Einsum is all you need - Einstein summation in deep learning. https:\/\/rockt.github.io\/2018\/04\/30\/einsum."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9076-0_9"},{"key":"e_1_3_2_2_48_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_3_2_2_49_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_3_2_2_50_1","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Enumerative combinatorics","author":"Stanley R. P.","year":"2012","unstructured":"Stanley , R. P. Enumerative combinatorics . Volume 1 , second ed., vol. 49 of Cambridge Studies in Advanced Mathematics . Cambridge University Press , Cambridge , 2012 . Stanley, R. P. Enumerative combinatorics. Volume 1, second ed., vol. 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2012."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-141050-6.50006-4"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322272"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_3_2_2_55_1","first-page":"380","article-title":"Linear and combinatorial optimization in ordered algebraic structures","volume":"10","author":"Zimmermann U","year":"1981","unstructured":"Zimmermann , U . Linear and combinatorial optimization in ordered algebraic structures . Ann. Discrete Math. 10 ( 1981 ), viii+ 380 . Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+ 380.","journal-title":"Ann. Discrete Math."}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524140","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3524140","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3524140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:04Z","timestamp":1750182544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3524140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":55,"alternative-id":["10.1145\/3517804.3524140","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3524140","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}