the complexity of evaluating relational queries
We prove a sequence of results which characterize exactly the complexity of problems related to the evaluation of relational queries consisting of projections and natural joins. We show that testing whether the result of a given query on a given relation equals some other given relation is D p complete ( D p is a class which includes both NP and co- NP, and was recently introduced in a totally different context [13]). We show that testing inclusion or equivalence of queries with respect to a fixed relation (or of relations with respect to a fixed query) is ? 2 p -complete. We also examine the complexity of estimating the number of tuples of the answer.
complexity evaluation relation queries queries sequence project test completeness class context inclusion estimates query