Chapter 4 Relational Database Design 7 Hours

3.1. Introduction to Relational-Database Design ( undesirable properties of a RDB design)

3.2. Functional Dependency(Basic concepts, F+, Closure of an Attribute set, Armstrong’s
axioms)
3.3. Concept of Decomposition
3.4. Desirable Properties of Decomposition ( Lossless join, Lossy join, Dependency
Preservation)
3.5. Concept of normalization, Normal Forms (1NF,2NF and 3NF), Examples
3.6 Keys Concept with Examples : Candidate Keys and Super Keys, Algorithm to find the
super keys / primary key for a relation

3.1 Introduction to Relational-Database Design ( undesirable properties

. of a RDB design)
In general, the goal of a relational-database design is to generate a set of relation schemas that
allows us to store information without unnecessary redundancy,

Pitfalls in Relational Database Design

Let us look at what can go wrong in a bad database design. Among the undesirable properties
that a bad design may have are:

• Repetition of information
• Inability to represent certain information

We shall discuss these problems with the help of a modified database design for our banking
example: suppose the information concerning loans is kept in one single relation, lending, which
is defined over the relation schema

◼ ER for Banking Enterprise

Schema Diagram for the Banking Enterprise

Example

◼ Consider the relation schema:

Lending-schema = (branch-name, branch-city, assets, customer-name, loan-number,
amount)
 ◼ Redundancy, why?
◼ Inability to represent certain information, why?
◼ Cannot store information about a branch if no loans exist
◼ Can use null values, but they are difficult to handle.

Why Redundancy Is Bad?

◼ Wastes space
◼ Complicates updating, introducing possibility of inconsistency of assets value
◼ We know why inability to represent certain information is bad.

RELATIONAL DATABASE DEGIN

Data base design is a process in which you create a logical data model for a database,
which store data of a company. It is performed after initial database study phase in the
database life cycle. You use normalization technique to create the logical data model for
a database and eliminate data redundancy. Normalization also allows you to organize
data efficiently in a data base and reduce anomalies during data operation. Various
normal forms, such as first, second and third can be applied to create a logical data model
for a database. The second and third normal forms are based on partial dependency and
transitivity dependency. Partial dependency occurs when a row of table is uniquely
identified by one column that is a part of a primary key. A transitivity dependency ours
when a non key column is uniquely identified by values in another non-key column of a
table.

Data base design process:

We can identify six main phases of the database design process:

1. Requirement collection and analysis

2. Conceptual data base design

3. Choice of a DBMS

4. Data model mapping(logical database design)

5. physical data base design

6. database system implementation and tuning

1. Requirement collection and analysis

Before we can effectively design a data base we must know and analyze the
expectation of the users and the intended uses of the database in as much as detail.

2. Conceptual data base design

The goal for this phase I s to produce a conceptual schema for the database that is
independent of a specific DBMS.

We often use a high level data model such er-model during this
phase
We specify as many of known database application on
transactions as possible using a notation the is independent of
any specific dbms.
Often the dbms choice is already made for the organization the
intent of conceptual design still to keep , it as free as possible
from implementation consideration.

3. Choice of a DBMS

The choice of dbms is governed by a no. of factors some technical other economic
and still other concerned with the politics of the organization.

The economics and organizational factors that offer the choice of the dbms are:
Software cost, maintenance cost, hardware cost, database creation and conversion
cost, personnel cost, training cost, operating cost.

4. Data model mapping (logical database design)

During this phase, we map the conceptual schema from the high level data model
used on phase 2 into a data model of the choice dbms.

5. Physical databse design

During this phase we design the specification for the database in terms of physical
storage structure ,record placement and indexes.

6. Database system implementation and tuning

During this phase, the database and application programs are implemented, tested
and eventually deployed for service.
 Functional Dependency(Basic concepts, F+, Closure of an Attribute set,
3.2 Armstrong’s axioms)

What is functional dependency?

• Functional Dependency is a relationship that exists between multiple attributes of a

relation.
• This concept is given by E. F. Codd.
• Functional dependency represents formalism on the infrastructure of relation.
• It is a type of constraint existing between various attributes of a relation.
• It is used to define various normal forms.
• These dependencies are restrictions imposed on the data in database.
• If P is a relation with A and B attributes, a functional dependency between these two
attributes is represented as {A → B}. It specifies that,

