Parallelizing Datalog programs by generalized pivoting
Jürgen Seib, Georg Lausen · 1991
A Datalog program consists of function-free Horn clause rules.The main problem in evaluating Datalog programs is to achieve an acceptable performance.The reason is, that Datalog programs usually are evaluated bottom-up to compute in an iterative way the fixpoint of the program.Given a large amount of base facts, program evaluation can be a very lengthy process.In the paper parallel processing of decomposable Datalog programs is considered to overcome this problem.A decomposable program can be evaluated in parallel such that neither a communication nor a synchronization of the processors haa to be established [WS88].The concept of generalized pivoting is proposed, which is a sufficient condition for decomposability of arbitrary Datalog programs.Moreover, the clam of completely decomposable programs is introduced and it is shown, that generalized pivoting is also a necessary condition for complete decomposability.