Why a single parallelization strategy is not enough in knowledge bases (Q686639)

The problem of parallelizing the evaluation of logic programs in data intensive applications is investigated. The particular class of programs which are considered are Datalog programs, i.e. Prolog programs without function symbols. The class is further restricted to programs with one recursive clause only whose head literal is unary or binary and which must be range restricted, i.e. all variables in the head literal must occur in the body literals. A typical example is the program for computing the transitive closure of some binary relation. The programs are classified into decomposable, strongly decomposable ones, and others. It is shown that the strongly decomposable programs are amenable to parallelization that does not incur communication or synchronization (pure parallelization). Moreover, strongly decomposable programs are precisely those that can be purely parallelized while guaranteeing minimal total evaluation costs. A syntactic characterization of strongly decomposable programs is given together with a decision algorithm. Three different parallelization schemas are defined. The first one decomposes the data with a predefined decomposition scheme. For example if the transitive closure of a binary relation over integers is to be computed, and there are \(n\) processors, then the i-th processor is responsible for computing the tuples with \(i\) = first component modulo \(n\). For strongly decomposable programs this strategy is cost minimal, but not time minimal because there is no load balancing. While the first parallelization scheme has no communication overhead, the second parallelization scheme allows communication of control information in order to balance the work load for the processors. The scheme is optimal for strongly decomposable programs. The third scheme permits exchange of data between the processors, but only the unavoidable exchange of relevant data.