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.837483e-05
Overall Rank: 1,997 | 86.13%
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
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
1,687	Automata Theory for Database Theoreticians	1989	PODS	0.0001090256
3,860	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6864693e-05
4,138	Safety of Datalog Queries over Infinite Databases	1989	PODS	6.4127061e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
7,884	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	4.6233362e-05
9,110	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3900304e-05
10,356	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.1905499e-05
10,415	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.1905499e-05
11,444	Deciding Boundedness of Monadic Sirups	2021	PODS	4.1905499e-05
12,835	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.1905499e-05
12,838	Universal Finiteness and Satisfiability	1994	PODS	4.1905499e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
12,915	Detecting Redundant Tuples During Query Evaluation	1991	PODS	4.1905499e-05
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-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.00064817807
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
154	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00040747653
541	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00020586706
612	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.0001915957
1,167	On Computing Restricted Projections of Representative Instances	1985	PODS	0.0001354084
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
1,489	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011687823
5,183	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6368566e-05
12,838	Universal Finiteness and Satisfiability	1994	PODS	4.1905499e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8555836e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.8389293e-05
7,594	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.6983854e-05
4,631	Tools for Datalog Boundedness	1991	PODS	6.0289457e-05
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05