Serializability

An interleaved schedule is safe when it is equivalent to running the transactions one at a time. The precedence graph tells you whether it is — and in which order.

Pairs: O(n²)

Cycle check: O(T + E)

Acyclic ⇔ serializable

Schedule

Animation Speed: 1000ms

Step 1 of 0

Click Play to begin.

When Two Operations Conflict

Same item, different transactions:

read → readswappable

read → writeconflict

write → readconflict

write → writeconflict

Conflict-serializability is the test real schedulers enforce. A few schedules — with blind writes — are view-serializable without being conflict-serializable, but checking view-serializability is NP-complete.

Knowledge Check

Question 1 of 3

Which pair of operations does NOT conflict?

DSAverse

Serializability

When Two Operations Conflict

Knowledge Check

See also

Serializability

When Two Operations Conflict

Knowledge Check

See also