2026-07-25T10:18:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19793 2024-03-14T08:42:35Z ddc:004 open_access

On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings Im, Sungjin Moseley, Benjamin Ngo, Hung Pruhs, Kirk Datalog convergence rate semiring Datalog^∘ is an extension of Datalog, where instead of a program being a collection of union of conjunctive queries over the standard Boolean semiring, a program may now be a collection of sum-product queries over an arbitrary commutative partially ordered pre-semiring. Datalog^∘ is more powerful than Datalog in that its additional algebraic structure alows for supporting recursion with aggregation. At the same time, Datalog^∘ retains the syntactic and semantic simplicity of Datalog: Datalog^∘ has declarative least fixpoint semantics. The least fixpoint can be found via the naïve evaluation algorithm that repeatedly applies the immediate consequence operator until no further change is possible. It was shown in [Mahmoud Abo Khamis et al., 2022] that, when the underlying semiring is p-stable, then the naïve evaluation of any Datalog^∘ program over the semiring converges in a finite number of steps. However, the upper bounds on the rate of convergence were exponential in the number n of ground IDB atoms. This paper establishes polynomial upper bounds on the convergence rate of the naïve algorithm on linear Datalog^∘ programs, which is quite common in practice. In particular, the main result of this paper is that the convergence rate of linear Datalog^∘ programs under any p-stable semiring is O(pn³). Furthermore, we show a matching lower bound by constructing a p-stable semiring and a linear Datalog^∘ program that requires Ω(pn³) iterations for the naïve iteration algorithm to converge. Next, we study the convergence rate in terms of the number of elements in the semiring for linear Datalog^∘ programs. When L is the number of elements, the convergence rate is bounded by O(pn log L). This significantly improves the convergence rate for small L. We show a nearly matching lower bound as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sungjin Im and Benjamin Moseley and Hung Ngo and Kirk Pruhs 2024 Is Part Of LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2024.11 urn:nbn:de:0030-drops-197939 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode