Transactions & Concurrency Control

Concurrent execution is necessary for throughput and dangerous for correctness, and the whole subject is the reconciliation.

The organising fact is that a schedule is correct if it is equivalent to some serial schedule, and every concurrency control protocol is a different way of guaranteeing that equivalence in advance.

Testing a completed schedule is easy: build a precedence graph and look for a cycle. But a scheduler must decide before the schedule is complete, which is why protocols exist. Two-phase locking, timestamp ordering and validation are three answers to the same question.

The second organising fact is that serializability is not enough. A schedule can be serializable and still leave the database unrecoverable after a crash, so recoverability is a separate, orthogonal requirement.

The third is that every protocol buys its guarantee with a specific cost, and knowing which cost belongs to which protocol is most of what the exam tests. Locking risks deadlock; timestamp ordering risks starvation through repeated restarts; validation risks wasted work.

1. Transactions and ACID

A transaction is a unit of work that must appear to happen entirely or not at all.

Atomicity means all operations take effect or none do, and is implemented by the recovery manager using the log.

Consistency means a transaction moves the database from one valid state to another, and is largely the application's responsibility.

Isolation means concurrent transactions do not see each other's intermediate states, and is what concurrency control provides.

Durability means committed effects survive a crash, and is implemented by forcing log records to stable storage.

A transaction passes through five states: active, partially committed after its final operation, committed after the log is forced, failed if it cannot proceed, and aborted after rollback.

2. Schedules and Serializability

A schedule is an interleaving of the operations of several transactions preserving each transaction's internal order.

A serial schedule runs transactions one after another with no interleaving, and is correct by definition.

Two operations conflict if they belong to different transactions, access the same item, and at least one is a write. Read-read pairs never conflict.

Two schedules are conflict equivalent if one can be turned into the other by swapping adjacent non-conflicting operations.

A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

The precedence graph decides this mechanically. Draw a node per transaction, and an edge from $T_i$ to $T_j$ whenever an operation of $T_i$ precedes and conflicts with an operation of $T_j$.

The schedule is conflict serializable exactly when the graph is acyclic, and any topological order of the graph gives an equivalent serial schedule.

View serializability is weaker and strictly larger. Two schedules are view equivalent if they agree on which transaction reads the initial value of each item, on which transaction each read takes its value from, and on which transaction performs the final write of each item.

Every conflict serializable schedule is view serializable, but not conversely. The extra schedules all involve blind writes, meaning a write with no preceding read of the same item by the same transaction.

Testing view serializability is NP-complete, which is why real systems enforce the conflict version.

3. Recoverability

Serializability says nothing about crashes, so a second classification is needed.

A schedule is recoverable if every transaction commits only after every transaction it read from has committed. Otherwise a committed transaction may have read a value that is later rolled back, and no repair is possible.

A schedule avoids cascading rollback if a transaction reads only values written by committed transactions. This is strictly stronger than recoverability and prevents one abort from forcing a chain of others.

A schedule is strict if no transaction reads or writes an item until the transaction that last wrote it has committed or aborted. Strictness makes rollback simple, because the before-image can be restored directly.

The containment is strict inside cascadeless inside recoverable, and each stronger property costs more concurrency.

4. Lock-Based Protocols

A shared lock permits reading; an exclusive lock permits writing. Shared locks are compatible with each other and with nothing else.

Two-phase locking has a growing phase in which locks are only acquired and a shrinking phase in which they are only released.

Two-phase locking guarantees conflict serializability. The point at which a transaction acquires its last lock is its lock point, and ordering transactions by lock point gives an equivalent serial order.

It guarantees nothing else. It does not prevent deadlock, and it does not guarantee recoverability, because a transaction may release locks and let others read its values before it commits.

Strict two-phase locking holds all exclusive locks until commit or abort. This makes schedules strict and therefore cascadeless and recoverable, and is what most systems implement.

Rigorous two-phase locking holds all locks, shared included, until commit, which additionally makes the commit order the serialization order.

Conservative two-phase locking acquires all locks before starting and is the only variant that is deadlock free, but it requires knowing the entire access set in advance and is rarely practical.

