https://www.dagstuhl.de/07212

### 20. – 25. Mai 2007, Dagstuhl-Seminar 07212

# Constraint Databases, Geometric Elimination and Geographic Information Systems

## Organisatoren

Bernd Bank (HU Berlin, DE)

Max J. Egenhofer (University of Maine, US)

Bart Kuijpers (Hasselt University – Diepenbeek, BE)

## Auskunft zu diesem Dagstuhl-Seminar erteilt

## Dokumente

## Summary

During the past 15 years the topic of constraint databases [1] 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 continous data, that have a geometric interpretation, need 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,1]. In these applications infinite geometrical sets of continous 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 extensively studied in real algebraic geometry). On the other hand, constraint databases provide us with a new view on classic (linear and nonlinear) optimization theory.

A variety of languages, mostly extensions of first-order logic over the reals, has been proposed and studied for querying constraint databases in various applications. The expressive power of these query languages has been analyzed in many aspects, especially with applications in GIS and spatial databases in mind. On the other hand, beyond general complexity results of real algebraic geometry, little is known about the specific complexity of query evaluation in constraint database systems. Consequently the propagation of theoretical research results into database practice is hindered by the inefficiency of general purpose algorithms from real algebraic geometry used up to now for the implementation of query evaluation. These implementations are mostly based on quantifier-elimination and only query languages for linear constraint databases have been implemented in practice. The need for efficient algorithms is most visible for the basic query language FO, first-order logic over the reals. Also extensions of FO by for instance the “sum (of a finite set)”, “topological connectivity”,“path connectivity” or other topological operators have received much attention in recent years and are considered to be of great importance for practical applications, specifically in GIS. Both for FO and for these extensions query evaluation is implemented through the standard general purpose algorithms from real algebraic geometry. The sequential time complexity of these algorithms depends intrinsically (and in worst case exponentially) on the arrangement size of the data and (superexponentially) on the number of quantifier alternations of the query under consideration. On the other hand this complexity is polynomial for fixed arrangement size of the data and fixed number of quantifier alternations of the query.

From the above it should be clear that researchers from the areas of constraint databases, geometric elimination algorithms and geographic information systems should work together to address the feasibility of the constraint database approach to deal with application demands in geographic information systems.

GIS researchers find in the constraint database model a powerful and elegant tool for application in spatial databases and GIS. Its clean mathematical formulation allows the study of the expressive power of query languages in much more rigorous way than is the case for most other, often ad-hoc, approaches in GIS. From the users side, GIS researchers can describe the requirements of applications and specify which fragments of the constraint database query languages are useful and needed in GIS practice.

Researchers in geometric elimination theory find a practical application par excellence of their algorithms in constraint databases. Efficient elimination algorithms form a bottleneck for the development of practical development of constraint database systems that have potential for commercial use in GIS.

The aim of this seminar is to bring together researchers from the areas of constraint databases, geometric elimination algorithms and geographic information systems to address the feasibility of the constraint database in the area of geographic information systems. This seminar also has the explicit purpose of identifying an appropriate forum for presenting and discussing future advances and exploring cross-fertilization to related topics, possibly in the form of setting up a joint conference (or series of conferences) on this topic.

References:

[1] G. Kuper, L. Libkin and J. Paredaens (eds.), Constraint Databases, Springer-Verlag, 2000.

[2] P. Rigaux, M. Scholl, and A. Voisard, Spatial Databases—With Application to GIS. Morgan Kaufmann, 2001.

## Classification

- Data Bases / Information Retrieval
- Data Structures / Algorithms / Complexity
- Interdisciplinary
- Geographic Information Systems

## Keywords

- Constraint databases
- Geometric elimination
- Quantier elimination algorithms
- Geographic information systems