Convergence of Datalog over (Pre-) Semirings

Summary: Defines least‑fixpoint Datalog semantics over ordered semirings and analyzes convergence of iterative evaluation beyond Boolean/monotone cases. Characterizes algebraic semiring properties that guarantee convergence and isolates a class of ordered semirings supporting semi‑naive evaluation for all Datalog programs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1835
Venue: PODS
Year: 2022
Pagerank: 7.933806e-05
Overall Rank: 2,907 | 79.78%
DOI: 10.1145/3517804.3524140

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05
6,833	Keep CALM and CRDT On	2023	VLDB	4.9125021e-05
7,342	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	4.7576316e-05
8,125	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5797807e-05
9,814	Optimizing Nested Recursive Queries	2024	SIGMOD	4.2783272e-05
10,004	Codd's Theorem for Databases over Semirings	2026	PODS	4.1945683e-05
10,284	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.1945683e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
10,357	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1945683e-05
10,922	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1945683e-05
10,929	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1945683e-05
10,997	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
31	Provenance Semirings	2007	PODS	0.0007857786
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
3,297	Greedy by Choice	1992	PODS	7.259032e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
452	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00022799064
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
9,814	Optimizing Nested Recursive Queries	2024	SIGMOD	4.2783272e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
10,929	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1945683e-05
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05