Normalisation – Part 2
3NF
From BCNF to 3NF
Facts
(1) There exists an algorithm that can generate a lossless
decomposition into BCNF.
(2) However, a BCNF-decomposition that is both lossless
and dependency-preserving does not always exist.
3NF is a less restrictive normal form such that a lossless and
dependency preserving decomposition can always be found.
3NF – Definition
A relation schema R is in 3NF if whenever a non-trivial FD X → A holds in
R, then X is a superkey or A is a prime attribute .
3NF allows data redundancy but excludes relation schemas with certain
kinds of FDs (i.e., partial FDs and transitive FDs).
Normalisation to 3NF
Consider the following FDs of ENROL:
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName};
{ConfirmedBy ID} → {StaffName}.
ENROL
StudentID CourseNo Semester ConfirmedBy ID StaffName
123456 COMP2400 2010 S2 u12 Jane
123458 COMP2400 2008 S2 u13 Linda
123458 COMP2600 2008 S2 u13 Linda
Is ENROL in 3NF?
{StudentID, CourseNo, Semester} is the only key.
ENROL is not in 3NF because {ConfirmedBy ID} → {StaffName},
{ConfirmedBy ID} is not a superkey and {StaffName} is not prime
attribute.
Normalisation to 3NF
Algorithm for a dependency-preserving and lossless 3NF-decomposition
Input: a relation schema R and a set Σ of FDs on R.
Output: a set S of relation schemas in 3NF, each having a set of FDs
Compute a minimal cover Σ′ for Σ and start with S = φ
Group FDs in Σ′ by their left-hand-side attribue sets
For each distinct left-hand-side Xi of FDs in Σ
′ that includes
Xi → A1,Xi → A2, . . . ,Xi → Ak :
Add Ri = Xi ∪ {A1} ∪ {A2} · · · ∪ {Ak} to S
Remove all redundant ones from S (i.e., remove Ri if Ri ⊆ Rj )
if S does not contain a superkey of R, add a key of R as R0 into S.
Project the FDs in Σ′ onto each relation schema in S
Normalisation to 3NF
Normalisation to 3NF
Normalisation to 3NF
Minimal Cover – The Hard Part!
Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that
1 Σm is equivalent to Σ, i.e., start with Σm = Σ;
2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;
3 Determinant: each FD has as few attributes on the left hand side as
possible, i.e., for each FD X → A in Σm, check each attribute B of X to
see if we can replace X → A with (X − B)→ A in Σm;
4 Remove a FD from Σm if it is redundant.
Minimal Cover
Theorem:
The minimal cover of a set of functional dependencies Σ always
exists but is not necessarily unique.
Examples: Consider the following set of functional dependencies:
Σ = {A→ BC,B → C,B → A,C → AB}
Σ has two different minimal covers:
Σ1 = {A→ B,B → C,C → A}
Σ2 = {A→ C,C → B,B → A}
Minimal Cover – Examples
The set {A→ B,B → C,A→ C} can be reduced to {A→ B,B → C},
because {A→ C} is implied by the other two.
Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);
3 determine if AB → D has any redundant attribute on the left hand side
(AB → D can be replaced by B → D);
4 look for a redundant FD in {B → A,D → A,B → D} (B → A is
redundant);
Therefore, the minimal cover of Σ is {D → A,B → D}.
Normalisation to 3NF – Example
Consider ENROL again:
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
StudentID CourseNo Semester ConfirmedBy ID StaffName
… … … … …
Can we normalise ENROL into 3NF by a lossless and dependency
preserving decomposition?
Normalisation to 3NF – Example
Consider ENROL again:
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
StudentID CourseNo Semester ConfirmedBy ID StaffName
… … … … …
A minimal cover is {{StudentID, CourseNo, Semester} →
{ConfirmedBy ID}, {ConfirmedBy ID} → {StaffName}}.
Hence, we have:
R1={StudentID, CourseNo, Semester, ConfirmedBy ID} with
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
R2={ConfirmedBy ID, StaffName} with
{ConfirmedBy ID} → {StaffName}
Omit R0 because R1 is a superkey of ENROL.
3NF – Exercises
Let us do some exercises for the 3NF-decomposition algorithm.
Exercise 1: R = {A,B,C,D} and Σ = {A→ B,B → C,AC → D}:
Exercise 2: R = {A,B,C,D} and Σ = {AD → B, AB → C, C → B}:
3NF – Exercises
Let us do some exercises for the 3NF-decomposition algorithm.
Exercise 1: R = {A,B,C,D} and Σ = {A→ B,B → C,AC → D}:
{A→ B,B → C,A→ D} is a minimal cover.
R1 = ABD, R2 = BC (omit R0 because R1 is a superkey of R)
The 3NF-decomposition is {ABD, BC} .
Exercise 2: R = {A,B,C,D} and Σ = {AD → B, AB → C, C → B}:
Σ is its own minimal cover.
R1 = ABD, R2 = ABC, R3 = CB (omit R3 because R3 ⊆ R2 and
omit R0 because R1 is a superkey of R)
The 3NF-decomposition is {ABD, ABC} .