Multiple granularity, validation-based protocol, log-based recovery

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Under the Thomas write rule, what happens to a write with TS(Ti) < WTS(X) and TS(Ti) ≥ RTS(X)? from Lesson 6.7.1
2. What is wound-wait? from Lesson 6.6.4
3. Which ACID properties does the recovery manager ensure? from Lesson 6.1.1

1 · The Hook

Three practical topics finish Phase 6. Should a transaction that scans a whole table lock it row by row? (Multiple granularity.) What if conflicts are rare: why lock at all? (Validation.) And after a crash, how does the DBMS know what to undo and redo? (Log-based recovery.) GATE asks about each in short questions.

2 · Predict First

A transaction T1 holds an exclusive lock on one row of STUDENT. T2 wants a shared lock on the whole STUDENT table. Should it be granted? How can the DBMS tell quickly, without checking every row?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

No: T2 would read the row T1 is writing. To avoid checking every row, T1 first places an intention lock (IX) on the table, which says "someone below is writing". T2's request for S on the table conflicts with IX and waits.

Multiple granularity locking

Data is a hierarchy: database → files (tables) → pages → records. A lock on a node implicitly locks everything below it. Intention modes signal what is happening below:

• IS: intend to take S locks below.
• IX: intend to take X locks below.
• SIX: S on this node + IX (read everything, write some parts).

Rules: lock from the root down (to take S or IS on a node, hold IS or IX on its parent; to take X, IX or SIX, hold IX or SIX on the parent); release bottom-up; obey 2PL.

Validation-based (optimistic) concurrency control

Each transaction runs in three phases:

1. Read phase: read the database, write only to private local copies.
2. Validation phase: check that applying its writes keeps serializability (no conflict with transactions that validated meanwhile).
3. Write phase: if valid, copy local writes to the database; otherwise restart.

Serialisation order = validation order. Good when conflicts are rare (mostly-read workloads); no locks, no deadlocks, but wasted work on restarts.

Log-based recovery

The log (on stable storage) records every change:

• ⟨Ti start⟩, ⟨Ti, X, old value, new value⟩, ⟨Ti commit⟩, ⟨Ti abort⟩.

Write-ahead logging (WAL): a change's log record must reach stable storage before the changed data does, and a transaction's commit record before it is declared committed.

Two update strategies:

Checkpoints limit the work: periodically flush all modified data and write ⟨checkpoint⟩ (with the list of active transactions). After a crash, transactions committed before the checkpoint need nothing; those committed after it are redone; those not committed are undone.

Recovery example

Log: ⟨T1 start⟩ ⟨T1, A, 10, 20⟩ ⟨T1 commit⟩ ⟨checkpoint⟩ ⟨T2 start⟩ ⟨T2, B, 5, 8⟩ ⟨T3 start⟩ ⟨T3, C, 1, 2⟩ ⟨T2 commit⟩ — crash.

• T1 committed before the checkpoint: nothing to do.
• T2 committed after it: redo (B = 8).
• T3 never committed: undo (C = 1).

4 · Visual

log:  T1 start | T1 A 10->20 | T1 commit | CHECKPOINT | T2 start | T2 B 5->8 | T3 start | T3 C 1->2 | T2 commit | CRASH
                                               ^
        before checkpoint: done           after: T2 committed -> REDO    T3 not committed -> UNDO

5 · Worked Examples

Example 1 Easy

A transaction wants to read the whole STUDENT table and update a few rows. Which lock should it take on the table?

Solution

SIX: S on the table (read all) plus IX (it will take X locks on some rows).

Example 2 Medium

Under deferred update, a transaction aborts before commit. What must recovery do for it?

Solution

Nothing: it never changed the database (its writes were deferred until commit).

Example 3 GATE

Log: ⟨T1 start⟩ ⟨T1, X, 5, 7⟩ ⟨T2 start⟩ ⟨T2, Y, 2, 4⟩ ⟨T1 commit⟩ ⟨T3 start⟩ ⟨T3, X, 7, 9⟩ — crash (no checkpoint, immediate update). Which transactions are redone and which undone? Final X and Y?

Solution

Redo T1 (committed): X = 7. Undo T2 and T3 (not committed): Y back to 2, X back to 7 (T3's old value). Final X = 7, Y = 2.

8 · Connect the Dots

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Granularity

Which pair of locks on the same table is compatible?

1. (A) SIX and IX
2. (B) IX and S
3. (C) IS and IX
4. (D) X and IS

Q2 · MCQ · 1 mark(s) — Optimistic

In validation-based concurrency control, the serialisation order is the order of:

1. (A) start times
2. (B) commits of readers
3. (C) validation
4. (D) first reads

Q3 · MCQ · 1 mark(s) — WAL

The write-ahead logging rule requires that:

1. (A) logs are optional with checkpoints
2. (B) the log record of a change reaches stable storage before the changed data
3. (C) the log is written only at commit
4. (D) data is written before the log

Q4 · MSQ · 2 mark(s) — Recovery

Log (immediate update): ⟨T1 start⟩ ⟨T1, A, 1, 2⟩ ⟨checkpoint⟩ ⟨T1 commit⟩ ⟨T2 start⟩ ⟨T2, B, 3, 4⟩ — crash. Which actions are needed?

1. (A) Redo T2
2. (B) Redo T1
3. (C) Undo T2
4. (D) Undo T1

Q5 · MCQ · 1 mark(s) — Deferred update

Deferred update recovery needs:

1. (A) undo only
2. (B) undo and redo
3. (C) redo only
4. (D) neither

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

multiple granularity lockingintention locks IS, IX, SIXvalidation-based (optimistic) protocolread / validation / write phaseslogwrite-ahead logging (WAL)deferred updateimmediate updateundoredocheckpoint