On the Equivalence of Recursive and Nonrecursive Datalog Programs

Summary: Decision problem: determine whether a recursive Datalog program is equivalent to a given nonrecursive Datalog program. Main result: establish tight triply-exponential time upper and lower bounds for this equivalence problem. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 955
Venue: PODS
Year: 1992
Pagerank: 0.00015428222
Overall Rank: 909 | 93.68%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri
2. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
48	Data Integration: A Theoretical Perspective	2002	PODS	0.00069720859
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054402763
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028596715
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
1,952	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.9677831e-05
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
2,830	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.054172e-05
2,877	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9715251e-05
3,168	Query Containment for Data Integration Systems	2000	PODS	7.4508875e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
5,471	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	5.4888202e-05
6,294	Containment of Nested XML Queries	2004	VLDB	5.1255418e-05
7,884	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	4.6277758e-05
12,826	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
2,036	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.714898e-05
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,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05
10,929	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1945683e-05
2,907	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.933806e-05
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
6,031	On Datalog vs. Polynomial Time	1991	PODS	5.2415551e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05