Why is Normalization needed in the design of a

database??
Normalization is a technique for organizing data in a database. It is important that
a database is normalized to minimize redundancy (duplicate data) and to ensure only related
data is stored in each table. It also prevents any issues stemming from database modifications
such as insertions, deletions, and updates.

How us Normalization done??

Normalization is a systematic approach of decomposing relations or tables to eliminate data
redundancy (repetition) and undesirable characteristics like Insertion, Update and Deletion
Anomalies. It is a multi-step process that puts data into tabular form, removing duplicated data
from the relation tables.

What is 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-

The following two properties must be followed when decomposing a given relation-

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.

NOTE : Lossless Decomposition is a mandatory property but Dependency

preservation is a desirable property to be taken care of, while decomposing
relations during Normalization process

Types of Decomposition-

Decomposition of a relation can be completed in the following two ways-

Determining Whether Decomposition Is Lossless Or

Lossy-

Consider a relation R is decomposed into two sub relations R 1 and R2.

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. Thus,

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.
Thus,

R1 ∩ R2 ≠ ∅

Condition-03:

Intersection of both the sub relations must be a super key of either R1 or R2 or both.
Thus,

R1 ∩ R2 = Super key of R1 or R2

PRACTICE PROBLEMS BASED ON DETERMINING

WHETHER DECOMPOSITION IS LOSSLESS OR
LOSSY-

Problem-01:

Consider a relation schema R ( A , B , C , D ) with the functional dependencies A → B

and C → D. Determine whether the decomposition of R into R1 ( A , B ) and R2 ( C , D )
is lossless or lossy.

Solution-

To determine whether the decomposition is lossless or lossy,

 We will check all the conditions one by one.
 If any of the conditions fail, then the decomposition is lossy otherwise lossless.
Condition-01:

According to condition-01, union of both the sub relations must contain all the attributes
of relation R.
So, we have-
R1 ( A , B ) ∪ R2 ( C , D )
=R(A,B,C,D)
Clearly, union of the sub relations contain all the attributes of relation R.
Thus, condition-01 satisfies.

Condition-02:

According to condition-02, intersection of both the sub relations must not be null.
So, we have-
R1 ( A , B ) ∩ R2 ( C , D )
=Φ
Clearly, intersection of the sub relations is null.
So, condition-02 fails.
Thus, we conclude that the decomposition is lossy.

Problem-02:

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

A→B
B→C
C→D
D→B
Determine whether the decomposition of R into R1 ( A , B ) , R2 ( B , C ) and R3 ( B , D )
is lossless or lossy.
 Solution-

Strategy to Solve

When a given relation is decomposed into more than two sub relations, then-
 Consider any one possible ways in which the relation might have been decomposed into
those sub relations.
 First, divide the given relation into two sub relations.
 Then, divide the sub relations according to the sub relations given in the question.
As a thumb rule, remember-
Any relation can be decomposed only into two sub relations at a time.

Consider the original relation R was decomposed into the given sub relations as shown-

Decomposition of R(A, B, C, D) into R'(A, B, C) and

R3(B, D)-

To determine whether the decomposition is lossless or lossy,

 We will check all the conditions one by one.
 If any of the conditions fail, then the decomposition is lossy otherwise lossless.

Condition-01:

According to condition-01, union of both the sub relations must contain all the attributes
of relation R.
 So, we have-
R‘ ( A , B , C ) ∪ R3 ( B , D )
=R(A,B,C,D)
Clearly, union of the sub relations contain all the attributes of relation R.
Thus, condition-01 satisfies.

Condition-02:

According to condition-02, intersection of both the sub relations must not be null.
So, we have-
R‘ ( A , B , C ) ∩ R 3 ( B , D )
=B
Clearly, intersection of the sub relations is not null.
Thus, condition-02 satisfies.

Condition-03:

According to condition-03, intersection of both the sub relations must be the super key of
one of the two sub relations or both.
So, we have-
R‘ ( A , B , C ) ∩ R 3 ( B , D )
=B
Now, the closure of attribute B is-
B+ = { B , C , D }
Now, we see-
 Attribute ‘B’ can not determine attribute ‘A’ of sub relation R’.
 Thus, it is not a super key of the sub relation R’.
 Attribute ‘B’ can determine all the attributes of sub relation R 3.
 Thus, it is a super key of the sub relation R3.

Clearly, intersection of the sub relations is a super key of one of the sub relations.
So, condition-03 satisfies.
Thus, we conclude that the decomposition is lossless.
 Decomposition of R'(A, B, C) into R1(A, B) and R2(B,
C)-

To determine whether the decomposition is lossless or lossy,

 We will check all the conditions one by one.
 If any of the conditions fail, then the decomposition is lossy otherwise lossless.

Condition-01:

According to condition-01, union of both the sub relations must contain all the attributes
of relation R’.
So, we have-
R1 ( A , B ) ∪ R2 ( B , C )
= R’ ( A , B , C )
Clearly, union of the sub relations contain all the attributes of relation R’.
Thus, condition-01 satisfies.

Condition-02:

