Modeling Topological Spatial Relations: Strategies for Query
Processing
Eliseo Clementini, Jayant Sharma, and
Max Egenhofer Computers and Graphics 18 (6): 815-822, 1994.
Abstract
This paper investigates the processing of spatial queries with
topological constraints, for which current database solutions are
inappropriate. Topological relations, such as disjoint, meet,
overlap, inside, and contains, have been well defined by the
9-intersection, a comprehensive model for binary topological
relations. We focus on two types of queries: (1) "Which objects
have a stated topological relation with a given spatial object?"
and (2) "What is the topological relation between two given spatial
objects?" Such queries are processed at two levels of detail.
First, Minimum Bounding Rectangles are used as an approximation of
the objects' geometry and as a means of identifying candidates that
might satisfy the query. Next, the nine intesections that determine
the topological relations between candidate pairs are calculated.
We present algorithms for minimizing these computations.
Considerable performance can be gained by exploiting the semantics
of spatial relations. We also compare the approach for a naive
cost model, which assumes that all relations have the same
frequency of occurrence, with a refined cost model, which
considers the probability of occurrence of the topological
relations. The strategies presented here have three key benefits:
(1) they are based on a well-defined formalism; (2) they are
customizable; and (3) they can take into account important
statistical information about the data.
Full article
Eliseo Clementini, 
Jayant Sharma, and
Max Egenhofer
