Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.

@inproceedings{DBLP:conf/pods/Vardi88,
  author    = {Moshe Y. Vardi},
  title     = {Decidability and Undecidability Results for Boundedness of Linear
               Recursive Queries},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {341-351},
  ee        = {http://doi.acm.org/10.1145/308386.308470, db/conf/pods/Vardi88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ASU79]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[BR86]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[Ch81]

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[CK86]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX

[CGKV87]

Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490 BibTeX

[CM77]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[CMG86]

Upen S. Chakravarthy, Jack Minker, John Grant: Semantic Query Optimization: Additional Constraints and Control Strategies. Expert Database Conf. 1986: 345-379 BibTeX

[GM78]

...

[GMSV87]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX

[HN84]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[Im86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Io85]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[JCV84]

Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX

[Ka86]

...

[Mo74]

...

[MUV84]

David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX

[Na86a]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX

[Na86b]

Jeffrey F. Naughton: Redundancy in Function-Free Recursive Rules. SLP 1986: 236-245 BibTeX

[Na86c]

...

[NS87]

Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 BibTeX

[Sa85]

Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 BibTeX

[Ul85]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[Va82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Va87]

...

[Zl76]

...

Referenced by

1. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
2. Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396
3. Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410
4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
5. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
6. Wenyu Lu, Dik Lun Lee, Jiawei Han: A Study on the Structure of Linear Recursion. IEEE Trans. Knowl. Data Eng. 6(5): 723-737(1994)
7. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
8. Foto N. Afrati: Bounded Arity Datalog (!=) Queries on Graphs. PODS 1994: 97-106
9. Surajit Chaudhuri: Finding Nonrecursive Envelopes for Datalog Predicates. PODS 1993: 135-146
10. Jiawei Han, Kangsheng Zeng, Tong Lu: Normalization of Linear Recursions in Deductive Databases. ICDE 1993: 559-567
11. Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308
12. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
13. Laks V. S. Lakshmanan, Héctor J. Hernández: Structural Query Optimization - A uniform Framework for Semantic Query Optimization in Deductive Databases. PODS 1991: 102-114
14. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12
15. Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
16. Thane E. Plambeck: Semigroup Techniques in Recursive Query Optimization. PODS 1990: 145-153
17. Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378
18. Irène Guessarian: Deciding Boundedness for Uniformly Connected Datalog Programs. ICDT 1990: 395-405
19. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
20. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
21. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
22. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
23. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
24. Guozhu Dong: On the Composition and Decomposition of Datalog Program Mappings. ICDT 1988: 87-101