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.1905499e-05
Overall Rank: 10,932 | 24.03%
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.00078516827
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
2,912	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.9261665e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,776	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS	6.7716942e-05
459	CONVERGENCE OF SIDEWAYS QUERY EVALUATION (Extended Abstract)	1986	PODS	0.00022684266
3,414	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1172834e-05
6,035	On Datalog vs. Polynomial Time	1991	PODS	5.2365238e-05
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
10,356	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1905499e-05
5,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05
2,912	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.9261665e-05