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

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 4, VLDB '75-'88" 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/vldb7588 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. 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

References

[Aho-Ullman79]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[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
[Bancilhon-Rama86]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
[Beeri87]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[Ceri86]: Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402
[Chandra82]: Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163
[Chang81]: Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260
[Delobel86]: ...
[Gallaire81]: ...
[Gallaire84]: Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
[Gardarin-DeMaindreville85]: ...
[Gardarin-DeMaindreville86]: Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186
[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)
[Lozinskii85]: Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177
[Kifer-Lozinskii86]: Michael Kifer, Eliezer L. Lozinskii: Implementing Logic Programs as a Database System. ICDE 1987: 375-385
[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
[Tarski55]: ...
[Ullman86]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)
[Vieille86]: Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267
[Zaniolo86]: ...