5.1 Binary Relations: Properties, Composition, and Closure

Users following users, tasks depending on tasks, services calling services, these can all be modeled as ordered pairs of objects. Relation theory doesn’t introduce a new data format; instead, it offers a language for assessing structural properties: does the relationship contain cycles? Is it reversible? Can it propagate across multiple steps?

Relations are subsets of Cartesian products

A binary relation R from set A to set B:

R ⊆ A×B

If (a,b)∈R, we write:

a R b

Example:

Users={alice,bob}
Projects={atlas,compiler}

Owns={
  (alice,atlas),
  (bob,compiler)
}

Owns represents only a subset of all possible user–project pairs.

Domain and range of a relation:

dom(R)={a∈A | ∃b∈B, aRb}
ran(R)={b∈B | ∃a∈A, aRb}

These may not equal the declared A and B. It's possible that some users own no projects, or that some projects have no assigned owner.

Inverse Relation

Swap the positions of each ordered pair:

R⁻¹ = {(b,a) | aRb}

If Owns(user,project), the inverse relation can be read as OwnedBy(project,user). The inverse relation does not imply that an operation is reversible; it only indicates that the direction of the pairing has been reversed.

(R⁻¹)⁻¹ = R

Relation Composition

Let:

R ⊆ A × B
S ⊆ B × C

The composed relation S∘R⊆A×C is defined as:

a (S∘R) c ⇔ ∃b∈B (aRb ∧ bSc)

Example: A user belongs to a team, and a team owns a repository:

MemberOf ⊆ User × Team
Owns     ⊆ Team × Repo

Owns∘MemberOf ⊆ User × Repo

The intermediate object Team is connected by an existential quantifier. The composition order mirrors function composition: first traverse R, then S, denoted as S∘R. Different textbooks and database systems may use alternative notations; clarify the convention before use.

Relation composition satisfies the associative law:

T∘(S∘R) = (T∘S)∘R

But it generally does not satisfy the commutative law.

Properties of Relations on Sets

We assume R⊆A×A.

Reflexive and Irreflexive

Reflexive:  ∀a∈A, aRa
Irreflexive: ∀a∈A, ¬aRa

≤ is reflexive, < is irreflexive. A relation might also be neither reflexive nor irreflexive.

These properties depend on the underlying set. On an empty set, the empty relation is both reflexive and irreflexive because both universal statements hold vacuously; on a nonempty set, they cannot both hold.

Symmetric, Antisymmetric, and Asymmetric

Symmetry:  aRb → bRa
Antisymmetric: (aRb ∧ bRa) → a = b
Asymmetric: aRb → ¬bRa

Antisymmetry does not mean “not symmetric.” Equality is both symmetric and antisymmetric; the empty relation can also satisfy both properties. Asymmetry implies irreflexivity.

"Same version" is a symmetric relation; set containment ⊆ is an antisymmetric relation; strict less than < is an asymmetric relation.

Transitivity

(aRb ∧ bRc) → aRc

≤ and “is an ancestor of” are transitive; “directly depends on” is generally not transitive, because if A directly depends on B and B directly depends on C, it does not mean A directly depends on C. Only its transitive closure represents "direct or indirect dependency".

Graph and Matrix Representation

Relations on a finite set can be represented as directed graphs: elements are vertices, and aRb is an edge from a→b.

Alternatively, a 0-1 adjacency matrix can be used:

M[i,j]=1 ⇔ a_i R a_j

This leads to the following properties:

• Reflexivity corresponds to all diagonal entries being 1;
• Symmetry corresponds to M=Mᵀ;
• Relation composition corresponds to Boolean matrix multiplication;
• Path reachability corresponds to the transitive closure.

Boolean matrix multiplication uses ∧ in place of multiplication and ∨ in place of addition:

(M⨀N)[i,k]=∨_j (M[i,j] ∧ N[j,k])

This expresses "there exists an intermediate node j".

With source rows and destination columns, M_R⨀M_S follows R then S, representing S∘R. Function composition reads right to left, while this path-matrix product follows edges left to right. Ordinary integer matrix multiplication counts intermediate paths and need not produce only 0 or 1.

Closures: Adding the Minimal Necessary Pairs

The closures below are the smallest relations containing R with the specified property, ordered by inclusion. Such an edge-adding operation does not exist for every property: if R already contains aRb,bRa with a≠b, adding edges cannot make it antisymmetric.

• Reflexive closure: add all pairs of the form (a,a);
• Symmetric closure: add the reverse of every edge, i.e., R∪R⁻¹;
• Transitive closure: add all pairs that are reachable via a path of length at least 1, commonly denoted R⁺;
• Reflexive transitive closure: includes paths of length zero as well, commonly written R*.

Given a dependency graph:

A→B, B→C

the transitive closure also includes A→C. It does not arbitrarily introduce "direct dependencies," but instead constructs a new "reachability" relationship.

For finite graphs, the closure can be computed using Floyd–Warshall, repeated search, or bitset optimization. The choice of algorithm depends on the graph's density, query frequency, and whether the graph is dynamically updated.

This Python 3 implementation uses Warshall’s Boolean update. Vertices must be unique and every edge endpoint must belong to the vertex set. After processing k, the matrix includes paths whose internal vertices come from the processed set; after all vertices, it represents R⁺:

def transitive_closure(vertices, edges):
    vertices = tuple(vertices)
    reach = {(u, v): (u, v) in edges for u in vertices for v in vertices}
    for k in vertices:
        for i in vertices:
            for j in vertices:
                reach[i, j] = reach[i, j] or (reach[i, k] and reach[k, j])
    return {pair for pair, present in reach.items() if present}

vertices = ("A", "B", "C", "D")
edges = {("A", "B"), ("B", "C")}
plus = transitive_closure(vertices, edges)
star = plus | {(v, v) for v in vertices}
print(sorted(plus - edges))       # [('A', 'C')]
print(("D", "D") in plus, ("D", "D") in star)  # False True
cycle = transitive_closure(("A", "B"), {("A", "B"), ("B", "A")})
print(("A", "A") in cycle)      # True

R⁺ can contain self-pairs: a positive-length cycle produces (a,a). R* also adds zero-length paths for isolated vertices. This implementation uses Θ(|V|³) Boolean updates and Θ(|V|²) storage and is intended for small static graphs.

Database Relationships Shouldn't Be Analogized Just by Name

A relation in the relational model can be viewed as a set of tuples satisfying attribute type constraints; a typical binary relation is simply a set of binary tuples. SQL tables also involve duplication, NULL, keys, and physical storage. Therefore:

• Mathematical relations help understand joins and projections;
• The actual semantics of SQL must be referenced to bags and three-valued logic;
• Foreign keys express referential constraints, not automatically enforcing transitivity or symmetry in business relationships.

Completion Check

Given a relation on A={1,2,3}:

R={(1,1),(1,2),(2,3),(3,3)}

1. Compute dom(R), ran(R), and R⁻¹;
2. Determine whether the relation is reflexive, irreflexive, symmetric, antisymmetric, or transitive;
3. Write the symmetric closure;
4. List the pairs added to form the transitive closure;
5. Represent the service call graph as an adjacency matrix, and explain the significance of a nonzero entry in the matrix square.

References

• MIT Mathematics for Computer Science