A New Paradigm for Parallel and Distributed Rule-Processing.

Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142

@inproceedings{DBLP:conf/sigmod/WolfsonO90,
  author    = {Ouri Wolfson and
               Aya Ozeri},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {A New Paradigm for Parallel and Distributed Rule-Processing},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {133-142},
  ee        = {http://doi.acm.org/10.1145/93597.98723, db/conf/sigmod/WolfsonO90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper is concerned with the parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network. We introduce a paradigm, called data-reduction, for the parallel evaluation of a general datalog program. Several parallelization strategies discussed previously in [CW, GST, W, WS] are special cases of this paradigm. The paradigm parallelizes the evaluation by partitioning among the processors the instantiations of the rules. After presenting the paradigm, we discuss the following issues, that we see fundamental for parallelization strategies derived from the paradigm properties of the strategies that enable a reduction in the communication overhead, decomposability, load balancing, and application to programs with negation. We prove that decomposability, a concept introduced previously in [WS, CW], is undecidable.

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

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990

, SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[ABW]: ...
[AJ]: Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66
[AP]: Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213
[Ban]: ...
[Bay]: ...
[BBDW]: 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)
[BR]: ...
[CK]: Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293
[CM]: ...
[CW]: Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216
[D]: Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
[DL]: ...
[F]: Nissim Francez: Distributed Termination. ACM Trans. Program. Lang. Syst. 2(1): 42-55(1980)
[GST]: Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152
[GMSV]: Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115
[HAC]: ...
[K]: Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30
[MW]: David Maier, David Scott Warren: Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings 1988, ISBN 0-8053-6681-4
[M1]: Friedemann Mattern: Algorithms for Distributed Termination Detection. Distributed Computing 2(3): 161-175(1987)
[M2]: Friedemann Mattern: Global Quiescence Detection Based on Credit Distribution and Recovery. Inf. Process. Lett. 30(4): 195-200(1989)
[P]: ...
[R]: Raghu Ramakrishnan: Parallelism in Logic Programs. POPL 1990: 246-260
[RSL]: Louiqa Raschid, Timos K. Sellis, Chih-Chen Lin: Exploiting Concurrency in a DBMS Implementation for Production. DPDS 1988: 34-45
[S]: Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249
[Sh]: ...
[SDSWY]: ...
[SMM]: ...
[U]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[UV]: ...
[VK]: ...
[WS]: Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336
[W]: Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. DPDS 1988: 46-55