Question 8 of 8: Transactions, ACID, and scheduling

Question 8: Transactions, ACID, and scheduling (5+5+(4+6)=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) ACID. Atomicity — a transaction's effects are all-or-nothing: either every one of its operations is reflected in the database, or none are (a failure partway through must leave no partial trace). Consistency — a transaction takes the database from one state satisfying all integrity constraints to another state also satisfying them (the DBMS enforces declared constraints; preserving application-level invariants is the transaction author's responsibility). Isolation — concurrently executing transactions must not observe each other's intermediate, uncommitted state; the observable effect of running several transactions concurrently must be equivalent to running them in some serial order. Durability — once a transaction commits, its effects survive any subsequent system failure (crash, power loss), typically by having been recorded on stable (non-volatile) storage before the commit is acknowledged.

(b) How A, I, D (not C) can hurt performance.

• Atomicity requires the ability to UNDO a partially-completed transaction's writes. Every write must therefore be logged (a before-image, or an equivalent undo record) before or as it happens, adding I/O and bookkeeping overhead to every single write, whether or not that transaction ever actually aborts; when an abort does occur, rolling back every already-applied write costs additional time proportional to the work already done.
• Isolation is normally enforced with concurrency control — locking makes transactions BLOCK and wait whenever they need an item another active transaction already holds incompatibly, directly reducing throughput and risking deadlocks whose detection/resolution (rollback-and-retry of a victim transaction) is itself extra overhead; optimistic or multiversion schemes avoid blocking but instead pay validation and version-storage costs, and can force late ABORTS-and-retries when a conflict is only discovered at commit time.
• Durability requires that a committed transaction's changes survive a crash, normally by force-writing (flushing) its log records to stable storage before acknowledging the commit. That synchronous disk write adds latency to every single commit and can become the system's throughput ceiling under heavy commit rates — mitigated in practice by group-commit batching, but never eliminated.

(c) Schedule $w_1(x)\ r_2(x)\ w_2(x)\ commit_2\ commit_1$ from non-strict 2PL.

1. (i) Serializability, via the precedence graph. The only item touched is $x$; every operation on it is either a write or reads a value another transaction wrote, so BOTH cross-transaction pairs ($w_1(x)$ before $r_2(x)$, and $w_1(x)$ before $w_2(x)$) are conflicts, and both place $T_1$ before $T_2$. The precedence graph has a single edge $T_1\to T_2$ with no cycle. $$\boxed{\text{Conflict-serializable, equivalent to the serial order } T_1;T_2}$$
2. (ii) Is it in commit order? "In commit order" (needed for a RECOVERABLE schedule) requires: whenever $T_j$ reads a value $T_i$ wrote, $T_i$ must COMMIT before $T_j$ commits. Here $T_2$'s read of $x$ ($r_2(x)$) reads the value $T_1$ just wrote — so recoverability requires $commit_1$ before $commit_2$. The schedule instead commits $T_2$ FIRST, then $T_1$. $$\boxed{\text{NOT in commit order}}$$

This is precisely the textbook gap in plain (non-strict) 2PL: 2PL's two-phase locking rule guarantees conflict-serializability, but says nothing about WHEN a transaction releases its locks relative to its own commit — a non-strict scheme may release $T_1$'s lock on $x$ (allowing $T_2$'s read) before $T_1$ itself commits. If $T_1$ were to abort AFTER $T_2$ has already committed, $T_2$'s committed result depends on a write that no longer exists — an unrecoverable state that no rollback can fix. Strict 2PL (hold every lock until the transaction's own commit/abort) is what actually prevents this by construction, since it would force $r_2(x)$ to wait until $commit_1$.

(d) REPEATABLE READ — schedule $r_1(x)\ r_1(y)\ w_1(x)\ r_2(y)\ r_2(x)\ w_1(y)\ commit_2\ commit_1$.

Given. REPEATABLE READ implemented via 2PL: every lock a transaction acquires (shared for a read, exclusive for a write, upgraded in place when the same transaction later writes an item it already read) is held until that transaction ends — this is exactly what "repeatable" means: no other transaction can be allowed to change a value once this transaction has read it.

Find. What actually happens when the operations are attempted in the order printed.

1. Trace $T_1$'s locks up to $w_1(y)$. $r_1(x)$: $T_1$ acquires $S(x)$. $r_1(y)$: $T_1$ acquires $S(y)$. $w_1(x)$: $T_1$ upgrades to $X(x)$ — succeeds immediately, since $T_1$ is the sole holder of $x$.
2. $r_2(y)$ succeeds. $T_2$ requests $S(y)$; $T_1$'s lock on $y$ is still Shared (not yet upgraded), and Shared/Shared is compatible — $T_2$ acquires $S(y)$ alongside $T_1$.
3. $r_2(x)$ BLOCKS. $T_2$ requests $S(x)$; $T_1$ holds $X(x)$ (Exclusive, from its earlier upgrade) — Shared/Exclusive conflicts, so $T_2$ must wait for $T_1$ to release $x$. Under REPEATABLE-READ/2PL, $T_1$ will not release ANY lock until it commits or aborts.
4. $w_1(y)$ ALSO blocks. $T_1$ next needs to upgrade its $S(y)$ to $X(y)$ for the write — but $T_2$ ALSO now holds $S(y)$ (from step 2), and an upgrade requires being the sole holder. $T_1$ must wait for $T_2$ to release $y$.
5. Circular wait → deadlock. $T_2$ is waiting on $T_1$ (to release $x$); $T_1$ is waiting on $T_2$ (to release $y$). Neither can proceed to release anything until the other does. $$\boxed{\text{DEADLOCK}}$$

So the schedule as literally printed cannot run to completion under REPEATABLE READ: the DBMS's deadlock detector (periodic wait-for-graph cycle check, or a timeout) will pick a victim — conventionally the transaction that has done less work or was started more recently — abort it, release its locks, and let the other proceed; the aborted transaction is then resubmitted. Note this is a genuinely different (and more severe) outcome than Question 8(c)'s non-strict-2PL schedule, which completed but was merely unrecoverable — here, holding locks to commit-time (what REPEATABLE READ/strict 2PL requires) prevents the earlier problem but introduces the possibility of deadlock instead, illustrating the classic trade-off between the two hazards.