1989 Reports
Parallel Evaluation of Datalog Programs by Load Sharing
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.
Subjects
Files
-
cucs-509-89.pdf application/pdf 1.15 MB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-509-89
- Published Here
- January 20, 2012