Parallel Processing of Recursive Queries in Distributed Architectures.

Guy Hulin: Parallel Processing of Recursive Queries in Distributed Architectures. VLDB 1989: 87-96
  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,}


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

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


Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 BibTeX
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
François Bancilhon, Raghu Ramakrishnan: Performance Evaluation of Data Intensive Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 439-517 BibTeX
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
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) BibTeX
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
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 BibTeX
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 BibTeX
Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX
Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 BibTeX
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX
Laurent Vieille: From QSQ towards QoSaQ: Global Optimization of Recursive Queries. Expert Database Conf. 1988: 743-778 BibTeX
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 BibTeX

Referenced by

  1. Sakti Pramanik, Sungwon Jung: Description and Identification of Distributed Fragments of Recursive Relations. IEEE Trans. Knowl. Data Eng. 8(6): 1002-1016(1996)
  2. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
  3. Sungwon Jung, Sakti Pramanik: An Efficient Representation of Distributed Fragments of Recursive Relations. DASFAA 1995: 397-404
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  5. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  6. Ing-Miin Hsu, Mukesh Singhal, Ming T. Liu: Distributed Rule Processing in Active Databases. ICDE 1992: 106-113
  7. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  8. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:40 2009