What is Functional Dependency?

A functional dependency occurs when one attribute uniquely determines

another attribute within a relation. It is a constraint that describes how
attributes in a table relate to each other. If attribute A functionally
determines attribute B we write this as the A→B.

Functional dependencies are used to mathematically express relations

among database entities and are very important to understanding advanced
concepts in Relational Database Systems.

Example:

roll_n nam dept_na dept_buildi

o e me ng

42 abc CO A4

43 pqr IT A3

44 xyz CO A4

45 xyz IT A3

46 mno EC B2

47 jkl ME B2

From the above table we can conclude some valid functional dependencies:

 roll_no → { name, dept_name, dept_building }→ Here, roll_no can

determine values of fields name, dept_name and dept_building, hence
a valid Functional dependency

 roll_no → dept_name , Since, roll_no can determine whole set of

{name, dept_name, dept_building}, it can determine its subset
dept_name also.
  dept_name → dept_building , Dept_name can identify the
dept_building accurately, since departments with different dept_name
will also have a different dept_building

 More valid functional dependencies: roll_no → name, {roll_no, name} ⇢

{dept_name, dept_building}, etc.

Here are some invalid functional dependencies:

 name → dept_name Students with the same name can have different
dept_name, hence this is not a valid functional dependency.

 dept_building → dept_name There can be multiple departments in

the same building. Example, in the above table departments ME and
EC are in the same building B2, hence dept_building → dept_name is
an invalid functional dependency.

 More invalid functional dependencies: name → roll_no, {name,

dept_name} → roll_no, dept_building → roll_no, etc.

Read more about What is Functional Dependency in DBMS ?

Types of Functional Dependencies in DBMS

1. Trivial functional dependency

2. Non-Trivial functional dependency

3. Multivalued functional dependency

4. Transitive functional dependency

1. Trivial Functional Dependency

In Trivial Functional Dependency, a dependent is always a subset of the

determinant. i.e. If X → Y and Y is the subset of X, then it is called trivial
functional dependency.

Symbolically: A→B is trivial functional dependency if B is a subset of A.

The following dependencies are also trivial: A→A & B→B

Example 1 :

 ABC -> AB

 ABC -> A

 ABC -> ABC

Example 2:

roll_n nam ag
o e e

42 abc 17

43 pqr 18

44 xyz 18

Here, {roll_no, name} → name is a trivial functional dependency, since the

dependent name is a subset of determinant set {roll_no, name}. Similarly,
roll_no → roll_no is also an example of trivial functional dependency.

2. Non-trivial Functional Dependency

In Non-trivial functional dependency, the dependent is strictly not a subset of

the determinant. i.e. If X → Y and Y is not a subset of X, then it is called Non-
trivial functional dependency.

Example 1 :

 Id -> Name

 Name -> DOB

Example 2:

roll_n nam ag
o e e

42 abc 17

43 pqr 18

44 xyz 18
Here, roll_no → name is a non-trivial functional dependency, since the
dependent name is not a subset of determinant roll_no. Similarly, {roll_no,
name} → age is also a non-trivial functional dependency, since age is not a
subset of {roll_no, name}

3. Semi Non Trivial Functional Dependencies

A semi non-trivial functional dependency occurs when part of the dependent

attribute (right-hand side) is included in the determinant (left-hand side), but
not all of it. This is a middle ground between trivial and non-trivial functional
dependencies. X -> Y is called semi non-trivial when X intersect Y is not
NULL.

Example:

Consider the following table:

Student_I Course_I
D D Course_Name

Computer
101 CSE101
Science

102 CSE102 Data Structures

Computer
103 CSE101
Science

Functional Dependency:

{StudentID,CourseID}→CourseID

This is semi non-trivial because:

 Part of the dependent attribute (Course_ID) is already included in the

determinant ({Student_ID, Course_ID}).

 However, the dependency is not completely trivial because

{StudentID}→CourseID is not implied directly.

4. Multivalued Functional Dependency

In Multivalued functional dependency, entities of the dependent set are not
dependent on each other. i.e. If a → {b, c} and there exists no functional
dependency between b and c, then it is called a multivalued functional
dependency.

Example:

bike_mod manuf_ye colo

el ar r

Blac
2007
tu1001 k

tu1001 2007 Red

Blac
2008
tu2012 k

tu2012 2008 Red

Blac
2009
tu2222 k

tu2222 2009 Red

In this table:

 X: bike_model

 Y: color

 Z: manuf_year

For each bike model (bike_model):

1. There is a group of colors (color) and a group of manufacturing years

(manuf_year).
 2. The colors do not depend on the manufacturing year, and the
manufacturing year does not depend on the colors. They are
independent.

3. The sets of color and manuf_year are linked only to bike_model.

That’s what makes it a multivalued dependency.

In this case these two columns are said to be multivalued dependent on

bike_model. These dependencies can be represented like this:

Read more about Multivalued Dependency in DBMS.

5. Transitive Functional Dependency

In transitive functional dependency, dependent is indirectly dependent on

determinant. i.e. If a → b & b → c, then according to axiom of transitivity, a →
c. This is a transitive functional dependency.

Example:

enrol_n nam dep building_

o e t no

42 abc CO 4

43 pqr EC 2

44 xyz IT 1

45 abc EC 2

Here, enrol_no → dept and dept → building_no. Hence, according to the

axiom of transitivity, enrol_no → building_no is a valid functional dependency.
This is an indirect functional dependency, hence called Transitive functional
dependency.

6. Fully Functional Dependency

In full functional dependency an attribute or a set of attributes uniquely

determines another attribute or set of attributes. If a relation R has attributes
X, Y, Z with the dependencies X->Y and X->Z which states that those
dependencies are fully functional.

Read more about Fully Functional Dependency.

7. Partial Functional Dependency

In partial functional dependency a non key attribute depends on a part of the

composite key, rather than the whole key. If a relation R has attributes X, Y, Z
where X and Y are the composite key and Z is non key attribute. Then X->Z
is a partial functional dependency in RBDMS.

Definition

A functional dependency exists when one attribute (or a group of attributes)

uniquely determines another attribute in a relation.

 Denoted as: X → Y

 Meaning: If two tuples (rows) have the same value for attribute(s) X,
then they must have the same value for attribute(s) Y.

Example:

Student_ID → Student_Name

Here, knowing Student_ID uniquely determines Student_Name.

Types of Functional Dependencies

1. Trivial Functional Dependency

o Occurs when the dependent attribute(s) is a subset of the

determinant.

o Example: {Roll_No, Name} → Name (trivial because Name is part

of the left side).

2. Non-Trivial Functional Dependency

o Occurs when the dependent attribute(s) is not a subset of the

determinant.

o Example: Roll_No → Name

 3. Transitive Functional Dependency

o Occurs when X → Y and Y → Z, then X → Z (transitively).

o Example: Roll_No → Dept_ID and Dept_ID → Dept_Name, so

Roll_No → Dept_Name.

4. Multivalued Dependency (MVD)

o Special case where one attribute determines multiple

independent values of another attribute.

o Represented as: X ↠ Y

Importance of Functional Dependencies

 Used in Normalization (reducing redundancy).

 Helps in designing database schemas.

 Ensures data consistency and integrity.

Examples

Consider a relation: Student(SID, Name, Course, Department)

 SID → Name
(Each student ID determines a unique name)

 SID → Course, Department

(Student ID determines course and department)

 Course → Department
(Each course belongs to one department)

Would you like me to give:

1. A table example with all functional dependencies derived?

2. How to find candidate keys using FDs?

3. Or a diagrammatic explanation of functional dependencies?

Which one should I explain next?

You said:

trivial,non-trivial,partial and full functional dependency with example

ChatGPT said:

Here’s a clear explanation of trivial, non-trivial, partial, and full functional

dependencies with examples:

1. Trivial Functional Dependency

A functional dependency is trivial when the right-hand side (RHS) is a subset

of the left-hand side (LHS).
It does not give any new information.

Notation:

X → Y is trivial if Y ⊆ X

Example:

Relation: Student(SID, Name, Course)

{SID, Name} → Name

 RHS (Name) is already a part of the LHS (SID, Name).

 Hence, it is trivial.

2. Non-Trivial Functional Dependency

A functional dependency is non-trivial when the RHS is not a subset of the

LHS.

Example:

Relation: Student(SID, Name, Course)

SID → Name

 RHS (Name) is not part of LHS (SID).

 Hence, it is non-trivial.

3. Partial Functional Dependency

A functional dependency is partial when a non-key attribute is functionally
dependent on part of a composite primary key, not on the whole key.

Example:

Relation: Student_Course(SID, Course_ID, Course_Name)

Primary Key: {SID, Course_ID}

Here:

 {SID, Course_ID} → Course_Name (Full dependency)

 But if Course_ID → Course_Name, then Course_Name depends only on

part of the key (Course_ID), not the whole key.

 This is a partial dependency, and it leads to redundancy (removed in

2NF).

4. Full Functional Dependency

A functional dependency is full when a non-key attribute depends on the

entire composite primary key, not just part of it.

Example:

Relation: Student_Course(SID, Course_ID, Marks)

Primary Key: {SID, Course_ID}

 {SID, Course_ID} → Marks

 Here, Marks depends on the whole key, not just SID or Course_ID
alone.

 Hence, this is a full functional dependency.

Armstrong's Axioms in Functional Dependency in DBMS

Armstrong's Axioms refer to a set of inference rules, introduced by William W.

Armstrong, that are used to test the logical implication of functional
dependencies. Given a set of functional dependencies F, the closure of F
(denoted as F+) is the set of all functional dependencies logically implied by
F. Armstrong's Axioms, when applied repeatedly, help generate the closure of
functional dependencies.

These axioms are fundamental in determining functional dependencies in

databases and are used to derive conclusions about the relationships
between attributes.

Axioms

 Axiom of Reflexivity: If A is a set of attributes and B is a subset of A,

then A holds B. If B⊆A then A→B. This property is trivial property.

 Axiom of Augmentation: If A→B holds and Y is the attribute set,

then AY→BY also holds. That is adding attributes to dependencies, does
not change the basic dependencies. If A→B, then AC→BC for any C.

 Axiom of Transitivity: Same as the transitive rule in algebra,

if A→B holds and B→C holds, then A→C also holds. A→B is called A
functionally which determines B. If X→Y and Y→Z, then X→Z.

Example:

Let’s assume the following functional dependencies:

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

1. Reflexivity: Since any set of attributes determines its subset, we can

immediately infer the following:

 {A} → {A} (A set always determines itself).

 {B} → {B}.

 {A, C} → {A}.

2. Augmentation: If we know that {A} → {B}, we can add the same attribute
(or set of attributes) to both sides:

 From {A} → {B}, we can augment both sides with {C}: {A, C} → {B,
C}.

 From {B} → {C}, we can augment both sides with {A}: {A, B} → {C,
B}.

3. Transitivity: If we know {A} → {B} and {B} → {C}, we can infer that:

 {A} → {C} (Using transitivity: {A} → {B} and {B} → {C}).

Although Armstrong's axioms are sound and complete, there are additional
rules for functional dependencies that are derived from them. These rules
are introduced to simplify operations and make the process easier.

Secondary Rules

These rules can be derived from the above axioms.

 Union: If A→B holds and A→C holds, then A→BC holds.

If X→Y and X→Z then X→YZ.

 Composition: If A→B and X→Y hold, then AX→BY holds.

 Decomposition: If A→BC holds then A→B and A→C hold.

If X→YZ then X→Y and X→Z.

 Pseudo Transitivity: If A→B holds and BC→D holds, then AC→D holds.
If X→Y and YZ→W then XZ→W.

Example:

Let’s assume we have the following functional dependencies in a relation

schema:
{A} → {B}
{A} → {C}
{X} → {Y}
{Y, Z} → {W}

Now, let's apply the Secondary Rules to derive new functional dependencies.

1. Union Rule: If A → B and A → C, then by the Union Rule, we can infer:

 A → BC This means if A determines both B and C, it also determines

