Normal Forms &
Normalization
Vu Tuyet Trinh
trinhvt@[Link]
Department of Information Systems, School of Information Technolog
Hanoi University of Technology
Database Design
Extended Entity Relationship
Top Down
Conceptual/Abstract View
Functional Dependencies
1.
2.
3.
Bottom Up
Synthesise relations
List all attributes
Consider the relationships between them
Decompose attributes into tables in order to eliminate the
redundancy.
Using functional dependencies
toSynthesise relations
studno
studno
studno
familyname
studno
givenname
studno
hons
studno
tutor
studno
slot
studno
year
studno, courseno
studno, courseno
courseno
courseno
courseno
lecturer
lecturer
lecturer
roomno
roomno
roomno
STUDENT
(studno,givenname,familyname,hons,tutor,slot,year)
labmark
exammark
courseno
subject
equip
lecturer
roomno
appraiser
lecturer
roomno
appraiser
ENROL(studno,courseno,labmark,exammark)
COURSE(courseno,subject,equip)
STAFF(lecturer,roomno,appraiser)
hons
hons
year
year
yeartutor
yeartutor
stud
no
s1
s1
s1
s2
s2
s3
s4
s5
s6
null
null
s7
year
yeartutor
year
yeartutor
name
tutor
jones
jones
jones
brown
brown
smith
blogg
jones
peters
null
null
patel
bush
bush
wibby
kahn
kahn
goble
goble
zobel
kahn
capon
null
null
YEAR(year,yeartutor)
roomn
o
2.26
2.26
2.26
IT206
IT206
2.82
2.82
2.34
A17
A14
null
null
SCHOOL(hons,faculty)
course no
labmark
subject
cs250
cs260
cs270
cs250
cs270
cs270
cs280
cs250
cs250
null
cs290
null
65
80
47
67
65
49
50
0
2
null
null
null
prog
graphics
elecs
prog
elecs
comms
design
prog
prog
null
specs
null
F
studno name, tutor
tutor roomno
roomno tutor
courseno subject
studno, courseno labmark
faculty
hons
F+
studno, courseno name partial
studno roomno
transitive
Process of Normalization
Represent all user views (e.g forms, reports etc) as a
collection of relations
Normalize these relations
Combine relations that have exactly the same primary
key/s.
First Normal Form (1NF)
Definition
there are no repeating groups.
a unique key has been identified for each relation
all attributes are functionally dependent on all or part of the key.
Example
STUDENT_DETAILS
(studno, name, tutor, roomno, {courseno, labmark, subject})
studno name, tutor
courseno subject
tutor roomno, roomno tutor
studno, courseno labmark
STUDENT
(studno, name, tutor, roomno)
studno name, tutor
tutor roomno,
roomno tutor
ENROL (studno, courseno, subject, labmark)
courseno subject
studno, courseno labmark
Second Normal Form (2NF)
Definition
the relation is in 1 NF
all non-key attributes are fully functionally dependent on the
entire key
partial dependency has been removed
Example
ENROL (studno, courseno, subject, labmark)
courseno subject
studno, courseno labmark
ENROL (studno, courseno, labmark)
studno, courseno labmark
COURSE (courseno, subject)
courseno subject
Third Normal Form (3NF)
Definition
the relation is in 2NF
all transitive dependencies have been removed.
Transitive dependency: non-key attribute dependent on another
non-key attribute.
STUDENT (studno, name, tutor, roomno)
studno name, tutor
tutor roomno
roomno tutor
STUDENT (studno, name, tutor)
studno name, tutor
TUTOR (tutor, roomno)
tutor roomno
roomno tutor
Example
STUDENT (studno, name, tutor)
studno name, tutor
TUTOR (tutor, roomno)
tutor roomno
roomno tutor
ENROL
(studno, courseno, labmark)
studno, courseno labmark
COURSE (courseno, subject)
courseno subject
Boye-Codd Normal Form (BCNF)
Definition
the relation is in 3NF
any remaining anomalies that result form functional
dependencies have been removed.
More Normal Forms
Fourth Normal Form (4NF)
Fifth Normal Form (5NF)
the relation is in BCNF
any multivalued dependencies have been removed.
the relation is in 4NF
any remaining anomalies that result form join dependencies
have been removed.
Remarks
only in rare situations that a relation in 3NF is not in 4NF or
5NF.
most relations that are in 3NF are also in BCNF.
Lossless or Non-additive Join
Given R ~ a relational scheme, F ~ a set of functional
dependencies on R.
Decomposition R = (R1, R2)
The decomposition of R is non-additive if at least one of
the following functional dependencies are in F+
R1 R2 R1
R1 R2 R2
The
decomposition of R is non-additive if for every state r
of R that satisfies F
<R1> (r)* ...* <Rm> (r) = r
Lossless or Non-additive Join
ENROL (studno, courseno, subject, labmark)
courseno subject
studno, courseno labmark
COURSE (courseno, subject)
courseno subject
ENROL (studno, courseno, labmark)
studno, courseno labmark
ENROL COURSE = courseno
courseno subject
(courseno, subject) = COURSE
Lossless or Non-additive Join
STUDENT
studno name
s1
jones
s2
brown
s3
smith
s4
bloggs
s5
jones
s6
peters
STUDENT1
studno name
s1
jones
s2
brown
s3
smith
s4
bloggs
s5
jones
s6
peters
STUDENT1
tutor
bush
kahn
goble
goble
zobel
kahn
tutor
bush
kahn
goble
goble
zobel
kahn
roomno
2.26
IT206
2.82
2.82
2.34
IT206
studno name
studno tutor
studno name
studno tutor
tutor roomno
roomno tutor
TUTOR
tutor
kahn
bush
goble
zobel
roomno
IT206
2.26
2.82
2.34
tutor roomno
roomno tutor
TUTORS = STUDENT
Dependency Preservation
The union of dependencies that hold on the individual
relations in decomposition D must be equivalent to F.
Given F on R, F(Ri) where Ri R
is the set of dependencies XY in F+ such that the
attributes in X Y are all contained in Ri
Decomposition D = {R1, R2, ..., Rm} of R is dependency
preserving w.r.t. F if
(F(R1)) .... F(Rm)))+ = F+
Given the restriction of functional dependencies to a
relation is the fds that involve attributes of that relation Fi
for Ri
n
n
U Fi F possible, but...
(U Fi)+ = F+
i=1
i =1
Dependency Preservation
STUDENT
studno name
s1
jones
s2
brown
s3
smith
s4
bloggs
s5
jones
s6
peters
STUDENT'
studno name
s1
jones
s2
brown
s3
smith
s4
bloggs
s5
jones
s6
peters
studno name
studno tutor
tutor
bush
kahn
goble
goble
zobel
kahn
roomno
2.26
IT206
2.82
2.82
2.34
IT206
appraiser
capon
watson
capon
capon
watson
watson
studno name
studno tutor
tutor roomno
tutor appraiser
roomno tutor
roomno appraiser
studno appraiser
studno roomno
studno appraiser
studno roomno
tutor
bush
kahn
goble
goble
zobel
kahn
TUTOR
studno
s1
s2
s3
s4
s5
s6
STUDENT
roomno
2.26
IT206
2.82
2.82
2.34
IT206
appraiser
capon
watson
capon
capon
watson
watson
* TUTOR = STUDENT
Designing a relational schema
Build a relational database
without redundancy
normalisation
without loss of information or gain of data
lossless join decomposition
without losing dependency integrity
dependency preservation
Exercises
10
