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.00015417107
Overall Rank: 907 | 93.70%
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
47	Data Integration: A Theoretical Perspective	2002	PODS	0.00069691761
82	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00054430106
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028572729
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
1,959	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.958725e-05
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
2,836	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0466188e-05
2,887	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.9640219e-05
3,174	Query Containment for Data Integration Systems	2000	PODS	7.444226e-05
3,414	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1172834e-05
5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	5.4741922e-05
6,293	Containment of Nested XML Queries	2004	VLDB	5.1206121e-05
7,884	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	4.6233362e-05
12,835	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.1905499e-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
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
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.7062591e-05
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,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
8,941	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.4229886e-05
5,996	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2365238e-05
10,932	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS	4.1905499e-05
2,912	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.9261665e-05
209	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00034147258
6,035	On Datalog vs. Polynomial Time	1991	PODS	5.2365238e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
3,414	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1172834e-05