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: 1021
Venue: PODS
Year: 1994
Pagerank: 7.60327e-05
Overall Rank: 3,245 | 77.74%
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
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,686	On Improving User Response Times in Tableau	2015	SIGMOD	8.25822e-05
6,098	The Impact of Virtual Views on Containment	2010	VLDB	5.9778168e-05
11,754	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	5.093636e-05
11,901	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	5.093636e-05
12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	5.093636e-05
12,364	Determining Relevance of Accesses at Runtime	2011	PODS	5.093636e-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
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
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
4,615	Tools for Datalog Boundedness	1991	PODS	6.6050069e-05
6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.9850223e-05
7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.5160399e-05

Semantically Similar Papers

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