CS计算机代考程序代写 Functional Dependencies database algorithm 1/50

1/50

Week 6 Workshop – Normalisation

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

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

R
Name StudentID Email
Mike 123456 .au
Tom 123123 .au

R1
Name Email
Mike .au
Tom .au

R2
StudentID Email
123456 .au
123123 .au

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′};

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′};

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′};

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′};

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′};

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.

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.

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.

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 ;

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 ;

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 ;

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 ;

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

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

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

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

38/50

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

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

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

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:

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:

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:

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.

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.

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}.

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}.

C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.

43/50

The Minimal Cover – More Example

4 Remove redundant FD: {P→ LC, LC→ A} |= P→ A.
5 Thus a minimal cover is {P→ LC, LC→ AP, A→ C}.

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

C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.

43/50

The Minimal Cover – More Example

(Case Y) Find a minimal cover of F = {P→ LCA, LC→ AP, A→ C}

C} |= P→ C.
5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.

43/50

The Minimal Cover – More Example

(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 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

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

C} |= P→ C.

5 Thus a minimal cover is {P→ LA, LC→ P, A→ C}.

43/50

The Minimal Cover – More Example

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)

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)

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

Related Posts