|
NeuroCOLT
Technical Report NC-TR-99-044
Query
languages for semi-algebraic databases based on descriptive complexity
over R
Klaus Meer
Abstract
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 in [8] and descriptive complexity for the latter developed
in [17]. Using this formal framework a uniform treatment of semi-algebraic
query languages is obtained. Precise results about both the data-
and the expressioncomplexity of several such query languages are proved.
More explicitly, relying on descriptive complexity theory over 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
(see [20] , [18]), 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.
Download Compressed Postscript
|