Schedules, Conflict Serializability and View Serializability: short notes (Database Management Systems)

Introduction

Isolation says that concurrent transactions must behave as if they ran one at a time. Serializability makes this precise: a schedule is acceptable if it is equivalent to some serial schedule. Two notions of equivalence are used. Conflict equivalence is tested in polynomial time with a precedence graph, and is what locking protocols guarantee. View equivalence is weaker and admits more schedules, but testing it is NP-complete.

The questions to answer about a schedule are whether it is conflict or view serializable, which serial orders it is equivalent to, and how many schedules are conflict equivalent to it.

Prerequisites

Transactions and the ACID Properties: operations $R_i(X)$ , $W_i(X)$ , $C_i$ , and schedules.

Core concepts

Notation. A schedule is written as a sequence such as $R_1(A)\, W_2(A)\, C_1$ . Only reads and writes matter for serializability; commits matter for Recoverability.

Conflicting operations. Two operations conflict if they belong to different transactions, access the same item, and at least one is a write. So $R$ - $W$ , $W$ - $R$ and $W$ - $W$ pairs conflict; $R$ - $R$ pairs never do. Swapping two adjacent non-conflicting operations of different transactions does not change any read value or the final state.

Conflict equivalence. $S$ and $S'$ are conflict equivalent if they contain the same operations and order every pair of conflicting operations the same way; equivalently, $S'$ can be reached from $S$ by swapping adjacent non-conflicting operations.

Result equivalence, where two schedules merely produce the same final state, is not used: it can hold by accident for particular values (for example, adding then subtracting the same amount) and says nothing about other inputs.

Conflict serializable (CSR). Conflict equivalent to some serial schedule.

Precedence graph $G(S)$ : one node per transaction, and an edge $T_i \to T_j$ whenever an operation of $T_i$ precedes and conflicts with an operation of $T_j$ .

Theorem. $S$ is conflict serializable iff $G(S)$ is acyclic. The equivalent serial orders are exactly the topological orders of $G(S)$ .

View equivalence. $S$ and $S'$ are view equivalent if, for every item $X$ :

the same transaction reads the initial value of $X$ in both;
each read $R_i(X)$ reads the value written by the same write (reads-from) in both;
the same transaction performs the final write of $X$ in both.

View serializable (VSR). View equivalent to some serial schedule. Every CSR schedule is VSR. A VSR schedule that is not CSR always contains a blind write (a write of an item the transaction has not read).

How it works: testing conflict serializability

Text

CSR-TEST(S)
  nodes <- transactions of S
  for each pair of operations o_i of T_i, o_j of T_j with o_i before o_j in S
      if i != j and same item and (o_i or o_j is a write): add edge T_i -> T_j
  if the graph has a cycle: S is not conflict serializable
  else: every topological order of the graph is an equivalent serial schedule

With $n$ operations the pair scan takes $O(n^2)$ time and cycle detection is linear in the graph size.

Precedence graph on T1, T2, T3, T4 with edges T1 to T3, T1 to T4, T2 to T3, T2 to T4 and T3 to T4; no cycle; equivalent serial orders T1 T2 T3 T4 and T2 T1 T3 T4 — Figure 1. Precedence graph of Example 3: acyclic, with two topological orders and so two equivalent serial schedules.

Mathematical explanation

Why acyclic implies CSR. Take a topological order and the serial schedule $S'$ in that order. Every conflicting pair $o_i$ before $o_j$ in $S$ gives an edge $T_i \to T_j$ , so $T_i$ precedes $T_j$ in $S'$ : every conflicting pair is ordered the same way.

Why a cycle rules it out. A cycle $T_1 \to T_2 \to \cdots \to T_1$ would force $T_1$ before itself in any equivalent serial order.

Why VSR without CSR needs a blind write. For a schedule without blind writes (every write is preceded by a read of the same item in its transaction), view equivalence to a serial schedule implies conflict serializability. This theorem compares a schedule to a serial order; it does not say arbitrary view-equivalent nonserial schedules are conflict equivalent.