their combination, BC.

2. Composition Rule: If A → B and X → Y hold, then by the Composition Rule,

we can infer:

 AX → BY

3. Decomposition Rule: If A → BC holds, then by the Decomposition Rule, we

can infer:

 A → B and A → C

4. Pseudo Transitivity Rule: If A → B and BC → D hold, then by the Pseudo

Transitivity Rule, we can infer:

 AC → D

Armstrong Relation

Armstrong Relation can be stated as a relation that is able to satisfy all

functional dependencies in the F+ Closure. In the given set of dependencies,
the size of the minimum Armstrong Relation is an exponential function of the
number of attributes present in the dependency under consideration.

Why Armstrong Axioms Are Considered Sound and Complete?

Soundness: Armstrong's axioms are sound because any functional

dependency inferred using them will always be valid and hold true in every
relation state that satisfies the original set of dependencies.

Completeness: Armstrong's axioms are complete because applying them

repeatedly will generate all possible functional dependencies that can be
derived from the original set, ensuring no dependencies are missed.

Armstrong's Axioms are a set of rules used in Database Management

Systems (DBMS) to infer all possible functional dependencies (FDs) from a
given set of FDs. They are sound (produce only correct FDs) and complete
(produce all possible correct FDs).

The Three Armstrong's Axioms

1. Reflexivity Rule

o If Y ⊆ X, then X → Y holds.

o Meaning: A set of attributes always determines its own subset.

Example:
If X = {A, B, C}, then X → {A, C} is true.

2. Augmentation Rule

o If X → Y, then XZ → YZ holds.

o Meaning: Adding extra attributes to both sides does not change

the dependency.

Example:
If A → B, then adding C gives AC → BC.

3. Transitivity Rule

o If X → Y and Y → Z, then X → Z holds.

o Meaning: Dependencies can be chained.

Example:
If A → B and B → C, then A → C.

Additional Rules Derived from Armstrong's Axioms

From these three axioms, other useful rules can be derived:

1. Union Rule

o If X → Y and X → Z, then X → YZ.

2. Decomposition Rule
 o If X → YZ, then X → Y and X → Z.

3. Pseudotransitivity Rule

o If X → Y and WY → Z, then WX → Z.

Importance of Armstrong's Axioms

 Used to find the closure of a set of functional dependencies (F+).

 Helps in normalization of databases (from 1NF to BCNF, 3NF, etc.).

 Provides a foundation for reasoning about FDs.

Attribute Closure in DBMS

Functional dependency and attribute closure are essential for maintaining

data integrity and building effective, organized and normalized databases.
Attribute closure of an attribute set can be defined as set of attributes which
can be functionally determined from it.

How to find attribute closure of an attribute set?

To find attribute closure of an attribute set:

 Add elements of attribute set to the result set.

 Recursively add elements to the result set which can be functionally

determined from the elements of the result set.

Using FD set of table 1, attribute closure can be determined as:

(STUD_NO)++= {STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE,

STUD_COUNTRY, STUD_AGE}
(STUD_STATE)+ = {STUD_STATE, STUD_COUNTRY}

Important Points About Attribute Closure

 Helps to identify all possible attributes that can be derived from a set
of given attributes.
  Helps in database design by showing how attributes and tables are
related, which can improve query performance.

 Can be computationally expensive, especially for large datasets.

 Become complex to manage as the number of attributes and tables

increases.

How to Find Candidate Keys and Super Keys Using Attribute Closure?

 If attribute closure of an attribute set contains all attributes of relation,

the attribute set will be super key of the relation.

 If no subset of this attribute set can functionally determine all

attributes of the relation, the set will be candidate key as well. For
Example, using FD set of table 1

(STUD_NO, STUD_NAME)+ = {STUD_NO, STUD_NAME, STUD_PHONE,

STUD_STATE, STUD_COUNTRY, STUD_AGE}

(STUD_NO)+= {STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE,

STUD_COUNTRY, STUD_AGE}

(STUD_NO, STUD_NAME) will be super key but not candidate key because its
subset (STUD_NO)+ is equal to all attributes of the relation. So, STUD_NO will
be a candidate key.

Prime and Non-Prime Attributes

Attributes which are parts of any candidate key of relation are called as
prime attribute, others are non-prime attributes. For Example, STUD_NO in
STUDENT relation is prime attribute, others are non-prime attribute.

GATE Questions

Q.1: Consider the relation scheme R = {E, F, G, H, I, J, K, L, M, N} and the set

