Normalization (Review)

Database Systems
 WARNING

• This stuff can get confusing.

• So concentrate. This is the science bit.

By Stanley Githinji
Redundancy & Normalisation

Redundant data
• Normalisation
•• Is data
Aims to that _already_
reduce exists elsewhere in the
data redundancy
database

• Redundancy is expressed in terms of dependencies

• Redundant data leads to various subtle, but
important problems:
• Normal forms are defined that do not have certain
types of dependency
• INSERT anomalies
• UPDATE anomalies
• DELETE anomalies

By Stanley Githinji
 What is Normalization?
• It is a mathematical process that converts
one set of formulae into another equivalent
set of formulae. That is it.

• This only makes sense if you think of

information in terms of propositions –
statements of fact.

• Do not think in terms of objects and entities

at the logical level. This is not how we
communicate information.
By Stanley Githinji
 Propositions Example
Program(X-Factor) & Host(Kate)
Program(I’m a celebrity) & Host(Ant) & Host(Dec)
Program(Big Brother) & Host(Davina) & coHost(Dermot)

Unnormalized Reality TV A mess

Program Host coHost
By rearranging these
X-Factor Kate null propositions into different
I’m a Celebrity Ant null forms we can achieve a
Dec better structure for
manipulating the info…
Big Brother Davina Dermot this is Normalization.
By Stanley Githinji
'Zeroth' and 1st Normal Form
• In
A relation
the original
is saiddefinition
to be in first
of the
normal
relational
form
model if
(1NF)
• All data values are atomic
• All data values should be atomic
• No duplicate columns
• This means that table entries should be single
• A 'relation'
values, not that is not in 1NF
be repeating is saidorto‘complex’
groups be in 'zeroth'
normal
objects form (0NF), and is unnormalized

By Stanley Githinji
 0NF to 1NF
To convert a 0NF ‘relation’ to a 1NF relation:
Split up any non-atomic values

0NF - Teaching 1NF - Teaching

Module Dept Lecturer Text Module Dept Lecturer Text
M1 D1 L1 T1 M1 D1 L1 T1
T2 M1 D1 L1 T2
M2 D1 L1 T1 M2 D1 L1 T1
T3 M2 D1 L1 T3
M3 D1 L2 T4 M3 D1 L2 T4
M4 D2 L3 T1 M4 D2 L3 T1
T5 M4 D2 L3 T5
M5 D2 L4 T6 M5 D2 L4 T6
By Stanley Githinji
 Back to Reality
Program(X-Factor) & Host(Kate)
Program(I’m a celebrity) & Host(Ant) & Host(Dec)
Program(Big Brother) & Host(Davina) & coHost(Dermot)

Program(X-Factor) & Host(Kate)

Program(I’m a celebrity) & Host(Ant)
Program(I’m a celebrity) & Host(Dec)
Program(Big Brother) & Host(Davina) & coHost(Dermot)

By Stanley Githinji
ONF - Reality TV
Program Host coHost
X-Factor Kate null
I’m a Celebrity Ant null
Dec
Big Brother Davina Dermot

1NF - Reality TV
Program Host coHost
X-Factor Kate null
I’m a Celebrity Ant null
I’m a Celebrity Dec null
Big Brother Davina Dermot
By Stanley Githinji
What have we done there?
• We took unformatted information and put it
into a format that allows it to be represented
as… a mathematical relation.

• 1NF is different from subsequent

normalizaiton - it essentially says, all data
must fit into relations.

• I.e. A table = relation by 1NF

By Stanley Githinji
 But there are still
problems in 1NF…
1NF - Teaching • INSERT anomalies
Module Dept Lecturer Text Can't add a module with
no texts
M1 D1 L1 T1
M1 D1 L1 T2
• UPDATE anomalies
M2 D1 L1 T1
M2 D1 L1 T3 To change lecturer for
M1, we have to
M3 D1 L2 T4
change two rows
M4 D2 L3 T1
M4 D2 L3 T5
M5 D2 L4 T6 • DELETE anomalies
If we remove M3, we
remove L2 as well
By Stanley Githinji
 Functional Dependencies
• Redundancy
A set of attributes,
can often
A, functionally
be describeddetermines
as a functional
another
dependency
set, B, if:
• A functional dependency (FD) is a semantic link between
• Whenever
two sets oftwo rows ofinthe
attributes relation have the same value
a relation
for all attributes in A then they also have the same value
• for all attributes in B.
Another part of 'normalisation‘ is to remove undesirable
FDs
• We say: A  B

