The parallel evaluation of datalog rule programs, mainly by processors that are interconnected by a communication network, is discussed. Data-reduction, a paradigm for the parallel evaluation of a datalog program, is introduced. Parallelization is accomplished by partitioning the rule-instantiations among the processors. After presenting the paradigm, its implementation with seminaive evaluation, its communication overhead, and its application to stratified-negation datalog programs are discussed. It is proven that decomposability, a related concept introduced in previous works, is undecidable.>

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.