A It is a determinant set.
B It is a dependent attribute.
A functionally determines B.
{A → B}
B is a functionally dependent on A.

• Each value of A is associated precisely with one B value. A functional dependency is

trivial if B is a subset of A.
• 'A' Functionality determines 'B' {A → B} (Left hand side attributes determine the values
of Right hand side attributes).

For example: <Employee> Table

EmpId EmpName

• In the above <Employee> table, EmpName (employee name) is functionally dependent

on EmpId (employee id) because the EmpId is unique for individual names.
• The EmpId identifies the employee specifically, but EmpName cannot distinguish the
EmpId because more than one employee could have the same name.
• The functional dependency between attributes eliminates the repetition of information.
• It is related to a candidate key, which uniquely identifies a tuple and determines the value
of all other attributes in the relation.
Advantages of Functional Dependency

• Functional Dependency avoids data redundancy where same data should not be repeated
at multiple locations in same database.
• It maintains the quality of data in database.
• It allows clearly defined meanings and constraints of databases.
• It helps in identifying bad designs.
• It expresses the facts about the database design.

Let us identify an important special type of FDs:

Definition

A functional dependency X → Y is regular if Y contains only a single attribute.

For example, AB → C is regular, but AB → CD is not, where A, B, C , and D are attributes.

There is an equivalence that explains why we can capture all irregular FDs by considering
only regular ones:

An irregular FD X → A1A2...At (where X is an attribute set, and each Ai (1 ≤ i ≤ t) is an

attribute) is equivalent to:

X → A1

X → A2

...

X → At

Example: AB → CD if and only if AB → C and AB → D.

Again, let F be the set of FDs we have collected. Then:

Definition

The closure of F, denoted as F +, is the set of all regular FDs that can be derived from F .

Do not confuse the closure of F with the closure of an attribute set.

Suppose we are given a relation schema R=(A,B,C,G,H,I) and the set of function
dependencies

A→B,A→C,CG→H,CG→I,B→H
We list several members of F+ here:
 A→H, since A→B and B→H hold, we apply the transitivity rule.

CG→HI. Since CG→H and CG→I , the union rule implies that CG→HI

AG→I, since A→C and CG→I, the pseudo transitivity rule implies that

AG→I holds

Algorithm of compute F+ :

To compute the closure of a set of functional dependencies F:

F+=F

repeat

for each functional dependency f in F+

apply reflexivity and augmentation rules on f add

the resulting functional dependencies to F+

for each pair of functional dependencies f1and f2 in F+ if f1

and f2 can be combined using transitivity

then add the resulting functional dependency to F+

until F+ does not change any further
 CLOSURE OF A SET OF FUNCTIONAL DEPEDENCIES

Given a relational schema R, a functional dependencies f on R is logically implied

by a set of functional dependencies F on R if every relation instance r(R) that
satisfies F also satisfies f.

The closure of F, denoted by F+, is the set of all functional dependencies logically
implied by F.

The closure of F can be found by using a collection of rules called Armstrong

axioms.

Introduction to Axioms Rules

• Armstrong's Axioms is a set of rules.

• It provides a simple technique for reasoning about functional dependencies.
• It was developed by William W. Armstrong in 1974.
• It is used to infer all the functional dependencies on a relational database.

Various Axioms Rules

A. Primary Rules

Reflexivity
Rule 1
If A is a set of attributes and B is a subset of A, then A holds B. { A → B }
Augmentation
Rule 2 If A hold B and C is a set of attributes, then AC holds BC. {AC → BC}
It means that attribute in dependencies does not change the basic dependencies.
Transitivity
If A holds B and B holds C, then A holds C.
Rule 3
If {A → B} and {B → C}, then {A → C}
A holds B {A → B} means that A functionally determines B.

B. Secondary Rules

Union
Rule 1 If A holds B and A holds C, then A holds BC.
If{A → B} and {A → C}, then {A → BC}
Decomposition
Rule 2 If A holds BC and A holds B, then A holds C.
If{A → BC} and {A → B}, then {A → C}
Pseudo Transitivity
Rule 3 If A holds B and BC holds D, then AC holds D.
If{A → B} and {BC → D}, then {AC → D}
Sometimes Functional Dependency Sets are not able to reduce if the set has following
properties,