Counting conflict-equivalent schedules. Conflict equivalence fixes a partial order on operations: each transaction's own order plus the order of every conflicting pair. The schedules conflict equivalent to $S$ are exactly the linear extensions of that partial order, which can be counted by hand for small schedules using binomial coefficients for independent chains.

Worked examples

Example 1: conflict serializable. $S_1 = R_1(A)\, W_1(A)\, R_2(A)\, W_2(A)\, R_1(B)\, W_1(B)\, R_2(B)\, W_2(B)$ . Every conflicting pair has the $T_1$ operation first, so $G(S_1)$ has the single edge $T_1 \to T_2$ . $S_1$ is conflict equivalent to $T_1 T_2$ and not to $T_2 T_1$ .

Example 2: not serializable. $S_2 = R_1(A)\, R_2(A)\, W_1(A)\, W_2(A)$ , the lost update. $R_2(A)$ before $W_1(A)$ gives $T_2 \to T_1$ ; $R_1(A)$ before $W_2(A)$ gives $T_1 \to T_2$ . Cycle: not CSR. It is not VSR either: in $T_1 T_2$ , $T_2$ would read from $T_1$ , and in $T_2 T_1$ , $T_1$ would read from $T_2$ , but in $S_2$ both read the initial value.

Example 3: several serial orders (Figure 1). $S_3 = R_2(A)\, R_1(B)\, W_2(A)\, R_3(A)\, W_1(B)\, W_3(B)\, R_4(B)\, W_4(A)$ .

$W_2(A)$ before $R_3(A)$ : $T_2 \to T_3$ ; $R_2(A)$ and $W_2(A)$ before $W_4(A)$ : $T_2 \to T_4$ ; $R_3(A)$ before $W_4(A)$ : $T_3 \to T_4$ .
$R_1(B)$ and $W_1(B)$ before $W_3(B)$ : $T_1 \to T_3$ ; $W_1(B)$ before $R_4(B)$ : $T_1 \to T_4$ ; $W_3(B)$ before $R_4(B)$ : $T_3 \to T_4$ .
The graph is acyclic; $T_1$ and $T_2$ are unordered, so the equivalent serial schedules are $T_1 T_2 T_3 T_4$ and $T_2 T_1 T_3 T_4$ .

Example 4: view serializable but not conflict serializable. $S_4 = R_1(A)\, W_2(A)\, W_1(A)\, W_3(A)$ . Edges: $T_1 \to T_2$ ( $R_1$ before $W_2$ ), $T_2 \to T_1$ ( $W_2$ before $W_1$ ), and $T_1 \to T_3$ , $T_2 \to T_3$ . The cycle $T_1 \leftrightarrow T_2$ means not CSR. View: $T_1$ reads the initial $A$ and $T_3$ writes it last, the same as in the serial schedule $T_1 T_2 T_3$ , and there are no other reads. So $S_4$ is VSR, equivalent only to $T_1 T_2 T_3$ . The writes of $T_2$ and $T_3$ are blind.

Example 5: counting conflict-equivalent schedules. $S_5 = R_1(A)\, W_1(A)\, R_2(A)\, W_2(A)\, R_1(B)\, W_1(B)$ . All conflicts are on $A$ and put $R_1(A)\, W_1(A)$ before $R_2(A)\, W_2(A)$ . After $W_1(A)$ the chains $R_2(A)\, W_2(A)$ and $R_1(B)\, W_1(B)$ are independent, so they interleave in $\binom{4}{2} = 6$ ways: 6 schedules (including $S_5$ ) are conflict equivalent to $S_5$ . For $S_3$ of Example 3 the same count is 10.

Example 6: a cycle without any write-write conflict. $S_6 = R_1(A)\, R_2(B)\, W_1(B)\, W_2(A)$ . $R_2(B)$ before $W_1(B)$ gives $T_2 \to T_1$ ; $R_1(A)$ before $W_2(A)$ gives $T_1 \to T_2$ . Cycle: not CSR, even though the transactions never write the same item. No serial order makes both reads see initial values, so it is not VSR either.

