 |
|
|
The DEDALE System for Complex Spatial Queries |
Full Paper (PDF)
|
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. |
References, where available, link to the DBLP on the World Wide Web.
[AS83]...
[BBC97]Alberto Belussi, Elisa Bertino, Barbara Catania:
Manipulating Spatial Data in Constraint Databases.
SSD 1997: 115-141[BCD89]François Bancilhon, Sophie Cluet, Claude Delobel:
A Query Language for the O2 Object-Oriented Database System.
DBPL 1989: 122-138[BDK92]François Bancilhon, Claude Delobel, Paris C. Kanellakis (Eds.):
Building an Object-Oriented Database System, The Story of O2.
Morgan Kaufmann 1992, ISBN 1-55860-169-4
Contents[BKSS90]Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331[Cod70]E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
CACM 13(6): 377-387(1970)[DGVG97]Freddy Dumortier, Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht:
On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases.
PODS 1997: 68-77[Fre87]Johann Christoph Freytag:
A Rule-Based View of Query Optimization.
SIGMOD Conference 1987: 173-180[Gae95]Volker Gaede:
Optimal Redundancy in Spatial Database Systems.
SSD 1995: 96-116[GK97]Stéphane Grumbach, Gabriel M. Kuper:
Tractable Recursion over Geometric Data.
CP 1997: 450-462[Gra93]Goetz Graefe:
Query Evaluation Techniques for Large Databases.
Computing Surveys 25(2): 73-170(1993)[GRS98]...
[GRSS97]Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin:
DEDALE, A Spatial Constraint Database.
DBPL 1997: 38-59[GS95]Ralf Hartmut Güting, Markus Schneider:
Realm-Based Spatial Data Types: The ROSE Algebra.
VLDB Journal 4(2): 243-286(1995)[GS97]Stéphane Grumbach, Jianwen Su:
Queries with Arithmetical Constraints.
TCS 173(1): 151-181(1997)[GST94]Stéphane Grumbach, Jianwen Su, Christophe Tollu:
Linear Constraint Query Languages: Expressive Power and Complexity.
LCC 1994: 426-446[Gut84]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[Güt89]Ralf Hartmut Güting:
Gral: An Extensible Relational Database System for Geometric Applications.
VLDB 1989: 33-44[Güt94]Ralf Hartmut Güting:
An Introduction to Spatial Database Systems.
VLDB Journal 3(4): 357-399(1994)[Her96]...
[Ja97]Jignesh M. Patel, Jie-Bing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy E. Hall, Karthikeyan Ramasamy, Roger Lueder, Curt Ellman, Jim Kupsch, Shelly Guo, David J. DeWitt, Jeffrey F. Naughton:
Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation.
SIGMOD Conference 1997: 336-347[KG94]...
[KKR90]Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz:
Constraint Query Languages.
PODS 1990: 299-313[KPV95]Bart Kuijpers, Jan Paredaens, Jan Van den Bussche:
Lossless Representation of Topological Spatial Data.
SSD 1995: 1-13[Mor89]...
[NHS84]Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
TODS 9(1): 38-71(1984)[OM88]Jack A. Orenstein, Frank Manola:
PROBE Spatial Data Modeling and Query Processing in an Image Database Application.
TSE 14(5): 611-629(1988)[PS85]...
[PVV94]Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht:
Towards a Theory of Spatial Database Queries.
PODS 1994: 279-288[RFS88]Nick Roussopoulos, Christos Faloutsos, Timos K. Sellis:
An Efficient Pictorial Database System for PSQL.
TSE 14(5): 639-650(1988)[Sam90]Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
[Sch86]...
[SFGM93]Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith:
The Sequoia 2000 Benchmark.
SIGMOD Conference 1993: 2-11[SGR96]...
[SRF87]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518[SV89]Michel Scholl, Agnès Voisard:
Thematic Map Modeling.
SSD 1989: 167-190[Tom90]...
[Ube94]Michael Ubell:
The Montage Extensible DataBlade Achitecture.
SIGMOD Conference 1994: 482[Ull88]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
[Ull89]Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
|
@inproceedings{DBLP:conf/sigmod/GrumbachRS98,
author = {St{\'e}phane Grumbach and
Philippe Rigaux and
Luc Segoufin},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {The DEDALE System for Complex Spatial Queries},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {213-224},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
