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}
}

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 ...

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/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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

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

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)
[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)
[3]: ...
[4]: Yannis E. Ioannidis: A Time Bound on the Materialization of Some Recursively Defined Views. Algorithmica 1(3): 361-385(1986)
[5]: Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30
[6]: Michael J. Maher: Eqivalences of Logic Programs. ICLP 1986: 410-424
[7]: Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279
[8]: Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989)
[9]: ...
[10]: Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
[11]: Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976)