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}
}
BibTeX

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 ... BibTeX

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 BibTeX

References

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

Referenced by

  1. Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed: Recursive Functions in Iris. ICDE 1993: 145-154
  2. Georges Gardarin, Rosana S. G. Lanzelotte: Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting. EDBT 1992: 534-549
  3. Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990)
  4. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  5. Nikolaus Steger, Helmut Schmidt, Ulrich Güntzer, Werner Kießling: Semantics and Efficient Compilation for Quantitative Deductive Databases. ICDE 1989: 660-669
  6. Qiming Chen, Georges Gardarin: An Implementation Model for Reasoning with Complex Objects. SIGMOD Conference 1988: 164-172
  7. Michael Kifer, Ai Li: On the Semantics of Rule-Based Expert Systems with Uncertainty. ICDT 1988: 102-117
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
 ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:33 2009