Deadlock: Explanation, Prevention, Detection, and Starvation

1. What is Deadlock?

Deadlock is a condition in a database system (or operating system) where no process proceeds for execution and each process waits for resources that have been acquired by other processes. In other words, a set of transactions are permanently blocked, each waiting for another to release a lock, and none can proceed.

"Deadlock is a condition where no process proceeds for execution and each waits for resources that have been acquired by the other processes."

Example of Deadlock

Consider two transactions T1 and T2, and two data items X and Y:

• T1 holds X and waits for Y.
• T2 holds Y and waits for X.
• Neither can proceed. This is a deadlock.

2. Deadlock Prevention Protocols

Deadlock prevention protocols ensure that the system never enters a deadlock state. Several schemes have been proposed, many using the concept of transaction timestamps.

"A transaction timestamp is a unique identifier assigned to each transaction."

a) Wait-Die Scheme (Non-Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older (smaller timestamp) than Tj, Ti is allowed to wait.
  • If Ti is younger (larger timestamp) than Tj, Ti dies (is rolled back and restarted).
• Older transactions wait; younger transactions are aborted.

Rule: Wait or Die

If TS(Ti) < TS(Tj)  --> Ti waits
If TS(Ti) > TS(Tj)  --> Ti dies (aborts)

b) Wound-Wait Scheme (Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older than Tj, Ti wounds (preempts/aborts) Tj.
  • If Ti is younger than Tj, Ti waits.
• Older transactions preempt younger ones; younger transactions wait.

Rule: Wound or Wait

If TS(Ti) < TS(Tj)  --> Ti wounds Tj (Tj aborts)
If TS(Ti) > TS(Tj)  --> Ti waits

c) Timeout-Based Scheme

"If a transaction waits for a period longer than a system-defined timeout period, the system assumes that the transaction may be deadlocked and aborts it -- regardless of whether a deadlock actually exists."

• Simple and practical due to low overhead.
• A transaction waiting beyond the timeout limit is automatically aborted and restarted.
• Limitation: May abort transactions that are not actually deadlocked (false positives).

Comparison Table

3. Deadlock Detection

"An alternative approach to deal with deadlock is deadlock detection, where the system checks if a state of deadlock actually exists."

When deadlock prevention is not used, the system must detect and recover from deadlocks.

How Deadlock Detection Works

The system maintains a Wait-For Graph (WFG):

• Nodes represent transactions.
• A directed edge Ti --> Tj means Ti is waiting for a resource held by Tj.
• A deadlock exists if and only if there is a cycle in the Wait-For Graph.

Example:

T1 --> T2 --> T3 --> T1   (Cycle detected = Deadlock!)

Detection Algorithm Steps

1. Build the Wait-For Graph from current lock and wait information.
2. Periodically invoke a cycle-detection algorithm.
3. If a cycle is found, select a victim transaction (usually the youngest or least-cost transaction).
4. Abort (rollback) the victim transaction to break the cycle.
5. Release all locks held by the victim and restart it later.

When to Invoke Detection

• After every lock request (high overhead, fast detection).
• Periodically at fixed time intervals (lower overhead, delayed detection).

"This solution is attractive if different transactions will rarely access the same items at the same time."

4. Starvation

"Starvation is a condition where process with higher priorities continuously uses the resources preventing low priority process to acquire the resources."

Starvation occurs when a transaction is indefinitely delayed because other transactions (usually of higher priority) continuously acquire the resources it needs. Unlike deadlock, in starvation some processes do proceed -- just not the starved one.

Difference Between Deadlock and Starvation

How Starvation Occurs in Deadlock Recovery

When the system repeatedly selects the same transaction as victim during deadlock recovery, that transaction is continuously rolled back and never completes -- this is starvation.

Prevention of Starvation

• Aging: Gradually increase the priority of a waiting transaction over time so it eventually

Conceptual Data Model and Types of Attributes in ER Diagram

Conceptual Data Model (2 marks)

A conceptual data model is a collection of concepts used to describe the structure of a database at a high level of abstraction, independent of any physical implementation. It provides the necessary means to achieve abstraction and acts as a conceptual tool for describing data and the relationships among data.

• It describes data at the logical and view level.
• It focuses on what data is stored rather than how it is stored.
• The most widely used conceptual data model is the Entity-Relationship (ER) Model.

The ER model describes the design of a database in terms of entities and relationships among them. An entity is an object in the real world with a set of attributes (e.g., customer_id, customer_name, customer_address).

Types of Attributes in ER Diagram (3 marks)

