Constraint databases, geometric elimination and geographic information systems

During the past 15 years the topic of constraint databases (CDB) [2, 3] has evolved into a mature area of computer science with sound mathematical foundations and with a profound theoretical understanding of the expressive power of a variety of query languages. Constraint databases are especially suited for applications in which possibly infinite sets of continuous data, which have a geometric interpretation, have to be stored in a computer. Today, the most important application domains of constraint databases are geographic information systems (GIS), spatial databases and spatio-temporal databases [2, 3, 4]. In these applications infinite geometrical sets of continuous data are finitely represented by means of finite combinations of polynomial equality and inequality constraints that describe these data sets (in mathematical terms these geometrical data sets are known as semi-algebraic sets and they have been exten-sively studied in real algebraic geometry). On the other hand, constraint databases provide us with a new view of classic (linear and nonlinear) optimization theory. A variety of languages, mostly extensions of first-order logic over the reals, has been pro-posed and studied for querying constraint databases in various applications. The expressive power of these query languages has been analyzed in many aspects, especially with application