1/50
Week 6 Workshop – Normalisation
http://en.wikipedia.org/wiki/Ursus_Wehrli
http://en.wikipedia.org/wiki/Ursus_Wehrli
2/50
Housekeeping
Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)
The mark and feedback will be released on 17 Sep 2021.
An optional exercise website for our course
https://cs.anu.edu.au/dab/bench/db-exercises/
An anonymous survey from our course representatives on Wattle
(till 4 Sep under Week 6)
Help us to improve our planning and teaching
https://cs.anu.edu.au/dab/bench/db-exercises/
2/50
Housekeeping
Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)
The mark and feedback will be released on 17 Sep 2021.
An optional exercise website for our course
https://cs.anu.edu.au/dab/bench/db-exercises/
An anonymous survey from our course representatives on Wattle
(till 4 Sep under Week 6)
Help us to improve our planning and teaching
https://cs.anu.edu.au/dab/bench/db-exercises/
2/50
Housekeeping
Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)
The mark and feedback will be released on 17 Sep 2021.
An optional exercise website for our course
https://cs.anu.edu.au/dab/bench/db-exercises/
An anonymous survey from our course representatives on Wattle
(till 4 Sep under Week 6)
Help us to improve our planning and teaching
https://cs.anu.edu.au/dab/bench/db-exercises/
3/50
Decomposition vs Normalisation
Decomposing a relation schema can possibly create
more problems than it solves!
Thus, we need to consider two important questions:
1 Do we need to decompose a relation?
Several normal forms
↪→ help us to decide whether or not to decompose a relation
2 What problem (if any) does a given decomposition cause?
Two properties
↪→ help us to decide how to decompose a relation
3/50
Decomposition vs Normalisation
Decomposing a relation schema can possibly create
more problems than it solves!
Thus, we need to consider two important questions:
1 Do we need to decompose a relation?
Several normal forms
↪→ help us to decide whether or not to decompose a relation
2 What problem (if any) does a given decomposition cause?
Two properties
↪→ help us to decide how to decompose a relation
3/50
Decomposition vs Normalisation
Decomposing a relation schema can possibly create
more problems than it solves!
Thus, we need to consider two important questions:
1 Do we need to decompose a relation?
Several normal forms
↪→ help us to decide whether or not to decompose a relation
2 What problem (if any) does a given decomposition cause?
Two properties
↪→ help us to decide how to decompose a relation
3/50
Decomposition vs Normalisation
Decomposing a relation schema can possibly create
more problems than it solves!
Thus, we need to consider two important questions:
1 Do we need to decompose a relation?
Several normal forms
↪→ help us to decide whether or not to decompose a relation
2 What problem (if any) does a given decomposition cause?
Two properties
↪→ help us to decide how to decompose a relation
3/50
Decomposition vs Normalisation
Decomposing a relation schema can possibly create
more problems than it solves!
Thus, we need to consider two important questions:
1 Do we need to decompose a relation?
Several normal forms
↪→ help us to decide whether or not to decompose a relation
2 What problem (if any) does a given decomposition cause?
Two properties
↪→ help us to decide how to decompose a relation
4/50
Two Properties
In addition to data redundancy, we need to consider the following
properties when decomposing a relation:
1 Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a
NATURAL JOIN operation is applied to the relations after decomposition.
2 Dependency preservation – “ capture the same meta-data ”
To ensure that each functional dependency can be inferred from
functional dependencies after decomposition.
4/50
Two Properties
In addition to data redundancy, we need to consider the following
properties when decomposing a relation:
1 Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a
NATURAL JOIN operation is applied to the relations after decomposition.
2 Dependency preservation – “ capture the same meta-data ”
To ensure that each functional dependency can be inferred from
functional dependencies after decomposition.
4/50
Two Properties
In addition to data redundancy, we need to consider the following
properties when decomposing a relation:
1 Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a
NATURAL JOIN operation is applied to the relations after decomposition.
2 Dependency preservation – “ capture the same meta-data ”
To ensure that each functional dependency can be inferred from
functional dependencies after decomposition.
5/50
Lossless Join – Example
Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a NATURAL
JOIN operation is applied to the relations after decomposition.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID DoB
123456 20/09/1989
123458 25/01/1988
Example 1: Does the decomposition of R into R1 and R2 has the lossless
join property?
Yes, because the natural join of R1 and R2 yields R.
5/50
Lossless Join – Example
Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a NATURAL
JOIN operation is applied to the relations after decomposition.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID DoB
123456 20/09/1989
123458 25/01/1988
Example 1: Does the decomposition of R into R1 and R2 has the lossless
join property?
Yes, because the natural join of R1 and R2 yields R.
5/50
Lossless Join – Example
Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a NATURAL
JOIN operation is applied to the relations after decomposition.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID DoB
123456 20/09/1989
123458 25/01/1988
Example 1: Does the decomposition of R into R1 and R2 has the lossless
join property?
Yes, because the natural join of R1 and R2 yields R.
6/50
Lossless Join – Example
Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a NATURAL
JOIN operation is applied to the relations after decomposition.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R3
Name StudentID
Mike 123456
Mike 123458
R4
Name DoB
Mike 20/09/1989
Mike 25/01/1988
Example 2: Does the decomposition of R into R3 and R4 has the lossless
join property?
No, because the natural join of R3 and R4 generates spurious tuples.
6/50
Lossless Join – Example
Lossless join – “ capture the same data ”
To disallow the possibility of generating spurious tuples when a NATURAL
JOIN operation is applied to the relations after decomposition.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R3
Name StudentID
Mike 123456
Mike 123458
R4
Name DoB
Mike 20/09/1989
Mike 25/01/1988
Example 2: Does the decomposition of R into R3 and R4 has the lossless
join property?
No, because the natural join of R3 and R4 generates spurious tuples.
7/50
Lossless Join – Example
Example 2: The following decomposition from R into R3 and R4 doesn’t
have the lossless join property. It generates spurious tuples.
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
SELECT * FROM R3 NATURAL JOIN R4
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123456 25/01/1988
Mike 123458 20/09/1989
Mike 123458 25/01/1988
R3
Name StudentID
Mike 123456
Mike 123458
R4
Name DoB
Mike 20/09/1989
Mike 25/01/1988
8/50
Lossless Join – Example
Lossless join – “ capture the same data ”
R
Name StudentID DoB
Mike 123456 20/09/1989
Mike 123458 25/01/1988
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID DoB
123456 20/09/1989
123458 25/01/1988
Lossless join
R3
Name StudentID
Mike 123456
Mike 123458
R4
Name DoB
Mike 20/09/1989
Mike 25/01/1988
Not lossless join
9/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 1: Given a FD {StudentID} → {Name} defined on R
R
Name StudentID CourseNo
Mike 123456 COMP2400
Mike 123458 COMP2600
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID CourseNo
123456 COMP2400
123458 COMP2600
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} and {Name} are both in R1 after decomposition
and thus {StudentID} → {Name} is preserved in R1.
9/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 1: Given a FD {StudentID} → {Name} defined on R
R
Name StudentID CourseNo
Mike 123456 COMP2400
Mike 123458 COMP2600
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID CourseNo
123456 COMP2400
123458 COMP2600
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} and {Name} are both in R1 after decomposition
and thus {StudentID} → {Name} is preserved in R1.
9/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 1: Given a FD {StudentID} → {Name} defined on R
R
Name StudentID CourseNo
Mike 123456 COMP2400
Mike 123458 COMP2600
R1
Name StudentID
Mike 123456
Mike 123458
R2
StudentID CourseNo
123456 COMP2400
123458 COMP2600
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} and {Name} are both in R1 after decomposition
and thus {StudentID} → {Name} is preserved in R1.
10/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 2: Given a FD {StudentID} → {Name} defined on R
R
Name StudentID CourseNo
Mike 123456 COMP2400
Mike 123458 COMP2600
R1
Name CourseNo
Mike COMP2400
Mike COMP2600
R2
StudentID CourseNo
123456 COMP2400
123458 COMP2600
Does the above decomposition preserves {StudentID} → {Name}?
No, because {StudentID} and {Name} are not in a same relation after
decomposition.
10/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 2: Given a FD {StudentID} → {Name} defined on R
R
Name StudentID CourseNo
Mike 123456 COMP2400
Mike 123458 COMP2600
R1
Name CourseNo
Mike COMP2400
Mike COMP2600
R2
StudentID CourseNo
123456 COMP2400
123458 COMP2600
Does the above decomposition preserves {StudentID} → {Name}?
No, because {StudentID} and {Name} are not in a same relation after
decomposition.
11/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 3: Given a set of FDs { {StudentID} → {Email}, {Email} →
{Name}, {StudentID} → {Name} } defined on R
R
Name StudentID Email
Mike 123456 .au
Tom 123123 .au
R1
Name Email
Mike .au
Tom .au
R2
StudentID Email
123456 .au
123123 .au
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} → {Name} can be inferred by {StudentID} →
{Email} (preserved in R2) and {Email} → {Name} (preserved in R1).
11/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 3: Given a set of FDs { {StudentID} → {Email}, {Email} →
{Name}, {StudentID} → {Name} } defined on R
R
Name StudentID Email
Mike 123456 .au
Tom 123123 .au
R1
Name Email
Mike .au
Tom .au
R2
StudentID Email
123456 .au
123123 .au
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} → {Name} can be inferred by {StudentID} →
{Email} (preserved in R2) and {Email} → {Name} (preserved in R1).
11/50
Dependency Preservation – Example
Dependency preservation: To ensure that each functional dependency
can be inferred from functional dependencies after decomposition.
Example 3: Given a set of FDs { {StudentID} → {Email}, {Email} →
{Name}, {StudentID} → {Name} } defined on R
R
Name StudentID Email
Mike 123456 .au
Tom 123123 .au
R1
Name Email
Mike .au
Tom .au
R2
StudentID Email
123456 .au
123123 .au
Does the above decomposition preserves {StudentID} → {Name}?
Yes, because {StudentID} → {Name} can be inferred by {StudentID} →
{Email} (preserved in R2) and {Email} → {Name} (preserved in R1).
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join?
Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving?
No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
12/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R2 = {A,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ2 = {A→ C}
Lossless join? Yes because A is a superkey for R1.
Dependency preserving? No because (Σ1 ∪ Σ2)∗ 6= Σ∗ from the fact
that {A→ B,A→ C} 2 B → C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join? Yes because B is a superkey for R3.
Dependency preserving? Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join? Yes because B is a superkey for R3.
Dependency preserving? Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join?
Yes because B is a superkey for R3.
Dependency preserving? Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join? Yes because B is a superkey for R3.
Dependency preserving? Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join? Yes because B is a superkey for R3.
Dependency preserving?
Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
13/50
Discussion
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
Lossless join if and only if the common attributes of R1 and R2 are a
superkey for R1 or R2;
Dependency preserving if and only if (Σ1 ∪ Σ2)∗ = Σ∗ holds.
Consider R={A, B, C} with the set of FDs Σ = {A→ B,B → C,A→ C}.
Does the decompostion of R into R1 = {A,B} and R3 = {B,C} fullfill
lossless join and dependency preserving?
Σ1 = {A→ B} and Σ3 = {B → C}
Lossless join? Yes because B is a superkey for R3.
Dependency preserving? Yes because (Σ1 ∪ Σ3)∗ = Σ∗ from the
fact that {A→ B,B → C} � A→ C.
14/50
Normal Forms
Normal forms Test criteria
1NF
⇓ weak
2NF
⇓⇓
3NF
⇓
BCNF strong
…
BCNF 3NF 2NF 1NF
Note that:
1NF is independent of keys and functional dependencies.
2NF, 3NF and BCNF are based on keys and functional dependencies.
4NF and 5NF are based on other dependencies (will not be covered in
this course).
15/50
BCNF
Do not represent the same fact twice (within a relation)!
16/50
BCNF – Definition
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
When a relation schema is in BCNF, all data redundancy based on
functional dependency are removed.
Here data redundancy is considered in terms of FDs, i.e., for a
non-trivial FD X → Y , there exists a relation R that contains two
distinct tuples t1 and t2 with t1[XY ] = t2[XY ].
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
16/50
BCNF – Definition
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
When a relation schema is in BCNF, all data redundancy based on
functional dependency are removed.
Here data redundancy is considered in terms of FDs, i.e., for a
non-trivial FD X → Y , there exists a relation R that contains two
distinct tuples t1 and t2 with t1[XY ] = t2[XY ].
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
16/50
BCNF – Definition
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
When a relation schema is in BCNF, all data redundancy based on
functional dependency are removed.
Here data redundancy is considered in terms of FDs, i.e., for a
non-trivial FD X → Y , there exists a relation R that contains two
distinct tuples t1 and t2 with t1[XY ] = t2[XY ].
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
17/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}.
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Is TEACH in BCNF?
Not in BCNF because {CourseName} is not a superkey.
Did we represent the same fact twice (or more times)?
Yes, the Instructor of Relational Databases is Yu.
17/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}.
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Is TEACH in BCNF?
Not in BCNF because {CourseName} is not a superkey.
Did we represent the same fact twice (or more times)?
Yes, the Instructor of Relational Databases is Yu.
17/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}.
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Is TEACH in BCNF?
Not in BCNF because {CourseName} is not a superkey.
Did we represent the same fact twice (or more times)?
Yes, the Instructor of Relational Databases is Yu.
17/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}.
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Is TEACH in BCNF?
Not in BCNF because {CourseName} is not a superkey.
Did we represent the same fact twice (or more times)?
Yes, the Instructor of Relational Databases is Yu.
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
18/50
Normalisation to BCNF
Algorithm for a BCNF-decomposition
Input: a relation schema R′ and a set Σ of FDs on R′.
Output: a set S of relation schemas in BCNF, each having a set of FDs
Start with S = {R′};
Do the following for each R ∈ S iteratively until no changes on S:
Find a (non-trivial) FD X → Y on R that violates BCNF, if any;
Replace R in S by two relation schemas XY and (R − Y ) and
project the FDs to these two relation schemas.
Does the above Algorithm always produce a lossless decomposition?
If R with a set Σ of FDs is decomposed into R1 with Σ1 and R2 with Σ2,
this decomposition is lossless join if and only if the common
attributes of R1 and R2 are a superkey for R1 or R2.
Yes because X is a superkey for XY .
19/50
Normalisation to BCNF
20/50
Normalisation to BCNF
21/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Can we normalise TEACH into BCNF? Yes.
R1
CourseName Instructor
Operating Systems Hegel
Relational Databases Yu
R2
StudentID CourseName
u123456 Operating Systems
u234566 Relational Databases
u234567 Relational Databases
Do not represent the same fact twice (within a relation)!
21/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Can we normalise TEACH into BCNF?
Yes.
R1
CourseName Instructor
Operating Systems Hegel
Relational Databases Yu
R2
StudentID CourseName
u123456 Operating Systems
u234566 Relational Databases
u234567 Relational Databases
Do not represent the same fact twice (within a relation)!
21/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Can we normalise TEACH into BCNF? Yes.
R1
CourseName Instructor
Operating Systems Hegel
Relational Databases Yu
R2
StudentID CourseName
u123456 Operating Systems
u234566 Relational Databases
u234567 Relational Databases
Do not represent the same fact twice (within a relation)!
21/50
Normalisation to BCNF
A relation schema R is in BCNF if whenever a non-trivial FD X → A holds in
R, then X is a superkey .
Consider the relation schema TEACH with the following FD:
{CourseName} → {Instructor}
TEACH
StudentID CourseName Instructor
u123456 Operating Systems Hegel
u234566 Relational Databases Yu
u234567 Relational Databases Yu
Can we normalise TEACH into BCNF? Yes.
R1
CourseName Instructor
Operating Systems Hegel
Relational Databases Yu
R2
StudentID CourseName
u123456 Operating Systems
u234566 Relational Databases
u234567 Relational Databases
Do not represent the same fact twice (within a relation)!
22/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
Is INTERVIEW in BCNF? If not, normalize INTERVIEW into BCNF.
{CustomerID, Date}, {OfficerID, Date, Time}, and {Date, Time,
Room} are the keys.
Any superkey must contain one of of these keys as a subset.
INTERVIEW is not in BCNF because {OfficerID, Date}→ {Room} and
{OfficerID, Date} is not a superkey.
22/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
Is INTERVIEW in BCNF? If not, normalize INTERVIEW into BCNF.
{CustomerID, Date}, {OfficerID, Date, Time}, and {Date, Time,
Room} are the keys.
Any superkey must contain one of of these keys as a subset.
INTERVIEW is not in BCNF because {OfficerID, Date}→ {Room} and
{OfficerID, Date} is not a superkey.
22/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
Is INTERVIEW in BCNF? If not, normalize INTERVIEW into BCNF.
{CustomerID, Date}, {OfficerID, Date, Time}, and {Date, Time,
Room} are the keys.
Any superkey must contain one of of these keys as a subset.
INTERVIEW is not in BCNF because {OfficerID, Date}→ {Room} and
{OfficerID, Date} is not a superkey.
22/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
Is INTERVIEW in BCNF? If not, normalize INTERVIEW into BCNF.
{CustomerID, Date}, {OfficerID, Date, Time}, and {Date, Time,
Room} are the keys.
Any superkey must contain one of of these keys as a subset.
INTERVIEW is not in BCNF because {OfficerID, Date}→ {Room} and
{OfficerID, Date} is not a superkey.
23/50
BCNF – Exercise
We decompose INTERVIEW along the FD: {OfficerID, Date} → {Room}:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
S1011 P105 12/11/2013 12:00 R15
S1024 P108 14/11/2013 14:00 R10
S1024 P107 14/11/2013 14:00 R10
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Do not represent the same fact twice (within a relation)!
23/50
BCNF – Exercise
We decompose INTERVIEW along the FD: {OfficerID, Date} → {Room}:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
S1011 P105 12/11/2013 12:00 R15
S1024 P108 14/11/2013 14:00 R10
S1024 P107 14/11/2013 14:00 R10
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Do not represent the same fact twice (within a relation)!
24/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Project FDs on two new relation schemas.
INTERVIEW1: {OfficerID, Date} → {Room}
INTERVIEW2: {CustomerID, Date} → {OfficerID, Time}, {OfficerID, Date,
Time} → {CustomerID}.
24/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Project FDs on two new relation schemas.
INTERVIEW1: {OfficerID, Date} → {Room}
INTERVIEW2: {CustomerID, Date} → {OfficerID, Time}, {OfficerID, Date,
Time} → {CustomerID}.
24/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Project FDs on two new relation schemas.
INTERVIEW1: {OfficerID, Date} → {Room}
INTERVIEW2: {CustomerID, Date} → {OfficerID, Time}, {OfficerID, Date,
Time} → {CustomerID}.
25/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Is this decomposition dependency-preservation?
No because {Date, Time, Room}→ {CustomerID} is lost (and cannot
be recovered)!
25/50
BCNF – Exercise
Consider INTERVIEW={OfficerID, CustomerID, Date, Time, Room} with the
following FDs:
{OfficerID, Date} → {Room}
{CustomerID, Date} → {OfficerID, Time}
{OfficerID, Date, Time} → {CustomerID}
{Date, Time, Room} → {CustomerID}
INTERVIEW1
OfficerID Date Room
S1011 12/11/2013 R15
S1024 14/11/2013 R10
INTERVIEW2
OfficerID CustomerID Date Time
S1011 P100 12/11/2013 10:00
S1011 P105 12/11/2013 12:00
S1024 P108 14/11/2013 14:00
S1024 P107 14/11/2013 14:00
Is this decomposition dependency-preservation?
No because {Date, Time, Room}→ {CustomerID} is lost (and cannot
be recovered)!
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
26/50
BCNF – Order Does Matter
When applying BCNF decomposition, the order in which the FDs are
applied may lead to different results.
Example: Consider R = {A,B,C} and {A→ B,C → B,B → C}.
Case 1: (Using C → B first)
R1 = {B,C},Σ1 = {B → C.C → B}; R2 = {A,C},Σ2 = {A→ C}
Case 2: (Using B → C first)
R′1 = {B,C},Σ
′
1 = {B → C,C → B}; R
′
2 = {A,B},Σ
′
2 = {A→ B};
27/50
Lossless Join & Dependency Preservation
So far, we know how to find a lossless BCNF-decomposition, but it may not
be dependency-preserving.
Is there a less restrictive normal form such that a lossless and
dependency-preserving decomposition can always be found?
Yes, refer to 3NF.
27/50
Lossless Join & Dependency Preservation
So far, we know how to find a lossless BCNF-decomposition, but it may not
be dependency-preserving.
Is there a less restrictive normal form such that a lossless and
dependency-preserving decomposition can always be found?
Yes, refer to 3NF.
28/50
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 .
Question: If R is in BCNF, then R is in 3NF?
Yes
3NF preserves all the functional dependencies at the cost of allowing
some data redundancy.
28/50
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 .
Question: If R is in BCNF, then R is in 3NF?
Yes
3NF preserves all the functional dependencies at the cost of allowing
some data redundancy.
28/50
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 .
Question: If R is in BCNF, then R is in 3NF?
Yes
3NF preserves all the functional dependencies at the cost of allowing
some data redundancy.
29/50
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.
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 .
Not in 3NF, because of {ConfirmedBy ID} → {StaffName}:
{ConfirmedBy ID} is NOT a superkey and {StaffName} is NOT a
prime attribute.
29/50
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.
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 .
Not in 3NF, because of {ConfirmedBy ID} → {StaffName}:
{ConfirmedBy ID} is NOT a superkey and {StaffName} is NOT a
prime attribute.
29/50
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.
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 .
Not in 3NF, because of {ConfirmedBy ID} → {StaffName}:
{ConfirmedBy ID} is NOT a superkey and {StaffName} is NOT a
prime attribute.
29/50
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.
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 .
Not in 3NF, because of {ConfirmedBy ID} → {StaffName}:
{ConfirmedBy ID} is NOT a superkey and {StaffName} is NOT a
prime attribute.
29/50
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.
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 .
Not in 3NF, because of {ConfirmedBy ID} → {StaffName}:
{ConfirmedBy ID} is NOT a superkey and {StaffName} is NOT a
prime attribute.
30/50
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
30/50
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
30/50
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
30/50
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
30/50
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
30/50
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
30/50
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
31/50
Normalisation to 3NF
32/50
Normalisation to 3NF
33/50
Normalisation to 3NF
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 ,
then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 ,
then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
34/50
Equivalence of Functional Dependencies
Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .
Σ∗1= Σ
∗
2 if Σ1 � Σ2 and Σ2 � Σ1.
Example 1:
Σ1 = {X → Y ,Y → Z ,X → Z} and Σ2 = {X → Y ,Y → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Example 2:
Σ1 = {X → Y ,XY → Z} and Σ2 = {X → Y ,X → Z}
If Σ∗1= Σ
∗
2 , then Σ1 is not minimal
Questions: Can we find the minimal one among equivalent sets of FDs?
35/50
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.
35/50
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.
35/50
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.
35/50
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.
35/50
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.
36/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
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;
{StudentID, CourseNo, Semester} → { ConfirmedBy ID, StaffName }
can be replaced by
{StudentID, CourseNo, Semester} → { ConfirmedBy ID }
{StudentID, CourseNo, Semester} → { StaffName }
36/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
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;
{StudentID, CourseNo, Semester} → { ConfirmedBy ID, StaffName }
can be replaced by
{StudentID, CourseNo, Semester} → { ConfirmedBy ID }
{StudentID, CourseNo, Semester} → { StaffName }
36/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
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;
{StudentID, CourseNo, Semester} → { ConfirmedBy ID, StaffName }
can be replaced by
{StudentID, CourseNo, Semester} → { ConfirmedBy ID }
{StudentID, CourseNo, Semester} → { StaffName }
36/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
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;
{StudentID, CourseNo, Semester} → { ConfirmedBy ID, StaffName }
can be replaced by
{StudentID, CourseNo, Semester} → { ConfirmedBy ID }
{StudentID, CourseNo, Semester} → { StaffName }
36/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
{ConfirmedBy ID} → {StaffName}
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;
{StudentID, CourseNo, Semester} → { ConfirmedBy ID, StaffName }
can be replaced by
{StudentID, CourseNo, Semester} → { ConfirmedBy ID }
{StudentID, CourseNo, Semester} → { StaffName }
37/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
check if { StudentID, CourseNo, Semester } → {ConfirmedBy ID} is
minimal with respect to the left hand side
check if { StudentID, CourseNo, Semester } → {StaffName} is
minimal with respect to the left hand side
All look good!
37/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
check if { StudentID, CourseNo, Semester } → {ConfirmedBy ID} is
minimal with respect to the left hand side
check if { StudentID, CourseNo, Semester } → {StaffName} is
minimal with respect to the left hand side
All look good!
37/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
check if { StudentID, CourseNo, Semester } → {ConfirmedBy ID} is
minimal with respect to the left hand side
check if { StudentID, CourseNo, Semester } → {StaffName} is
minimal with respect to the left hand side
All look good!
37/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
check if { StudentID, CourseNo, Semester } → {ConfirmedBy ID} is
minimal with respect to the left hand side
check if { StudentID, CourseNo, Semester } → {StaffName} is
minimal with respect to the left hand side
All look good!
38/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
4 look for a redundant FD in { {StudentID, CourseNo, Semester} →
{ConfirmedBy ID}, {StudentID, CourseNo, Semester} →
{StaffName}, {ConfirmedBy ID} → {StaffName} }
{StudentID, CourseNo, Semester} → {StaffName} is redundant
and thus is removed
5 Therefore, the minial cover of Σ is { {StudentID, CourseNo,
Semester} → {ConfirmedBy ID}, {ConfirmedBy ID} → {StaffName}}
38/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
4 look for a redundant FD in { {StudentID, CourseNo, Semester} →
{ConfirmedBy ID}, {StudentID, CourseNo, Semester} →
{StaffName}, {ConfirmedBy ID} → {StaffName} }
{StudentID, CourseNo, Semester} → {StaffName} is redundant
and thus is removed
5 Therefore, the minial cover of Σ is { {StudentID, CourseNo,
Semester} → {ConfirmedBy ID}, {ConfirmedBy ID} → {StaffName}}
38/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
4 look for a redundant FD in { {StudentID, CourseNo, Semester} →
{ConfirmedBy ID}, {StudentID, CourseNo, Semester} →
{StaffName}, {ConfirmedBy ID} → {StaffName} }
{StudentID, CourseNo, Semester} → {StaffName} is redundant
and thus is removed
5 Therefore, the minial cover of Σ is { {StudentID, CourseNo,
Semester} → {ConfirmedBy ID}, {ConfirmedBy ID} → {StaffName}}
38/50
Minimal Cover – Examples
Given the set of FDs Σ
{StudentID, CourseNo, Semester} → {ConfirmedBy ID}
{StudentID, CourseNo, Semester} → {StaffName}
{ConfirmedBy ID} → {StaffName}
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;
3 check whether all the FDs in Σ have redundant attribute on the left
hand side;
4 look for a redundant FD in { {StudentID, CourseNo, Semester} →
{ConfirmedBy ID}, {StudentID, CourseNo, Semester} →
{StaffName}, {ConfirmedBy ID} → {StaffName} }
{StudentID, CourseNo, Semester} → {StaffName} is redundant
and thus is removed
5 Therefore, the minial cover of Σ is { {StudentID, CourseNo,
Semester} → {ConfirmedBy ID}, {ConfirmedBy ID} → {StaffName}}
39/50
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?
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved? Yes.
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved? Yes.
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved? Yes.
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved? Yes.
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved?
Yes.
40/50
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.
Is {StudentID, CourseNo, Semester} → {ConfirmedBy ID, StaffName}
preserved? Yes.
41/50
Normalisation to 3NF – Example
Consider INTERVIEW:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
… … … … …
1 {OfficerID, Date} → {Room}
2 {CustomerID, Date} → {OfficerID, Time}
3 {OfficerID, Date, Time} → {CustomerID}
4 {Date, Time, Room} → {CustomerID}
Is INTERVIEW in 3NF? If not, normalise INTERVIEW into lossless and
dependency preserving 3NF.
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 .
We know that {CustomerID, Date}, {OfficerID, Date, Time}, and
{Date, Time, Room} are the keys.
INTERVIEW is in 3NF because all the attributes are prime attributes.
41/50
Normalisation to 3NF – Example
Consider INTERVIEW:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
… … … … …
1 {OfficerID, Date} → {Room}
2 {CustomerID, Date} → {OfficerID, Time}
3 {OfficerID, Date, Time} → {CustomerID}
4 {Date, Time, Room} → {CustomerID}
Is INTERVIEW in 3NF? If not, normalise INTERVIEW into lossless and
dependency preserving 3NF.
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 .
We know that {CustomerID, Date}, {OfficerID, Date, Time}, and
{Date, Time, Room} are the keys.
INTERVIEW is in 3NF because all the attributes are prime attributes.
41/50
Normalisation to 3NF – Example
Consider INTERVIEW:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
… … … … …
1 {OfficerID, Date} → {Room}
2 {CustomerID, Date} → {OfficerID, Time}
3 {OfficerID, Date, Time} → {CustomerID}
4 {Date, Time, Room} → {CustomerID}
Is INTERVIEW in 3NF? If not, normalise INTERVIEW into lossless and
dependency preserving 3NF.
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 .
We know that {CustomerID, Date}, {OfficerID, Date, Time}, and
{Date, Time, Room} are the keys.
INTERVIEW is in 3NF because all the attributes are prime attributes.
41/50
Normalisation to 3NF – Example
Consider INTERVIEW:
INTERVIEW
OfficerID CustomerID Date Time Room
S1011 P100 12/11/2013 10:00 R15
… … … … …
1 {OfficerID, Date} → {Room}
2 {CustomerID, Date} → {OfficerID, Time}
3 {OfficerID, Date, Time} → {CustomerID}
4 {Date, Time, Room} → {CustomerID}
Is INTERVIEW in 3NF? If not, normalise INTERVIEW into lossless and
dependency preserving 3NF.
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 .
We know that {CustomerID, Date}, {OfficerID, Date, Time}, and
{Date, Time, Room} are the keys.
INTERVIEW is in 3NF because all the attributes are prime attributes.
42/50
The Minimal Cover – More Example
Let us consider a relation schema LOTS(PropertyID, County, Lot, Area) with
the following FDS:
FD1: PropertyID→ Lot, County, Area
FD2: Lot, County→ Area, PropertyID
FD3: Area→ County
Let us abbriviate attributes of LOTS with first letter of each attribute and
represent our set of dependencies as F: {P→ LCA, LC→ AP, A→ C}
The minimal cover of a set of functional dependencies always exists but is
not necessarily unique.
42/50
The Minimal Cover – More Example
Let us consider a relation schema LOTS(PropertyID, County, Lot, Area) with
the following FDS:
FD1: PropertyID→ Lot, County, Area
FD2: Lot, County→ Area, PropertyID
FD3: Area→ County
Let us abbriviate attributes of LOTS with first letter of each attribute and
represent our set of dependencies as F: {P→ LCA, LC→ AP, A→ C}
The minimal cover of a set of functional dependencies always exists but is
not necessarily unique.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
43/50
The Minimal Cover – More Example
(Case X) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.
(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}
1 Initialise: {P→ LCA, LC→ AP, A→ C}
2 Dependent: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
3 Determinant: {P→ L, P→ C, P→ A, LC→ A, LC→ P, A→ C}.
4 Remove redundant FD: {LC→ P, P→ A} |= LC→ A. {P→ A, A→
C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.
44/50
Normal Forms
BCNF: Whenever a non-trivial FD X → A holds in R, then
X is a superkey .
Do not represent the same fact more than once within a relation,
even if some FDs have to be abandoned!
3NF: Whenever a non-trivial FD X → A holds in R, then X is a superkey
or A is a prime attribute .
Do not abandon any FDs, even if
some facts have to be represented more than once within a relation!
44/50
Normal Forms
BCNF: Whenever a non-trivial FD X → A holds in R, then
X is a superkey .
Do not represent the same fact more than once within a relation,
even if some FDs have to be abandoned!
3NF: Whenever a non-trivial FD X → A holds in R, then X is a superkey
or A is a prime attribute .
Do not abandon any FDs, even if
some facts have to be represented more than once within a relation!
44/50
Normal Forms
BCNF: Whenever a non-trivial FD X → A holds in R, then
X is a superkey .
Do not represent the same fact more than once within a relation,
even if some FDs have to be abandoned!
3NF: Whenever a non-trivial FD X → A holds in R, then X is a superkey
or A is a prime attribute .
Do not abandon any FDs, even if
some facts have to be represented more than once within a relation!
44/50
Normal Forms
BCNF: Whenever a non-trivial FD X → A holds in R, then
X is a superkey .
Do not represent the same fact more than once within a relation,
even if some FDs have to be abandoned!
3NF: Whenever a non-trivial FD X → A holds in R, then X is a superkey
or A is a prime attribute .
Do not abandon any FDs, even if
some facts have to be represented more than once within a relation!
45/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What properties do these algorithms have?
⇓
Lossless join
⇓
Lossless join + dependency
preservation
45/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What properties do these algorithms have?
⇓
Lossless join
⇓
Lossless join + dependency
preservation
45/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What properties do these algorithms have?
⇓
Lossless join
⇓
Lossless join + dependency
preservation
45/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What properties do these algorithms have?
⇓
Lossless join
⇓
Lossless join + dependency
preservation
46/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What do you need to compute using FDs?
⇓
SOME superkeys (check)
⇓
SOME superkeys (check)
ALL candidate keys
ONE minimal cover
46/50
Normalisation Algorithms
BCNF-decomposition
Repeat until no changes
– Find a problematic FD
– Split R into two smaller ones
and project FDs
3NF-decomposition
Find a minimal cover
Group FDs in the minimal cover
Remove redundant ones
Add a key (if necessary)
Project FDs
What do you need to compute using FDs?
⇓
SOME superkeys (check)
⇓
SOME superkeys (check)
ALL candidate keys
ONE minimal cover
47/50
Denormalisation
Do we need to normalize relation schemas in all cases when designing
a relational database?
Denormalisation is a design process that
happens after the normalisation process,
is often performed during the physical design stage, and
reduces the number of relations that need to be joined for certain
queries.
We need to distinguish:
Unnormalised – there is no systematic design.
Normalised – redundancy is reduced after a systematic design (to
minimise data inconsistencies).
Denormalised – redundancy is introduced after analysing the
normalised design (to improve efficiency of queries)
48/50
Trade-offs – Data Redundancy vs. Query Efficiency
Normalisation: No Data Redundancy but No Efficient Query Processing
Data redundancies are eliminated in the following relations.
STUDENT
Name StudentID DoB
COURSE
CourseNo Unit
ENROL
StudentID CourseNo Semester
However, the query for “list the names of students who enrolled in a course
with 6 units” requires 2 join operations.
SELECT Name, CourseNo
FROM Enrol e, Course c, Student s
WHERE e.StudentID=s.StudentID AND e.CourseNo=c.CourseNo
AND c.Unit=6;
48/50
Trade-offs – Data Redundancy vs. Query Efficiency
Normalisation: No Data Redundancy but No Efficient Query Processing
Data redundancies are eliminated in the following relations.
STUDENT
Name StudentID DoB
COURSE
CourseNo Unit
ENROL
StudentID CourseNo Semester
However, the query for “list the names of students who enrolled in a course
with 6 units” requires 2 join operations.
SELECT Name, CourseNo
FROM Enrol e, Course c, Student s
WHERE e.StudentID=s.StudentID AND e.CourseNo=c.CourseNo
AND c.Unit=6;
49/50
Trade-offs – Data Redundancy vs. Query Efficiency
Denormalisation: Data Redundancy but Efficient Query Processing
If a student enrolled 15 courses, then the name and DoB of this student
need to be stored repeatedly 15 times in ENROLMENT.
ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12
Michael 123458 21/04/1985 COMP2400 2009 S2 6
The query for “list the names of students who enrolled a course with 6 units”
can be processed efficiently (no join needed).
SELECT Name, CourseNo FROM Enrolment WHERE Unit=6;
49/50
Trade-offs – Data Redundancy vs. Query Efficiency
Denormalisation: Data Redundancy but Efficient Query Processing
If a student enrolled 15 courses, then the name and DoB of this student
need to be stored repeatedly 15 times in ENROLMENT.
ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12
Michael 123458 21/04/1985 COMP2400 2009 S2 6
The query for “list the names of students who enrolled a course with 6 units”
can be processed efficiently (no join needed).
SELECT Name, CourseNo FROM Enrolment WHERE Unit=6;
50/50
(credit cookie) Raymond F. Boyce (1947-1974)
“SEQUEL: A Structured English Query Language”,
D.D. Chamberlin and R.F. Boyce,
Proc. ACM SIGMOD Workshop on Data Description, Access and Control,
Ann Arbor, Michigan (May 1974)
http://www.almaden.ibm.com/cs/people/chamberlin/sequel-1974.pdf
http://www.almaden.ibm.com/cs/people/chamberlin/sequel-1974.pdf