# Convergence of Datalog over (Pre-) Semirings

arXiv: https://arxiv.org/abs/2105.14435 · HTML: https://mlsanity.com/paper/2105.14435/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2021.

## Built on by (most cited first, 5 of 5)

- [Scallop: A Language for Neurosymbolic Programming](https://mlsanity.com/paper/2304.04812/) (2023)
- [The Complexity of Why-Provenance for Datalog Queries](https://mlsanity.com/paper/2303.12773/) (2023)
- [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026)
- [A Unifying Framework for Semiring-Based Constraint Logic Programming With Negation (full version)](https://mlsanity.com/paper/2507.16067/) (2025)
- [PAGR: Proof-Carrying Algebraic-Geometric Retrieval: A Quiver-, Provenance-, and Sheaf-Theoretic Framework for Grounded LLM Retrieval](https://mlsanity.com/paper/2609.06127/) (2026)

## Abstract (arXiv)

Recursive queries have been traditionally studied in the framework of datalog, a language that restricts recursion to monotone queries over sets, which is guaranteed to converge in polynomial time in the size of the input. But modern big data systems require recursive computations beyond the Boolean space. In this paper we study the convergence of datalog when it is interpreted over an arbitrary semiring. We consider an ordered semiring, define the semantics of a datalog program as a least fixpoint in this semiring, and study the number of steps required to reach that fixpoint, if ever. We identify algebraic properties of the semiring that correspond to certain convergence properties of datalog programs. Finally, we describe a class of ordered semirings on which one can use the semi-na"ive evaluation algorithm on any datalog program.