{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T00:05:49Z","timestamp":1755993949386,"version":"3.44.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Carnegie Bosch Junior Faculty Chair"},{"name":"Google Research Award"},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["2423106, 2121745, 1844939, 2121744, 1845146, 1907673, 2209654"],"award-info":[{"award-number":["2423106, 2121745, 1844939, 2121744, 1845146, 1907673, 2209654"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-22-1-2701, N00014-22-1-2702"],"award-info":[{"award-number":["N00014-22-1-2701, N00014-22-1-2702"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Infor Research Award"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            Datalog\n            <jats:sup>o<\/jats:sup>\n            is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike Datalog, the natural iterative evaluation of some Datalogo programs over some semirings may not converge. It is known that the commutative semirings for which the iterative evaluation of Datalogo programs is guaranteed to converge are exactly those semirings that are stable. Previously, the best known upper bound on the number of iterations until convergence over p-stable semirings is \u2211i=1 ^n (p+2)\n            <jats:sup>i<\/jats:sup>\n            = \u0398(p\n            <jats:sup>n<\/jats:sup>\n            ) steps, where n is (essentially) the output size. We establish that, in fact, the natural iterative evaluation of a Datalogo program over a p-stable semiring converges within a polynomial number of iterations. In particular our upper bound is O(\u03c3 p n\n            <jats:sup>2<\/jats:sup>\n            ( n\n            <jats:sup>2<\/jats:sup>\n            lg \u039b + lg \u03c3)) where \u03c3 is the number of elements in the semiring present in either the input databases or the Datalogo program, and \u03bb is the maximum number of terms in any product in the Datalogo program.\n          <\/jats:p>","DOI":"10.1145\/3695839","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-19","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5994-7280","authenticated-orcid":false,"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8162-017X","authenticated-orcid":false,"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, 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":"RelationalAI, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-1753","authenticated-orcid":false,"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"University of Pittsburgh, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"volume-title":"Foundations of Databases","author":"Abiteboul Serge","key":"e_1_2_1_1_1","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. http:\/\/webdam.inria.fr\/Alice\/"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"volume-title":"Introduction to algorithms","author":"Cormen Thomas H.","key":"e_1_2_1_3_1","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to algorithms third ed.). MIT Press, Cambridge, MA. xx1292 pages."},{"key":"e_1_2_1_4_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857917"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_7_1","series-title":"Operations Research\/Computer Science Interfaces Series","volume-title":"dioids and semirings","author":"Gondran Michel","unstructured":"Michel Gondran and Michel Minoux. 2008. Graphs, dioids and semirings. Operations Research\/Computer Science Interfaces Series, Vol. 41. Springer, New York. xx383 pages. New models and algorithms."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1999.782634"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2024.11"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524140"},{"volume-title":"Automata and Computability","author":"Kozen Dexter C.","key":"e_1_2_1_12_1","unstructured":"Dexter C. Kozen. 1997. Automata and Computability. Springer-Verlag, Berlin, Heidelberg."},{"volume-title":"Handbook of formal languages","author":"Kuich Werner","key":"e_1_2_1_13_1","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--677."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304--3975(77)90056--1"},{"key":"e_1_2_1_15_1","volume-title":"Papadimitriou","author":"Lewis Harry R.","year":"1998","unstructured":"Harry R. Lewis and Christos H. Papadimitriou. 1998. Elements of the theory of computation, 2nd Edition. Prentice Hall.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2--6.4.663"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02253318"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--7091--9076-0_9"},{"volume-title":"Enumerative combinatorics","author":"Stanley Richard P.","key":"e_1_2_1_20_1","unstructured":"Richard P. Stanley. 2012. Enumerative combinatorics. Volume 1 second ed.). Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge. xiv626 pages."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322272"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695839","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:35:41Z","timestamp":1755916541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695839"],"URL":"https:\/\/doi.org\/10.1145\/3695839","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}