Parallel evaluation of recursive rule queries
Stavros S. Cosmadakis, Paris Christos Kanellakis · 1985
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.