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

One-Sided Recursions.

Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348
@inproceedings{DBLP:conf/pods/Naughton87,
  author    = {Jeffrey F. Naughton},
  title     = {One-Sided 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     = {340-348},
  ee        = {http://doi.acm.org/10.1145/28659.28695, db/conf/pods/Naughton87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The performance of systems with recursive query languages can be improved by recognizing simple, easily evaluable classes of recursions and using algorithms tailored to these classes whenever possible. In this paper we identify a useful subset of recursive definitions, the one-sided recursions. We show how to detect one-sided recursions, and give two simple evaluation algorithms that cover one-sided definitions in that for any selection on a one-sided definiton, at least one of the two algorithms will apply. These algorithms have simple termination conditions, maintain minimal state and use selections on the recursively defined relation whenever possible. We show that there are no similar algorithms for many-sided recursions. We also prove that it is undecidable whether an arbitrary definition has an equivalent one-sided definition. However, we do present a procedure that converts many potentially one-sided recursions to one-sided form, and prove it complete for a useful class of 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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

Journal Version

Jeffrey F. Naughton: One-Sided Recursions. J. Comput. Syst. Sci. 42(2): 199-236(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. J. ACM 40(3): 683-713(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Jeffrey F. Naughton: One-Sided Recursions. J. Comput. Syst. Sci. 42(2): 199-236(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Jeffrey F. Naughton: Minimizing function-free recursive inference rules. J. ACM 36(1): 69-91(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:54 2010 by Michael Ley (ley@uni-trier.de)