Example 7: how many interleavings are CSR? $T_1 = R_1(A)\, W_1(A)\, R_1(B)\, W_1(B)$ and $T_2 = R_2(A)\, W_2(A)$ have $\binom{6}{2} = 15$ interleavings. Only item $A$ is shared. If both operations of $T_2$ come before $R_1(A)$ , the schedule is equivalent to $T_2 T_1$ : 1 schedule. If both come after $W_1(A)$ , it is equivalent to $T_1 T_2$ , and the two operations of $T_2$ interleave freely with $R_1(B)\, W_1(B)$ : $\binom{4}{2} = 6$ schedules. Any other placement puts one operation of $T_2$ on $A$ before a conflicting operation of $T_1$ and the other after, which creates the cycle $T_1 \to T_2 \to T_1$ . So $1 + 6 = 7$ of the 15 interleavings are CSR.

Example 8: a blind write is not enough for VSR. $S_8 = R_1(A)\, W_2(A)\, W_1(A)\, R_2(A)$ . $W_2(A)$ is blind ( $T_2$ has not read $A$ ), and the precedence graph has the cycle $T_1 \leftrightarrow T_2$ , so $S_8$ is not CSR. Check both serial orders for view equivalence:

$T_1 T_2$ : $R_2(A)$ reads from $T_2$ 's own write, but in $S_8$ it reads from $W_1(A)$ . Not equivalent.
$T_2 T_1$ : $R_1(A)$ reads $T_2$ 's write, but in $S_8$ it reads the initial value. Not equivalent.

So $S_8$ is not VSR. A blind write is necessary for "VSR but not CSR", not sufficient: the read $R_2(A)$ after $W_1(A)$ pins the order $T_1$ before $T_2$ on top of the cycle.

Example 9: serial orders are not the same count as equivalent schedules. $S_9 = R_1(A)\, W_2(A)\, R_3(B)\, W_3(B)$ . The only conflict gives $T_1 \to T_2$ ; $T_3$ touches only $B$ .

Conflict-equivalent serial orders: the topological orders $T_1 T_2 T_3$ , $T_1 T_3 T_2$ , $T_3 T_1 T_2$ , so 3.
Conflict-equivalent schedules: the operations interleave in $\frac{4!}{1!\,1!\,2!} = 12$ ways, and exactly half keep $R_1(A)$ before $W_2(A)$ , so 6 (including $S_9$ ).

"How many serial schedules is it equivalent to" and "how many schedules are equivalent to it" are different questions.

Important properties and observations

Conflicts: different transactions, same item, at least one write.
CSR iff the precedence graph is acyclic; serial equivalents are the topological orders.
CSR is a subset of VSR, and the difference needs blind writes.
Testing: CSR in polynomial time, VSR NP-complete in general.
Serial schedules are trivially CSR; there are $n!$ of them for $n$ transactions.
Number of equivalent serial orders equals the number of topological orders of $G(S)$ .

Common misconceptions.

"Two reads of the same item conflict." They do not.
"An edge is added only between adjacent operations." Every earlier-later conflicting pair adds an edge.
"A schedule that is not CSR is not serializable at all." It may still be VSR (Example 4).
"If $G(S)$ is acyclic, $S$ is equivalent to exactly one serial schedule." It is equivalent to every topological order (Example 3).

GATE examination perspective

Draw the precedence graph. Decide CSR, and list equivalent serial orders.
View serializability. Apply this to schedules with blind writes.
Count. Schedules conflict equivalent to a given one, or all CSR schedules of two short transactions.
Combine. Combine this with Recoverability: a schedule can be CSR but not recoverable, or the reverse.
Protocols. Lock-Based Concurrency Control produces only CSR schedules.

Summary

Transactions and the ACID Properties: prerequisite.
Recoverability: Recoverable, Cascadeless and Strict Schedules: dependent; commit-order properties.
Lock-Based Concurrency Control: dependent; a protocol that guarantees CSR.
Topological Sort and Strongly Connected Components: cycle detection and topological orders.

Schedules, Conflict Serializability and View Serializability

Introduction

Prerequisites

Core concepts

How it works: testing conflict serializability

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

How it works: testing conflict serializability

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps