Query languages for semi-algebraic databases based on descriptive complexity over \mathbb R
Klaus Meer
We propose the study of query languages for databases involving real numbers as data (called semi-algebraic databases in the sequel). As main new aspect our approach is based on real number complexity theory as introduced by Blum, Shub and Smale and descriptive complexity for the latter developed by Grädel and the author. Using this formal framework a uniform treatment of semi-algebraic query languages is obtained. Precise results about both the data- and the expression-complexity of several such query languages are proved. More explicitly, relying on descriptive complexity theory over $\mathbb R$ gives the possibility to derive a hierarchy of complete languages for most of the important real number complexity classes. A clear correspondence between different logics and such complexity classes is established. In particular, it is possible to formalize queries involving in a uniform manner real spaces of different dimensions. This can be done in such a way that the logical description exactly reflects the computational complexity of a query. The latter might circumvent a problem appearing in some of the former approaches dealing with semi-algebraic databases, where the use of first-order logic over real-closed fields can imply inefficiency as soon as the dimension of the underlying real space is not fixed - no matter whether the query under consideration is easy to compute or not.