DATABASE NORMALIZATION

What is Normalization ?
 NORMALIZATION is a database design technique that organizes tables in a manner that reduces
redundancy and dependency of data.

 Normalization divides larger tables into smaller tables and links them using relationships.

 The purpose of Normalization is to eliminate redundant (useless) data and ensure data is stored
logically.

• The inventor of the relational model [Link] proposed the theory of normalization.
 Redundancy
• Row Level Redundancy: • If the SID is primary key to each
row, you can use it to remove
the duplicates as shown below:
SID SName Age SID SName Age
1 PQR 20
1 PQR 20
2 Kit 25
2 Kit 25

1 PQR 20
 Redundancy (Cont..)
• Column Level Redundancy:
• Now Rows are same but in column level because of Sid is primary key
but columns are same. Redundant
Sid Sname Cid Cname Fid Fname Salary Column
Values
1 AA C1 DBMS F1 PQR 30000

2 BB C2 JAVA F2 KK 50000

3 CC C1 DBMS F1 PQR 30000

4 DD C1 DBMS F1 PQR 30000

 What is an Anomaly?
• Anomalies in dbms can be defined as the flaws or problems in the relational database that can be
occurred by the operations such as some instances of insertion leading to insertion anomalies in
dbms, deleting rows that can lead to deletion anomalies in dbms.
• Problems that can occur in poorly planned, unnormalized databases where all the data is stored
in one table.
• These anomalies can arise due to various factors such as improper database design, incomplete
or inconsistent data entries, or inadequate data manipulation operations. We will explore real-
world examples to illustrate these anomalies and highlight their impact on data consistency and
reliability.

• Types of Anomalies:
• Insert
• Delete
• Update
 Anomalies in DBMS
• Insert Anomaly : An Insert Anomaly occurs when certain attributes
cannot be inserted into the database without the presence of other
attributes.
• Delete Anomaly: A Delete Anomaly exists when certain attributes are
lost because of the deletion of other attributes.
• Update Anomaly: An Update Anomaly exists when one or more
instances of duplicated data is updated, but not all.
Anomaly Example
• Below table University consists of seven attributes: Sid, Sname, Cid,
Cname, Fid, Fname, and Salary. And the Sid acts as a key attribute or
a primary key in the relation.
 Insertion Anomaly
• Suppose a new faculty joins the University, and the Database
Administrator inserts the faculty data into the above table. But he is
not able to insert because Sid is a primary key, and can’t be NULL. So
this type of anomaly is known as an insertion anomaly.
 Delete Anomaly
• When the Database Administrator wants to delete the student details
of Sid=2 from the above table, then it will delete the faculty and
course information too which cannot be recovered further.

SQL:
DELETE FROM University WHERE Sid=2;
 Update Anomaly
• When the Database Administrator wants to change the salary of
faculty F1 from 30000 to 40000 in above table University, then the
database will update salary in more than one row due to data
redundancy. So, this is an update anomaly in a table.

SQL:
UPDATE University
SET Salary= 40000
WHERE Fid=“F1”;

To remove all these anomalies, we need to normalize the data

in the database.
 Normal forms
• The Theory of Data Normalization in SQL is still being developed further. For example, there are
discussions even on 6th Normal Form. However, in most practical applications, normalization
achieves its best in 3rd Normal Form. The evolution of Normalization theories is illustrated
below-
 Functional Dependency
• Functional dependency in RDBMS, as the name suggests is a
relationship between attributes of a table dependent on each other.
Introduced by E. F. Codd, it helps in preventing data redundancy.

• The functional dependency is a relationship that exists between two

attributes. It typically exists between the primary key and non-key
attribute within a table.
 Functional Dependency
• Functional Dependency is represented by -> (arrow sign).
• Then the following will represent the functional dependency between
attributes with an arrow sign A -> B
• The left side of FD is known as a determinant, the right side of the
production is known as a dependent.
 Functional Dependency
• If α and β are the two sets of attributes in a relational table R where-
α⊆R
β⊆R
Then, for a functional dependency to exist from α to β.
 Functional Dependency
Employee number Employee Name Salary City
1 Dana 50000 San Francisco
2 Francis 38000 London
3 Andrew 25000 Tokyo

