Carol's Recipe for Finding Candidate Keys

• Carol's Recipe
• Useful Facts for Finding Candidate Keys
• Worked Example

Carol's Recipe

Ingredients:

A relation

A minimal FD list and/or minimal FD diagram

Instructions:

1. Place in a working list your "educated guess" of a possible candidate key for the relation

2. Repeat until no more attributes can be added to the working list:

   Choose an FD all of whose left-hand side is in the working list
   and add the right-hand side of this FD to the working list
   (remembering not to add any attributes which are already in the working list)

3. If the working list now contains every attribute in the relation, then your guess is a superkey (it contains a candidate key)

   Check to see which attributes (if any) in your "guess" are redundant and remove them

   When your "guess" is as small as possible, while still being a superkey, it is a candidate key

   If the working list does not contain every attribute in the relation, then your "guess" is not a superkey

4. Keep making guesses until all candidate keys have been found

[Top]

Useful Facts for Finding Candidate Keys

An attribute which is not in the right-hand side (RHS) of any FD
must be in every candidate key

An attribute which is in the right-hand side (RHS) of an FD,
and is not in the left-hand side of any FD,
is in no candidate key

[Top]

Worked Example

Relation:

Minimal FD List:

A, C  →  T

V  →  C

Finding Candidate Keys Using Recipe:

First educated guess: {A, C}    a determinant
Working List 1: A, C
Working List 2: A, C, T         stop
{A, C} is not a superkey

Second educated guess: {V}      a determinant
Working List 1: V
Working List 2: V, C            stop
{V} is not a superkey

Third educated guess {A, C, V}  union first two guesses
Working List 1: A, C, V
Working List 2: A, C, V, T      stop
{A, C, V} is a superkey

Is {A, C, V} a candidate key?

Try removing A
Working List 1: C, V            stop
{A, C} is not a superkey

Try removing C
Working List 1: A, V
Working List 2: A, V, C
Working List 3: A, V, C, T     stop
{A, V} is a superkey
Therefore,{A, C, V} is not a candidate key

Is {A, V} a candidate key?

We already know that V is not a superkey on its own
Let us check to see if A is a superkey on its own
Working List 1: A              stop
A is not a superkey on its own

Therefore, {A, V} is a candidate key

Are there any more candidate keys?   No

We know that A and V must be in every candidate key because they are not determined by any of the other attributes.
So, once we know that {A, V} is a candidate key, we know that {A, V} is the candidate key

[Top]