An attribute is a property or characteristic that describes an entity. The following types of attributes are used in ER diagrams:

1. Simple (Atomic) Attribute

• An attribute that cannot be divided into smaller sub-parts.
• It holds a single value.
• Example: Roll_No, Age
• Represented by an oval in ER diagram.

2. Composite Attribute

• An attribute that can be divided into smaller sub-parts, each representing a more basic attribute.
• Example: Name can be divided into First_Name, Middle_Name, Last_Name.
• Represented by an oval connected to smaller ovals.

3. Single-Valued Attribute

• An attribute that holds only one value for a particular entity.
• Example: Date_of_Birth, SSN (Social Security Number).

4. Multi-Valued Attribute

• An attribute that can hold more than one value for a single entity.
• Example: Phone_Number (a person may have multiple phone numbers).
• Represented by a double oval in ER diagram.

5. Derived Attribute

• An attribute whose value can be derived or computed from another attribute.
• Example: Age can be derived from Date_of_Birth.
• Represented by a dashed oval in ER diagram.

6. Key Attribute

• An attribute that uniquely identifies each entity in an entity set.
• Example: Student_ID, Employee_ID.
• Represented by an oval with the attribute name underlined.

7. Null Attribute

• An attribute that may have a null (unknown or not applicable) value for some entities.
• Example: Middle_Name may be null for some persons.

Summary Table

Short Notes

a. Natural Join

Natural Join is a binary relational operation that combines two relations based on their common attributes (columns that share the same name and same data type).

Key Characteristics:

• It is denoted by the join symbol (⋈)
• The common attribute(s) must have the same name and same data type in both relations
• It automatically performs an equi-join on all matching attribute names
• It eliminates duplicate attributes from the result, keeping only one copy of the common column(s)
• It effectively combines selection and Cartesian product into a single operation

Example:

If relation R(A, B, C) and relation S(C, D, E) share attribute C:

R ⋈ S  produces tuples where R.C = S.C, with C appearing only once
Result schema: (A, B, C, D, E)

Important Note on Lossless Decomposition:

A decomposition {R1, R2, R3} of a relation R is called a lossless decomposition if the natural join of R1, R2, R3 produces exactly the original relation R.

However, if a "fat relation" (one with too many grouped attributes) is split and then rejoined using natural join, it may generate more tuples than the original, making it impossible to recover the original table. This is known as a lossy decomposition.

b. Shadow Paging

Shadow paging is a recovery technique used in database systems to handle transaction failures without using a traditional log.

Basic Concept:

• The database is considered to be made up of a number of fixed-sized disk blocks (say n blocks)
• A directory with n entries is constructed, where the i-th entry points to the i-th database page on disk
• This directory is kept in main memory if it is not too large

How It Works:

During Transaction Execution:

1. The shadow directory is never modified during transaction execution
2. When a write operation is performed on a page:
   • A new copy of the modified page is created on a previously unused disk block
   • The old copy is NOT overwritten
3. For every page updated by the transaction, two versions are maintained:
   • Old version referenced by the shadow directory
   • New version referenced by the current directory

Recovery:

• On transaction failure: simply discard the current directory and restore the shadow directory. The old pages remain intact.
• On successful commit: the current directory replaces the shadow directory permanently.

Advantage:

Simple recovery with no need for redo/undo logs for the modified pages.

Disadvantage:

Requires extra disk space to maintain two versions of modified pages simultaneously.

Conflict Schedule

Definition

A conflict schedule (more precisely, a schedule with conflicting operations) refers to a schedule in which two or more transactions contain conflicting operations. Two operations in a schedule are said to conflict if they satisfy all three of the following conditions:

1. They belong to different transactions.
2. They access the same data item X.
3. At least one of them is a write operation.

The possible conflicting pairs are:

Conflict Serializability

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. To test this, a precedence graph (serialization graph) is constructed.

Algorithm (from notes):

1. Look at only read_Item(X) and write_Item(X) operations.
2. Construct a precedence graph with directed edges.
3. Draw an edge from Ti → Tj if an operation in Ti appears before a conflicting operation in Tj.
4. The schedule is conflict serializable if and only if the precedence graph has no cycles.

Example

Consider two transactions:

• T1: read(X), write(X), read(Y), write(Y)
• T2: read(X), write(X), read(Y), write(Y)

Schedule S:

Identifying Conflicts:

Every pair below is on the same data item, from different transactions, with at least one write, so each pair contributes an edge in the direction of the operation that comes first in the schedule.

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• Edges run in both directions, so the graph contains a cycle (T1 → T2 → T1).
• Therefore, Schedule S is NOT conflict serializable. Neither serial order works: T2 reads X before T1 writes it, which would put T2 first, while T1 writes X before T2 writes it, which would put T1 first.

A Conflict Serializable Schedule S1:

Interleaving the same two transactions differently gives a schedule that is conflict serializable.

Here every conflicting pair has the T1 operation first: read(X) of T1 before write(X) of T2, write(X) of T1 before both read(X) and write(X) of T2, read(Y) of T1 before write(Y) of T2, and write(Y) of T1 before both read(Y) and write(Y) of T2.

Precedence Graph:

T1 ---------> T2

• There is no cycle in this precedence graph.
• Therefore, Schedule S1 is conflict serializable, equivalent to the serial schedule T1 → T2, even though its operations are interleaved.

Example of a NON-Conflict Serializable Schedule

Schedule S2:

Conflicts:

• T2:write(X) before T1:write(X) → T2 → T1
• T1:write(Y) before T2:write(Y) → T1 → T2

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• There is a cycle (T1 → T2 → T1).
• Therefore, Schedule S2 is NOT conflict serializable.

Summary

A conflict schedule contains conflicting operations (same data item, different transactions, at least one write). It is conflict serializable if its precedence graph contains no cycle, meaning it is equivalent to some serial execution of the transactions.

Buffer Management in DBMS

Definition

Buffer Management refers to the process by which the DBMS manages a collection of in-memory buffers (called the DBMS cache) that temporarily hold disk pages (blocks) containing data items needed for processing. Since disk I/O is slow, the DBMS brings data into main memory buffers, performs operations there, and then writes the modified data back to disk at an appropriate time.

How Buffer Management Works

When a transaction needs to read or update a data item, the DBMS follows these steps:

1. Check the buffer directory to see if the required disk page is already in the DBMS cache (buffer pool).
2. If not present, the page is fetched from disk into a free buffer slot.
3. The data item is updated in memory (not directly on disk).
4. A dirty bit is associated with each buffer:
   • Dirty bit = 0: the buffer has not been modified.
   • Dirty bit = 1: the buffer has been modified and needs to be written back to disk.
5. Eventually, the modified buffer is written back to disk based on the recovery policy in use.

Key Policies in Buffer Management

Buffer management is closely tied to recovery algorithms. Two important policy pairs govern when modified pages are written to disk:

1. Steal / No-Steal Policy

2. Force / No-Force Policy

Role of the DBMS Cache Directory

• A directory is maintained to track which database pages are currently held in the buffer pool.
• This avoids redundant disk reads if the same page is needed again.
• The DBMS recovery subsystem uses this information to manage undo and redo operations during crash recovery.

Importance of Buffer Management

• Reduces the number of expensive disk I/O operations.
• Ensures data consistency by controlling when dirty pages are flushed to disk.
• Supports transaction recovery by coordinating with logging mechanisms (undo/redo logs).
• Works together with checkpointing, where all modified buffers are force-written to disk to establish a consistent recovery point.

Summary

Buffer management is the mechanism by which the DBMS controls a pool of main memory buffers (DBMS cache) to hold disk pages temporarily, tracks modifications using dirty bits and a directory, and applies steal/no-steal and force/no-force policies to decide when to write data back to disk, thereby balancing performance and recoverability.

Deadlock: Explanation, Prevention, Detection, and Starvation

1. What is Deadlock?

Deadlock is a condition in a database system (or operating system) where no process proceeds for execution and each process waits for resources that have been acquired by other processes. In other words, a set of transactions are permanently blocked, each waiting for another to release a lock, and none can proceed.

"Deadlock is a condition where no process proceeds for execution and each waits for resources that have been acquired by the other processes."

Example of Deadlock

Consider two transactions T1 and T2, and two data items X and Y:

• T1 holds X and waits for Y.
• T2 holds Y and waits for X.
• Neither can proceed. This is a deadlock.

2. Deadlock Prevention Protocols

Deadlock prevention protocols ensure that the system never enters a deadlock state. Several schemes have been proposed, many using the concept of transaction timestamps.

"A transaction timestamp is a unique identifier assigned to each transaction."

a) Wait-Die Scheme (Non-Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older (smaller timestamp) than Tj, Ti is allowed to wait.
  • If Ti is younger (larger timestamp) than Tj, Ti dies (is rolled back and restarted).
• Older transactions wait; younger transactions are aborted.

Rule: Wait or Die

If TS(Ti) < TS(Tj)  --> Ti waits
If TS(Ti) > TS(Tj)  --> Ti dies (aborts)

b) Wound-Wait Scheme (Preemptive)

