Chapter 10 of 30

Relations

"Asha is enrolled in DBMS." "City A has a direct flight to city B." "3 divides 12." "Function main calls function parse." Each sentence says that two things are related in some way. Unlike a function, a relation does not promise one partner per element: Asha may take three courses, and some city may have no flights at all.

Relations are everywhere in computer science. A relational database is literally a collection of relations; a directed graph is a relation on its vertices; "happens-before" in concurrency, "is a subclass of" in OOP and "depends on" in build systems are all relations. In the Functions chapter we saw functions as special subsets of A × B. In this chapter we drop the "exactly one image" condition and study relations in general: how to define them, represent them (pairs, matrices, digraphs), count them, and combine them (inverse, composition, powers). Properties such as reflexive, symmetric and transitive are the topic of the next chapter, Properties of Relations.


What Is a Relation?

A binary relation R from a set A to a set B is a subset of the Cartesian product A × B. If (a, b) ∈ R we write a R b and say "a is related to b". A relation on a set A is a relation from A to A, i.e. a subset of A × A.

That is the whole definition: a relation is just a set of ordered pairs. Any set of pairs at all, including ∅ (the empty relation) and A × B itself (the universal relation), is a relation.

Example 1: students and courses

A = {Asha, Ravi, Meena} (students), B = {DBMS, OS, CN} (courses), and

R = { (Asha, DBMS), (Asha, OS), (Ravi, OS), (Meena, CN) }

Asha is related to two courses, Ravi and Meena to one each. This is not a function A → B (Asha has two images), but it is a perfectly good relation.

Example 2: "divides" on A = {1, 2, 3, 4}

a R b ⟺ a divides b (b is a multiple of a).

R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }      |R| = 8

Example 3: relations defined by a rule on infinite sets

  • On ℤ: a R b ⟺ a < b. Then (2, 5) ∈ R but (5, 2) ∉ R.

  • On ℤ: a R b ⟺ a − b is divisible by 3 ("congruence mod 3"). Then (7, 1) ∈ R and (1, 7) ∈ R.

  • On the set of all strings: x R y ⟺ x is a prefix of y.

Domain and range of a relation

For R ⊆ A × B: the domain of R is { a | (a, b) ∈ R for some b } and the range is { b | (a, b) ∈ R for some a }. In Example 1, the domain is {Asha, Ravi, Meena} and the range is {DBMS, OS, CN}. (Some books use "domain" for all of A; check your syllabus.)

Relations versus functions

Question

Relation R ⊆ A × B

Function f : A → B

How many partners can an a ∈ A have?

Any number: 0, 1, 2, …

Exactly 1

Is it a set of pairs?

Yes

Yes (a special kind)

Matrix view

Any 0/1 matrix

Each row has exactly one 1

Number from A to B (|A| = m, |B| = n)

2mn

nm

Every function is a relation, but most relations are not functions.


Representing Relations

We use three standard representations. All of them carry exactly the same information.

1. Set of ordered pairs

As above. Good for definitions and proofs.

2. Zero-one matrix

For A = {a1, …, am} and B = {b1, …, bn}, the matrix MR is m × n with

M[i][j] = 1  if (a_i, b_j) ∈ R
M[i][j] = 0  otherwise

For the divides relation of Example 2 (rows and columns in the order 1, 2, 3, 4):

R

1

2

3

4

1

1

1

1

1

2

0

1

0

1

3

0

0

1

0

4

0

0

0

1

The number of 1s is |R| = 8. This is the same as the adjacency matrix of a graph, and it is how programs store dense relations.

3. Directed graph (digraph)

For a relation on a set A, draw one vertex per element and an arrow a → b for every pair (a, b) ∈ R. A pair (a, a) becomes a loop. The divides relation:

   (1) --------> (2) --------> (4)
    |                           ^
    +---------------------------+
    |
    +--------> (3)

 arrows: 1→2, 1→3, 1→4, 2→4
 plus a loop at every vertex: 1→1, 2→2, 3→3, 4→4

For a relation between two different sets A and B, draw A on the left, B on the right, and arrows across (a bipartite picture), just like the arrow diagram for functions.

Representation

Good for

Space for a relation on n elements

Set of pairs (edge list)

Proofs, sparse relations

proportional to |R|

0/1 matrix

Fast "is (a, b) in R?" checks, composition by matrix product

