DATABASE MANAGEMENT SYSTEMS

Transaction Management
Comprehensive Student Notes — Definitions · Diagrams · Examples ·
Comparisons

Topic Page

Transaction Definition & Properties (ACID) 2

Transaction State Diagram 2

Commit and Rollback 3

Serializability (Conflict & View) 4

Concurrency Control Overview 5

Lock-Based Protocols 5

Two-Phase Locking (2PL) 6

Timestamp Ordering Protocol 7

Recovery Management 8

Deadlock Handling & Prevention 9

1. Transaction — Definition & Properties
Definition: A transaction is a logical unit of database work that accesses and possibly modifies the
contents of a database. It must be executed as an all-or-nothing operation to maintain database
consistency.

Example: A bank transfer of ■5000 from Account A to Account B involves two operations: (1) Debit A by ■5000,
(2) Credit B by ■5000. Both must succeed together — a partial execution corrupts the database.

1.1 ACID Properties

Every transaction must satisfy the four ACID properties:

Propert
Full Name Meaning Bank Transfer Example
y

Either ALL operations execute or NONE Debit + Credit both happen, or neither
A Atomicity
do. does.

Total balance before = total balance

C Consistency DB moves from one valid state to another.
after.

Concurrent transactions appear Intermediate states not visible to

I Isolation
sequential. others.

Committed changes persist even after Transfer survives power failure after
D Durability
crash. commit.

1.2 Transaction State Diagram

A transaction passes through several states during its lifetime:

Transaction State Diagram

Read/Write PARTIALLY Output

ACTIVE COMMITTED COMMITTED

Error Error

Rollback
FAILED ABORTED

Figure 1: Transaction State Transition Diagram

State Description Possible Next State(s)

Active Initial state; transaction is executing. Partially Committed, Failed

Partially Committed Final operation executed; awaiting commit. Committed, Failed

Committed Transaction completed successfully; changes are permanent.

—
State Description Possible Next State(s)

Failed Normal execution cannot proceed; error detected. Aborted

Aborted Transaction rolled back; DB restored to prior state. Active (restart) or Killed
Table 1: Transaction States and Transitions
2. Commit and Rollback
2.1 COMMIT
COMMIT: Signals successful completion. All changes made by the transaction are permanently saved to
the database and become visible to other transactions.
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 5000 WHERE acc_id = 'A';
UPDATE accounts SET balance = balance + 5000 WHERE acc_id = 'B';
COMMIT; -- Changes are now permanent

2.2 ROLLBACK (Abort)

ROLLBACK: Undoes all changes made by the current transaction, restoring the database to the state
before the transaction began. Used when an error occurs.
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 5000 WHERE acc_id = 'A';
-- Error: Account B does not exist!
ROLLBACK; -- Debit to A is also undone

Feature COMMIT ROLLBACK

Purpose Save all changes permanently Undo all changes in transaction

When used Transaction succeeds completely Error occurs / forced abort

Effect on data Changes become durable Changes are discarded

Visibility Changes visible to others Changes never visible

Recovery needed No Yes — undo log used

Table 2: Commit vs Rollback Comparison

■ SAVEPOINT: A partial rollback point within a transaction. ROLLBACK TO SAVEPOINT undoes work only up to
that point, not the entire transaction.
3. Serializability
Serializability: A schedule (sequence of operations from concurrent transactions) is serializable if its
outcome is equivalent to that of some serial (non-interleaved) execution of those transactions.

When multiple transactions run concurrently, their operations are interleaved. Serializability is the gold standard
for correctness — it guarantees isolation.

3.1 Conflict Serializability

Two operations conflict if they belong to different transactions, access the same data item, and at least one is a
write. A schedule is conflict serializable if it can be converted to a serial schedule by swapping non-conflicting
operations.

Example — Conflict Serializable Schedule:

Schedule S: T1:R(A) T2:R(A) T1:W(A) T2:W(A)

Conflict pairs (same item, at least one Write, different Txns):

