On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs

Summary: Maps the complexity of equivalence between recursive and nonrecursive Datalog under realistic program restrictions, improving on prior triply-exponential worst-case bounds. Identifies natural classes where equivalence complexity falls across a spectrum from NP to co‑NEXPTIME. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1022
Venue: PODS
Year: 1994
Pagerank: 7.1172834e-05
Overall Rank: 3,414 | 76.28%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri
2. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
2,318	On Improving User Response Times in Tableau	2015	SIGMOD	9.04679e-05
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
7,272	The Impact of Virtual Views on Containment	2010	VLDB	4.7760673e-05
11,562	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.1905499e-05
11,975	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.1905499e-05
12,176	Determining Relevance of Accesses at Runtime	2011	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
209	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00034147258
541	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00020586706
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
2,048	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.689916e-05
3,417	Overbound and Right-Linear Queries	1991	PODS	7.116211e-05
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,343	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	8.9968717e-05
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
10,932	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1905499e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
8,941	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.4229886e-05
6,795	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9197522e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8555836e-05
5,183	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6368566e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107