Transactions and Serializability

A transaction is a sequence of database operations that must behave as one indivisible unit of work. Transferring ₹500 from account A to B reads and writes both balances; it must never happen halfway.

ACID

Transaction states

• Active: the transaction is executing its reads and writes.
• Partially committed: its last operation has run, but its changes may still be only in memory.
• Committed: the commit record is safely on disk; the changes are now permanent.
• Failed: normal execution cannot continue (an error, a deadlock, a crash).
• Aborted: all its changes have been rolled back; it can be restarted or killed.

Schedules

A schedule is the order in which the operations of concurrent transactions are executed. We write R1(A) for "transaction T1 reads A", W2(B) for "T2 writes B", and C1 for "T1 commits".

• A serial schedule runs transactions one after another with no interleaving. It is always correct, but slow.
• A concurrent (interleaved) schedule mixes their operations. It is correct if it is serializable: equivalent to some serial schedule.

Two transactions with m and n operations can be interleaved in C(m + n, m) ways (keeping each transaction's own order); with 3 and 2 operations that is C(5, 3) = 10 schedules.

Problems that bad interleavings cause:

Conflict serializability

Two operations conflict if they belong to different transactions, access the same item, and at least one is a write: R–W, W–R or W–W. Two reads never conflict.

Swapping adjacent non-conflicting operations does not change the result. A schedule is conflict serializable if such swaps can turn it into a serial schedule.

Test with a precedence graph: draw a node for each transaction, and an edge Ti → Tj whenever an operation of Ti conflicts with a later operation of Tj. The schedule is conflict serializable if and only if the graph has no cycle. Each topological order of the graph is an equivalent serial schedule.

Example: S = R1(A) R2(B) W1(B) R3(A) W2(C) W3(C).

• R2(B) before W1(B) on B: edge T2 → T1.
• W2(C) before W3(C) on C: edge T2 → T3.
• R1(A) and R3(A) are both reads: no edge.

There is no cycle, and both T2, T1, T3 and T2, T3, T1 are topological orders, so S is equivalent to either serial schedule. The program below builds the graph and lists the serial orders:

from itertools import permutations

def parse(schedule):
    # "R1(A)" -> ("R", 1, "A")
    return [(op[0], int(op[1]), op[3]) for op in schedule.split()]

def precedence_edges(ops):
    edges = set()
    for i, (a, ti, x) in enumerate(ops):
        for b, tj, y in ops[i + 1:]:
            if ti != tj and x == y and "W" in (a, b):
                edges.add((ti, tj))
    return edges

def serial_orders(schedule):
    ops = parse(schedule)
    txns = sorted({t for _, t, _ in ops})
    edges = precedence_edges(ops)
    return edges, [p for p in permutations(txns)
                   if all(p.index(i) < p.index(j) for i, j in edges)]

for s in ["R1(A) R2(B) W1(B) R3(A) W2(C) W3(C)",
          "R1(A) R2(A) W1(A) W2(A)",
          "R1(A) W2(A) W1(A) W3(A)"]:
    edges, orders = serial_orders(s)
    print(s, "| edges:", sorted(edges), "| serial orders:", orders)

R1(A) R2(B) W1(B) R3(A) W2(C) W3(C) | edges: [(2, 1), (2, 3)] | serial orders: [(2, 1, 3), (2, 3, 1)]
R1(A) R2(A) W1(A) W2(A) | edges: [(1, 2), (2, 1)] | serial orders: []
R1(A) W2(A) W1(A) W3(A) | edges: [(1, 2), (1, 3), (2, 1), (2, 3)] | serial orders: []

The second schedule is the lost update: T1 → T2 (R1(A) before W2(A)) and T2 → T1 (R2(A) before W1(A)) form a cycle.

View serializability

Conflict serializability is sufficient but not necessary. Two schedules are view equivalent if, for every item:

1. the same transaction does the initial read (reads the original value),
2. every read reads the value written by the same transaction (the same "reads-from"), and
3. the same transaction does the final write.

A schedule is view serializable if it is view equivalent to some serial schedule. Every conflict serializable schedule is view serializable. The extra view-serializable schedules always contain blind writes (a write with no earlier read of the item by that transaction).

The third schedule above, R1(A) W2(A) W1(A) W3(A), has a cycle T1 ⇄ T2, so it is not conflict serializable. But compare it with the serial order T1, T2, T3: T1 does the initial read of A in both, and T3 does the final write in both, so it is view serializable. W2(A) and W3(A) are blind writes.

Testing view serializability is NP-complete, so real systems enforce conflict serializability.

Recoverability

Serializability ignores aborts. These classes describe what happens when a transaction aborts. Say Tj reads from Ti if Tj reads a value that Ti wrote.

• W1(A) R2(A) C2 C1 is not recoverable: T2 commits a value read from T1; if T1 then aborts, T2 cannot be undone.
• W1(A) R2(A) C1 C2 is recoverable but not cascadeless: if T1 aborted before committing, T2 would have to abort too (a cascading rollback).
• W1(A) W2(A) C1 C2 is cascadeless (no read at all) but not strict: T2 overwrites a value T1 has not committed.

Strict ⊂ cascadeless ⊂ recoverable, and strict two-phase locking (next lesson) produces strict schedules.

Practice questions