Query languages for real number databases based on descriptive complexity over R

  • We propose the study of query languages for databases involving real numbers as data (called real number 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 query languages for such databases 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 ℝ 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 aWe propose the study of query languages for databases involving real numbers as data (called real number 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 query languages for such databases 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 ℝ 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.show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Klaus MeerGND
URL:http://link.springer.com/chapter/10.1007%2F3-540-48340-3_2
DOI:https://doi.org/10.1007/3-540-48340-3_2
ISBN:978-3-540-66408-6
Title of the source (English):Mathematical foundations of computer science 1999, 24th international symposium, MFCS '99, Szklarska Pore̜ba, Poland, September 6 - 10, 1999, proceedings
Publisher:Springer
Place of publication:Berlin [u.a.]
Editor: Miroslaw Kutylowski, Pacholski Leszek, Tomasz Wierzbicki
Document Type:Conference Proceeding
Language:English
Year of publication:1999
First Page:12
Last Page:22
Series ; volume number:Lecture Notes in Computer Science ; 1672
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.