On the convergence rate of Datalogo programs 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-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 sequence opeator until no further change is possible. This talk presents a recent result, which states that when the underlying semiring is p-stable, then the naive evaluation of any Datalogo program over the semiring converges in a polynomial number of steps. Prior to our this result, only exponential convergence rate was know. The talk is based on joint work with Ben Moseley, Kirk Pruhs, and Sungjin Im. We started working on this problem when all co-authors attended the Fall 2023 Simons program on Logic and Algorithms in AI and Databases. We are grateful for the support from the Simons.