In the name of
ALLAH
Introduction to
Database Systems
Lecture 22
03-01-11
Fall 2010
Normalization
A step by step process to
produce more efficient and
accurate database design
Purposeis to produce an
anomaly free design
Department of Computer Science
Anomalies
A state of DB that can lead the DB
to inconsistency or incorrect state of
database
Four types of anomalies are of
concern here; Redundancy,
insertion, deletion and updation
Department of Computer Science
Normalization
A strongly recommended step
Normalized
design makes the
maintenance of database easier
Normalization applied on each
table of a DB design
Department of Computer Science
Normalization
Performed after the logical
database design
Informally also performed
during conceptual DB design
Department of Computer Science
Normalization Process
Different forms or levels of normalization
Called first, second, third and so on forms
Each form has got certain conditions
If a table fulfils the condition(s) for a
normal form then the table is in that
normal form
Department of Computer Science
Normalized DB Design
Process is applied on each table
The minimum form in which all tables
are in is called the normal form of the
entire database
Objective is to place the DB in
highest form of normalization
Department of Computer Science
Functional Dependency
Normalization is based on
functional dependencies (FDs)
A type of relationship between
attributes of a relation
Department of Computer Science
Functional Dependency
Definition: If A and B are attributes
of a relation R, then B is
functionally dependent on A if each
value of A in R is associated with
exactly one value of B; written as
A B
Department of Computer Science
Functionally Dependency
It does not mean that A derives B,
although it may be the case sometime
Means that if we know value of A then
we can precisely determine a unique
value of B
Department of Computer Science
Functional Dependency
Attribute of set of attributes on the left
side are called determinant and on the
right are called dependents
Like R (a, b, c, d, e)
a b, c, d
d d, e
Department of Computer Science
FD Example
STD(stId, stName, stAdr, prName, credits)
stId stName, stAdr, prName, credits
prName credits
Department of Computer Science
Thanks
Department of Computer Science
In the name of
ALLAH
Introduction to
Database Systems
Lecture 23
06-01-11
Fall 2010
FDs and Keys
We can determine the keys of a
table seeing its FDs
The determinant of an FD that
determines all attributes of that
table is the super key
Department of Computer Science
FDs and Keys
A minimal super key is the
candidate key, so if a
determinant of an FD determines
all attributes of that relation then
it is definitely a super key, and
Department of Computer Science
FDs and Keys
If there is no other FD where a subset of
this determinant/SK is a super key, then
it is a candidate key
So FDs help to identify keys, how
Department of Computer Science
R(a, b, c, d, e, f, g)
a, c b, d, e, f, g
c d, e
a b, d, f
f g, a, b, c, d, e
Department of Computer Science
FDs and Keys
EMP(eId, eName, eAdr, eDept, prId, prSal)
eId eName, eDept, eAdr
eId, prId prSal
STD(stId, stName, prName, adr, nic, cgpa)
stId stName, prName, adr, nic, cgpa
nic stName, prName, adr, stId, cgpa
Department of Computer Science
Inference Rules
Called inference axioms or
armstrong axioms
These are rules that establish certain
FDs from a given set of FDs
These rules are sound
Department of Computer Science
Reflexivity
If B is a subset of A then A B,
it also implies that A A
always hold, that is
stName, stAdr stName
Or stName stName
Department of Computer Science
Augmentation
If we have A B then
AC BC that is
if stId stName then
stId, stAdr stName, stAdr
Department of Computer Science
Transitivity
If
A B and B C then
A C
that is
If stId prName and prName
credits
Then stId credits
Department of Computer Science
Additivity or Union
If A B and A C then A BC
if empId eName and empId qual
Then we can write it as
empId eName, qual
Department of Computer Science
Projectivity or Decomposition
If A BC then A B and A C
if empId eName, qual
Then we can write it as
empId eName and empId qual
Department of Computer Science
Pseudotransitivity
If
A B and CB D then
AC D
if stId stName and
stName, fName stAdr
Then we can write it as
stId, fName stAdr
Department of Computer Science
Thanks
Department of Computer Science
In the name of
ALLAH
Introduction to
Database Systems
Lecture 24
10-01-11
Fall 2010
Normal Forms
First Normal Form
A relation is in first normal form
iff every attribute in every tuple
contains an atomic value
Thereis no multivaued
(repeating group) in the relation
Department of Computer Science
First Normal Form
One of the basic properties of relation
Multiple values create problems in
performing different operations, like, select
or join
Remember the treatment of multivalued
attributes in the mapping process
Department of Computer Science
First Normal Form
STD(stId, stName, stAdr, prName, bkId)
stId stName stAdr prName bkId
S1020 Sohail Dar I-8 Islamabad MCS B00129
S1038 Shoaib Ali G-6 Islamabad BCS B00327
S1015 Tahira Ejaz L Rukh Wah MCS B08945,
B06352
S1018 Arif Zia E-8, Islamabad. BIT B08474
Department of Computer Science
First Normal Form
stId bkId stName stAdr prName
S1020 B00129 Sohail Dar I-8 Islamabad MCS
S1038 B00327 Shoaib Ali G-6 Islamabad BCS
S1015 B08945 Tahira Ejaz L Rukh Wah MCS
S1015 B06352 Tahira Ejaz L Rukh Wah MCS
S1018 B08474 Arif Zia E-8, Islamabad. BIT
Mind the key please Department of Computer Science
Second Normal Form
Full functional dependency: an
attribute B is fully functionally
dependent on A if the B can be
determined by whole of A not by
any proper subset of A
Department of Computer Science
Full Functional Dependence
Consider the relation
CLASS(crId, stId, stName, fId, room, grade)
crId, stId stName, fId, room, grade
stId stName
crId fId, room
Department of Computer Science
Second Normal Form
A relation is in 2nd normal form iff it
is in the first normal form and all
non key attributes are fully
functionally dependent on key,
that is, there is no partial
dependency
Department of Computer Science
Anomalies
crId stId stName fId room grade
C3456 S1020 Suhail Dar F2345 104 B
C5678 S1020 Suhail Dar F4567 106
C3456 S1038 M Shoaib F2345 104
Department of Computer Science
Second Normal Form
CLASS(crId, stId, stName, fId, room, grade)
crId, stId stName, fId, room, grade
stId stName crId fId, room
Department of Computer Science
Anomalies
Redundancy
InsertionAnomaly
Deletion Anomaly
Updation Aomaly
Department of Computer Science
Anomalies
crId stId stName fId room grade
C3456 S1020 Suhail Dar F2345 104 B
C5678 S1020 Suhail Dar F4567 106
C3456 S1038 Shoaib Ali F2345 104 A
C5678 S1015 Tahira Ejaz F4567 106 B
Department of Computer Science
Second Normal Form
Relation is decomposed based on the FDs
CLASS(crId, stId, stName, fId, room, grade)
crId, stId stName, fId, room, grade
stId stName crId fId, room
STD(stId, stName)
COURSE(crId, fId, room)
CLASS(crId, stId, grade)
Department of Computer Science
Second Normal Form
Each of these tables is in
second normal form
Free of anomalies due to partial
dependency
Department of Computer Science
Thanks
Department of Computer Science
In the name of
ALLAH
Introduction to
Database Systems
Lecture 25
03-01-11
Fall 2010
Third Normal Form
A table is in third normal form
(3NF) iff it is in 2NF and there is
no transitive dependency, that
is, no non-key attribute is
dependent on another non-key
attribute
Department of Computer Science
Transitive Dependency
STD(stId, stName, stAdr, prName, prCrdts)
stId stName, stAdr, prName, prCrdts
prName prCrdts
Department of Computer Science
Anomalies
stId stName stAdr prName prCrdts
S1020 Sohail Dar I-8 Islamabad MCS 64
S1038 Shoaib Ali G-6 Islamabad BCS 132
S1015 Tahira Ejaz L Rukh Wah MCS 64
S1018 Arif Zia E-8, Islamabad. BIT 134
Department of Computer Science
stId stName stAdr prName
S1020 Sohail Dar I-8 Islamabad MCS
S1038 Shoaib Ali G-6 Islamabad BCS
S1015 Tahira Ejaz L Rukh Wah MCS
S1018 Arif Zia E-8, Islamabad. BIT
Department of Computer Science
prName prCrdts
MCS 68
BCS 132
BIT 134
Department of Computer Science
Third Normal Form
STD(stId, stName, stAdr, prName, prCrdts)
stId stName, stAdr, prName, prCrdts
prName prCrdts
STD (stId, stName, stAdr, prName)
PROGRAM (prName, prCrdts)
Department of Computer Science
3NF Relations
Each of the table is in 3NF
Free of all anomalies
Department of Computer Science
Boyce-Codd Normal Form
A general form of 3NF
Every relation in BCNF is in 3NF
vice-versa is not always true
3NF is checked in steps, BCNF
checked directly
Department of Computer Science
BCNF
A table is in BCNF if every
determinant is a candidate key
Situation when table in 3NF is not
in BCNF
A non-key determines a part of the
composite primary key
Department of Computer Science
BCNF
FACULTY(fId, dept, office, rank, dateHired)
fId, dept office, rank, dateHired
office dept
Table is in 3NF, not in BCNF since the office is not a
candidate key
Generates multiple overlapping candidate keys so we
have fId, office dept, rank, dateHired
Department of Computer Science
BCNF
We decompose the table again to
bring it into BCNF
FACULTY (fId, dept, office, rank, dateHired)
FACULTY(fId, office, rank, dateHred)
OFFICE(office, dept)
Department of Computer Science
Higher Normal Forms
After BCNF fourth, fifth and domain-
key normal forms exist
4NF deals with multivalued
dependency, fifth deals with possible
lossless decompositions, DKNF
reduces further chances of any
possible inconsistency
Department of Computer Science
Consistenthardwork is major
key for success in life
Department of Computer Science