Module 5 · Transactions and concurrency control

Episode 34 Serializability

8 min · SQL · Postgres

Title card of Episode 34: Serializability

▶ This video is coming to YouTube soon.

When is an interleaving of transactions safe? This episode builds the precedence (conflict) graph of a schedule step by step, swaps non-conflicting operations to reach a serial order, finds the cycle in the schedule that lost $30, and topologically sorts a three-transaction graph. Then Postgres SERIALIZABLE aborts the cyclic schedule with SQLSTATE 40001 and commits the acyclic one.

Chapters

  1. 0:00Intro
  2. 0:17252 ways to interleave
  3. 0:37Two operations conflict when order matters
  4. 1:07Every conflict is an edge
  5. 1:48Conflict equivalence: swap what doesn't conflict
  6. 2:40A cycle means no serial order
  7. 3:27Topological order = the serial schedule
  8. 4:06The code: build the graph, look for a cycle
  9. 4:34The two schedules we'll run in Postgres
  10. 5:14Proof: SERIALIZABLE aborts the cycle
  11. 6:58Conflict-serializable is a safe subset
  12. 7:26How databases keep the graph acyclic
  13. 7:50Recap
  14. 8:16Next: Two-Phase Locking