According to condition-02, intersection of both the sub relations must not be null.
So, we have-
R1 ( A , B ) ∩ R 2 ( B , C )
=B
Clearly, intersection of the sub relations is not null.
Thus, condition-02 satisfies.

Condition-03:

According to condition-03, intersection of both the sub relations must be the super key of
one of the two sub relations or both.
So, we have-
R1 ( A , B ) ∩ R 2 ( B , C )
 =B
Now, the closure of attribute B is-
B+ = { B , C , D }
Now, we see-
 Attribute ‘B’ can not determine attribute ‘A’ of sub relation R 1.
 Thus, it is not a super key of the sub relation R1.
 Attribute ‘B’ can determine all the attributes of sub relation R 2.
 Thus, it is a super key of the sub relation R2.

Clearly, intersection of the sub relations is a super key of one of the sub relations.
So, condition-03 satisfies.
Thus, we conclude that the decomposition is lossless.

Conclusion-
Overall decomposition of relation R into sub relations R 1, R2 and R3 is lossless.
 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.

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 3 rd Normal
Form. The evolution of Normalization theories is illustrated below-

Normal Forms-
Database Normalization Example:
We will study normalization with the help of a case study. Assume, a video
library maintains a database of movies rented out. Without any
normalization, all information is stored in one table as shown below.

Table 1
Here you see Movies Rented column has multiple values. Now let's
move into 1st Normal Forms:

1NF (First Normal Form) Rules

 Each table cell should contain a single value.
 Each record needs to be unique.

1NF Example

Table 1: In 1NF Form

Student_id Name Subjects

100 Ajay Computer Networks

100 Ajay Designing

101 Aman Database Management System

 102 Anjali Automata

102 Anjali Compiler Design

Table 2 : Relation is already 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-

A given relation is called in Second Normal Form (2NF) if and only if-
1. Relation already exists in 1NF.
2. 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-
1. A is a subset of some candidate key
2. 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.
 Example-

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

VW → XY, Y → V and 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-

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

Transitive Dependency
A → B is called a transitive dependency if and only if-
1. A is not a super key.
2. 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.
 OR

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
1. A is a super key
2. 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-

1. Relation already exists in 3NF.
2. For each non-trivial functional dependency A → B, A is a super key of the relation.

Example-

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 RHS of each given functional dependency is a candidate key.
Thus, we conclude that the given relation is in BCNF.

Algorithm to convert a Relation into BCNF if it not

already into BCNF

Initialize S = {R}
While S has a relation Q that is not in BCNF do:
Pick a FD: X->Y that holds in Q and violates
BCNF
Add the relation XY to S
Update Q = Q-Y
Return S
 Example :
R(A, B, C, D, E) with functional dependencies: A -> B, C -> D

Solution :
Here , candidate key is ACE
R(ABCDE)

R1( A, C,D,E) R2(A, B)

F1{C->D} F2{A->B}
This relation is not This is in BCNF
in BCNF because C is
not a super key of R1

So break R1 into two parts

R1

R11(ACE) R12(CD)
Now In BCNF Now in BCNF

Some important points about normal forms

Point-01:

Remember the following diagram which implies-

 A relation in BCNF will surely be in all other normal forms.
 A relation in 3NF will surely be in 2NF and 1NF.
 A relation in 2NF will surely be in 1NF.
 Point-02:

The above diagram also implies-

 BCNF is stricter than 3NF.
 3NF is stricter than 2NF.
 2NF is stricter than 1NF.

Point-03:

While determining the normal form of any given relation,

 Start checking from BCNF.
 This is because if it is found to be in BCNF, then it will surely be in all other normal
forms.
 If the relation is not in BCNF, then start moving towards the outer circles and check for
other normal forms in the order they appear.

Point-04:

 In a relational database, a relation is always in First Normal Form (1NF) at least.

Point-05:

 Singleton keys are those that consist of only a single attribute.

 If all the candidate keys of a relation are singleton candidate keys, then it will always
be in 2NF at least.
 This is because there will be no chances of existing any partial dependency.
 The candidate keys will either fully appear or fully disappear from the dependencies.
 Thus, an incomplete candidate key will never determine a non-prime attribute.
 Point-06:

 If all the attributes of a relation are prime attributes, then it will always be in 2NF at
least.
 This is because there will be no chances of existing any partial dependency.
 Since there are no non-prime attributes, there will be no Functional
Dependency which determines a non-prime attribute.

Point-07:

 If all the attributes of a relation are prime attributes, then it will always be in 3NF at
least.
 This is because there will be no chances of existing any transitive dependency for
non-prime attributes.

Point-08:

 Third Normal Form (3NF) is considered adequate for normal relational database
design.

Point-09:

 Every binary relation (a relation with only two attributes) is always in BCNF.

Point-10:

 BCNF is free from redundancies arising out of functional dependencies (zero

redundancy).

Point-11:

 A relation with only trivial functional dependencies is always in BCNF.

 In other words, a relation with no non-trivial functional dependencies is always in
BCNF.
 Point-12:

 BCNF decomposition is always lossless but not always dependency preserving.