Example:
For the given table, if we know the value of Employee number, we can obtain Employee Name, city, salary, etc.
By this, we can say that the city, Employee Name, and salary are functionally depended on Employee number.
 Functional Dependency
Example
• We have a <Department> table with two attributes − DeptId and DeptName.
• The DeptId is primary key.
DeptId DeptName

001 Finance

002 Marketing

003 HR

• Here, DeptId uniquely identifies the DeptName attribute. This is because if you want to know the
department name, then at first you need to have the DeptId.
• Above functional dependency between DeptId and DeptName can be determined as DeptId is
functionally dependent on DeptName −
DeptId -> DeptName
Types of Functional Dependency

•Trivial Functional Dependency

•Non-Trivial Functional Dependency
•Completely Non-Trivial Functional Dependency
 Trivial functional dependency
A → B has trivial functional dependency if B is a subset of A.
OR
A functional dependency X → Y is said to be trivial if and only if Y ⊆ X.
• Thus, if RHS of a functional dependency is a subset of LHS, then it is called as a trivial functional dependency.

• The examples of trivial functional dependencies are-

• AB → A
• AB → B
• AB → AB

• The following dependencies are also trivial like: A → A, B → B

Consider a table with two columns Employee_Id and Employee_Name.
• {Employee_id, Employee_Name} → Employee_Id
is a trivial functional dependency as Employee_Id is a subset of {Employee_Id, Employee_Name}.

• Also, Employee_Id → Employee_Id and Employee_Name → Employee_Name are trivial dependencies too.
 Trivial functional dependency
Example
• We have a <Department> table with two attributes − DeptId and
DeptName.
• The DeptId is primary key.

The following is a trivial functionnal dependency since DeptId is a subset of DeptId and DeptName

{ DeptId, DeptName } -> Dept Id

 Non Trivial functional dependency

• A → B has a non-trivial functional dependency if B is not a subset of A.

OR
A functional dependency X → Y is said to be non-trivial if and only if Y ⊄ X.
• Thus, if there exists at least one attribute in the RHS of a functional dependency that is not a part of
LHS, then it is called as a non-trivial functional dependency.

The examples of non-trivial functional dependencies are-

• AB → BC (PARTIAL)
• AB → CD (COMPLETE)

When A intersection B is NULL, then A → B is called as complete non-trivial.

ID → Name,
Name → DOB
 Non Trivial functional dependency

• Functional dependency which also known as a nontrivial dependency occurs

when A->B holds true where B is not a subset of A. In a relationship, if attribute
B is not a subset of attribute A, then it is considered as a non-trivial dependency.
Company CEO Age
Microsoft Satya Nadella 51
• Example:
Google Sundar Pichai 46
Apple Tim Cook 57

• (Company} -> {CEO} (if we know the Company, we knows the CEO name)

• But CEO is not a subset of Company, and hence it's non-trivial functional
dependency.
 Rules for Functional Dependency-
Rule-01:
• A functional dependency X → Y will always hold if all the values of X are unique (different)
irrespective of the values of Y.
• Example-Consider the following table-

The following functional dependencies will always hold since all the values of attribute ‘A’ are unique-
• A→B
• A → BC
• A → CD
• A → BCD
• A → DE
• A → BCDE
In general, we can say following functional dependency will always hold-
A → Any combination of attributes A, B, C, D, E
 Rules for Functional Dependency-
Rule-02:
• A functional dependency X → Y will always hold if all the values of Y are same irrespective of the
values of X.
• Example-
• Consider the following table-

The following functional dependencies will always hold since all the values of attribute ‘C’ are same-
• A→C
• AB → C
• ABDE → C
• DE → C
• AE → C

• In general, we can say following functional dependency will always hold true-
Any combination of attributes A, B, C, D, E → C
 VALID/INVALID FD
X Y Z
1 4 2
1 5 3
1 6 3
1 2 2
 VALID/INVALID FD
A B C
1 2 4
3 5 4
3 7 2
1 4 2
 Key terms
