# What does this definition of a Primary key mean?

My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated.

Let $R$ be a relation. Then the primary key for $R$ is a subset of the set of attributes of $R$, say $K$, satisfying the following two properties:

1. Uniqueness Property: No two distinct tuples of $R$ have the same value for $K$.

2. Irreducibility Property: No proper subset of $K$ has the uniqueness property.

I'm getting lost by the Irreducibility property.

• Beware: 1) more than one subset of columns may satisfy those properties, so eventually, the primary key is what the person defining primary keys chooses it to be; 2) in practice, DBMSes that support primary keys enforce property 1, but not property 2 (although I haven't checked this for many). – reinierpost Sep 16 '16 at 10:15
• Note: if the book says "the primary key" then it is misleading. It is possible and not uncommon for multiple different sets of columns existing which could be taken as PK. – AnoE Sep 16 '16 at 15:41

Consider the following table:

FirstName  LastName  Pet  FavColour
-----------------------------------
Alice      Jones     dog  red
Alice      Smith     dog  green
Bob        Smith     cat  blue


A key is any set of attributes: any subset of {FirstName, LastName, Pet, FavColour}. The uniqueness property says that no two records can have the same values for the attributes in a key. So, for example, {FavColour} is a key that has the uniqueness property: no two records have the same value for it. {Firstname, Lastname} is also unique: no two records have the same first and last name. {Pet}, on the other hand, is not unique, since the first and second records have the same value for that attribute.

Now, {FirstName, LastName, Pet, FavColour} is also a unique key: no two records have the same value for all the attributes. But that's kind of a silly key, right? Irreducibility says that, if you remove any of the attributes from your key, it stops being unique. So {Firstname, LastName, Pet, FavColour} isn't irreducible because, if you remove FavColour, you get the key {FirstName, LastName, Pet}, which still has uniqueness. And that isn't irreducible because you can throw away Pet and get {FirstName, LastName}, which is still unique. However, {FirstName, LastName} is irreducible because neither {FirstName} nor {LastName} is unique: there are two people with the same first name and two people with the same last name.

• tl;dr: the smallest set of columns that can uniquely identify a record – DForck42 Sep 22 '16 at 18:20
• @DForck42 No, a smallest set of columns that can uniquely identify every record. – David Richerby Sep 22 '16 at 18:24
• The question is phrased in terms of databases, which I would understand to mean schema, not a single relation instance. Keys of a relation schema can't be determined by examining sample data. Sample data may tell us sets of attributes that are NOT keys (e.g. {Pet} is not a key in this instance), but functional dependencies are the only sound basis for determining the actual keys. – nvogel Oct 4 '16 at 22:08

Note how $K$ can be a set of columns. Irreducibility means that you have to pick minimal sets of columns.

Nota bene: They should require $K \neq \emptyset$.

For instance, consider this relation.

A   B   C

1   4   4
2   4   6
3   6   6


Let us investigate all possible keys.

1. A -- unique and irreducible.
2. B -- not unique.
3. C -- not unique.
4. A,B -- reducible to A.
5. A,C -- reducible to A.
6. B,C -- unique and irreducible.
7. A,B,C -- reducible to A.

Hence, there are two choices for primare keys here: A and B,C.

• Re: "They should require $K \neq \emptyset$": That doesn't seem necessary to me. If the relation is empty or contains only one tuple, then $\emptyset$ arguably is the primary key; and if the relation contains more than one tuple, then $\emptyset$ doesn't satisfy the uniqueness property. – ruakh Sep 16 '16 at 5:51
• @ruakh Point taken. – Raphael Sep 16 '16 at 6:46

Irreducibility simply refers to a minimum set of attributes that we can't go below without losing uniqueness. For example, in a table of people, we may find (Lastname, Firstname) are unique while (Lastname) and (Firstname) are not.

Once we have uniqueness we can keep adding attributes without losing it, so irreducibility addresses that problem.