RDBMS Module 4 — Transactions & Concurrency

Unit 18 · 3 hrs

Transaction Processing

Intro, System Concepts, States, Logging

Definition

A transaction is a logical unit of work — one or more DB operations that must execute atomically and leave the DB in a consistent state.

read(X) — read data item X into memory | write(X) — write variable back to DB

Transaction State Machine

State Descriptions

State	What's Happening
Active	Operations executing normally
Partially Committed	Last op done; data still in memory buffer (not disk yet)
Committed	All changes written permanently to disk ✅
Failed	Error / constraint violation / deadlock — can't continue
Aborted	Rolled back; DB restored to pre-transaction state
Terminated	Transaction lifecycle complete (committed or aborted)

System Log (Transaction Log) ▼ expand

        Write-Ahead Logging (WAL): Log entry MUST be written to disk before actual data is modified. This ensures recovery is always possible.
      

Log Entry	Meaning
[start_transaction, T]	T has begun
[write_item, T, X, old, new]	T wrote X; old→new value
[read_item, T, X]	T read data item X
[commit, T]	T committed successfully
[abort, T]	T was aborted / rolled back

Exam Tip

WAL = write LOG first, then DB. "Partially Committed" ≠ "Committed" — data still in buffer, not disk.

Unit 19 · 1 hr

ACID Properties

A — Atomicity

All or Nothing. Either all ops commit or none do.

Enforced by: Recovery manager (undo log)

Bank transfer: crash after debit → debit is rolled back. No money lost.

C — Consistency

Valid State → Valid State. All constraints hold before and after.

Enforced by: App logic + constraint checking

Transfer ₹2000: Total money in system stays same (₹15K → ₹15K)

I — Isolation

No Interference. Each T runs as if it's the only one.

Enforced by: Concurrency control manager (locking)

T2 sees account balance BEFORE or AFTER T1's transfer — never mid-state

D — Durability

Committed = Permanent. Survives crashes.

Enforced by: WAL + disk storage before ACK

Ticket booked & server crashes → reservation still exists after recovery

Memory Trick

All or nothing · Constraints hold · Isolated from others · Disk survives crash

Unit 20 · 2 hrs

Schedules, Serializability & Recoverability

Core Definitions

Schedule — an ordering of ops from multiple transactions where each T's ops keep their original order.

Serial Schedule — transactions run one after another (no interleaving). Always correct. Low performance.

Serializable Schedule — concurrent but equivalent in effect to some serial schedule. ✅ Correct AND faster.

Conflict Serializability

Two operations conflict if ALL three hold:

Different transactions

Same data item

At least one is WRITE

Pair	Conflicts?
Read – Read	❌ NO — safe
Read – Write	✅ YES
Write – Read	✅ YES
Write – Write	✅ YES

Precedence Graph (Serializability Test)

Create a node for each transaction
Draw edge T1 → T2 if any op of T1 conflicts with a later op of T2
If graph has NO cycle → Conflict Serializable ✅
If graph has a cycle → NOT serializable ❌

Schedule Types Hierarchy (most → least restrictive)

SERIAL

↓

STRICT

No read/write until writer commits OR aborts

↓

CASCADELESS

Read only AFTER writer commits (prevents cascading rollback)

↓

RECOVERABLE

