Schedules, Serializability, VSR & CSR

01 · Motivation

The five anomalies

Concurrency exists because serial execution wastes the machine: hundreds of transactions per second cannot each wait for the previous one’s disk I/O. The price is that interleaving can produce states no serial execution ever would.

There are exactly five, and each has a signature read/write pattern worth memorising — exam answers often need the name, and the name follows from the pattern.

The fourth deserves its own worked look, because it is the one whose “victim” did nothing wrong. Take the constraint $A + B + C = 100$, with $A = 50$, $B = 30$, $C = 20$:

T1: r(A)=50, r(B)=30                    T1 has seen 80 so far
T2:            r(B)=30, r(C)=20
T2:            B := 40, C := 10         T2 preserves the sum: 50+40+10 = 100
T2:            w(B), w(C)
T1: r(C)=10                             T1 now computes 50+30+10 = 90

T2’s update is entirely legal — it does not change the total. T1 nevertheless observes a total of 90, because it read B before and C after. To T1 it looks as though somebody else broke the invariant; to T2 nothing is wrong. That is the anomaly.

Two of these — the fourth and the fifth — are called phantoms precisely because the interfering change is invisible at the level of the individual objects the first transaction touched.

02 · Model

Schedules: the model

To reason precisely we strip transactions down to their reads and writes, and drop the program variables entirely.

An operation is a read or write of a specific object by a specific transaction: $r_1(x)$, $w_2(x)$. Operations differ if the transaction differs or the object differs — $r_1(x)$ and $r_1(y)$ are different operations, and so are $r_1(x)$ and $r_2(x)$.

A schedule is a sequence of operations performed by concurrent transactions that respects the order of operations within each transaction. Given

T1:  r1(x) w1(x)
T2:  r2(z) w2(z)

a schedule may interleave them any way that keeps $r_1$ before $w_1$ and $r_2$ before $w_2$. How many are there? For $n$ transactions where $T_i$ has $k_i$ operations:

$N_S$ counts the permutations of whole transactions; $N_D$ counts the interleavings of all operations, divided by the orderings that would violate each transaction’s internal sequence. For the two transactions above, $N_S = 2$ and $N_D = 4!/(2! \cdot 2!) = 6$ — of which two are serial, and the rest are interleaved or nested. As transactions grow, $N_S \lll N_D$: almost every schedule is interleaved, which is why we need a test rather than an enumeration.

In a serial schedule, each transaction’s actions occur in one contiguous block. In a serializable schedule, the database ends in the same state as it would under some serial schedule of the same transactions — the universally accepted definition of correctness.

Different notions of equivalence give different classes of “correct” schedules, and they trade accuracy against the cost of checking. Two matter.

03 · Classes

View-serializability

The more permissive of the two. Two schedules are equivalent if every read sees the same value and the final state of every object comes from the same transaction.

Two definitions do the work:

• $r_i(x)$ reads-from $w_j(x)$ in schedule $S$ when $w_j(x)$ precedes $r_i(x)$ and no other $w_k(x)$ falls between them.
• $w_i(x)$ is a final write if it is the last write on $x$ in $S$.

Two schedules are view-equivalent ($S_i \approx_V S_j$) when they have the same operations, the same reads-from relation, and the same final writes. A schedule is view-serializable if it is view-equivalent to some serial schedule of the same transactions; the class is VSR.

Mnemonically: every read sees the same value it would have seen, and every object ends up with the value the same transaction gave it.

S3:  w0(x) r2(x) r1(x) w2(x) w2(z)
S4:  w0(x) r1(x) r2(x) w2(x) w2(z)        ← serial: T0, T1, T2
     reads-from: r1(x) and r2(x) both from w0(x)
     final writes: w2(x), w2(z)
     ⇒ S3 ≈V S4, so S3 ∈ VSR

Swapping two reads changed nothing, because reads do not affect what anyone else sees.

