A · Compressed recap
Recoverable: a reader commits after the writer it read from; cascadeless: reads only committed data; strict: no read or write of an item until its writer finishes. Strict ⊂ cascadeless ⊂ recoverable; independent of serializability.
Locks: S (shared, read), X (exclusive, write); only S–S compatible. 2PL (growing then shrinking) ⇒ conflict serializable in lock-point order; can deadlock; basic 2PL can cascade. Strict 2PL (X locks to commit) ⇒ strict schedules; rigorous (all locks to commit) ⇒ commit-order serialisation; conservative (all locks first) ⇒ no deadlock. Deadlocks: cycle in the wait-for graph; prevention with timestamps: wait-die (old waits, young dies), wound-wait (old wounds, young waits); original timestamps prevent starvation.
B · Merged rule card
6.5.1 Recoverable, cascadeless and strict schedules; how they nest
- Tj reads from Ti: Tj reads X last written by Ti.
- Recoverable: reader commits after writer commits.
- Cascadeless: reads only committed data (read after the writer's commit).
- Strict: no read or write of X until its last writer commits/aborts.
- Strict ⊂ cascadeless ⊂ recoverable; serial is strict; independent of serializability.
6.6.1 Shared/exclusive locks; compatibility matrix
- S lock to read (shared), X lock to write (exclusive).
- Compatibility: only S–S compatible.
- Lock manager grants compatible requests, else the requester waits; upgrade S → X waits for other S holders.
- Locking needs a release rule (2PL) to guarantee serializability.
6.6.2 Two-phase locking: growing/shrinking, lock point, guarantees
- 2PL: growing (acquire only) then shrinking (release only); lock point = last acquisition.
- 2PL ⇒ conflict serializable; serial order = order of lock points.
- 2PL does not prevent deadlocks or cascading rollbacks; 2PL schedules ⊊ CS schedules.
- Upgrades count as acquisitions.
6.6.3 Strict, rigorous and conservative 2PL
- Strict 2PL: X locks held to commit/abort → strict schedules.
- Rigorous 2PL: all locks held to commit → serial order = commit order.
- Conservative 2PL: lock everything before starting → deadlock-free; needs predeclaration.
- All give conflict serializability; only conservative avoids deadlock.
6.6.4 Deadlocks: wait-for graph, wait-die, wound-wait, starvation
- Deadlock ⇔ cycle in the wait-for graph (Ti → Tj: Ti waits for Tj); detect, pick a victim, abort.
- Smaller TS = older. Wait-die: old waits, young dies. Wound-wait: old wounds young, young waits.
- Restart with the original TS → no starvation.
- Other: timeouts, no-waiting, global lock ordering.
C · Interleaved GATE-style questions
Q1 · MCQ · 1 mark(s) — Recoverable
W1(A) R2(A) W2(B) C2 C1 is:
- (A) cascadeless
- (B) strict
- (C) recoverable
- (D) not recoverable
Q2 · MCQ · 2 mark(s) — Classes
R1(A) W1(A) C1 R2(A) W2(A) C2 is:
- (A) strict
- (B) cascadeless but not strict
- (C) not recoverable
- (D) recoverable only
Q3 · MCQ · 1 mark(s) — Compatibility
T1 holds X on A; T2 requests S on A. T2:
- (A) aborts T1
- (B) upgrades T1's lock
- (C) is granted
- (D) waits
Q4 · MCQ · 2 mark(s) — 2PL
Which statement about basic 2PL is false?
- (A) The serial order follows the lock points.
- (B) It prevents deadlocks.
- (C) It can produce cascading rollbacks.
- (D) It ensures conflict serializability.
Q5 · MCQ · 1 mark(s) — Variants
Which variant makes the serialisation order equal to the commit order?
- (A) Conservative 2PL
- (B) Wait-die
- (C) Rigorous 2PL
- (D) Basic 2PL
Q6 · NAT · 2 mark(s) — Wound-wait
Wound-wait with TS(T1) = 5, TS(T2) = 15, TS(T3) = 25. Requests: T3 asks for an item held by T1; T1 asks for an item held by T2; T2 asks for an item held by T3. How many of these requests cause a rollback (consider each request on its own)?
Numerical answer: ________
Q7 · MCQ · 1 mark(s) — Deadlock
A deadlock exists exactly when:
- (A) two transactions hold S locks on the same item
- (B) the wait-for graph has a cycle
- (C) the precedence graph has a cycle
- (D) a transaction aborts
Q8 · MSQ · 2 mark(s) — Facts
Which are true?
- (A) Strict 2PL avoids cascading rollbacks.
- (B) Conservative 2PL avoids deadlocks.
- (C) Rigorous 2PL is deadlock-free.
- (D) All 2PL variants guarantee conflict serializability.
D · Answer Vault
Reveal answers when you’re ready
Q1 Answer: (D) · 1 mark(s)
T2 reads from T1 and commits first.
- (A) is wrong: No.
- (B) is wrong: No.
- (C) is wrong: No.
Re-read: Lesson 6.5.1 — Recoverable, cascadeless and strict schedules; how they nest
Q2 Answer: (A) · 2 mark(s)
Serial in effect.
- (B) is wrong: Also strict.
- (C) is wrong: Recoverable.
- (D) is wrong: Stronger.
Re-read: Lesson 6.5.1 — Recoverable, cascadeless and strict schedules; how they nest
Q3 Answer: (D) · 1 mark(s)
Incompatible.
- (A) is wrong: Not by default.
- (B) is wrong: No.
- (C) is wrong: No.
Re-read: Lesson 6.6.1 — Shared/exclusive locks; compatibility matrix
Q4 Answer: (B) · 2 mark(s)
Deadlocks can occur.
- (A) is wrong: True.
- (C) is wrong: True.
- (D) is wrong: True.
Re-read: Lesson 6.6.2 — Two-phase locking: growing/shrinking, lock point, guarantees
Q5 Answer: (C) · 1 mark(s)
All locks held until commit.
- (A) is wrong: Lock-point order.
- (B) is wrong: Not a 2PL variant.
- (D) is wrong: Lock-point order.
Re-read: Lesson 6.6.3 — Strict, rigorous and conservative 2PL
Q6 Answer: 2 · 2 mark(s)
T3 younger than T1: waits. T1 older than T2: wounds T2. T2 older than T3: wounds T3.
Re-read: Lesson 6.6.4 — Deadlocks: wait-for graph, wait-die, wound-wait, starvation
Q7 Answer: (B) · 1 mark(s)
Definition of detection.
- (A) is wrong: Compatible.
- (C) is wrong: That is non-serializability.
- (D) is wrong: No.
Re-read: Lesson 6.6.4 — Deadlocks: wait-for graph, wait-die, wound-wait, starvation
Q8 Answer: (A) (B) (D) · 2 mark(s)
Rigorous 2PL can deadlock.
- (C) is wrong: Can deadlock.
Re-read: Lesson 6.6.3 — Strict, rigorous and conservative 2PL