ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Decidable Class of Bounded Recursions.

Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236
@inproceedings{DBLP:conf/pods/NaughtonS87,
  author    = {Jeffrey F. Naughton and
               Yehoshua Sagiv},
  title     = {A Decidable Class of Bounded Recursions},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {227-236},
  ee        = {http://doi.acm.org/10.1145/28659.28684, db/conf/pods/NaughtonS87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Detecting bounded recursion is a powerful optimization technique for recursive database query languages as bounded recursions can be replaced by equivalent nonrecursive definitions. The problem is of theoretical interest because by varying the class of recursions considered one can generate instances that vary from linearly decidable to NP-hard to undecidable. In this paper we review and clarify the existing definitions of boundedness. We then specify a simple criterion that guarantees that the condition in Naughton [7] is necessary and sufficient for boundedness.The programs satisfying this criterion subsume and extend previously known decidable classes of bounded linear recursions.

Copyright © 1987 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. J. ACM 40(3): 683-713(1993) BibTeX
[3]
...
[4]
Yannis E. Ioannidis: A Time Bound on the Materialization of Some Recursively Defined Views. Algorithmica 1(3): 361-385(1986) BibTeX
[5]
Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30 BibTeX
[6]
Michael J. Maher: Eqivalences of Logic Programs. ICLP 1986: 410-424 BibTeX
[7]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 BibTeX
[8]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX
[9]
...
[10]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[11]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

Referenced by

  1. Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396
  2. Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
  5. 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)
  6. Inderpal Singh Mumick, Oded Shmueli: Universal Finiteness and Satisfiability. PODS 1994: 190-200
  7. Jiawei Han, Kangsheng Zeng, Tong Lu: Normalization of Linear Recursions in Deductive Databases. ICDE 1993: 559-567
  8. 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
  9. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12
  10. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
  11. Irène Guessarian: Deciding Boundedness for Uniformly Connected Datalog Programs. ICDT 1990: 395-405
  12. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
  13. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  14. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  15. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  16. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  17. Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336
  18. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
  19. Peter T. Wood, Alberto O. Mendelzon, Paolo Atzeni: Idempotent Single-Predicate Horn Clauses. ICDT 1988: 129-143
  20. Guozhu Dong: On the Composition and Decomposition of Datalog Program Mappings. ICDT 1988: 87-101
  21. Weining Zhang, Clement T. Yu: A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule. SIGMOD Conference 1987: 345-356
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:52 2009