You are here

Brock TR # CS-05-01 Abstract

Relation algebras and their application in qualitative spatial reasoning    [PDF]
I. Düntsch, February 2005.

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is "pointless".

Relation algebras were introduced into temporal reasoning by Allen [1] and into spatial reasoning by Egenhofer and Sharma [32]. The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux [55]. In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.