A binary relation R on a set X is a subset of , i.e. is a set of ordered pairs (x,y) with We will speak of R as a relation instead of . The collection of all binary relations on X will be denoted by Rel(X).

Some important classes of binary relations over a set X are:

• reflexive:  x in X it holds that xRx.
• irreflexive:  it holds that not xRx.
• symmetric:  it holds that if xRy then yRx.
• antisymmetric:  it holds that if xRy and yRx then x = y.
• asymmetric:  it holds that if xRy then not yRx.
• transitive:  it holds that if xRy and yRz then xRz.
• functional:  it holds that if xRy and xRz then y=z.

If R is a binary relation over X, then each of the following are binary relations over X:

• Converse:  , defined as R^-1 = { (y, x) |}. A binary relation over a set is equal to its converse if and only if it is symmetric. Sometimes the term reverse is used as well. The converse of a surjective and injective function is called its inverse.
• Reflexive closure: R⁼, defined as R⁼ or the smallest reflexive relation over X containing R. This can seen to be equal to the intersection of all reflexive relations containing R.
• Transitive closure: R⁺, defined as the smallest transitive relation over X containing R. This can seen to be equal to the intersection of all transitive relations containing R.
• Transitive-reflexive closure: R^*, defined as R^* = ( R⁺) ⁼.

If R, S are binary relations over X, then each of the following are binary relations:

• Union:  , defined as .
• Intersection: , defined as  .

If R and S are binary relations over X, then the following is a binary relation over X as well:

• Composition:  is defined as .
• Weak composition:  is defined as , or informally the strongest relation  which contains .

Ternary Relations

A ternary relation on a set X is accordingly a subset of X×X×X, i.e. is a set of ordered pairs <x,y,z> with x,y,z ∈ X.

Permutations

Because we have three arguments, we have 3! = 6 possible ways of arranging the arguments for a transformation. Following Zimmermann and Freksa [ZF96] the following terminology and symbols refer to these permutations of the arguments (a,b : c):

An example for these binary operations can be found in [DM04].

With ternary relations, one can think of different ways of composing them. However there are only a few ways to compose them in a way such that it can be used for enforcing local consistency [SN01]. In the case of a real relation algebra, i.e. being closed under transformation and composition, e.g. the flip-flop calculus [IM99], we can enforce 4-consistency [IC00] using the following generalized scheme of strong composition  [MN03]: 

Unfortunately, some calculi as for example the TPCC calculus is not closed under strong composition. For that reason we can not directly enforce 4-consistency. But we can define a weak composition operation  of two relations r1 and r2. It is the most specific relation such that: .

[DM04]: F. Dylla and R. Moratz. Emprical complexity issues of practical qualitative spatial reasoning about relative position. In Proceedings of the Workshop on Spatial and Temporal Reasoning, ECAI 2004, 2004.

[IC00]: A. Isli and A. Cohn, Qualitative spatial reasoning: A new approach to cyclic ordering of 2d orientation, Artficial Intelligence 122:137-187, 2000

[IM99]: A. Isli and R. Moratz, Qualitative Spatial Representation and Reasoning: Algebraic Models for Relative Position, TechReport Universität Hamburg FBI-HH-M-284/99 M-284, 1999

[MN03]: R. Moratz, B. Nebel, and C. Freksa, Qualitative Spatial Reasoning about Relative Position: The Tradeoff between Strong Formal Properties and Successful Reasoning about Route Graphs. Spatial Cognition 2003: 385-400, 2003

[SN01]: A. Scivos and B. Nebel, Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation, Proc. COSIT-2001, Springer-Verlag, 2001

[ZF96]: K.Zimmermann and C. Freksa, Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge, Applied Intelligence, Volume 6, No.1, pp. 49-58, 1996.