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