Parallel evaluation of recursive rule queries

Abstract

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 psrt of the PROLOG language aud can be eva!uated 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 ETIME and cannot be evaluated in this fashion. 1. InJroduction Relational query languages (IO, 351 augmented with recursion (as an added primitive) have received considerable attention in the literature. e.g.,