Relation Composition

The composition of two relations creates a new relation by 'connecting' the first with the second. If in the first relation an element connects to an intermediate element, and in the second relation that intermediate connects to a third, then in the composition the first element connects to the third.

Formal Definition

In other words: first apply the S relation, then the R relation. If S connects a to b, and R connects b to c, then the composition (R ∘ S) connects a to c.

Example of Composition

Suppose we have two relations:

• S = "sibling of" relation among people.
• R = "child of" relation among people.

The R ∘ S composition gives who is my sibling's child – that is, my nephew/niece.

Properties

• Composition is not commutative: generally R ∘ S ≠ S ∘ R.
• Composition is associative: (R ∘ S) ∘ T = R ∘ (S ∘ T).
• Even if R and S are transitive, their composition is not necessarily transitive.

Further Example

Let S = { (1,2), (2,3) } and R = { (2,4), (3,5) }. Then the composition R ∘ S = { (1,4), (2,5) }, because 1 connects to 2 in S, 2 connects to 4 in R, so 1 connects to 4 in the composition; similarly, 2 connects to 3, and 3 connects to 5, so (2,5) is also in it.

Summary

Relation composition allows us to apply two different connections in sequence and thus create a new connection. This is a useful tool in mathematics and computer science, for example, in graph analysis, databases, and function examination.

Practice Exercise