Transaction, Lost Update, and Dirty Read Problems

What is a Transaction?

A transaction is a logical unit of work that consists of a sequence of database operations (such as read and write) that must be executed as a single, indivisible unit. A transaction either completes fully (commits) or has no effect at all (rolls back).

A transaction must satisfy the ACID properties:

Example of a transaction:

BEGIN TRANSACTION
    READ(A)
    A = A - 500
    WRITE(A)
    READ(B)
    B = B + 500
    WRITE(B)
COMMIT

Problems in Concurrent Execution of Transactions

When multiple transactions execute concurrently without proper control, several problems can arise. Two major problems are:

1. Lost Update Problem
2. Dirty Read Problem

1. Lost Update Problem

Definition

The lost update problem occurs when two transactions read the same data item and then both update it based on the original value they read. The update made by the first transaction is overwritten (lost) by the second transaction, resulting in incorrect data.

How It Occurs

• Transaction T1 reads a data item X.
• Transaction T2 also reads the same data item X.
• T1 updates X and writes it back.
• T2 updates X based on the old value it read and writes it back.
• T1's update is lost because T2 overwrites it.

Example

Suppose two bank clerks are updating the same account balance simultaneously.

Initial Balance of Account A = 1000

Expected Result: 1000 + 200 - 300 = 900

Actual Result: 700

T1's update of +200 is lost because T2 read the old value (1000) before T1 wrote its result, and T2's WRITE overwrote T1's update.

2. Dirty Read Problem

Definition

The dirty read problem (also called the temporary update problem) occurs when a transaction reads data that has been modified by another transaction that has not yet committed. If the first transaction later rolls back, the second transaction has read data that never officially existed, leading to inconsistency.

How It Occurs

• Transaction T1 reads a data item X and updates it.
• Transaction T2 reads the updated (dirty) value of X before T1 commits.
• T1 fails and rolls back, restoring X to its original value.
• T2 has already used the incorrect (dirty) value in its computation.

Example

Suppose a flight booking system where two transactions operate on available seats.

Initial Seats Available = 10

Expected Result: T1 rolled back, so only T2 should have booked. Seats should be 9.

Actual Result: 8

T2 read the dirty (uncommitted) value of 9 written by T1. After T1 rolled back, the actual value was restored to 10, but T2 already computed based on 9, causing an incorrect final value of 8.

Summary Comparison

Solution

These problems are solved by concurrency control mechanisms such as:

• Locking protocols (shared lock, exclusive lock)
• Timestamp ordering
• Serializable schedules

These ensure that concurrent transactions produce results equivalent to some serial execution of those transactions.

ER Diagram: Need and Design

Part 1: Need for an ER Diagram (3 marks)

An Entity-Relationship (ER) Diagram is a high-level conceptual data model that graphically represents the structure of a database. The need for an ER diagram arises due to the following reasons:

1. Visual Representation of Data: It provides a clear, pictorial view of the database structure, making it easy to understand the relationships among data entities before actual implementation.

2. Communication Tool: It serves as a common language between database designers, developers, and non-technical stakeholders (clients, managers) to discuss and validate requirements.

3. Blueprint for Database Design: It acts as a blueprint for translating the conceptual model into a logical and then physical database schema (tables, keys, constraints).

4. Error Detection at Early Stage: Design flaws, redundancies, and missing relationships can be identified and corrected at the design stage, saving time and cost during implementation.

5. Documentation: It serves as permanent documentation of the database structure for future maintenance and modification.

6. Simplifies Complex Systems: For large and complex systems, ER diagrams break down the system into manageable entities and relationships, making design systematic and organized.

Part 2: ER Diagram Design (7 marks)

Assumptions / Scenario: University Management System

Entities and Their Attributes

Relationships

Special Requirements Checklist

ER Diagram (Text/Notation Representation)

                    [DOB]  ((Phone))  [Name]  [Address]
                      |       |         |        |
                    (Age*)    |         |        |
                      \       |         |        /
                       ======[STUDENT]======
                      /                      \
              (double line)                   \
                  ||                           \
           <BELONGS_TO>                    <ENROLLS> (M:N)
                  |                             |
           [DEPARTMENT]                      [COURSE]
           DeptID, DeptName,              CourseID, CourseName,
           Location                       Credits
                                               |
                                          <TEACHES>
                                               |
                                         [PROFESSOR]
                                    ProfID, ProfName, Salary
                                        /           \
                                  <WORKS_IN>    <HAS_DEPENDENT>
                                       |               || (double line)
                                 [DEPARTMENT]    [[DEPENDENT]]
                                              DepName(dashed underline),
                                              Relationship, Age

