The development of formalisms for spatial relations has been among
the most popular research topics in geographic databases during the
last five years. Countless conference proceedings in the areas of
spatial database systems and geographic information systems witness
the wide interest by computer scientists and GIS experts, and they
document the results of various approaches, philosophies, and
incremental improvements of a relatively small core of concepts.
These findings have advanced our knowledge of spatial data models
and they are now finding their way into commercial products (e.g.,
Oracle's Spatial Data Option) and standards (e.g., SQL3/MM and
SAIF). These recent developments provide a timely motivation for
assessing the state of the art in models for spatial relations and
for examining the potential applicability of advanced models for
spatial relations. This 2-hour tutorial will focus on formalisms of
and inferences about spatial relations.
All participants will get a workbook with all overheads, a survey paper that discusses most of the issues, and an extensive reference list.
The role and importance of spatial relations in geographic database systems, spatial query languages, and data exchange.
2. Models for Spatial Relations
After a short review of some early ad-hoc approaches to modeling spatial relations, we will focus on models derived from a comprehensive framework. We will also discuss the rationale for partitioning investigations of spatial relations into different types.
2.1 Topological Relations
This part will review the RCC model (Cohn et al.) and the 9-intersection (Egenhofer).
2.1.1 Models for regions
2.1.2 Generalizations to higher dimensional spaces
2.1.3 Generalized spatial objects
2.1.4 Detailed topological relations
2.2 Cardinal Directions
This part will focus on projection-based and cone-shaped models for cardinal directions (Peuquet, Frank, Freksa), including a review of such models as 2-D strings (Chang et al.) and symbolic arrays (Papadias et al.).
2.2.1 Between point objects
2.2.2 Between extended spatial objects
2.3 Approximate Distances
Will review the few models that have been developed for approximate distances (Frank, Hong, Hernández et al.).
2.4 Hybrid models
Some hybrid models have been proposed for spatial relations (Hernández, Papadias), which combine topology with direction, and we will compare them with the models introduced above.
3. Reasoning about Spatial Relations
These models for spatial relations are particularly useful as a foundation to make formal inferences. This part will review two aspects of reasoning about spatial relations: conceptual neighborhoods and composition.
3.1 Conceptual Neighborhoods
Conceptual neighborhoods capture the similarity among spatial relations. We will review conceptual neighborhood models for 1-dimensional intervals (Freksa), topological relations (Egenhofer), and cardinal directions (Hernández, Sharma).
3.2 Composition
Composition is the most common inference mechanism with relations. This section will focus on compositions for topological (Egenhofer) and direction (Frank) relations. We will also investigate composition models that combine approximate distances with direction relations (Frank, Hong, Hernández et al.), and topological relations with cardinal directions (Sharma).
4. Integration into Spatial Query Languages
The models and inference mechanisms form the basis for query processing. This part will review different approaches to the integration of spatial relations into query languages (e.g., van Oosterom) and the resulting syntax in the spatial part of SQL3/MM. We will also address concerns of query processing such as detecting inconsistencies in spatial queries, optimizing the calculation of 9-intersections, and processing topological queries over R-trees.
4.1 Syntax
4.2 Query Processing and Query Optimization
5. Conclusions and Applications of Spatial Relations
The formalisms for spatial relations enable new types of applications, and we will discuss some of them.
5.1 Qualitative Descriptions of Spatial Scenes
5.2 Relation-Based Similarity Assessment
5.3 Definition of Natural-Language Spatial Predicates
5.4 Integration of the Semantics of Graphical and Textual Spatial Descriptions