T1:W(A) → T2:W(A) (W-W conflict)
T1:W(A) → T2:R(A)? No — T2:R(A) comes BEFORE T1:W(A)

Precedence Graph: T1 → T2 (no cycle) → CONFLICT SERIALIZABLE

Equivalent serial order: T1 then T2

3.2 View Serializability

A schedule S is view serializable if it is view equivalent to some serial schedule. View equivalence requires:
same initial reads, same reads-from relationships, and same final writes. View serializability is broader than
conflict serializability — every conflict serializable schedule is view serializable, but not vice versa.

Aspect Conflict Serializability View Serializability

Based on Swapping non-conflicting ops Initial reads, reads-from, final writes

Test Precedence (acyclic) graph Polynomial but complex check

Strictness Stricter (subset) More general (superset)

Practicality Widely used in DBMSs Rarely enforced directly

Blind writes Not allowed by itself Can include blind writes

Example T1→T2→T3 (no cycle) May allow non-conflict-ser. schedules

Table 3: Conflict Serializability vs View Serializability

■ Precedence Graph Test: Draw a node for each transaction. Draw edge Ti→Tj if Ti's operation conflicts with and
precedes Tj's operation. If the graph has NO cycle, the schedule is conflict serializable.
4. Concurrency Control
Concurrency control mechanisms ensure that concurrent execution of transactions results in a database state
equivalent to serial execution. Without it, the following anomalies occur:

Problem Description Example

Dirty Read T2 reads data written by uncommitted T1;T1

T1writes X=50; T2 reads X=50; T1 rolls back → T2 used wrong value.
aborts.

Lost Update T2 overwrites T1's update. T1 reads X=100; T2 reads X=100; both write X+10 → one +10 is lost.

Non-repeatable Read T1 reads same item twice and gets different

T1 values.
reads X=100; T2 updates X=200; T1 re-reads X=200.

Phantom Read New rows appear between two reads by the

T1 same
countstxn.
rows; T2 inserts row; T1 recounts — gets different count.
Table 4: Concurrency Anomalies
5. Lock-Based Protocols
Lock: A mechanism that controls concurrent access to a data item. A transaction must acquire a lock
before accessing an item and releases it afterward.

5.1 Lock Types

Lock Type Symbol Also Called Permits Compatibility

Shared Lock S Read Lock Read only Compatible with other S locks

Exclusive Lock X Write Lock Read and Write NOT compatible with S or X locks

5.2 Lock Compatibility Matrix

Request → S (Shared) X (Exclusive)

Held: S ✔ Compatible ✘ Conflict

Held: X ✘ Conflict ✘ Conflict

Table 5: Lock Compatibility Matrix

5.3 Example: Lock-Based Concurrency Control

T1: S-lock(A) → Read(A) → X-lock(B) → Write(B) → Unlock(A) → Unlock(B)
T2: S-lock(A) → Read(A) → X-lock(A) → [WAIT: T1 holds S-lock on A]

T2 must wait until T1 releases S-lock(A) before it can acquire X-lock(A).

5.4 Two-Phase Locking (2PL)

The most widely used lock-based protocol guaranteeing conflict serializability:

• Phase 1 — Growing Phase: Transaction acquires locks but does NOT release any.
• Phase 2 — Shrinking Phase: Transaction releases locks but does NOT acquire any new ones.
• The point at which the last lock is acquired is called the Lock Point.

Two-Phase Locking (2PL) — Lock Acquisition vs Time

# Locks
Growing Phase Shrinking Phase

Time
Lock Point

Figure 2: Two-Phase Locking — Growing vs Shrinking Phase

Variant Description Key Difference Guarantees

Basic 2PL Two phases; may release before commit

Locks released any time in shrinking
Conflict Serializability

Strict 2PL Exclusive locks held until commit/abortPrevents cascading rollback Conflict-SR + Strict

Rigorous 2PL ALL locks held until commit/abort Even shared locks kept till end Strictest isolation

