Many transactions run at once. Only some interleavings are safe.
Running transactions strictly one after another is correct but painfully slow. This lesson defines when interleaving them is provably just as safe, and what it means for a schedule to be recoverable if something goes wrong.
After this lesson
You should be able to
- Explain why running transactions one at a time is correct but too slow for a real system.
- Define serializability and explain what a precedence graph is used to test.
Serial execution is obviously correct, and obviously wasteful
A serial schedule runs transactions one completely after another, with zero overlap — since each transaction alone is correct (by definition), and nothing else touches the database while it runs, a serial schedule is trivially correct. But it wastes the CPU and disk sitting idle while one transaction waits on I/O that another transaction's CPU-bound work could have used simultaneously — exactly the throughput loss any single-threaded system suffers.
Concurrent execution interleaves operations from multiple transactions to keep hardware busy, but this reopens exactly the danger Unit 1 flagged with two programs writing one file at once: interleaved operations from different transactions can corrupt each other's work if done carelessly.
Serializability: interleaved, but provably equivalent to some serial order
A schedule is serializable if its final effect on the database is guaranteed equivalent to some serial (one-at-a-time) execution of the same transactions — the interleaving is allowed to happen, as long as the outcome is indistinguishable from a safe, non-overlapping order. This is the formal target: not "never interleave," but "interleave freely, as long as correctness is preserved."
A precedence graph (or serializability graph) tests this formally: draw one node per transaction, and an edge from Ti to Tj whenever Ti's operation on some data item happens before Tj's conflicting operation on the same item. If this graph has no cycle, the schedule is conflict-serializable — genuinely equivalent to the serial order given by any topological sort of the graph. A cycle means no such equivalent serial order exists, and the schedule is unsafe.
Recoverability: what happens when a transaction reads another's uncommitted write
If transaction T2 reads a value that transaction T1 wrote before T1 commits, and T1 later aborts, T2's read was based on data that officially never happened. A schedule is recoverable if, in every such case, T2 does not commit until T1 commits first — this prevents T2 from finalizing work built on a foundation that got rolled back.
Recoverability and serializability are two separate, complementary safety properties: serializability is about the schedule's final result being logically correct; recoverability is about never being able to commit work that depended on a transaction that turned out to fail. A real DBMS needs both, not just one.
Try it yourself
Two transactions run concurrently: T1 writes to item X, then T2 reads that same X, then T2 commits, then T1 aborts. Explain why this schedule is not recoverable and what could go wrong as a result.
Need a hint?
T2 committed based on a value T1 wrote, but T1's write was later undone by the abort — check whether T2 committed before or after T1's fate was decided.
Check the worked solution
This is not recoverable because T2 committed before T1's outcome (commit or abort) was known — when T1 subsequently aborts, T2's committed result was based on a value that officially never existed, and since T2 already committed, that inconsistency cannot be undone. A recoverable schedule would have forced T2 to wait until T1 committed before allowing T2 to commit.
Quick check
Why is a no-cycle precedence graph considered a proof that a schedule is safe, rather than just a helpful heuristic?
Why this lesson exists
Syllabus mapping
Concurrent Executions, Serializability, Recoverability · Implementation of Isolation, Testing for serializability
Maps to course outcome CO3.