# Schedules and Serializability — Database Fundamentals

Source: https://www.skillbyai.com/en/database-fundamentals/t-schedules

> Test schedules for conflict serializability using precedence graphs.

## When is interleaving safe?

A **schedule** is an ordering of the operations (reads, writes, commits) of several concurrent transactions. A **serial** schedule runs one transaction completely after another, which is always correct but slow. A schedule is **serializable** if its effect equals that of **some** serial schedule. **Conflict serializability** is the practical test: two operations **conflict** if they belong to different transactions, access the same data item and at least one is a **write** (read-write, write-read, write-write). Swapping adjacent non-conflicting operations does not change the outcome. Build a **precedence graph**: one node per transaction and an edge Ti → Tj whenever an operation of Ti conflicts with and comes **before** an operation of Tj. The schedule is conflict serializable **if and only if the graph has no cycle**, and a topological order of the graph gives an equivalent serial order. Schedules should also be **recoverable** (a transaction commits only after transactions it read from have committed) and ideally **cascadeless** (transactions read only committed data).

## A precedence graph worked by hand

Schedule S: R1(A) W2(A) R2(B) W1(B)

```text
operations in order:    T1: R(A)   T2: W(A)   T2: R(B)   T1: W(B)

conflicts:
  R1(A) before W2(A)   same item A, one write  -> edge T1 -> T2
  R2(B) before W1(B)   same item B, one write  -> edge T2 -> T1

precedence graph:  T1 -> T2 -> T1   (cycle)
=> S is NOT conflict serializable

change S to: R1(A) W1(B) W2(A) R2(B)
  edges: T1 -> T2 only -> acyclic -> equivalent to serial order T1, T2
```

## Sharing a whiteboard

Two people can read the same whiteboard in any order. Trouble starts when one writes while the other reads or writes the same spot; the order of those clashes decides whether the result matches doing the work one person at a time.

**Quiz:** When is a schedule conflict serializable?

- [ ] When transactions never read data
- [ ] When it has exactly two transactions
- [ ] When all operations are writes
- [x] When its precedence graph contains no cycle

*Answer:* When its precedence graph contains no cycle. An acyclic precedence graph means an equivalent serial order exists.