A · Compressed recap
Timestamp ordering: each transaction has TS; each item has RTS and WTS. Read aborts if TS < WTS; write aborts if TS < RTS or TS < WTS; otherwise update RTS/WTS. Thomas write rule ignores obsolete writes (TS < WTS, TS ≥ RTS) and admits some view-serializable schedules. TO is deadlock-free, conflict serializable, may starve, is not automatically recoverable.
Multiple granularity uses IS, IX, SIX intention locks top-down. Optimistic control: read, validate, write; order = validation order. Recovery: WAL; deferred update → redo only; immediate update → undo + redo; checkpoints limit redo to transactions committed after the checkpoint and undo the uncommitted ones.
B · Merged rule card
6.7.1 Timestamp ordering protocol; Thomas write rule
- TS(Ti) at start; RTS(X), WTS(X) per item.
- read(X): abort if TS < WTS(X); else RTS = max(RTS, TS).
- write(X): abort if TS < RTS(X); abort if TS < WTS(X) (Thomas: ignore); else WTS = TS.
- Basic TO: CS, deadlock-free, starvation possible, not necessarily recoverable. Thomas: VS schedules allowed.
6.8.1 Multiple granularity, validation-based protocol, log-based recovery
- Multiple granularity: IS, IX, S, SIX, X; lock root-down, release bottom-up; IS/IX compatible; IX vs S incompatible.
- Optimistic: read → validate → write; order = validation order; good for rare conflicts.
- Log records + WAL. Deferred update: redo only. Immediate update: undo + redo.
- Checkpoint: committed before → nothing; committed after → redo; uncommitted → undo (old values).
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — TO
TS(T1) = 7, RTS(X) = 9, WTS(X) = 4. T1 issues write(X). Basic TO:
- (A) ignores it
- (B) aborts T1
- (C) executes it
- (D) makes T1 wait
Q2 · MCQ · 1 mark(s) — TO
TS(T1) = 7, RTS(X) = 9, WTS(X) = 4. T1 issues read(X). Basic TO:
- (A) executes it; RTS stays 9
- (B) aborts T1
- (C) executes it; RTS becomes 7
- (D) ignores it
Q3 · NAT · 2 mark(s) — Trace
TS(T1) = 1, TS(T2) = 2, TS(T3) = 3. Basic TO on R3(A) W1(A) W2(B) R1(B). How many transactions abort?
Numerical answer: ________
Q4 · MCQ · 2 mark(s) — Properties
Which is guaranteed by basic TO but not by basic 2PL?
- (A) Freedom from deadlock
- (B) Conflict serializability
- (C) No starvation
- (D) Recoverability
Q5 · MCQ · 1 mark(s) — Granularity
To set an X lock on a row, a transaction must hold on the row's table:
- (A) IS
- (B) nothing
- (C) S
- (D) IX (or SIX)
Q6 · MSQ · 2 mark(s) — Recovery
Immediate update, log: ⟨T1 start⟩ ⟨T1, X, 3, 6⟩ ⟨T1 commit⟩ ⟨T2 start⟩ ⟨T2, X, 6, 8⟩ — crash, no checkpoint. Which are true?
- (A) T2 is undone.
- (B) T1 is redone.
- (C) Final X = 8.
- (D) Final X = 6.
Q7 · MCQ · 1 mark(s) — Optimistic
Validation-based protocols work best when:
- (A) transactions are long and write-heavy
- (B) conflicts are frequent
- (C) deadlocks are common
- (D) conflicts are rare
Q8 · MCQ · 1 mark(s) — Thomas
The Thomas write rule allows schedules that are:
- (A) view serializable but possibly not conflict serializable
- (B) not serializable at all
- (C) only strict
- (D) only serial
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (B) · 1 mark(s)
TS < RTS: a younger transaction already read X.
- (A) is wrong: Thomas ignores only when TS < WTS and TS ≥ RTS.
- (C) is wrong: Too late.
- (D) is wrong: TO never waits.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule
Q2 Answer: (A) · 1 mark(s)
7 ≥ WTS 4: read allowed; RTS = max(9, 7) = 9.
- (B) is wrong: No younger write.
- (C) is wrong: RTS keeps the maximum.
- (D) is wrong: Reads are not ignored.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule
Q3 Answer: 1 · 2 mark(s)
R3(A): RTS(A) = 3. W1(A): 1 < 3 → T1 aborts; R1(B) skipped. W2(B) fine.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule
Q4 Answer: (A) · 2 mark(s)
TO never waits.
- (B) is wrong: Both guarantee it.
- (C) is wrong: Neither.
- (D) is wrong: Neither.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule
Q5 Answer: (D) · 1 mark(s)
Intention to write below.
- (A) is wrong: IS only allows S below.
- (B) is wrong: Required.
- (C) is wrong: Wrong mode.
Re-read: Lesson 6.8.1 — Multiple granularity, validation-based protocol, log-based recovery
Q6 Answer: (A) (B) (D) · 2 mark(s)
Redo T1 (X = 6), undo T2 (X back to 6).
- (C) is wrong: T2 is undone.
Re-read: Lesson 6.8.1 — Multiple granularity, validation-based protocol, log-based recovery
Q7 Answer: (D) · 1 mark(s)
Few restarts.
- (A) is wrong: Costly restarts.
- (B) is wrong: Many restarts.
- (C) is wrong: Not related.
Re-read: Lesson 6.8.1 — Multiple granularity, validation-based protocol, log-based recovery
Q8 Answer: (A) · 1 mark(s)
Ignoring obsolete blind writes yields view-equivalent results.
- (B) is wrong: Still serializable.
- (C) is wrong: No.
- (D) is wrong: No.
Re-read: Lesson 6.7.1 — Timestamp ordering protocol; Thomas write rule