Can I read On the Complexity of Database Queries (Extended Abstract) on EtoBox?

On the Complexity of Database Queries (Extended Abstract) by Christos H. Papadimitriou; Mihalis Yannakakis is a scholarly article available to read on EtoBox.

What is On the Complexity of Database Queries (Extended Abstract) about?

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.

Author

Christos H. Papadimitriou; Mihalis Yannakakis

Publisher

ACM Press

Published

1997

Language

EN