of functional dependencies {{E, F} -> {G}, {F} -> {I, J}, {E, H} -> {K, L}, K
-> {M}, L -> {N} on R. What is the key for R? (GATE-CS-2014)

A. {E, F}
B. {E, F, H}
C. {E, F, H, K, L}
D. {E}

Solution:
Finding attribute closure of all given options, we get:
{E,F}+ = {EFGIJ}
{E,F,H}+= {EFHGIJKLMN}
{E,F,H,K,L}+ = {{EFHGIJKLMN}
{E}+= {E}
{EFH}+ and {EFHKL}+ results in set of all attributes, but EFH is minimal. So
it will be candidate key. So correct option is (B).

Q.2: How to check whether an FD can be derived from a given FD set?

Solution:

To check whether an FD A->B can be derived from an FD set F,

1. Find (A)+ using FD set F.

2. If B is subset of (A)+, then A->B is true else not true.

Q.3: In a schema with attributes A, B, C, D and E following set of functional

dependencies are given
{A -> B, A -> C, CD -> E, B -> D, E -> A}
Which of the following functional dependencies is NOT implied by the above
set? (GATE IT 2005)

A. CD -> AC
B. BD -> CD
C. BC -> CD
D. AC -> BC

Solution:

Using FD set given in question,

(CD)+ = {CDEAB} which means CD -> AC also holds true.
(BD)+ = {BD} which means BD -> CD can't hold true. So this FD is no
implied in FD set. So (B) is the required option.
Others can be checked in the same way.

Q.4: Consider a relation scheme R = (A, B, C, D, E, H) on which the following

functional dependencies hold: {A–>B, BC–> D, E–>C, D–>A}. What are the
candidate keys of R? [GATE 2005]

(a) AE, BE
(b) AE, BE, DE
(c) AEH, BEH, BCH
(d) AEH, BEH, DEH

Solution:

(AE)+ = {ABECD} which is not set of all attributes. So AE is not a candidate

key. Hence option A and B are wrong.
(AEH)+= {ABCDEH}
(BEH)+ = {BEHCDA}
(BCH)+= {BCHDA} which is not set of all attributes. So BCH is not a
candidate key. Hence option C is wrong.
So correct answer is D.

Closure Of Functional Dependency : Introduction

 The Closure Of Functional Dependency means the complete set of all

possible attributes that can be functionally derived from given
functional dependency using the inference rules known as Armstrong’s
Rules.

 If “F” is a functional dependency then closure of functional dependency

can be denoted using “{F}+”.

 There are three steps to calculate closure of functional dependency.

These are:

Step-1 : Add the attributes which are present on Left Hand Side in the
original functional dependency.

Step-2 : Now, add the attributes present on the Right Hand Side of the
functional dependency.

Step-3 : With the help of attributes present on Right Hand Side, check the
other attributes that can be derived from the other given functional
dependencies. Repeat this process until all the possible attributes which can
be derived are added in the closure.
  Seems difficult? Check out the example explained below and it will
surely clear your doubt on how to calculate closure of functional
dependency.

Closure Of Functional Dependency : Examples

Example-1 : Consider the table student_details having (Roll_No, Name,Marks,

Location) as the attributes and having two functional dependencies.

FD1 : Roll_No Name, Marks

FD2 : Name Marks, Location

Now, We will calculate the closure of all the attributes present in the relation
using the three steps mentioned below.

Step-1 : Add attributes present on the LHS of the first functional dependency
to the closure.

{Roll_no}+ = {Roll_No}

Step-2 : Add attributes present on the RHS of the original functional

dependency to the closure.

{Roll_no}+ = {Roll_No, Marks}

Step-3 : Add the other possible attributes which can be derived using
attributes present on the RHS of the closure. So Roll_No attribute cannot
functionally determine any attribute but Name attribute can determine other
attributes such as Marks and Location using 2 nd Functional
Dependency(Name [icon name="long-arrow-right" class=""
unprefixed_class=""] Marks, Location).

Therefore, complete closure of Roll_No will be :

{Roll_no}+ = {Roll_No, Marks, Name, Location}

Similarly, we can calculate closure for other attributes too i.e “Name”.

Step-1 : Add attributes present on the LHS of the functional dependency

to the closure.

{Name}+ = {Name}

Step-2 : Add the attributes present on the RHS of the functional dependency
to the closure.

{Name}+ = {Name, Marks, Location}

Step-3 : Since, we don’t have any functional dependency where “Marks or

Location” attribute is functionally determining any other attribute , we
cannot add more attributes to the closure. Hence complete closure of Name
would be :

{Name}+ = {Name, Marks, Location}

NOTE: We don’t have any Functional dependency where marks and location
can functionally determine any attribute. Hence, for those attributes we can
only add the attributes themselves in their closures. Therefore,

{Marks}+ = {Marks}

and

{Location}+ = {Location}

Example-2 : Consider a relation R(A,B,C,D,E) having below mentioned

functional dependencies.

FD1 : A BC

FD2 : C B

FD3 : D E

FD4 : E D

Now, we need to calculate the closure of attributes of the relation R. The

closures will be:
{A}+ = {A,
B, C}

{B}+ = {B}

{C}+ = {B,
C}

{D}+ = {D,
E}

{E}+ = {E}

Closure Of Functional Dependency : Calculating Candidate Key

 “A Candidate Key of a relation is an attribute or set of attributes that

can determine the whole relation or contains all the attributes in its
closure."

 Let’s try to understand how to calculate candidate keys.

Example-1 : Consider the relation R(A,B,C) with given functional

dependencies :

FD1 : A B

FD2 : B C

Now, calculating the closure of the attributes as :

{A}+ = {A,
B, C}

{B}+ = {B,
C}

{C}+ = {C
}

Clearly, “A” is the candidate key as, its closure contains all the attributes
present in the relation “R”.

Example-2 : Consider another relation R(A, B, C, D, E) having the Functional

dependencies :
FD1 : A BC

FD2 : C B

FD3 : D E

FD4 : E D

Now, calculating the closure of the attributes as :

{A}+ = {A,
B, C}

{B}+ = {B}

{C}+ = {C,
B}

{D}+ = {E,
D}

{E}+ = {E,
D}

In this case, a single attribute is unable to determine all the attribute on its
own like in previous example. Here, we need to combine two or more
attributes to determine the candidate keys.

{A, D}+ = {A, B,

C, D, E}

{A, E}+ = {A, B,

C, D, E}

Hence, "AD" and "AE" are the two possible keys of the given relation “R”. Any
other combination other than these two would have acted as extraneous
attributes.

NOTE : Any relation “R” can have either single or multiple

candidate keys.

Closure Of Functional Dependency : Key Definitions

 1. Prime Attributes : Attributes which are indispensable part of candidate
keys. For example : “A, D, E” attributes are prime attributes in above
example-2.

2. Non-Prime Attributes : Attributes other than prime attributes which

does not take part in formation of candidate keys. For example.

3. Extraneous Attributes : Attributes which does not make any effect on

removal from candidate key.

For example : Consider the relation R(A, B, C, D) with functional

dependencies :

FD1 : A BC

FD2 : B C

FD3 : D C

Here, Candidate key can be “AD” only. Hence,

Prime Attributes : A, D.

Non-Prime Attributes : B, C

Extraneous Attributes : B, C(As if we add any of the to the candidate key, it

will remain unaffected). Those attributes, which if removed does not affect
closure of that set.

Closure of Functional Dependencies (F⁺)

The closure of functional dependencies (F⁺) is the complete set of all

functional dependencies that can be logically derived from a given set of FDs
(F) using Armstrong’s axioms:

 Reflexivity

 Augmentation

 Transitivity

Why is Closure Important?

 To determine all possible functional dependencies in a relation.

 To check if a particular FD is implied by a set of FDs.

 To find candidate keys for a relation.

  To help in normalization.

Types of Closure

1. Closure of a Set of Functional Dependencies (F⁺)

This is the set of all FDs that can be derived from a given set F.

Example:

 Given FDs: F = { A → B, B → C }

 Derived FDs:

o From given: A → B, B → C

o By Transitivity: A → C

 So, F⁺ = { A → B, B → C, A → C }

2. Closure of an Attribute Set (X⁺)

This is the set of all attributes that can be determined by X using F.

Steps to Find Attribute Closure (X⁺)

1. Start with X⁺ = X.

2. For each functional dependency P → Q in F:

o If P ⊆ X⁺, then add Q to X⁺.

3. Repeat until no more attributes can be added.

Example: Find A⁺

Given:
Relation R(A, B, C, D)
FDs: F = { A → B, B → C, C → D }

Steps:

1. Start: A⁺ = {A}

2. A → B ⇒ A⁺ = {A, B}

3. B → C ⇒ A⁺ = {A, B, C}

4. C → D ⇒ A⁺ = {A, B, C, D}

Result: A⁺ = {A, B, C, D}
Normal Forms in DBMS

In the world of database management, Normal Forms are important for

ensuring that data is structured logically, reducing redundancy, and
maintaining data integrity. When working with databases, especially
relational databases, it is critical to follow normalization techniques that help
to eliminate unnecessary duplication, improve performance, and minimize
the risk of anomalies.

What is Normalization in DBMS?

Normalization is a systematic approach to organize data within a database to

reduce redundancy and eliminate undesirable characteristics such as
insertion, update, and deletion anomalies. The process involves breaking
down large tables into smaller, well-structured ones and defining
relationships between them. This not only reduces the chances of storing
duplicate data but also improves the overall efficiency of the database.

Why is Normalization Important?

 Reduces Data Redundancy: Duplicate data is stored efficiently,

saving disk space and reducing inconsistency.

 Improves Data Integrity: Ensures the accuracy and consistency of

data by organizing it in a structured manner.

 Simplifies Database Design: By following a clear structure,

database designs become easier to maintain and update.

 Optimizes Performance: Reduces the chance of anomalies and

increases the efficiency of database operations.

What are Normal Forms in DBMS?

Normalization is a technique used in database design to reduce

redundancy and improve data integrity by organizing data into tables and
ensuring proper relationships. Normal Forms are different stages of
normalization, and each stage imposes certain rules to improve the structure
and performance of a database. Let's break down the various normal forms
step-by-step to understand the conditions that need to be satisfied at each
level:

1. First Normal Form (1NF): Eliminating Duplicate Records

A table is in 1NF if it satisfies the following conditions:

  All columns contain atomic values (i.e., indivisible values).

 Each row is unique (i.e., no duplicate rows).

 Each column has a unique name.

 The order in which data is stored does not matter.

Example of 1NF Violation: If a table has a column "Phone Numbers" that

stores multiple phone numbers in a single cell, it violates 1NF. To bring it into
1NF, you need to separate phone numbers into individual rows.

2. Second Normal Form (2NF): Eliminating Partial Dependency

A relation is in 2NF if it satisfies the conditions of 1NF and additionally. No

partial dependency exists, meaning every non-prime attribute (non-key
attribute) must depend on the entire primary key, not just a part of it.

Example: For a composite key (StudentID, CourseID), if

the StudentName depends only on StudentID and not on the entire key, it
violates 2NF. To normalize, move StudentName into a separate table where
it depends only on StudentID.

3. Third Normal Form (3NF): Eliminating Transitive Dependency

A relation is in 3NF if it satisfies 2NF and additionally, there are no transitive

dependencies. In simpler terms, non-prime attributes should not depend on
other non-prime attributes.

Example: Consider a table with (StudentID, CourseID, Instructor).

If Instructor depends on CourseID, and CourseID depends on StudentID,
then Instructor indirectly depends on StudentID, which violates 3NF. To
resolve this, place Instructor in a separate table linked by CourseID.

4. Boyce-Codd Normal Form (BCNF): The Strongest Form of 3NF

BCNF is a stricter version of 3NF where for every non-trivial functional

dependency (X → Y), X must be a superkey (a unique identifier for a record in
the table).

Example: If a table has a dependency (StudentID, CourseID) → Instructor,

but neither StudentID nor CourseID is a superkey, then it violates BCNF. To
bring it into BCNF, decompose the table so that each determinant is a
candidate key.

5. Fourth Normal Form (4NF): Removing Multi-Valued Dependencies

A table is in 4NF if it is in BCNF and has no multi-valued dependencies. A
multi-valued dependency occurs when one attribute determines another, and
both attributes are independent of all other attributes in the table.

Example: Consider a table where (StudentID, Language, Hobby) are

attributes. If a student can have multiple hobbies and languages, a multi-
valued dependency exists. To resolve this, split the table into separate
tables for Languages and Hobbies.

6. Fifth Normal Form (5NF): Eliminating Join Dependency

5NF is achieved when a table is in 4NF and all join dependencies are
removed. This form ensures that every table is fully decomposed into smaller
tables that are logically connected without losing information.

Example: If a table contains (StudentID, Course, Instructor) and there is a

dependency where all combinations of these columns are needed for a
specific relationship, you would split them into smaller tables to remove
redundancy.

Advantages of Normal Form

1. Reduced data redundancy: Normalization helps to eliminate duplicate

data in tables, reducing the amount of storage space needed and improving
database efficiency.

2. Improved data consistency: Normalization ensures that data is stored

in a consistent and organized manner, reducing the risk of data
inconsistencies and errors.

3. Simplified database design: Normalization provides guidelines for

organizing tables and data relationships, making it easier to design and
maintain a database.

4. Improved query performance: Normalized tables are typically easier to

search and retrieve data from, resulting in faster query performance.

5. Easier database maintenance: Normalization reduces the complexity

of a database by breaking it down into smaller, more manageable tables,
making it easier to add, modify, and delete data.

Common Challenges of Over-Normalization

While normalization is a powerful tool for optimizing databases, it's important

not to over-normalize your data. Excessive normalization can lead to:
  Complex Queries: Too many tables may result in multiple joins,
making queries slow and difficult to manage.

 Performance Overhead: Additional processing required for joins in

overly normalized databases may hurt performance, especially in
large-scale systems.

In many cases, denormalization (combining tables to reduce the need for

complex joins) is used for performance optimization in specific applications,
such as reporting systems.

When to Use Normalization and Denormalization

 Normalization is best suited for transactional systems where data

integrity is paramount, such as banking systems and enterprise
applications.

 Denormalization is ideal for read-heavy applications like data

warehousing and reporting systems where performance and query
speed are more critical than data integrity.

Applications of Normal Forms in DBMS

 Ensures Data Consistency:Prevents data anomalies by ensuring

each piece of data is stored in one place, reducing inconsistencies.

 Reduces Data Redundancy: Minimizes repetitive data, saving

storage space and avoiding errors in data updates or deletions.

 Improves Query Performance: Simplifies queries by breaking large

tables into smaller, more manageable ones, leading to faster data
retrieval.

 Enhances Data Integrity: Ensures that data is accurate and reliable

by adhering to defined relationships and constraints between tables.

 Easier Database Maintenance: Simplifies updates, deletions, and

modifications by ensuring that changes only need to be made in one
place, reducing the risk of errors.

 Facilitates Scalability: Makes it easier to modify, expand, or scale

the database structure as business requirements grow.

 Supports Better Data Modeling: Helps in designing databases that

are logically structured, with clear relationships between tables,
making it easier to understand and manage.
  Reduces Update Anomalies: Prevents issues like insertion, deletion,
or modification anomalies that can arise from redundant data.

 Improves Data Integrity and Security: By reducing unnecessary

data duplication, normal forms help ensure sensitive information is
securely and correctly maintained.

 Optimizes Storage Efficiency: By organizing data into smaller

tables, storage is used more efficiently, reducing the overhead for
large databases

Difference between Normalization and Denormalization

Normalization and Denormalization are used to alter the structure of a

database. The main difference between normalization and denormalization is
that normalization is used to remove the redundancy in the table, while
denormalization is used to add the redundancy which means combining
multiple tables so that execute query quickly. In this article, we'll explore the
key differences between Normalization and Denormalization and how they
impact database design.

What is the Normalization?

Normalization is the method used in a database to reduce the data

redundancy and data inconsistency from the table. It is the technique in
which Non-redundancy and consistency data are stored in the set schema.
By using normalization the number of tables is increased instead of
decreased.

Advantages

 Data is reduced in the table.

 Optimized memory.

 Maintain data integrity.

Disadvantages

 The number of tables is increased.

 Consume more resources when using joins expensive operations.

What is the Denormalization?

Denormalization is also the method which is used in a database. It is used to
add the redundancy to execute the query quickly. It is a technique in which
data are combined to execute the query quickly. By using denormalization
the number of tables is decreased which oppose to the normalization.

Advantages

 Execute the query quickly.

 Decreased the number of tables.

Disadvantages

 Wastage of memory because store the duplicate data.

 Increase the number of tables.

 Does not maintain data integrity.

Difference Between Normalization and Denormalization

Normalization Denormalization

In normalization, Non-redundancy
In denormalization, data are combined
and consistency data are stored in
to execute the query quickly.
set schema.

In normalization, Data redundancy In denormalization, redundancy is

and inconsistency is reduced. added for quick execution of queries.

Data integrity is maintained in Data integrity is not maintained in

normalization. denormalization.

In denormalization, redundancy is
In normalization, redundancy is
added instead of reduction or
reduced or eliminated.
elimination of redundancy.

Number of tables in normalization Denormalization, Number of tables in

is increased. decreased.
Normalization optimize the uses of Denormalization do not optimize the
disk spaces. disk spaces.

Conclusion

Normalization and Denormalization both are the method which use in

database but it works opposite to each other. One side normalization is used
for reduce or removing the redundancy which means there will be no
duplicate data or entries in the same table while Denormalization is used for
add the redundancy into normalized table so that enhance the functionality
and minimize the running time of database queries (like joins operation ).

Transaction in DBMS

Last Updated : 06 Aug, 2025

A transaction refers to a sequence of one or more operations (such as read,

write, update, or delete) performed on the database as a single logical unit of
work.

 A transaction ensures that either all the operations are successfully

executed (committed) or none of them take effect (rolled back).

 Transactions are designed to maintain the integrity, consistency and

reliability of the database, even in the case of system failures or
concurrent access.
Transaction

All types of database access operation which are held between the beginning
and end transaction statements are considered as a single logical
transaction. During the transaction the database is inconsistent. Only once
the database is committed the state is changed from one consistent state to
another.

Example: Let’s consider an online banking application:

Transaction: When a user performs a money transfer, several operations

occur, such as:

 Reading the account balance of the sender.

 Writing the deducted amount from the sender’s account.

 Writing the added amount to the recipient’s account.

In a transaction, all these steps should either complete successfully or, if

any error occurs, the database should rollback to its previous state,
ensuring no partial data is written to the system.

Facts about Database Transactions

  A transaction is a program unit whose execution may or may not
change the contents of a database.

 The transaction is executed as a single unit.

 If the database operations do not update the database but only

retrieve data, this type of transaction is called a read-only transaction.

 A successful transaction can change the database from one

CONSISTENT STATE to another.

 DBMS transactions must be atomic, consistent, isolated and durable.

 If the database were in an inconsistent state before a transaction, it

would remain in the inconsistent state after the transaction.

Operations of Transaction

A user can make different types of requests to access and modify the
contents of a database. So, we have different types of operations relating to
a transaction. They are discussed as follows:

1) Read(X)

A read operation is used to read the value of a particular database

element X and stores it in a temporary buffer in the main memory for further
actions such as displaying that value.

Example: For a banking system, when a user checks their balance, a Read
operation is performed on their account balance:

SELECT balance FROM accounts WHERE account_id = 'A123';

This updates the balance of the user's account after withdrawal.

2) Write(X)