ER Diagram (Formal Diagram Description)

+------------------------------------------------------------------+
|                  UNIVERSITY MANAGEMENT SYSTEM                    |
+------------------------------------------------------------------+

  [DOB]  ((Phone))  [Name]  [Address]
    |        |         |       |
  (Age*)     |         |       |
    +--------+---------+-------+
    |                          |
 ====[  STUDENT  ]====         |
 ||  StudentID(PK)  ||         |
 ||  Name, Address  ||         |
 ||  DOB            ||         |
 ||  Age*           ||         |
 ||  {Phone}        ||         |
 ====                ====      |
  |                    |       |
  | (Total)            |       |
  |                    |       |
<BELONGS_TO>      <ENROLLS> (M:N)
  |                    |
  |              [  COURSE  ]
[DEPARTMENT]     CourseID(PK)
DeptID(PK)       CourseName
DeptName         Credits
Location              |
  |              <TEACHES>
  |                   |
<WORKS_IN>----[PROFESSOR]----<HAS_DEPENDENT>
              ProfID(PK)              ||
              ProfName           [[DEPENDENT]]
              Salary             DepName (partial key, dashed underline)
                                 Relationship
                                 Age

Notation Key

Cardinality Summary

The M:N relationship ENROLLS cannot be represented by a foreign key in either table, so on conversion to tables it becomes a separate relation ENROLLMENT(StudentID, CourseID, Grade) whose primary key is the pair of foreign keys. The weak entity DEPENDENT likewise becomes DEPENDENT(ProfID, DepName, Relationship, Age) with ProfID as both part of the primary key and a foreign key, deleted along with its owner professor.

Conclusion

An ER diagram is needed because it captures the structure of the data, the entities, their attributes and the relationships among them, before any table is written, and it does so in a notation that a non technical user can still read and approve. The design above satisfies the requirements of the question: five entities (STUDENT, DEPARTMENT, COURSE, PROFESSOR and the weak entity DEPENDENT), a many to many relationship between the two strong entities STUDENT and COURSE, a derived attribute (Age, computed from DOB) and a multi-valued attribute (Phone) on STUDENT, and total participation of STUDENT in BELONGS_TO.

Normalization: Need, 1NF, 2NF, and 3NF

Why is Normalization Required?

Normalization is the process of organizing a relational database to reduce data redundancy and improve data integrity by decomposing large, poorly structured tables into smaller, well-structured ones.

Problems Without Normalization (Anomalies)

Consider the following unnormalized table:

1. Insertion Anomaly: A new course cannot be inserted unless at least one student is enrolled in it. The course data depends on student data being present.

2. Deletion Anomaly: If Student 2 (Sita) drops Course C01, the information about Dr. Sharma teaching DBMS is also lost.

3. Update Anomaly: If Dr. Sharma's name changes, it must be updated in every row where C01 appears. Missing even one row causes inconsistency.

Goals of Normalization

• Eliminate redundant data
• Ensure data dependencies make sense
• Make the database easier to maintain
• Reduce storage space

First Normal Form (1NF)

Definition

A relation is in 1NF if:

• All attributes contain atomic (indivisible) values
• There are no repeating groups or multi-valued attributes
• Each column contains values of a single type
• Each row is uniquely identifiable

Example

Violation of 1NF:

Here, the Courses column has multiple values -- this violates 1NF.

After converting to 1NF:

Now every attribute is atomic. The table is in 1NF.

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

Consider the table (Primary Key = {StudentID, CourseID}):

Functional Dependencies:

• {StudentID, CourseID} --> Grade (full dependency -- OK)
• StudentID --> StudentName (partial dependency -- violates 2NF)
• CourseID --> CourseName (partial dependency -- violates 2NF)

After converting to 2NF (decompose):

Student Table:

Course Table:

Enrollment Table:

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

Third Normal Form (3NF)

Definition

A relation is in 3NF if:

• It is already in 2NF
• There is no transitive dependency -- no non-key attribute depends on another non-key attribute

Transitive Dependency: If A --> B and B --> C, then A --> C is a transitive dependency (C depends on A through B).

Example

Consider the table (Primary Key = StudentID):

Functional Dependencies:

• StudentID --> DeptID (direct dependency -- OK)
• DeptID --> DeptName (DeptName depends on DeptID, not on StudentID)
• Therefore: StudentID --> DeptID --> DeptName (transitive dependency -- violates 3NF)