1. The Right-hand side set of functional dependency holds only one attribute.
2. The Left-hand side set of functional dependency cannot be reduced; it changes the entire
content of the set.
3. Reducing any functional dependency may change the content of the set.

A set of functional dependencies with the above three properties are also called as Canonical or
Minimal.

Trivial Functional Dependency

If A holds B {A → B}, where A is a subset of B, then it is called a Trivial

Trivial
Functional Dependency. Trivial always holds Functional Dependency.
If A holds B {A → B}, where B is not a subset A, then it is called as a Non-
Non-Trivial
Trivial Functional Dependency.
Completely Non- If A holds B {A → B}, where A intersect Y = Φ, it is called as a Completely
Trivial Non-Trivial Functional Dependency.

Example:
Consider relation E = (P, Q, R, S, T, U) having set of Functional Dependencies (FD).
P→Q P→R
QR → S Q→T
QR → U PR → U

Calculate some members of Axioms are as follows,

1. P → T
2. PR → S
3. QR → SU
4. PR → SU

Solution:

1. P → T
In the above FD set, P → Q and Q → T
So, Using Transitive Rule: If {A → B} and {B → C}, then {A → C}
∴ If P → Q and Q → T, then P → T.
P→T

2. PR → S
In the above FD set, P → Q
As, QR → S
So, Using Pseudo Transitivity Rule: If{A → B} and {BC → D}, then {AC → D}
∴ If P → Q and QR → S, then PR → S.
PR → S
3. QR → SU
In above FD set, QR → S and QR → U
So, Using Union Rule: If{A → B} and {A → C}, then {A → BC}
∴ If QR → S and QR → U, then QR → SU.
QR → SU

4. PR → SU
So, Using Pseudo Transitivity Rule: If{A → B} and {BC → D}, then {AC → D}
∴ If PR → S and PR → U, then PR → SU.
PR → SU

Example: Assume that there are 4 attributes A, B, C, D, and that

F = {A → B, B → C }. Then, F + includes all the following FDs:

A → A, A → B, A → C , B → B, B → C , C → C , D → D, AB → A, AB → B, AB → C , AC
→ A, AC → B, AC → C , AD → A, AD → B, AD → C , AD → D, BC → B, BC → C , BD →
B, BD → C , BD → D, CD → C , CD → D, ABC → A, ABC → B, ABC → C , ABD → A,
ABD → B, ABD → C , ABD → D, BCD → B, BCD → C , BCD → D, ABCD → A, ABCD →
B, ABCD → C , ABCD → D.

Finding the Closure of a Set of FDs

algorithm (F )

/* F is a set of FDs */

1. F + = ∅

2. for each possible attribute set X

3. compute the closure X + of X on F
4. for each attribute A ∈ X +
5. add to F + the FD: X → A

5. return F +

Example: Assume that there are 4 attributes A, B, C , D, and that

F = {A → B, B → C }. To compute F +, we first get:

A+ = AB+ = AC + = ABC + = {A, B, C }

B+ = BC + = {B, C }

C + = {C }

D+ = {D}

AD+ = {A, D}

BC + = {B, C }

BD+ = BCD+ = {B, C , D} ABD+ = ABCD+ = {A, B, C , D} ACD+ = {A, C , D}

It is easy to generate the FDs in F + from the closures of the above attribute sets.

Closure of Attribute sets:-

To test whether a set α is a super key, we must devise an algorithm for omputing
the set of attributes functionally determined by alpha. One way of doing this is to
compute F+ take all functional dependencies. However doing so can be
expensive, since F+ can be large.

Closure of Attribute Sets

Given a set of attributes α, define the closure of α under F (denoted by α+) as
the set of attributes that are functionally determined by α

under F: α → β is in F+ <=> β ⊆ α+

Algorithm to compute α+, the closure of α under F result := α; while

(changes to result) do for each β → γ in F do begin

if β ⊆ result then
result :=

result ∪ γ end
 Example of Attribute Set Closure
R=(A,B,C,G,H,I)
F={A→B A→C CG→HCG→IB→H}

(AG)+