Conservative 2PL All locks acquired before txn starts No deadlock possible Deadlock-free + CS
Table 6: Variants of Two-Phase Locking
6. Timestamp Ordering Protocol
Timestamp: A unique identifier assigned to each transaction based on the time it starts. TS(Ti) denotes the
timestamp of transaction Ti. Older transactions have smaller timestamps.

Timestamp Ordering Protocol

T1 T2 T3 T4
TS=10 TS=20 TS=30 TS=40
Time

Each transaction assigned a unique timestamp at start; older TS = higher priority

Figure 3: Transactions with Assigned Timestamps

Each data item Q maintains two timestamp values:

• W-timestamp(Q): Largest timestamp of any transaction that successfully wrote Q.

• R-timestamp(Q): Largest timestamp of any transaction that successfully read Q.

6.1 Timestamp Ordering Rules

Operation Condition Action

TS(Ti) < W-timestamp(Q)

Ti reads Q ROLLBACK Ti (too late to read old value)
(younger txn already wrote)

Ti reads Q TS(Ti) ≥ W-timestamp(Q) Allow read; update R-timestamp(Q) = max(R-ts, TS(Ti))

TS(Ti) < R-timestamp(Q)

Ti writes Q ROLLBACK Ti (read expected older value)
(younger txn already read)

TS(Ti) < W-timestamp(Q)

Ti writes Q SKIP write (Thomas Write Rule) or ROLLBACK
(younger txn already wrote)

Ti writes Q TS(Ti) ≥ both R-ts and W-ts Allow write; update W-timestamp(Q) = TS(Ti)
Table 7: Timestamp Ordering Rules

Feature Timestamp Ordering Two-Phase Locking

Mechanism Timestamps (time-based priority) Locks (block-based control)

Deadlock No deadlock possible Deadlocks can occur

Starvation Possible (older txns keep aborting) Possible (waiting indefinitely)

Overhead Timestamp comparison per operation Lock acquisition/release overhead

Serializability Guarantees conflict-serializable Guarantees conflict-serializable

Cascade Rollback Possible Avoided by Strict 2PL

Table 8: Timestamp Ordering vs Two-Phase Locking
7. Recovery Management
Recovery: The process of restoring the database to a consistent state after a failure. Recovery relies
primarily on the log (journal) — a sequential record of all database modifications.

7.1 Types of Failures

Failure Type Cause Scope Recovery Method

Transaction Failure Logic error, divide-by-zero, abort

Single transaction Rollback using undo log

System Failure OS crash, power failure, DBMS

Allcrash
active transactions in RAM Redo
lost committed, undo uncommitted

Media Failure Disk crash, head crash On-disk data corrupted or lost Restore from backup + redo log

7.2 Log-Based Recovery

The write-ahead log (WAL) rule: before modifying a database item on disk, its log record must be written to
stable storage.
Log record format:

Example log for bank transfer:

-- A decremented
-- B incremented

7.3 UNDO vs REDO Operations

Operation When Applied How It Works Purpose

UNDO(Ti) Ti did NOT commit before failure

Restore old_value for all Ti's writes (reverse order)
Remove partial effects of failed txn

REDO(Ti) Ti committed before failure butRe-apply

changes new_value
lost for all Ti's writes (forwardEnsure
order) committed changes are durable

7.4 Checkpointing
A checkpoint is a snapshot point at which the DBMS forces all dirty (modified) buffer pages to disk and records
a checkpoint log entry. This limits how far back the system must scan during recovery.
Checkpoint algorithm:
1. Suspend all new transactions temporarily.
2. Write all log records currently in RAM to stable storage.
3. Write all dirty buffer pages to disk.
4. Write record to the log.
5. Resume transactions.

Recovery only needs to scan log from the last checkpoint!

■ Shadow Paging: An alternative recovery method that maintains two page tables (current and shadow). On
commit, the shadow becomes current. No log needed, but fragmentation is a drawback.
8. Deadlock Handling and Prevention
Deadlock: A situation where two or more transactions are waiting indefinitely for each other to release
locks. None of them can proceed — circular wait!