A write operation stores updated data from main memory back to the
database. It usually follows a read, where data is fetched, modified (e.g.,
arithmetic changes), and then written back to save the updated value.

Example: For the banking system, if a user withdraws money,

a Write operation is performed after the balance is updated:

UPDATE accounts SET balance = balance - 100 WHERE account_id = 'A123';

This updates the balance of the user’s account after withdrawal.

3) Commit
This operation in transactions is used to maintain integrity in the database.
Due to some failure of power, hardware, or software, etc., a transaction
might get interrupted before all its operations are completed. This may cause
ambiguity in the database, i.e. it might get inconsistent before and after the
transaction.

Example: After a successful money transfer in a banking system,

a Commit operation finalizes the transaction:

COMMIT;

Once the transaction is committed, the changes to the database are

permanent, and the transaction is considered successful.

4) Rollback

A rollback undoes all changes made by a transaction if an error occurs,

restoring the database to its last consistent state. It helps prevent data
inconsistency and ensures safety.

Example: Suppose during the money transfer process, the system

encounters an issue, like insufficient funds in the sender’s account. In that
case, the transaction is rolled back:

ROLLBACK;

This will undo all the operations performed so far and ensure that the
database remains consistent.

ACID Properties of Transaction

Transactions in DBMS must ensure data is accurate and reliable. They follow
four key ACID properties:

1. Atomicity: A transaction is all or nothing. If any part fails, the entire

transaction is rolled back. Example: While transferring money, both
debit and credit must succeed. If one fails, nothing should change.

2. Consistency: A transaction must keep the database in a valid state,

moving it from one consistent state to another. Example: If balance is
₹1000 and ₹200 is withdrawn, the new balance should be ₹800.

3. Isolation: Transactions run independently. One transaction’s

operations should not affect another’s intermediate steps. Example:
Two users withdrawing from the same account must not interfere with
each other’s balance updates.
 4. Durability: Once a transaction is committed, its changes stay even if
the system crashes. Example: After a successful transfer, the updated
balance remains safe despite a power failure.

Transaction Schedules

When multiple transaction requests are made at the same time, we need to
decide their order of execution. Thus, a transaction schedule can be defined
as a chronological order of execution of multiple transactions. Example: After
a successful transfer, the updated balance remains safe despite a power
failure.

There are broadly two types of transaction schedules discussed as follows:

i) Serial Schedule

In a serial schedule, transactions execute one at a time, ensuring database

consistency but increasing waiting time and reducing system throughput. To
improve throughput while maintaining consistency, concurrent schedules
with strict rules are used, allowing safe simultaneous execution of
transactions.

ii) Non-Serial Schedule

Non-serial schedule is a type of transaction schedule where multiple

transactions are executed concurrently, interleaving their operations, instead
of running one after another. It improves system efficiency but requires
concurrency control to maintain database consistency.

Types of Schedules in DBMS

Last Updated : 28 Jul, 2025

Scheduling is the process of determining the order in which transactions are

executed. When multiple transactions run concurrently, scheduling ensures
that operations are executed in a way that prevents conflicts or overlaps
between them.

There are several types of schedules, all of them are depicted in the diagram
below:
Types of Schedules

Let's discuss the different types of schedules one by one:

Serial Schedule

Schedules in which the transactions are executed non-interleaved, i.e., a

serial schedule is one in which no transaction starts until a running
transaction has ended are called serial schedules. Example: Consider the
following schedule involving two transactions T1 and T2 .
T1 T2

R(A
)

W(A
)

R(B
)

W(B
)

R(A
)

R(B
)

where R(A) denotes that a read operation is performed on some data item 'A'
This is a serial schedule since the transactions perform serially in the order
T1 —> T2

Non-Serial Schedule

This is a type of Scheduling where the operations of multiple transactions are

interleaved. This might lead to a rise in the concurrency problem. The
transactions are executed in a non-serial manner, keeping the end result
correct and same as the serial schedule. This sort of schedule does not
provide any benefit of the concurrent transaction. It can be of two types
namely,

[Link] Scheduling (Concurrency Control)

 Ensures database consistency in non-serial schedules by verifying if

they behave like serial schedules.
  In a serial schedule, transactions execute one after another, ensuring
correctness without conflicts.

 Non-serial schedules allow concurrent transactions but must be

serializable to maintain correctness.

Why Serializable?

 Prevents anomalies due to concurrent execution.

 Allows better CPU and resource utilization.

 Improves throughput without sacrificing consistency.

Two types of serializable scheduling are:

i. Conflict Serializable: A schedule is called conflict serializable if it can be

transformed into a serial schedule by swapping non-conflicting operations.
Two operations are said to be conflicting if all conditions satisfy:

 They belong to different transactions

 They operate on the same data item

 At Least one of them is a write operation

ii. View Serializable: A Schedule is called view serializable if it is view

equal to a serial schedule (no overlapping transactions). A conflict schedule
is a view serializable but if the serializability contains blind writes, then the
view serializable does not conflict serializable.

2. Non-Serializable Scheduling

Schedules that do not preserve serial equivalence and may lead to

inconsistencies if not handled carefully.

i. Recoverable Schedule: Schedules in which transactions commit only

after all transactions whose changes they read commit are
called recoverable schedules. In other words, if some transaction T j is
reading value updated or written by some other transaction Ti , then the
commit of Tj must occur after the commit of Ti .

Example: Consider the following schedule involving two transactions T1 and

T2 .

T1 T2
R(A)

W(A)

W(A)

R(A)

comm
it

comm
it

This is a recoverable schedule since T1 commits before T2 , that makes the

value read by T2 correct. There can be three types of recoverable schedule:

ii. Cascading Schedule: Also called Avoids cascading aborts/rollbacks

(ACA). When there is a failure in one transaction and this leads to the rolling
back or aborting other dependent transactions, then such scheduling is
referred to as Cascading rollback or cascading abort. Example:

iii. Cascadeless Schedule: Schedules in which transactions read values

only after all transactions whose changes they are going to read commit are
called cascadeless schedules. Avoids that a single transaction abort leads to
a series of transaction rollbacks. A strategy to prevent cascading aborts is to
disallow a transaction from reading uncommitted changes from another
transaction in the same schedule.

In other words, if some transaction Tj wants to read value updated or written

by some other transaction Ti , then the commit of Tj must read it after the
commit of Ti .

Example: Consider the following schedule involving two transactions T1 and

T2 .

T1 T2

R(A)
W(A)

W(A)

comm
it

R(A)

comm
it

This schedule is cascadeless. Since the updated value of A is read by T2 only

after the updating transaction i.e. T1 commits.

Example: Consider the following schedule involving two transactions T1 and

T2 .

T1 T2

R(A)

W(A
)

R(A)

W(A
)
abor
t

abor
t

It is a recoverable schedule but it does not avoid cascading aborts. It can be

seen that if T1 aborts, T2 will have to be aborted too in order to maintain the
correctness of the schedule as T2 has already read the uncommitted value
written by T1 .

iv. Strict Schedule: A schedule is strict if for any two transactions Ti , Tj , if

a write operation of Ti precedes a conflicting operation of Tj (either read or
write), then the commit or abort event of Ti also precedes that conflicting
operation of Tj . In other words, Tj can read or write updated or written value
of Ti only after Ti commits/aborts.

Example: Consider the following schedule involving two transactions T1 and

T2 .

T1 T2

R(A)

R(A)

W(A)

comm
it

W(A)

R(A)
 comm
it

This is a strict schedule since T2 reads and writes A which is written by

T1 only after the commit of T1 .

v. Non-Recoverable Schedule: Example: Consider the following schedule

involving two transactions T1 and T2 .

T1 T2

R(A)

W(A
)

W(A)

R(A)

comm
it

abor
t

T2 read the value of A written by T1, and committed. T1 later aborted,

therefore the value read by T2 is wrong, but since T2 committed, this
schedule is non-recoverable.

Note - It can be seen that:

 Cascadeless schedules are stricter than recoverable schedules or are a

subset of recoverable schedules.
  Strict schedules are stricter than cascadeless schedules or are a subset
of cascadeless schedules.

 Serial schedules satisfy constraints of all recoverable, cascadeless and

strict schedules and hence is a subset of strict schedules.

The relation between various types of schedules can be depicted as:

Example:

Consider the following schedule:

S:R1(A), W2(A), Commit2, W1(A), W3(A), Commit3, Commit1

Question: Which of the following is true?

(A) The schedule is view serializable schedule and strict recoverable

schedule(
B) The schedule is non-serializable schedule and strict recoverable schedule
(C) The schedule is non-serializable schedule and is not strict recoverable
schedule.
(D) The Schedule is serializable schedule and is not strict recoverable
schedule

Solution: The schedule can be re-written as:-

T1 T2 T3

R(A)

W(A)

Comm
it

W(A)

W(A)

Comm
it

Comm
it

First of all, it is a view serializable schedule as it has view equal serial

schedule T1 —> T2 —> T3 which satisfies the initial and updated reads and
final write on variable A which is required for view serializability. Now we can
see there is write – write pair done by transactions T1 followed by T3 which is
violating the above-mentioned condition of strict schedules as T3 is
supposed to do write operation only after T1 commits which is violated in the
given schedule. Hence the given schedule is serializable but not strict
recoverable.
So, option (D) is correct.
🔹 What is Lock-Based Concurrency Control?

Lock-based concurrency control is a synchronization technique in DBMS

where transactions use locks on data items before accessing them.

This prevents conflicts (lost update, dirty read, etc.) when multiple
transactions execute concurrently.

🔹 Types of Locks

1. Shared Lock (S-lock / Read lock)

o If a transaction holds a shared lock, it can read but cannot

write.

o Multiple transactions can hold a shared lock on the same item.

2. Exclusive Lock (X-lock / Write lock)

o If a transaction holds an exclusive lock, it can read and write.

o No other transaction can hold either S-lock or X-lock on the same

item.

🔹 Example

Two transactions:

 T1: Read balance of A, deduct ₹500, write back.

 T2: Read balance of A, add ₹200, write back.

Without Locks ❌

Both read the same balance at the same time → final result is inconsistent
(lost update).

With Locks ✅

 T1 first requests an X-lock on A → it can update safely.

 T2 must wait until T1 releases the lock.

 After T1 finishes, T2 gets the lock and updates.

👉 Final balance is correct.
🔹 Lock-Based Protocols

1. Simple Locking

o Transaction requests a lock before accessing data.

o Releases lock after use.

2. Two-Phase Locking (2PL)

o Ensures serializability.

o Phase 1 (Growing phase): Transaction acquires locks, but

cannot release any.

o Phase 2 (Shrinking phase): Transaction releases locks, but

cannot acquire new ones.

3. Strict 2PL

o Locks are released only after transaction commits/aborts.

o Prevents cascading rollbacks.

🔹 Problems with Locking

 Deadlock → Two transactions wait for each other’s locks forever.

 Starvation → A transaction keeps waiting for locks because others

keep preempting.

👉 DBMS uses deadlock detection, prevention, or timeouts to handle

these.

✅ In short:
Lock-based concurrency control = DBMS uses shared and exclusive locks
to manage concurrent execution.

 Prevents inconsistencies

 Ensures isolation (ACID)

 Commonly implemented as 2-phase locking (2PL)

Concurrent execution in a DBMS refers to the capacity to carry out numerous
transactions simultaneously in a shared database. A collection of database
activities known as a transaction, such as inserting, updating, or removing
data, is carried out as a single unit of work. Concurrent execution allows
many transactions to access the same data concurrently, which can have
numerous benefits, such as higher system throughput and reaction time.

Problems with Concurrent Execution in DBMS

