Mathematical Relations

Codd’s radical idea

In the 1970s, Edgar Codd proposed a simple but powerful idea: give users a model of data and a language for manipulating that data which is completely independent of the details of its representation and implementation. This model is based on mathematical relations.

By separating the logical view of data from the physical storage, Codd’s relational model decouples development of the DBMS from the development of database applications. Users query the database in terms of the relations they see; the DBMS decides how to execute those queries on whatever storage structures it uses internally.

Cartesian products

Let $S$ and $T$ be sets. The Cartesian product of $S$ and $T$ is:

$S \times T = \{(s, t) \mid s \in S, t \in T\}$

That is, the set of all ordered pairs where the first element comes from $S$ and the second from $T$.

Example.

$\{A, B\} \times \{3, 4, 5\} = \{(A, 3), (A, 4), (A, 5), (B, 3), (B, 4), (B, 5)\}$

Six pairs total, since $|S \times T| = |S| \times |T| = 2 \times 3 = 6$.

Binary relations

A binary relation over $S \times T$ is any set $R$ with:

$R \subseteq S \times T$

That is, a relation is simply a subset of the Cartesian product. In the example above, one possible relation is:

$R = \{(A, 3), (B, 4), (B, 5)\}$

This particular $R$ contains three of the six possible pairs. There is no requirement that every element of $S$ or $T$ appears in $R$, nor that any particular pairing pattern holds.

Domains and database relations

In database parlance, the sets $S$ and $T$ are referred to as domains. A domain is the set of all possible values that a given column may take (the type of the column).

We are interested in finite relations $R$ that are explicitly stored in the database. This distinguishes database relations from mathematical relations studied in logic, such as those arising from integer linear programming constraints, where relations may be infinite or defined by a predicate rather than explicitly enumerated.

Why finite relations?

A database stores a finite number of rows. The relational model is grounded in set theory, but the sets we work with are finite and explicit — we can inspect every tuple, insert and delete tuples, and compute results by applying operations to the tuples themselves. The theory of relational algebra (covered in later notes) relies on relations being sets of known tuples.

Summary

• Codd’s relational model separates the logical model of data from physical implementation.
• A Cartesian product $S \times T$ is the set of all ordered pairs from $S$ and $T$.
• A binary relation over $S \times T$ is any subset $R \subseteq S \times T$.
• In databases, $S$ and $T$ are called domains; relations are finite and explicitly stored.