Jose Antonio Cotelo Lema and Ralf Hartmut Güting
Praktische Informatik IV, Fernuniversität Hagen
D-58084 Hagen, Germany
{Jose-Antonio.Cotelo-Lema,
gueting}@fernuni-hagen.de
Abstract: Systems of spatial data types and operations, or spatial algebras, are fundamental for the implementation of spatial database systems. Several designs of such algebras have been proposed in the last decade, and recently commercial DBMS offer such algebras in the form of extension packages (e.g. ``data blades''). However, actual implementations are generally severely restricted when compared to designs in the literature. A main reason is that at the implementation level one cannot further ignore the problems of robustness and topological correctness arising from the discrete number representations used in computers. Therefore, implemented packages either avoid ``problematic'' operations, or accept inconsistencies and topological errors in the answers of queries due to rounding effects.
The ROSE algebra, proposed and implemented earlier, goes a long way towards avoiding such problems, since it was defined from scratch with robustness problems in mind. It is founded on a discrete geometric basis called a realm. The ROSE algebra guarantees a correct behavior of operations and has an entirely robust implementation. Unfortunately, the realm concept and its interaction with DBMS are difficult to implement, and certain kinds of topological problems still remain.
In this paper we introduce the concept of dual grid, which provides a new approach for the representation of spatial information that avoids any robustness and topological correctness problem and allows a less restrictive implementation of spatial algebras. As an example, we show how can it be used for implementing the ROSE algebra without realms, and show that such an implementation does not suffer from the side effects and disadvantages of the original realm-based one.
Keywords: spatial database, spatial data types, finite resolution, numerical robustness, topological correctness, geometrical consistency, realm, ROSE algebra, dual grid