1. result = AG

2. result = ABCG (A → C and A → B)

3. result = ABCGH (CG → H and CG ⊆ AGBC)

4. result = ABCGHI (CG → I and CG ⊆ AGBCH)
Is AG a candidate key?
Is AG a super key?

Does AG → R? == Is (AG)+ ⊇ R
Is any subset of AG a superkey?

Does A → R? == Is (A)+ ⊇ R

Does G → R? == Is (G)+ ⊇ R

Uses of Attribute Closure

There are several uses of the attribute closure algorithm:
Testing for super key:

To test if α is a superkey, we compute α+, and check if α+ contains all

attributes of R.

Testing functional dependencies

To check if a functional dependency α → β holds (or, in other words, is

in F+), just check if β ⊆ α+.

That is, we compute α+ by using attribute closure, and then check if it

contains β.
 Is a simple and cheap test, and very useful
Computing closure of F

For each γ ⊆ R, we find the closure γ+, and for each S ⊆ γ+, we output a
functional dependency γ → S.
 Canonical Cover
Sets of functional dependencies may have redundant dependencies that can be inferred
from the others

Eg: A → C is redundant in: {A → B, B → C, A → C} Parts of a

functional dependency may be redundant

E.g. on RHS: {A → B, B → C, A → CD} can be simplified

to {A→B, B→C, A→D}

E.g. on LHS: {A → B, B → C, AC → D} can be simplified

to {A→B, B→C, A→D}

Intuitively, a canonical cover of F is a “minimal” set of functional dependencies
equivalent to F, having no redundant dependencies or redundant parts of dependencies

Extraneous Attributes
Consider a set F of functional dependencies and the functional dependency
α → β in F.
Attribute A is extraneous in α if A ∈ α and F logically implies (F – {α →β}) ∪ {(α – A) → β}.

Attribute A is extraneous in β if A ∈ β and the set of functional dependencies (F – {α → β})

∪ {α →(β – A)} logically implies F.

Note: implication in the opposite direction is trivial in each of the cases above, since a “stronger”
functional dependency always implies a weaker one

Example: Given F = {A → C, AB → C }

B is extraneous in AB → C because {A → C, AB → C} logically implies A → C (I.e. the result of

dropping B from AB → C).

Example: Given F = {A → C, AB → CD}

C is extraneous in AB → CD since AB → C can be inferred even after deleting C

 Testing if an Attribute is Extraneous
Consider a set F of functional dependencies and the functional dependency α → β in F.

To test if attribute A ∈ α is extraneous in α

compute ({α} – A)+ using the dependencies in F
check that ({α} – A)+ contains A; if it does, A is extraneous
To test if attribute A ∈ β is extraneous in β

compute α+ using only the dependencies in F’ = (F – {α → β})∪ {α →(β – A)},

check that α+ contains A; if it does, A is extraneous

Canonical Cover
A canonical cover for F is a set of dependencies Fc such that F logically implies all dependencies in
Fc, and
Fc logically implies all dependencies in F, and
No functional dependency in Fc contains an extraneous attribute, and
Each left side of functional dependency in Fc is unique.
To compute a canonical cover for F: repeat
Use the union
rule to

replace any dependencies in F α1 → β1 and α1 → β2 with

α1→β1β2 Find a functional dependency α → β with an

extraneous attribute either in α or in β If an extraneous

attribute is found, delete it from α → β until F does not change Note:

Union rule may become applicable after some extraneous attributes have
been deleted, so it has to be re-applied
 Example of Computing a Canonical Cover

R=(A,B,C)F={A→BC B→C A→B AB→C}

Combine A → BC and A → B into A → BC

Set is now {A → BC, B → C, AB → C}

A is extraneous in AB → C

Check if the result of deleting A from AB → C is implied by the other

dependencies

Yes: in fact, B → C is already present!

Set is now {A → BC, B → C}

C is extraneous in A → BC

Check if A → C is logically implied by A → B and the other

dependencies Yes: using transitivity on A → B and B →
C.

Can use attribute closure of A in more complex cases

The canonical cover is: A→B B→C

Candidate Key Revisited

