School of Computing

Science and Engineering

Program: B.TECH
Course Code:E2UC302B
Course Name: Database Management
System
 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Recommended Books
Text books
 Abraham Silberschatz, Henry F. Korth and S. Sudarshan- “Database System
Concepts”, Fourth Edition, McGraw-Hill, 2002.
Reference Book
 Ramez Elmasri and Shamkant B. Navathe, “Fundamental Database Systems”,
Third Edition, Pearson Education, 2003.
 Raghu Ramakrishnan, “Database Management System”, Tata McGraw- Hill
Publishing Company, 2003.
 Hector Garcia–Molina, Jeffrey D.Ullman and Jennifer Widom- “Database System
Implementation”- Pearson Education- 2000
 Peter Rob and Corlos Coronel- “Database System, Design, Implementation and
Management”, Thompson Learning Course Technology- Fifth edition, 2003
Additional online materials
 Coursera - https://www.coursera.org/learn/database-management
 NPTEL- https://nptel.ac.in/courses/106/105/106105175/
 https://www.coursera.org/learn/research-methods
 https://www.coursera.org/browse/physical-science-and-engineering/research-
methods
Program Name: B.TECH Program Code: E2UC302B
 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Functional Dependency
 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.
X → Y

The left side of FD is known as a determinant, the right side of the

production is known as a dependent.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Functional Dependency: Example
 Assume we have an employee table with attributes: Emp_Id,
Emp_Name, Emp_Address.
 Here Emp_Id attribute can uniquely identify the Emp_Name attribute
of employee table because if we know the Emp_Id, we can tell that
employee name associated with it.
 Functional dependency can be written as:
 Emp_Id → Emp_Name

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Types of Functional Dependency

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Types of Functional Dependency

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Inference Rule
 The Armstrong's axioms are the basic inference rule.
 Armstrong's axioms are used to conclude functional
dependencies on a relational database.
 The inference rule is a type of assertion. It can apply to a
set of FD(functional dependency) to derive other FD.
 Using the inference rule, we can derive additional
functional dependency from the initial set.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Inference Rule
1. Reflexive Rule (IR1)
In the reflexive rule, if Y is a subset of X, then X determines Y.
1.If X ⊇ Y then X → Y
Example:
2.X = {a, b, c, d, e}
3.Y = {a, b, c}

2. Augmentation Rule (IR2)

The augmentation is also called as a partial dependency. In augmentation, if X
determines Y, then XZ determines YZ for any Z.
If X → Y then XZ → YZ
Example:
For R(ABCD), if A → B then AC → BC

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Inference Rule
3. Transitive Rule (IR3)
In the transitive rule, if X determines Y and Y determine Z, then X must
also determine Z.
1.If X → Y and Y → Z then X → Z
4. Union Rule (IR4)
Union rule says, if X determines Y and X determines Z, then X must also
determine Y and Z.
2.If X → Y and X → Z then X → YZ
1. X → Y (given)
2. X → Z (given)
3. X → XY (using IR2 on 1 by augmentation with X. Where XX = X)
4. XY → YZ (using IR2 on 2 by augmentation with Y)
5. X → YZ (using IR3 on 3 and 4)

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Inference Rule
5. Decomposition Rule (IR5)
Decomposition rule is also known as project rule. It is the reverse of union
rule.
This Rule says, if X determines Y and Z, then X determines Y and X
determines Z separately.
1.If X → YZ then X → Y and X → Z
Proof:
1. X → YZ (given)
2. YZ → Y (using IR1 Rule)
3. X → Y (using IR3 on 1 and 2)

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Inference Rule
6. Pseudo transitive Rule (IR6)
In Pseudo transitive Rule, if X determines Y and YZ determines W, then XZ
determines W.
1.If X → Y and YZ → W then XZ → W
Proof:
1. X → Y (given)
2. WY → Z (given)
3. WX → WY (using IR2 on 1 by augmenting with W)
4. WX → Z (using IR3 on 3 and 2)

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Normalization
 A large database defined as a single relation may result in
data duplication.
 This repetition of data may result in: Making relations
