Chapter 15

Advanced Normalization

Pearson Education © 2014

Chapter 15 - Objectives
Normal forms that go beyond Third Normal
Form (3NF), which includes Boyce-Codd
Normal Form (BCNF), Fourth Normal Form
(4NF), and Fifth Normal Form (5NF).

How to identify Boyce–Codd Normal Form

(BCNF).

How to represent attributes shown on a

report as BCNF relations using normalization.
2
Pearson Education © 2014
Chapter 15 - Objectives
Concept of multi-valued dependencies and
Fourth Normal Form (4NF).

The problems associated with relations that

break the rules of 4NF.

How to create 4NF relations from a relation,

which breaks the rules of to 4NF.

3
Pearson Education © 2014
Boyce–Codd Normal Form (BCNF)
Based on functional dependencies that take
into account all candidate keys in a relation,
however BCNF also has additional constraints
compared with the general definition of 3NF.

Boyce–Codd normal form (BCNF)

A relation is in BCNF if and only if every
determinant is a candidate key.

4
Pearson Education © 2014
Boyce–Codd Normal Form (BCNF)
Difference between 3NF and BCNF is that for a
functional dependency A → B, 3NF allows this
dependency in a relation if B is a primary-key
attribute and A is not a candidate key.
Whereas, BCNF insists that for this dependency
to remain in a relation, A must be a candidate
key.

Every relation in BCNF is also in 3NF. However,

a relation in 3NF is not necessarily in BCNF.
5
Pearson Education © 2014
Boyce–Codd Normal Form (BCNF)
Violation of BCNF is quite rare.

The potential to violate BCNF may occur in a

relation that:
contains two (or more) composite candidate keys;
the candidate keys overlap, that is have at least
one attribute in common.

6
Pearson Education © 2014
Review of Normalization (UNF to
BCNF)

7
Pearson Education © 2014
Review of Normalization (UNF to
BCNF)
StaffProperyInspection in UNF
Must handle multi-valued attribute to get to 1NF

8
Pearson Education © 2014
Review of Normalization (UNF to
BCNF)
StaffPropertyInspection in 1NF
2 tuples -> 5 tuples

9
Pearson Education © 2014
Identify all Functional
Dependencies in 1NF version

10
Pearson Education © 2014
1NF -> 2NF
1NF
StaffPropertyInspection (propertyNo, iDate, iTime,
pAddress, comments, staffNo, sName, carReg)
Primary key: propertyNo, iDate
Functional dependencies fd1 to fd6 (see previous
slide)
1NF -> 2NF
Remove partial fd (fd2): propertyNo -> pAddress
Create 2 tables from StaffPropertyInspection
PropertyInspection & Property

Pearson Education © 2014

2NF -> 3NF
2NF
PropertyInspection (propertyNo, iDate, iTime,
comments, staffNo, sName, carReg)
Property (propertyNo, pAddress)
2NF -> 3NF
Remove transitive fd (fd3) from PropertyInspection
fd1 propertyNo, iDate -> … staffNo..
fd3 staffNo-> sName
Create 2 tables from PropertyInspection
PropertyInspect & Staff

Pearson Education © 2014

3NF Schema
PropertyInspect (propertyNo, iDate, iTime,
comments, staffNo, carReg)
fd1’ propertyNo, iDate -> iTime, comments,
staffNo, sName, carReg
fd4 staffNo, iDate -> carReg
fd5’ carReg, iDate, iTime -> propertyNo,
commends, staffNo
fd6’ staffNo, iDate, iTime -> propertyNo, comments
Property (propertyNo, pAddress)
fd2 propertyNo -> pAddress
Staff (staffNo, sName)
fd3 staffNo -> sName
Pearson Education © 2014
3NF -> BCNF
All determinants (lhs) must be candidate keys
Staff and Property in BCNF
PropertyInspect: not in BCNF
fd4 staffNo, iDate -> carReg
Staff assigned same car for the whole day
staffNo, iDate is not a candidate key for
PropertyInspect
Staff could inspect >1 properties on the same day
(domain knowledge)
Create two new relations from PropertyInspect
Inspection (propertyNo, iDate, iTime, comments,
staffNo)
StaffCar (staffNo iDate, carReg) Pearson Education © 2014
BCNF Schema
Inspection (propertyNo, iDate, iTime,
comments, staffNo)
fd1’’ propertyNo, iDate -> iTime, comments,
staffNo, sName
fd5’’ iDate, iTime -> propertyNo, comments,
staffNo
fd6’ staffNo, iDate, iTime -> propertyNo, comments
Property (propertyNo, pAddress)
fd2 propertyNo -> pAddress
Staff (staffNo, sName)
fd3 staffNo -> sName
StaffCarReg (staffNo, iDate, carReg)
fd4 staffNo, iDate -> carReg
Pearson Education © 2014
Review of Normalization (1NF to
BCNF)

16
Pearson Education © 2014
Fourth Normal Form (4NF)
Multi-valued Dependency (MVD)
Dependency between attributes (for example, A,
B, and C) in a relation, such that for each value of
A there is a set of values for B and a set of values
for C. However, the set of values for B and C are
independent of each other.
Defined as a relation that is in Boyce-Codd
Normal Form and contains no nontrivial multi-
valued dependencies.

17
Pearson Education © 2014
Fourth Normal Form (4NF)
MVD between attributes A, B, and C in a
relation using the following notation:
A −>> B
A −>> C

