DEDALE - Reports and publications
Publications
- Philippe Rigaux, Michel Scholl, Luc Segoufin, Stephane Grumbach,
Building a Constraint-Based Spatial Database System: Model, Languages, and Implementation. Information Systems 28(6) pp 563-595, 2003
Abstract
This paper presents dedale, a spatial
database system which provides an abstract and non-specialized data model and
query language for representating and manipulating geometric data in arbitrary
dimension. dedale relies on a logical model based on linear constraints. The
main features of the constraint model are (1) a uniform representation of all
sorts of data, including geometric, spatio-temporal or elevation data, (2) an
algebraic query language whose formal foundations constitute a basis for
practical query optimization. We show the practical relevance of the approach
by describing an implementation which builds on standard technology for data
storage, database indexing and on the parsing and optimization of SQL. dedale
validates the linear constraint model over various applications, proposes a
user query language based on SQL which allows to query the database in a purely
declarative way, and gives some first steps towards query optimization. We
believe that this experience is a fruitful step toward sound and consistent
database models which hide the complexity of arbitrary geometric data, while
keeping manipulation languages intuitive and efficient.
- S. GRUMBACH, P. RIGAUX, Luc Segoufin,
Manipulating Interpolated Data is Easier than You Thought. VLDB'00
Abstract
Data defined by interpolation is frequently found in new applications
involving, for instance, geographical concepts, moving objects, and
spatio-temporal data. This data leads to potentially infinite collections of
items, (e.g. the elevation of any point in a map), whose definition is based
on the association of a collection of samples with an interpolation
function. We first argue that the manipulation of the data through direct
access to the samples and interpolation functions easily leads
to cumbersome or inaccurate queries. We therefore suggest hiding the
samples and the interpolation function away from the logical level, and
letting the system manipulate them at the physical level.
We propose to model such data conceptually using infinite relations (e.g.
the map with elevation yields an infinite ternary relation) which can be
manipulated through standard relational query languages (e.g. SQL), with no
mention of the interpolated definition. This approach is simple and
establishes a clear separation between logical and physical levels. It
requires standard relational query languages whose semantics is
well-defined. Moreover, we show that the evaluation of queries, which
includes the computation of the sampling collection and the interpolation
function of the output, can be done very efficiently, and we describe the
physical level algorithms. We show that
this approach can be easily supported by standard database techniques, and
demonstrate this with a prototype.
- S. GRUMBACH, P. RIGAUX, Luc Segoufin,
On the Orthographic Dimension of Constraint Databases. ICDT 1999
Abstract
The complexity of querying constraint databases by standard
means such as first-order queries
depends badly (roughly speaking
exponentially) upon the dimension of the data.
A precise analysis of the
trade-off between the dimension of the input data and the complexity of the
queries reveals that the complexity strongly depends upon the
use the input makes of
its dimensions. We introduce the concept of orthographic dimension, which,
for an object O, corresponds to the dimension of the (component)
objects O1,...,O_n, such that O=O1 X ... X On.
We study properties of databases with bounded
orthographic dimension in a general
setting of o-minimal structures, and provide a syntactic characterization of
first-order orthographic dimension preserving queries.
The main result of the paper concerns linear constraint databases.
In the context of linear constraint databases, we prove
that orthographic dimension preserving Boolean combination of conjunctive
queries, can be evaluated independently of the global dimension,
with operators limited to the orthographic dimension, in parallel
on the components.
This
results in an extremely efficient optimization mechanism, very easy to use in
practical applications.
- S. GRUMBACH, P. RIGAUX, Luc Segoufin,
Spatio-Temporal Data Handling with Constraints. ACM-GIS
Abstract
Most spatial information systems are limited to a fixed
dimension (generally 2) which is not extensible.
On the other hand, the emerging paradigm of constraint databases
allows the representation of data of arbitrary dimension, together
with abstract query
languages. The complexity of evaluating queries though might be costly
if the dimension of the objects is really arbitrary.
In this paper, we present a data model, based on linear constraints,
dedicated to the representation
and manipulation of multidimensional data.
In order to preserve a low complexity for query evaluation,
we introduce the orthographic dimension of an object O,
as the dimension of the components O1,...,On, such that
O=O1 X ... X On. This allows to process
queries independently on each component, therefore achieving a
satisfying trade-off between design simplicity, expressive power of
the query language and efficiency of query evaluation.
We illustrate these concepts in the context of spatio-temporal
databases where space and time are the natural components.
This data model has been implemented in the DEDALE system and a
spatio-temporal application, with orthographic dimension 2, is currently
running, thus showing the practical relevance of the approach.
-
S. GRUMBACH, P. RIGAUX, Luc Segoufin
The DEDALE System for Complex Spatial Queries. In Proc. Intl. Conf. on the Management of data (SIGMOD'98). A longer version
of this paper is availiable here
Abstract
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. 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.
- S. GRUMBACH, P. RIGAUX, M. SCHOLL, Luc Segoufin,
Dedale : A Spatial Constraint Database. In Proc. Intl. Workshop on Database
programming Languages (DBPL'97), Estes Park, Colorado, USA.
Abstract
This paper presents a first prototype of a constraint database for
spatial information, DEDALE. Implemented on top of the O2
DBMS, data is stored in an object-oriented framework, with spatial
data represented using linear constraints over a dense domain. The
query language is the standard OQL, with special functions for
constraint solving and geometric operations.
A simple geographical application from the French Institute for
Geography, IGN, is running on DEDALE. The data initially in vector
mode was loaded into the database after a translation to constraint
representation. Although it is too early to speak of performance
since not all operations have been optimized yet, our experience
with DEDALE demonstrates already the advantages of the constraint
approach for spatial manipulation.
Technical Reports
The current available reports describe (possibly in french) some particular
part of the DEDALE implementation.