n² bits

Digraph

Seeing paths and cycles, property checks by eye

(a picture; in code it becomes an adjacency list)


Counting Relations

A relation from A to B is any subset of A × B. If |A| = m and |B| = n, then |A × B| = mn, and by the power set result from the Sets & Set Operations chapter:

number of relations from A to B  =  |P(A × B)|  =  2^(mn)
number of relations on A (|A| = n)  =  2^(n²)

Each of the mn possible pairs is independently "in" or "out", i.e. each cell of the matrix is independently 0 or 1.

Question

Answer

Relations from {a, b} to {1, 2, 3}

26 = 64

Relations on a 3-element set

29 = 512

Relations on a 3-element set that contain the pair (1, 2)

28 = 256 (one cell fixed to 1, eight free)

Relations on a 4-element set

216 = 65536

Relations on a 3-element set with exactly 2 pairs

C(9, 2) = 36

Counting relations that are reflexive, symmetric and so on is done in the Properties of Relations chapter.


Operations on Relations

Set operations

Since relations are sets, we can take ∪, ∩, −, ⊕ and complement (relative to A × B).

Example. On ℤ, let R be "<" and S be "=". Then

  • R ∪ S is "≤".

  • R ∩ S = ∅ (nothing is both less than and equal to).

  • The complement of R (in ℤ × ℤ) is "≥".

For relations on a finite set with n elements, |complement of R| = n² − |R|. In matrix form, ∪ is element-wise OR, ∩ is element-wise AND, and complement flips every bit.

Inverse (converse) relation

The inverse of R ⊆ A × B is R−1 = { (b, a) | (a, b) ∈ R } ⊆ B × A.

  • The inverse of "<" is ">". The inverse of "divides" is "is a multiple of". The inverse of "is a parent of" is "is a child of".

  • Matrix: MR−1 is the transpose of MR. Digraph: reverse every arrow.

  • (R−1)−1 = R, and |R−1| = |R|.

Unlike the inverse of a function, the inverse relation always exists. If R happens to be a function, R−1 is a function exactly when R is a bijection, which matches the Functions chapter.

Composition

If R ⊆ A × B and S ⊆ B × C, the composition S ∘ R ⊆ A × C is { (a, c) | there is some b ∈ B with (a, b) ∈ R and (b, c) ∈ S }.

Read S ∘ R as "first R, then S", the same order as g ∘ f for functions: (a, c) ∈ S ∘ R means you can walk from a to c by one R-step followed by one S-step.

Notation warning: some books write the same relation as R ∘ S or R ; S (left-to-right order). Always check how your textbook defines it. In this tutorial, S ∘ R means R first.

Example 4: students, courses, teachers

R (student → course) from Example 1, and S (course → teacher):

R = { (Asha, DBMS), (Asha, OS), (Ravi, OS), (Meena, CN) }
S = { (DBMS, K), (OS, S), (CN, K), (CN, S) }       K, S = two professors

S ∘ R relates a student to every professor who teaches one of the student's courses:

Asha  → DBMS → K       (Asha, K)
Asha  → OS   → S       (Asha, S)
Ravi  → OS   → S       (Ravi, S)
Meena → CN   → K       (Meena, K)
Meena → CN   → S       (Meena, S)

S ∘ R = { (Asha, K), (Asha, S), (Ravi, S), (Meena, K), (Meena, S) }

This is exactly what a SQL join on the course column followed by a projection computes.

Composition with matrices

If MR and MS are the matrices of R and S, then

