Parallel Evaluation of Datalog Programs by Load Sharing

Wolfson, Ouri

We propose a method of parallelizing the evaluation of data-intensive Dalalog 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 Dalalog 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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-509-89
Published Here
January 20, 2012