ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs.

Georges Gardarin: Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs. VLDB 1987: 21-30
@inproceedings{DBLP:conf/vldb/Gardarin87,
  author    = {Georges Gardarin},
  editor    = {Peter M. Stocker and
               William Kent and
               Peter Hammersley},
  title     = {Magic Functions: A Technique to Optimize Extended Datalog Recursive
               Programs},
  booktitle = {VLDB'87, Proceedings of 13th International Conference on Very
               Large Data Bases, September 1-4, 1987, Brighton, England},
  publisher = {Morgan Kaufmann},
  year      = {1987},
  isbn      = {0-934613-46-X},
  pages     = {21-30},
  ee        = {db/conf/vldb/Gardarin87.html},
  crossref  = {DBLP:conf/vldb/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Several methods have been proposed to compile recursive Datalog programs. The most well-known perform a rewriting of rules using MAGIC or PROBLEM predicates in order to push selections before recursion. Rewritten rule systems are generally complex and difficult to translate into optimized relational algebra programs. Moreover, they often generate too many results; thus, the query must be applied to the generated results to eliminate non relevant answers. In this paper, after a survey of the existing compilation techniques which points out their limitations, we develop the magic function method introduced in [Gardarin- DeMaindreville86]. It is based on an understanding of the query as a function which maps columns of a relation to other columns. A query against recursive rules is then translated into a fixpoint functional equation. The resolution of this fixpoint equation using Tarski's theorem leads to efficient computation of the query answer. In particular, the derived algorithms push selections through recursion, because selections appear as function arguments. They generate only relevant answers to a given query, without redundant data computation. The purpose of this paper is the introduction of a generalized method to obtain and resolve the fixpoint functional equation. The method is general enough to handle non-binary rules, cyclic rules and function symbols. The main advantages of the method are : (1) It directly generates an optimized relational algebra program. (2) It performs a symbolic precomputation which permits rule redundancy elimination. (3) It fully supports function symbols and range queries.

Copyright © 1987 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 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Peter M. Stocker, William Kent, Peter Hammersley (Eds.): VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. Morgan Kaufmann 1987, ISBN 0-934613-46-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Aho-Ullman79]
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
[Bancilhon85]
...
[Bancilhon86]
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
[Bancilhon-Rama86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Beeri87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ceri86]
Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chandra82]
Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Chang81]
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
[Delobel86]
...
[Gallaire81]
...
[Gallaire84]
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gardarin-DeMaindreville85]
...
[Gardarin-DeMaindreville86]
Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gardarin-Pucheral86]
...
[Gardarin87]
...
[Gardarin-Guessarian-DeMaindreville]
...
[Guessarian87]
...
[Henschen-Naqvi84]
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
[Lozinskii85]
Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kifer-Lozinskii86]
Michael Kifer, Eliezer L. Lozinskii: Implementing Logic Programs as a Database System. ICDE 1987: 375-385 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Marque-Pucheu83]
...
[Merrett84]
...
[Rohmer85]
...
[Sacca-Zaniolo86]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tarski55]
...
[Ullman86]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vieille86]
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
[Zaniolo86]
...

Copyright © Mon Mar 15 03:55:50 2010 by Michael Ley (ley@uni-trier.de)