By Stanley Githinji
 Why care about FD?
• Not
We define
all FDsacause
set ofa'normal
problem,
forms‘
but…

• We
Eachidentify
normalvarious
form has
sorts
fewer
of FD
FDs
that
than
do.
the last

• Since
Each normal
FDs represent
form removes
redundancy,
a typeeach
of FDnormal
that isform
a
has less redundancy than the last
problem.

• We will also need a way to remove FDs.

By Stanley Githinji
 Properties of FDs
In any relation:
• The primary key FDs any set of attributes
in that relation: K  X

Primary key

Set of other attributes

• Any set of attributes is of course FD on itself:

XX
By Stanley Githinji
 Rules for FD’s

• Reflexivity:
If B is a subset of A then: A  B

• Augmentation:
If A  B then A U C  B U C

• Transitivity:
If A  B and B  C then A  C
By Stanley Githinji
 FD Example
• The primary key is {Module, Text} so
1NF - Teaching
{Module, Text}  {Dept, Lecturer}
Module Dept Lecturer Text
• 'Trivial'
M1 D1FDs, L1
eg: T1
M1
{Text, D1
Dept} L1{Text}
T2
M2 D1 L1 T1
{Module}  {Module}
M2 D1 L1 T3
{Dept, D1
M3 Lecturer}
L2  {T4
}
M4 D2 L3 T1
M4 D2 L3 T5
M5 D2 L4 T6

By Stanley Githinji
 FD Example
• Other FDs are
1NF
• -{Module}
Teaching  {Lecturer}
Module Dept Lecturer
• {Module} Text
 {Dept}
• {Lecturer}
M1 D1 
L1{Dept}
T1
M1 D1 L1 T2
M2 D1 L1 T1
• These are non-trivial and don't come from the
M2 D1 L1 T3
M3 primary
D1 key L2 T4
M4 D2 L3 T1
M4 D2 L3 T5
M5 D2 L4 T6

By Stanley Githinji
 FD Diagrams

Module Dept Lecturer Text

{Module, Text} is the primary key, so we put a double box around them
{Lecturer}  {Dept}, so we have an arrow from Lecturer to Dept
{Module}  {Dept} and {Module}  {Lecturer}, so we have
{Module}  {Dept, Lecturer}

By Stanley Githinji
 Partial FDs and 2NF
Partial
• 2nd FDs: form
normal
A relation is in second normal form (2NF) if it is in 1NF
• and
A FD,noAnon-primary-key attribute
 B is a partial FD, if some is attribute
partially of A
can be removed
dependent on theand the FDkey
primary still holds

• Formally, there is some proper subset of A, C  A,

such that C  B

i.e. a member of the set

A is superfluous
By Stanley Githinji
 Second Normal Form
1NF - Teaching
• 1NF is not in 2NF
Module Dept Lecturer Text
M1 D1 L1 T1 We have the FD:
M1 D1 L1 T2
{Module, Text} 
M2 D1 L1 T1
{Lecturer, Dept}
M2 D1 L1 T3
M3 D1 L2 T4 but also…
M4 D2 L3 T1 {Module}  {Lecturer, Dept}
M4 D2 L3 T5
M5 D2 L4 T6 • And so Lecturer and
Dept are partially
Module Dept Lecturer Text dependent on the
primary key
By Stanley Githinji
 So what do we do?
• Say we have a relation • Well it turns out that
with scheme S and the we can split the
full FD A  B.
relation into two
• We can organize this to parts:
make sure A ∩ B = { }.
(ie. no trivial
dependencies) R1, with scheme: C U A
R2, with scheme: A U B
• Let C = S – (A U B)
• The original relation can
• So we have be recovered as the
• A – attributes on the
natural join of R1 and
LHS of the FD
• B – attributes on the R2
RHS of the FD
• C – all other attributes Vital point
By Stanley Githinji
 1NF to 2NF – Example
1NF - Teaching 2NF - Modules 2NF - Text
Module Dept Lecturer Text Module Dept Lecturer Module Text
M1 D1 L1 T1 M1 D1 L1 M1 T1
M1 D1 L1 T2 M2 D1 L1 M1 T2
M2 D1 L1 T1 M3 D1 L2 M2 T1
M2 D1 L1 T3 M4 D2 L3 M2 T3
M3 D1 L2 T4 M5 D2 L4 M3 T4
M4 D2 L3 T1 M4 T1
M4 D2 L3 T5 M4 T5
M5 D2 L4 T6 M1 T6

