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

Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules.

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
@inproceedings{DBLP:conf/sigmod/NaughtonRSU89,
  author    = {Jeffrey F. Naughton and
               Raghu Ramakrishnan and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {235-242},
  ee        = {http://doi.acm.org/10.1145/67544.66948, db/conf/sigmod/NaughtonRSU89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present an algorithm for the efficient evaluation of a useful subset of recursive queries. Like the magic sets transformation, the algorithm consists of a rewriting phase followed by semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of recursions, this algorithm achieves a factor of O(n) speedup over magic sets. Intuitively, the transformations in this algorithm achieve their performance by reducing the arity of the recursive predicates in the transformed rules.

Copyright © 1989 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 ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library


References

[Agr87]
Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AU79]
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
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BR86]
...
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha81]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HN84]
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
[HN88]
Ramsey W. Haddad, Jeffrey F. Naughton: Counting Methods for Cyclic Relations. PODS 1988: 333-340 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KL86]
...
[Nau87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nau88]
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RHDM86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sag88]
...
[SZ86]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vie86]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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