TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 07212

Constraint Databases, Geometric Elimination and Geographic Information Systems

( 20. May – 25. May, 2007 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/07212

Organisatoren



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.


Teilnehmer
  • 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]

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

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