Deadlock handling has two prevention schemes based on timestamps, and their names are worth reading carefully.

Wait-die is non-preemptive: an older transaction waits for a younger one, and a younger requesting from an older dies and restarts.

Wound-wait is preemptive: an older transaction wounds the younger one, forcing it to abort, and a younger one requesting from an older waits.

In both, the restarted transaction keeps its original timestamp, which is what prevents starvation, since it eventually becomes the oldest.

5. Timestamp Ordering

Each transaction receives a timestamp on arrival, and the protocol enforces the serial order of those timestamps.

Each item carries a read timestamp and a write timestamp, recording the largest timestamp of any transaction that has read or written it.

A read by $T$ is rejected if the item's write timestamp exceeds $T$'s timestamp, because $T$ would be reading a value written by a transaction that should come after it. $T$ is rolled back and restarted with a new timestamp.

A write by $T$ is rejected if either timestamp on the item exceeds $T$'s, for the same reason.

Thomas's write rule relaxes the second case. If only the write timestamp exceeds $T$'s, the write is simply ignored rather than causing a rollback, because a later write has already superseded it.

Thomas's write rule produces schedules that are view serializable but not conflict serializable, which is one of the few practical uses of the wider class.

Timestamp ordering is deadlock free, since nothing ever waits, but it can starve a transaction that is repeatedly restarted.

6. Isolation Levels and Recovery

SQL defines four isolation levels by which anomalies they permit.

A dirty read reads uncommitted data. A non-repeatable read gets different values for the same row twice. A phantom is a row appearing in a repeated range query.

Preventing phantoms requires locking the range rather than the rows, since the offending row does not exist when the lock would be taken.

Recovery relies on a log with write-ahead logging. A log record describing a change must reach stable storage before the change itself does.

Undo removes the effects of transactions that had not committed, using the before-images.

Redo reapplies the effects of transactions that had committed, using the after-images, since their pages may not have been written.

A checkpoint records which transactions are active and forces dirty pages, bounding how far back recovery must scan.

7. Worked Examples

Example 1. Determine whether this schedule is conflict serializable, and if so give an equivalent serial order.

The schedule is $r_1(A)$, $w_2(A)$, $r_3(B)$, $w_1(B)$, $r_2(C)$, $w_3(C)$.

Find every conflicting pair.

On item $A$: $r_1(A)$ precedes $w_2(A)$, and a read conflicts with a later write. Edge from $T_1$ to $T_2$.

On item $B$: $r_3(B)$ precedes $w_1(B)$. Edge from $T_3$ to $T_1$.

On item $C$: $r_2(C)$ precedes $w_3(C)$. Edge from $T_2$ to $T_3$.

The graph has edges $T_1\to T_2$, $T_2\to T_3$, $T_3\to T_1$, which is a cycle.

The schedule is not conflict serializable.

Note that no single pair is problematic. Each edge individually is satisfiable; the contradiction only appears when all three are combined, which is exactly why the graph test exists rather than a rule about pairs.

Example 2. Show that this schedule is view serializable but not conflict serializable.

The schedule is $w_1(A)$, $r_2(A)$, $w_2(A)$, $w_3(A)$, and there are no other operations.

Build the precedence graph.

$w_1(A)$ before $r_2(A)$ gives $T_1\to T_2$. $w_1(A)$ before $w_2(A)$ gives $T_1\to T_2$ again. $r_2(A)$ before $w_3(A)$ gives $T_2\to T_3$. $w_2(A)$ before $w_3(A)$ gives $T_2\to T_3$.

No cycle appears here, so this particular schedule is in fact conflict serializable, equivalent to $T_1,T_2,T_3$.

Now modify it to $w_1(A)$, $r_2(A)$, $w_3(A)$, $w_2(A)$.

The graph now gains $T_3\to T_2$ from $w_3(A)$ preceding $w_2(A)$, alongside $T_2\to T_3$ from $r_2(A)$ preceding $w_3(A)$.

That is a cycle, so the schedule is not conflict serializable.

Check view equivalence against the serial order $T_1,T_3,T_2$.