Key Terms Description
Axioms is a set of inference rules used to infer all the
Axiom
functional dependencies on a relational database.
It is a rule that suggests if you have a table that appears
to contain two entities which are determined by the
Decomposition
same primary key then you should consider breaking
them up into two different tables.
It is displayed on the right side of the functional
Dependent
dependency diagram.
It is displayed on the left side of the functional
Determinant
dependency Diagram.
It suggests that if two tables are separate, and the PK is
Union
the same, you should consider putting them. together
 Armstrong’s Axioms(Inference Rules) in
Functional Dependency
The term Armstrong axioms refer to the sound and complete set of
inference rules or axioms, introduced by William W. Armstrong, that is
used to test the logical implication of functional dependencies. If F is a
set of functional dependencies then the closure of F, denoted as F^+, is
the set of all functional dependencies logically implied by F.
Armstrong’s Axioms are a set of rules, that when applied repeatedly,
generates a closure of functional dependencies.
 ,

Armstrong’s Axioms(Inference Rules) in

Functional Dependency
PRIMARY RULES
Reflexivity-
• If B is a subset of A, then A → B always holds.
Augmentation-
• If A → B, then AC → BC always holds.
Transitivity-
• If A → B and B → C, then A → C always holds.
 ,

Armstrong’s Axioms(Inference Rules) in

Functional Dependency
SECONDARY RULES
Additive(Union)-
• If A → B and A → C, then A → BC always hold
Decomposition-
• If A → BC, then A → B and A → C always holds.
• Composition-
• If A → B and C → D, then AC → BD always holds.
 Closure of an Attribute Set/Attribute
Closure
•The set of all those attributes which can be functionally determined from an attribute set is called
as a closure of that attribute set.
•Closure of attribute set {X} is denoted as {X} +

Steps to Find Closure of an Attribute Set-

Following steps are followed to find the closure of an attribute set-

Step-01:

Add the attributes contained in the attribute set for which closure is being calculated to the result set.

Step-02:

Recursively add the attributes to the result set which can be functionally determined from the attributes already
contained in the result set.
 Closure of an Attribute Set/Attribute
Example-
Closure
• Consider a relation R ( A , B , C , D , E , F , G ) with the functional
dependencies-
A → BC, BC → DE, D → F, CF → G
Now, let us find the closure of some attributes and attribute sets
 Closure of an Attribute Set/Attribute
• Example-
Closure
• Consider a relation R ( A , B , C , D , E , F , G ) with the functional
dependencies-
• A → BC, BC → DE, D → F, CF → G
Now, let us find the closure of some attributes and attribute sets
• Consider a relation R ( A , B , C , D , E , F , G ) with the functional
dependencies-
• A → BC, BC → DE, D → F, CF → G
• {B,C}+={B,C}
• ={B,C,D,E} using BC → DE
• ={B,C,D,E,F} using D → F
={B,C,D,E,F,G} using CF → G
 GIVEN FOLLOWING FD’S
AB->CD
AF->D
DE->F
C->G
F->E

G->A
Which statement is false?
• [CF]+=[A,C,D,E,F,G]
• [BE]+=[A,B,C,D,E]
• [AF]+=[A,C,D,E,F,G]
• [AB]+=[A,C,D,F,G]
 Different Types Of Keys in DBMS-

• The terms ‘relation’ and ‘table’ are used interchangeably.

• The terms ‘tuple’ and ‘record’ are used interchangeably.

Types of keys

• Super key
• Candidate key
• Primary key
• Alternate key
• Foreign key
 Super Key
• A super key is a set of attributes that can identify each tuple uniquely in the given relation.
• A super key is not restricted to have any specific number of attributes.
• Thus, a super key may consist of any number of attributes.

Example- Consider the following Student schema-

• Student ( roll , name , age , address , class , section )

Given below are the examples of super keys since each set can uniquely identify each student in the Student
table-

• ( roll , name , age , address , class , section )

• ( class , section , roll )
• (section , roll )
• ( name , address )

NOTE-
• All the attributes in a super key are definitely sufficient to identify each tuple uniquely in the given relation
but all of them may not be necessary.
 Candidate Key
A minimal super key is called as a candidate key.
OR
A set of minimal attribute(s) that can identify each tuple uniquely in the given relation
is called as a candidate key.

Example- Consider the following Student schema-

Student ( roll , name , sex , age , address , class , section )

