1.1 Concurrency control concepts

This section covers the basic theory of atomic transactions and serializability. It introduces transactions, schedules, the ACID properties, anomalies that may arise when transactions are not executed atomically, anomalies that may arise when transactions are aborted, various classes of schedules, and the important serializqbility theorem.

Transactions

A transaction is effectively a sequence of read and write operations on atomic database items. A transaction may be incomplete because the (database) system crashes, or because it is aborted by either the system or the user (or application). Complete transactions are committed. Transactions must terminate by either aborting or committing. For performance reasons, transactions (associated with different applications or different users) may be interleaved.

Each transaction should satisfy the ACID properties:

Consistency and isolation are primarily the responsibility of a scheduler; atomicity and durability are primarily the responsibility of a recovery manager.

Schedules

A schedule is a sequence of read, write, abort and commit operations from a set of transactions. Each schedule must preserve the order of the operations in its constituent transactions. A schedule is serial if it is the concatenation of its constituent transactions. A schedule is serialisable if the effect of its committed projection (the restriction to its committed transactions) on any consistent database is identical to that of some serial schedule of its committed transactions.

Example 1 (R&G, Fig. 16.2)

R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B) C2 C1

This schedule is equivalent to transaction~T1 followed by transaction~T2.

To make the above definitions more precise: Two operations on the same data item in different transactions conflict if one of them is a write. Two schedules are (conflict) equivalent if they have the same operations and each pair of conflicting operations occurs in the same order in each schedule. A schedule is (conflict) serialisable if it is (conflict) equivalent to a serial schedule.

Conflicting operations may give rise to the following anomalies:

Aborted transactions cause additional problems.

Example 2 (R&G, Fig. 16.5)

R1(A) W1(A) R2(A) W2(A) R2(B) W2(B) C2 A1

Here, transaction T1 is intended to transfer $100 from A to B, and transaction T2 is intended to increment A and B by 6%. However, T2 has incremented a value of B it should never have read. It should recover from this operation by aborting, but it can't because it has committed. This schedule is unrecoverable. A schedule is recoverable if (after an abort) the database can be restored to a consistent state by undoing the effects of one or more transactions in the schedule. A schedule is recoverable if transactions only commit after all transactions whose changes they read commit.

A schedule avoids cascading aborts (or, is cascade-free) if (after an abort) the database can be restored to a consistent state by undoing the effects of the aborted transaction only. Consider the following schedule (B, H8):

W1(X) W1(Y) R2(U) W2(X) R2(Y) W2(Y) W1(Z) A1

Here, T2 has read Y, which was changed by T1, before T1 committed. So when T1 aborts, T2 has to undo its changes to Y and X before T1 undoes its changes to Y and X.

A schedule avoids cascading aborts if transactions read only the changes of committed transactions (i.e., a transaction does not read an item changed by another transaction until that transaction has committed). Schedules that avoid cascading aborts are (by definition) recoverable.

Suppose T1 changes A from 5 to 6, then T2 changes A from 6 to 7, then T1 aborts. It (operating in isolation) resets A to 5, but then T2's change to A is inadvertently lost even if it commits. (See also B, H9.)

A schedule is called strict if every value written by a transaction $T$ is not read or changed by other transactions until T either aborts or commits.

Strict schedules avoid cascading aborts.

Every serial schedule is strict, but serialisable schedules may or may not be strict, avoid cascading aborts or recoverable!

Serialisability theorem

Given a schedule S, define the serialisation graph SG(S) to have the committed transactions of S as its nodes, and a directed edge from T1 to T2 if T1 and T2 contain conflicting operations O1 and O2 such that O1 precedes O2 in S. Then S is serialisable if and only if SG(S) is acyclic.

References

See Bernstein et al., Chapters 1 and 2, excluding 2.6, for details.

Problems