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.1240395e-05
Overall Rank: 3,413 | 76.26%
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
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
2,311	On Improving User Response Times in Tableau	2015	SIGMOD	9.0539767e-05
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
7,275	The Impact of Virtual Views on Containment	2010	VLDB	4.7806552e-05
11,558	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.1945683e-05
11,967	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.1945683e-05
12,168	Determining Relevance of Accesses at Runtime	2011	PODS	4.1945683e-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
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
3,414	Overbound and Right-Linear Queries	1991	PODS	7.1232056e-05
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,339	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	9.005745e-05
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
10,929	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1945683e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05
6,794	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	4.9244886e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8602644e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222