In a DBMS, concurrent execution might offer a number of issues that need to

be resolved in order to guarantee accurate and dependable database
operation. Some of the issues with concurrent execution in DBMS include the
following ?

Lost Update

When two or more transactions try to update the same data item at the
same time, a lost update happens, and the outcome relies on the sequence
in which the transactions are executed. The modifications made by the other
transaction will be lost if one transaction overwrites them before they are
committed. Inconsistent data and inaccurate findings might occur from lost
updates.

Dirty Read

When a transaction accesses data that has already been updated but hasn't
been committed, it's known as a dirty read. The information read by the first
transaction will be invalid if the modifying transaction rolls back. Data
discrepancies and inaccurate outcomes might occur from dirty readings.

Non-Repeatable Read

When a transaction reads the same data item twice and the data is updated
by another transaction between the two reads, this is known as a non-
repeatable read. This might result in discrepancies in outcomes and data.

Phantom Read

When a transaction reads a group of rows that meet a given criterion and a
subsequent transaction adds or deletes rows that meet the same
requirement, this is known as a phantom read. The same set of data will
have new rows that were not present the first time when the initial
transaction reads them. Results and data discrepancies may emerge from
this.

Deadlock

In a DBMS, a deadlock happens when many transactions are held up as they

wait for one another to release the resources they are
holding. Deadlocks can happen when resources are not released properly or
are acquired by transactions in a different sequence. Deadlocks can result in
decreased system performance or even system crashes.

Starvation

In a DBMS, starvation happens when one transaction is perpetually blocked

from using a resource or finishing a job because that resource has been
allocated to another transaction. When resources are not equitably
distributed among transactions or when priorities are not correctly
controlled, starvation may result.
Performance of Locking

The performance of locking in databases or concurrent systems refers to

how well a locking mechanism manages concurrent access to shared
resources (tables, rows, files, memory objects) while balancing throughput,
response time, and overhead.

Here’s a breakdown:

🔹 1. Locking Basics

 Locking ensures consistency by preventing conflicting operations

(e.g., two transactions updating the same row).

 But locks also restrict concurrency, so performance depends on how

efficiently locks are managed.

🔹 2. Factors Affecting Locking Performance

1. Granularity of Locks

o Fine-grained locks (e.g., row-level): allow high concurrency but

more overhead in lock management.

o Coarse-grained locks (e.g., table-level): less overhead, but more

blocking.

2. Lock Contention

o Occurs when multiple transactions compete for the same lock.

o High contention → waiting → reduced throughput.

3. Lock Duration

o Long-held locks (due to slow transactions) reduce system

performance.

o Short transactions improve concurrency.

 4. Deadlocks

o When two transactions wait for each other → system must detect
& resolve → adds overhead.

5. Lock Modes

o Shared locks (readers) → allow multiple readers.

o Exclusive locks (writers) → block others → reduce concurrency.

🔹 3. Performance Trade-offs

Aspect Impact of Locking

Decreases if locks are coarse or long-

Concurrency
held

Consistency Ensures correctness of data

Throughput High contention reduces throughput

Latency/Response
Increases when waiting for locks
Time

Fine-grained locks increase CPU &

Overhead
memory cost

🔹 4. Locking Performance Optimizations

 Two-Phase Locking (2PL): Ensures serializability but may cause

deadlocks.

 Optimistic Concurrency Control (OCC): Avoids locks, validates at

commit → good when conflicts are rare.

 Multi-Version Concurrency Control (MVCC): Readers don’t block

writers (used in PostgreSQL, Oracle, MySQL InnoDB).

 Deadlock Detection & Timeout Policies: Quickly resolve blocking

situations.

 Lock Escalation: Dynamically converts many fine-grained locks into

coarser locks to reduce overhead.
2PL (Two-Phase Locking) is a concurrency control protocol used in
DBMS (Database Management Systems) to ensure serializability of
transactions.

It works in two distinct phases:

1. Growing Phase

o A transaction can acquire locks (read/write) on data items.

o No locks can be released in this phase.

2. Shrinking Phase

o Once a transaction releases a lock, it cannot acquire any

new locks.

o Only unlocking is allowed here.

⚖️This ensures that transactions follow a predictable locking pattern,

preventing conflicts and guaranteeing serializable schedules.

✅ Example:

 Transaction T1 wants to read and then update a record.

o It first acquires the lock(s) it needs → Growing Phase.

o After finishing, it releases locks → Shrinking Phase.

🔑 Why 2PL is important?

 Guarantees conflict-serializability.
  Prevents problems like dirty reads, uncommitted data access, and
inconsistent results.

⚠️Drawback:

 Can cause deadlocks (if two transactions wait for each other’s locks).

There are mainly three types of Two-Phase Locking (2PL) protocols,

each with different rules on how locks are released:

1. Basic 2PL

 Follows the growing and shrinking phases strictly.

 Once a lock is released, no new lock can be acquired.

 ✅ Ensures conflict-serializability.

 ❌ Does not guarantee recoverability (may cause cascading

rollbacks).

2. Strict 2PL

 All exclusive (write) locks are held until the transaction commits or
aborts.

 Shared (read) locks may be released earlier.

 ✅ Prevents cascading rollbacks.

 ✅ Guarantees recoverable schedules.

3. Rigorous 2PL

 Both shared (read) and exclusive (write) locks are held until the
transaction commits or aborts.
  No lock is released before the end.

 ✅ Produces strict schedules.

 ✅ Easier for recovery (safe but less concurrency).

📊 Comparison Table

When Locks
Type Advantages Drawbacks
Released

Basic After entering Guarantees conflict- Cascading rollbacks

2PL shrinking phase serializability possible

Strict Write locks at Prevents cascading

Less concurrency
2PL commit/abort only rollbacks

Rigorous All locks at Strongest recoverability Minimum

2PL commit/abort only guarantee concurrency
🔒 Performance of Locking

Locking is a concurrency control technique used to ensure consistency

and isolation of transactions in a multi-user database system.
However, the performance of locking depends on several factors:

✅ Advantages (Good Performance Aspects)

1. Ensures Consistency & Isolation

Prevents conflicts such as lost updates, dirty reads, and uncommitted
data being read.

2. Supports Concurrency
Multiple users can access different parts of the database
simultaneously if locks are managed well.

3. Fairness & Deadlock Prevention (with proper policies)

If lock scheduling and priority rules are set correctly, performance
improves.

⚠️Performance Issues (Drawbacks)

1. Lock Overhead

o Managing locks requires time and memory.

o For every transaction, the DBMS must keep lock tables and check
for conflicts.

2. Reduced Concurrency

o If too many locks are held, other transactions are forced to wait.

o This can lead to low throughput.

 3. Deadlocks

o Two or more transactions waiting for each other’s locks → system

must detect & resolve.

o Deadlock resolution (abort/rollback) reduces performance.

4. Starvation

o Some transactions may keep waiting if high-priority transactions

always get the locks first.

5. Granularity Trade-off

o Fine-grained locks (row-level) → high concurrency but high

overhead.

o Coarse-grained locks (table-level) → low overhead but low

concurrency.

📊 Factors Affecting Locking Performance

1. Locking Granularity

o Row-level locks → better concurrency, slower overhead.

o Table-level locks → less concurrency, faster overhead.

2. Lock Mode

o Shared vs Exclusive locks.

o More exclusive locks → more blocking → less concurrency.

3. Transaction Length

o Longer transactions hold locks for a long time, reducing

concurrency.

4. Deadlock Handling Strategy

o Deadlock prevention (wait-die, wound-wait) vs detection

(timeout, cycle detection).

5. Workload Type

o Read-heavy workload → shared locks scale better.

 o Write-heavy workload → more conflicts, locking reduces
performance.

🚀 Improving Locking Performance

 Use optimistic concurrency control when conflicts are rare.

 Apply row-level locking instead of table-level (if system supports it).

 Use shorter transactions (commit frequently).

 Deadlock detection and resolution strategies.

 Employ multi-version concurrency control (MVCC) to reduce

blocking.

✅ Advantages of Locking

1. Maintains Data Consistency

Prevents problems like lost updates, dirty reads, and uncommitted data
being accessed.

2. Ensures Transaction Isolation (ACID Property)

Each transaction executes as if it is alone in the system.

3. Supports Concurrency

o With shared locks, multiple read operations can proceed

together.

o Allows controlled parallel execution.

4. Granularity Flexibility

o Can lock at different levels (row, page, or table) depending on

need.

o Row-level locks allow high concurrency.

5. Simple to Implement
Locking mechanisms are well-studied and widely implemented in
almost all DBMS.

⚠️Disadvantages of Locking
 1. Performance Overhead

o Managing lock tables, granting/releasing locks requires extra

time and resources.

2. Reduced Concurrency

o If many locks are held, other transactions are forced to wait →

slows down throughput.

3. Deadlocks

o Two or more transactions wait for each other’s locks indefinitely

→ needs detection/resolution.

4. Starvation

o Some transactions may keep waiting if higher-priority

transactions always acquire the locks first.

5. Granularity Trade-off

o Fine-grained locks (row-level): High concurrency, but costly

overhead.

o Coarse-grained locks (table-level): Low overhead, but poor

concurrency.

6. Long Transaction Blocking

o If a transaction takes too long, others remain blocked, reducing

system responsiveness.

🔄 Transaction Support in SQL

A transaction is a sequence of one or more SQL statements that are

executed as a single logical unit of work.
Transactions in SQL are mainly used to ensure data integrity and follow the
ACID properties.

🔑 ACID Properties

1. Atomicity → All operations in a transaction are executed completely or

none at all.
 2. Consistency → Database moves from one consistent state to another.

3. Isolation → Concurrent transactions do not interfere with each other.

4. Durability → Once a transaction is committed, the changes are

permanent.

🛠 SQL Commands for Transactions

1. START TRANSACTION / BEGIN TRANSACTION

Marks the beginning of a transaction.

2. BEGIN TRANSACTION;

3. COMMIT
Saves all the changes made in the current transaction permanently.

4. COMMIT;

5. ROLLBACK
Undoes all the changes made in the current transaction (restores
database to the last committed state).

6. ROLLBACK;

7. SAVEPOINT
Sets a point within a transaction to which you can roll back without
affecting the entire transaction.

8. SAVEPOINT sp1;

9. ROLLBACK TO SAVEPOINT
Rolls back to a specific savepoint instead of the beginning.

10. ROLLBACK TO sp1;

11. SET TRANSACTION

Defines transaction characteristics like isolation level.

12. SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

📌 Example: Bank Transaction

Suppose a user transfers ₹500 from Account A to Account B:

BEGIN TRANSACTION;
UPDATE Accounts SET balance = balance - 500 WHERE acc_id = 'A';

UPDATE Accounts SET balance = balance + 500 WHERE acc_id = 'B';

COMMIT;

 If both statements succeed → COMMIT saves changes.

 If one fails (e.g., insufficient balance) → ROLLBACK cancels changes.

⚠️Without Transactions

If we didn’t use transactions, money could be deducted from A but not

credited to B, leaving the system inconsistent.

💥 Crash Recovery in DBMS

🔎 What is Crash Recovery?

Crash Recovery is the process of restoring the database to a consistent

state after a failure (like system crash, power failure, or software error).

Since databases must ensure ACID properties, especially Atomicity and

Durability, recovery mechanisms are needed when failures occur.

⚠️Types of Failures That Require Recovery

1. Transaction Failure

o Example: Division by zero, logical error, or transaction abort.

2. System Crash

o Example: Power failure, OS crash, or hardware malfunction.

3. Disk Failure

o Example: Head crash, unreadable sectors, complete disk

corruption.
 4. Media Failure

o Example: Permanent data loss due to disk crash or fire.

🎯 Goals of Crash Recovery

 Ensure Atomicity → either the whole transaction happens or none of

it.

 Ensure Durability → once a transaction is committed, it must not be

lost.

 Restore the database to the last consistent state.

 Minimize data loss and downtime.

