Transactions and the ACID Properties

A transaction is a unit of program execution that reads and possibly updates database items and must behave as one indivisible step: either all of its effects persist or none do, and other transactions see it as if it ran alone. A funds transfer that debits one account and credits another is the standard example: stopping half-way, or interleaving it carelessly with another transfer, leaves the database wrong.

The transaction model used by every later concurrency topic is the read and write operations, the ACID properties and the component of the system responsible for each, the transaction states, and the anomalies that uncontrolled interleaving causes. The same model is enough to tell which property or component is at fault in a scenario and which state transitions are possible.

None within the GATE syllabus.

Operations. A transaction $T_i$ accesses data items (a row, a block, a field) through:

Computation on local variables is invisible to the database; only reads and writes matter for correctness of interleavings.

The ACID properties and who enforces them:

Storage model. Atomicity and durability are defined against three kinds of storage. Volatile storage (main memory, the buffer) loses its contents in a system crash. Nonvolatile storage (disk, flash) survives a crash but can fail. Stable storage is an abstraction that never loses data, approximated by keeping several copies on independent nonvolatile devices. The log that recovery relies on must reach stable storage before a transaction is declared committed; this is why a write executed by $W_i(X)$ is not yet durable when it is only in the buffer.

Transaction states (the five states of Korth, Silberschatz and Sudarshan):

After an abort the system may restart the transaction (as a new transaction) if the failure was not caused by its own logic, or kill it. A committed transaction cannot be undone by aborting; its effects can only be reversed by a separate compensating transaction.

Running transactions concurrently improves throughput (CPU and disk work overlap) and response time (short transactions need not wait behind long ones). Without control, interleaving produces these anomalies:

The rest of the concurrency notes define which interleavings are acceptable (Schedules and Serializability) and protocols that allow only those.

A schedule is an interleaving of the operations of a set of transactions that keeps each transaction's own order. A serial schedule runs the transactions one after another; with $n$ transactions there are $n!$ serial schedules. Isolation is formalised as serializability: the schedule must be equivalent to some serial schedule. Consistency of each transaction alone, plus serializability, gives a consistent final state, because a serial schedule is a sequence of consistency-preserving steps.

The number of all schedules grows quickly: transactions with $n_1, \ldots, n_k$ operations have $\frac{(n_1 + \cdots + n_k)!}{n_1! \cdots n_k!}$ interleavings. Two transactions of 3 operations each already have $20$ schedules, of which only 2 are serial.

Example 1: atomicity. $T_1$ transfers 100 from $A = 500$ to $B = 300$: $R_1(A)$, $A := A - 100$, $W_1(A)$, $R_1(B)$, $B := B + 100$, $W_1(B)$. If the system crashes after $W_1(A)$ reaches disk but before $W_1(B)$, the database shows $A = 400$, $B = 300$: the total drops from 800 to 700. Atomicity requires the recovery system to undo $W_1(A)$.

Example 2: lost update. $X = 100$. $T_1$: $X := X - 10$; $T_2$: $X := X + 20$. The interleaving $R_1(X)\, R_2(X)\, W_1(X)\, W_2(X)$ ends with $X = 120$; both serial orders give $110$. The update of $T_1$ is lost. Of the 6 interleavings, the 2 serial ones give 110, the 2 in which $T_2$ writes last after both reads give 120, and the 2 in which $T_1$ writes last after both reads give 90 (the update of $T_2$ is lost).

Example 3: dirty read. $X = 100$. $T_1$ executes $W_1(X)$ with value 90. $T_2$ executes $R_2(X)$ (reads 90), $W_2(X)$ with value 110, and commits. Then $T_1$ aborts. Undoing $T_1$ restores its before-image $X = 100$, which also erases the write of the committed $T_2$; not undoing it leaves 110, a value computed from a write that officially never happened. Either way a committed transaction is wrong, so the schedule must be prevented (Recoverability calls it nonrecoverable).

Example 4: incorrect summary. $A = 50$, $B = 50$. $T_1$ moves 10 from $A$ to $B$ while $T_3$ sums the two. With $R_3(A)$ (reads 50) before $T_1$ runs and $R_3(B)$ (reads 60) after, $T_3$ reports $110$, but every consistent state has total 100.

Example 5: unrepeatable read. $T_2$ reads $X = 100$; $T_1$ writes $X = 90$ and commits; $T_2$ reads $X$ again and sees 90.

Example 6: which property? A system that keeps committed results only in volatile memory violates durability. Two correct transfers that interleave into a wrong total violate isolation. A transfer program that credits 100 but debits 10 violates consistency, and no DBMS component can repair it.

Example 7: counting schedules. $T_1$ has 2 operations and $T_2$ has 3: there are $5!/(2!\,3!) = 10$ schedules, 2 of them serial. Three transactions of 2 operations each have $6!/(2!\,2!\,2!) = 90$ schedules and $3! = 6$ serial ones.

Related material. SQL lets a transaction weaken isolation. The SQL standard defines four isolation levels by the phenomena they allow: READ UNCOMMITTED allows dirty reads, nonrepeatable reads and phantoms; READ COMMITTED prevents dirty reads; REPEATABLE READ also prevents nonrepeatable reads; SERIALIZABLE prevents all three. (Korth 17.8; Elmasri and Navathe 20.6.)

Common misconceptions.