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.4342107e-05
Overall Rank: 3,316 | 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.00014680086
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,697	On Improving User Response Times in Tableau	2015	SIGMOD	8.1166572e-05
6,233	The Impact of Virtual Views on Containment	2010	VLDB	5.8412765e-05
12,063	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.9769913e-05
12,207	How Can Reasoners Simplify Database Querying (And Why Haven’t They Done It Yet)?	2018	PODS	4.9769913e-05
12,462	Does Query Evaluation Tractability Help Query Containment?	2014	PODS	4.9769913e-05
12,661	Determining Relevance of Accesses at Runtime	2011	PODS	4.9769913e-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.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
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012723733
1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
3,677	Overbound and Right-Linear Queries	1991	PODS	7.1041732e-05
4,714	Tools for Datalog Boundedness	1991	PODS	6.4537538e-05
6,206	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8479648e-05
8,142	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.390003e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,631	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,501	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
4	8,059	Polynomial-time program transformations in deductive databases	1990	PODS
5	9,276	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
6	6,804	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS
7	7,702	Hard problems for simple logic programs	1990	SIGMOD
8	5,417	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
9	6,746	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS