Sets, and why a table is one

A set is an unordered collection of distinct things. Write it with curly braces.

Two marks to learn. $x\in S$ is said "x is in S", or "x is an element of S", and means that $x$ is one of the things in $S$. $x\notin S$ is said "x is not in S", and means it isn't. So $3\in S$ is true, and $4\notin S$ is true.

Two properties matter enormously later, and they are the reason a set is the right model for a database table.

Unordered. $\{2,3\}=\{3,2\}$. There is no first element.

No duplicates. $\{1,1,2\}$ is just $\{1,2\}$. An element is either in or out; it cannot be in twice.

The empty set is written $\varnothing$. It has nothing in it. It is not nothing — it is a perfectly good set that happens to be empty, the way an empty table is still a table.

Saying which things, instead of listing them

Listing works for four elements. It does not work for four million. So you describe the members by a condition.

Say it: the set of all x in S such that x is greater than 3. The colon means such that. You will also see a vertical bar, $\{x\in S\mid x>3\}$, meaning exactly the same thing.

The shape is always the same three parts: where the elements come from, a colon, and which ones you keep. With $S=\{2,3,5,7\}$ that set is $\{5,7\}$.

This is the `WHERE` clause. `SELECT * FROM S WHERE x > 3` and $\{x\in S:x>3\}$ are the same thought.

Size

$|S|$ is how many elements a set has — say the size of S, or the cardinality of S.

Put that together with the last section and you already have `COUNT`:

The number of elements of $S$ greater than 3. That is `SELECT COUNT(*) FROM S WHERE x > 3`.

One mark more: $A\subseteq B$, said A is a subset of B, means every element of $A$ is also in $B$. So $\{2,3\}\subseteq \{2,3,5,7\}$ is true, and $\{2,4\}\subseteq \{2,3,5,7\}$ is false.

Tuples, and the Cartesian product

A tuple is an ordered list of things, written with round brackets — $(1,\text{Ada},\text{Leeds})$. Unlike a set, order matters and duplicates are allowed: $(1,2)\ne (2,1)$. A tuple of two things is a pair, of three a triple, of $n$ things an n-tuple.

The Cartesian product $A\times B$, said A cross B, is the set of every pair you can make by taking one element from $A$ and one from $B$.

Note the size: $|A\times B|=|A|\cdot |B|$. Always. You can cross more than two, and $A\times B\times C$ is the set of all triples. This is the `CROSS JOIN`, and it is where the word relational comes from.

A table is a set of tuples

Here is the whole idea, and it is worth pausing on, because everything else is built on it.

A table with columns `(cust_id, name, city)`, where ids are integers and the other two are strings, is a subset of the product of its column domains:

Say it: Customer is a subset of the integers cross string cross string. That one line says every row is a triple; the first slot holds an integer and the other two hold strings; and the table holds some of the possible such triples, not all of them.

A relation is exactly that — a set of tuples. A table is a relation. That is the entire content of the phrase "relational database", and it is why the mathematics of sets applies to it without modification.

The running example

Everything from the third note onwards uses this tiny database. It is worth keeping to hand.

Customer has three rows: $(1,\text{Ada},\text{Leeds})$, $(2,\text{Bo},\text{Leeds})$ and $(3,\text{Cy},\text{Hull})$.

Order has three: $(10,1,\text{Jan 5})$, $(11,1,\text{Feb 11})$ and $(12,2,\text{Feb 14})$ — the second column is the customer.

Line has four: $(10,A,2,5.00)$, $(10,B,1,12.00)$, $(11,A,3,5.00)$ and $(12,C,1,40.00)$ — order, sku, quantity, unit price.

So $|\text{Customer}|=3$, $|\text{Order}|=3$ and $|\text{Line}|=4$. Note that Cy has no orders. He is deliberate, and he is how you will find out whether a formula is right.