• Given below are the examples of candidate keys since each set consists of minimal
attributes required to identify each student uniquely in the Student table-
• ( class , section , roll )
• ( name , address )
 Candidate Key
NOTES-

• All the attributes in a candidate key are sufficient as well as necessary to

identify each tuple uniquely.
• Removing any attribute from the candidate key fails in identifying each
tuple uniquely.
• The value of candidate key must always be unique.
• The value of candidate key can never be NULL.
• It is possible to have multiple candidate keys in a relation.
• Those attributes which appears in some candidate key are called as prime
attributes.
 Primary Key
A primary key is a candidate key that the database designer selects while designing the
database.
OR
Candidate key that the database designer implements is called as a primary key.

NOTES-

• The value of primary key can never be NULL.

• The value of primary key must always be unique.
• The values of primary key can never be changed i.e. no updation is possible.
• The value of primary key must be assigned when inserting a record.
• A relation is allowed to have only one primary key.
 Alternate Key

Candidate keys that are left unimplemented or unused after

implementing the primary key are called as alternate keys.
OR
Unimplemented candidate keys are called as alternate keys.
 Foreign Key

• An attribute ‘X’ is called as a foreign key to some other attribute ‘Y’

when its values are dependent on the values of attribute ‘Y’.
• The attribute ‘X’ can assume only those values which are assumed by
the attribute ‘Y’.
• Here, the relation in which attribute ‘Y’ is present is called as the
referenced relation.
• The relation in which attribute ‘X’ is present is called as the
referencing relation.
• The attribute ‘Y’ might be present in the same table or in some other
table.
 Foreign Key

• An attribute ‘X’ is called as a foreign key to some other attribute ‘Y’

when its values are dependent on the values of attribute ‘Y’.
• The attribute ‘X’ can assume only those values which are assumed by
the attribute ‘Y’.
• Here, the relation in which attribute ‘Y’ is present is called as the
referenced relation.
• The relation in which attribute ‘X’ is present is called as the
referencing relation.
• The attribute ‘Y’ might be present in the same table or in some other
table.
Foreign Key
 Way of finding candidate key
Step-01:
• Determine all essential attributes of the given relation.
• Essential attributes are those attributes which are not present on RHS of any functional
dependency.
• Essential attributes are always a part of every candidate key.
• This is because they can not be determined by other attributes.

Example

• Let R(A, B, C, D, E, F) be a relation scheme with the following functional dependencies-

• A → B, C → D, D → E

• Here, the attributes which are not present on RHS of any functional dependency are A, C and F.
• So, essential attributes are- A, C and F.
 Way of finding candidate key
Step-02:
• The remaining attributes of the relation are non-essential attributes. This is because they can be determined by using
essential attributes.
• Now, following two cases are possible-

Case-01:

• If all essential attributes together can determine all remaining non-essential attributes, then the combination of essential
attributes is the candidate key.
• It is the only possible candidate key.

Case-02:

• If all essential attributes together can not determine all remaining non-essential attributes, then-
• The set of essential attributes and some non-essential attributes will be the candidate key(s).
• In this case, multiple candidate keys are possible.
• To find the candidate keys, we check different combinations of essential and non-essential attributes.
 Normalization in DBMS
In DBMS, database normalization is a process of making the database consistent by-
•Reducing the redundancies
•Ensuring the integrity of data through lossless decomposition
• Normalization is done through normal forms.

Normal Forms-

• The standard normal forms used are-

• First Normal Form (1NF)

• Second Normal Form (2NF)
• Third Normal Form (3NF)
• Boyce-Codd Normal Form (BCNF)

There exists several other normal forms even after BCNF

 First Normal Form (1NF)
First Normal Form-

A given relation is called in First Normal Form (1NF) if each cell of the table contains only an atomic value.

OR

A given relation is called in First Normal Form (1NF) if the attribute of every tuple is either single valued or a
null value.

Example-

The following relation is not in 1NF-

Student_id Name Subjects

100 Akshay Computer Networks, Designing
101 Aman Database Management System
102 Anjali Automata, Compiler Design
However,
First Normal Form (1NF)
This relation can be brought into 1NF.
This can be done by rewriting the relation such that each cell of the table contains only one value.

Student_id Name Subjects