🛠 Crash Recovery Techniques

1. Backup & Restore

o Periodic database backups are stored.

o On crash → restore last backup + apply redo logs.

2. Logging (Write-Ahead Logging – WAL)

o Every transaction’s changes are written to a log file before

being applied to the database.

o Log contains info for UNDO (for uncommitted transactions) and

REDO (for committed transactions).

3. Checkpoints

o A checkpoint is a snapshot of the database at a particular time.

o It reduces recovery time by marking a safe point from which

recovery can begin.

4. Deferred Update (No-Undo/Redo)

o Changes are applied to the database only after commit.

o If crash occurs before commit → nothing to undo.

5. Immediate Update (Undo/Redo)

 o Changes are applied immediately to the database, but logs are
kept.

o If crash occurs:

 Undo incomplete transactions.

 Redo committed ones.

📊 Recovery Example

Suppose transaction T1 transfers ₹500 from A to B:

1. T1 starts → log entry created.

2. A’s balance reduced → log entry stored.

3. B’s balance increased → log entry stored.

4. If crash occurs before commit → UNDO changes.

5. If crash occurs after commit → REDO changes from log.

✅ In short:
Crash recovery in DBMS is about restoring the system to a consistent state
after a failure, using techniques like logs, backups, checkpoints, and
undo/redo operations.

🔒 Two-Phase Locking (2PL) and 💥 Crash Recovery

1️⃣ Role of 2PL

 Two-Phase Locking (2PL) is a concurrency control protocol.

 It ensures conflict-serializability, meaning the concurrent execution

of transactions produces the same result as some serial execution.

👉 But 2PL does not guarantee recoverability by itself. If a crash occurs,

we also need recovery mechanisms.

2️⃣ Crash Recovery Basics

  When a crash happens, some transactions may be:

o Committed → must persist (REDO).

o Uncommitted → must be rolled back (UNDO).

 Recovery uses logs (Write-Ahead Logging – WAL) and

checkpoints.

3️⃣ Combining 2PL with Recovery

To ensure both serializability + recoverability, DBMS often uses Strict

2PL.

🔹 Strict 2PL

 Exclusive locks are held until COMMIT/ROLLBACK.

 This prevents other transactions from reading or writing uncommitted

data.

 If a crash happens:

o Committed transactions → REDO using logs.

o Uncommitted transactions → UNDO (no other transaction has

seen their effects).

 Result: Avoids cascading rollbacks and simplifies recovery.

4️⃣ Example: Transaction with 2PL + Crash Recovery

Let’s say:

 T1: Transfer ₹500 from A to B

 T2: Check balance of B

Case without Strict 2PL:

 T1 writes new balance of B, but hasn’t committed.

 T2 reads B’s value → if system crashes, T2 has seen an uncommitted

value → leads to inconsistency.

Case with Strict 2PL:

  T1 holds the exclusive lock on B until commit.

 T2 cannot read B’s value until T1 commits/rolls back.

 If crash occurs → recovery just UNDOs T1 (no cascading rollback

needed).

5️⃣ Why 2PL + Recovery Go Together

 2PL ensures serializability (correctness of concurrent schedules).

 Strict 2PL ensures recoverability (no dirty reads, no cascading

rollbacks).

 Crash Recovery ensures atomicity + durability (using undo/redo

logs).

✅ In short:

 2PL handles concurrency control.

 Strict 2PL ensures safe recovery.

 Crash Recovery restores the database after failures.

👉 Together, they guarantee ACID properties.

🔒 Introduction to Lock Management

🔑 What is Lock Management?

 In a multi-user database system, many transactions may access

the same data item at the same time.

 To ensure isolation (one of the ACID properties), DBMS uses locks.

 Lock Management refers to the mechanism of granting,

maintaining, and releasing locks so that transactions can execute
safely and concurrently without violating consistency.

📌 Why Locks are Needed?

Without locks:

 Two transactions may read and write the same data item
simultaneously.

 This can lead to lost updates, dirty reads, or inconsistent results.

Locks prevent such problems by controlling concurrent access.

📌 Types of Locks

1. Shared Lock (S-Lock):

o Allows multiple transactions to read a data item.

o No transaction can write while shared locks exist.

2. Exclusive Lock (X-Lock):

o Allows a transaction to read and write the data item.

o No other transaction can access it until the lock is released.

📌 Lock Granularity

Locks can be applied at different levels:

 Database-level lock → Entire DB locked (lowest concurrency, lowest

overhead).

 Table-level lock → Locks one table.

 Page/Block-level lock → Locks one disk block.

 Row-level lock → Locks a single tuple (highest concurrency, but more

overhead).

👉 Trade-off: Fine-grained locks = better concurrency but higher overhead.

📌 Lock Manager

The Lock Manager is a DBMS component that:

 Maintains a lock table in memory.

 Keeps records of:

 o Data item identifier

o Lock type (shared/exclusive)

o Transaction(s) holding the lock

o Queue of waiting transactions

 Ensures rules of compatibility matrix (e.g., multiple shared locks are

allowed, but shared + exclusive is not).

📊 Lock Compatibility Matrix

Request \ Exclusive
Shared (S)
Held (X)

Shared (S) ✅ Allowed ❌ Not Allowed

Exclusive
❌ Not Allowed ❌ Not Allowed
(X)

📌 Problems in Lock Management

1. Deadlocks – two or more transactions wait for each other’s locks.

2. Starvation – some transactions keep waiting indefinitely.

3. Overhead – managing locks consumes memory and CPU.

(DBMS handles these with deadlock prevention, detection, and

recovery policies).

✅ In summary:
Lock Management is the heart of concurrency control in DBMS. It uses
shared and exclusive locks, applied at different granularities, and is
controlled by a lock manager that maintains a lock table.

🛠 Strategies for Dealing with Deadlocks

There are three main approaches:

1️⃣ Deadlock Prevention (Proactive)

  Goal: Ensure deadlocks never occur by controlling the way locks are
requested.

 Techniques:

1. Wait-Die Scheme

 Older transaction waits, younger aborts.

2. Wound-Wait Scheme

 Older transaction aborts the younger transaction holding

the lock.

3. Pre-allocation (Conservative 2PL)

 Transaction requests all needed locks at the start.

 ✅ Advantage: Deadlocks are avoided completely.

 ❌ Disadvantage: Can reduce concurrency.

2️⃣ Deadlock Avoidance

 Goal: Decide at runtime whether granting a lock will cause deadlock.

 Techniques:

o Wait-for Graph: Graph shows which transactions are waiting for

which resources.

o Cycle Detection: If granting a lock creates a cycle → don’t grant

the lock.

 ✅ Advantage: Higher concurrency than prevention.

 ❌ Disadvantage: Needs runtime monitoring and overhead.

3️⃣ Deadlock Detection and Recovery (Reactive)

 Goal: Let deadlocks occur but detect and resolve them.

 Steps:

1. Periodically check for cycles in the wait-for graph.

 2. If cycle detected → choose a victim transaction to abort (based
on cost or priority).

3. Release its locks → allow other transactions to continue.

 ✅ Advantage: Good concurrency, simple to implement.

 ❌ Disadvantage: Some transactions may need to be rolled back.

⚡ Deadlock vs Starvation

Aspect Deadlock Starvation

Transaction waits too long due to

Cause Cyclic waiting for resources
priority/fairness

Detectio Wait-for graph / cycle

Can’t be directly detected
n detection

Abort one transaction /

Solution Fair scheduling policies
prevention

📌 Summary

 Deadlock = cyclic waiting → indefinite blocking.

 Dealing with deadlocks:

1. Prevention → never allow deadlocks.

2. Avoidance → grant locks only if safe.

3. Detection & Recovery → detect deadlocks, abort victim

transactions.
Memory Hierarchy

1. Levels of Storage in DBMS

DBMS usually manages storage at different levels:

1. Primary Storage (Main Memory / RAM)

o Very fast, but volatile (data is lost when power goes off).

o Used for cache, buffer management, query processing.

2. Secondary Storage (Disk / SSD)

o Non-volatile (data persists).

o Main place for storing database files, indexes, logs.

o Cheaper and larger than RAM.

3. Tertiary Storage (Backup Storage)

o Magnetic tapes, cloud storage, archival disks.

 o Used for backups and disaster recovery.

In DBMS, the data on external storage refers to all the database files
and related data that are physically stored on secondary storage
devices (like hard disks, SSDs, or other non-volatile media).
These files hold the actual data, indexes, logs, and other information
needed for the database to function.

Let’s understand it in detail 👇

🔹 What Is “Data on External Storage”?

It means the persistent data that a DBMS keeps outside the main
memory (RAM) — on devices like hard disks or cloud storage — so that
it remains available even after power is off.

🔹 Types of Data Stored Externally

Type of File Description Example

Contain actual database tables — Student, Employee,

Data Files
rows and columns of user data. Orders tables

Contain indexes that speed up B+ Tree or Hash Index

Index Files
search and retrieval. on Student_ID

Store transaction logs for recovery Write-Ahead Log

Log Files
and rollback. (WAL)

Data
Metadata — info about tables,
Dictionary / Schema details
columns, constraints, users, etc.
Catalog

Temporary Used for sorting, joins, or temporary

TempDB, sort areas
Files results during queries.

Copies of database data for recovery

Backup Files .bak or .dump files
purposes.
🔹 How DBMS Accesses Data on External Storage

1. Data is stored in blocks or pages on disk.

2. When a query is executed, the Storage Manager and Buffer

Manager:

o Locate the required block on disk

o Read (fetch) it into main memory (buffer)

o Process it

o Write back updates to disk if needed

3. Access is managed through I/O operations, which are slower than

memory access.

🔹 Example

Suppose you have a table:

CREATE TABLE Student (

ID INT,

Name VARCHAR(50),

Marks INT

);

When data is inserted:

INSERT INTO Student VALUES (1, 'Raj', 85);

➡️This record is stored in a data file (e.g., student_data.dbf) on external

storage (hard disk).
When you query it:

SELECT * FROM Student WHERE ID = 1;

➡️DBMS reads the relevant page from disk into memory, processes it,
and returns the result.
🔹 Key Components Involved

 Storage Manager – controls how data is stored and retrieved.

 File Manager – manages physical files on disk.

 Buffer Manager – handles temporary storage in main memory.

🧠 Summary

Feature Description

Hard disk, SSD, or other non-volatile

Where stored
device

Why stored
Too large for RAM; needs persistence
externally

Tables, indexes, logs, metadata,

Data examples
backups

Through storage manager and I/O

Access method
operations

Data Stored on External Storage in DBMS

In DBMS, external storage means the non-volatile storage outside the

main memory (RAM), where large amounts of data are kept permanently.

Since main memory is small and volatile (data is lost when power goes off),
DBMS stores almost all persistent data on external storage.

🔹 What is External Storage?

 Definition: External storage refers to secondary storage devices

(like hard disks, SSDs) and sometimes tertiary storage (like magnetic
tapes, cloud storage), where the database files, indexes, and logs are
kept.

 It is “external” relative to the DBMS’s main memory.

 Characteristics:
 o Non-volatile → data persists even after power failure.

o Much larger capacity than RAM.

o Slower access compared to main memory.

o Organized into blocks (pages), which are transferred into main

memory when needed.

🔹 Examples of External Storage in DBMS

1. Hard Disks (HDDs)

o Traditional secondary storage, widely used.

o Stores tables, indexes, metadata, logs.

2. Solid-State Drives (SSDs)

o Faster random access than HDDs.

o Common in modern DBMS.

3. Magnetic Tapes / Cloud Storage (Tertiary)

o Used for backup & archival.

🔹 How Data is Stored on External Storage

DBMS doesn’t directly store rows one by one. Instead:

1. Data is stored in files.

2. Files are divided into fixed-size blocks/pages (e.g., 4 KB, 8 KB).

3. Blocks are read/written between disk and memory.

4. Inside a block → records (tuples) are stored.

