[Solved]: What does this definition of a Primary key mean?

Problem Detail: 

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.

Asked By : FutureSci

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63512