Parallel evaluation of datalog programs by load sharing

AbstractWe propose a method of parallelizing the evaluation of data-intensive Datalog programs. The method is distinguished by the fact that it is pure, i.e., does not require interprocessor communication, or synchronization overhead. The method cannot be used to parallelize every Datalog program, but we syntactically characterize several classes of Datalog programs that are sharable, i.e., programs to which the method can be applied. We also provide a characterization of a class of nonsharable programs, and demonstrate that sharability is a fundamental notion that is independent of the syntactic parallelization method proposed in this paper. This notion is related to bottom-up evaluation (we propose a formal characterization of this type of control-strategies) and to program classification