Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs

Summary: Datalog◦ extends Datalog with aggregation/recursion over commutative semirings; iterative evaluation converges on p-stable semirings. New bound: O(σ p n^2(n^2 log λ + log σ)) iterations; improves prior Θ(p^n) to polynomial time. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1957
Venue: PODS
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,929 | 23.97%
DOI: 10.1145/3695839

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,767	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS	6.7783966e-05
452	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00022799064
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
6,031	On Datalog vs. Polynomial Time	1991	PODS	5.2415551e-05
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05