🔹 Types of Data Stored Externally

 Database tables (actual data)

 Indexes (for fast access, e.g., B+ Tree, Hash)

 System catalog (metadata)

  Transaction logs (for crash recovery)

 Backups / archived data

✅ Summary

 External storage = non-volatile storage (mainly disks/SSDs) where

DBMS keeps data permanently.

 Needed because RAM is too small and temporary.

 DBMS organizes data in files → blocks → records.

 Includes tables, indexes, metadata, logs, backups.

Types of External Storage in DBMS

In DBMS, external storage means non-volatile storage outside the main

memory (RAM). It is where the database is permanently stored.

There are mainly three categories of external storage:

🔹 1. Secondary Storage

 This is the main place where DBMS stores data.

 Large capacity, cheaper than RAM, non-volatile.

 Used for tables, indexes, metadata, and logs.

 Examples:

o Magnetic Disks (HDDs) → traditional, block-structured storage.

o Solid State Drives (SSDs) → faster random access, widely

used in modern DBMS.
🔹 2. Tertiary Storage

 Slower, cheaper, very high capacity.

 Mainly used for backup and archival, not for day-to-day DBMS
operations.

 Data access is sequential.

 Examples:

o Magnetic tapes

o Optical disks (CD/DVD/Blu-ray)

o Cloud archival storage

🔹 3. RAID-based Storage Systems

 RAID = Redundant Array of Independent Disks.

 Uses multiple disks together for performance + fault tolerance.

 Data is stored in a combination of:

o Striping (RAID 0) → performance

o Mirroring (RAID 1) → reliability

o Parity (RAID 5/6) → balance of both

RAID itself uses secondary storage devices (disks/SSDs) but organizes

them for efficiency and safety.

📌 Summary Table

Type Purpose in DBMS Examples

Main storage for DBMS

Secondary HDDs, SSDs
data

Magnetic tapes, optical, cloud

Tertiary Backup, archival storage
archival

RAID Reliable + fast storage

RAID 0, RAID 1, RAID 5, RAID 10
Systems system
✅ Final Answer:
The types of external storage in DBMS are:

1. Secondary storage (HDD, SSD)

2. Tertiary storage (tapes, optical disks, cloud backup)

3. RAID-based storage systems (multiple disks for

reliability/performance)

1. Internal Storage in DBMS

 Definition:
Data stored inside the computer’s primary memory (RAM) or
cache.
It is directly accessible by the CPU without needing Input/Output
operations.

 Characteristics:

o Very fast access (nanoseconds).

o Volatile → data is lost when power goes off.

o Used for temporary data during query execution, sorting, joins,

etc.

o Limited in size compared to external storage.

 Examples in DBMS:

o Buffer pool (RAM area where DBMS loads disk pages).

o Temporary tables stored in main memory.

o Index pages or frequently accessed rows cached in memory.

2. External Storage in DBMS

 Definition:
Data stored on secondary storage devices like hard disks, SSDs,
 magnetic tapes, RAID systems, or cloud storage.
DBMS uses disk I/O operations to access this data.

 Characteristics:

o Much slower than internal storage (milliseconds).

o Non-volatile → data persists even after power loss.

o Provides very large capacity.

o Used for long-term storage of databases.

 Examples in DBMS:

o Database files stored on disk.

o Tables, indexes, logs, backups on HDD/SSD.

o RAID arrays used for performance + fault tolerance.

Key Differences

Internal Storage (Main External Storage (Secondary

Aspect
Memory) Storage)

Speed Very fast (nanoseconds) Slower (milliseconds)

Volatility Volatile (lost if power off) Non-volatile (persistent)

Capacity Small & limited Very large

Usage in Temporary execution data, Permanent storage of DB,

DBMS buffers indexes, logs

Access
Direct CPU access Needs I/O operations
Method

✅ In short:

 Internal storage = temporary + fast + volatile (RAM).

 External storage = permanent + large + non-volatile (disk/RAID).

External Storage in DBMS

1. Definition

External storage refers to the secondary or auxiliary storage devices

where the actual database is permanently stored.
Unlike internal storage (RAM), it is non-volatile → data is not lost when
the power goes off.

Examples:

 Hard Disk Drives (HDDs)

 Solid State Drives (SSDs)

 Magnetic tapes (for backups/archives)

 Optical disks (CD/DVD)

 RAID systems (Redundant Array of Independent Disks)

 Cloud storage

2. Characteristics

 Non-volatile: Data persists even without power.

 Large capacity: Can store terabytes or petabytes of data.

 Slower access: Compared to RAM (requires I/O operations).

 Cheaper cost per GB compared to main memory.

 Bulk storage: Entire databases, tables, indexes, logs, and backups

are stored here.

3. Role in DBMS

In a DBMS, external storage is used for:

 Storing tables, records, and indexes.

 Transaction logs (for crash recovery).

 Database backups & snapshots.

 Archival of old or rarely used data.

4. Types of External Storage in DBMS

(a) Magnetic Disks (HDDs)

 Most common for databases.

 Data stored in blocks (pages).

 Access methods: Sequential access & direct/random access.

 Example: Database files stored on a server’s hard disk.

(b) Solid State Drives (SSDs)

 Faster than HDD (no moving parts).

 Used for high-performance databases.

 More expensive but reduces I/O bottlenecks.

(c) Magnetic Tapes

 Cheap, very high capacity.

 Sequential access only (slow).

 Used for backup & archival, not active databases.

(d) RAID (Redundant Array of Independent Disks)

 A system of multiple disks working together.

 Provides fault tolerance (data redundancy) + performance

improvement.

 RAID Levels:

o RAID 0 → Striping (fast, no redundancy).

o RAID 1 → Mirroring (redundancy, slower).

o RAID 5/6/10 → Combination of speed + redundancy.

(e) Cloud Storage

  External storage provided over the internet (AWS S3, Azure Blob,
Google Cloud Storage).

 Scalable & managed by third-party providers.

 Used for distributed DBMS and big data.

5. File Organization on External Storage

DBMS organizes external storage into files and pages:

 Heap file organization → records stored in any order.

 Sequential file organization → sorted records.

 Hashing & Indexing (B+ Trees) → fast access to records.

✅ In short:
External storage in DBMS = where all the actual database lives
(HDD/SSD/RAID/cloud).
It is permanent, non-volatile, large, but slower than RAM.
1. File Organization in DBMS

File organization defines how records (data) are stored on storage

devices (like hard disks). The way records are placed affects how efficiently
data can be retrieved, inserted, or deleted.

Types of File Organizations:

1. Heap (Unordered) File Organization

o Records are stored in random order as they arrive.

o New record → simply placed in the first available block.

o Searching may require scanning the entire file.

o ✅ Advantage: Easy to insert.

o ❌ Disadvantage: Very slow search.

2. Sequential (Ordered) File Organization

o Records are stored in sorted order (based on a key field).

o Searching is faster using binary search.

o Useful for range queries.

o ✅ Advantage: Good for sequential access and range queries.

 o ❌ Disadvantage: Insertion & deletion are expensive (need
reordering).

3. Hashing File Organization

o Uses a hash function to determine record placement.

o Directly calculates the block address for a given key.

o ✅ Advantage: Very fast search (O(1)).

o ❌ Disadvantage: Collisions may occur, not efficient for range

queries.

4. Clustered File Organization

o Records that are frequently accessed together are stored

together (based on some clustering key).

o Reduces number of disk I/Os.

o ✅ Advantage: Efficient for related data queries.

o ❌ Disadvantage: Costly maintenance when data changes.

2. Indexing in DBMS

Indexing is like a book index – it helps to quickly locate data without

scanning the whole file.

Types of Indexes:

1. Primary Index

o Created on a primary key field.

o Records are ordered based on this key.

o Example: Index on EmployeeID in Employee table.

2. Secondary Index

o Created on non-primary attributes.

o Useful for searching by fields other than the primary key.

 o Example: Index on EmployeeName.

3. Clustered Index

o Determines the physical order of records in the table.

o Only one clustered index per table.

4. Non-Clustered Index

o Does not affect the physical order of records.

o Stores pointers to the data instead.

o Multiple non-clustered indexes can exist.

Indexing Methods:

 Dense Index: Every search-key value has an entry in the index.

 Sparse Index: Only some search-key values are indexed (saves

space).

 Multilevel Index: Index on an index to speed up access.

 B+ Tree Index: Widely used in databases, supports efficient search,

insertion, deletion, and range queries.

 Hash Index: Uses hashing, best for exact-match queries.

✅ In short:

 File Organization → How data is physically stored.

 Indexing → How to speed up searching in those files.

1. Primary Index

 Built on the primary key of a table.

 Records are stored in sorted order of the primary key.

 Each data block has an entry in the index, pointing to the location of
the first record in that block.

 Example: If a table has a primary key Roll_No, the primary index is

created on Roll_No.

2. Secondary Index

 Created on non-primary key attributes (candidate keys or other

fields).

 Useful for searching based on fields other than the primary key.

 May not be unique, so multiple entries can point to the same record.

 Example: Creating an index on Name in a student table when Roll_No

is the primary key.

3. Clustering Index

 Used when records are physically stored in sorted order on a

non-key attribute (called the clustering field).
  One index entry points to a block of records, not individual records.

 Example: Students stored in order of Department. All students of the

same department are stored together.

4. Dense Index

 Has an index entry for every search key value in the data file.

 Provides faster access since every record is directly mapped.

 Requires more space because the index is large.

 Example: Every Roll_No in a student table has an entry in the index.

5. Sparse Index

 Has index entries for only some search key values.

 An entry points to the first record in a block, and the search

continues sequentially in that block.

 Saves space but is slower than dense index.

 Example: Indexing every 10th student record in a sorted file.

6. Multilevel Index

 Index on top of another index (like a hierarchy).

 The first-level index may itself be large, so a second-level index is built

on it, and so on.

 Reduces the number of I/O operations.

 Similar to how a B+ Tree works.

7. B-Tree Index

 Balanced tree structure.

 Nodes contain keys and pointers.

 Provides efficient searching, insertion, and deletion.

  Ensures logarithmic search time.

8. B+ Tree Index

 Variation of B-Tree, widely used in DBMS.

 Internal nodes store keys, leaf nodes store actual data pointers.

 All leaf nodes are linked (supports range queries efficiently).

 Preferred over B-Tree in databases.

✅ Summary Table

Type Key Feature

Primary Index Built on primary key

Secondary
Built on non-primary fields
Index

Clustering
Records grouped by non-key attribute
Index

Dense Index Entry for every record

Sparse Index Entry for some records only

Multilevel
Index of indexes
Index

B-Tree Index Balanced tree structure

Tree with linked leaves, supports range

B+ Tree Index
queries

Do you want me to also make a diagram-based explanation (with visuals

of dense, sparse, B-tree, and B+ tree indexes) so it’s easier to understand?

You said:

explain with examples

ChatGPT said:
Perfect 👍 Let’s go step by step with examples for each type of indexing. I’ll
use a simple Student Table example:

🎓 Example Student Table

Roll_No Nam Dep Mark

(PK) e t s

101 Ankit CSE 85

102 Riya ECE 90

Moha
103 CSE 78
n

104 Neha ME 92

105 Sita CSE 88

1. Primary Index

 Built automatically on primary key (Roll_No).

 Records are sorted by Roll_No.

🔹 Index Table:

Roll_N Pointer to
o record

101 → Record 101

102 → Record 102

103 → Record 103

104 → Record 104

105 → Record 105

👉 Searching for Roll_No = 104 is direct because it’s indexed.

2. Secondary Index
  Suppose we want to search by Name.

 Create index on Name.

🔹 Index Table:

Nam Pointer to
e record

Ankit → 101

Moha
→ 103
n

Neha → 104

Riya → 102

Sita → 105

👉 Now we can search quickly by Name, even though it’s not primary.

3. Clustering Index

 Suppose records are physically stored grouped by Dept.

🔹 Index Table:

Dep Pointer to first

