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 
Journal Version
Jeffrey F. Naughton:
One-Sided Recursions.
J. Comput. Syst. Sci. 42(2): 199-236(1991)
References
- [1]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120
- [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
- [3]
- François Bancilhon, Raghu Ramakrishnan:
An Amateur's Introduction to Recursive Query Processing Strategies.
SIGMOD Conference 1986: 16-52
- [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)
- [6]
- ...
- [7]
- Lawrence J. Henschen, Shamim A. Naqvi:
On compiling queries in recursive first-order databases.
J. ACM 31(1): 47-85(1984)
- [8]
- H. V. Jagadish, Rakesh Agrawal, Linda Ness:
A Study of Transitive Closure As a Recursion Mechanism.
SIGMOD Conference 1987: 331-344
- [9]
- Paris C. Kanellakis:
Logic Programming and Parallel Complexity.
ICDT 1986: 1-30
- [10]
- Jack Minker, Jean-Marie Nicolas:
On recursive axioms in deductive databases.
Inf. Syst. 8(1): 1-13(1983)
- [11]
- Jeffrey F. Naughton:
Data Independent Recursion in Deductive Databases.
PODS 1986: 267-279
- [12]
- Jeffrey F. Naughton:
One-Sided Recursions.
J. Comput. Syst. Sci. 42(2): 199-236(1991)
- [13]
- Jeffrey F. Naughton:
Minimizing function-free recursive inference rules.
J. ACM 36(1): 69-91(1989)
- [14]
- ...
- [15]
- Yehoshua Sagiv:
Optimizing Datalog Programs.
PODS 1987: 349-362
Copyright © Fri Mar 12 17:19:54 2010
by Michael Ley (ley@uni-trier.de)
