Technical Report CS0564

Title: Parallel Bottom-Up Evaluation of Datalog Program By Load Sharing
Authors: Ouri Wolfson
Abstract: We propose a method of parallelizing bottom-up-evaluation of logic 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 logic progtam, but we syntactically characterize several classes of logic programs to which the method can be applied (e.g., the class of linear single rule programs). We also provide a characterization for a class of programs to which the parallelization method cannot be applied, and show that in general, determining applicability is undecidable. Then, we generalize the concepts beyond the proposed method, and lay the foundations for a theory of logic progranis and parallelization. It demonstrates that the logic programs have an interesting hiezarchical class structure, with respect to pure parallelization.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion