This paper is highly theoretical and is concerned with the characterization of the complexity of problems related to the evaluation of relational queries, consisting of projections and natural joins.

Relational queries are expressed using relational algebra, which has been shown elsewhere to be equivalent to a version of first-order logic. The results of this paper imply that, unlike in ordinary algebra of integer operations (with exponentiation), intermediate results can be inherently much larger than both input (relations) and the results.

Specifically, it is shown that testing whether the result of a given query in a given relation equals some other given relation is DP-complete [1]. Testing a inclusion or equivalence of queries with respect to a fixed relation (or of relations with respect to a fixed query) is found to be &pgr; ^p2 - complete [2]. Furthermore, the complexity of estimating or bounding the number of tuples of the answer is examined. In essence, these problems are very precisely characterized in terms of where they fall in the polynomial-time hierarchy.

The complexity results are proved by reduction of the appropriate complete satisfiability problem [2] to the problem in question. A construction extensively used in the proofs is reminiscent of that used, for example, in [3].