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: 954
Venue: PODS
Year: 1992
Pagerank: 0.00012997935
Overall Rank: 953 | 93.47%
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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,630	On the Decidability of Query Containment under Constraints	1998	PODS	0.00010180625
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.2831426e-05
2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	8.0012184e-05
3,039	Query Containment for Data Integration Systems	2000	PODS	7.8265533e-05
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
5,361	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.2484907e-05
6,185	Containment of Nested XML Queries	2004	VLDB	5.9488248e-05
7,888	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.5217972e-05
13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	5.093636e-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
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05

Semantically Similar Papers

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