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
   but whose right-hand side is not in the working list
   and add the right-hand side of this FD to 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]