After converting to 3NF (decompose):

Student Table:

Department Table:

Now there is no transitive dependency. Both tables are in 3NF.

Summary Table

Conclusion

Normalization is required because an unnormalized table stores the same fact in many rows, which wastes space and, more seriously, allows the copies to disagree. Removing repeating groups gives 1NF, removing partial dependency on part of a composite key gives 2NF, and removing transitive dependency through a non-key attribute gives 3NF. Each step replaces one table by two smaller tables joined on a key, so the insertion, deletion and update anomalies disappear while the original information can still be recovered by a join. Most practical database designs stop at 3NF (or BCNF), since further decomposition begins to cost more in join time than it saves in redundancy.

Three Schema Architecture and Data Independence

Three Schema Architecture

The three schema architecture (also called the ANSI/SPARC architecture) is a framework for database systems that separates the database into three distinct levels or schemas. This architecture was proposed to achieve data independence and support multiple user views.

The Three Levels

1. External Level (View Level)

• The highest level of abstraction, closest to the end users.
• Describes how individual users or groups of users see the data.
• Each user group has its own external schema (user view), showing only the portion of the database relevant to that user.
• Different users can have different views of the same data.
• Example: A student may see only their own grades, while a teacher sees all student grades.

2. Conceptual Level (Logical Level)

• The middle level, representing the community or organizational view of the entire database.
• Described by a conceptual schema, which defines:
  • All entities, attributes, and relationships
  • Constraints, security, and integrity rules
• Hides the physical storage details but describes what data is stored and how it is logically structured.
• Managed by the Database Administrator (DBA).

3. Internal Level (Physical Level)

• The lowest level, closest to physical storage.
• Described by an internal schema, which defines:
  • How data is physically stored on disk
  • File organization, indexing, hashing, access paths
  • Storage allocation and compression
• Deals with the actual implementation of the database.

Diagram

+-----------------------------+
|   External Schema 1  |  External Schema 2  |  ...  |   <- External Level
+-----------------------------+
           |
+-----------------------------+
|      Conceptual Schema      |                           <- Conceptual Level
+-----------------------------+
           |
+-----------------------------+
|       Internal Schema       |                           <- Internal Level
+-----------------------------+
           |
+-----------------------------+
|     Physical Database       |
+-----------------------------+

How the Architecture Creates Data Independence

Data independence is the ability to change the schema at one level without having to change the schema at the next higher level. The three schema architecture achieves this through two types of mappings:

1. Logical Data Independence

• The ability to change the conceptual schema without changing the external schemas or application programs.
• Example: Adding a new attribute (column) to a table, or splitting a table, does not affect the user views as long as the mapping between external and conceptual levels is updated.
• This is harder to achieve in practice.

2. Physical Data Independence

• The ability to change the internal schema without changing the conceptual schema.
• Example: Changing the file organization from sequential to indexed, or moving data to a different storage device, does not affect the logical structure.
• This is easier to achieve and is supported by most DBMS.

Summary Table

Conclusion

The three schema architecture creates data independence by introducing clear separation between how data is physically stored, how it is logically organized, and how it is viewed by users. The mappings between levels ensure that changes at one level are translated appropriately, shielding higher levels from lower-level changes. This reduces maintenance cost, improves flexibility, and allows the database to evolve without disrupting existing applications.

Database Recovery and Shadow Paging

What is Database Recovery? (2 marks)

Database recovery is the process of restoring a database to a correct and consistent state after a failure (such as system crash, transaction failure, media failure, or power loss).

The primary goals of database recovery are:

• Atomicity: Ensure that incomplete transactions are rolled back (undone).
• Durability: Ensure that committed transactions are not lost.

Recovery relies on the concept of maintaining redundant information (logs, shadow copies) so that the database can be restored to the last consistent state.

Shadow Paging for Database Recovery (3 marks)

Shadow paging is a recovery technique that avoids the use of a log file by maintaining two page tables simultaneously:

How Shadow Paging Works

Setup:

• The database is organized into fixed-size pages.
• At the start of a transaction, both the current page table and the shadow page table point to the same physical pages on disk.

During a Transaction:

• When a transaction modifies a page, a new copy of that page is created in a different disk location.
• The current page table is updated to point to the new (modified) page.
• The shadow page table remains unchanged, still pointing to the old (original) pages.