In creating a table, it may seem that so far we have been specifying candidate keys based on
our preferences. This illusion is created because we did not understand FDs. In fact,
candidate keys are not up to us at all. Instead, they are uniquely determined by the set F of
functional dependencies from the underlying application. See the next slide.

Let F be a set of FDs, and R a relation.

Definition

A candidate key is a set X of attributes in R such that

X + includes all the attributes in R.

There is no proper subset Y of X such that Y + includes all the attributes in R.

Note: A proper subset Y is a subset of X such that Y ƒ= X (i.e., X has at least one element
not in Y ).

Example. Consider a table R(A, B, C , D), and that

F = {A → B, B → C }.

A is not a candidate key, because A+ = {A, B, C } which does not include D.

ABD is not a candidate key even though ABD+ = {A, B, C , D}.

This is because AD+ = {A, B, C , D}, namely, there is a proper

subset AD of ABD such that AD+ includes all the attributes.

AD is a candidate key.

3.3 Concept of Decomposition

What is decomposition?

• Decomposition is the process of breaking down in parts or elements.

• It replaces a relation with a collection of smaller relations.
• It breaks the table into multiple tables in a database.
• It should always be lossless, because it confirms that the information in the original
relation can be accurately reconstructed based on the decomposed relations.
• If there is no proper decomposition of the relation, then it may lead to problems like loss
of information.

3.4 Desirable Properties of Decomposition ( Lossless join, Lossy join,

. Dependency Presevation)

Properties of Decomposition

Following are the properties of Decomposition,

1. Lossless Decomposition
2. Dependency Preservation
3. Lack of Data Redundancy

1. Lossless Decomposition
• Decomposition must be lossless. It means that the information should not get lost from
the relation that is decomposed.
• It gives a guarantee that the join will result in the same relation as it was decomposed.
• A decomposition of a relation scheme R<S,F> into the relation schemes Ri(1<=i<=n)
is said to be a lossless join decomposition or simply lossless if for every relation R
that satisfies the FDs in F, the natural join of the projections or R gives the original
relation R, i.e,
• R=∏R1( R ) ∏R2( R ) …….. ∏Rn( R )
•
• If R is subset of ∏R1( R ) ∏R2( R ) Then the decomposition is called lossy.

Example:
Let's take 'E' is the Relational Schema, With instance 'e'; is decomposed into: E1, E2, E3, . . . .
En; With instance: e1, e2, e3, . . . . en, If e1 ⋈ e2 ⋈ e3 . . . . ⋈ en, then it is called as 'Lossless
Join Decomposition'.

• In the above example, it means that, if natural joins of all the decomposition give the original
relation, then it is said to be lossless join decomposition.

Example: <Employee_Department> Table

Eid Ename Age City Salary Deptid DeptName

E001 ABC 29 Pune 20000 D001 Finance
E002 PQR 30 Pune 30000 D002 Production
E003 LMN 25 Mumbai 5000 D003 Sales
E004 XYZ 24 Mumbai 4000 D004 Marketing
E005 STU 32 Bangalore 25000 D005 Human Resource

• Decompose the above relation into two relations to check whether decomposition is lossless
or lossy.
• Now, we have decomposed the relation that is Employee and Department.

Relation 1 : <Employee> Table

Eid Ename Age City Salary

E001 ABC 29 Pune 20000
E002 PQR 30 Pune 30000
E003 LMN 25 Mumbai 5000
E004 XYZ 24 Mumbai 4000
E005 STU 32 Bangalore 25000

• Employee Schema contains (Eid, Ename, Age, City, Salary).

Relation 2 : <Department> Table

Deptid Eid DeptName

D001 E001 Finance
D002 E002 Production
 D003 E003 Sales
D004 E004 Marketing
D005 E005 Human Resource

• Department Schema contains (Deptid, Eid, DeptName).

• So, the above decomposition is a Lossless Join Decomposition, because the two relations
contains one common field that is 'Eid' and therefore join is possible.
• Now apply natural join on the decomposed relations.

Employee ⋈ Department

Eid Ename Age City Salary Deptid DeptName

E001 ABC 29 Pune 20000 D001 Finance
E002 PQR 30 Pune 30000 D002 Production
E003 LMN 25 Mumbai 5000 D003 Sales
E004 XYZ 24 Mumbai 4000 D004 Marketing
E005 STU 32 Bangalore 25000 D005 Human Resource

