On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs

Summary: Maps the complexity of equivalence between recursive and nonrecursive Datalog under realistic program restrictions, improving on prior triply-exponential worst-case bounds. Identifies natural classes where equivalence complexity falls across a spectrum from NP to co‑NEXPTIME. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h7c78608b99d6861f
Venue: PODS
Year: 1994
Pagerank: 7.4376793e-05
Overall Rank: 3,315 | 77.72%
DOI: 10.1145/182591.182604

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Hewlett Packard Enterprise)
2. Moshe Y. Vardi (IBM; Rice University)

BibTeX Citation

@inproceedings{chaudhuri_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs}},
        url = {https://dl.acm.org/doi/10.1145/182591.182604},
        doi = {10.1145/182591.182604},
        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 = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,700	On Improving User Response Times in Tableau	2015	SIGMOD	8.1188166e-05
6,230	The Impact of Virtual Views on Containment	2010	VLDB	5.844043e-05
12,057	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.9793485e-05
12,201	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9793485e-05
12,456	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.9793485e-05
12,655	Determining Relevance of Accesses at Runtime	2011	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
3,675	Overbound and Right-Linear Queries	1991	PODS	7.1075276e-05
4,712	Tools for Datalog Boundedness	1991	PODS	6.4568103e-05
6,201	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8507344e-05
8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.3925529e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,629	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS
2	1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
3	11,495	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
4	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
5	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
6	6,798	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
7	7,696	Hard problems for simple logic programs	1990	SIGMOD
8	5,413	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
9	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS