Unit 1

ADVANCES IN DATA BASE

MANAGEMENT SYSTEM
Schema Refinement
and Normal Forms
Dr. Renukadevi M N
Dept. of CS&E
School of Engineering
Dayananda Sagar University
ADBMS
 Advanced DBMS goes beyond basic
relational DBMS.
 It handles complex, large-scale, and
distributed data efficiently.
 Provide support for modern applications
like multimedia, GIS, healthcare, and big data
analytics.
 Main goal: improve performance, flexibility,
and scalability
Key Features
 Complex Data Handling: Works with not just
text/numbers, but also images, videos, and geospatial
data.
 Scalability: Supports large datasets and multiple users
simultaneously.
 Object-oriented models: Allow representation of real-
world entities as objects.
 Advanced Query Optimization: Ensures faster retrieval
even in massive datasets.
 Overall, these features make Advanced DBMS more
powerful than traditional DBMS.
Types of Advanced Databases
 Distributed Databases: Data stored across multiple physical
locations; improves reliability and availability.
 Parallel Databases: Use parallel processing to handle big queries
faster.
 Object-Oriented Databases: Store data as objects, aligning with
programming languages like Java/C++.
 Multimedia Databases: Handle images, audio, video (e.g.,
YouTube, Spotify).
 Temporal Databases: Manage historical and time-based data (e.g.,
stock market records).
 Spatial Databases: Store and query geographic or spatial data
(e.g., Google Maps, GIS).
Applications
 Banking & Financial Systems: Secure, large-scale transaction
management.
 Healthcare & Bioinformatics: Stores patient records, genome
data, medical imaging.
 GIS & Navigation: Used in Google Maps, smart city applications.
 Social Media & Recommendations: Analyzes user behavior to
suggest content/products.
 Advanced DBMS is industry-wide and supports real-time decision-
making.
Fundamentals
Attribute
An attribute is a column in a relation (table).
It represents a property or field of the entity being

modelled.
Each attribute has:

 Name (e.g., Student_ID, Name, Age)

 Domain (the set of allowed values, e.g., integers,

strings, dates).
👉 Example:

In a Student table, the attributes could be:

Student_ID, Name, Age, Department.
Tuple
A tuple is a row in a relation (table).

It represents a single record or instance of

the entity.
Each tuple consists of values corresponding to

the table’s attributes.

For the Student table:
Here:
•Student_ID, Name, Age, Department → Attributes (columns)
•(101, Ananya, 20, CSE) → Tuple (row)

Student_ID Name Age Department

101 Ananya 20 CSE
102 Rahul 21 ECE
 Review: Database Design
 Requirements Analysis
 user needs; what must database do?
 Conceptual Design
 high level description (often done with ER model)
 Logical Design
 translate ER into DBMS data model
 Schema Refinement
 consistency, normalization
 Physical Design - indexes, disk layout
 Security Design - who accesses what
Schema Refinement

 Process of improving a database schema for

efficiency and consistency.
 Removes data redundancy and anomalies
(insertion, update, deletion).
 Uses formal techniques like Functional
Dependencies (FDs).
 Goal: Create a schema that is simple,
consistent, and reliable.
 The Evils of Redundancy
 Redundancy is at the root of several problems
associated with relational schemas:
 redundant storage, insert/delete/update anomalies
 Integrity constraints, in particular functional
dependencies, can be used to identify schemas with
such problems and to suggest refinements.
 Main refinement technique: decomposition
 replacing ABCD with, say, AB and BCD, or ACD and ABD.
 Decomposition should be used judiciously:
 Is there reason to decompose a relation?
 What problems (if any) does the decomposition cause?
 Functional Dependencies (FDs)
 A functional dependency X  Y holds over relation
schema R if, for every allowable instance r of R:
t1  r, t2  r, X (t1) = X (t2)
implies Y (t1) = Y (t2)
(where t1 and t2 are tuples;X and Y are sets of
attributes)
 In other words: X  Y means
Given any two tuples in r, if the X values are the
same, then the Y values must also be the same.
(but not vice versa)
 Can read “” as “determines”
Functional Dependencies (Contd.)
 An FD is a statement about all allowable
relations.
 Must be identified based on semantics of application.
 Given some instance r1 of R, we can check if r1
violates some FD f, but we cannot determine if f holds
over R.
 Question: How related to keys?
 if “K  all attributes of R” then K is a superkey for R
(does not require K to be minimal.)

 FDs are a generalization of keys.

 Example: Constraints on Entity
Set
 Consider relation obtained from Hourly_Emps:
Hourly_Emps (ssn, name, lot, rating, wage_per_hr, hrs_per_wk)

 We sometimes denote a relation schema by listing the

attributes: e.g., SNLRWH
 Sometimes, we refer to the set of all attributes of a relation by
using the relation name. e.g., “Hourly_Emps” for SNLRWH

What are some FDs on Hourly_Emps?

ssn is the key: S  SNLRWH
rating determines wage_per_hr: R  W
lot determines lot: L  L (“trivial”
dependnency)
 Problems Due to R  W
S N L R W H
123-22-3666 Attishoo 48 8 10 40
231-31-5368 Smiley 22 8 10 30
131-24-3650 Smethurst 35 5 7 30
434-26-3751 Guldu 35 5 7 32
612-67-4134 Madayan 35 8 10 40 Hourly_Emps

 Update anomaly: Can we modify W in only the 1st tuple of

SNLRWH?
 Insertion anomaly: What if we want to insert an employee
and don’t know the hourly wage for his or her rating? (or we
get it wrong?)
 Deletion anomaly: If we delete all employees with rating 5,
we lose the information about the wage for rating 5!
 Refining an ER Diagram by FD: Attributes Can Easily Be
Associated with the “Wrong” Entitity Set in ER Design.

 1st diagram becomes:

Workers(S,N,L,D,Si) Before:
Departments(D,M,B) since
 Lots associated with workers.
name dname
ssn lot did budget
 Suppose all workers in a
dept are assigned the same lot:
Employees Works_In Departments
DL
 Redundancy; fixed by
decomposition:
Workers2(S,N,D,Si) After: budget
Dept_Lots(D,L) since
name dname
Departments(D,M,B)
ssn did lot
 Can fine-tune this:
Workers2(S,N,D,Si)
Employees Works_In Departments
Departments(D,M,B,L)
What’s is Anomaly in DBMS?
Problems Due to Anomaly
In DBMS (Database Management Systems), an anomaly refers
to an inconsistency, redundancy, or problem that arises when
data is not stored properly.
•Insertion Anomaly
Problem when you cannot insert data into a table without
having other, unrelated data present.
Example:
Suppose you have a single table storing : Student(ID, Name, Course,
Instructor)
If a new course is introduced but no student has enrolled yet, you
cannot add the course details because the table requires a
student entry.
• Update Anomaly
Problem when you have to update the same piece of data in multiple
places, which may lead to inconsistencies.
Example:
In the same Student table, if the instructor of a course changes,
you must update it in all rows where that course appears. If you
miss one row, inconsistent data occurs
 Problems Due to Anomaly
• Deletion Anomaly
Problem when deleting one piece of data also removes useful,
unrelated data.
Example:
If the last student enrolled in a course leaves (deleted from
the table), then the course information itself is lost, even
though the course still exists

•Insertion Anomaly → Can’t add data without other data.

•Update Anomaly → Need to update in multiple places → risk of
inconsistency.
•Deletion Anomaly → Deleting data unintentionally removes other
important data.
Detecting Redundancy
StudentID StudentName CourseID CourseName Instructor
101 Ravi C1 DBMS Prof. Sharma
102 Priya C2 Networks Prof. Gupta
103 Anil C1 DBMS Prof. Sharma
104 Meena C3 AI Prof. Verma
105 Ravi C2 Networks Prof. Gupta

Where redundancy occurs?

Course details (CourseName, Instructor) are repeated for every student

taking that course.
Student details (like Ravi’s name) are repeated if he takes multiple courses.
 Anomalies in the table
StudentID StudentName CourseID CourseName Instructor
101 Ravi C1 DBMS Prof. Sharma
102
. Priya C2 Networks Prof. Gupta
103 Anil C1 DBMS Prof. Sharma
104 Meena C3 AI Prof. Verma
105 Ravi C2 Networks Prof. Gupta
Decomposing a relation
To detect redundancy in this table:
Step1: Look for repeated values (e.g., "DBMS – Prof. Sharma" appears in
multiple rows).
This signals data duplication → risk of anomalies.
Decomposing a Relation
 Reasoning About FDs
 Given some FDs, we can usually infer additional FDs:
title  studio, star implies title  studio and title  star
title  studio and title  star implies title  studio, star
title  studio, studio  star implies title  star

But, title, star  studio does NOT necessarily imply that

title  studio or that star  studio
 An FD f is implied by a set of FDs F if f holds whenever all
FDs in F hold.
 F+ = closure of F is the set of all FDs that are implied by F.
(includes “trivial dependencies”)
 Rules of Inference
 Armstrong’s Axioms (X, Y, Z are sets of attributes):
 Reflexivity: If X  Y, then X  Y
 Augmentation: If X  Y, then XZ  YZ for any Z
 Transitivity: If X  Y and Y  Z, then X  Z

 These are sound and complete inference rules for FDs!

 i.e., using AA you can compute all the FDs in F+ and only

these FDs.
 Some additional rules (that follow from AA):
 Union: If X  Y and X  Z, then X  YZ
 Decomposition: If X  YZ, then X  Y and X  Z
 Example
 Contracts(cid,sid,jid,did,pid,qty,value), and:
 C is the key: C  CSJDPQV
 P(roject) purchases a given part using a single contract: JP  C
 D(ept) purchases at most 1 part from a supplier: SD  P

 Problem: Prove that SDJ is a key for Contracts

 JP  C, C  CSJDPQV imply JP  CSJDPQV
(by transitivity) (shows that JP is a key)
 SD  P implies SDJ  JP (by augmentation)
 SDJ  JP, JP  CSJDPQV imply SDJ  CSJDPQV (by
transitivity) thus SDJ is a key.
 Attribute Closure
 Typically, we just want to check if a given FD X  Y is in
the closure of a set of FDs F. An efficient check:
 Compute attribute closure of X (denoted X+) w.r.t. F.

X+ = Set of all attributes A such that X  A is in F+

 X+ := X
 Repeat until no change: if there is an FD U  V in F such

that U is in X+, then add V to X+

 Check if Y is in X+
 The approach can also be used to find the keys of a
relation.
 If all attributes of R are in the closure of X, then X is a
superkey for R.
 Normal Forms
 How to do schema refinement?
 We use normal forms as guidance.

 If a relation is in a normal form (BCNF, 3NF etc.):

 we know that certain problems are avoided/minimized.
 helps decide whether decomposing a relation is useful.
 Normal Forms vs. Functional Dependencies

 Role of FDs in detecting redundancy:

 Consider a relation R with 3 attributes, ABC.
 No (non-trivial) FDs hold: There is no redundancy here.
 Given A  B: If A is not a key, then several tuples could
have the same A value, and if so, they’ll all have the same
B value!
 The normal forms based on FDs are:
 First Normal Form (1NF), 2NF, 3NF, and Boyce-Codd
Normal Form (BCNF)
 These forms have increasingly restrictive requirements:
 1NF  2NF (of historical interest)  3NF  BCNF
1st Normal Form
 1st Normal Form – all attributes are atomic
 Given a relation R in 1NF, for a tuple t of R, t’s every
attribute can contain only atomic values,
 i. e., attribute values are not lists or sets.

 We can imagine there exists FDs in the

following manner:
 Attribute A  some unique value in A’s domain.
Normal Form

 Example
 A company obtains parts from a number of
suppliers.
 Each supplier is located in one city.
 A city can have more than one supplier located
there
 and each city has a status code associated with it.
 Each supplier may provide many parts.
First normal form
All values of the columns are atomic
Anomalies with 1NF
 INSERT.
 The fact that a certain supplier (s5) is located in a particular city
(Athens) cannot be added until they supplied a part.
 DELETE.
 If a row is deleted, then not only is the information about quantity
and part lost but also information about the supplier.
 UPDATE.
 If supplier s1 moved from London to New York, then six rows
would have to be updated with this new information.
2NF

 A relational table is in second normal form

2NF if it is in 1NF and every non-key column
is fully dependent upon the primary key.
 Is FIRST in 2NF?
 S#->city,status
 City->status
 (s#,p#)->qty
Decompose 1NF into 2NF
 Identify any determinants other than the composite key,
and the columns they determine.
 Create and name a new table for each determinant and
the unique columns it determines.
 Move the determined columns from the original table to
the new table. The determinate becomes the primary
key of the new table.
 Delete the columns you just moved from the original
table except for the determinate which will serve as a
foreign key.
 The original table may be renamed to maintain
semantic meaning.
2NF
Problems of 2NF

 INSERT.
 The fact that a particular city has a certain status
(Rome has a status of 50) cannot be inserted until
there is a supplier in the city.
 DELETE.
 Deleting any row in SUPPLIER destroys the
status information about the city as well as the
association between supplier and city.
3NF
 A relational table is in third normal form (3NF) if it is
already in 2NF and every non-key column is non
transitively dependent upon its primary key. In other
words, all nonkey attributes are functionally dependent
only upon the primary key.
 SUPPLIER is in 2NF but not in 3NF because it contains
a transitive dependency.
 A transitive dependency occurs when a non-key column that is a
determinant of the primary key is the determinate of other
columns.
Decompose to 3NF
 Identify any determinants, other than the primary key,
and the columns they determine.
 Create and name a new table for each determinant
and the unique columns it determines.
 Move the determined columns from the original table
to the new table. The determinate becomes the
primary key of the new table.
 Delete the columns you just moved from the original
table except for the determinate which will serve as a
foreign key.
 The original table may be renamed to maintain
semantic meaning.
3NF results
Advantages of 3NF
 It eliminates redundant data
 INSERT.
 Facts about the status of a city, Rome has a status of 50, can be
added even though there is not supplier in that city.
 Likewise, facts about new suppliers can be added even though
they have not yet supplied parts.
 DELETE.
 Information about parts supplied can be deleted without destroying
information about a supplier or a city.
 UPDATE.
 Changing the location of a supplier or the status of a city requires
modifying only one row.
Why 3NF?

 The motivation for 3NF is rather technical.

 Lossless-join, dependency preserving decomposition
does not always exist for BCNF.

 We can ensure every relation schema can be

decomposed into a collection of 3NF relations
 using only lossless-join, dependency preserving
decompositions.
 Decomposition into 3NF
 The algorithm for lossless join decomposition into BCNF can
be used to obtain a lossless join decomposition into 3NF
 but does not ensure dependency preservation.
 To ensure dependency preservation, one idea:
 If X  Y is not preserved, add relation XY.
Problem is that XY may violate 3NF!
e.g., consider the addition of JPC to `preserve’ JP  C. What if we also
have J  C ?
 Refinement: Instead of the given set of FDs F, use a minimal
cover for F.
BCNF
 Boyce-Codd normal form (BCNF) is a more
rigorous version of the 3NF deal with relational
tables that had
 (a) multiple candidate keys,
 (b) composite candidate keys, and
 (c) candidate keys that overlapped
 BCNF is based on the concept of determinants.
 A determinant column is one on which some of
the columns are fully functionally dependent.
 A relational table is in BCNF if and only if every
determinant is a candidate key.
 Boyce-Codd Normal Form (BCNF)

 Relation R with FDs F is in BCNF if for all X  A in F+

 A  X (called a trivial FD), or
 X is a superkey for R.
 Intuitively, R is in BCNF if the only non-trivial FDs over
R are key constraints.
 Boyce-Codd Normal Form (Contd.)

 If R in BCNF, then every field of every tuple records

information that cannot be inferred using FDs alone.
 Say we know FD X  A holds for this example relation:

X Y A
x y1 a
x y2 ?
• Can you guess the value of
the missing attribute?
•Yes, so relation is not in BCNF
 Decomposition of a Relation Schema

 If a relation is not in a desired normal form, it can

be decomposed into multiple relations that each
are in that normal form.

 Suppose that relation R contains attributes A1 ...

An. A decomposition of R consists of replacing R
by two or more relations such that:
 Each new relation schema contains a subset of the
attributes of R,
 and every attribute of R appears as an attribute of at
least one of the new relations.
 Example (same as before)
S N L R W H
123-22-3666 Attishoo 48 8 10 40
231-31-5368 Smiley 22 8 10 30
131-24-3650 Smethurst 35 5 7 30 Hourly_Emps
434-26-3751 Guldu 35 5 7 32
612-67-4134 Madayan 35 8 10 40
 SNLRWH has FDs S  SNLRWH and R  W
 Q: Is this relation in BCNF?

No, The second FD causes a violation;

W values repeatedly associated with R values.
 Decomposing a Relation
 Easiest fix is to create a relation RW to store these associations, and
to remove W from the main schema:

S N L R H
123-22-3666 Attishoo 48 8 40 R W
231-31-5368 Smiley 22 8 30 8 10
131-24-3650 Smethurst 35 5 30 5 7
434-26-3751 Guldu 35 5 32
612-67-4134 Madayan 35 8 40
Wages
Hourly_Emps2
•Q: Are both of these relations are now in BCNF?
•Decompositions should be used only when needed

–Q: potential problems of decomposition?

 Problems with Decompositions
 There are three potential problems to consider:
1) May be impossible to reconstruct the original relation!
(Lossiness)
 Fortunately, not in the SNLRWH example.
2) Dependency checking may require JOINs.
 Fortunately, not in the SNLRWH example.
3) Some queries become more expensive.
 e.g., How much does person earn?

Tradeoff: Must consider these issues vs. redundancy.

 Lossless Decomposition (example)
S N L R H
R W


123-22-3666 Attishoo 48 8 40
231-31-5368 Smiley 22 8 30 8 10
131-24-3650 Smethurst 35 5 30
434-26-3751 Guldu 35 5 32
5 7
612-67-4134 Madayan 35 8 40

S N L R W H
123-22-3666 Attishoo 48 8 10 40

=
231-31-5368 Smiley 22 8 10 30
131-24-3650 Smethurst 35 5 7 30
434-26-3751 Guldu 35 5 7 32
612-67-4134 Madayan 35 8 10 40
Lossy Decomposition (example)

A B B C
A B C
1 2 2 3
1 2 3 4 5 5 6
4 5 6 7 2 2 8
7 2 8
A  B; C  B
A B C
1 2 3
A B B C 4 5 6
1
4
2
5  2
5
2
3
6
8
= 7
1
7
2
2
2
8
8
3
7 2
 Lossless Join Decompositions

 Decomposition of R into X and Y is lossless-join w.r.t.

a set of FDs F if, for every instance r that satisfies F:
 X(r)   Y (r) = r
 It is always true that r   X (r)   Y (r)
 In general, the other direction does not hold! If it does,
the decomposition is lossless-join.
 Definition extended to decomposition into 3 or more
relations in a straightforward way.
 It is essential that all decompositions used to deal
with redundancy be lossless! (Avoids Problem #1)
 Simple Test on Lossless Decomposition

 The decomposition of R into X and Y is

lossless w. r. t. F iff the closure of F contains:
X  Y  X, or
XYY

 In the example: decomposing ABC into AB and BC

is lossy, because intersection (i.e., “B”) is not a key
of either resulting relation.

 Useful result: If W  Z holds over R and W  Z is empty,

then decomposition of R into R-Z and WZ is loss-less.
 Lossless Decomposition (example)

A B C A C B C
1 2 3 1 3 2 3
4 5 6 4 6 5 6
7 2 8 7 8
2 8
A  B; C  B

A C B C A B C
1 3
4 6
7 8
 2 3
5 6
2 8
= 1 2 3
4 5 6
7 2 8
But, now we can’t check A  B without doing a join!
 illustrate Lossy
Decomposition in DBMS
Relation R(A, B, C)

A B C
1 X 10
2 Y 20

Decomposition:
Decomposition: We decompose R into two relations:
We decompose R into two relations: R2(B, C)
R1(A, B)

A B B C
1 X X 10
2 Y Y 20
 When we join R1 and R2 on B:
A B C
1 X 10
2 Y 20

This is a Lossless Join (original table is recovered).

Now, if we change the decomposition slightly:

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

A B A C
1 X 1 10
2 Y 2 20
 When we join R1 and R2 on A, we get:

A B C
1 X 10 Still lossless.

2 Y 20

But consider this case (lossy):

Original R(A, B, C)

A B C
1 X 10
1 Y 20
Decompose into:
R1(A, B)
A B
1 X
1 Y
A decomposition is lossy if, after
R2(B, C) joining, you get extra tuples not
present in the original relation.
B C
X 10
Y 20

Join on B gives:
A B C
1 X 10
1 Y 20
1 X 20
1 Y 10
Extra (spurious) tuples appear, so this is a
Lossy Decomposition.
Decomposition into BCNF
R(A, B, C)

A B C
1 X 100
1 Y 100
2 X 200
2 Y 200
Non-BCNF Example
R(A, B, C)
Functional Dependencies:
1.A → B
2.B → C
Decomposition of A,B,C

R(A,B)

What if we do the decomposition by using the dependency JS

first?
Advanced NFs
 After 3NF, all normalization problems involve only
tables which have three or more columns and all
the columns are keys.
 Many practitioners argue that placing entities in
3NF is generally sufficient because it is rare that
entities that are in 3NF are not also in 4NF and
5NF.
 They further argue that the benefits gained from
transforming entities into 4NF and 5NF are so
slight that it is not worth the effort.
4NF
Fourth Normal Form (4NF)
A relation is in 4NF if:
It is already in Boyce–Codd Normal Form (BCNF)
And every Multi-Valued Dependency (MVD) in the relation is also
a Functional Dependency (FD)

Multi-Valued Dependency (MVD)

Denoted as A —>> B (read as “A multi-determines B”)
Occurs when:
For a given value of attribute A, there exists a set of values of B
That set of B values is independent of other attributes (like C) in
the same relation
 Example 1: Multi-Valued Dependency
Relation: STUDENT(SID, SKILL, HOBBY)
•In the above table, every
combination of SKILL and HOBBY
SID SKILL HOBBY for the same student appears.
S1 C++ Reading
•For S1, we have 4 tuples instead of
S1 Java Reading the logical 2 SKILLs + 2 HOBBYs.
S1 C++ Painting
•This leads to data redundancy and
S1 Java Painting update anomalies.
Example 1: Multi-Valued Dependency
Relation: STUDENT(SID, SKILL, HOBBY)

•A student can have multiple SKILLs and

multiple HOBBYies.
•But SKILL and HOBBY are independent of each
other.
👉 Hence,
•SID —>> SKILL and
•SID —>> HOBBY
are Multi-Valued Dependencies (MVDs).
 4NF Decomposition

To remove redundancy, decompose into two separate relations:

R1(SID, SKILL)

SID SKILL
S1 C++
S1 Java

R2(SID, HOBBY)

SID HOBBY
S1 Reading
S1 Painting
Both R1 and R2 are in 4NF.
Each now represents one independent fact about the key SID.
Examples
 employees can be assigned to multiple projects and
employees can have multiple job skills.
 The primary key should be (emp#,prj#,skill#)
 The relationship between emp# and prj# is a multivalued
dependency because for each pair of emp#/skill values in
the table, the associated set of prj# values is determined
only by emp# and is independent of skill.
 The relationship between emp# and skill is also a
multivalued dependency, since the set of Skill values for an
emp#/prj# pair is always dependent upon emp# only.
Relation: EMP_PROJ_SKILL(emp#, prj#, skill#)
emp# prj# skill#
E1 P1 Java
E1 P1 SQL
E1 P2 Java
E1 P2 SQL
E2 P3 Python
E2 P3 HTML
E2 P4 Python
E2 P4 HTML
•Each employee (emp#) can:
✅ Work on multiple projects (prj#)
✅ Have multiple skills (skill#)
•But:
•The projects assigned to an employee are independent of their skills
•The skills of an employee are independent of their projects
Multi-Valued Dependencies
[Link]# —>> prj#
1. For each employee, the set of projects
depends only on emp#
2. Independent of which skill they have
[Link]# —>> skill#
1. For each employee, the set of skills
depends only on emp#
2. Independent of which project they are
on

Why Redundancy Occurs

•Because each combination of an employee’s project and skill appears
as a separate row,
there is repetition (e.g., E1–P1–Java, E1–P1–SQL, etc.).
•This causes:
• Update anomalies (adding new skills or projects requires
repeating data)
• Insertion anomalies (can’t insert a skill without a project)
• Deletion anomalies (deleting a project may remove skill info)
 4NF Decomposition
To eliminate redundancy due to MVDs, decompose the relation into two
independent ones:

Relation for Employee–Project Relation for Employee–Skill

EMP_PROJ(emp#, prj#) EMP_SKILL(emp#, skill#)

emp# prj# emp# skill#

E1 P1 E1 Java
E1 P2 E1 SQL
E2 P3 E2 Python
E2 P4 E2 HTML

Now both relations are in Fourth Normal Form (4NF)

•Each table captures one independent multi-valued fact about emp#.
•Redundancy is eliminated.
•If needed, we can reconstruct the original table by joining on emp#.
5NF
•A relation is in 5NF if:
•It is in 4NF, and
•It cannot be decomposed further into smaller relations
without losing information, i.e.,
it can be reconstructed by natural joins of its projections.
•5NF deals with Join Dependencies (JD)

 When 5NF is Needed

5NF occurs when information can be reconstructed only by joining
multiple tables,
but no smaller subset of joins can do that.
It handles cases where facts are stored as combinations of multiple
independent relationships.
Example: Supplier–Part–Project
Relation: SUPP_PART_PROJ (Supplier, Part, Project)

Supplier Part Project

S1 P1 J1
S1 P2 J1
S1 P1 J2
S2 P1 J1
•A Supplier can supply many Parts.
•A Supplier can work on many Projects.
•Each Part can be used in many Projects.
•But not all combinations are valid — only certain triplets exist.

Join Dependency
•The relationship here is a Join Dependency (JD):
{Supplier, Part, Project} → {Supplier, Part},
{Supplier, Project}, {Part, Project}
•The data can be represented correctly only when all three are
joined together.
 Decomposition into 5NF

Step 1: Decompose into smaller relations

R1(Supplier, Part)
R3(Part, Project)
Supplier Part
S1 P1 Part Project
S1 P2 P1 J1
S2 P1 P1 J2
R2(Supplier, Project) P2 J1

Supplier Project
S1 J1
S1 J2
S2 J1
Step 2: Reconstructing the Original Relation
•When you join R1, R2, and R3,
you can reconstruct the original SUPP_PART_PROJ table
without loss of data.
•No smaller combination (like joining just R1 and R2) can
reproduce the original table completely.
✅ Hence, the relation is in 5NF.
 Summary of Schema Refinement
 BCNF: each field contains information that cannot
be inferred using only FDs.
 ensuring BCNF is a good heuristic.
 Not in BCNF? Try decomposing into BCNF
relations.
 Must consider whether all FDs are preserved!
 Lossless-join, dependency preserving
decomposition into BCNF impossible? Consider
3NF.
 Same if BCNF decomp is unsuitable for typical queries
 Decompositions should be carried out and/or re-examined
while keeping performance requirements in mind.
Physical Database
Design and Tuning
 Introduction
• We will be talking at length about “database design”
– Conceptual Schema: info to capture, tables, columns,
views, etc.
– Physical Schema: indexes, clustering, etc.
• Physical design linked tightly to query optimization
– So we’ll study this “bottom up”
– But note: DB design is usually “top-down”
• conceptual then physical. Then iterate.
• We must begin by understanding the workload:
– The most important queries and how often they arise.
– The most important updates and how often they arise.
– The desired performance for these queries and updates.
 Understanding the Workload
• For each query in the workload:
– Which relations does it access?
– Which attributes are retrieved?
– Which attributes are involved in selection/join
conditions? How selective are these conditions likely
to be?
• For each update in the workload:
– Which attributes are involved in selection/join
conditions? How selective are these conditions likely
to be?
– The type of update (INSERT/DELETE/UPDATE), and the
attributes that are affected.
 Creating an ISUD Chart
An ISUD Chart is a data analysis and documentation tool used in Database
Design to show how different entities in a system are affected by the four
basic operations:
I – Insert
S – Select
U – Update
D – Delete
It helps database designers understand data flow, operations, and
dependencies between entities and processes during the Database Life
Cycle (DBLC).

Insert, Select, Update, Delete Frequencies

 Student Database
Process / Select Update Delete
Insert (I)
Entity (S) (U) (D)
Register
Student
Student
Assign
Course Entities:
Course •Student
•Course
Enroll •Enrolment
Enrollmen Student, Enrollmen
Student in Processes:
t Course t [Link] Student
Course [Link] Course
[Link] Student in Course
Student, [Link] Report
Generate Course, [Link] Enrolment
Report Enrollmen
t
Delete
Enrollmen
Enrollmen Enrolment
t
t
•The Register Student process inserts a new record into
the Student entity.
•The Enroll Student in Course process reads Student
and Course data and inserts/updates Enrollment records.
•The Generate Report process selects data from multiple
entities.
•The Delete Enrollment process deletes records from
the Enrollment entity
 Index Selection and Optimization in
DBMS
What is an Index?
•An index is a data structure that improves the speed of
data retrieval operations on a database table.
•It acts like a lookup table to locate records faster
without scanning the entire table.
•Common structures: B+ Trees, Hash Indexes, etc.
Which Relations Should Have Indexes?
Create indexes on relations (tables) that are:
•Frequently accessed in search or join operations.
•Large in size, where full table scan would be slow.
•Used in WHERE, ORDER BY, GROUP BY, or JOIN clauses.
 Which Fields Should Be the Search
Key?
Attributes that are:
Frequently used in filtering conditions (WHERE clause).
Used in sorting (ORDER BY).
Foreign keys and primary keys.
Join attributes connecting two or more tables.
Examples:
student_id in Enrollment table
product_id in Sales table
customer_id in Orders table
Index Types

Clustered → Data stored in index order. Physically

orders the data rows based on the index key
Non-clustered → Maintains a separate structure with
pointers to data rows
Static Fixed size and structure
 Decisions to Make
• What indexes should we create?
– Which relations should have indexes? What field(s)
should be the search key? Should we build several
indexes?
• For each index, what kind of an index should it
be?
– Clustered? Dynamic/static?
• Should we make changes to the conceptual
schema?
– More on this later…
• Horizontal partitioning, replication, views ...
Database Tuning
and Optimization
Overview
Clustering, Indexing, and Performance
Enhancement
 Clustering & Indexing
Clustering: Physically stores related records
together on disk.
Improves performance for queries retrieving
related tuples.
Example: Storing Students and Enrollments in
the same block for quick access.
Indexing builds auxiliary structures for faster
lookups.
Common index types: B+-Tree, Hash, Bitmap.
 Creating Indexes
CREATE INDEX idx_student_name ON
Students(student_name);
Speeds up: SELECT * FROM Students WHERE
student_name = 'Rahul';
CREATE INDEX idx_order_customer_date ON
Orders(customer_id, order_date);
Speeds up: SELECT * FROM Orders WHERE
customer_id = 1023 AND order_date >=
'2025-01-01';
Clustered vs. Non-Clustered
Index

Clustered Index: Data stored in index

order; only one per table.
Non-Clustered Index: Separate structure;
multiple indexes possible.
Clustered – ideal for range queries, sorting.
Non-Clustered – ideal for random lookups.
Example: Clustered → ORDER BY student_id;
Non-Clustered → lookup by email_id.
 Clustered vs Non-Clustered
Index
CREATE CLUSTERED INDEX idx_emp_id ON
Employee(emp_id);
Ideal for range queries: SELECT * FROM
Employee WHERE emp_id BETWEEN 1000
AND 2000;
CREATE NONCLUSTERED INDEX idx_emp_email
ON Employee(email);
Ideal for lookups: SELECT emp_name FROM
Employee WHERE email = 'john@[Link]';
Index-Only Plans

Definition: Query answered entirely from

the index — no table access needed.
Reduces I/O cost drastically.
Requirements: All requested attributes
appear in the index.
Example: SELECT name FROM Employee
WHERE emp_id=101; if index=(emp_id,
name).
Index-Only Plan Example

CREATE INDEX idx_emp_covering ON

Employee(emp_id, emp_name);
Query uses index-only plan:
SELECT emp_name FROM Employee WHERE
emp_id = 105;
→ No table lookup required as all data is in
the index.
Tools to Assist in Index Selection

Oracle SQL Tuning Advisor, SQL Server

Database Engine Tuning Advisor (DTA).
MySQL EXPLAIN PLAN and OPTIMIZER
TRACE.
Functions: Suggest missing indexes,
evaluate usage, recommend removal.
Example: DTA suggests index on
(customer_id, order_date) for frequent
reports.
Overview of Database Tuning

Goal: Optimize performance, scalability,

and concurrency.
Steps: Analyze workload, examine
execution plans, tune iteratively.
Tuning domains: Physical Design, Query
Optimization, Memory & Disk
Management.
Monitor response time and I/O statistics.
Query Tuning Examples
❌ Slow: SELECT * FROM Sales WHERE
YEAR(order_date) = 2025;
✅ Optimized: SELECT * FROM Sales WHERE
order_date BETWEEN '2025-01-01' AND '2025-12-
31';
❌ Subquery: SELECT student_name FROM Students
WHERE student_id IN (SELECT student_id FROM
Enrollment WHERE course_id = 301);
✅ Optimized Join: SELECT s.student_name FROM
Students s JOIN Enrollment e ON s.student_id =
e.student_id WHERE e.course_id = 301;
Tuning the Conceptual Schema

Adjust data model to improve performance.

Techniques: Denormalization, Derived
Attributes, Partitioning, Replication.
Example: Merge Order & Customer tables
for reporting.
Trade-off: Higher redundancy → more
update overhead.
Tuning Queries and Views

Use proper JOIN order and index-based

conditions.
Replace subqueries with joins where
possible.
Avoid SELECT *; fetch only needed attributes.
Use materialized views for repetitive
aggregations.
Example: Use date range instead of
YEAR(order_date)=2025.
Impact of Concurrency on Tuning

Concurrency control ensures isolation but

adds overhead.
Impacts: Locking delays, index contention,
slower throughput.
Solutions: Row-level locking, reduce
hotspot indexes, batch updates.
Example: Frequent Balance updates cause
lock contention → move updates to
queue.
Concurrency and Locking
Example

BEGIN TRANSACTION;
UPDATE Account SET balance = balance -
100 WHERE acc_no = 101;
COMMIT;
→ Row-level locking improves concurrency
by locking only affected rows.
Summary & Best Practices

Build indexes strategically based on

workload.
Use clustering to speed range queries.
Employ index-only plans for small attribute
retrievals.
Tune schema, queries, and views periodically.
Monitor concurrency impacts and adjust
locking levels.
Use DBMS tuning tools for automation.
 Points to Remember
• Indexes must be chosen to speed up important
queries (and perhaps some updates!).
– Index maintenance overhead on updates to key fields.
– Choose indexes that can help many queries, if possible.
– Build indexes to support index-only strategies.
– Clustering is an important decision; only one index on a
given relation can be clustered!
– Order of fields in composite index key can be important.

• Static indexes may have to be periodically re-built.

• Statistics have to be periodically updated.
 Points to remember (Contd.)
• Over time, indexes have to be fine-tuned (dropped,
created, re-clustered, ...) for performance.
– Should determine the plan used by the system, and
adjust the choice of indexes appropriately.
• System may still not find a good plan:
– Only left-deep plans?
– Null values, arithmetic conditions, string expressions,
the use of ORs, nested queries, etc. can confuse an
optimizer.
• So, may have to rewrite the query/view:
– Avoid nested queries, temporary relations, complex
conditions, and operations like DISTINCT and GROUP BY.