ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Parallel Processing of Recursive Queries in Distributed Architectures.

Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96
@inproceedings{DBLP:conf/vldb/Hulin89,
  author    = {Guy Hulin},
  editor    = {Peter M. G. Apers and
               Gio Wiederhold},
  title     = {Parallel Processing of Recursive Queries in Distributed Architectures},
  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     = {87-96},
  ee        = {db/conf/vldb/Hulin89.html},
  crossref  = {DBLP:conf/vldb/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper presents a parallel algorithm for recursive query processing and shows how it can be efficiently implemented in a local computer network. The algorithm relies on an interpretive approach where recursive rule processing and data retrieval are merged in a top-down computation. It employs "sideways information passing" to restrict to relevant facts the information extracted from the relational database. Evaluation is divided into a compilation phase and a dynamic phase. The compilation phase statically constructs a derivation tree that expresses the decomposition of a query into subqueries and the "sideways information passing" strategy. In the dynamic phase, cooperative processes are associated with subsets of "equivalent" nodes of the derivation tree. They communicate by message passing without sharing memory. Some optimizations are discussed for a practical parallel implementation. Gains in efficiency with respect to classical sequential algorithms are also discussed.

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

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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
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
[3]
François Bancilhon, Raghu Ramakrishnan: Performance Evaluation of Data Intensive Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 439-517 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
K. Mani Chandy, Jayadev Misra: An Example of Stepwise Refinement of Distributed Programs: Quiescence Detection. ACM Trans. Program. Lang. Syst. 8(3): 326-343(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
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
[8]
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
[9]
...
[10]
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
[11]
...
[12]
...
[13]
Martin L. Kersten, Peter M. G. Apers, Maurice A. W. Houtsma, Erik J. A. van Kuyk, Rob L. W. van de Weg: A Distributed, Main-Memory Database Machine. IWDM 1987: 353-369 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
G. Marque-Pucheu, J. Martin-Gallausiaux, Geneviève Jomier: Interfacing Prolog and Relational Data Base Management Systems. ICOD-2 Workshop on New Applications of Data Bases 1983: 225-244 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
...
[18]
...
[19]
...
[20]
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
...
[23]
Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
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
[25]
Laurent Vieille: From QSQ towards QoSaQ: Global Optimization of Recursive Queries. Expert Database Conf. 1988: 743-778 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
...

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)