dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

The DEDALE System for Complex Spatial Queries.

Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
@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-995-5},
  pages     = {213-224},
  ee        = {http://doi.acm.org/10.1145/276304.276324},
  crossref  = {DBLP:conf/sigmod/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ... Online Version (ACM WWW Account required): Full Text in PDF Format

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Laura M. Haas, Ashutosh Tiwary (Eds.): SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. ACM Press 1998, ISBN 0-89791-995-5 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 27(2), June 1998
Contents

Online Edition: ACM SIGMOD

[Abstract]
[Full Text (Postscript)]

References

[AS83]
...
[BBC97]
Alberto Belussi, Elisa Bertino, Barbara Catania: Manipulating Spatial Data in Constraint Databases. SSD 1997: 115-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BCD89]
François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O2 Object-Oriented Database System. DBPL 1989: 122-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cod70]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre87]
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gae95]
Volker Gaede: Optimal Redundancy in Spatial Database Systems. SSD 1995: 96-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GK97]
Stéphane Grumbach, Gabriel M. Kuper: Tractable Recursion over Geometric Data. CP 1997: 450-462 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GRS98]
...
[GRSS97]
Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS95]
Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB J. 4(2): 243-286(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS97]
Stéphane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. Theor. Comput. Sci. 173(1): 151-181(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GST94]
Stéphane Grumbach, Jianwen Su, Christophe Tollu: Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994: 426-446 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GŁt89]
Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GŁt94]
Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Her96]
...
[Ja97]
Jignesh M. Patel, Jie-Bing Yu, Navin Kabra, Kristin Tufte, Biswadeep Nag, Josef Burger, Nancy E. Hall, Karthikeyan Ramasamy, Roger Lueder, Curt J. Ellmann, 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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KG94]
...
[KKR90]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KPV95]
Bart Kuijpers, Jan Paredaens, Jan Van den Bussche: Lossless Representation of Topological Spatial Data. SSD 1995: 1-13 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mor89]
...
[NHS84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OM88]
Jack A. Orenstein, Frank Manola: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PS85]
...
[PVV94]
Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RFS88]
Nick Roussopoulos, Christos Faloutsos, Timos K. Sellis: An Efficient Pictorial Database System for PSQL. IEEE Trans. Software Eng. 14(5): 639-650(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sam90]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sch86]
...
[SFGM93]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SGR96]
...
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SV89]
Michel Scholl, Agnès Voisard: Thematic Map Modeling. SSD 1989: 167-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tom90]
...
[Ube94]
Michael Ubell: The Montage Extensible DataBlade Achitecture. SIGMOD Conference 1994: 482 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:17 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page