Hence, the decomposition is Lossless Join Decomposition.

• If the <Employee> table contains (Eid, Ename, Age, City, Salary) and <Department> table
contains (Deptid and DeptName), then it is not possible to join the two tables or relations,
because there is no common column between them. And it becomes Lossy Join
Decomposition.

2. Dependency Preservation

• Dependency is an important constraint on the database.

• Every dependency must be satisfied by at least one decomposed table.
• If {A → B} holds, then two sets are functional dependent. And, it becomes more useful for
checking the dependency easily if both sets in a same relation.
• This decomposition property can only be done by maintaining the functional dependency.
• In this property, it allows to check the updates without computing the natural join of the
database structure.

Given a relation scheme R<S,F> where F is the associated set of functional

dependencies on the attributes in S,R is decomposed into the relation schemes
R1,R2,…Rn with the fds F1,F2…Fn, then this decomposition of R is dependency
preserving if the closure of F’ (where F’=F1 U F2 U … Fn)

Example:
 Let R(A,B,C) AND F={A→B}. Then the decomposition of R into R1(A,B) and
R2(A,C) is lossless because the FD { A→B} is contained in R1 and the common
attribute A is a key of R1.

Example:

Let R(A,B,C) AND F={A→B}. Then the decomposition of R into R1(A,B) and
R2(B,C) is not lossless because the common attribute B does not functionally
determine either A or C. i.e, it is not a key of R1 or R 2.

Example:

Let R(A,B,C,D) and F={A→B, A→C, C→D,}. Then the decomposition of R into
R1(A,B,C) with the FD F1={ A→B , A→C }and R2(C,D) with FD F2={ C→D} . In
this decomposition all the original FDs can be logically derived from F1 and F2, hence
the decomposition is dependency preserving also . the common attribute C forms a key
of R2. The decomposition is lossless.

Example:

Let R(A,B,C,D) and F={A→B, A→C, A→D,}. Then the decomposition of R into
R1(A,B,D) with the FD F1={ A→B , A→D }and R2(B,C) with FD F2={ } is lossy
because the common attribute B is not a candidate key of either R1 and R2 . In
addition , the fds A→C is not implied by any fds R1 or R2. Thus the decomposition is
not dependency preserving.

3. Lack of Data Redundancy

• Lack of Data Redundancy is also known as a Repetition of Information.

• The proper decomposition should not suffer from any data redundancy.
• The careless decomposition may cause a problem with the data.
• The lack of data redundancy property may be achieved by Normalization process.
 Full functional dependency:

Given a relational scheme R and an FD X→Y ,Y is fully functional dependent on X if

there is no Z, where Z is a proper subset of X such that Z→Y. The dependency X→Y
is left reduced, there being no extraneous attributes attributes in the left hand side of
the dependency.

Partial dependency:

Given a relation dependencies F defined on the attributes of R and K as a candidate

key ,if X is a proper subset of K and if F|= X→A, then A is said to be partial
dependent on K

Prime attribute and non prime attribute:

A attribute A in a relation scheme R is a prime attribute or simply prime if A is part

of any candidate key of the relation. If A is not a part of any candidate key of R, A is
called a nonprime attribute or simply non prime .

Trivial functional dependency:

A FD X→Y is said to be a trivial functional dependency if Y is subset of X.

Introduction to Normalization

The basic objective of normalization is to reduce redundancy which means that

information is to be stored only once. Storing information several times leads to
wastage of storage space and increase in the total size of the data stored. Relations are
normalized so that when relations in a database are to be altered during the life time of
the database, we do not lose information or introduce inconsistencies. The type of
alterations normally needed for relations are:

o Insertion of new data values to a relation. This should be possible without being
forced to leave blank fields for some attributes.
o Deletion of a tuple, namely, a row of a relation. This should be possible without
losing vital information unknowingly.
 o Updating or changing a value of an attribute in a tuple. This should be possible
without exhaustively searching all the tuples in the relation.

3.5 Concept of normalization, Normal Forms (1NF,2NF and 3NF),

