Compiling Separable Recursions.
Jeffrey F. Naughton:
Compiling Separable Recursions.
SIGMOD Conference 1988: 312-319@inproceedings{DBLP:conf/sigmod/Naughton88,
author = {Jeffrey F. Naughton},
editor = {Haran Boral and
Per-{\AA}ke Larson},
title = {Compiling Separable Recursions},
booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
Management of Data, Chicago, Illinois, June 1-3, 1988},
publisher = {ACM Press},
year = {1988},
pages = {312-319},
ee = {http://doi.acm.org/10.1145/50202.50240, db/conf/sigmod/Naughton88.html},
crossref = {DBLP:conf/sigmod/88},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
In this paper we consider evaluating queries on
relations defined by a combination of recursive rules.
We first define separable recursions. We then give a
specialized algorithm for evaluating selections on separable recursions. Like the Generalized Magic Sets
and Generalized Counting algorithms, this algorithm
uses selection constants to avoid examining irrelevant portions of the database, however, on some simple recursions this algorithm is O(n), whereas Generalized Magic Sets is Omega(n2) and Generalized Counting is Omega(n2).
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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Haran Boral, Per-Åke Larson (Eds.):
Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988.
ACM Press 1988
,
SIGMOD Record 17(2), June 1988
Contents
References
- [AU79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120
![bibliographical record in XML](../../xml.gif)
- [BKBR87]
- Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan:
Bounds on the Propagation of Selection into Logic Programs.
PODS 1987: 214-226
![bibliographical record in XML](../../xml.gif)
- [BMSU86]
- François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman:
Magic Sets and Other Strange Ways to Implement Logic Programs.
PODS 1986: 1-15
![bibliographical record in XML](../../xml.gif)
- [BR87]
- Catriel Beeri, Raghu Ramakrishnan:
On the Power of Magic.
PODS 1987: 269-284
![bibliographical record in XML](../../xml.gif)
- [Cha81]
- Chin-Liang Chang:
On Evaluation of Queries Containing Derived Relations in a Relational Data Base.
Advances in Data Base Theory 1979: 235-260
![bibliographical record in XML](../../xml.gif)
- [HH87]
- Jiawei Han, Lawrence J. Henschen:
Handling Redundancy in the Processing of Recursive Database Queries.
SIGMOD Conference 1987: 73-81
![bibliographical record in XML](../../xml.gif)
- [HN84]
- Lawrence J. Henschen, Shamim A. Naqvi:
On compiling queries in recursive first-order databases.
J. ACM 31(1): 47-85(1984)
![bibliographical record in XML](../../xml.gif)
- [MN82]
- Jack Minker, Jean-Marie Nicolas:
On recursive axioms in deductive databases.
Inf. Syst. 8(1): 1-13(1983)
![bibliographical record in XML](../../xml.gif)
- [Nau87]
- Jeffrey F. Naughton:
One-Sided Recursions.
PODS 1987: 340-348
![bibliographical record in XML](../../xml.gif)
- [Nau88a]
- ...
- [Nau88b]
- ...
- [SZ86]
- Domenico Saccà, Carlo Zaniolo:
The Generalized Counting Method for Recursive Logic Queries.
ICDT 1986: 31-53
![bibliographical record in XML](../../xml.gif)
- [Ull86]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
![bibliographical record in XML](../../xml.gif)
Copyright © Fri Mar 12 17:21:28 2010
by Michael Ley (ley@uni-trier.de)