Classic Example:
T1: X-lock(A) → wants X-lock(B) → WAITING for T2
T2: X-lock(B) → wants X-lock(A) → WAITING for T1

→ Deadlock! T1 waits for T2, T2 waits for T1 — circular dependency.

Deadlock — Wait-For Graph (Cycle = Deadlock)

T4 T5
waits
T1 T2

waits waits

T6
T3
Cycle detected = Deadlock! No cycle = No Deadlock

Figure 4: Wait-For Graph — Cycle indicates Deadlock

8.1 Deadlock Detection

The system periodically constructs a Wait-For Graph (WFG) where each transaction is a node and an edge
Ti→Tj means Ti is waiting for a lock held by Tj. A cycle in the WFG indicates a deadlock.

• If cycle found → select a victim transaction to abort (rollback).

• Victim selection criteria: minimum work done, fewest locks held, or most rollback progress.

8.2 Deadlock Prevention Schemes

Scheme Mechanism Behavior Starvation Risk

Wait-Die
Older txn waits for younger; younger
Ti waits
txn dies
if TS(Ti)
(aborts)
< TS(Tj);
if requesting
otherwise
lockTifrom
Younger
rollsolder.
back.
txns may repeatedly die.
(non-preemptive)

Wound-Wait
Older txn wounds (forces rollback)Tiyounger;
wounds younger
Tj if TS(Ti)
waits
< TS(Tj);
for older.
Ti waits
Younger
if TS(Ti)txns
> TS(Tj).
may be repeatedly wounde
(preemptive)

Timeout Transaction aborted if it waits longer

Simple
than to
a set
implement;
timeout period.
no WFG needed.
Low if timeout is well-tuned.
Table 9: Deadlock Prevention Schemes

8.3 Deadlock Avoidance — Banker's Algorithm Concept

The DBMS checks in advance whether granting a lock request leads to an unsafe state (potential deadlock). If
so, the request is deferred. This is similar to Dijkstra's Banker's Algorithm. However, it requires knowledge of
maximum resource needs in advance, which is impractical for most DBMS workloads.
 Approach Strategy Overhead Deadlock Possible?
Used In

Detection + Recovery Let deadlock occur; detect andPeriodic

resolve WFG constructionYes — then resolved
Most commercial DBMSs

Prevention (Wait-Die/Wound-Wait)
Abort txn before deadlock forms
Per lock request check No Distributed DBMSs

Prevention (Timeout) Abort after waiting too long Very low Theoretically no Simple/embedded DBMSs

Avoidance (Banker's) Never enter unsafe state High (advance knowledge No

needed) OS-level; rare in DBMS
Table 10: Deadlock Handling Strategy Comparison

Quick Revision Summary

Topic Key Point to Remember

ACID Atomicity, Consistency, Isolation, Durability — all four must hold.

States Active → Partially Committed → Committed (success path); → Failed → Aborted (failure path).

Commit Saves all changes permanently; visible to all.

Rollback Undoes all changes; uses undo log; DB restored.

Conflict-SR Precedence graph with no cycle → conflict serializable.

View-SR Broader than Conflict-SR; checks initial read, reads-from, final write.

Locks S-lock: read only; X-lock: read+write; X conflicts with everything.

2PL Growing phase (acquire only) + Shrinking phase (release only) = Conflict-SR.

Strict 2PL Hold X-locks till commit → no cascading rollbacks.

Timestamp No deadlock; older txn has priority; abort younger on conflict.

WAL Log before modifying disk — foundation of all recovery.

Undo/Redo Undo uncommitted txns; Redo committed txns lost in crash.

Checkpoint Flush buffers to disk; limit recovery scan range.

Deadlock Cycle in Wait-For Graph = Deadlock; abort a victim to break it.

Wait-Die Older waits; younger dies. Non-preemptive.

Wound-Wait Older wounds younger (preempts); younger waits for older.