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.9261665e-05
Overall Rank: 2,912 | 79.77%
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,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05
6,831	Keep CALM and CRDT On	2023	VLDB	4.9077892e-05
7,338	Optimizing Recursive Queries with Program Synthesis	2022	SIGMOD	4.7531793e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
9,813	Optimizing Nested Recursive Queries	2024	SIGMOD	4.2742278e-05
10,003	Codd's Theorem for Databases over Semirings	2026	PODS	4.1905499e-05
10,296	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.1905499e-05
10,356	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1905499e-05
10,369	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1905499e-05
10,926	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1905499e-05
10,932	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1905499e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-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.00078516827
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
3,299	Greedy by Choice	1992	PODS	7.2519332e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,795	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9197522e-05
10,356	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1905499e-05
459	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00022684266
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
9,813	Optimizing Nested Recursive Queries	2024	SIGMOD	4.2742278e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
2,887	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9640219e-05
10,932	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1905499e-05
5,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05