• If transaction Ti requests a resource held by Tj:
  • If Ti is older than Tj, Ti wounds (preempts/aborts) Tj.
  • If Ti is younger than Tj, Ti waits.
• Older transactions preempt younger ones; younger transactions wait.

Rule: Wound or Wait

If TS(Ti) < TS(Tj)  --> Ti wounds Tj (Tj aborts)
If TS(Ti) > TS(Tj)  --> Ti waits

c) Timeout-Based Scheme

"If a transaction waits for a period longer than a system-defined timeout period, the system assumes that the transaction may be deadlocked and aborts it -- regardless of whether a deadlock actually exists."

• Simple and practical due to low overhead.
• A transaction waiting beyond the timeout limit is automatically aborted and restarted.
• Limitation: May abort transactions that are not actually deadlocked (false positives).

Comparison Table

3. Deadlock Detection

"An alternative approach to deal with deadlock is deadlock detection, where the system checks if a state of deadlock actually exists."

When deadlock prevention is not used, the system must detect and recover from deadlocks.

How Deadlock Detection Works

The system maintains a Wait-For Graph (WFG):

• Nodes represent transactions.
• A directed edge Ti --> Tj means Ti is waiting for a resource held by Tj.
• A deadlock exists if and only if there is a cycle in the Wait-For Graph.

Example:

T1 --> T2 --> T3 --> T1   (Cycle detected = Deadlock!)

Detection Algorithm Steps

1. Build the Wait-For Graph from current lock and wait information.
2. Periodically invoke a cycle-detection algorithm.
3. If a cycle is found, select a victim transaction (usually the youngest or least-cost transaction).
4. Abort (rollback) the victim transaction to break the cycle.
5. Release all locks held by the victim and restart it later.

When to Invoke Detection

• After every lock request (high overhead, fast detection).
• Periodically at fixed time intervals (lower overhead, delayed detection).

"This solution is attractive if different transactions will rarely access the same items at the same time."

4. Starvation

"Starvation is a condition where process with higher priorities continuously uses the resources preventing low priority process to acquire the resources."

Starvation occurs when a transaction is indefinitely delayed because other transactions (usually of higher priority) continuously acquire the resources it needs. Unlike deadlock, in starvation some processes do proceed -- just not the starved one.

Difference Between Deadlock and Starvation

How Starvation Occurs in Deadlock Recovery

When the system repeatedly selects the same transaction as victim during deadlock recovery, that transaction is continuously rolled back and never completes -- this is starvation.

Prevention of Starvation

• Aging: Gradually increase the priority of a waiting transaction over time so it eventually

Data Independence and Three-Schema Architecture

Data Independence

Data independence is the capacity to change the schema at one level of a database system without having to change the schema at the next higher level.

There are two types of data independence:

1. Logical Data Independence

It is the capacity to change the conceptual schema without having to change the external schemas or application programs. For example, we may add new entity types, change constraints, or reduce the database. Only the view definition and mappings need to be updated; the external/user views remain unaffected.

2. Physical Data Independence

It is the capacity to change the internal schema without having to change the conceptual schema (and hence the external schemas also need not change). Changes to the internal schema may be needed because physical files were reorganized or storage structures were modified. As long as the same data remains in the database, the conceptual schema should not need to change.

Three-Schema Architecture

The goal of the three-schema architecture is to separate user applications from the physical database, thereby achieving data independence and data abstraction.

The three schemas are only descriptions of data; the actual data is stored at the physical level only. Requests and results are transformed between levels through a process called mappings.

External Users
      |
  [External Level]  -- External Views (View 1, View 2, ...)
      |
  External/Conceptual Mapping
      |
  [Conceptual Level] -- Conceptual Schema
      |
  Conceptual/Internal Mapping
      |
  [Internal Level]  -- Internal Schema
      |
  Stored Database

Level 1: External Level (View Level)

• The highest level of abstraction.
• Describes the part of the database that a particular user group is interested in.
• Each user group has its own external view (also called a subschema).
• Hides the rest of the database from that user group.
• Defined using View Definition Language (VDL).

Level 2: Conceptual Level

• Describes what data is stored in the database and the relationships among the data for the entire organization.
• Hides the details of physical storage structures.
• Represents the logical structure of the whole database (entities, attributes, constraints, relationships).
• Defined using Data Definition Language (DDL).

Level 3: Internal Level (Physical Level)