100 Akshay Computer Networks
100 Akshay Designing
101 Aman Database Management System
102 Anjali Automata
102 Anjali Compiler Design

Relation is in 1NF

This relation is in First Normal Form (1NF).

NOTE-

By default, every relation is in 1NF.

This is because formal definition of a relation states that value of all the attributes must be atomic.
 Second Normal Form (2NF)
A given relation is called in Second Normal Form (2NF) if and only if-
• Relation already exists in 1NF.
• No partial dependency exists in the relation.

Partial Dependency
A partial dependency is a dependency where few attributes of the candidate key determines non-prime
attribute(s). OR
A partial dependency is a dependency where a portion of the candidate key or incomplete candidate key
determines non-prime attribute(s).

In other words,

• A → B is called a partial dependency if and only if-

• A is a subset of some candidate key
• B is a non-prime attribute.

• If any one condition fails, then it will not be a partial dependency.

• NOTE-
• To avoid partial dependency, incomplete candidate key must not determine any non-prime attribute.
• However, incomplete candidate key can determine prime attributes.
 Second Normal Form (2NF)
Example-

Consider a relation- R ( V , W , X , Y , Z ) with functional dependencies-

VW → XY
Y→V
WX → YZ

The possible candidate keys for this relation are-

VW , WX , WY

From here,
Prime attributes = { V , W , X , Y }
Non-prime attributes = { Z }

Now, if we observe the given dependencies-

There is no partial dependency.
This is because there exists no dependency where incomplete candidate key determines any non-prime
attribute.

Thus, we conclude that the given relation is in 2NF.

 Third Normal Form (3NF)
A given relation is called in Third Normal Form (3NF) if and only if-
Relation already exists in 2NF.
No transitive dependency exists for non-prime attributes.

Transitive Dependency

A → B is called a transitive dependency if and only if-

A is not a super key.
B is a non-prime attribute.
If any one condition fails, then it is not a transitive dependency.

NOTE-

Transitive dependency must not exist for non-prime attributes.

However, transitive dependency can exist for prime attributes.
 Third Normal Form (3NF)
A relation is called in Third Normal Form (3NF) if and only if-
Any one condition holds for each non-trivial functional dependency A → B
A is a super key
B is a prime attribute

Example-

Consider a relation- R ( A , B , C , D , E ) with functional dependencies-

A → BC
CD → E
B→D
E→A
The possible candidate keys for this relation are-
A , E , CD , BC
From here,
Prime attributes = { A , B , C , D , E }
There are no non-prime attributes
Now,
It is clear that there are no non-prime attributes in the relation.
In other words, all the attributes of relation are prime attributes. Thus, all the attributes on RHS of each
functional dependency are prime attributes.
Thus, we conclude that the given relation is in 3NF.
 Boyce-Codd Normal Form -BCNF
A given relation is called in BCNF if and only if-
Relation already exists in 3NF.
For each non-trivial functional dependency A → B, A is a super key of the relation.
Thus, we conclude that the given relation is in 3NF.

Consider a relation- R ( A , B , C ) with the functional dependencies-

A→B
B→C
C→A

The possible candidate keys for this relation are-

A,B,C

Now, we can observe that LHS of each given functional dependency is a candidate key.
Thus, we conclude that the given relation is in BCNF.
 Decomposition of a Relation-
• The process of breaking up or dividing a single relation into two or more sub relations is called as
decomposition of a relation.

Properties of Decomposition-
1. Lossless decomposition-Lossless decomposition ensures-
• No information is lost from the original relation during decomposition.
• When the sub relations are joined back, the same relation is obtained that was decomposed.
• Every decomposition must always be lossless.

• 2. Dependency Preservation-Dependency preservation ensures-

• None of the functional dependencies that holds on the original relation are lost.
• The sub relations still hold or satisfy the functional dependencies of the original relation.
Types of Decomposition-
 Types of Decomposition-

• 1. Lossless Join Decomposition-

• Consider there is a relation R which is decomposed into sub
relations R1 , R2 , …. , Rn.
• This decomposition is called lossless join decomposition when the
join of the sub relations results in the same relation R that was
decomposed.
• For lossless join decomposition, we always have-

R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn = R
where ⋈ is a natural join operator
Types of Decomposition-
Example-

