• Tweet
• Sumo

• Tweet

As my final exam on Database Management Course closely approaching, I think I’m a bit forced (in a good way) to write some notes on the topics I’ve learned so far. This time it’s the notes on how to find candidate key of a given relation.

Lately after I started post my database notes on conflict and view serializability, and BCNF and 3NF check, I see increased visitors traffic to my blog. Some visitors actually visited my blog to find how to find candidate keys of a relation. I just have the time now to write this post, hopefully it’s not really too late.

Enough for the introduction, get your pencil and paper, let’s find that candidate keys!

Pencil and Paper? Can you just give me an App?

Sure, here it is:
http://www.koffeinhaltig.com/fds/kandidatenschluessel.php

If you don’t need to understand the process behind finding the candidate keys you can stop reading this blog post now. For those of you who still want to know how to find it manually, read on.

How to find it manually

Finding candidate keys is just as simple as applying some algorithm here and there. Here I post examples of different cases.

First example

WHOSE
WH -> S
HOS -> E

Steps:
1. Find the attributes that are neither on the left and right side
> (none)

2. Find attributes that are only on the right side
> E

3. Find attributes that are only on the left side
> WHO

4. Combine the attributes on step 1 and 3
> since step 1 has no attributes, it’s just WHO

5. Test if the closures of attributes on step 4 are all the attributes
> in our case, yes it is. Because with WH we can get S, and by HOS, we can get E.
So we have only one candidate key, that is WHO.

Second example

ABCDEFG
AB -> F
AD -> E
F -> G

Steps:
1. C
2. EG
3. ABD
4. ABCD
5. The closures of ABCD is ABCDEFG, so ABCD is our candidate key this time.

Third example

ABCD
ABC -> D
D -> A

Steps:
1. –
2. –
3. BC
4. BC
5. The closure of BC is only BC, we should find the relation exterior.
6. Find the relation exteriors, that is the attributes not included in step 4 and step 2.
> in this example it is AD
7. Now test the closures of attributes on step 4 + one attribute in step 6 one at a time.
> ABC closures are ABCD, so it is a candidate key
> BCD closures are ABCD, so it is also a candidate key
> so in this case we have two candidate keys, they are ABC and BCD.

Hoahm… these are too easy, harder examples please..

Allright, ready for some harder examples, here are they:

Hard example #1

ABCDEF
DF -> C
BC -> F
E -> A
ABC -> E

Hard example #2

ABCDE
A -> BC
CD -> E
B -> D
E -> A

Conclusion

This is not the only algorithm of finding candidate key. Another way includes to find the attributes that are on both sides (see comment of RandomSpectrum on my other blog post to know about it). I suppose both algorithms are correct, it’s just a matter of personal preference.

I’m not going to post the answers here for the hard examples just to make it a bit harder. You can find it on different post: answer.