Finding All Candidate Keys of a Relation

Concept

Finding candidate keys is the most frequently set numerical question in this subject. Trial and error works on tiny examples and fails on real ones. The method below is systematic and always terminates.

Step 1 — classify every attribute

The reasoning behind row one: if an attribute never appears on the right, nothing can determine it, so the only way to know its value is to include it in the key. The reasoning behind row two follows the same logic in reverse — an attribute that is always determined by something else is never needed in a minimal key.

Step 2 — the procedure

  1  Classify all attributes as essential, non essential
     or middle.

  2  Let CORE = the essential attributes.
     Compute CORE+.
       if CORE+ = R   then CORE is the ONLY candidate key.
                      STOP - nothing else can be minimal.

  3  Otherwise, add ONE middle attribute to CORE and
     compute the closure of each combination.
       any combination whose closure is R is a candidate key.

  4  If any combination still falls short, try CORE plus
     TWO middle attributes, and so on.

  5  Never extend a set that is already a candidate key -
     the result would not be minimal.

Worked example 1 — a single key

  R ( A, B, C, D )
  F = { A -> B, B -> C, C -> D }

  STEP 1  classify
     left sides:  A, B, C
     right sides: B, C, D

     A  left only          -> ESSENTIAL
     B  both               -> middle
     C  both               -> middle
     D  right only         -> NON ESSENTIAL

  STEP 2  CORE = { A }
     A+ :  { A }
           A -> B   { A, B }
           B -> C   { A, B, C }
           C -> D   { A, B, C, D }
     A+ = R

  -> { A } is the ONLY candidate key. Stop.

Worked example 2 — two keys

  R ( A, B, C, D, E )
  F = { A B -> C, C -> D, D -> A, B D -> E }

  STEP 1  classify
     left sides:  A, B, C, D
     right sides: C, D, A, E

     A  both        -> middle
     B  left only   -> ESSENTIAL
     C  both        -> middle
     D  both        -> middle
     E  right only  -> NON ESSENTIAL

  STEP 2  CORE = { B }
     B+ = { B }        no dependency has B alone on the left
     not R, so continue

  STEP 3  add one middle attribute at a time

     (B A)+ :  { A, B }
               A B -> C   { A, B, C }
               C -> D     { A, B, C, D }
               D -> A     have A
               B D -> E   { A, B, C, D, E }
               = R        -> CANDIDATE KEY { A, B }

     (B C)+ :  { B, C }
               C -> D     { B, C, D }
               D -> A     { A, B, C, D }
               A B -> C   have C
               B D -> E   { A, B, C, D, E }
               = R        -> CANDIDATE KEY { B, C }

     (B D)+ :  { B, D }
               D -> A     { A, B, D }
               A B -> C   { A, B, C, D }
               B D -> E   { A, B, C, D, E }
               = R        -> CANDIDATE KEY { B, D }

  STEP 4  do NOT test { A, B, C } or larger - each already
          contains a candidate key, so none can be minimal.

  ANSWER  three candidate keys: { A, B }, { B, C }, { B, D }
          Note B is in all three, exactly as step 1 predicted.

Worked example 3 — no essential attribute

  R ( A, B, C )
  F = { A -> B, B -> C, C -> A }

  STEP 1  every attribute appears on both sides
          -> no essential attributes, CORE is empty

  STEP 2  empty closure is empty. Continue.

  STEP 3  try each single attribute
     A+ = { A, B, C } = R      -> candidate key
     B+ = { B, C, A } = R      -> candidate key
     C+ = { C, A, B } = R      -> candidate key

  ANSWER  { A }, { B }, { C } - three candidate keys.

  A cycle of dependencies makes every attribute a key on
  its own, which is a useful pattern to recognise on sight.

Prime and non prime attributes

These terms are needed from the very first sentence of Phase 8: 2NF and 3NF are both defined in terms of non prime attributes, so candidate keys must be found before normalisation can even begin.

Common mistakes

• Skipping the classification step. It removes most of the search space in one move.
• Including a right only attribute in a key. It can never be needed.
• Stopping at the first candidate key. The question usually asks for all of them.
• Testing supersets of a known candidate key. Those cannot be minimal.
• Forgetting an attribute that appears in no dependency. It is essential and must be in every key — a classic trap.
• Confusing prime with primary. Prime means in some candidate key.

Exam and interview questions

1. Describe the method for finding all candidate keys.
2. Why must an attribute appearing only on the left be in every candidate key?
3. Why can an attribute appearing only on the right never be in a candidate key?
4. Define prime and non prime attributes.
5. What does it tell you when the closure of the essential attributes is already the whole relation?

Practice

1. R(A,B,C,D,E), F = { A -> B C, C D -> E, B -> D, E -> A }. Find all candidate keys.
2. R(A,B,C,D), F = { A B -> C, C -> D, D -> A }. Find all candidate keys and list prime attributes.
3. R(A,B,C,D,E,F), F = { A B -> C, C -> D E, E -> F }. Find the candidate key and explain why it is unique.
4. Construct a relation with exactly four candidate keys.

Conclusion

Classify attributes first, build the compulsory core, then extend one attribute at a time and stop as soon as a set is minimal. The prime and non prime labels that fall out of this are what Phase 8 needs to define 2NF and 3NF.