The parallel complexity of single rule logic programs

The paper considers logic programs without function symbols, called Datalog programs, and studies their parallel complexity. It surveys the tools developed for proving that there is a PRAM algorithm which computes the minimum model of a Datalog program in polylogarithmic parallel time using a polynomial number of processors (that is, for proving membership in 𝒩𝒞). The paper extends certain of these tools to be applied to a wider class of programs; as they were, they were applied to chain rule programs (i.e., the relations on the right-hand side of the rule are binary and form a chain). It examines the parallel complexity of weak-chain rule programs (i.e., the relations on the right-hand side of the rule form a weak chain), and proves certain subclasses to belong to 𝒩𝒞. Finally the paper proves a wide class of programs to be log space complete for 𝒫, by giving sufficient conditions for a single rule program to be 𝒫-complete.