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: h6b8ddcaf6a685707
Venue: PODS
Year: 1992
Pagerank: 0.00012729663
Overall Rank: 979 | 93.42%
DOI: 10.1145/137097.137109

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Stanford University)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{chaudhuri_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{On the Equivalence of Recursive and Nonrecursive Datalog Programs}},
        url = {https://dl.acm.org/doi/10.1145/137097.137109},
        doi = {10.1145/137097.137109},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chaudhuri, Surajit and Vardi, Moshe Y.},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
1,660	On the Decidability of Query Containment under Constraints	1998	PODS	9.9592164e-05
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.1006747e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,095	Query Containment for Data Integration Systems	2000	PODS	7.6532922e-05
3,315	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4376793e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05
6,319	Containment of Nested XML Queries	2004	VLDB	5.8153622e-05
8,055	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.3979237e-05
13,310	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9793485e-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
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015380574
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5498891e-05
1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
2,024	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.166955e-05
3,675	Overbound and Right-Linear Queries	1991	PODS	7.1075276e-05
4,712	Tools for Datalog Boundedness	1991	PODS	6.4568103e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,696	Hard problems for simple logic programs	1990	SIGMOD
2	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
3	6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
4	11,495	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
5	2,630	Convergence of Datalog over (Pre-) Semirings	2022	PODS
6	317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS
7	6,370	On Datalog vs. Polynomial Time	1991	PODS
8	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	3,315	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS