dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries.

Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries. VLDB 1990: 372-379
@inproceedings{DBLP:conf/vldb/KuittinenNSS90,
  author    = {Juhani Kuittinen and
               Otto Nurmi and
               Seppo Sippu and
               Eljas Soisalon-Soininen},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Efficient Implementation of Loops in Bottom-Up Evaluation of
               Logic Queries},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {372-379},
  ee        = {http://www.vldb.org/conf/1990/P372.PDF},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We consider the efficient implementation of the bottom-up evaluation method for recursive queries in logic databases. In the bottom-up evaluation algorithms the non-mutually-recursive rules are evaluated in certain order, whereas the evaluation order within a set of the mutually recursive rules is free. However, significant savings in join operations can be achieved by arranging the mutually recursive rules appropriately. We present an algorithm for splitting the evaluation loop for mutually recursive rules into subloops and for determining the order in which the rules shouldbe evaluated within a loop. The semi- naive evaluation algorithm is modified accordingly to gain advantagefrom the evaluation order and to work with the incremental relations ("deltas") appearing at different levels in the loop structure. The computation within a subloop is optimized by identifying loop- invariant factors in the rules to be evaluated. Using an experimental logic database system we demonstrate the usefulness of our algorithm in implementing data- log queries optimized by the "magic sets" and related term rewriting strategies.

Copyright © 1990 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.


Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
...
[3]
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
[4]
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
[5]
...
[6]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
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
[8]
Stefano Ceri, Letizia Tanca: Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries. VLDB 1987: 31-41 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
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
[14]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Mon Sep 17 22:00:48 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page