Almost every normalization question starts the same way: given a relation and its functional dependencies, find the candidate keys. The tool for that is the attribute closure X⁺, the set of every attribute that X determines. This page computes closures by hand, uses them to find all the keys, and then reads off the normal form.
The example (the one in Silberschatz's Database System Concepts): R(A, B, C, D, E) with
A → BC
CD → E
B → D
E → A
Computing a closure
Start with X. Then, over and over, look for a dependency whose left side is already inside your set, and add its right side. Stop when a full pass adds nothing.
B⁺:
| Step | Set so far | Dependency used |
|---|---|---|
| 0 | { B } | start |
| 1 | { B, D } | B → D |
A → BC needs A, CD → E needs C, E → A needs E. None apply, so B⁺ = { B, D }. B is not a key.
BC⁺:
| Step | Set so far | Dependency used |
|---|---|---|
| 0 | { B, C } | start |
| 1 | { B, C, D } | B → D |
| 2 | { B, C, D, E } | CD → E (C and D are both in now) |
| 3 | { A, B, C, D, E } | E → A |
BC⁺ is the whole relation, so BC is a superkey. Neither B⁺ = { B, D } nor C⁺ = { C } reaches everything, so no smaller part of it works: BC is a candidate key.
All the closures you need
| X | X⁺ | Key? |
|---|---|---|
| A | A B C D E | candidate key |
| E | A B C D E | candidate key |
| B | B D | no |
| C | C | no |
| D | D | no |
| BC | A B C D E | candidate key |
| CD | A B C D E | candidate key |
| BD | B D | no |
| AD | A B C D E | superkey, but not minimal (A alone works) |
Candidate keys: A, E, BC, CD. Every attribute appears in at least one key, so all five are prime, and there are no non-prime attributes.
Notice the keys are different sizes. A common mistake is to stop as soon as the single-attribute keys A and E are found. BC and CD are just as much candidate keys, because no proper subset of either determines everything.
A shortcut for big relations
Testing every subset gets slow, so first sort the attributes by where they appear:
- Never on a right side: must be in every key, since nothing else can produce it.
- Only on a right side, never on a left: is in no key.
- Both sides: might be in a key; these are the only ones you have to try.
Start from the "must be in every key" set, take its closure, and only add "both sides" attributes if it isn't already the whole relation. In this example every attribute is on some right side and some left side, so the shortcut doesn't narrow anything down, which is exactly why it is an exam favourite.
From keys to the normal form
Once you have the keys, check each dependency X → Y (with Y not inside X):
| Form | It fails when |
|---|---|
| 2NF | X is a proper part of a candidate key and Y has a non-prime attribute (a partial dependency) |
| 3NF | X is not a superkey and Y has a non-prime attribute (a transitive dependency) |
| BCNF | X is not a superkey, whatever Y is |
For our relation:
- A → BC, CD → E and E → A all have a key on the left. Fine for BCNF.
- B → D: B⁺ = { B, D }, so B is not a superkey. That breaks BCNF. But D is prime, so it doesn't break 3NF.
R is in 3NF but not BCNF.
Three short drills
| Dependencies | Candidate keys | Highest form | Why |
|---|---|---|---|
| AB → C, B → D | AB | 1NF | B is part of the key and determines non-prime D: partial |
| A → B, B → C | A | 2NF | B is not a superkey and determines non-prime C: transitive |
| AB → C, C → B | AB, AC | 3NF | C → B: C isn't a superkey, but B is prime |
The third one is the standard "3NF but not BCNF" example. Decomposing it into BCNF loses the dependency AB → C, which is why 3NF is sometimes the better design.
Common mistakes
- Stopping a closure too early. After adding attributes, go back through all the dependencies again; CD → E only fired once D had been added.
- Reporting a superkey as a candidate key. AD determines everything, but it isn't minimal.
- Missing keys of a larger size once a smaller key is found (BC and CD above).
- Calling an attribute non-prime because it isn't in the primary key. Prime means "in any candidate key".
Check your answers
The attribute closure calculator computes X⁺ for any set and says whether it is a superkey. The candidate key finder lists every candidate key, splits prime from non-prime attributes, and names the dependency that breaks each normal form. Paste in the four dependencies above and you get A, E, BC and CD, and "3NF, B → D breaks BCNF".
For a related walkthrough, read SQL to Relational Algebra: Worked Examples.