BITS College
Undergraduate Program
SE241
Fundamentals of Database Systems
Normalization
Well Structured Relations
A relation that contains minimal data redundancy and allows users to
insert, delete, and update rows without causing data inconsistencies
The goal is to avoid anomalies
Insertion Anomaly–adding new rows forces user to create duplicate data
Deletion Anomaly–deleting rows may cause a loss of data that would be
needed for other future rows
Modification Anomaly–changing data in a row forces changes to other
rows because of duplication
General rule of thumb: A table should not pertain to more than one
entity type (to have a well structured relation)
Example 1
EmpID Fname Lname SkillID Skill SkillType School SchoolAD SkillLevel
12 Almaz Mekuria 2 SQL Database AAU Sidist_Kilo 5
16 Abebe Alemu 5 C++ Programming St. Mary Mexico 6
12 Almaz Mekuria 2 Java Programming Unity Gergi 6
28 Melaku Worku 2 SQL Database BITS Shola 10
25 Woldu Kebede 6 Java Programming AAU SidistKilo 8
65 Dereje Taye 2 SQL Database Hilcoe Aratkilo 9
24 Selam Belay 8 Prolog Programming Jimma AbaJifar 5
65 Dereje Taye 4 IP Networking Jimma AbaJifar 8
94 Alem Ayele 3 Cisco Networking Hilcoe Arat Kilo 7
18 Girma Dereje 1 Oracle Database Unity Gerji 4
65 Dereje Taye 6 Java Programming AAU Sidistkilo 6
Example 1 ..
Is this a relation?
Answer–Yes: Unique rows and no multivalued attributes
What is the primary key?
Empid + skillid
What happens if we delete empid 16?
We delete the skill and also the School records
What happens if we delete emp id 94?
We delete the skill
What if we want to enter an employee with no skill
We can not?
Example 2
Example 2…
Question–Is this a relation?
Answer–Yes: Unique rows and no multivalued attributes
Question–What’s the primary key?
Answer–Composite: Emp_ID, Course_Title
Anomalies in the table
Insertion–can’t enter a new employee without having the employee take a
class
Deletion–if we remove employee 140, we lose information about the
existence of a Tax Acc class
Modification–giving a salary increase to employee 100 forces us to update
multiple records
Why do these anomalies exist?
Because there are multiple themes (entity types) in this one relation.
➔ results in data duplication
➔ unnecessary dependency between the entities
Imparting clear semantics in relations
Guideline 1. Design a relation schema so that it is easy to explain its
meaning. Do not combine attributes from multiple entity types and
relationship types into a single relation.
The semantics of a relation refers to its meaning resulting from the
interpretation of attribute values in a tuple
the easier it is to explain the semantics of the relation—or in other words,
what a relation exactly means and stands for—the better the relation
schema design will be.
Guideline 2. Design the base relation schemas so that no insertion,
deletion, or modification anomalies are present in the relations.
Guideline3. As far as possible, avoid placing attributes in a base
relation whose values may frequently be NULL. If NULLs are
unavoidable, make sure that they apply in exceptional cases only and
do not apply to a majority of tuples in the relation.
Functional Dependencies and Keys
Functional
Dependency: The value of one attribute (the determinant)
determines the value of another attribute
Candidate Key:
A unique identifier. One of the candidate keys will become the primary key
Eg. if there are both passport no. and driving liscence no. in a table both are
candidate keys
Each non-key field is functionally dependent on every candidate key
The essence of this idea is that if the existence of something, call it A,
implies that B must exist and have a certain value, then we say that "B
is functionally dependent on A.“
Data Dependency
Thelogical associations between data items that point the database
designer in the direction of a good database design are referred to as
determinant or dependent relationships.
Two data items A and B are said to be in a determinant or dependent
relationship if certain values of data item B always appears with certain
values of data item A.
If the data item A is the determinant data item and B the dependent data
item then the direction of the association is from A to B and not vice versa.
FDs are derived from the real-world constraints on the attributes
Data Dependency …
We also often express this idea by saying that "A determines B," or that
"B is a function of A," or that "A functionally governs B."
Often,
the notions of functionality and functional dependency are
expressed briefly by the statement, "If A, then B."
It is important to note that the value B must be unique for a given value of
A, i.e., any given value of A must imply just one and only one value of B, in
order for the relationship to qualify for the name "function."
(However, this does not necessarily prevent different values of A from
implying the same value of B.)
X ➔ Y holds if whenever two tuples have the same value for X, they
must have the same value for Y
Data Dependency …
The notation is: A➔B which is read as;
B is functionally dependent on A
In general, a functional dependency is a relationship among attributes.
In relational databases, we can have a determinant that governs one
other attribute or several other attributes.
Who determines this FD? How do we know?
Partial Dependency
Ifan attribute which is not a member of the primary key is dependent
on some part of the primary key (if we have composite primary key)
then that attribute is partially functionally dependent on the primary
key.
Let {A,B} be the Primary Key and C a non key attribute.
Then if {A,B} → C and B → C
Then C is partially functionally dependent on {A,B}
Full Dependency
If
an attribute which is not a member of the primary key is not
dependent on some part of the primary key but the whole key (if we
have composite primary key) then that attribute is fully functionally
dependent on the primary key.
Let {A,B} be the Primary Key and C is non key attribute
Then if {A,B}➔C and if (B➔C and A➔C) does not hold
Then C Fully functionally dependent on {A,B}
Transitive Dependency
In mathematics and logic, a transitive relationship is a relationship of
the following form: "If A implies B, and if also B implies C, then A implies
C."
Example:
If Mr X is a Human, and if every Human is an Animal, then Mr X must be
an Animal.
Generalized way of describing transitive dependency is that:
If A functionally governs B, AND If B functionally governs C THEN
A functionally governs C
Provided that neither C nor B determines A i.e. (B /➔A and C /➔A)
In the normal notation:
{(A➔B) AND(B➔C)} ==> A➔C provided thatB /➔A and C /➔A
Steps of Normalization
Wehave various levels or steps in normalization called Normal
Forms.
The level of complexity, strength of the rule and decomposition
increases as we move from one lower level Normal Form to the higher.
A table in a relational database is said to be in a certain normal form if it
satisfies certain constraints.
Next normal form represents a stronger condition than the previous one
Example 1
EmpID Fname Lname SkillID Skill SkillType School SchoolAD SkillLevel
12 Almaz Mekuria 2 SQL Database AAU Sidist_Kilo 5
Java Programming Unity Gergi 6
16 Abebe Alemu 5 C++ Programming St. Mary Mexico 6
28 Melaku Worku 2 SQL Database BITS Shola 10
25 Woldu Kebede 6 Java Programming AAU SidistKilo 8
65 Dereje Taye 2 SQL Database Hilcoe Aratkilo 9
IP Networking Jimma Abajifrar 8
Java Programming AAU Sidistkilo 6
24 Selam Belay 8 Prolog Programming Jimma AbaJifar 5
94 Alem Ayele 3 Cisco Networking Hilcoe Arat Kilo 7
18 Girma Dereje 1 Oracle Database Unity Gerji 4
Database Table Normalization
Normalization – series of stages called normal forms:
First normal form (1NF), Second normal form (2NF), and Third normal
form (3NF).
2NF is better than 1NF; 3NF is better than 2NF
For most business database design purposes, 3NF is as high as
needed in normalization
Highest level of normalization is not always most desirable
Normalization works one relation at a time
Progressively breaks table into new set of relations based on
identified dependencies
Denormalization produces a lower normal form
Increased performance but greater data redundancy
First Normal Form (1NF)
Requires that all column values in a table are Moving this repeating
groups to a new row by repeating the common attributes. If so then
Find the key with which you can find all data
Thus
No multi valued attributes
Every attribute value is atomic
The above table is not in its 1st Normal Form (multi valued attributes)
it is not a relation
While decomposing the multi valued attributes into different rows makes it
in its 1st Normal form
Formal Definition: a table (relation) is in 1NF
If
There are no duplicate rows in the table. Unique identifier
Each cell is single-valued (i.e., there are no repeating
groups).
Entries in a column (attribute, field) are of the same kind.
Unnormalized…
EmpID Fname Lname SkillID Skill SkillType School SchoolAD SkillLevel
12 Almaz Mekuria 2 SQL Database AAU Sidist_Kilo 5
Java Programming Unity Gergi 6
16 Abebe Alemu 5 C++ Programming St. Mary Mexico 6
28 Melaku Worku 2 SQL Database BITS Shola 10
25 Woldu Kebede 6 Java Programming AAU SidistKilo 8
65 Dereje Taye 2 SQL Database Hilcoe Aratkilo 9
IP Networking Jimma Abajifrar 8
Java Programming AAU Sidistkilo 6
24 Selam Belay 8 Prolog Programming Jimma AbaJifar 5
94 Alem Ayele 3 Cisco Networking Hilcoe Arat Kilo 7
18 Girma Dereje 1 Oracle Database Unity Gerji 4
Remove all repeating groups. Distribute the multi-valued attributes
into different rows and identify a unique identifier for the relation so
that it is a relation in relational database
EmpID Fname Lname SkillID Skill SkillType School SchoolAD SkillLevel
12 Almaz Mekuria 2 SQL Database AAU Sidist_Kilo 5
16 Abebe Alemu 5 C++ Programming St. Mary Mexico 6
12 Almaz Mekuria 2 Java Programming Unity Gergi 6
28 Melaku Worku 2 SQL Database BITS Shola 10
25 Woldu Kebede 6 Java Programming AAU SidistKilo 8
65 Dereje Taye 2 SQL Database Hilcoe Aratkilo 9
24 Selam Belay 8 Prolog Programming Jimma AbaJifar 5
65 Dereje Taye 4 IP Networking Jimma AbaJifar 8
94 Alem Ayele 3 Cisco Networking Hilcoe Arat Kilo 7
18 Girma Dereje 1 Oracle Database Unity Gerji 4
65 Dereje Taye 6 Java Programming AAU Sidistkilo 6