Module Dept Lecturer Text Module Dept Lecturer Module Text

By Stanley Githinji
Problems Resolved in 2NF
Those 1NF problems: • In 2NF the first two
are resolved, but not
• INSERT – Can't add a module with no texts
the third one
• UPDATE – To change lecturer for M1, we have to
change two rows 2NF - Modules
• DELETE – If we remove M3, weModule
removeDept
L2 asLecturer
well, and
lose information we might not have
M1 wanted
D1 to! L1
M2 D1 L1
M3 D1 L2
M4 D2 L3
M5 D2 L4
By Stanley Githinji
Problems Remaining in 2NF
2NF - Modules
• INSERT anomalies
• Can't add lecturers who teach Module Dept Lecturer
no modules
• UPDATE anomalies M1 D1 L1
M2 D1 L1
• To change the department for L1 we must alter two
M3 D1 L2
rows
M4 D2 L3
• DELETE anomalies M5 D2 L4
• If we delete M3 we delete L2 as well

Module Dept Lecturer

By Stanley Githinji
 Transitive FDs and 3NF
• Transitive
Third normal FDs:form:
• An FD, A  C is a transitive FD, if there is
some
A set Bis such
relation thatnormal
in third A  B form
and (3NF) B if
itCis
are non-trivial
in 2NF FDs in the relation
and no non-primary-key attribute is
transitively dependent on the primary key
• I.e. There exists:
ABC

By Stanley Githinji
 Third Normal Form
2NFis–not
• This Modules
in 3NF
Module Dept Lecturer
• We M1
have the
D1 FDs: L1
{Module}
M2 {Lecturer}
D1 L1
M3
{Lecturer} D1 L2
 {Dept}
M4 D2 L3
M5
So there isD2 L4
a transitive FD from the primary key
{Module} to {Dept}

Module Dept Lecturer

By Stanley Githinji
 2NF to 3NF – Example
2NF - Modules 3NF - place 3NF - Modules
Module Dept Lecturer Lecturer Dept Module Lecturer
M1 D1 L1 L1 D1 M1 L1
M2 D1 L1 L2 D1 M2 L1
M3 D1 L2 L3 D2 M3 L2
M4 D2 L3 L4 D2 M4 L3
M5 D2 L4 M5 L4

Module Dept Lecturer Lecturer Dept Module Lecturer

By Stanley Githinji
 Problems Resolved in 3NF
• Problems in 2NF • In 3NF all of these
are resolved:
• INSERT – Can't add
lecturers who teach no 3NF - Places 3NF - Modules
modules Lecturer Dept Module Lecturer
L1 D1 M1 L1
• UPDATE – To change the L2 D1 M2 L1
department for L1 we L3 D2 M3 L2
must alter two rows L4 D2 M4 L3
M5 L4
• DELETE – If we delete
M3 we delete L2 as well
By Stanley Githinji
Normalisation and Design
• Normalisation
When you findisyou
integrally
have a related
non-3NFtoDB:
DB
design:
• Identify the FDs that are causing a problem
• A database should normally be in 3NF at least
• Think if they will lead to any insert, update, or delete
anomalies
• Try to remove
If your them to a non-3NF DB, then you
design leads
might want to revise it

By Stanley Githinji
 So, the story so far:
• 1NF – turn your propositions into a format
that fits relations by removing repeating
groups.

• 2NF – look for partial FD’s and separate

into another table anything that is not
functionally dependent on the full primary
key.

• 3NF – look for transitive FD’s and separate

off into a separate table.
By Stanley Githinji
1. Normalization refresher
• Normalization reduces data redundancy in a database

• By doing so it eliminates serious manipulation

anomalies.

• Normalization is ultimately just rearranging

propositions to a better structure.

• This is done by identifying and removing damaging

functional dependencies.

By Stanley Githinji
 Normal forms so Far…
• First normal form
• All data values are
atomic, and so
everything fits into a • Third normal form
mathematical relation. • As 2NF plus no non-
primary-key attribute
depends transitively on
• Second normal form the primary key
• As 1NF plus no non-
primary-key attribute
is partially dependant
on the primary key

