Recoverability, strict schedules and log-based recovery
Goals and model
Classify schedules using read-from relationships and commit/abort order, explain cascading rollback, and connect atomicity/durability to write-ahead logging. Use r_i(X),w_i(X),c_i,a_i. In the single-version examples, a read sees the latest preceding write. Reads of initial committed values create no dependency on another active transaction. Recovery examples use explicit before/after-image logging assumptions rather than claiming all database engines implement one identical algorithm.
1. Recoverable schedules
If Tj reads a value written by Ti, a recoverable schedule requires Ti to commit before Tj commits. Tj can read before Ti commits and may execute other operations, but must not commit first. If Ti instead aborts, Tj must not commit based on that dirty value; rollback may propagate. Recoverability is about committed transactions not depending on aborted work.
Example: w1(X),r2(X),c1,c2 is recoverable: T2 reads from T1 and c1 precedes c2. It contains a dirty read because r2 precedes c1, so recoverable does not mean cascadeless. In w1(X),r2(X),c2,a1, T2 has already committed using a value that T1 later aborts. This is unrecoverable. Merely having a conflict-equivalent serial order T1 then T2 does not solve the commit-order problem.
Track the actual source of each read. In w1(X),c1,w3(X),c3,r2(X),c2, T2 reads from T3, not from every earlier writer. It therefore has a direct read dependency on T3; any transitive dependencies of T3 may also matter. Do not add a read-from relation just because two operations mention the same item.
2. Cascadeless and strict schedules
A cascadeless schedule permits a read of Ti's written value only after Ti commits. Preventing dirty reads removes the need to abort readers solely because their source transaction aborted. The earlier schedule w1(X),r2(X),c1,c2 is recoverable but not cascadeless. Change it to w1(X),c1,r2(X),c2 and it is cascadeless.
A strict schedule requires that after Ti writes X, no other transaction may read or write X until Ti commits or aborts. It prevents both dirty reads and dirty writes. Strict implies cascadeless, which implies recoverable. The reverse implications do not hold. These are schedule properties; strict two-phase locking is one protocol that can enforce strict schedules, not the definition of strictness.
Counterexample to “cascadeless implies strict”: w1(X),w2(X),c1,c2 has no reads, so it is cascadeless vacuously. It is not strict, because T2 overwrites X before T1 ends. Its conflict graph is acyclic, but overwriting uncommitted data complicates rollback. Distinguish a schedule's recoverability classification from whether a particular recovery algorithm could safely execute it.
Strictness does not alone guarantee conflict serializability. In r1(A),r2(B),w1(B),w2(A),c1,c2, each write is followed by no other transaction's read/write of that item before its writer finishes. Thus the schedule is strict, but the graph has T1→T2 on A and T2→T1 on B. Strict two-phase locking adds the two-phase rule to obtain conflict serializability.
3. Cascading abort trace
Consider w1(X),r2(X),w2(Y),r3(Y),a1. T2 read T1's uncommitted value and T3 read T2's uncommitted output. When T1 aborts, both T2 and T3 must roll back, even if T3 never directly read X. The dependency chain is T1→T2→T3. If a transaction had read only an old committed version under a suitable multiversion protocol, this particular dirty-read chain would not arise; version rules must be stated before changing the classification.
4. Buffer policies explain UNDO and REDO
Data pages modified in memory may reach persistent storage at times different from transaction commit. STEAL permits a page containing an uncommitted update to be written to disk; that means UNDO may be needed after failure. NO-STEAL prevents such uncommitted updates reaching disk under the model, removing that UNDO requirement. FORCE writes all of a transaction's changed data pages durably by commit; NO-FORCE allows committed updates to remain only in memory, so REDO may be needed after failure.
Thus the usual abstract combinations are: STEAL/NO-FORCE requires both UNDO and REDO; STEAL/FORCE requires UNDO; NO-STEAL/NO-FORCE requires REDO; NO-STEAL/FORCE needs neither data-page UNDO nor REDO for this crash model. These statements concern data updates and stated buffer assumptions, not an absence of all metadata, logging, or failure handling. Many practical systems favor STEAL/NO-FORCE for performance and use more sophisticated recovery.
5. Write-ahead logging and a concrete crash
For an update log record <Ti,X,old,new>, the relevant log information must be durably stored before the changed data page is written to persistent storage. This is the write-ahead rule. Before reporting commit under log-based NO-FORCE recovery, make the transaction's required log records and its commit record durable. Data pages themselves need not all be forced at commit. Log durability and data-page durability are different.
Simple worked trace: initially disk X=10,Y=20. Durable log contains <T1,X,10,15>, <commit T1>, <T2,Y,20,25>; no commit for T2. Assume T1's X page was not flushed, but T2's Y page was flushed, then the system crashes. With this before/after-image recovery model, REDO committed T1 to restore X=15 and UNDO uncommitted T2 to restore Y=20. The final intended state is X=15,Y=20. Applying only UNDO loses T1's committed update; applying only REDO leaves T2's uncommitted update.
For multiple updates of an aborted transaction, undo in reverse update order. If T2 changes X from 10 to 12 and then 12 to 19, reversing the second update restores 12 and reversing the first restores 10. Restoring before-images in forward order could leave 12 instead of 10. Real recovery systems may use compensation records, page sequence numbers and repeat-history recovery; do not substitute this simplified trace for a full ARIES specification.
6. Checkpoints and pitfalls
A checkpoint records recovery-relevant progress so that restart need not blindly inspect all historical log records. A simple quiescent checkpoint can coordinate transactions and flushes; fuzzy checkpoints allow concurrent work and require richer metadata. “A checkpoint means every transaction committed” is false. Whether a page or log prefix is flushed depends on the stated checkpoint protocol.
For an exam schedule: identify who each read reads from; compare commit orders for recoverability; compare read times to source commits for cascadelessness; then check both reads and writes following uncommitted writes for strictness. For recovery: mark committed versus incomplete transactions, state buffer policies and durable log boundary, then derive which effects to undo or redo. Never assume an operation in a lost volatile log survived the crash.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. w1(X),r2(X),c1,c2 is:
A. Unrecoverable B. Recoverable but not cascadeless C. Strict D. Cascadeless but not recoverable
Answer: B
A: The source commits before its reader commits.
B: Commit order is safe, but r2 is a dirty read.
C: T2 reads before T1 ends.
D: Cascadeless implies recoverable, and this has a dirty read.
P02. Which implication always holds?
A. Recoverable ⇒ strict B. Cascadeless ⇒ strict C. Strict ⇒ cascadeless D. Conflict serializable ⇒ recoverable
Answer: C
A: Dirty reads can occur in recoverable schedules.
B: Dirty writes can remain in cascadeless schedules.
C: Strictness prevents reading uncommitted writes.
D: Commit order can still be unsafe.
P03. w1(X),w2(X),c1,c2 has no reads. Which classification is correct?
A. Strict B. Cascadeless but not strict C. Not recoverable D. Not cascadeless
Answer: B
A: The second write overwrites uncommitted data.
B: No dirty reads occur, but a dirty write does occur.
C: There are no read-from commit dependencies to violate.
D: Without reads, cascadelessness holds vacuously.
P04. Under the stated buffer-policy model, STEAL and NO-FORCE require support for:
A. UNDO only B. REDO only C. Both UNDO and REDO D. Neither
Answer: C
A: NO-FORCE also permits missing committed pages.
B: STEAL also permits uncommitted pages on disk.
C: STEAL motivates UNDO; NO-FORCE motivates REDO.
D: Both types of crash effects can occur.
P05. Write-ahead logging requires an update log record to be durable before:
A. The changed data page is flushed B. The transaction reads any item C. Every SELECT statement starts D. The DBMS allocates any memory
Answer: A
A: The log must permit recovery of a persisted update.
B: Ordinary reads need not wait for unrelated update logs.
C: SELECT start is not the write-ahead ordering rule.
D: Memory allocation is unrelated to this rule.
P06. T2 writes X:10→12, then X:12→19, and aborts. Correct before-image undo order is:
A. Restore 10, then 12 B. Restore 12, then 10 C. Keep 19 because writes occurred D. Restore only 12
Answer: B
A: Forward undo can leave an intermediate value.
B: Reverse update order restores the original 10.
C: Aborted effects must not remain in this model.
D: One reversal is insufficient for two updates.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in