. Examples
• Normalization is a process of organizing the data in the database.
• It is a systematic approach of decomposing tables to eliminate data redundancy.
• It was developed by E. F. Codd.
• Normalization is a multi-step process that puts the data into a tabular form by removing the
duplicate data from the relation tables.
• It is a step by step decomposition of complex records into simple records.
• It is also called as Canonical Synthesis.
• It is the technique of building database structures to store data.

Definition of Normalization

“Normalization is a process of designing a consistent database by minimizing redundancy and

ensuring data integrity through decomposition which is lossless.”

Features of Normalization

• Normalization avoids the data redundancy.

• It is a formal process of developing data structures.
• It promotes the data integrity.
• It ensures data dependencies make sense that means data is logically stored.
• It eliminates the undesirable characteristics like Insertion, Updation and Deletion Anomalies.

Types of Normalization

Following are the types of Normalization:

1. First Normal Form
2. Second Normal Form
3. Third Normal Form
4. Fourth Normal Form
5. Fifth Normal Form
6. BCNF (Boyce – Codd Normal Form)
7. DKNF (Domain Key Normal Form)

1. First Normal Form (1NF)

• First Normal Form (1NF) is a simple form of Normalization.

• It simplifies each attribute in a relation.
• In 1NF, there should not be any repeating group of data.
• Each set of column must have a unique value.
• It contains atomic values because the table cannot hold multiple values.
Example: Employee Table

ECode Employee_Name Department_Name

1 ABC Sales, Production
2 PQR Human Resource
3 XYZ Quality Assurance, Marketing

Employee Table using 1NF

ECode Employee_Name Department_Name

1 ABC Sales
1 ABC Production
2 PQR Human Resource
3 XYZ Quality Assurance
3 XYZ Marketing

2. Second Normal Form (2NF)

• In 2NF, the table is required in 1NF.

• The main rule of 2NF is, 'No non-prime attribute is dependent on the proper subset of any
candidate key of the table.'
• An attribute which is not part of candidate key is known as non-prime attribute.

Example : Employee Table using 1NF

ECode Employee_Name Employee_Age

1 ABC 38
1 ABC 38
2 PQR 38
3 XYZ 40
3 XYZ 40

Candidate Key: ECode, Employee_Name

Non prime attribute: Employee_Age

• The above table is in 1NF. Each attribute has atomic values. However, it is not in 2NF
because non prime attribute Employee_Age is dependent on ECode alone, which is a proper
subset of candidate key. This violates the rule for 2NF as the rule says 'No non-prime attribute
is dependent on the proper subset of any candidate key of the table'.

2NF (Second Normal Form) : Employee1 Table

ECode Employee_Age
 1 38
2 38
3 40

Employee2 Table

ECode Employee_Name
1 ABC
1 ABC
2 PQR
3 XYZ
3 XYZ

• Now, the above tables comply with the Second Normal Form (2NF).

3. Third Normal Form (3NF)

• Third Normal Form (3NF) is used to minimize the transitive redundancy.

• In 3NF, the table is required in 2NF.
• While using the 2NF table, there should not be any transitive partial dependency.
• 3NF reduces the duplication of data and also achieves the data integrity.

Example : <Employee> Table

EId Ename DOB City State Zip

001 ABC 10/05/1990 Pune Maharashtra 411038
002 XYZ 11/05/1988 Mumbai Maharashtra 400007

• In the above <Employee> table, EId is a primary key but City, State depends upon Zip code.
• The dependency between Zip and other fields is called Transitive Dependency.
• Therefore we apply 3NF. So, we need to move the city and state to the new
<Employee_Table2> table, with Zip as a Primary key.

<Employee_Table1> Table

EId Ename DOB Zip

001 ABC 10/05/1990 411038
002 XYZ 11/05/1988 400007

<Employee_Table2> Table
 City State Zip
Pune Maharashtra 411038
Mumbai Maharashtra 400007

• The advantage of removing transitive dependency is, it reduces the amount of data
dependencies and achieves the data integrity.
• In the above example, using with the 3NF, there is no redundancy of data while inserting the
new records.
• The City, State and Zip code will be stored in the separate table. And therefore the updation
becomes more easier because of no data redundancy.

4. BCNF (Boyce – Code Normal Form)