very large.
 It isn't easy to maintain and update data as it would
involve searching many records in relation.
 Wastage and poor utilization of disk space and resources.
 The likelihood of errors and inconsistencies increases.
So to handle these problems, we should analyze and decompose the
relations with redundant data into smaller, simpler, and well-
structured relations that are satisfy desirable properties.
Normalization is a process of decomposing the relations into
relations with fewer attributes.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS

What is 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 undesirable characteristics like
Insertion, Update, and Deletion Anomalies.
 Normalization divides the larger table into smaller and links
them using relationships.
 The normal form is used to reduce redundancy from the database
table.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 6.97%
Course Code :E2UC302B Course Name: DBMS

Why do we need Normalization?

 The main reason for normalizing the relations is removing these
anomalies.
 Failure to eliminate anomalies leads to data redundancy and can
cause data integrity and other problems as the database grows.
Normalization consists of a series of guidelines that helps to
guide you in creating a good database structure.
Duration 18:10

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS

 Data modification anomalies can be categorized into three

types:
 Insertion Anomaly: Insertion Anomaly refers to when one
cannot insert a new tuple into a relationship due to lack of
data.
 Deletion Anomaly: The delete anomaly refers to the situation
where the deletion of data results in the unintended loss of
some other important data.
 Updatation Anomaly: The update anomaly is when an update
of a single data value requires multiple rows of data to be
updated.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code :E2UC302B Course Name: DBMS
Types of Normal Forms:

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Types of Normal Form

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

 Advantages of Normalization
 Normalization helps to minimize data redundancy.
 Greater overall database organization.
 Data consistency within the database.
 Much more flexible database design.
 Enforces the concept of relational integrity.
 Disadvantages of Normalization
 You cannot start building the database before knowing what the user needs.
 The performance degrades when normalizing the relations to higher normal
forms, i.e., 4NF, 5NF.
 It is very time-consuming and difficult to normalize relations of a higher
degree.
 Careless decomposition may lead to a bad database design, leading to
serious problems.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

First Normal Form

 A relation will be 1NF if it contains an atomic value.
 It states that an attribute of a table cannot hold multiple values. It must hold only
single-valued attribute.
 First normal form disallows the multi-valued attribute, composite attribute, and
their combinations.
•Example 1 – Relation STUDENT in table 1 is not in 1NF because of multi-valued
attribute STUD_PHONE. Its decomposition into 1NF has been shown in table 2.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

First Normal Form

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS
Second Normal Form
 In the 2NF, relational must be in 1NF.
 In the second normal form, all non-key attributes are fully functional dependent on the
primary key
 Example: Let's assume, a school can store the data of teachers and the subjects they
teach. In a school, a teacher can teach more than one subject.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS
Third Normal Form
 A relation will be in 3NF if it is in 2NF and not contain any transitive
partial dependency.
 3NF is used to reduce the data duplication. It is also used to achieve the
data integrity.
 If there is no transitive dependency for non-prime attributes, then the
relation must be in third normal form.
 A relation is in third normal form if it holds atleast one of the following
conditions for every non-trivial function dependency X → Y.
 X is a super key.
 Y is a prime attribute, i.e., each element of Y is part of some candidate
key.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Super key in the table above:

1.{EMP_ID}, {EMP_ID, EMP_NAME}, {EMP_ID, EMP_NAME, EMP_ZIP}....so on
Candidate key: {EMP_ID}
Non-prime attributes: In the given table, all attributes except EMP_ID are non-prime.
 Here, EMP_STATE & EMP_CITY dependent on EMP_ZIP and EMP_ZIP dependent on
EMP_ID. The non-prime attributes (EMP_STATE, EMP_CITY) transitively dependent on super
key(EMP_ID). It violates the rule of third normal form.
 That's why we need to move the EMP_CITY and EMP_STATE to the new <EMPLOYEE_ZIP>
table, with EMP_ZIP as a Primary key.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS
BCNF
 Boyce Codd normal form (BCNF)
 BCNF is the advance version of 3NF. It is stricter than 3NF.
 A table is in BCNF if every functional dependency X → Y, X is the
super key of the table.
 For BCNF, the table should be in 3NF, and for every FD, LHS is super
key.
 Example: Let's assume there is a company where employees work in
more than one department.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Candidate key: {EMP-ID, EMP-

 DEPT}
The table is not in BCNF because neither EMP_DEPT nor EMP_ID alone are keys.
 To convert the given table into BCNF, we decompose it into three tables:

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Functional dependencies:
1.EMP_ID → EMP_COUNTRY
2.EMP_DEPT → {DEPT_TYPE, EMP_DEPT_NO}
Candidate keys:
For the first table: EMP_ID
For the second table: EMP_DEPT
For the third table: {EMP_ID, EMP_DEPT}
Now, this is in BCNF because left side part of both the functional dependencies
is a key.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

 Fourth normal form (4NF)

 A relation will be in 4NF if it is in Boyce Codd normal form and has
no multi-valued dependency.
 For a dependency A → B, if for a single value of A, multiple values of
B exists, then the relation will be a multi-valued dependency.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS
The given STUDENT table is in 3NF, but the COURSE and HOBBY are
two independent entity. Hence, there is no relationship between COURSE
and HOBBY.
In the STUDENT relation, a student with STU_ID, 21 contains two
courses, Computer and Math and two hobbies, Dancing and Singing. So
there is a Multi-valued dependency on STU_ID, which leads to unnecessary
repetition of data.
So to make the above table into 4NF, we can decompose it into two tables:

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Course Code : E2UC302B Course Name: DBMS

Fifth Normal Form

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

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

Fifth Normal Form

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

 Suppose 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:

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

Relational Decomposition
 When a relation in the relational model is not in appropriate normal form then the
decomposition of a relation is required.
 In a database, it breaks the table into multiple tables.
 If the relation has no proper decomposition, then it may lead to problems like loss
of information.
 Decomposition is used to eliminate some of the problems of bad design like
anomalies, inconsistencies, and redundancy.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS
 Lossless Decomposition
 If the information is not lost from the relation that is decomposed, then the
decomposition will be lossless.
 The lossless decomposition guarantees that the join of relations will result in the
same relation as it was decomposed.
 The relation is said to be lossless decomposition if natural joins of all the
decomposition give the original relation.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS
 Dependency Preserving
 It is an important constraint of the database.
 In the dependency preservation, at least one decomposed table must
satisfy every dependency.
 If a relation R is decomposed into relation R1 and R2, then the
dependencies of R either must be a part of R1 or R2 or must be
derivable from the combination of functional dependencies of R1
and R2.
 For example, suppose there is a relation R (A, B, C, D) with
functional dependency set (A->BC). The relational R is decomposed
into R1(ABC) and R2(AD) which is dependency preserving because
FD A->BC is a part of relation R1(ABC).

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS
 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.

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

 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. The representation of these dependencies is shown
below:
 BIKE_MODEL → → MANUF_YEAR
 BIKE_MODEL → → COLOR
 This can be read as "BIKE_MODEL multidetermined MANUF_YEAR"
and "BIKE_MODEL multidetermined COLOR".

Program Name: B.TECH Program Code: E2UC302B

 School of Computing Science and Engineering
Loaded: 9.17%
Course Code : E2UC302B Course Name: DBMS

 Join Dependency
 Join decomposition is a further generalization of Multivalued
dependencies.
 If the join of R1 and R2 over C is equal to relation R, then we can say
that a join dependency (JD) exists.
 Where R1 and R2 are the decompositions R1(A, B, C) and R2(C, D)
of a given relations R (A, B, C, D).

 A JD ⋈ {R1, R2,..., Rn} is said to hold over a relation R if R1, R2,.....,

 Alternatively, R1 and R2 are a lossless decomposition of R.

Rn is a lossless-join decomposition.
 The *(A, B, C, D), (C, D) will be a JD of R if the join of join's
attribute is equal to the relation R.
 Here, *(R1, R2, R3) is used to indicate that relation R1, R2, R3 and
so on are a JD of R.

Program Name: B.TECH Program Code: E2UC302B