A Decidable Class of Bounded Recursions

Summary: Proposes a simple syntactic criterion yielding a decidable class of bounded recursions that subsumes previously known decidable linear cases. Proves that under this criterion Naughton’s condition is necessary and sufficient, enabling safe replacement of recursive queries by nonrecursive equivalents for optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 797
Venue: PODS
Year: 1987
Pagerank: 9.2910236e-05
Overall Rank: 2,206 | 84.66%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jeffrey F. Naughton
2. Yehoshua Sagiv

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,189	Independence of Logic Database Queries and Updates	1990	PODS	0.00013441514
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05
3,855	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6953401e-05
4,136	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4188795e-05
4,370	Distributed Processing Of Logic Programs	1988	SIGMOD	6.2486359e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
9,738	The Space-Efficient Core of Vadalog	2019	PODS	4.2936538e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
12,829	Universal Finiteness and Satisfiability	1994	PODS	4.1945683e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
200	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00035012858
617	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00019090876
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
673	One-Sided Recursions	1987	PODS	0.00018348841
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
1,991	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.84713e-05