Realm-Based Spatial Data Types: The ROSE Algebra.

Ralf Hartmut Güting, Markus Schneider: Realm-Based Spatial Data Types: The ROSE Algebra. VLDB J. 4(2): 243-286(1995)

@article{DBLP:journals/vldb/GutingS95,
  author    = {Ralf Hartmut G{\"u}ting and
               Markus Schneider},
  title     = {Realm-Based Spatial Data Types: The ROSE Algebra},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {2},
  year      = {1995},
  pages     = {243-286},
  ee        = {db/journals/vldb/GutingS95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Spatial data types or algebras for database systems should (1) be fully general, that is, closed under set operations, (2) have formally defined semantics, (3) be defined in terms of finite representations available in computers, (4) offer facilities to enforce geometric consistency of related spatial objects, and (5) be independent of a particular DBMS data model, but cooperate with any. We present an algebra that uses realms as geometric domains underlying spatial data types. A realm, as a general database concept, is a finite, dynamic, user-defined structure underlying one or more system data types. Problems of numerical robustness and topological correctness are solved within and below the realm layer so that spatial algebras defined above a realm have very nice algebraic properties. Realms also interact with a DBMS to enforce geometric consistency on object creation or update. The ROSE algebra is defined on top of realms and offers general types to represent point, line, and region features, together with a comprehensive set of operations. It is described within a polymorphic type system and interacts with a DBMS data model and query language through an abstract object model interface. An example integration of ROSE into the object-oriented data model O2 and its query language is presented.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Realm, finite resolution, numerical robustness, topological correctness, geometric consistency, object model interface.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An4-1 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[Bancilhon 1989]: François Bancilhon: Query Languages for Object-Oriented Database Systems: Analysis and a Proposal. BTW 1989: 1-18
[Bancilhon et al. 1989]: François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O₂ Object-Oriented Database System. DBPL 1989: 122-138
[Bancilhon et al. 1992]: 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
[Becker & Güting 1992]: Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992)
[Bentley & Ottmann 1979]: Jon Louis Bentley, Thomas Ottmann: Algorithms for Reporting and Counting Geometric Intersections. IEEE Trans. Computers 28(9): 643-647(1979)
[Egenhofer et al. 1989]: Max J. Egenhofer, Andrew U. Frank, Jeffrey P. Jackson: A Topological Data Model for Spatial Databases. SSD 1989: 271-286
[Frank & Kuhn 1986]: ...
[Gargano et al. 1991]: M. Gargano, Enrico Nardelli, Maurizio Talamo: Abstract data types for the logical modeling of complex data. Inf. Syst. 16(6): 565-583(1991)
[Greene & Yao 1986]: Daniel H. Greene, F. Frances Yao: Finite-Resolution Computational Geometry. FOCS 1986: 143-152
[Güting 1988a]: Ralf Hartmut Güting: Geo-Relational Algebra: A Model and Query Language for Geometric Database Systems. EDBT 1988: 506-527
[Güting 1988b]: ...
[Güting 1989]: Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44
[Güting 1993]: Ralf Hartmut Güting: Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. SIGMOD Conference 1993: 277-286
[Güting et al. 1995]: Ralf Hartmut Güting, Thomas de Ridder, Markus Schneider: Implementation of the ROSE Algebra: Efficient Algorithms for Realm-Based Spatial Data Types. SSD 1995: 216-239
[Güting & Schneider 1993]: Ralf Hartmut Güting, Markus Schneider: Realms: A Foundation for Spatial Data Types in Database Systems. SSD 1993: 14-35
[Henrich et al. 1989]: Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53
[Joseph & Cardenas 1988]: Thomas Joseph, Alfonso F. Cardenas: PICQUERY: A High Level Query Language for Pictorial Database Management. IEEE Trans. Software Eng. 14(5): 630-638(1988)
[Lipeck & Neumann 1986]: Udo W. Lipeck, Karl Neumann: Modelling and Manipulating Objects in Geoscientific Databases. ER 1986: 67-85
[Nievergelt & Preparata 1982]: Jürg Nievergelt, Franco P. Preparata: Plane-Sweep Algorithms for Intersecting Geometric Figures. Commun. ACM 25(10): 739-747(1982)
[Orenstein & Manola 1988]: 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)
[O2 User's Manual 1993]: ...
[de Ridder 1994]: ...
[de Ridder 1995]: ...
[Roussopoulos et al. 1988]: Nick Roussopoulos, Christos Faloutsos, Timos K. Sellis: An Efficient Pictorial Database System for PSQL. IEEE Trans. Software Eng. 14(5): 639-650(1988)
[Schek & Weikum 1991]: Hans-Jörg Schek, Gerhard Weikum: Erweiterbarkeit, Kooperation, Föderation von Datenbanksystemen. BTW 1991: 38-71
[Scholl & Voisard 1989]: Michel Scholl, Agnès Voisard: Thematic Map Modeling. SSD 1989: 167-190
[Svensson & Huang 1991]: Per Svensson, Zhexue Huang: Geo-SAL: A Query Language for Spatial Data Analysis. SSD 1991: 119-140
[Tomlin 1990]: C. Dana Tomlin: Geographic Information Systems and Cartographic Modelling. Prentice-Hall 1990, ISBN 0-13-350927-3
[Voisard 1992]: ...

Referenced by

Eliseo Clementini, Paolino Di Felice: Spatial Operators. SIGMOD Record 29(3): 31-38(2000)
Luca Forlizzi, Ralf Hartmut Güting, Enrico Nardelli, Markus Schneider: A Data Model and Data Structures for Moving Objects Databases. SIGMOD Conference 2000: 319-330
Alberto Belussi, Elisa Bertino, Barbara Catania: An Extended Algebra for Constraint Databases. IEEE Trans. Knowl. Data Eng. 10(5): 686-705(1998)
Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
Peter A. Boncz, Annita N. Wilschut, Martin L. Kersten: Flattening an Object Algebra to Provide Performance. ICDE 1998: 568-577
Martin Erwig, Markus Schneider, Ralf Hartmut Güting: Temporal Objects for Spatio-Temporal Data Models and a Comparison of Their Representations. ER Workshops 1998: 454-465
Thodoros Topaloglou, John Mylopoulos: Representing Partial Spatial Information in Databases. ER 1996: 325-340
Jan Paredaens: Spatial Databases, The Final Frontier. ICDT 1995: 14-32
Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)