T2 commits AFTER T1 (if T2 read T1's data)

↓

SERIALIZABLE

Schedule Types — Quick Reference

Type	Rule	Avoids
Serial	No interleaving	Everything — always correct
Strict	No R/W until writer commits/aborts	Dirty R/W, cascading rollback, easiest recovery
Cascadeless	Read only after writer commits	Dirty reads, cascading rollback
Recoverable	T2 commits after T1 (if T2 read T1's data)	Committed dirty reads
Serializable	Equivalent to some serial schedule	Incorrect concurrent results

Exam Tip

Every Serial schedule is Strict. Every Strict is Cascadeless. Every Cascadeless is Recoverable. But NOT vice versa!

Dirty Read = reading uncommitted data. Cascading Rollback = chain rollback of multiple Ts that read each other's dirty data.

Unit 21 · 1 hr

Transaction Support in SQL

SQL Transaction Commands

Command	What It Does
BEGIN / START TRANSACTION	Marks start of transaction
COMMIT	Save all changes permanently; release locks
ROLLBACK	Undo ALL changes since BEGIN
SAVEPOINT name	Set named checkpoint for partial rollback
ROLLBACK TO SAVEPOINT name	Undo only to savepoint (keep rest)
RELEASE SAVEPOINT name	Remove a savepoint

Savepoint Example — Bank Transfer

START TRANSACTION;

UPDATE ACCOUNT SET Balance = Balance - 5000 WHERE Acc_No = 'A101';

SAVEPOINT after_debit;          -- checkpoint here

UPDATE ACCOUNT SET Balance = Balance + 5000 WHERE Acc_No = 'B202';

-- if credit fails:
ROLLBACK TO SAVEPOINT after_debit;   -- undo credit only

-- if all ok:
COMMIT;

Isolation Levels & Anomalies

Higher isolation = more correct, lower concurrency

Isolation Level	Dirty Read	Non-Repeatable Read	Phantom Read
READ UNCOMMITTED	✅ Possible	✅ Possible	✅ Possible
READ COMMITTED	❌ Prevented	✅ Possible	✅ Possible
REPEATABLE READ	❌ Prevented	❌ Prevented	✅ Possible
SERIALIZABLE	❌ Prevented	❌ Prevented	❌ Prevented

Dirty Read

Read data written by an uncommitted transaction. Writer rolls back → you read invalid data.

Non-Repeatable Read

Same row read twice → different values because another T committed between your reads.

Phantom Read

Same query run twice → different set of rows (another T inserted/deleted matching rows).

Exam Tip

Dirty Read prevented at READ COMMITTED. Non-Repeatable prevented at REPEATABLE READ. Phantom prevented only at SERIALIZABLE.

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

Unit 22 · 3 hrs

Concurrency Control — 2PL

Concurrency Problems (without control)

Lost Update: T1 and T2 both read X (=1000). T1 writes 1500, T2 writes 1200. T1's update is lost. Should be 1700.

Dirty Read (Temporary Update): T1 writes X, then aborts. T2 already read the modified (dirty) value.

Incorrect Summary: T1 computes SUM while T2 transfers money mid-way. T1 reads inconsistent state.

Lock Types

Shared Lock

For READ. Multiple Ts can hold simultaneously.

Exclusive Lock

For WRITE. Only ONE T can hold at a time.

Lock Compatibility Matrix

Held ↓ / Requested →	S (Read)	X (Write)
S (Read)	✓ Compatible	✗ Block
X (Write)	✗ Block	✗ Block

Two-Phase Locking (2PL)

Guarantees conflict serializability. Transactions acquire and release locks in exactly two phases.

2PL Variants

Variant	When Released	Key Property
Basic 2PL	During execution (shrinking phase)	Serializable; cascading rollbacks possible
Conservative 2PL	All locks acquired BEFORE start	Deadlock-free; low concurrency
Strict 2PL ⭐	X-locks held until commit/abort	Most widely used; prevents dirty reads
Rigorous 2PL	ALL locks held until commit/abort	Strictest; serializes by commit time

⭐ Strict 2PL = most used in practice (MySQL InnoDB default)

Unit 22 cont.

Deadlock & Timestamp Ordering

Deadlock — Definition

Deadlock = Two or more Ts each waiting for the other to release a lock. Circular wait — none can proceed.

1) Why They Wait (Lock-Level View)

2) Wait-for Graph Cycle + Resolution

Detection rule: In a wait-for graph, node = transaction and edge Ti->Tj means Ti is waiting for Tj. If a cycle exists, deadlock exists.

Deadlock Prevention Schemes

Both use timestamps. Older transaction = smaller TS = higher priority.

Wait-Die

