Parallel Evaluation of Recursive Rule Queries

We investigate the parallel computational complexity of recursive rule queries. These queries are a subset of first-order relational queries augmented with recursion. They form an important part of the PROLOG language and can be evaluated in PTIME. In [32] Sagiv has shown that it is decidable whether a typed recursive rule query is equivalent to a first-order relational query. We present an alternative proof of this fact We demonstrate a "gap" theorem for these queries. We provide two classes of queries, which can be evaluated in NC, using a logarithmic number of iterations of a first-order query. Finally, we give various, syntactically tight, queries which are logspace-complete in PTIME and cannot be evaluated in this fashion.