Point-13:

 Sometimes, going for BCNF may not preserve functional dependencies.

 So, go for BCNF only if the lost functional dependencies are not required else
normalize till 3NF only.

Point-14:

 There exist many more normal forms even after BCNF like 4NF and more.
 But in the real world database systems, it is generally not required to go beyond
BCNF.

Point-15:

 Lossy decomposition is not allowed in 2NF, 3NF and BCNF.

 So, if the decomposition of a relation has been done in such a way that it is lossy, then
the decomposition will never be in 2NF, 3NF and BCNF.

Point-16:

 Unlike BCNF, Lossless and dependency preserving decomposition into 3NF and 2NF
is always possible.

Point-17:

 A prime attribute can be transitively dependent on a key in a 3NF relation.

 A prime attribute can not be transitively dependent on a key in a BCNF relation.

Point-18:
 If a relation consists of only singleton candidate keys and it is in 3NF, then it must also
be in BCNF.

Point-19:

 If a relation consists of only one candidate key and it is in 3NF, then the relation must
also be in BCNF.

Fourth Normal Form (4NF)

Fourth Normal Form comes into picture when Multi-valued Dependency occur in any
relation. We will learn about Multi-valued Dependency, how to remove it and how to
make any table satisfy the fourth normal form.

Rules for 4th Normal Form

For a table to satisfy the Fourth Normal Form, it should satisfy the following two
conditions:

1. It should be in the Boyce-Codd Normal Form.

2. And, the table should not have any Multi-valued Dependency.

Let's try to understand what multi-valued dependency is in the next section.

What is Multi-valued Dependency?

A table is said to have multi-valued dependency, if the following conditions are true,

1. For a dependency A → B, if for a single value of A, multiple value of B exists,

then the table may have multi-valued dependency.
2. Also, a table should have at-least 3 columns for it to have a multi-valued
dependency.
3. And, for a relation R(A,B,C), if there is a multi-valued dependency between, A
and B, then B and C should be independent of each other.

If all these conditions are true for any relation(table), it is said to have multi-valued
dependency
Example
Below we have a college enrolment table with columns s_id, course and hobby.

s_id course hobby

1 Science Cricket

1 Maths Hockey

2 C# Cricket

2 Php Hockey

As you can see in the table above, student with s_id 1 has opted for two
courses, Science and Maths, and has two hobbies, Cricket and Hockey.
You must be thinking what problem this can lead to, right?
Well the two records for student with s_id 1, will give rise to two more records, as
shown below, because for one student, two hobbies exists, hence along with both
the courses, these hobbies should be specified.

s_id course hobby

1 Science Cricket

1 Maths Hockey

1 Science Hockey

1 Maths Cricket
And, in the table above, there is no relationship between the
columns course and hobby. They are independent of each other.
So there is multi-value dependency, which leads to un-necessary repetition of data
and other anomalies as well.

How to satisfy 4th Normal Form?

To make the above relation satify the 4th normal form, we can decompose the table
into 2 tables.
CourseOpted Table

s_id course

1 Science

1 Maths

2 C#

2 Php

And, Hobbies Table,

s_id hobby

1 Cricket

1 Hockey

2 Cricket
 2 Hockey

Now this relation satisfies the fourth normal form.

A table can also have functional dependency along with multi-valued dependency. In
that case, the functionally dependent columns are moved in a separate table and the
multi-valued dependent columns are moved to separate tables.
If you design your database carefully, you can easily avoid these issues.

Fifth Normal Form / Projected

Normal Form (5NF or PJNF):
A relation R is in 5NF if and only if every join dependency in R is implied by the
candidate keys of R. A relation decomposed into two relations must have loss-less
join Property, which ensures that no spurious or extra tuples are generated, when
relations are reunited through a natural join.
Properties – A relation R is in 5NF if and only if it satisfies following conditions:
1. R should be already in 4NF.
2. It cannot be further non loss decomposed (join dependency)

Example – Consider the above schema, with a case as “if a company makes a
product and an agent is an agent for that company, then he always sells that product
for the company”. Under these circumstances, the ACP table is shown as:

Table – ACP
AGENT COMPANY PRODUCT

A1 PQR Nut

A1 PQR Bolt

A1 XYZ Nut

A1 XYZ Bolt

A2 PQR Nut
The relation ACP is again decompose into 3 relations. Now, the natural Join of all the
three relations will be shown as:

Table – R1
AGENT COMPANY

A1 PQR

A1 XYZ

A2 PQR

Table – R2
AGENT PRODUCT

A1 Nut

A1 Bolt

A2 Nut

Table – R3
COMPANY PRODUCT

PQR Nut

PQR Bolt

XYZ Nut

XYZ Bolt

Result of Natural Join of R1 and R3 over ‘Company’ and then Natural Join of R13
and R2 over ‘Agent’and ‘Product’ will be table ACP.
Hence, in this example, all the redundancies are eliminated, and the decomposition
of ACP is a lossless join decomposition. Therefore, the relation is in 5NF as it does
not violate the property of lossless join.