About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIGMOD/PODS 1986
Conference paper
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 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.