Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 79 ยท Transactions and ACID

Schedules, Serializability and Precedence Graphs

Learn serial and concurrent schedules, conflicting operations, the precedence graph test for conflict serializability, view serializability and recoverable schedules.

A database that runs one transaction at a time is correct but slow: while one transaction waits for the disk, the CPU and every other client sit idle. So real systems interleave the operations of many transactions. The question this lesson answers is: when is an interleaving safe? The answer is a precise one, called serializability, and it comes with a simple algorithm you will run yourself.

A schedule is the order in which the operations of several transactions are executed. We write operations in shorthand: R1(A) means transaction T1 reads item A, W2(B) means T2 writes B, and C1 means T1 commits. A schedule must keep the operations of each transaction in their original order, but may mix different transactions freely.

Kinds of schedules

Serial One transaction at a time, no mixing.
Concurrent Operations interleaved.
Serializable Equivalent to some serial schedule.

Safe concurrency means serializable.

1 / 2

Serial and concurrent schedules

In a serial schedule the transactions do not overlap: all of T1, then all of T2. Every serial schedule is correct, assuming each transaction is correct by itself, because that is exactly what "one at a time" means. With n transactions there are n! serial schedules, and they can give different results (transferring money then computing interest differs from the reverse), yet each is acceptable.

A concurrent (or interleaved) schedule mixes the operations. Most interleavings are fine, some corrupt data. The rule we adopt is the one the whole field uses: a concurrent schedule is correct if it is equivalent to some serial schedule. Such a schedule is called serializable. The next sections define "equivalent" in two ways.

Conflicting operations

Two operations conflict when all three conditions hold:

  1. they belong to different transactions,
  2. they access the same data item,
  3. at least one of them is a write.

So a read and a read never conflict (their order cannot change what either sees), but read-write, write-read and write-write pairs on the same item do. Swapping two adjacent non-conflicting operations from different transactions never changes the outcome. Swapping conflicting ones can. That observation defines the first kind of equivalence.

Two schedules are conflict equivalent if they contain the same operations and every pair of conflicting operations appears in the same order in both. A schedule is conflict serializable if it is conflict equivalent to a serial schedule. Intuitively, you may shuffle non-conflicting operations until the schedule becomes serial.

The precedence graph test

You do not have to guess the shuffling. Build the precedence graph (also called serialization graph) of a schedule:

  • one node per transaction;
  • an edge Ti โ†’ Tj whenever an operation of Ti conflicts with a later operation of Tj.

The theorem is: a schedule is conflict serializable if and only if its precedence graph has no cycle. If it is acyclic, any topological order of the nodes is an equivalent serial order. An edge Ti โ†’ Tj says "Ti must come before Tj in every equivalent serial schedule", and a cycle would require Ti both before and after Tj, which is impossible.

flowchart LR
  T1["T1"] -->|"A: W1 before R2"| T2["T2"]
  T2 -->|"B: W2 before R1"| T1

A cycle between T1 and T2 means no serial order can reproduce this schedule.

Below is a small tester. It parses a schedule written as text, finds the conflicts, prints the edges, and either gives an equivalent serial order (a topological sort) or reports the transactions that sit on a cycle.

Python Precedence graph tester

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

S1 mixes T1 and T2 but every conflict points from T1 to T2, so it is equivalent to running T1 completely and then T2. S2 is the same two transactions, but on item A T1 goes first while on item B T2 goes first: the graph has the cycle T1 โ†’ T2 โ†’ T1, so no serial schedule matches it. S3 is the classic lost update: both transactions read the old value, then both write, so T2's write overwrites T1's. S4 contains only reads, therefore no conflicts and every order is equivalent.

A real DBMS does not run this test on a finished schedule, because that would be too late and the graph can get huge. It uses a protocol, such as two-phase locking, that guarantees the precedence graph stays acyclic. The graph is how we prove the protocol correct.

View serializability

Conflict serializability is sufficient but stricter than necessary. View equivalence compares what each transaction actually sees and produces. Two schedules over the same transactions are view equivalent if:

  1. every transaction reads the same initial value of an item in both (or reads the value written by the same transaction): same reads-from relation;
  2. for each item, the same transaction performs the final write.

A schedule is view serializable if it is view equivalent to some serial schedule. Every conflict serializable schedule is view serializable, but not the other way around. The gap comes from blind writes, writes of a value that was not read first. Consider R1(A) W2(A) W1(A) W3(A). The precedence graph has the cycle T1 โ†’ T2 โ†’ T1, but T2's write is overwritten by T1 and then by T3 before anyone reads it, so it has no visible effect. The schedule is view equivalent to the serial order T1, T2, T3.

Python View equivalence by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first schedule is view serializable (although we showed it is not conflict serializable); the second, the lost update, is neither. Testing view serializability is NP-complete in general, which is why brute force is the best a tester can do and why no real DBMS uses it. Practical systems enforce the stricter but cheap conflict test.

Recoverable and cascadeless schedules

So far we pretended transactions always commit. They do not: a transaction can abort, and then everything it wrote must be undone. That creates a second correctness question about the commit order.

If T2 reads a value written by T1 (T2 "reads from" T1), and T1 later aborts, T2 has used data that never officially existed. We classify schedules by how well they cope:

  • Recoverable: whenever T2 reads from T1, T1 commits before T2 commits. Then no committed transaction ever depends on a transaction that aborts.
  • Cascadeless (avoids cascading aborts): transactions read only values written by committed transactions. Then one abort never forces others to abort.
  • Strict: a transaction neither reads nor overwrites a value written by an uncommitted transaction. Undo is then trivial: restore the before-image.

Each class is contained in the previous one: strict โŠ‚ cascadeless โŠ‚ recoverable. A non-recoverable schedule can leave the database permanently wrong. Notice that all three classes are about commit timing and are independent of serializability: a schedule can be serializable and still not recoverable.

Python Classify schedules by recoverability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Schedule A is dangerous: T2 read T1's uncommitted value and committed first, so if T1 aborts, T2's commit can no longer be undone. B fixes that by ordering the commits, but T2 still read dirty data, so an abort of T1 would drag T2 down with it (a cascading abort). C reads nothing yet overwrites uncommitted data, which is cascadeless but not strict. D is strict. Real databases aim for strict schedules, which is what strict two-phase locking produces by holding write locks until commit.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which pair of operations conflicts?

    Conflicting operations belong to different transactions, touch the same item, and at least one is a write. Only R1(A) and W2(A) satisfy all three conditions.
  2. 2. What does a cycle in the precedence graph tell you?

    An edge Ti to Tj means Ti must precede Tj in any equivalent serial schedule. A cycle demands contradictory orders, so no serial schedule is conflict equivalent.
  3. 3. Schedule W1(A) R2(A) C2 C1 is...

    T2 reads from T1 but commits before T1. If T1 aborted, T2 would have committed on data that never existed, and the commit cannot be undone.
  4. 4. Why does a real DBMS not use the view serializability test?

    View serializability admits a few more schedules, but deciding it is NP-complete. Protocols enforce conflict serializability instead, which is easy to guarantee.

Summary

  • A schedule is an interleaving of transaction operations; a correct one is equivalent to some serial schedule (serializable).
  • Operations conflict if they come from different transactions, touch the same item, and at least one writes.
  • A schedule is conflict serializable exactly when its precedence graph is acyclic; a topological order gives an equivalent serial schedule.
  • View serializability is more permissive (it allows some blind writes) but NP-complete to test.
  • Recoverable, cascadeless and strict schedules constrain commit timing so aborts stay safe; strict is the practical target.

Next: Isolation Levels and Concurrency Anomalies.