Initial reads: the only read is $r_2(A)$, which in the schedule reads the value written by $T_1$. In the serial order $T_1,T_3,T_2$, transaction $T_2$ would read what $T_3$ wrote, so this order fails.

Try $T_1,T_2,T_3$. There $T_2$ reads from $T_1$, matching. But the final write of $A$ in the serial order is $T_3$'s, while in the schedule it is $T_2$'s. So this order fails too.

Neither works, so this schedule is not view serializable either.

The genuine example needs the final writer to line up. Take $r_1(A)$, $w_2(A)$, $w_1(A)$, $w_3(A)$.

The precedence graph has $T_1\to T_2$ from the read before the write, and $T_2\to T_1$ from $w_2(A)$ before $w_1(A)$, which is a cycle, so it is not conflict serializable.

Now compare with the serial order $T_1,T_2,T_3$. In both, $T_1$ reads the initial value of $A$, and in both the final write of $A$ is $T_3$'s. No other transaction reads $A$ at all, so the read-from condition is vacuous.

The schedules are view equivalent, so this one is view serializable without being conflict serializable, and the writes by $T_2$ and $T_3$ are both blind.

The takeaway is the diagnostic rule. A schedule that is view serializable but not conflict serializable must contain a blind write, a write by a transaction that never read that item. Look for one before attempting the harder test.

Example 3. Three transactions have 2, 3 and 3 operations respectively. How many schedules are possible in total, and how many are serial?

A schedule is an interleaving preserving each transaction's internal order.

The count is the multinomial coefficient, choosing which positions in the sequence belong to which transaction.

Total operations are $2+3+3=8$.

The number of schedules is $\frac{8!}{2!\cdot 3!\cdot 3!}$.

Computing: $8!=40320$, and $2!\cdot 3!\cdot 3!=2\cdot 6\cdot 6=72$.

So there are $40320/72=560$ schedules.

The number of serial schedules is $3!=6$, one per ordering of the transactions.

The general formula for $n$ transactions with $m$ operations each is $\frac{(nm)!}{(m!{)}^n}$, and the serial count is always $n!$.

Notice how few schedules are serial: 6 out of 560, about one percent. The overwhelming majority are interleaved, and the protocols exist to keep only the correct ones among them.

Example 4. Trace two transactions under strict two-phase locking and show that deadlock is possible.

$T_1$ reads $A$ then writes $B$. $T_2$ reads $B$ then writes $A$.

Under strict two-phase locking, both hold exclusive locks until commit.

Step 1: $T_1$ requests a shared lock on $A$ and gets it.

Step 2: $T_2$ requests a shared lock on $B$ and gets it.

Step 3: $T_1$ requests an exclusive lock on $B$, and it must wait, because $T_2$ holds a shared lock and shared is incompatible with exclusive.

Step 4: $T_2$ requests an exclusive lock on $A$. It must wait, because $T_1$ holds a shared lock on $A$.

Each waits for a lock the other holds, and neither will release before committing, which it cannot do while waiting. That is deadlock.

Two-phase locking guarantees serializability, not deadlock freedom, and this example is the standard proof.

Now apply wound-wait, assuming $T_1$ is older.

At step 3, $T_1$ is older and requests from the younger $T_2$, so $T_1$ wounds $T_2$, aborting it and taking the lock. $T_1$ proceeds and commits, and $T_2$ restarts with its original timestamp.

Under wait-die instead, at step 3 the older $T_1$ requesting from the younger $T_2$ simply waits. At step 4 the younger $T_2$ requests from the older $T_1$, so $T_2$ dies and restarts, releasing its lock on $B$ and letting $T_1$ proceed.

Both schemes break the cycle, and in both the restarted transaction keeps its timestamp, which guarantees it eventually becomes old enough to win.

Example 5. Under basic timestamp ordering, transaction $T_2$ with timestamp 20 attempts to write item $X$, which has read timestamp 25 and write timestamp 10. Then $T_3$ with timestamp 15 attempts to write $X$ after $T_2$'s attempt is resolved. Trace both.

