Skip to main content

Conflict serializability precedence graph

Short answer

Edges: T1→T2 (x), T2→T1 (y), T2→T3 (y,z), T3→T1 (y). Cycle T1→T2→T1 exists, so not conflict serializable.

Consider the transactions: T1: r1(x); w1(x); r1(y); w1(y) T2: r2(z); r2(y); w2(y); r2(x); w2(x) T3: r3(y); r3(z); w3(y); w3(z) Consider the schedule S1: r2(z); r2(y); w2(y); r3(y); r3(z); r1(x); w1(x); w3(y); w3(z); r2(x); r1(y); w1(y); w2(x). Draw the precedence graph and test whether S1 is conflict serializable.

A precedence (serialization) graph has one node per transaction and an edge Ti → Tj if an operation of Ti conflicts with a later operation of Tj on the same item (different transactions, at least one is a write: r-w, w-r or w-w). A schedule is conflict serializable if and only if the graph has no cycle.

S1: r2(z); r2(y); w2(y); r3(y); r3(z); r1(x); w1(x); w3(y); w3(z); r2(x); r1(y); w1(y); w2(x)

Conflicts item by item (in schedule order)

ItemOperations in orderEdges
xr1(x), w1(x), r2(x), w2(x)T1 → T2 (w1(x) before r2(x), w2(x))
yr2(y), w2(y), r3(y), w3(y), r1(y), w1(y)T2 → T3 (r2(y)-w3(y), w2(y)-r3(y), w2(y)-w3(y)); T2 → T1 (r2(y)-w1(y), w2(y)-r1(y), w2(y)-w1(y)); T3 → T1 (r3(y)-w1(y), w3(y)-r1(y), w3(y)-w1(y))
zr2(z), r3(z), w3(z)T2 → T3 (r2(z) before w3(z))

Edges: T1 → T2, T2 → T1, T2 → T3, T3 → T1.

Precedence graph

        T1 <======> T2
         ^           |
         |           |
         +--- T3 <---+

Reading the arrows: T1 → T2, T2 → T1, T2 → T3, T3 → T1.

Test

There are cycles: T1 → T2 → T1 (because T1 must come before T2 for x, but T2 before T1 for y), and also T2 → T3 → T1 → T2.

The graph has a cycle, so S1 is NOT conflict serializable. No serial order T_i, T_j, T_k is equivalent to S1 by conflict swapping.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Database Management System chapter 7 questions →