Keys and Superkeys: Formal Definitions

Defining a superkey

Let $R(X)$ be a relational schema, where $X$ is the set of attributes (columns) of $R$. Let $Z \subseteq X$ be a subset of those attributes.

$Z$ is a superkey for $R$ if, for any two records $u$ and $v$ in any valid instance of $R$:

$u[Z] = v[Z] \implies u[X] = v[X]$

In words: if two records agree on all attributes in $Z$, they must be the same record. No two distinct rows in a valid instance of $R$ can have identical values for all attributes in $Z$.

The entire set of attributes $X$ is trivially a superkey for any relation, since $u[X] = v[X]$ tautologically implies $u[X] = v[X]$.

Defining a key

$Z$ is a key (or candidate key) for $R$ if:

1. $Z$ is a superkey for $R$, and
2. No proper subset of $Z$ is a superkey for $R$.

The second condition is minimality: you cannot remove any attribute from $Z$ and still have a superkey. A key is a minimal superkey.

Notation

The notation $R(\underline{Z}, Y)$ indicates that $Z$ is a key for $R$, and that $R$‘s full set of attributes is $Z \cup Y$. The underline marks the key.

For a table with multiple candidate keys, one is designated as the primary key. The others remain alternate keys.

Example: Movies table

Schema: Movies(movie_id, title, year)

• $\{\text{movie\_id}\}$ is a superkey: no two movies share the same movie_id.
• $\{\text{movie\_id}\}$ is also a key: removing the only element leaves the empty set, which is not a superkey.
• $\{\text{movie\_id}, \text{title}\}$ is a superkey but not a key (it is not minimal: you can drop title).
• $\{\text{title}, \text{year}\}$ might be a key if we assume no two films share both title and year — but this is a design choice, not a formal guarantee.

Example: Directed table (all-key)

Schema: Directed(movie_id, person_id)

• $Z_1 = \{\text{movie\_id}\}$: not a superkey. A film can have multiple directors, so $u[\text{movie\_id}] = v[\text{movie\_id}]$ does not force $u = v$.
• $Z_2 = \{\text{person\_id}\}$: not a superkey. A person can direct multiple films.
• $Z_3 = \{\text{movie\_id}, \text{person\_id}\}$: is a superkey. A given (movie, person) pair appears at most once in the Directed relationship.
• $Z_3$ is also a key: neither subset alone is a superkey.
• No proper subset of $Z_3$ is a superkey, so $Z_3$ is minimal. This is an all-key table.

Example: People table

Schema: People(person_id, name, birthYear)

• $\{\text{person\_id}\}$ is a key (assuming synthetic keys).
• $\{\text{name}, \text{birthYear}\}$ might be a key if name+birthYear is unique — but it is not safe to rely on.

Multiple keys

A relation can have more than one key. A table of UK citizens might have both:

• $\{\text{ni\_number}\}$ (National Insurance number)
• $\{\text{person\_id}\}$ (synthetic key)

Both are keys (minimal superkeys), and either could be chosen as primary key. In practice, synthetic keys are preferred (see the note on synthetic keys in Lecture 2).

Formal property: every relation has a key

Since the set of all attributes $X$ is always a superkey, we can always find a key by starting with $X$ and iteratively removing attributes while the result remains a superkey. The resulting minimal subset is a key. In the worst case, $X$ itself is the only key (e.g., an all-key relationship table).

Superkey vs. key summary

Property	Superkey	Key
Uniquely identifies rows	Yes	Yes
Minimal	Not necessarily	Yes
$\text{all attributes}$ is one?	Always	Only if no proper subset is a superkey
A table can have many?	Yes	Yes

Connection to normalisation

The concept of a key becomes critical in normalisation (Lecture 5). A relation is in a normalised form if all non-key attributes are functionally dependent on the key — and no other set of attributes. This is a preview: the key is the anchor for all other data in the row.

Summary

• A superkey is any set of attributes that uniquely identifies rows.
• A key is a minimal superkey.
• $\{\text{all attributes}\}$ is always a superkey.
• All-key tables occur for many-to-many relationship tables.
• Every relation has at least one key.
• The key is the foundation of normalisation: all data should depend on the key, the whole key, and nothing but the key.