Argument Reduction by Factoring.

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182

@inproceedings{DBLP:conf/vldb/NaughtonRSU89,
  author    = {Jeffrey F. Naughton and
               Raghu Ramakrishnan and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  editor    = {Peter M. G. Apers and
               Gio Wiederhold},
  title     = {Argument Reduction by Factoring},
  booktitle = {Proceedings of the Fifteenth International Conference on Very
               Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands},
  publisher = {Morgan Kaufmann},
  year      = {1989},
  isbn      = {1-55860-101-5},
  pages     = {173-182},
  ee        = {db/conf/vldb/NaughtonRSU89.html},
  crossref  = {DBLP:conf/vldb/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We identify a useful property of a program with respect to a predicate, called factoring. While we prove that detecting factorability is undecidable in general, we show that for a large class of programs, the program obtained by applying the Magic Sets transformation is factorable with respect to the recursive predicate. When the factoring property holds, a simple optimization of the program generated by the Magic Sets transformation results in a new program that is never lessefficient than the Magic Sets program and is often dramatically more efficient,due to the reduction of the arity of the recursive predicate. We show that the concept of factoring generalizes some previously identified special cases of recursions, including separable recursions and right- and left-linear recursions, and that the specialized evaluation algorithms and rewriting strategies developed for those classes can be derived automatically by applying the Magic Sets transformation and then factoring the result.

Copyright © 1989 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" 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/vldb8997 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

Peter M. G. Apers, Gio Wiederhold (Eds.): Proceedings of the Fifteenth International Conference on Very Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. Morgan Kaufmann 1989, ISBN 1-55860-101-5

References

[ASU79]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[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
[CM77]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[Nau87]: Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348
[Nau88]: Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319
[NRSU89]: Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
[Ram87]: Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159
[RBK88]: Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
[Sag87]: Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
[SZ86]: Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53