Decidability and Undecidability Results for Boundedness of Linear Recursive Queries

Summary: Proves boundedness (recursion elimination) undecidable for linear Datalog even with a single binary intensional predicate, tightening Gaifman et al.'s 4-ary result. Shows that for linear programs with one recursive rule and a binary intensional predicate boundedness is decidable and NP-complete. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 845
Venue: PODS
Year: 1988
Pagerank: 9.84713e-05
Overall Rank: 1,991 | 86.16%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
1,688	Automata Theory for Database Theoreticians	1989	PODS	0.00010913301
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,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
7,884	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	4.6277758e-05
9,112	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3942347e-05
10,344	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1945683e-05
10,404	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.1945683e-05
11,441	Deciding Boundedness of Monadic Sirups	2021	PODS	4.1945683e-05
12,826	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	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,905	Detecting Redundant Tuples During Query Evaluation	1991	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
58	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00064826446
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
154	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00040645847
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
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
1,196	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00013403617
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
12,829	Universal Finiteness and Satisfiability	1994	PODS	4.1945683e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8602644e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0347472e-05
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05