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. Constraint 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 again within the constraint model. For reasons of efficiency, this model is implemented with only linear polynomial constraints. In this case, we also have a closure property: linear queries evaluated on linear databases yield linear databases. However, the limitation to linear polynomial constraints has severe implications on the expressive power of the query language. 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 not expressible. The aim of this paper is to identify a class of two-dimensional constrain