On the complexity of database queries (extended abstract)
Christos H. Papadimitriou, Mihalis Yannakakis · 1997
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 the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queries, 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 query evaluation algorithm, with the implication becoming stronger as the expressibility of the query language increases.For recursive languages (fixpoint logic, Datalog) this is provably the case [14].On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with # (but not <) inequalities.IA third kind, expression complezify assun~cs that tho database instance is fixed, and is rarely differentiated from tho combined complexity.