A New Paradigm for Parallel and Distributed Rule-Processing

Technical reports:

Title:: A New Paradigm for Parallel and Distributed Rule-Processing
Author(s):: Wolfson, Ouri
Ozeri, Aya
Date:: 1989
Type:: Technical reports
Department:: Computer Science
Permanent URL:: http://hdl.handle.net/10022/AC:P:12127
Series:: Columbia University Computer Science Technical Reports
Part Number:: CUCS-463-89
Publisher:: Department of Computer Science, Columbia University
Publisher Location:: New York
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.
Subject(s):: Computer science