On the complexity of database queries

We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory. We show that, if th e query size (or the number of variables in the query) is considered as a p arameter, then the relational calculus and its fragments (conjunctive queri es, positive queries) are classified at appropriate levels of the so-called W hierarchy of Downey and Fellows. These results strongly suggest that the query size is inherently in the exponent of the data complexity of any que ry evaluation algorithm, with the implication becoming stronger as the expr essibility of the query language increases. On the positive side, we show t hat this exponential dependence can be avoided for the extension of acyclic queries with not equal (but not <) inequalities. (C) 1999 Academic Press.