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.00012723733
Overall Rank: 979 | 93.43%
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.00055018384
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.0003753293
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023580688
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014680086
1,661	On the Decidability of Query Containment under Constraints	1998	PODS	9.9545204e-05
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5674072e-05
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS	8.0968483e-05
2,924	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8481787e-05
3,097	Query Containment for Data Integration Systems	2000	PODS	7.649698e-05
3,316	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4342107e-05
5,496	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1058078e-05
6,323	Containment of Nested XML Queries	2004	VLDB	5.8126093e-05
8,061	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.3953684e-05
13,316	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9769913e-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.00037991902
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026648806
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015373336
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5453747e-05
1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
3,677	Overbound and Right-Linear Queries	1991	PODS	7.1041732e-05
4,714	Tools for Datalog Boundedness	1991	PODS	6.4537538e-05

Semantically Similar Papers

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