|
Title
|
|
|
|
Euclid, Tarski, and Engeler encompassed (Preliminary report)
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| The research presented in this paper is situated in the framework of constraint databases that was introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990. In this area, databases and query languages are defined using real polynomial constraints. As a consequence of a classical result by Tarski, first-order queries in the constraint database model are effectively computable, and their result is within the constraint model. In practical applications, for reasons of efficiency, this model is implemented with only linear polynomial constraints. Here, we also have a closure property: linear queries evaluated on linear databases yield linear databases. The limitation to linear polynomial constraints has severe implications on the expressive power of the query language, however. Indeed, the constraint database model has its most important applications in the field of spatial databases and, with only linear polynomials, the data modeling capabilities are limited and queries important for spatial applications that involve Euclidean distance are no longer expressible. The aim of this paper is to identify a class of two-dimensional constraint databases and a query language within the constraint model that go beyond the linear model. Furthermore, this language should allow the expression of queries concerning distance. Hereto, we seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. In the course of reaching our goal, we have studied three languages for ruler-and-compass constructions. Firstly, we present a programming language. We show that this programming language captures exactly the ruler and compass constructions that are also expressible in the first-order constraint language with arbitrary polynomial constraints. If our programming language is extended with a while operator, we obtain a language that is complete for all ruler-and-compass constructions in the plane, using techniques of Engeler. Secondly, we transform this programming; language into a query language for a constraint database model. We show that the full expressive power of this query language is that of the first-order language with arbitrary polynomial constraints. It is therefore too powerful for our purposes. Thirdly, we consider a safe fragment of this language. Safe queries have the property that they map finite point relations to finite point relations that are constructible from the former. The latter language is the key ingredient in the formulation of our main result. We prove a closure property for the class of constraint databases consisting of those planar figures that can be described by means of constraints that use linear polynomials and polynomials that represent circles. Based on our notion of safe queries, mentioned above, we define a query language on this class of databases. When the attention is restricted to finite databases, this language captures exactly the ruler-and-compass constructions. We also compare the expressive power of the different languages mentioned above. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Lecture notes in computer science. - Berlin, 1973, currens
| |
|
Publication
|
|
|
|
Berlin
:
1998
| |
|
ISSN
|
|
|
|
0302-9743
[print]
1611-3349
[online]
| |
|
Volume/pages
|
|
|
|
1369
(1998)
, p. 1-24
| |
|
ISI
|
|
|
|
000082725500001
| |
|