• The lowest level of abstraction.
• Describes how data is physically stored on storage media (file organization, indexing, access paths, record formats, etc.).
• Defined using Storage Definition Language (SDL).

Summary Table

Note: Most DBMSs do not completely and explicitly separate the three levels, but they support the three-schema architecture to some extent.

Conceptual Data Model and Types of Attributes in ER Diagram

Conceptual Data Model (2 marks)

A conceptual data model is a collection of concepts used to describe the structure of a database at a high level of abstraction, independent of any physical implementation. It provides the necessary means to achieve abstraction and acts as a conceptual tool for describing data and the relationships among data.

• It describes data at the logical and view level.
• It focuses on what data is stored rather than how it is stored.
• The most widely used conceptual data model is the Entity-Relationship (ER) Model.

The ER model describes the design of a database in terms of entities and relationships among them. An entity is an object in the real world with a set of attributes (e.g., customer_id, customer_name, customer_address).

Types of Attributes in ER Diagram (3 marks)

An attribute is a property or characteristic that describes an entity. The following types of attributes are used in ER diagrams:

1. Simple (Atomic) Attribute

• An attribute that cannot be divided into smaller sub-parts.
• It holds a single value.
• Example: Roll_No, Age
• Represented by an oval in ER diagram.

2. Composite Attribute

• An attribute that can be divided into smaller sub-parts, each representing a more basic attribute.
• Example: Name can be divided into First_Name, Middle_Name, Last_Name.
• Represented by an oval connected to smaller ovals.

3. Single-Valued Attribute

• An attribute that holds only one value for a particular entity.
• Example: Date_of_Birth, SSN (Social Security Number).

4. Multi-Valued Attribute

• An attribute that can hold more than one value for a single entity.
• Example: Phone_Number (a person may have multiple phone numbers).
• Represented by a double oval in ER diagram.

5. Derived Attribute

• An attribute whose value can be derived or computed from another attribute.
• Example: Age can be derived from Date_of_Birth.
• Represented by a dashed oval in ER diagram.

6. Key Attribute

• An attribute that uniquely identifies each entity in an entity set.
• Example: Student_ID, Employee_ID.
• Represented by an oval with the attribute name underlined.

7. Null Attribute

• An attribute that may have a null (unknown or not applicable) value for some entities.
• Example: Middle_Name may be null for some persons.

Summary Table

Short Notes

a. Natural Join

Natural Join is a binary relational operation that combines two relations based on their common attributes (columns that share the same name and same data type).

Key Characteristics:

• It is denoted by the join symbol (⋈)
• The common attribute(s) must have the same name and same data type in both relations
• It automatically performs an equi-join on all matching attribute names
• It eliminates duplicate attributes from the result, keeping only one copy of the common column(s)
• It effectively combines selection and Cartesian product into a single operation

Example:

If relation R(A, B, C) and relation S(C, D, E) share attribute C:

R ⋈ S  produces tuples where R.C = S.C, with C appearing only once
Result schema: (A, B, C, D, E)

Important Note on Lossless Decomposition:

A decomposition {R1, R2, R3} of a relation R is called a lossless decomposition if the natural join of R1, R2, R3 produces exactly the original relation R.

However, if a "fat relation" (one with too many grouped attributes) is split and then rejoined using natural join, it may generate more tuples than the original, making it impossible to recover the original table. This is known as a lossy decomposition.

b. Shadow Paging

Shadow paging is a recovery technique used in database systems to handle transaction failures without using a traditional log.

Basic Concept:

• The database is considered to be made up of a number of fixed-sized disk blocks (say n blocks)
• A directory with n entries is constructed, where the i-th entry points to the i-th database page on disk
• This directory is kept in main memory if it is not too large

How It Works:

During Transaction Execution:

1. The shadow directory is never modified during transaction execution
2. When a write operation is performed on a page:
   • A new copy of the modified page is created on a previously unused disk block
   • The old copy is NOT overwritten
3. For every page updated by the transaction, two versions are maintained:
   • Old version referenced by the shadow directory
   • New version referenced by the current directory

Recovery:

• On transaction failure: simply discard the current directory and restore the shadow directory. The old pages remain intact.
• On successful commit: the current directory replaces the shadow directory permanently.

Advantage:

Simple recovery with no need for redo/undo logs for the modified pages.

Disadvantage:

Requires extra disk space to maintain two versions of modified pages simultaneously.

Conflict Schedule

Definition

