Spatial Data Types for Database Systems

Markus Schneider
Doctoral Thesis, FernUniversität Hagen, 1995

Abstract: In various application fields there is a need to manage and process geometric or spatial data, that is, data related to space. For this purpose spatial database systems are designed which are full-fledged database systems with additional capabilities for representing, querying, and manipulating spatial data. Such systems provide the underlying database technology needed to support applications such as geographical information systems. Spatial data types like point, line, and region provide a fundamental abstraction for modelling the structure of geometric entities, their relationships, properties, and operations. Their definition and implementation is probably the most fundamental issue in the development of spatial database systems. In this thesis we introduce a system of spatial data types, or a spatial algebra, which is called ROSE algebra and which avoids many of the deficiencies of current approaches. The development of the ROSE algebra consists of three steps:

The first step introduces the concept of a realm as a discrete geometric basis underlying one or more spatial data types. A realm is a finite set of points and non-intersecting line segments over a discrete grid and conceptually describes the complete underlying geometry of a particular application space in two dimensions. The idea is to construct the geometries of spatial objects by composing them from points or segments in the realm. As a basis for the design of spatial data types very often Euclidean space is used or implicitly assumed. A point in the plane is then represented by a pair of real numbers. Unfortunately, in practice there are no real numbers available in computers but only finite approximations. This leads to many problems in geometric computation. The realm concept solves these problems of numerical robustness and topological correctness below and within the realm layer. In particular, it solves the line segment intersection problem over a discrete grid and enforces geometric consistency of related spatial objects. Furthermore, it enables one to formally define quite general spatial data types or algebras on top of it that enjoy nice closure properties not only in theory but also in computational practice.

The second step deals with the formal definition of the ROSE algebra itself which is defined on top of realms and offers realm-based spatial data types to represent point, line, and region features in the plane together with a comprehensive set of spatial operations. The ROSE algebra has a number of interesting features: It (i) offers (values of) data types of a very general structure, (ii) has a complete formal definition of the semantics of types and operations, (iii) has realms as a discrete geometric basis which allows for a numerically correct and robust implementation of types and operations in terms of integer arithmetic, (iv) treats consistency between distinct spatial objects with common parts, and (v) has a general object model interface which allows it to cooperate with different kinds of database systems. Moreover, concepts of the ROSE algebra are used to formally define spatial objects with undetermined boundaries.

The third step relates to the ROSE system as an implementation of the ROSE algebra. This system realizes the algebra's types and operations by providing efficient data structures and new realm-based geometric algorithms defined over a discrete grid. The main techniques used are parallel traversal of objects, plane-sweep, and graph algorithms. All algorithms are analysed with respect to their worst case time and space requirements. Due to the realm properties, these algorithms are relatively simple, efficient, and numerically completely robust. In contrast to traditional work on algorithms, the focus is not on finding the most efficient algorithm for each single problem, but rather on considering a spatial algebra as a whole, and on reconciling the various requirements posed by different algorithms within a single data structure for each type.

(No full Postscipt version available. Printed copy available from the author on request.) 

Last change: October 21, 1998, Markus Schneider