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(n²) and Generalized Counting is Omega(n²).

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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

Online Edition: ACM Digital Library

References

[AU79]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[BKBR87]: Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226
[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
[BR87]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[Cha81]: Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260
[HH87]: Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
[HN84]: Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)
[MN82]: Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983)
[Nau87]: Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348
[Nau88a]: ...
[Nau88b]: ...
[SZ86]: Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53
[Ull86]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents