6.2Schedules and conflict serializability
The idea
A schedule is an interleaving of operations. It is conflict serializable when it can be turned into a serial schedule by swapping non-conflicting operations. A precedence graph tests this.
Think of it like this: Two cooks sharing a kitchen: if they never touch the same ingredient at the same time, the order does not matter, so the dish is as if one cook finished first.
Why it exists
Drawing the graph and counting serial orders is a regular two-mark question.
How it works
- Conflict = different transactions, same item, at least one write.
- Draw an edge Ti → Tj when a conflicting op of Ti comes before one of Tj.
- A cycle means not conflict serializable.
- No cycle: any topological order is an equivalent serial schedule; count the topological orders.
Worked example: r1(A) r2(A) w1(A) w2(A)
r2(A) before w1(A) gives T2 → T1, r1(A) before w2(A) gives T1 → T2: cycle, not serializable.
Now play with it
- →Select each example and read the edges.
- →Edit the schedule text to remove a conflict and watch the cycle vanish.
| time → | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| T1 | R(A) | W(A) | Commit | |||
| T2 | R(A) | W(A) | Commit |
Check yourself
A schedule has precedence graph T1 → T2, T1 → T3. How many equivalent serial schedules?
Exam notes (the dense version)
A schedule interleaves the operations of several transactions. Two operations conflict if they are from different transactions, on the same item, and at least one is a write (RW, WR, WW). Build the precedence graph (edge Ti → Tj if a conflicting op of Ti comes first). The schedule is conflict serializable iff the graph is acyclic; any topological order is an equivalent serial schedule.
Previous year questions: Transactions & Concurrency Control (15)
PYQs are grouped by topic, so this is the full set for Transactions & Concurrency Control; try the ones that match this subtopic. Open all 15 on the topic page.