By Stanley Githinji
2. Normalization Example
• Consider
Columnsa table representing orders in an
online
• Orderstore
• Product
• Customer
• Each entry in the table represents an item on
• Address
a particular order. (thinking in terms of
• Quantity
records. Yuk.)
• UnitPrice

• Primary key is {Order, Product}

By Stanley Githinji
Functional Dependencies
Each order is for a single {Order}  {Customer}
customer

Each customer has a single {Customer}  {Address}

address

Each product has a single {Product}  {UnitPrice}

price

FD’s 1 and 2 are transitive {Order}  {Address}

By Stanley Githinji
 Example – FD Diagram

1NF
R
Order Product Customer Address Quantity UnitPrice

By Stanley Githinji
 Normalisation to 2NF
• Remember 2nd normal form means no partial
dependencies on the key. But we have:

{Order}  {Customer, Address}

{Product}  {UnitPrice}

And a primary key of: {Order, Product}

• So to get rid of the first FD we project over:

{Order, Customer, Address}
and
{Order, Product, Quantity and UnitPrice}

By Stanley Githinji
 Normalisation to 2NF
1NF
R
Order Product Customer Address Quantity UnitPrice

R1 Order Customer Address

R2 Order Product Quantity UnitPrice

By Stanley Githinji
 Normalisation to 2NF
• R1 is now in 2NF, but there is still a partial FD in R2:

{Product}  {UnitPrice}

Order Product Quantity UnitPrice

• To remove this we project over:

{Product, UnitPrice} and {Order, Product, Quantity}

By Stanley Githinji
 Normalisation to 2NF
1NF R2
Order Product Quantity UnitPrice

2NF
R3 R4
Product UnitPrice Order Product Quantity

By Stanley Githinji
 Now let’s go 3NF…
• R has now been split into 3 relations - R1, R3, and
R4… but R1 has a transitive FD on its key…

R1 Order Customer Address

{Order}  {Customer}  {Address}

• To remove this problem we project R1 over:

{Order, Customer} and {Customer, Address}

By Stanley Githinji
 So more chopping…

2NF
R1 Order Customer Address

3NF
R5 Order Customer R6 Customer Address
By Stanley Githinji
 Let’s summarize that:
• 1NF:
{Order, Product, Customer, Address, Quantity, UnitPrice}

• 2NF:
{Order, Customer, Address}
{Product, UnitPrice}
{Order, Product, Quantity}

• 3NF:
{Product, UnitPrice}
{Order, Product, Quantity}
{Order, Customer}
{Customer, Address}
By Stanley Githinji
 So this…

0NF

R
Order Product Customer Address Quantity UnitPrice

By Stanley Githinji
 has become this…

3NF
Prices Product UnitPrice

Amounts Order Product Quantity

Purchase Order Customer

Details Customer Address

By Stanley Githinji
3. Boyce-Codd Normal Form
• Did Codd
Edgar make any
F. Codd.
mistakes alongdb’s
Revolutionized the way?
by inventing the
RM at IBM in 1970
• Nulls

Very clever. complex

• Forbidding
objects in 1NF.
English. Obviously.
• Not initially seeing that
Primary
Also keys are
responsible fora
allsuperfluous
that DBS concept.
coursework you
•have to do….
Initially thinking 3NF was
By Stanley Githinji
enough.
 The Primary Key Myth
• In all our discussions so far we have
considered the existence of a primary key.

• What if there is more than one column(s)

which could be the primary key? Which of
these candidate key should we pick?

• None - Candidate keys are the vital concept.

Calling one ‘primary’ is pretty unimportant.

By Stanley Githinji
 But hold on there
sherlock?
• When we defined our normal forms we always talked
about the primary key.

• This was fine if we only had one candidate key, but

what if there are more several candidate keys?

• This realization changed the requirement of having

data in 3NF to requiring Boyce-Codd Normal Form

• … which relies on a concept called prime attributes.

By Stanley Githinji
 Prime Attributes
• An attribute of a relation is called prime if it is part
of a candidate key, and non-prime otherwise.

2NF definition alters:

As 1NF and in addition As 1NF and in addition
no non-primary-key no non-prime
attribute is partially attribute is partially
dependant on the dependent on any
primary key. candidate key.

n.b. these are the same if there

By Stanley Githinji is only one candidate key
 3NF Revisited