M(S ∘ R) = M_R ⊙ M_S        (Boolean matrix product: R's matrix on the LEFT)

(M_R ⊙ M_S)[i][j] = OR over k of ( M_R[i][k] AND M_S[k][j] )

It is ordinary matrix multiplication with + replaced by OR and × replaced by AND. The entry is 1 exactly when some middle element k links ai to cj.

Properties of composition

  • Associative: T ∘ (S ∘ R) = (T ∘ S) ∘ R. Both mean "an R-step, then an S-step, then a T-step".

  • Not commutative: in general S ∘ R ≠ R ∘ S. ("Mother of a father" is a paternal grandmother; "father of a mother" is a maternal grandfather.)

  • Inverse of a composition: (S ∘ R)−1 = R−1 ∘ S−1.

  • Distributes over union: T ∘ (R ∪ S) = (T ∘ R) ∪ (T ∘ S).

  • Only ⊆ for intersection: T ∘ (R ∩ S) ⊆ (T ∘ R) ∩ (T ∘ S), and equality can fail.

Proof of the inverse rule. (c, a) ∈ (S ∘ R)−1 ⟺ (a, c) ∈ S ∘ R ⟺ ∃b [(a, b) ∈ R ∧ (b, c) ∈ S] ⟺ ∃b [(c, b) ∈ S−1 ∧ (b, a) ∈ R−1] ⟺ (c, a) ∈ R−1 ∘ S−1. ∎

Counterexample for intersection. On {1, 2, 3}, let R = {(1, 1)}, S = {(1, 2)}, T = {(1, 3), (2, 3)}. Then R ∩ S = ∅, so T ∘ (R ∩ S) = ∅. But T ∘ R = {(1, 3)} and T ∘ S = {(1, 3)}, so their intersection is {(1, 3)} ≠ ∅. The two routes from 1 to 3 go through different middle elements, and intersecting first destroys both.

We checked associativity, the inverse rule and distribution over union by brute force on 20,000 random triples of relations on a 3-element set (there are 512 such relations); all held.


Powers of a Relation

For a relation R on A, define R1 = R and Rn+1 = Rn ∘ R for n ≥ 1.

In the digraph, (a, b) ∈ Rn exactly when there is a path of length n (n arrows) from a to b. (Proof by induction on n, as in the Mathematical Induction chapter: a path of length n + 1 is a path of length n followed by one more arrow.)

Example 5

On A = {1, 2, 3, 4}, let R = {(1, 2), (2, 3), (3, 4), (2, 4)}.

  1 ──> 2 ──> 3 ──> 4
        |           ^
        +-----------+

R   = { (1,2), (2,3), (2,4), (3,4) }
R²  = { (1,3), (1,4), (2,4) }         1→2→3, 1→2→4, 2→3→4
R³  = { (1,4) }                        1→2→3→4
R⁴  = ∅                                no path has 4 arrows

Notice (2, 4) is in both R and R²: there is a direct arrow and also a 2-step path 2 → 3 → 4. The union R ∪ R² ∪ R³ ∪ … contains (a, b) whenever b is reachable from a; this is the transitive closure, which the Properties of Relations chapter studies (along with Warshall's algorithm to compute it).

Computing it in Python

def compose(R, S):
    """S o R: first R, then S.  (a, c) is in it when a R b and b S c for some b."""
    return {(a, c) for (a, b1) in R for (b2, c) in S if b1 == b2}

def inverse(R):
    return {(b, a) for (a, b) in R}

def matrix(R, rows, cols):
    return [[1 if (r, c) in R else 0 for c in cols] for r in rows]

def bool_product(M, N):
    n, m, p = len(M), len(N), len(N[0])
    return [[int(any(M[i][k] and N[k][j] for k in range(m))) for j in range(p)]
            for i in range(n)]

A = [1, 2, 3, 4]
R = {(1, 2), (2, 3), (3, 4), (2, 4)}

R2 = compose(R, R)
R3 = compose(R2, R)
R4 = compose(R3, R)
print("R   =", sorted(R))
print("R^2 =", sorted(R2))
print("R^3 =", sorted(R3))
print("R^4 =", sorted(R4))
print("R^-1 =", sorted(inverse(R)))

M = matrix(R, A, A)
print("M_R         =", M)
print("M_R (.) M_R =", bool_product(M, M))
print("matches R^2:", bool_product(M, M) == matrix(R2, A, A))

divides = {(a, b) for a in A for b in A if b % a == 0}
print("divides on A:", sorted(divides), "size", len(divides))

Output:

R   = [(1, 2), (2, 3), (2, 4), (3, 4)]
R^2 = [(1, 3), (1, 4), (2, 4)]
R^3 = [(1, 4)]
R^4 = []
R^-1 = [(2, 1), (3, 2), (4, 2), (4, 3)]
M_R         = [[0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0]]
M_R (.) M_R = [[0, 0, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
matches R^2: True
divides on A: [(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)] size 8

Note the argument order: compose(R, S) computes S ∘ R (R first), matching the mathematical definition.


n-ary Relations and Databases

An n-ary relation on sets A1, …, An is a subset of A1 × A2 × ⋯ × An. Its elements are n-tuples, and n is its degree (arity).

A table in a relational database is exactly an n-ary relation: each row is a tuple, each column (attribute) corresponds to one set Ai. E. F. Codd's relational model (1970) took the word "relation" directly from this mathematics.

Enrolment (degree 3) ⊆ RollNo × Course × Grade

RollNo | Course | Grade
-------+--------+------
  101  | DBMS   |  A
  101  | OS     |  B
  102  | OS     |  A
  103  | CN     |  C

Relational operation

Set-theory meaning

SQL idea

Selection σ

Keep the tuples satisfying a condition (a subset)

WHERE Grade = 'A'

Projection π

Keep only some coordinates of each tuple, removing duplicates

SELECT DISTINCT Course

Join ⋈

Combine tuples that agree on shared attributes (generalises composition)

JOIN … ON

Union, difference

Set union and difference of relations with the same columns

UNION, EXCEPT

Projecting the Enrolment table onto Course gives {DBMS, OS, CN}: three rows, not four, because a set has no duplicates. (Real SQL keeps duplicates unless you write DISTINCT, because SQL tables are really multisets.)


Common Mistakes

  • Thinking every relation must be a function. A relation may relate an element to many partners or to none.

  • Composing in the wrong order. In S ∘ R, R is applied first; in the matrix product, MR goes on the left.

  • Using ordinary arithmetic in the Boolean product. 1 + 1 must be 1 (OR), not 2.

  • Counting relations as 2n or n2. On an n-element set there are 2n² relations.

  • Taking the complement relative to A instead of A × B. The complement of R is (A × B) − R.

  • Assuming R2 ⊆ R. That only holds for transitive relations (next chapter); in Example 5, (1, 3) ∈ R² but (1, 3) ∉ R.


Interview and GATE-Style Questions

Q1. How many relations are there on a set with 4 elements? How many of them contain the pair (a, a) for one fixed element a?

216 = 65536 relations. Fixing one cell to 1 leaves 15 free cells: 215 = 32768.

Q2. Let A = {1, 2, 3}, R = {(1, 2), (2, 3), (3, 1)}. Find R², R³ and R−1.

R² = {(1, 3), (2, 1), (3, 2)} (follow two arrows around the triangle). R³ = {(1, 1), (2, 2), (3, 3)}, the identity relation, because three steps go all the way round. R−1 = {(2, 1), (3, 2), (1, 3)}, which happens to equal R².

Q3. R is a relation from A to B with |A| = 5, |B| = 4, and |R| = 7. How many pairs are in the complement of R? In R−1?

|A × B| = 20, so the complement has 20 − 7 = 13 pairs. R−1 has 7 pairs (it is a subset of B × A).

Q4. On the set of all people, let F = "is the father of" and M = "is the mother of" (x F y means x is the father of y). What is F ∘ M?

(x, z) ∈ F ∘ M means: x M y (x is the mother of y) and y F z (y is the father of z) for some y. So x is the mother of z's father: F ∘ M is "is the paternal grandmother of".

Q5. If MR and MS are n × n Boolean matrices, how many bit operations does computing MS∘R take with the direct method?

Each of the n² entries needs an OR of n ANDs, so about n³ operations (n² · (2n − 1) to be exact), the same as naive matrix multiplication.

Q6. True or false: (S ∘ R)−1 = S−1 ∘ R−1.

False in general. The correct rule reverses the order: (S ∘ R)−1 = R−1 ∘ S−1. (With S−1 ∘ R−1, the sets do not even fit together unless A = C.)


Summary

  • A binary relation from A to B is any subset of A × B; a relation on A is a subset of A × A.

  • Three representations: set of pairs, 0/1 matrix, digraph. They carry the same information.

  • There are 2mn relations from an m-set to an n-set, and 2n² on an n-set.

  • Relations support set operations, inverse (transpose the matrix, reverse the arrows) and composition (Boolean matrix product, MR on the left for S ∘ R).

  • Composition is associative, not commutative, and (S ∘ R)−1 = R−1 ∘ S−1.

  • Rn contains (a, b) exactly when there is a path of length n from a to b.

  • n-ary relations are database tables; selection, projection and join are set operations on them.

A relation is just a set of pairs, but the right pairs describe courses, flights, function calls and databases. The next chapter, Properties of Relations, classifies relations by how their pairs behave.