What does this definition of a Primary key mean?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.