MODULE-3

Problems Caused by Redundancy

Storing the same information redundantly, that is, in more than one place within
a database, can lead to several problems:

Update Anomalies: If one copy of such repeated data is updated, an

inconsistency is created unless all copies similarly updated.
Insertion Anomalies: It is not be possible to store certain information unless
some other, unrelated, information is stored as well.
Deletion Anomalies: It may not be possible to delete certain information
without losing Some other, unrelated, information as well.
Consider a relation obtained by translating a variant of the Hourly_Emps entity
Hourly_Emps(ssn, sname, lot, rating, hourly_wages, hours_worked)
Functional dependency in DBMS
The attributes of a table is said to be dependent on each other when an attribute
of a table uniquely identifies another attribute of the same table.
Then the following will represent the functional dependency between attributes
with an arrow sign −

A -> B
Example
The following is an example that would make it easier to understand functional
dependency −
We have a <Department> table with two attributes − DeptId and DeptName.

DeptId = Department ID
DeptName = Department Name

The DeptId is our primary key.

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.

DeptId DeptName

001 Finance

002 Marketing

003 HR

Therefore, the above functional dependency

between DeptId and DeptName can be determined as DeptId is functionally
dependent on DeptName −

DeptId -> DeptName

Types of Functional Dependency

Functional Dependency has three forms −

 Trivial Functional Dependency

 Non-Trivial Functional Dependency
 Completely Non-Trivial Functional Dependency
Let us begin with Trivial Functional Dependency −
Trivial Functional Dependency
It occurs when B is a subset of A in −

A ->B

Example
We are considering the same <Department> table with two attributes to
understand the concept of trivial dependency.
The following is a trivial functional dependency since DeptId is a subset
of DeptId and DeptName

{ DeptId, DeptName } -> Dept Id

Non –Trivial Functional Dependency

It occurs when B is not a subset of A in −
A ->B

Example

DeptId -> DeptName

The above is a non-trivial functional dependency since DeptName is a not a

subset of DeptId.
Completely Non - Trivial Functional Dependency
It occurs when A intersection B is null in −

A ->B

Armstrong’s Axioms Property of Functional Dependency

Armstrong’s Axioms property was developed by William Armstrong in 1974 to
reason about functional dependencies.
The property suggests rules that hold true if the following are satisfied:

 Transitivity
If A->B and B->C, then A->C i.e. a transitive relation.
 Reflexivity
A-> B, if B is a subset of A.
 Augmentation
The last rule suggests: AC->BC, if A->B
 Closure of an Attribute Set-

 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}+.

Example-
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 attribute A-
A+ = { A }

={A,B,C} ( Using A → BC )

={A,B,C,D,E} ( Using BC → DE )

={A,B,C,D,E,F} ( Using D → F )

={A,B,C,D,E,F,G} ( Using CF → G )

Thus,

A+ = { A , B , C , D , E , F , G }

Closure of attribute D-
 D+ = { D }

= { D , F } ( Using D → F )

We can not determine any other attribute using attributes D and F contained in
the result set.

Thus,

D+ = { D , F }

Closure of attribute set {B, C}-

{ 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 )

Thus,

{ B , C }+ = { B , C , D , E , F , G }

Super Key-

 If the closure result of an attribute set contains all the attributes of the relation,
then that attribute set is called as a super key of that relation.
 Thus, we can say-

“The closure of a super key is the entire relation schema.”

Example-
 In the above example,
 The closure of attribute A is the entire relation schema.
 Thus, attribute A is a super key for that relation.

Candidate Key-

 If there exists no subset of an attribute set whose closure contains all the
attributes of the relation, then that attribute set is called as a candidate key of
that relation.

Example-

In the above example,

 No subset of attribute A contains all the attributes of the relation.
 Thus, attribute A is also a candidate key for that relation.

Example-2
Given relational schema R( P Q R S T) having following attributes P Q R S and
T, also there is a set of functional dependency denoted by FD = { P->QR, RS-
>T, Q->S, T-> P }. Determine Closure of ( T )+

Example 3

Given R(E-ID, E-NAME, E-CITY, E-STATE)