For $T_2$'s write, check both timestamps on $X$.

The read timestamp is 25, which exceeds $T_2$'s timestamp of 20.

This means some transaction with timestamp 25 has already read $X$, and it read the older value. If $T_2$ writes now, that reader would have needed to see $T_2$'s value, since 20 comes before 25 in the enforced order.

The write is rejected and $T_2$ is rolled back, restarting with a fresh, larger timestamp.

Now $T_3$ with timestamp 15 attempts to write $X$, where the read timestamp is 25 and the write timestamp is 10.

Again the read timestamp exceeds $T_3$'s, so under the basic rule $T_3$ is also rolled back.

Now change the scenario so that $X$ has read timestamp 12 and write timestamp 30, and $T_3$ with timestamp 15 attempts a write.

The read timestamp 12 does not exceed 15, so no reader is violated.

But the write timestamp 30 exceeds 15, meaning a later transaction has already written $X$.

Under the basic rule, $T_3$ is rolled back.

Under Thomas's write rule, the write is simply ignored and $T_3$ continues.

The justification is that $T_3$'s value would be immediately overwritten by the transaction with timestamp 30 in any serial order consistent with the timestamps, so writing it changes nothing observable.

This is where view serializability earns its keep, since the resulting schedule is view serializable without being conflict serializable.

Example 6. Classify this schedule as recoverable, cascadeless or strict.

The schedule is $w_1(A)$, $r_2(A)$, $w_2(B)$, $c_1$, $c_2$, where $c$ denotes commit.

Check recoverability. $T_2$ reads $A$ from $T_1$, and $T_1$ commits at position 4, before $T_2$ commits at position 5.

A transaction commits only after the one it read from, so the schedule is recoverable.

Check cascadelessness. $T_2$ reads $A$ at position 2, but $T_1$ does not commit until position 4.

$T_2$ read uncommitted data, so if $T_1$ had aborted, $T_2$ would have had to abort too.

The schedule is not cascadeless.

Check strictness. Since it is not cascadeless, it cannot be strict, as strict is the strongest of the three.

The classification is recoverable but not cascadeless.

To make it cascadeless, move $c_1$ before $r_2(A)$, giving $w_1(A)$, $c_1$, $r_2(A)$, $w_2(B)$, $c_2$.

That version is also strict, because no transaction reads or writes an item that an uncommitted transaction last wrote.

The general containment worth memorising: strict implies cascadeless implies recoverable, and each step costs concurrency.

Summary

A schedule is correct if it is equivalent to some serial one, and every protocol guarantees that equivalence in advance rather than testing it afterwards.

ACID names four properties with four different implementers: recovery gives atomicity and durability, the application gives consistency, and concurrency control gives isolation.

Two operations conflict if they are from different transactions on the same item with at least one write. A schedule is conflict serializable exactly when its precedence graph is acyclic, and a topological order gives the equivalent serial schedule.

View serializability is strictly weaker, the extra schedules all involve blind writes, and testing it is NP-complete.

Recoverability is orthogonal to serializability. Strict implies cascadeless implies recoverable, and each step costs concurrency.

Two-phase locking guarantees conflict serializability through the lock point, but guarantees neither deadlock freedom nor recoverability. Strict two-phase locking holds exclusive locks until commit and gives strictness; rigorous holds all locks and makes commit order the serialization order; conservative acquires everything up front and is the only deadlock-free variant.

Wait-die is non-preemptive and wound-wait is preemptive, and in both the restarted transaction keeps its timestamp so it cannot starve.

Timestamp ordering enforces the timestamp order using per-item read and write timestamps, is deadlock free, and can starve. Thomas's write rule ignores an obsolete write instead of rolling back, producing view serializable schedules that are not conflict serializable.

The four isolation levels are distinguished by dirty reads, non-repeatable reads and phantoms, and preventing phantoms requires range locking.

The number of schedules for $n$ transactions of $m$ operations is $(nm)!$ over $(m!{)}^n$, of which $n!$ are serial.

Recovery uses write-ahead logging, undoing uncommitted transactions and redoing committed ones, with checkpoints bounding the scan.