Conflict & View Serializability

When multiple transactions execute concurrently, the interleaved order of their operations is called a Schedule. A schedule is Serializable if its effect is equivalent to executing the transactions one after another (serially). Serializability is the gold standard for correctness.

1. Conflict Serializability

Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a WRITE.

A schedule is Conflict Serializable if it can be transformed into a serial schedule by swapping non-conflicting adjacent operations.

Testing with a Precedence Graph:

Create a node for each transaction.
Add a directed edge from $T_i$ to $T_j$ if $T_i$ has an operation that conflicts with an operation of $T_j$ and $T_i$'s operation comes first.
If the precedence graph has no cycles, the schedule is conflict serializable. The topological sort of the graph gives the equivalent serial order.

2. View Serializability

A schedule $S$ is View Serializable if it is view equivalent to some serial schedule. View equivalence requires three conditions for every data item:

If $T_i$ reads the initial value in the serial schedule, $T_i$ must also read the initial value in $S$.
If $T_i$ reads a value written by $T_j$ in the serial schedule, $T_i$ must also read the value written by $T_j$ in $S$.
The final write on each data item must be by the same transaction in both schedules.

Key Difference: Every conflict serializable schedule is also view serializable, but NOT vice versa. View serializability is a superset. However, testing view serializability is NP-complete, so databases use conflict serializability in practice.

3. Recoverable and Cascadeless Schedules

Recoverable Schedule: If $T_j$ reads a value written by $T_i$, then $T_i$ must commit before $T_j$ commits.
Cascadeless Schedule: $T_j$ reads a value written by $T_i$ only after $T_i$ has committed. This prevents cascading rollbacks where one aborted transaction forces the rollback of many others.