FDs = { E-ID->E-NAME, E-ID->E-CITY, E-ID->E-STATE, E-CITY->E-

STATE }
The attribute closure of E-ID can be calculated as:
1. Add E-ID to the set {E-ID}
2. Add Attributes which can be derived from any attribute of set. In this case,
E-NAME and E-CITY, E-STATE can be derived from E-ID. So these are
also a part of closure.
3. As there is one other attribute remaining in relation to be derived from E-
ID. So result is:
(E-ID)+ = {E-ID, E-NAME, E-CITY, E-STATE }
Similarly,
(E-NAME)+ = {E-NAME}
(E-CITY)+ = {E-CITY, E_STATE}
Candidate Key
Candidate Key is minimal set of attributes
E-ID and it is minimal as well. So it will be Candidate key of the relation.
A candidate key may or may not be a primary key.
Super Key
Super Key is set of attributes of a relation which can be used to identify a tuple
uniquely
.For Example, each tuple of EMPLOYEE relation given in Table 1 can be
uniquely identified by
E-ID or (E-ID, E-NAME) or (E-ID, E-CITY) or (E-ID, E-STATE) or (E_ID,
E-NAME, E-STATE) etc.
So all of these are super keys of EMPLOYEE relation.
Note: A candidate key is always a super key but vice versa is not true.
NORMALIZATION

 Normalization is the process of organizing the data in the database.

 Normalization is used to minimize the redundancy from a relation or set of
relations. It is also used to eliminate the undesirable characteristics like
Insertion, Update and Deletion Anomalies.
 Normalization divides the larger table into the smaller table and links them
using relationship.
 The normal form is used to reduce redundancy from the database table.

Types of Normal Forms

There are the four types of normal forms:
First Normal Form
First Normal Form is defined in the definition of relations (tables) itself.
1. This rule defines that all the attributes in a relation must have atomic
domains.
2. The values in an atomic domain are indivisible units.

We re-arrange the relation (table) as below, to convert it to First Normal Form.

Each attribute must contain only a single value from its pre-defined domain.
Second Normal Form
Before we learn about the second normal form, we need to understand the
following –
1. IT SHOULD BE IN 1NF
2. THERE SHLD NOT BE ANY PARTIAL DEPENDENCY
 Prime attribute − An attribute, which is a part of the candidate-key, is
known as a prime attribute.
 Non-prime attribute − An attribute, which is not a part of the prime-key,
is said to be a non-prime attribute.
If we follow second normal form,
then every non-prime attribute should be fully functionally dependent on prime
key attribute. That is, if X →A holds, then there should not be any proper subset
Y of X, for which Y → A also holds true.
CD=(S_IDP_ID)

We see here in Student_Project relation that the prime key attributes are Stu_ID
and Proj_ID. According to the rule, non-key attributes, i.e. Stu_Name and
Proj_Name must be dependent upon both and not on any of the prime key
attribute individually.
But we find that Stu_Name can be identified by Stu_ID and Proj_Name can be
identified by Proj_ID independently. This is called partial dependency, which
is not allowed in Second Normal Form.

We broke the relation in two as depicted in the above picture. So there exists no
partial dependency

EXAMPLES
R(ABCDEF) IS NOT IN 2NF
FUNCIONAL DEPENDENCIES
{ C->F X
E->A, X
EC->D 2NF
A->B} 2NF
C+=={C,F}
E+=={E,A,B}
EC+=={E,C,F,A,B,D}
A+=={A,B}
CANDIDATE KEY={EC}
PRIME ATTRIBUTES=={E,C}
NON PRIME ATTRIBUTES=={A,B,D,F}
TRY THIS
R(A,B,C,D,E)
D🡪B
CE🡪D
C🡪A
R1(B,D,C,E) d🡪b,ce🡪d,
R2(C,A) c🡪a

Third Normal Form

For a relation to be in Third Normal Form, it must be in Second Normal form
and the following must satisfy –
1. IT SHLD 2NF
2. THERE SHLD NOT BE ANY TRANSITIVE DEPENDENCY

 No non-prime attribute is transitively dependent on prime key attribute.

 For any non-trivial functional dependency, X → A, then either −
 X is a superkey or,
 A is prime attribute.

We find that in the above Student_detail relation, Stu_ID is the key and only
prime key attribute.
We find that City can be identified by Stu_ID as well as Zip itself.
Neither Zip is a superkey nor is City a prime attribute.
Additionally, Stu_ID→ Zip → City, so there exists transitive dependency.
To bring this relation into third normal form, we break the relation into two
relations as follows −

PROBLEM
1.R(ABCDE)
AB🡪CD YES
D🡪A YES
BC🡪DE YES

CD AB+= {A,B,C,D,E}
D={D,A}
BC={B,C,D,E,A}

X🡪A
X IS SK ( OR)
A IS PA
SUPER KEY/CANDIDATE KEYS ARE AB, BC
PRIME ATTRIBUTES={A,B,C}
NON PRIME ATTRIBUTES={D,E}

HENCE IT IS IN 3NF

TRY THIS
R(ABCDE)
A🡪B
BC🡪E
DE🡪A
CD { ACD, BCD, CDE }

Boyce-Codd Normal Form

Boyce-Codd Normal Form (BCNF) is an extension of Third Normal Form on
strict terms. BCNF states that –
1. IT SHLD BE IN 3NF
2. For any non-trivial functional dependency, X → A, X must be a super-key.
In the above image, Stu_ID is the super-key in the relation Student_Detail
and
Zip is the super-key in the relation ZipCodes. So,
Stu_ID→Stu_Name, Zip
and
Zip → City
Which confirms that both the relations are in BCNF.

EX1:
R(ABCDE)
A🡪B
B🡪E
C🡪D
CD {
A={A,B,E}
B+
 C+
AC={A,B,E,C,D}

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.

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.

Example:

E1, E2, E3, . . . . En; With instance: e1, e2, e3, . . . .en, If e1 ⋈ e2 ⋈ e3 . . . .
Let's take 'E' is the Relational Schema, With instance 'e'; is decomposed into:

⋈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

 E00 ABC 29 Pune 20000 D001 Finance
1
E00 PQR 30 Pune 30000 D002 Production
2
E00 LMN 25 Mumbai 5000 D003 Sales
3
E00 XYZ 24 Mumbai 4000 D004 Marketing
4
E00 STU 32 Bangalor 25000 D005 Human Resource
5 e

 Decompose the above relation into two relations to check whether a

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 E00 Finance
1
D002 E00 Production
2
 D003 E00 Sales
3
D004 E00 Marketing
4
D005 E00 Human Resource
5

 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

E00 ABC 29 Pune 20000 D001 Finance
1
E00 PQR 30 Pune 30000 D002 Production
2
E00 LMN 25 Mumbai 5000 D003 Sales
3
E00 XYZ 24 Mumbai 4000 D004 Marketing
4
E00 STU 32 Bangalor 25000 D005 Human Resource
5 e

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

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.

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.
Time for an 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 (SID IS NOT PRIMARY
KEY)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_i course
d

1 Science

1 Maths

2 C#

2 Php

And, Hobbies Table,

s_i hobby
d

1 Cricket
1 Hockey

2 Cricket

2 Hockey

Now this relation satisfies the fourth normal form.

Fifth normal form (5NF)

 A relation is in 5NF if it is in 4NF and not contains any join dependency

and joining should be lossless.
 5NF is satisfied when all the tables are broken into as many tables as
possible in order to avoid redundancy.
 5NF is also known as Project-join normal form (PJ/NF).

Example
SUBJECT LECTURER SEMESTER

Computer Anshika Semester 1

Computer John Semester 1

Math John Semester 1

Math Akash Semester 2

Chemistr Praveen Semester 1

y
next →← prev
Fifth normal form (5NF)

 A relation is in 5NF if it is in 4NF and not contains any join

dependency and joining should be lossless.
 5NF is satisfied when all the tables are broken into as many
tables as possible in order to avoid redundancy.
  5NF is also known as Project-join normal form (PJ/NF).

Example
SUBJECT LECTURER SEMESTER

Computer Anshika Semester 1

Computer John Semester 1

Math John Semester 1

Math Akash Semester 2

Chemistr Praveen Semester 1

y

In the above table, John takes both Computer and Math class for
Semester 1 but he doesn't take Math class for Semester 2. In this
case, combination of all these fields required to identify a valid
[Link] we add a new Semester as Semester 3 but do not know
about the subject and who will be taking that subject so we leave
Lecturer and Subject as NULL. But all three columns together acts
as a primary key, so we can't leave other two columns blank.

So to make the above table into 5NF, we can decompose it into

three relations P1, P2 & P3:

P1

SEMESTER SUBJECT

Semester 1 Computer

Semester 1 Math

Semester 1 Chemistry

Semester 2 Math
P2

SUBJECT LECTURER

Computer Anshika

Computer John

Math John

Math Akash

Chemistry Praveen

P3

SEMSTER LECTURER

Semester 1 Anshika

Semester 1 John

Semester 1 John

Semester 2 Akash

Semester 1 Praveen