DBScholar

Back to papers

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
844
Venue
PODS
Year
1988
Pagerank
9.7653696e-05
Overall Rank
1,788 | 87.74%
DOI
10.1145/308386.308470

Incoming Non-self Citations Over Time

Authors

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
686 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00014948634
953 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012997935
1,856 Automata Theory for Database Theoreticians 1989 PODS 9.6053834e-05
4,343 On Distributed Processibility of Datalog Queries by Decomposing Databases 1989 SIGMOD 6.7529086e-05
4,615 Tools for Datalog Boundedness 1991 PODS 6.6050069e-05
6,077 Safety of Datalog Queries over Infinite Databases 1989 PODS 5.9850223e-05
7,888 Finding Nonrecursive Envelopes for Datalog Predicates 1993 PODS 5.5217972e-05
7,972 On the First-Order Expressibility of Recursive Queries 1989 PODS 5.5160399e-05
9,173 Optimizing Recursive Queries in SQL 2005 SIGMOD 5.3090815e-05
10,640 Circuits and Formulas for Datalog over Semirings 2025 PODS 5.093636e-05
10,690 Dynamic Pruning for Recursive Joins 2025 SIGMOD 5.093636e-05
11,639 Deciding Boundedness of Monadic Sirups 2021 PODS 5.093636e-05
13,020 Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract) 1994 PODS 5.093636e-05
13,023 Universal Finiteness and Satisfiability 1994 PODS 5.093636e-05
13,099 Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases 1991 PODS 5.093636e-05
13,100 Detecting Redundant Tuples During Query Evaluation 1991 PODS 5.093636e-05
13,116 Semigroup techniques in recursive query optimization 1990 PODS 5.093636e-05
Previous Page 1 / 1 Next

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
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
97 Efficient Optimization of a Class of Relational Expressions 1978 SIGMOD 0.00034574497
357 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00020283734
616 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015712636
916 A Time Bound on the Materialization of Some Recursively Defined Views 1985 VLDB 0.00013224702
1,173 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011822695
1,417 On Computing Restricted Projections of Representative Instances 1985 PODS 0.00010839353
2,015 A Decidable Class of Bounded Recursions 1987 PODS 9.3047297e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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