CalculusofRelations

Closures of Relations

A closure of a relation Rel is the most minimal relation with respect to some property Prop that contains the source relation Rel.

Thinking computationally, the closure operation takes a relation and adds the least number of relations needed so that the resulting relation fulfills the property Prop.

If we think about the relationship between any closure to the source relation Rel, one might note the following rule holds:

Extensivity

Rel ⊆ Closure(Rel)

Structural Interpretation

Closure (with respect to any property) contains the source relation as a subset.

Information Interpretation

Closure is more information rich than the source relation.

There are also two other neat properties closures have:

Idempotence

Closure(Closure(Rel)) = Closure(Rel)

Structural Interpretation

Applying a closure on a relation which already has closure results in the same relation.

Informational Interpretation

Repeated application of closure produces no new information.

Monotonicity

Rel1 ⊆ Rel2 => Closure(Rel1) ⊆ Closure(Rel2)

Structural Interpretation

Closure operation respects the underlying containment relations or that “the diagram commutes”.

Informational Interpretation

Information gained by applying a transitive closure on a subset SubRel C would be a subset of the one gained by applying it on its superset Rel C.

Note that since the closure property is extensive, once a closure relation is applied to a relation, one might need to apply the reverse process called kernel operation to make it acquire arbitrary desired properties. Otherwise, if closure operation is the only one we have in our repertoire, we would be left with operations that only increase the information but not reduce it. This aspect will be explored in a later outing in this blog post.