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: he35f2f380446f43c
Venue: PODS
Year: 1988
Pagerank: 9.5498891e-05
Overall Rank: 1,830 | 87.70%
DOI: 10.1145/308386.308470

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{vardi_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Decidability and Undecidability Results for Boundedness of Linear Recursive Queries}},
        url = {https://dl.acm.org/doi/10.1145/308386.308470},
        doi = {10.1145/308386.308470},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012729663
1,908	Automata Theory for Database Theoreticians	1989	PODS	9.3940283e-05
4,420	On Distributed Processibility of Datalog Queries by Decomposing Databases	1989	SIGMOD	6.6068305e-05
4,712	Tools for Datalog Boundedness	1991	PODS	6.4568103e-05
6,201	Safety of Datalog Queries over Infinite Databases	1989	PODS	5.8507344e-05
8,055	Finding Nonrecursive Envelopes for Datalog Predicates	1993	PODS	5.3979237e-05
8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS	5.3925529e-05
9,347	Optimizing Recursive Queries in SQL	2005	SIGMOD	5.1900828e-05
11,083	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.9793485e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05
11,946	Deciding Boundedness of Monadic Sirups	2021	PODS	4.9793485e-05
13,310	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	4.9793485e-05
13,313	Universal Finiteness and Satisfiability	1994	PODS	4.9793485e-05
13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.9793485e-05
13,390	Detecting Redundant Tuples During Query Evaluation	1991	PODS	4.9793485e-05
13,406	Semigroup techniques in recursive query optimization	1990	PODS	4.9793485e-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
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
368	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00019864474
633	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015380574
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012936921
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011560838
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010599099
2,062	A Decidable Class of Bounded Recursions	1987	PODS	9.0974416e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,201	Data Independent Recursion in Deductive Databases	1986	PODS
2	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
3	5,413	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
4	13,313	Universal Finiteness and Satisfiability	1994	PODS
5	7,696	Hard problems for simple logic programs	1990	SIGMOD
6	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	7,064	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
8	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
9	4,712	Tools for Datalog Boundedness	1991	PODS
10	2,062	A Decidable Class of Bounded Recursions	1987	PODS