In practice, for exam-sized schedules with three or four transactions, you do not enumerate. You compute the reads-from set and the final writes, then look for a serial order compatible with them — and the freedom you exploit is almost always blind writes, writes not preceded by a read of the same object by that transaction. A blind write can often be slid past other operations without changing what anybody reads.

04 · Classes

Conflict-serializability and the conflict graph

A stricter equivalence that is cheap to decide — and the one every exam exercise actually runs.

Two operations $o_i$ and $o_j$ ($i \ne j$) are in conflict when they address the same object and at least one is a write. So there are read-write conflicts ($r$–$w$, $w$–$r$) and write-write conflicts ($w$–$w$); two reads never conflict.

Two schedules are conflict-equivalent ($\approx_C$) when they contain the same operations and every conflicting pair appears in the same order in both. A schedule is

conflict-serializable — class CSR — when it is conflict-equivalent to a serial schedule.

The payoff is a decidable test:

The practical recipe — and the one to use under exam pressure — is to project the schedule onto each object first, because conflicts only ever arise within one object’s projection:

05 · Classes

The class hierarchy, and how the exam wants you to use it

CSR is strictly contained in VSR. Knowing the direction of that containment — and the ones that follow in chapters 6 and 7 — converts one verdict into five.

Every conflict-serializable schedule is view-serializable, and the proof is two lines. Suppose $S_1 \approx_C S_2$. They must have the same final writes, since otherwise two writes would appear in different orders and writes conflict. They must have the same reads-from relations, since otherwise some conflicting pair would appear in a different order. Hence $S_1 \approx_V S_2$.

The converse fails, and the standard counter-example is worth memorising:

S = r1(x) w2(x) w1(x) w3(x)

  view-equivalent to the serial T1 T2 T3 = r1(x) w1(x) w2(x) w3(x)
    reads-from: r1(x) reads the initial value in both
    final write: w3(x) in both                                  ⇒ S ∈ VSR

  but not conflict-serializable:
    r1(x) before w2(x)  ⇒ T1 → T2
    w2(x) before w1(x)  ⇒ T2 → T1                               ⇒ cycle, S ∉ CSR

The gap is created entirely by blind writes. w2(x) is blind — T2 never read x — so nobody observes the value it wrote, and it can be reordered freely under view equivalence while conflict equivalence, which looks only at operation types, forbids it. With no blind writes anywhere, VSR and CSR coincide.

The full picture, with the classes chapters 6 and 7 add:

with the timestamp classes branching off separately (chapter 7 shows TS ⊂ CSR but TS and 2PL incomparable).

That paper’s schedule is the widget’s first example, so you can run the classification you just read and check every intermediate step against the marked solution — projections, arcs, the two view-equivalent serial schedules. Then edit the schedule and watch a single blind write flip the CSR verdict without touching VSR.

06 · Bridge

From theory to real schedulers

Everything above judges a schedule after the fact. A real scheduler must decide about operation k without knowing operation k+1.

Three things break when we move to a running system:

• CSR checking would be efficient if we knew the graph in advance — but we do not. Maintaining the conflict graph and re-testing acyclicity at every operation request is not feasible.
• The commit-projection assumption is unrealistic. Aborts do occur, and a scheduler cannot restrict its attention to transactions that will turn out to commit.
• The scheduler needs a simple, local decision criterion that avoids as many anomalies as possible with negligible overhead.

A vocabulary distinction follows. So far, $r_1(x)\, w_2(x)\, w_1(x)$ denoted a schedule — an a-posteriori record of what happened, also called a history. For online control we also need arrival sequences: the order in which operation requests are emitted. The notation is the same and the meaning is clear from context, but the difference is real — the January 2025 exam turns on it, handing you an arrival sequence decorated with lock requests and asking what history a scheduler actually produces.

Two families of technique answer the problem, and the next two chapters take one each:

Commercial systems take the best of both — typically strict two-phase locking for writes combined with multiversion timestamps for reads.