Schedules

For a set of transactions

{T_{1}, \dots T_{k}}

produces an execution order of operations

S

such that

Goal

Produce a correct schedule with maximal parallelism

If $T_{i}$ and $T_{j}$ are concurrent transactions, then it is always correct to schedule the operations in such way that

$T_{i}$ will appear to precede $T_{j}$
1. $T_{j}$ will see all updates made by $T_{i}$
2. $T_{i}$ will not see any updates made by $T_{j}$
$T_{i}$ will appear to follow $T_{j}$
1. $T_{i}$ will see $T_{j}$ ‘s updates
2. $T_{j}$ will not see $T_{i}$ ‘s updates

Correct: Schedule appears to clients that the transactions are executed sequentially

Equivalent to some serial execution of the same transactions

All conflicting operations for two schedules are ordered the same way

Two operations conflict if they

Schedule $S_{1}$ is a conflict serializable schedule if it is conflict equivalent to some serial schedule $S_{2}$

View Equivalence

Preserves initial reads and final writes

$S G (N, E)$ for a schedule $S$ is a directed graph

Nodes $T_{i} \in N$ corresponding to the transactions of $S$
Edges $T_{i} \to T_{j} \in E$ whenever an operation $o_{i} [x]$ for transaction $T_{i}$ occurs prior $o_{j} [x]$ for transaction $T_{j}$ in $S$ , where $o_{i} [x]$ and $o_{j} [x]$ are conflicting operations

Theorem: Schedule $S$ is serializable if and only if the serialization graph $S G$ for $S$ is acyclic