Consider the following relation R( A , B , C )-

R( A , B , C )

Consider this relation is decomposed into two sub relations R1( A , B ) and R2( B , C )-

A B C
1 2 1
2 5 3
3 3 3
 Types of Decomposition-
The two sub relations are-

R1( A , B )

R2( B , C )

Now, let us check whether this decomposition is lossless or not.

For lossless decomposition, we must have-
R1 ⋈ R2 = R

Now, if we perform the natural join ( ⋈ ) of the sub relations R1 and R2 , we get-

This relation is same as the original relation R.

Thus, we conclude that the above decomposition is lossless join decomposi
A B B C A B C
1 2 2 1 1 2 1
2 5 5 3 2 5 3
3 3 3 3 3 3 3
 Types of Decomposition-
2. Lossy Join Decomposition-

•Consider there is a relation R which is decomposed into sub relations R1 , R2 , …. , Rn.

•This decomposition is called lossy join decomposition when the join of the sub relations does
not result in the same relation R that was decomposed.
•The natural join of the sub relations is always found to have some extraneous tuples.
•For lossy join decomposition, we always have-

where ⋈ is a natural join operator R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn ⊃ R

 Determining Whether
Decomposition Is Lossless Or
Lossy
• Consider a relation R is decomposed into two sub relations R and R .
1 2

• Then,If all the following conditions satisfy, then the decomposition is lossless. If any of these
conditions fail, then the decomposition is lossy.
Condition-01: Union of both the sub relations must contain all the attributes that are present
in the original relation R.
R1 ∪ R2 = R
Condition-02: Intersection of both the sub relations must not be null.
• In other words, there must be some common attribute which is present in both the sub
relations.
R1 ∩ R2 ≠ ∅
Condition-03: Intersection of both the sub relations must be a super key of either R1 or R2 or
both.
R1 ∩ R2 = Super key of R1 or R2
 Dependency Preserving
Decomposition
• If we decompose a relation R into relations R1 and R2, All
dependencies of R either must be a part of R1 or R2 or must be
derivable from combination of FD’s of R1 and R2.

• For Example, A relation R (A, B, C, D) with FD set{A->BC} is

decomposed into R1(ABC) and R2(AD) which is dependency
preserving because FD A->BC is a part of R1(ABC).
 Dependency Preserving
Decomposition
Consider a schema R(A,B,C,D) and functional dependencies A->B and
C->D which is decomposed into R1(AB) and R2(CD)
This decomposition is dependency preserving decompostion because
• A->B can be ensured in R1(AB)
• C->D can be ensured in R2(CD)

Is it lossy or lossless decomposition?

 Fourth Normal Form (4NF)
Any relation is said to be in the fourth normal form when it satisfies the
following conditions:
• It must be in Boyce Codd Normal Form (BCNF).
• It should have no multi-valued dependency.

A multi-valued dependency is said to occur when there are two

attributes in a table which depend on a third attribute but are
independent of each other.

In order to denote a multi-valued dependency, “->->” this sign is used.

 Multivalued Dependency

• Multivalued dependency occurs when two attributes in a table are

independent of each other but, both depend on a third attribute.

• A multivalued dependency consists of at least two attributes that are

dependent on a third attribute that's why it always requires at least
three attributes.

• Example: Suppose there is a bike manufacturer company which

produces two colors(white and black) of each model every year.
 Multivalued Dependency
• Example: Suppose there is a bike manufacturer company which produces two
colors(white and black) of each model every year.

• Here columns COLOR and MANUF_YEAR are dependent on BIKE_MODEL and

independent of each other.
• In this case, these two columns can be called as multivalued dependent on
BIKE_MODEL. These can be shown as
• BIKE_MODEL → → MANUF_YEAR
• BIKE_MODEL → → COLOR
 Fifth Normal Form (5NF)
Any relation in order to be in the fifth normal form must satisfy the
following conditions:
• It must be in Fourth Normal Form (4NF).
• It should have no join dependency(All dependency must be
preserve) and also the joining must be lossless.

In the fifth normal form the relation must be decomposed in as many

sub-relations as possible so as to avoid any kind of redundancy and
there must be no extra tuples generated when the sub-relations are
combined together by using natural join.