If requester is older: it WAITS.

If requester is younger: it DIES (rollback + restart later).

Rule focus: younger requester gets rolled back.

Wound-Wait

If requester is older: it WOUNDS younger holder (abort holder).

If requester is younger: it WAITS.

Rule focus: older requester never waits behind younger.

      Quick example: TS(T1)=5 (older), TS(T2)=20 (younger), and T2 holds a lock needed by T1.

      Wait-Die: T1 waits.

      Wound-Wait: T1 aborts T2 immediately.

Scheme	Older requests younger's lock	Younger requests older's lock
Wait-Die	WAIT	DIE
Wound-Wait	WOUND (abort younger)	WAIT

Memory trick: Wait-Die = requester may die. Wound-Wait = holder may be wounded.

Timestamp-Based Concurrency Control

Alternative to locking. Each T gets unique timestamp TS(T) at start. Conflicts resolved by comparing timestamps — no deadlocks!

Each data item X tracks:

RTS(X)

Latest TS that READ X

WTS(X)

Latest TS that WROTE X

      Thomas's Write Rule: If T tries to write X but WTS(X) > TS(T), the write is obsolete — safely IGNORE it instead of rolling back. Improves performance.
    

2PL vs Timestamp Ordering

Aspect	2PL (Locking)	Timestamp Ordering
Mechanism	Acquire/release locks	TS comparison on each op
Deadlock	Possible ❌	Impossible ✅
Rollbacks	Less frequent	More frequent ❌
Serializability	Guaranteed ✅	Guaranteed ✅
Overhead	Lock management	Timestamp management

Study Mode

Flashcards

Tap to flip • All key exam concepts

∑

Quick Reference

Master Cheatsheet

Everything in One Table

Topic	Key Formula / Rule
ACID-A	All or Nothing → undo log
ACID-C	Valid state → Valid state → constraints
ACID-I	No interference → locking
ACID-D	Committed = permanent → WAL + disk
Conflict	Diff T + Same item + ≥1 Write = CONFLICT
Serializable?	Precedence graph — NO cycle = YES
WAL	Log BEFORE data write
S lock	Read; many can share
X lock	Write; exclusive — no sharing
2PL	Growing phase (acquire) → Lock Point → Shrinking phase (release)
Strict 2PL	Hold X-locks until commit/abort (most common)
Wait-Die	Older waits; Younger dies
Wound-Wait	Older wounds younger; Younger waits
Deadlock detect	Wait-for graph → cycle → abort victim
Thomas Write Rule	Obsolete write → IGNORE (don't abort)
Dirty Read	Prevented at READ COMMITTED+
Non-Repeatable	Prevented at REPEATABLE READ+
Phantom Read	Prevented at SERIALIZABLE only

Quick Terms

Glossary of Shorthands

Fast meaning lookup for symbols and abbreviations used in this module.

Common Symbols

Short Form	Meaning	Example / Context
T	Transaction	T1, T2 are two concurrent transactions
TS(T)	Timestamp of transaction T	Smaller TS means older transaction
RTS(X)	Read Timestamp of item X	Latest TS of any transaction that read X
WTS(X)	Write Timestamp of item X	Latest TS of any transaction that wrote X
R(X)	Read operation on item X	Read item X from DB/buffer
W(X)	Write operation on item X	Write updated value of X to DB
S-lock	Shared lock (read lock)	Multiple transactions may hold it together
X-lock	Exclusive lock (write lock)	Only one transaction can hold it
2PL	Two-Phase Locking	Growing phase then shrinking phase
WAL	Write-Ahead Logging	Write log record before writing data item
WFG	Wait-For Graph	Cycle in WFG indicates deadlock
ACID	Atomicity, Consistency, Isolation, Durability	Core transaction correctness properties
DBMS / RDBMS	Database Management System / Relational DBMS	Software that stores and manages structured data

Memory Tip

T = transaction, TS = transaction age/order, RTS/WTS = latest read/write time on a data item.