Normalize up to BCNF, Boyce-codd normal form normalization, steps in normalizing a relation to bcnf relation
Question:
Normalize the following table. Show
all work and clearly indicate the primary and foreign keys.
R(elevator_no, building_no, building_name,
capacity, staff_no, first_name, last_name, date_examined) with the following functional
dependencies:
1. elevator_no → building_no,capacity
2.
building_no →
building_name
3.
staff_no →
first_name,last_name
4.
elevator_no,staff_no → date_examined
Normalize
table R up to BCNF.
Solution:
1NF – The table R is already in first normal
form because of atomic attributes. All the attributes of R are atomic.
2NF – Second normal form is about elimination
of partial key functional dependency. To proceed further, we need to find the
key for R. For that we need to find the how to find attribute closure for all the left hand
side attributes of the given functional dependencies.
elevator_no+
Result = building_no, capacity – from the FD elevator_no →
building_no,capacity
= building_no, capacity, building_name - from building_no →
building_name
Result of elevator_no+ does not include all
attributes of R. Hence, elevator_no cannot be the key of R.
staff_no+
Result = first_name, last_name – from
the FD staff_no → first_name,last_name
Result of staff_no+ does not include all
attributes of R. hence, staff_no cannot be the key of R.
(Elevator_no, staff_no)+
Result =
date_examined
from the FD elevator_no,staff_no → date_examined
=
date_examined, building_no, capacity
from elevator_no →
building_no,capacity
= date_examined, building_no, capacity,
building_name
from building_no
→ building_name
= elevator_no, building_no, building_name, capacity,
staff_no, first_name, last_name, date_examined
from staff_no
→ first_name,last_name
The
result includes all the attributes of R for (Elevator_no, staff_no)+.
Hence, (Elevator_no, staff_no) is the key (composite key) of R.
Do we have partial key
dependencies in R?
Yes. The following are the partial key
dependencies.
elevator_no → building_no,capacity
staff_no →
first_name,last_name
The
reason is, both elevator_no and staff_no are parts of the key of R. They can
uniquely identify some of the non-key attributes. Because of these partial key
dependencies, R is not in 2NF.
To
convert R into 2NF relations, we need to decompose R on partial key
dependencies. Thus, we get the following relations; (primary keys are
underlined)
R1
(elevator_no, building_no, capacity, building_name)
From FDs elevator_no → building_no,capacity and building_no → building_name
R2
(staff_no, first_name, last_name)
From FD staff_no → first_name,last_name
R3
(elevator_no, staff_no, date_examined)
From FD elevator_no,staff_no → date_examined
– in R3 elevator_no is one foreign key
referencing R1, and staff_no is another foreign key referencing the relation
R2.
Are R1, R2, and R3 in
2NF?
Yes. In all the relations, all non-key
attributes are fully-functionally dependent on the primary keys.
3NF – Third normal form is about elimination
of non-key dependencies, that is, a functional dependency with a non-key
attribute is dependent on another non-key attribute.
Do we have non-key dependencies
in R1?
Yes. See below;
R1 (elevator_no,
building_no, capacity, building_name)
F
= {elevator_no → building_no,capacity and building_no → building_name}
In R1 we have a non-key dependency building_no
→ building_name, that is the non-key attribute building_no uniquely determines the
other non-key attribute building_name.
R1 is in 2NF
because of no partial key dependencies and not in
3NF because of non-key dependencies.
To convert R1 into 3NF relations, decompose
R1 on non-key dependencies. Thus, we get the following relations;
R11 (elevator_no,
building_no, capacity)
From FD elevator_no
→ building_no, capacity
R12 (building_no,
building_name)
From FD building_no → building_name a non-key
dependency.
– in R12 building_no is the primary key
and in R11 building_no is the foreign key referencing the relation R12.
Do we have non-key
dependencies in R11 and R12?
No. Hence, R11 and R12 are in 3NF.
Do we have non-key
dependencies in R2 and R?
No. Hence, R2 and R3 are in 3NF.
BCNF – The determinants in a FD should be the
key for the relation.
Are R11, R12, R2, and R3
are in BCNF?
Yes. Each relation have only one
functional dependency. And the determinants of the functional dependencies are
the primary keys. Hence the relations R11, R12, R2, and R3 are in BCNF.
***************
Go to Normalization - Solved Exercises page