Relations
Previously, we explored the mathematical formalism of sets. Sets allow us to model collections of data. However, we frequently wish to capture relevant relationships in our data. Structured data is called as such because the data in the collection is related in some way. For example:
- An element precedes another element in a list.
- A person is friends with another person in a social network.
- One number is a divisor of another number.
To model structured data, we need some way of modeling these relationships between individual datum. In this chapter, we use sets to develop the theory of relations which will allow us to formally reason about these relationships.
Definitions and Notation
Intuitively, a relation relates two objects by some property as defined by the relation. To capture this correspondence we combine pairs with sets:
Definition (Relation): A relation \(R\) over a universe \(U\) is a subset of pairs of elements drawn from \(U\), i.e., \(R \in \mathcal{P}(U \times U)\).
Suppose we have a relation \(R\). An element of \(R\), \((a, b) \in R\) denotes that \(a\) and \(b\) are related by \(R\), which we can express in several different ways:
| Notation | Form |
|---|---|
| \((a, b) \in R\) | Set notation |
| \(R(a, b)\) | Function notation |
| \(a \; R \; b\) | Infix notation |
For example, let our universe \(U = \{\, \text{"Mary"}, \text{"Miguel"}, \text{"Li"}, \text{"Lana"} \,\}\). Then we can define a relation \(\mathsf{owes} : U ×\times U\) that captures whether one person owes another money. With this relation, the following expressions:
- \((\text{"Miguel"}, \text{"Li"}) \in \mathsf{owes}\).
- \(\mathsf{owes}(\text{"Miguel"}, \text{"Li"})\).
- \(\text{"Miguel"} \mathsf{owes} \text{"Li"}\).
All posit that Miguel owes Li money.
Note that because the order of a pair matters, these expressions do not automatically assert that Li owes Miguel money. We would need to include this fact separately: \((\text{"Li"}, \text{"Miguel"}) \in \mathsf{owes}\).
Operations Over Relations
Because we define relations in terms of sets, we can define our fundamental operations over relations using set-theoretic notation.
Domain and Range
First, we can project out the left-hand and right-hand elements of a relation, typically called the domain and range, respectively.
Definition (Domain): Let \(R\) be a relation. Define the domain of \(R\), written \(\mathrm{dom}(R)\), as:
\[ \mathrm{dom}(R) = \{\, x \mid \exists y \ldotp (x, y) \in R \,\}. \]
Definition (Range): Let \(R\) be a relation. Define the range of \(R\) as:
\[ \mathrm{range}(R) = \{\, y \mid \exists x \ldotp (x, y) \in R \,\}. \]
Alternatively, the range may also be called the codomain of the relation.
Example (Cardinality). Frequently, we may want to have the domain and range of a relation come from disparate sets \(S\) and \(T\). This is no problem for our definition of relation; we can simply define the universe to be the union of \(S\) and \(T\). Then our pairs are drawn from this union where the domain is always an element of \(S\) and the range is always an element of \(T\).
In this case, we can define a relation between sets \(S\) and natural numbers \(n\) where \(n\) is the number of elements in \(S\). We commonly call this the cardinality of a set. This is normally written \(|S| = n\), but to align with our relation notation, we can write \(\mathsf{card}(S, n)\) to denote this fact. For example:
- \((\{\, 1, 2, 3 \,\}, 3) \in \mathsf{card}\).
- \((\{\, a \,\}, 10) \notin \mathsf{card}\).
- \((\emptyset, 0) \in \mathsf{card}\).
Lifted Operations
Because relations are sets, we can lift any binary operation over sets to relations. As examples, let \(R\) and \(S\) be two relations. Then define the following lifted operations over sets to relations as:
\[\begin{align} R \cup S &= \{\, (a, b) \mid (a, b) \in R \vee (a, b) \in S \,\} \\ R \cap S &= \{\, (a, b) \mid (a, b) \in R \wedge (a, b) \in S \,\} \\ \overline{R} &= \{\, (a, b) \mid (a, b) \notin R \,\} \end{align}\]
Example (Relational Union): as a practical example of applying set-theoretic operations to relations, consider using relations to map items in a store to their stock, i.e., a relation whose domain is (abstract) objects and the codomain is natural numbers. We might have two different stores, with their own separate stocks of disparate items:
- \(R_1 = \{\, (a, 2), (b, 0), (c, 3) \,\}\).
- \(R_2 = \{\, (d, 1), (e, 5), (f, 0) \,\}\).
Then \(R_1 \cup R_2\) might represent joining together the stocks into a single store:
- \(R_1 \cup R_2 = \{\, (a, 2), (b, 0), (c, 3), (d, 1), (e, 5), (f, 0) \,\}\).
Transformations
Beyond lifted operations, we can also define several fundamental transformations over relations.
Definition (Inverse): Let \(R\) be a relation. Define the inverse of \(R\), written \(R^{-1}\), as:
\[ R^{-1} = \{\, (b, a) \mid (a, b) \in R \,\} \]
Definition (Composition): Let \(R\) and \(S\) be relations. Define the composition of \(R\) and \(S\), written \(S \circ R\) (LaTeX: \circ) as:
\[ S \circ R = \{\, (a, c) \mid (a, b) \in R, (b, c) \in S \,\} \]
Note that with composition that we “run the relation” from right-to-left, first through \(R\) and then through \(S\).
Definition (Image): Let \(R\) be a relation. Define the image of an element \(a\), written \(R(a)\), as:
\[ R(a) = \{\, b \mid (a, b) ∈ R \,\} \]
This final transformation is particularly useful when talking about functions which (we will discover shortly) are a special case of relations. In particular, note that if we have a function \(f\), then both the definition and notation of image coincides with “run the function”, \(f(x)\).