Shadow Page Table          Current Page Table
  [Page 1] --> P1            [Page 1] --> P1  (unchanged)
  [Page 2] --> P2            [Page 2] --> P2' (new modified copy)
  [Page 3] --> P3            [Page 3] --> P3  (unchanged)

On COMMIT (Transaction Success):

1. All modified pages are written to disk.
2. The current page table replaces the shadow page table (i.e., the shadow page table pointer is updated to point to the current page table).
3. The old shadow pages that were replaced are freed.
4. The database is now in a new consistent state.

On ABORT / Failure (Transaction Failure):

1. The current page table is simply discarded.
2. The shadow page table (which still points to the old consistent pages) is restored as the current page table.
3. No undo operations are needed -- the database automatically reverts to the last consistent state.

Advantages of Shadow Paging

• No need for a redo/undo log.
• Recovery is simple and fast -- just restore the shadow page table.
• No cascading rollbacks.

Disadvantages of Shadow Paging

• Fragmentation: Pages of the same file may scatter across disk over time.
• Garbage collection: Old shadow pages must be reclaimed.
• Overhead: Copying entire pages even for small changes is costly.
• Not suitable for large databases with many concurrent transactions.

Summary: Shadow paging ensures recovery by keeping an untouched shadow copy of the last consistent database state. On failure, the shadow copy is restored; on commit, the shadow is updated to reflect the new state.

Two Phase Locking (2PL) Protocol

Definition

Two Phase Locking (2PL) is a concurrency control protocol that ensures serializability of transactions by regulating when locks can be acquired and released. It states that:

A transaction must acquire all the locks it needs before releasing any lock.

The protocol divides the execution of a transaction into two distinct phases:

The Two Phases

Phase 1: Growing Phase (Lock Acquisition Phase)

• A transaction may acquire locks (shared or exclusive).
• A transaction may NOT release any lock.
• The number of locks held by the transaction increases (or stays the same).

Phase 2: Shrinking Phase (Lock Release Phase)

• A transaction may release locks.
• A transaction may NOT acquire any new lock.
• The number of locks held decreases until all are released.

The point at which the last lock is acquired is called the Lock Point.

Number
of Locks
    |        /\
    |       /  \
    |      /    \
    |     /      \
    |    /        \
    |___/          \___
    |
    +--Growing--+--Shrinking-->  Time

Types of 2PL

How 2PL Can Lead to Deadlock

Deadlock occurs when two or more transactions are waiting for each other to release locks, forming a circular wait condition.

Example:

Consider two transactions T1 and T2:

Result:

• T1 holds lock on A and waits for B
• T2 holds lock on B and waits for A
• Neither can proceed -- DEADLOCK

Why 2PL Causes This:

In the growing phase, a transaction acquires locks one at a time (not all at once). This means:

• T1 acquires lock on A, then tries to acquire lock on B
• T2 acquires lock on B, then tries to acquire lock on A
• Since neither can release a lock during the growing phase (2PL rule), a circular dependency forms

This is a direct consequence of the 2PL rule that locks cannot be released until the shrinking phase begins, combined with the fact that locks are acquired incrementally.

Deadlock Handling

Since 2PL can cause deadlocks, the DBMS must handle them using:

• Deadlock Detection -- using a wait-for graph; if a cycle is detected, one transaction is rolled back (victim selection)
• Deadlock Prevention -- using timestamp-based schemes (Wait-Die or Wound-Wait protocols)

Summary

Views in SQL

What is a View?

A view is a virtual table that is derived from one or more base tables (or other views) using a SQL query. It does not physically store data itself; instead, it stores the query definition, and the data is retrieved dynamically whenever the view is accessed.

Key characteristics of a view:

• It behaves like a table (can be queried using SELECT)
• It simplifies complex queries
• It provides data security by restricting access to specific rows/columns
• It provides logical data independence

Creating a View in SQL

Syntax:

CREATE VIEW view_name AS
SELECT column1, column2, ...
FROM table_name
WHERE condition;

Example

Consider a base table:

Employee table:

Step 1: Create a View

Suppose we want to create a view that shows only IT department employees without exposing their salary:

CREATE VIEW IT_Employees AS
SELECT EmpID, EmpName, Department
FROM Employee
WHERE Department = 'IT';

Step 2: Query the View

SELECT * FROM IT_Employees;

Output:

Dropping a View

DROP VIEW IT_Employees;

Summary

A view thus acts as a saved query that can be treated as a table, providing security, simplicity, and abstraction over the underlying data.