Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 07212

Constraint Databases, Geometric Elimination and Geographic Information Systems

( May 20 – May 25, 2007 )

Please use the following short url to reference this page:



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.


[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.

  • Bernd Bank (HU Berlin, DE)
  • Saugata Basu (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Max J. Egenhofer (University of Maine, US) [dblp]
  • Floris Geerts (University of Edinburgh, GB) [dblp]
  • Marc Giusti (Ecole Polytechnique - Palaiseau, FR)
  • Rafael Grimson (Hasselt University - Diepenbeek, BE)
  • Joos Heintz (University of Cantabria, ES) [dblp]
  • Bart Kuijpers (Hasselt University - Diepenbeek, BE)
  • Lutz Lehmann (HU Berlin, DE)
  • Lixin Li (Georgia Southern University, US)
  • Stephan Mäs (Universität der Bundeswehr - München, DE) [dblp]
  • Walied Othman (Hasselt University - Diepenbeek, BE) [dblp]
  • Reinhard Piltner (Georgia Southern University, US)
  • Jochen Renz (Australian National University, AU) [dblp]
  • Peter Revesz (University of Nebraska - Lincoln, US)
  • Maria Andrea Rodríguez-Tastets (University of Concepción, CL)
  • Takeshi Shirabe (TU Wien, AT)
  • Thomas Sturm (Universität Passau, DE) [dblp]
  • Jan Van den Bussche (Hasselt University - Diepenbeek, BE) [dblp]

  • data bases / information retrieval
  • data structures / algorithms / complexity
  • interdisciplinary
  • geographic information systems

  • constraint databases
  • geometric elimination
  • quantier elimination algorithms
  • geographic information systems