A conflict schedule (more precisely, a schedule with conflicting operations) refers to a schedule in which two or more transactions contain conflicting operations. Two operations in a schedule are said to conflict if they satisfy all three of the following conditions:

1. They belong to different transactions.
2. They access the same data item X.
3. At least one of them is a write operation.

The possible conflicting pairs are:

Conflict Serializability

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. To test this, a precedence graph (serialization graph) is constructed.

Algorithm (from notes):

1. Look at only read_Item(X) and write_Item(X) operations.
2. Construct a precedence graph with directed edges.
3. Draw an edge from Ti → Tj if an operation in Ti appears before a conflicting operation in Tj.
4. The schedule is conflict serializable if and only if the precedence graph has no cycles.

Example

Consider two transactions:

• T1: read(X), write(X), read(Y), write(Y)
• T2: read(X), write(X), read(Y), write(Y)

Schedule S:

Identifying Conflicts:

Every pair below is on the same data item, from different transactions, with at least one write, so each pair contributes an edge in the direction of the operation that comes first in the schedule.

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• Edges run in both directions, so the graph contains a cycle (T1 → T2 → T1).
• Therefore, Schedule S is NOT conflict serializable. Neither serial order works: T2 reads X before T1 writes it, which would put T2 first, while T1 writes X before T2 writes it, which would put T1 first.

A Conflict Serializable Schedule S1:

Interleaving the same two transactions differently gives a schedule that is conflict serializable.

Here every conflicting pair has the T1 operation first: read(X) of T1 before write(X) of T2, write(X) of T1 before both read(X) and write(X) of T2, read(Y) of T1 before write(Y) of T2, and write(Y) of T1 before both read(Y) and write(Y) of T2.

Precedence Graph:

T1 ---------> T2

• There is no cycle in this precedence graph.
• Therefore, Schedule S1 is conflict serializable, equivalent to the serial schedule T1 → T2, even though its operations are interleaved.

Example of a NON-Conflict Serializable Schedule

Schedule S2:

Conflicts:

• T2:write(X) before T1:write(X) → T2 → T1
• T1:write(Y) before T2:write(Y) → T1 → T2

Precedence Graph:

T1 ---------> T2
 ^            |
 |____________|

• There is a cycle (T1 → T2 → T1).
• Therefore, Schedule S2 is NOT conflict serializable.

Summary

A conflict schedule contains conflicting operations (same data item, different transactions, at least one write). It is conflict serializable if its precedence graph contains no cycle, meaning it is equivalent to some serial execution of the transactions.

Buffer Management in DBMS

Definition

Buffer Management refers to the process by which the DBMS manages a collection of in-memory buffers (called the DBMS cache) that temporarily hold disk pages (blocks) containing data items needed for processing. Since disk I/O is slow, the DBMS brings data into main memory buffers, performs operations there, and then writes the modified data back to disk at an appropriate time.

How Buffer Management Works

When a transaction needs to read or update a data item, the DBMS follows these steps:

1. Check the buffer directory to see if the required disk page is already in the DBMS cache (buffer pool).
2. If not present, the page is fetched from disk into a free buffer slot.
3. The data item is updated in memory (not directly on disk).
4. A dirty bit is associated with each buffer:
   • Dirty bit = 0: the buffer has not been modified.
   • Dirty bit = 1: the buffer has been modified and needs to be written back to disk.
5. Eventually, the modified buffer is written back to disk based on the recovery policy in use.

Key Policies in Buffer Management

Buffer management is closely tied to recovery algorithms. Two important policy pairs govern when modified pages are written to disk:

1. Steal / No-Steal Policy

2. Force / No-Force Policy

Role of the DBMS Cache Directory

• A directory is maintained to track which database pages are currently held in the buffer pool.
• This avoids redundant disk reads if the same page is needed again.
• The DBMS recovery subsystem uses this information to manage undo and redo operations during crash recovery.

Importance of Buffer Management

• Reduces the number of expensive disk I/O operations.
• Ensures data consistency by controlling when dirty pages are flushed to disk.
• Supports transaction recovery by coordinating with logging mechanisms (undo/redo logs).
• Works together with checkpointing, where all modified buffers are force-written to disk to establish a consistent recovery point.

Summary

Buffer management is the mechanism by which the DBMS controls a pool of main memory buffers (DBMS cache) to hold disk pages temporarily, tracks modifications using dirty bits and a directory, and applies steal/no-steal and force/no-force policies to decide when to write data back to disk, thereby balancing performance and recoverability.

Database integrity refers to the accuracy, consistency, and correctness of data stored in a database. It ensures that the data in the database remains valid and reliable throughout its lifecycle. Integrity constraints are rules or condit...

