Argument Reduction by Factoring.

Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
  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,}


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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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


Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 BibTeX
Jeffrey F. Naughton: Compiling Separable Recursions. SIGMOD Conference 1988: 312-319 BibTeX
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 BibTeX
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX
Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX

Referenced by

  1. Sergio Greco: Binding Propagation in Disjunctive Databases. VLDB 1998: 287-298
  2. Kenneth A. Ross: Tail Recursion Elimination in Deductive Databases. ACM Trans. Database Syst. 21(2): 208-237(1996)
  3. Peter T. Wood: Magic Factoring of Closure Programs. PODS 1995: 174-183
  4. Sergio Greco, Luigi Palopoli, Eugenio Spadafora: DatalogA: Array Manipulations in a Deductive Database Language. DASFAA 1995: 180-188
  5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  6. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
  7. Konstantinos F. Sagonas, Terrance Swift, David Scott Warren: XSB as an Efficient Deductive Database Engine. SIGMOD Conference 1994: 442-453
  8. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: Implementation of the CORAL Deductive Database System. SIGMOD Conference 1993: 167-176
  9. Sergio Greco: Optimization of Chain Queries. DASFAA 1993: 261-268
  10. Sergio Greco, Carlo Zaniolo: Optimization of Linear Logic Programs Using Counting Methods. EDBT 1992: 72-87
  11. S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
  12. S. Seshadri, Jeffrey F. Naughton: On the Expected Size of Recursive Datalog Queries. PODS 1991: 268-279
  13. Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101
  14. Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141
  15. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey: Design Overview of the Aditi Deductive Database System. ICDE 1991: 240-247
  16. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
  17. Kotagiri Ramamohanarao: The Aditi Deductive Database System (Extented Abstract). DASFAA 1991: 201-208
  18. Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
  19. Jeffrey F. Naughton, Raghu Ramakrishnan: How to Forget the Past Without Repeating It. VLDB 1990: 278-289
  20. David B. Kemp, Kotagiri Ramamohanarao, Zoltan Somogyi: Right-, left- and multi-linear rule transformations that maintain context information. VLDB 1990: 380-391
  21. Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:41 2009