t record

CSE → Roll_No 101

ECE → Roll_No 102

ME → Roll_No 104

👉 All CSE students (101, 103, 105) are stored together → faster group
queries.

4. Dense Index

 Index for every record.

🔹 Index Table (on Marks):

Mark Point
s er

78 → 103

85 → 101

88 → 105

90 → 102

92 → 104

👉 Searching Marks = 88 directly takes us to Roll_No 105.

5. Sparse Index

 Index only some records, e.g., every 2nd record.

🔹 Index Table (on Roll_No):

Roll_N Point
o er

101 → 101

103 → 103

105 → 105

👉 Searching Roll_No = 104 → first check 103, then scan sequentially → 104.

6. Multilevel Index

 If primary index is too large, build index on index.

Example:

 Level 1 Index: Points to chunks of Roll_No.

 Level 2 Index: Inside chunk.

🔹 Level 1:

Roll_No Point
Range er
101–103 → L2A

104–105 → L2B

🔹 Level 2 (L2A):

Roll_N Point
o er

101 → 101

102 → 102

103 → 103

👉 Searching Roll_No = 102 → L1 directs to L2A, then L2A to record.

7. B-Tree Index

 Keys are stored in a balanced tree structure.

Example: B-Tree for Roll_No

[103]

/ \

[101,102] [104,105]

👉 Searching 104 → Start at root (103), go right, find 104.

8. B+ Tree Index

 Like B-Tree but all data in leaf nodes, and leaf nodes are linked for
fast range queries.

Example: B+ Tree for Roll_No

[103]

/ \

[101,102] [104,105]

| | | |

→ → → →
👉 Searching 101–105 is efficient because leaves are linked.

✅ Quick Recap with Uses

 Primary Index → Fast search by primary key.

 Secondary Index → Fast search by non-key fields.

 Clustering Index → Efficient for grouped queries.

 Dense Index → Faster but larger index size.

🌳 B-Tree (Balanced Tree) — Introduction with Example

🔹 Definition

A B-Tree is a self-balancing search tree used to store large amounts of

sorted data.
It ensures:

 Fast search, insertion, and deletion.

 Minimal disk access (important for databases).

 All leaf nodes stay at the same level (balanced).

🔹 Basic Rules of a B-Tree of Order m

If the order of the B-Tree is m:

 Each node can have at most (m – 1) keys.

 Each node can have at most m children.

 Each node (except root) must have at least ⌈m/2⌉ children.

 All keys within a node are stored in sorted order.

 The root must have at least 1 key.

🔹 Example: Constructing a B-Tree of Order 3

That means:

 Each node can have 2 keys maximum.

  Each node can have 3 children maximum.

Let’s insert these keys one by one:

👉 Keys to insert: 10, 20, 5, 6, 12, 30, 7, 17

🔸 Step 1: Insert 10

Tree is empty → create a root node.

[10]

🔸 Step 2: Insert 20

Add 20 in sorted order.

[10 | 20]

✅ Node not full yet (2 keys max).

🔸 Step 3: Insert 5

Now inserting 5 → [5 | 10 | 20]

⚠ Node overflow! (3 keys > 2 allowed)

➡ Split the node around the middle key (10).

10 becomes the new root.

[10]

/ \

[5] [20]

🔸 Step 4: Insert 6

6 < 10 → goes to left child [5]

Insert 6 → [5 | 6]

[10]

/ \

[5 | 6] [20]
🔸 Step 5: Insert 12

12 > 10 → goes to right child [20]

Insert 12 → [12 | 20]

[10]

/ \

[5 | 6] [12 | 20]

🔸 Step 6: Insert 30

30 > 10 → right child [12 | 20]

Insert 30 → [12 | 20 | 30] → Overflow!
Split around 20.

[10 | 20]

/ | \

[5 | 6] [12] [30]

🔸 Step 7: Insert 7

7 < 10 → goes to [5 | 6]
Insert 7 → [5 | 6 | 7] → Overflow!
Split around 6.

[10 | 20]

/ | \

[5] [7 | 12] [30]

✅ Balanced B-Tree maintained.

🔸 Step 8: Insert 17

17 lies between 10 and 20 → goes to middle child [7 | 12]

Insert 17 → [7 | 12 | 17] → Overflow! Split around 12.

[10 | 12 | 20]
 / | | \

[5] [7] [17] [30]

✅ Final B-Tree of order 3 after all insertions.

🔹 Final B-Tree Structure

[10 | 12 | 20]

/ | | \

[5] [7] [17] [30]

🔹 Key Features Observed

 All leaf nodes are at the same level.

 The tree stays balanced after every insertion.

 Search, insertion, and deletion all take O(log n) time.

🔹 Real-World Use

 Database Indexes (e.g., MySQL, Oracle)

 File Systems (e.g., NTFS, HFS+)

 Search Engines

✅ Best Practices for Index Tuning:

1. Index Frequently Queried Columns

o Use indexes on columns in WHERE, JOIN, ORDER BY, or

GROUP BY.

o Example:

o SELECT * FROM orders WHERE customer_id = 101;

→ Create index on customer_id.

2. Avoid Over-Indexing

o Too many indexes slow down data modification.

 o Only keep indexes that are actively used by queries.

3. Use Composite Indexes Wisely

o Example:
(customer_id, order_date) is better than creating two separate
indexes if they’re often used together.

4. Use the Query Execution Plan

o Tools like EXPLAIN (MySQL, PostgreSQL) show whether the DBMS

is using your index.

o Helps find unused or missing indexes.

5. Rebuild and Reorganize Indexes

o Over time, indexes can become fragmented, slowing

performance.

o Rebuilding restores efficiency.

6. Index Selective Columns

o High selectivity = column with many unique values.

o Avoid indexing low-selectivity columns (e.g., gender, is_active).

7. Index Foreign Keys

o Improves performance of JOINs and referential integrity

checks.

🔹 5. Example: Performance Before and After Indexing

Without Index:

SELECT * FROM employees WHERE emp_name = 'Ravi';

→ DBMS checks every record (Full Table Scan).

Slow for large tables.

With Index:

CREATE INDEX idx_emp_name ON employees(emp_name);

→ DBMS uses index lookup to directly find 'Ravi'.

Much faster.
🔹 6. Drawbacks of Indexes

 Extra space on disk.

 Slower writes (insert/update/delete).

 Maintenance cost when data changes frequently.

🔹 7. Tools and Techniques for Performance Tuning

 EXPLAIN / EXPLAIN ANALYZE: Shows query execution plan.

 Database Profiler: Tracks slow queries.

 Index Rebuilding: Defragment indexes regularly.

 Query Optimization: Rewrite inefficient queries.

 Partitioning: Split large tables to improve index efficiency.

Guidelines for Index Selection in DBMS (Database Management

Systems) — these help in choosing the right type and number of indexes to
improve query performance while minimizing overhead.

🔹 1. Analyze Query Patterns

 Create indexes based on the most frequently executed queries.

 Focus on columns used in:

o WHERE conditions

o JOIN conditions

o ORDER BY or GROUP BY clauses

 Example:

 SELECT * FROM students WHERE student_id = 101;

→ Index on student_id improves performance.

🔹 2. Choose a Suitable Index Type

 Primary Index: On primary key (unique, sorted).

 Clustered Index: When records are frequently retrieved in sorted

order.

 Secondary Index: For non-key attributes used in search conditions.

 Composite Index: When multiple columns are often used together in

queries.
Example:

 SELECT * FROM orders WHERE customer_id = 12 AND order_date =

'2025-10-13';

→ Composite index on (customer_id, order_date) helps.

🔹 3. Avoid Excessive Indexing

 Too many indexes slow down INSERT, UPDATE, DELETE operations

because all indexes must also be updated.

 Create indexes only when read performance is more critical than

write performance.

🔹 4. Index Selective Columns

 Choose columns with high selectivity (many unique values).

 Avoid indexing columns with few distinct values (e.g., gender, status).

🔹 5. Use Clustered Index for Range Queries

 Clustered indexes are ideal for range-based searches:

 SELECT * FROM employees WHERE salary BETWEEN 50000 AND

100000;

→ Clustered index on salary improves performance.

🔹 6. Keep Index Keys Small

 Smaller index keys = faster search and less storage space.

 Avoid indexing long text fields (VARCHAR(255), TEXT, etc.).

🔹 7. Monitor and Tune Regularly

 Use query execution plans to identify missing or unused indexes.

 Periodically rebuild or reorganize indexes to maintain efficiency.

🔹 8. Index Foreign Keys

 Always index foreign key columns to speed up JOIN operations and

referential integrity checks.

🔹 9. Consider Composite Index Order

 Place the most selective column first in a composite index.

Example:
(city, last_name) is better than (last_name, city) if city has many
distinct values.

🔹 10. Avoid Redundant Indexes

 Do not create multiple indexes on the same column or combinations

already covered by a composite index.

📘 Basic Examples of Index Selection

Index selection means choosing the right columns and index types to
improve query performance without adding unnecessary overhead.

🔹 Example 1: Searching by Primary Key

Table: students(student_id, name, age, city)

Query:

SELECT * FROM students WHERE student_id = 105;

✅ Best Index:

 Primary Index on student_id (automatically created if it’s a PRIMARY

KEY).

📈 Reason:
student_id is unique and used to identify each record → perfect for primary
index.

🔹 Example 2: Searching by Non-Key Column

Query:

SELECT * FROM students WHERE name = 'Priya';

✅ Best Index:

CREATE INDEX idx_name ON students(name);

📈 Reason:
name is not the primary key but used often in search → secondary index
helps speed up lookups.

🔹 Example 3: Range Search

Query:

SELECT * FROM employees WHERE salary BETWEEN 50000 AND 100000;

✅ Best Index:

CREATE CLUSTERED INDEX idx_salary ON employees(salary);

📈 Reason:
Clustered index keeps records physically sorted by salary → ideal for
range queries.

🔹 Example 4: Multiple Columns in WHERE Clause

Query:
SELECT * FROM orders WHERE customer_id = 200 AND order_date = '2025-
10-13';

✅ Best Index:

CREATE INDEX idx_cust_orderdate ON orders(customer_id, order_date);

📈 Reason:
A composite index on both columns improves performance when both are
used together in searches.

🔹 Example 5: Sorting or Grouping

Query:

SELECT * FROM sales ORDER BY sale_date;

✅ Best Index:

CREATE INDEX idx_sale_date ON sales(sale_date);

📈 Reason:
Index on sale_date allows the DBMS to fetch data in sorted order — no need
for extra sorting.

🔹 Example 6: Joining Two Tables

Tables:
orders(order_id, customer_id, amount)
customers(customer_id, name)

Query:

SELECT o.order_id, [Link]

FROM orders o

JOIN customers c ON o.customer_id = c.customer_id;

✅ Best Indexes:

CREATE INDEX idx_orders_customerid ON orders(customer_id);

CREATE INDEX idx_customers_customerid ON customers(customer_id);

📈 Reason:
Indexes on foreign key columns (customer_id) speed up JOIN operations.

🔹 Example 7: Avoid Index on Low-Selectivity Column

Query:

SELECT * FROM students WHERE gender = 'F';

🚫 Avoid Index Here

📉 Reason:
gender has very few distinct values (e.g., M/F) → indexing won’t help much.
DBMS still scans most of the table.

🔹 Example 8: Text Columns

Query:

SELECT * FROM articles WHERE title LIKE 'Database%';

✅ Best Index:

CREATE INDEX idx_title ON articles(title);

📈 Reason:
Index helps when the pattern starts with a fixed prefix ('Database%'), not
when it starts with %.

✅ Summary Table

Best Index
Query Type Example Column
Type

Search by primary
Primary Index student_id
key

Search by non-key
Secondary Index name
field

Range query Clustered Index salary

Multiple conditions Composite Index (customer_id,

 order_date)

Sorting / Grouping Single Index sale_date

Index on Foreign
Join operations customer_id
Key