Normalization in Database Design

Definition of Normalization

Normalization is the process of organizing the attributes and tables of a relational database to minimize data redundancy and dependency. It involves decomposing a large, poorly structured table into smaller, well-structured tables while preserving data integrity and relationships. The process is guided by a series of rules called Normal Forms (NF).

Why Normalization is Important in Database Design

Normalization is important for the following reasons:

Types of Anomalies (Before Normalization)

Consider the following unnormalized table:

• Update Anomaly: If Dr. Sharma's name changes, it must be updated in multiple rows.
• Insertion Anomaly: A new course cannot be added without a student.
• Deletion Anomaly: Deleting Sita's record also deletes information about Course C01.

Normal Forms

1. First Normal Form (1NF)

Definition: A relation is in 1NF if:

• All attributes contain only atomic (indivisible) values.
• Each column contains values of a single type.
• Each row is unique (has a primary key).
• There are no repeating groups or multi-valued attributes.

Example of a table NOT in 1NF:

Here, the Courses column contains multiple values, which violates 1NF.

Converting to 1NF:

Now each cell has an atomic value. This table is in 1NF. Primary Key: (StudentID, Course)

2. Second Normal Form (2NF)

Definition: A relation is in 2NF if:

• It is already in 1NF.
• Every non-key attribute is fully functionally dependent on the entire primary key (no partial dependency).

Partial Dependency: A non-key attribute depends on only a part of a composite primary key.

Example of a table in 1NF but NOT in 2NF:

Primary Key: (StudentID, Course)

Functional Dependencies:

• (StudentID, Course) --> InstructorName (full dependency - OK)
• StudentID --> StudentName (partial dependency - VIOLATION)

StudentName depends only on StudentID, not on the full composite key.

Converting to 2NF (Remove partial dependencies):

Student Table:

Enrollment Table:

Now all non-key attributes are fully dependent on the primary key. Both tables are in 2NF.

3. Third Normal Form (3NF)

Definition: A relation is in 3NF if:

• It is already in 2NF.
• There is no transitive dependency of non-key attributes on the primary key.

Transitive Dependency: A non-key attribute depends on another non-key attribute, which in turn depends on the primary key. If A --> B and B --> C, then A --> C is a transitive dependency.

Example of a table in 2NF but NOT in 3NF:

Primary Key: (StudentID, Course)

Functional Dependencies:

• (StudentID, Course) --> InstructorID (full dependency - OK)
• InstructorID --> InstructorName (transitive dependency - VIOLATION)

Here: (StudentID, Course) --> InstructorID --> InstructorName

InstructorName depends on InstructorID (a non-key attribute), not directly on the primary key.

Converting to 3NF (Remove transitive dependencies):

Enrollment Table:

Instructor Table:

The transitive dependency is now gone. InstructorName is stored exactly once, in the table whose key it actually depends on, while the Enrollment table keeps only InstructorID as a foreign key. Both tables are in 3NF, and the original information can be recovered without loss by joining them on InstructorID.

The anomalies listed at the beginning disappear with it. Correcting Dr. Sharma's name now changes a single row of the Instructor table, so there is no update anomaly. A new instructor can be recorded before any student enrols under that instructor, so there is no insertion anomaly. Deleting the last enrolment for a course no longer erases the instructor's details, so there is no deletion anomaly.

Summary of the Three Normal Forms

Normalization therefore moves a design from a single wide table full of repeated facts towards a set of narrow tables in which every fact is stored once and depends on the key, the whole key and nothing but the key. Stricter forms such as BCNF and 4NF handle the remaining special cases, but 3NF is normally sufficient for practical database design, and a controlled amount of denormalization is added afterwards only where read performance demands it.

Fat File System and Advantages of DBMS Approach

Part 1: Fat File System (File Processing System)

A fat file system (also called a file processing system or flat file system) is a traditional approach to data management where data is stored in separate, independent files managed directly by individual application programs. Each application maintains its own set of files, and there is no centralized control or management of the data.

Key characteristics:

• Data is stored in isolated files with no central coordination
• Each application program defines and manages its own data files
• Data is accessed through application-specific programs
• There is no standard interface for accessing or sharing data across applications

Major problems of the fat file system:

• Data redundancy and inconsistency - same data stored in multiple files
• Difficulty in accessing data - no flexible query mechanism
• Data isolation - data scattered in various files and formats
• Integrity problems - difficult to enforce constraints
• Atomicity problems - difficult to ensure all-or-nothing operations
• Concurrent access anomalies - multiple users accessing same file causes problems
• Security problems - difficult to enforce access control

