Canonical cover and normal forms: 1NF, 2NF, 3NF, BCNF

Last week you saw closure and finding keys. This week you use them to do two things: reduce an FD set to its simplest form (canonical cover) and find the highest normal form of a schema. The question “What is the highest normal form of R?” is almost guaranteed in the exam. The recipe is always the same:

1. Find all candidate keys.
2. Write the prime attributes: those that appear in at least one candidate key.
3. Test every non-trivial FD in turn against BCNF, 3NF and 2NF.

Canonical cover

There can be many FD sets that carry the same information. The canonical cover $F_c$ is a set that is equivalent to $F$ (the same $F^+$) but contains nothing superfluous:

• No FD has an extraneous attribute.
• Every left side is unique (use $A \to BC$ instead of $A \to B$ and $A \to C$).

The extraneous attribute test

PITFALL · under which F? In the left-side test, the closure is taken with the unchanged F. In the right-side test, you put the shortened FD into the set and take the closure. Mixing the two leads to wrong “extraneous” decisions.

Worked example

$F = \{A \to BD,\ AB \to C,\ C \to D,\ B \to D\}$

1) Split the right sides:   A -> B, A -> D, AB -> C, C -> D, B -> D

2) Left sides:              is B extraneous in AB -> C?
                            {A}+ (under F): A -> B, A -> D, AB -> C  →  ABCD   C is there → B is extraneous
                            is A extraneous? {B}+ = BD, no C → it is not
                            FD:  A -> C

3) Redundant FDs:           if A -> D is removed: {A}+ = A -> B, A -> C, C -> D → ABCD   D is there → remove
                            if B -> D is removed: {B}+ = B, no D → needed
                            if C -> D is removed: {C}+ = C, no D → needed
                            if A -> B is removed: {A}+ = ACD, no B → needed
                            if A -> C is removed: {A}+ = ABD, no C → needed

4) Combine:                 Fc = { A -> BC,  B -> D,  C -> D }

Final check: is $F_c$ equivalent to $F$? Every FD in $F$ can be derived from $F_c$, and the reverse holds too. Equivalent.

TIP · the canonical cover is not unique. If you do the redundancy tests in a different order, you may find a different but equivalent $F_c$. If you write your steps in the exam, both answers are accepted. The examples on this page were solved in order from left to right.

First normal form (1NF)

A schema is in 1NF if the domain of every attribute is atomic: no list, set or repeating group in a cell.

This table is not in 1NF. Fix: a separate table student_phone(stu_id, phone), with each phone in its own row. In the relational model every table is assumed to be in 1NF by default; the following forms look at FDs.

Second normal form (2NF)

1NF + no non-prime attribute depends on a proper subset of a candidate key. This forbidden situation is called a partial dependency.

University example: takes_wide(stu_id, course_id, grade, stu_name, title), with FDs $\{\text{stu\_id, course\_id}\} \to \text{grade}$, $\text{stu\_id} \to \text{stu\_name}$, $\text{course\_id} \to \text{title}$.

The only key is {stu_id, course_id}. stu_name depends only on stu_id, and title only on course_id. Both are partial dependencies: highest 1NF. The update anomaly of last week’s wide table came from exactly this.

Example with letters: $R(A,B,C,D)$, $F = \{AB \to C,\ B \to D\}$. The key is AB, and $B \to D$ is partial: 1NF.

PITFALL · a single-attribute key. If all candidate keys are single attributes, a partial dependency is impossible; if the schema is in 1NF, it is automatically in 2NF. In that case skip the 2NF test and go straight to 3NF.

Third normal form (3NF)

For every non-trivial $X \to A$, at least one of the following must be true:

1. $X$ is a superkey, or
2. $A$ is a prime attribute.

The typical violating case is a transitive dependency: key → non-key → non-key.

University example: student_dept(stu_id, name, dept_name, building), with FDs $\text{stu\_id} \to \text{name, dept\_name}$, $\text{dept\_name} \to \text{building}$. The key is stu_id (a single attribute, so 2NF is automatic). $\text{dept\_name} \to \text{building}$: dept_name is not a superkey, and building is not prime. 3NF is violated: highest 2NF.

Example with letters: $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ A \to D\}$: the key is A, $B \to C$ is transitive, 2NF.

Boyce-Codd normal form (BCNF)

For every non-trivial $X \to Y$, $X$ must be a superkey. There is no “or A is prime” escape route as in 3NF. Every BCNF schema is in 3NF; the reverse is not always true.

The classic case that is in 3NF but not in BCNF: a non-key attribute determines part of a key. University example: tutoring(stu_id, subject, tutor_id). The rules: each tutor handles a single subject, and each student works with a single tutor for each subject.

$\text{tutor\_id} \to \text{subject} \qquad \{\text{stu\_id, subject}\} \to \text{tutor\_id}$

The keys: {stu_id, subject} and {stu_id, tutor_id}. All three attributes are prime. $\text{tutor\_id} \to \text{subject}$: tutor_id is not a superkey, a BCNF violation. But subject is prime, so 3NF holds. Highest 3NF.

The version with letters: $R(A,B,C)$, $F = \{AB \to C,\ C \to B\}$, keys AB and AC, result 3NF.

All together: a worked determination

$R(A,B,C,D,E)$, $F = \{AB \to CDE,\ C \to D,\ D \to B\}$.

Keys:        A is not on the right → in every key
             {A}+ = A
             {A,B}+ = ABCDE   key
             {A,C}+: C -> D, D -> B, AB -> CDE  = ABCDE  key
             {A,D}+: D -> B, AB -> CDE          = ABCDE  key
             {A,E}+ = AE      not a key
Prime:       A, B, C, D        (E is not prime)

AB -> CDE    AB is a superkey          BCNF ok
C  -> D      C is not a superkey       BCNF violation; D is prime → 3NF ok
D  -> B      D is not a superkey       BCNF violation; B is prime → 3NF ok

Result: 3NF (not BCNF)

One more BCNF example: $R(A,B,C,D)$, $F = \{A \to BCD,\ BC \to A\}$. $\{A\}^+$ and $\{B,C\}^+$ are both ABCD: every left side is a superkey, BCNF. The university’s course(course_id, title, dept_name, credits) and department(dept_name, building, budget) tables are in BCNF for the same reason: their only FDs come from the key.

PITFALL · looking only at F in the pieces. When you test the whole schema, looking at the FDs in F is enough. But when you test a decomposed piece, you have to think of the projection of $F^+$ onto that piece: FDs that come through an intermediate attribute not visible in the piece count too. We will use this next week.

Summary table of normal forms

Common mistakes