Why a Single Parallelization Strategy in not Enough in Knowledge Bases.

Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216
  author    = {Simona Rabinovici-Cohen and
               Ouri Wolfson},
  title     = {Why a Single Parallelization Strategy in not Enough in Knowledge
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {200-216},
  ee        = {, db/conf/pods/CohenW89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP,}


We argue that the appropriate parallelization strategy for logic-program evaluation depends on the program being evaluated. Therefore, this paper is concerned with the issues of program-classification, and parallelization- strategies. We propose five parallelization strategies that differ based on the following criteria. Their evaluation cost, the overhead of communication and synchronization among processors, and the programs to which they are applicable. In particular, we start our study with pure-parallelization, i.e., parallelization without overhead. An interesting class-structure of logic programs is demonstrated, when considering amenability to pure-parallelization. The relationship to the NC complexity class is discussed. Then we propose strategies that do incur an overhead, but are optimal in a sense that will be precisely defined.

This paper makes the initial steps towards a theory of parallel logic-programming.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library


Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 BibTeX
Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 BibTeX
Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40 BibTeX
Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) 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
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
M. Seetha Lakshmi, Philip S. Yu: Effect of Skew on Join Performance in Parallel Architectures. DPDS 1988: 107-120 BibTeX
Katherine A. Morris, Jeffrey F. Naughton, Yatin P. Saraiya, Jeffrey D. Ullman, Allen Van Gelder: YAWN! (Yet Another Window on NAIL!). IEEE Data Eng. Bull. 10(4): 28-43(1987) BibTeX
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. Algorithmica 3: 5-42(1988) BibTeX
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 BibTeX
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55 BibTeX

Referenced by

  1. Weining Zhang, Ke Wang, Siu-Cheung Chau: Data Partition and Parallel Evaluation of Datalog Programs. IEEE Trans. Knowl. Data Eng. 7(1): 163-176(1995)
  2. Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: Mapping Datalog Program Execution to Networks of Procesors. IEEE Trans. Knowl. Data Eng. 7(3): 351-361(1995)
  3. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  5. Ouri Wolfson, Aya Ozeri: Parallel and Distributed Processing of Rules by Data Reduction. IEEE Trans. Knowl. Data Eng. 5(3): 523-530(1993)
  6. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  7. Ing-Miin Hsu, Mukesh Singhal, Ming T. Liu: Distributed Rule Processing in Active Databases. ICDE 1992: 106-113
  8. Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251
  9. Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142
  10. Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152
  11. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
  12. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:33:57 2009