• The same change is made to 3NF:

3NF definition alters:

As 2NF and in addition As 2NF and in addition
no non-primary-key no non-prime
attribute depends attribute is transitively
transitively on the dependent on any
primary key candidate key.

By Stanley Githinji
 Boyce-Codd Normal Form

• Going to explain this by Schema:

example.
• Each course can have
several lab session slots.
• Consider a relation, Labs,
which stores information • Each student taking a
about the enrollments for course is assigned to a
the various lab sessions single lab session slot for
on computer science it.
courses :
• Each lab session slot is
managed by a single
lecturer.
By Stanley Githinji
 Example: Labs Relation

Student Subject Lecturer

Pauline Java Jim
Pauline Databases Peter
Enden Java Jim
Enden Databases Peter
Blom Java Tim

Candidate keys: {Student, Subject} and {Student, Lecturer}

By Stanley Githinji
 FDs in the Labs Relation
The labs table has the following non-trivial FDs:

• For each lab subject a student is only taught Lecturer:

{Student, Subject}  {Lecturer}
• A lecturer only teaches one lab subject :
{Lecturer}  {Subject}

Student Subject Lecturer

By Stanley Githinji
 Can we normalize?
Student Subject Lecturer

Pauline Java Jim {Student, Subject}

Pauline Databases Peter  {Lecturer}
Enden Java Jim
Enden Databases Peter {Lecturer}  {Subject}
Blom Java Tim

• 1NF - Any repeating groups? NO

• 2NF - Are there any partial dependencies? NO
• 3NF - Is {Student, Subject}  {Lecturer}  {Subject} cyclic? NO
(The key at the start is {Student, Subject} not {Subject} )

…so the table is already in 3NF

By Stanley Githinji
But it still has Anomalies!
INSERT anomolies 3NF Labs
You can’t setup an Student Subject Lecturer
empty lab session
Pauline Java Jim
UPDATE anomolies Pauline Databases Peter
Enden Java Jim
Gary taking over Jim’s Enden Databases Peter
Java lab involves Blom Java Tim
changing two rows.

DELETE anomolies Oh for pete's

sake, so much
Deleting Blom, means
for 3NF…
losing all knowledge of
Tim’s Java lab.
By Stanley Githinji
4. Boyce-Codd Normal Form
• It was quickly found that 3NF isn't perfect.

• But ONLY on the rare occurrences that:

(a) Candidate keys are composite
(b) there is more than one candidate key
(c) those candidate keys overlap.

• The problem is being caused by dependence between

parts of the keys themselves:

{Lecturer}  {Subject} but

Subject by itself is not a key:
Student Subject Lecturer
By Stanley Githinji
 The Solution - BCNF

• A relation is in Boyce-Codd normal form (BCNF)

if for every FD A  B either:
• B is contained in A (the FD is trivial), or
• A contains a candidate key of the relation

• This is the same as 3NF except we don’t allow B to

be prime (part of a candidate key)

• Remember if there is only one candidate key then

3NF and BCNF are the same thing.

By Stanley Githinji
 So what do we do?
3NF
Student Subject Lecturer

BCNF
Student Subject Subject Lecturer

NO! - because we have lost information this way. We

have lost the links between an individual 'lab' and the
person in it!
By Stanley Githinji
We would incorrectlly have:
Student Subject Subject Lecturer

Pauline Java Java Jim

Pauline Databases Java Tim
Enden Java Databases Peter
Enden Databases
Blom Java

If we joined them back together

we would have no way of
knowing which people who did
Java were in Tim’s session or
By Stanley Githinji Jim’s session.
 BCNF completed
• If you fail BCNF, there is something wrong with
your propositions…
• …they were actually about two things, at least one
of which you did not identify correctly.

Enrollment Labs
Student Subject Lab Lab Lecturer

Pauline Java 1 1 Jim

Pauline Databases 3 2 Tim
Enden Java 1 3 Peter
Enden Databases 3
Blom Java 2
By Stanley Githinji
 Higher Normal Forms
• BCNF is as far as we
1NF Relations
can go with FDs
2NF Relations
• Higher normal forms 3NF Relations
are based on other
sorts of dependency BCNF Relations

• Fourth normal form 4NF Relations

removes multi-valued 5NF Relations
dependencies

• Fifth normal form

removes join
dependencies
By Stanley Githinji