Self-Assessment Quiz: Relations

Twenty questions to check your understanding of representations, the four properties, equivalence relations and partitions, closures, and the relational model. Answer before opening the key. Aim for 16+.

Question 1

A binary relation from $A$ to $B$ is, by definition:

A) a function $f\colon A \to B$ B) a subset of the Cartesian product $A \times B$ C) a list of all elements in $A$ and $B$ D) a pairing in which every element of $A$ appears exactly once

Question 2

Which is true of every function $f\colon A \to B$ viewed as a relation $R_f \subseteq A \times B$?

A) every $a \in A$ appears in exactly one pair of $R_f$ B) every $a \in A$ appears in at least two pairs of $R_f$ C) $R_f$ is automatically symmetric D) $R_f$ is automatically reflexive

Question 3

In the adjacency matrix of a relation on a finite set, "reflexive" appears as:

A) the matrix equals its transpose B) every row sums to 1 C) the main diagonal is all $1$s D) the matrix is all $1$s

Question 4

A relation's directed graph has a self-loop on some but not all nodes. The relation is:

A) reflexive B) symmetric C) not reflexive D) transitive

Question 5

Which relation on $\{1, 2, 3\}$ is symmetric but not transitive?

A) $\{(1,1),(2,2),(3,3)\}$ B) $\{(1,2),(2,1),(2,3),(3,2)\}$ C) $\{(1,2),(2,3),(1,3)\}$ D) $\{(1,1)\}$

Question 6

"$\le$" on $\mathbb{Z}$ has exactly which combination of the four properties?

A) reflexive, symmetric, transitive B) reflexive, antisymmetric, transitive C) symmetric, antisymmetric, transitive D) reflexive, symmetric, antisymmetric

Question 7

Which statement about "symmetric" and "antisymmetric" is correct?

A) they are logical negations of each other B) a relation cannot be both C) a relation can be both, neither, or exactly one D) every reflexive relation is antisymmetric

Question 8

An equivalence relation is a relation that is:

A) reflexive, antisymmetric, and transitive B) reflexive, symmetric, and transitive C) symmetric and transitive only D) antisymmetric and transitive

Question 9

The equivalence class $[a]$ of an element $a$ under an equivalence relation $R$ on $A$ is:

A) $\{x \in A \mid (a, x) \in R\}$ B) $\{a\}$ always C) the set of all pairs containing $a$ D) the whole set $A$

Question 10

"Congruent mod $n$" on $\mathbb{Z}$ has how many distinct equivalence classes?

A) infinitely many B) $n$ C) $n - 1$ D) $2^n$

Question 11 (True/False, justify)

True or false: The equivalence classes of an equivalence relation on $A$ always form a partition of $A$. Justify in one sentence.

Question 12 (True/False, justify)

True or false: Two equivalence classes of the same relation can overlap without being equal. Justify in one sentence.

Question 13

The transitive closure of a relation $R$ on a finite set is best described as:

A) $R$ with all self-loops added B) $R$ with every reverse pair added C) the reachability relation: $(a, b)$ is in it iff there is a path of length $\ge 1$ from $a$ to $b$ D) the smallest equivalence relation containing $R$

Question 14

Why does computing the transitive closure by "add all missing shortcuts" sometimes need more than one pass?

A) the set of pairs is infinite B) adding shortcuts can create new two-step paths that need their own shortcuts C) the algorithm is randomized D) it never needs more than one pass

Question 15

The symmetric closure of $R$ is obtained by adding:

A) the diagonal $\{(a,a) \mid a \in A\}$ B) the reverse $\{(b,a) \mid (a,b) \in R\}$ C) all shortcuts for two-step paths D) every possible pair

Question 16

In the relational model, a database JOIN ... ON corresponds to:

A) a projection B) a Cartesian product followed by a selection C) a union D) a transitive closure

Question 17

A PRIMARY KEY constraint on a column asserts that the projection onto that column is:

A) surjective B) injective C) reflexive D) transitive

Question 18

A CROSS JOIN of a 200-row table and a 30-row table produces how many rows?

A) 230 B) 170 C) 6000 D) 100

Question 19 (Short answer)

State the three conditions a collection of subsets of $A$ must satisfy to be a partition of $A$.

Question 20 (Short answer)

In one sentence, explain why "the equivalence-relation/partition correspondence is a bijection" means that choosing one is the same as choosing the other.

Answer Key

Q Ans Note
1 B A relation is a subset of $A \times B$ — the entire definition (§12.1).
2 A A function is the special relation where each input appears in exactly one pair.
3 C Reflexive ⇔ all $(a,a) \in R$ ⇔ diagonal all $1$s.
4 C Reflexivity needs the loop on every node; some-but-not-all is non-reflexive.
5 B Every arrow has its reverse (symmetric) but $(1,2),(2,3)$ lack $(1,3)$ (not transitive).
6 B $\le$ is reflexive, antisymmetric, transitive — a partial order (Ch. 13); not symmetric.
7 C They live on different axes; equality is both, $\{(1,2),(2,1),(2,3)\}$ is neither.
8 B Equivalence = reflexive + symmetric + transitive (a generalized equality).
9 A $[a]$ is everything related to $a$.
10 B The $n$ residue classes $[0], [1], \dots, [n-1]$.
11 True Reflexivity gives non-empty/covering; overlap-implies-equal gives disjointness (§12.4 theorem).
12 False Distinct classes are disjoint; if they share any element they are the same set.
13 C Transitive closure = reachability via paths of length $\ge 1$.
14 B The cascade: new shortcuts create new paths; iterate until a pass adds nothing.
15 B Symmetric closure unions in the transpose (reverse of every pair).
16 B A join is the Cartesian product filtered by the ON selection.
17 B A key asserts distinct rows project to distinct key-tuples — injectivity (§12.6).
18 C $200 \times 30 = 6000$ — the size of the full Cartesian product.
19 — Blocks non-empty; pairwise disjoint; union is all of $A$.
20 — Every equivalence relation yields exactly one partition (its classes) and vice versa, so the two sets of objects are in one-to-one correspondence.

Topics to review by question

Questions Topic
1–2 Relations as sets of pairs; functions as special relations (§12.1)
3–4, 7 Properties as matrix/digraph patterns; symmetric vs. antisymmetric (§12.2–12.3)
5–6 Classifying a relation by the four properties (§12.3)
8–12, 19–20 Equivalence relations, classes, and the partition correspondence (§12.4)
13–15 Closures, especially transitive closure and the cascade (§12.5)
16–18 The relational model: join, key, Cartesian product (§12.6)