• BCNF which stands for Boyce – Code Normal From is developed by Raymond F. Boyce and
E. F. Codd in 1974.
• BCNF is a higher version of 3NF.
• It deals with the certain type of anomaly which is not handled by 3NF.
• A table complies with BCNF if it is in 3NF and any attribute is fully functionally dependent
that is A → B. (Attribute 'A' is determinant).
• If every determinant is a candidate key, then it is said to be BCNF.
• Candidate key has the ability to become a primary key. It is a column in a table.

Example : <EmployeeMain> Table

Empid Ename DeptName DepType

E001 ABC Production D001
E002 XYZ Sales D002

The functional dependencies are:

Empid → EmpName
DeptName → DeptType

Candidate Key:
Empid
DeptName

• The above table is not in BCNF as neither Empid nor DeptName alone are keys.
• We can break the table in three tables to make it comply with BCNF.

<Employee> Table

Empid EmpName
E001 ABC
E002 XYZ
 <Department> Table

DeptName DeptType
Production D001
Sales D002

<Emp_Dept> Table

Empid DeptName
E001 Production
E002 Sales

Now, the functional dependencies are:

Empid → EmpName
DeptName → DeptType

Candidate Key:
<Employee> Table : Empid
<Department> Table : DeptType
<Emp_Dept> Table : Empid, DeptType

• So, now both the functional dependencies left side part is a key, so it is in the BCNF.

5. Fourth Normal Form (4NF)

• Fourth Normal Form (4NF) does not have non-trivial multivalued dependencies other than a
candidate key.
• 4NF builds on the first three normal forms (1NF, 2NF and 3NF) and the BCNF.
• It does not contain more than one multivalued dependency.
• This normal form is rarely used outside of academic circles.

For example : A table contains a list of three things that is 'Student', 'Teacher', 'Book'.
Teacher is in charge of Student and recommended book for each student. These three
elements (Student, Teacher and Book) are independent of one another. Changing the student's
recommended book, for instance, has no effect on the student itself. This is an example of
multivalued dependency, where an item depends on more than one value. In this example, the
student depends on both teacher and book.

• Therefore, 4NF states that a table should not have more than one dependencies.

6. Fifth Normal Form (5NF)

• 5NF is also knows as Project-Join Normal Form (PJ/NF).

• It is designed for reducing the redundancy in relational databases.
• 5NF requires semantically related multiple relationships, which are rare.
 • In 5NF, if an attribute is multivalued attribute, then it must be taken out as a separate entity.
• While performing 5NF, the table must be in 4NF.

7. DKNF (Domain Key Normal Form)

• DKNF stands for Domain Key Normal Form requires the database that contains no constraints
other than domain constraints and key constraints.
• In DKNF, it is easy to build a database.
• It avoids general constraints in the database which are not clear domain or key constraints.
• The 3NF, 4NF, 5NF and BCNF are special cases of the DKNF.
• It is achieved when every constraint on the relation is a logical consequence of the definition.

Example :-

Unnormalized relation:

FIRST NORMAL FORM:

A relation scheme is said to be in first normal form(1NF) if the values in the domain of each
attribute of the relation are atomic. In other words, only one value is associated with each attribute
and the value is not a set of values or a list of values.
Functional dependencies are:

orderno → orderdate

SECOND NORMAL FORM:

 Example 2:

What is denormalization?

• Denormalization is the process of increasing the redundancy in the database.

• It is the opposite process of normalization.
• It is mostly done for improving the performance.
• It is a strategy that database managers use to increase the performance of a database structure.
• Denormalization adds redundant data normalized database for reducing the problems with
database queries which combine data from the various tables into a single table.
• The process of adding redundant data to get rid of complex join, in order to optimize database
performance. This is done to speed up database access by moving from higher to lower form
of normalization.
• Data is included in one table from another in order to eliminate the second table which
reduces the number of JOINS in a query and thus achieves performance.
3.6Keys Concept with Examples : Candidate Keys and Super Keys,
Algorithm to find the super keys / primary key for a relation
Solved Exercises :
Ex. 9.5.1 : Consider the relation R={A,B,C,D,E,F,G,H,I,J} the functional dependency is
F={ ABD->E,AB->G,B->F,C->J,CJ->I,G->H}
what are the candidate keys of R?
what are the super keys of R?
Assignment 4