Conflict Serialisable Schedules

COMP207 Lectures 2021-10-19

This is how we calculate quickly how much concurrency we can allow while satisfying isolation and consistency.

Conflict-Serialisability

This is a stronger from of serialisability that is used by most commercial DBMS. It is base on the notion of conflict:

A conflict in a schedule is a pair of operations, from different transaction, that cannot be swapped without changing the behaviour of at least one of the transactions.

r_{1} (X); \underset{conflict}{\underset{⏟}{w_{1} (X); r_{2} (X)}}; w_{2} (X); r_{1} (Y); w_{1} (Y);

Look for a write, then read, from different transactions. Read, then write, is okay.

Conflicts

A conflict in a schedule is a pair of operations:

From different transactions.
That access the same item.
At least one of them is a write operation.

Conflict-Equivalency

Two schedules $S$ and $S^{'}$ are conflict-equivalent if $S^{'}$ can be obtained from $S$ by swapping any number of: consecutive, non-conflicting, operations from different transactions.

Example

You want to order the transactions to make it serial:

\begin{aligned} S : & r_{1} (X); w_{1} (X); w_{2} (X); r_{2} (Y); r_{1} (Y); w_{1} (Z) \\ r_{1} (X); w_{1} (X); w_{2} (X); r_{1} (Y); r_{2} (Y); w_{1} (Z) \\ r_{1} (X); w_{1} (X); r_{1} (Y); w_{2} (X); r_{2} (Y); w_{1} (Z) \\ r_{1} (X); w_{1} (X); r_{1} (Y); w_{2} (X); w_{1} (Z); r_{2} (Y) \\ S^{'} : & r_{1} (X); w_{1} (X); r_{1} (Y); w_{1} (Z); w_{2} (X); r_{2} (Y) \end{aligned}

A schedule is conflict-serialisable if it is conflict-equivalent to a serial schedule.

Hierarchy of Schedules

All of the types of schedules shown so far are represented below:

Inclusions in the diagram are strict.