On the Convergence Rate of Linear Datalogo over Stable Semirings

Datalogo 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. Datalogo is more powerful than Datalog in that its additional algebraic structure alows for supporting recursion with aggregation. At the same time, Datalogo retains the syntactic and semantic simplicity of Datalog: Datalogo 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~\cite{Khamis0PSW22} that, when the underlying semiring is $p$-stable, then the naïve evaluation of any Datalogo 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 {\bf linear} Datalogo programs, which is quite common in practice. In particular, the main result of this paper is that the convergence rate of linear Datalogo programs under any $p$-stable semiring is $O(pn^3)$. Next, we study the convergence rate in terms of the number of elements in the semiring for linear Datalogo programs. When $L$ is the number of elements, we show that the convergence rate is bounded by $O(pn \log L)$. This significantly improves the convergence rate for small $L$.