The dedale System for Complex Spatial Queries.
Stephane Grumbach (Universita di Roma Tre and INRIA)
Philippe Rigaux (CEDRIC/CNAM)
Luc Segoufin (INRIA)
This paper presents dedale, a spatial database system intended to
overcome some limitations of current systems by providing an abstract and
non-specialized data model and query language for the representation and
manipulation of spatial objects. dedale relies on a logical model
based on linear constraints, which generalizes the constraint database model of
[KKR90]. While in the classical constraint model, spatial data is always
decomposed into its convex components, in dedale holes are allowed to
fit the need of practical applications. The logical representation of spatial
data although slightly more costly in memory, has the advantage of simplifying
the algorithms. dedale relies on nested relations, in which all sorts
of data (thematic, spatial, etc.) are stored in a uniform fashion. This new
data model supports declarative query languages, which allow an intuitive and
efficient manipulation of spatial objects. Their formal foundation constitutes
a basis for practical query optimization. We describe several evaluation rules
tailored for geometric data and give the specification of an optimizer module
for spatial queries. Except for the latter module, the system has been fully
implemented upon the O2 DBMS, thus proving the effectiveness of a
constraint-based approach for the design of spatial database systems.