18
Pearson Education © 2014
Example
BranchStaffOwner
Has two independent, mulivalued dependencies in
same table:
branchNo ->> sName (branches have multiple staff)
branchNo ->> oName (branches have multiple properties
which may have different owners)
End up having to duplicate tuples to show each
staff member with each owner
E.g., add a new staff member, have to add 2 new tuples,
one for each oName
Solution: make a separate relation for each
dependency
Pearson Education © 2014
4NF - Example

20
Pearson Education © 2014
Fifth Normal Form (5NF)
Only rarely does a 4NF not conform to 5NF
In 5NF if
cannot be decomposed into further relations with
a lossless join
i.e., if you decompose a table into multiple tables
If you rejoin it with a natural join
• You get original table back, with no errors

21
Pearson Education © 2014
Fifth Normal Form (5NF)
In other words, in 5NF, all relations are
decomposed into as many relations as possible
without introducing errors
All tables are key, and attributes that depend on
key; no other fd

22
Pearson Education © 2014
5NF
Do NOT decompose tables if all attributes
depend on same key
E.g., <SSN, Name, Birthdate, Zip> stays in one
table
Do not decompose into
<SSN, Name>
<SSN, Birthdate>
<SSN, Zip>

Pearson Education © 2014

5NF – Example (table is in 4NF)
Traveling Salesman Brand Product Type

Jack Schneider Acme Vacuum Cleaner

Jack Schneider Acme Breadbox

Mary Jones Robusto Pruning Shears

Mary Jones Robusto Vacuum Cleaner

Mary Jones Robusto Breadbox

Mary Jones Robusto Umbrella Stand

Louis Ferguson Robusto Vacuum Cleaner

Louis Ferguson Robusto Telescope

Louis Ferguson Acme Vacuum Cleaner

Louis Ferguson Acme Lava Lamp

Louis Ferguson Nimbus Tie Rack

24
Pearson Education © 2014
5NF - Example
Primary Key: Composite of all three attributes
(Traveling Salesman, Brand, Product Type)
In 4NF
Suppose there is a rule that, if a salesman offers
the same product from TWO different Brands
Then he must offer all other products from those
brands IF he sells those products at all

25
Pearson Education © 2014
5NF - Example
So, If Jack Schneider starts to sell Robusto’s
Vacuum Cleaners
He must also now sell Robusto’s Breadboxes, too,
because he sells Breadboxes
But, he doesn’t sell Pruning Shears or Umbrella Stands
(from Robusto) or Lava Lamps (from Acme)
That’s okay
If not in 5NF,
Need logic in the insert function to enforce rules
Add 2 tuples
<Jack Schneider, Robusto, Vacuum Cleaner>
<Jack Schneider, Robusto, Breadbox>
26
Possibility of update/insert/deletion errors Pearson Education © 2014
5NF - Example
Instead, decompose into 3 relations:
Traveling Salesman -> Product Type
Traveling Salesman -> Brand
Brand -> Product Type
Now, table design excludes possibility of
inconsistencies
He starts selling Robusto Vaccuum cleaners
Add <Jack Schneider, Robusto> to
TravellingSalesman+Brand table
Captures that he sells Breadboxes and Vacuum
Cleaners from Robusto and Acme
27
Pearson Education © 2014
 5NF - Example Traveling Salesman

Jack Schneider
Brand

Acme
Traveling Salesman Product Type Mary Jones Robusto
Jack Schneider Vacuum Cleaner Louis Ferguson Robusto
Jack Schneider Breadbox Louis Ferguson Acme
Mary Jones Pruning Shears Louis Ferguson Nimbus
Mary Jones Vacuum Cleaner

Mary Jones Breadbox

Brand Product Type
Mary Jones Umbrella Stand
Acme Vacuum Cleaner
Louis Ferguson Vacuum Cleaner
Acme Breadbox
Louis Ferguson Telescope
Acme Lava Lamp
Louis Ferguson Lava Lamp
Robusto Pruning Shears
Louis Ferguson Tie Rack
Robusto Vacuum Cleaner

Robusto Breadbox

Robusto Umbrella Stand

Robusto Telescope

Nimbus 28
Tie Rack
Pearson Education © 2014
5NF - Example
Need to join all 3 relations to get original
relation
Can get spurious tuples by just joining two relations
E.g., join <Jack Schneider, Acme> with <Acme, Lava
Lamp>
Conclude that Jack sells Acme Lava Lamps and he
doesn’t
Must join with all 3 relations
<Jack Schneider, Acme> with
<Jack Schneider, Vacuum Cleaner> AND <Jack Schneider,
Breadbox> with
<Acme, Vacuum Cleaner> <Acme, Breadbox> <Acme,
Lava Lamp> 29
Pearson Education © 2014
Normalization Summary
As we normalize, we change schema to contain
more and more tables with fewer and fewer
attributes in each table
Reduces redundancy
BUT need to do joins to answer queries
E.g., can get sName for a given date, time an property
from StaffPropertyInspection (2NF)
Need to join PropertyInspect and Staff on staffNo to get
the name in 3NF
Classic time/space trade-off in CS

30
Pearson Education © 2014
Normalization Summary
If you do an object-oriented design of your
database, you will be generally be in 4NF
E.g., classes (relations) for: property, staff, owners,
cars, etc…
Attributes for each class in the relation for that
class

31
Pearson Education © 2014