Part 2: Advantages of Using DBMS Approach

A good DBMS provides the following advantages:

1. Providing Backup and Recovery

The backup and recovery subsystem of a DBMS is responsible for recovery. For example, if the computer fails in the middle of a complex update transaction, the recovery system ensures the database is restored to the state it was in before the transaction started executing. Disk backup is also necessary in case of catastrophic disk failure.

2. Providing Multiple User Interfaces

Many types of users with varying levels of technical knowledge use a database. A DBMS provides a variety of user interfaces including:

• Apps for mobile users
• Query language for casual users
• Programming language interfaces for application programmers
• Forms and commands for parametric users
• Menu-driven and natural language interfaces for standalone users
• Graphical User Interfaces (GUIs)

3. Flexibility

It may be necessary to change the structure of a database as requirements change. Modern DBMS allow certain types of evolutionary changes to the structure of the database without affecting existing application programs. For example, a new user group may emerge that needs additional information, requiring new files or extended data elements.

4. Availability of Up-to-Date Information

As soon as a user's update is applied to the database, all other users can immediately see that update. This availability of up-to-date information is essential for many transaction-processing applications such as reservation systems or banking databases.

5. Reduced Data Redundancy and Inconsistency

By centralizing data management, DBMS minimizes duplication of data across multiple files, thereby reducing inconsistency.

6. Enforcing Integrity Constraints

DBMS allows integrity constraints to be defined and automatically enforced, ensuring data accuracy and validity.

In summary, the DBMS approach overcomes all the major drawbacks of the fat file system by providing centralized, controlled, secure, and flexible data management with support for multiple users and recovery mechanisms.

--- Data abstraction refers to the process of hiding the complexity of the internal details of how data is stored and maintained, and exposing only the relevant information to the users. A database system achieves this through three leve...

Aggregation is an abstraction concept in the Entity-Relationship (ER) model where a relationship itself is treated as a higher-level entity. It allows a relationship between entities to participate in another relationship. In other words...

Functional Dependencies and Second Normal Form (2NF)

Functional Dependency (FD)

A functional dependency is a constraint between two sets of attributes in a relation. For a relation R, a functional dependency X → Y means that the value of attribute set X uniquely determines the value of attribute set Y.

• X is called the determinant
• Y is called the dependent

Example: In a Student table, StudentID → StudentName means that knowing the StudentID uniquely determines the StudentName.

A set of functional dependencies is given for each relation, and each relation has a designated primary key, which is then evaluated for normalization. (from notes)

Second Normal Form (2NF)

"To be in second normal form, a relation must be in First Normal Form AND the relation must not contain any partial dependency." (from notes)

Key Definitions:

• Non-prime attribute: An attribute that is not part of any candidate key
• Partial Dependency: When a proper subset of a candidate key determines a non-prime attribute

Partial Dependency = Proper subset of candidate key → non-prime attribute

Conditions for 2NF:

1. The relation must be in 1NF
2. There must be no partial dependency (every non-prime attribute must be fully functionally dependent on the whole candidate key)

Example

Table NOT in 2NF:

• Primary Key (Composite): {StudentID, CourseID}
• Functional Dependencies:
  • StudentID, CourseID → Grade (full dependency - OK)
  • StudentID → StudentName (partial dependency - violation)
  • CourseID → CourseName (partial dependency - violation)

Since StudentName depends only on StudentID (a proper subset of the composite key), this is a partial dependency, so the table is NOT in 2NF.

Decomposition to achieve 2NF:

Table 1: Student

Table 2: Course

Table 3: Enrollment

Now every non-prime attribute is fully dependent on the entire primary key. All three tables are in 2NF.

Summary

• Customer(<uCustomerID</u, CustomerName, Address, Phone, Email) - Borrows(<uCustomerID</u, <uLoanNumber</u) - Loan(<uLoanNumber</u, LoanType, Amount) --- $$\tau{CustomerName}(\pi{CustomerName}(\sigma{Address='Lalitpur'}(Customer)))$$ Wh...

A timestamp is a unique identifier assigned to each transaction by the DBMS, typically based on the system clock or a logical counter at the time the transaction starts. The timestamp ordering protocol uses these timestamps to determine ...

--- A relational database is a database that organizes and stores data in the form of tables (relations). Each table consists of rows (tuples) and columns (attributes). It is based on the relational data model proposed by E.F. Codd. Well...