Conflict Serializability: 5 Solved Precedence-Graph Problems + Practice
Quick answer: A schedule is conflict-serializable exactly when its precedence graph has no directed cycle. An edge T1 → T2 means a conflicting operation of T1 occurs before one of T2. A topological order of an acyclic graph gives a conflict-equivalent serial order.
This is a focused problem-solving companion to DBMS concurrency and isolation notes, not a replacement chapter. Work through five original schedules, then try three questions before opening their answers. These are general BTech CSE practice problems, not copied past papers or a prediction of your exam.
Read the notation first
r1(A) means transaction T1 reads item A; w2(B) means T2 writes item B. Read schedules left to right. Within each transaction, keep its operation order unchanged. Our exercises use the standard read/write conflict model on named items; commit and abort operations are omitted. The graph alone does not prove recoverability, strictness or freedom from dirty reads.
When do two operations conflict?
All three conditions must hold: different transactions, the same data item, and at least one write. A read-write pair, write-read pair or write-write pair can conflict. Two reads never conflict in this model. Operations of the same transaction do not create graph edges, and A versus B is not a same-item conflict.
Pocket reference: graphs and serial orders
| Tool | What it records | What the test tells you |
|---|---|---|
| Precedence graph | Earlier conflicting operation to later transaction | Cycle: not conflict-serializable |
| Wait-for graph | Transaction waits for a lock held by another | Cycle: deadlock in the usual single-instance lock model |
| Topological order | An ordering that respects all precedence edges | Exists only when the directed graph is acyclic |
Do not confuse an ordering constraint with a current wait. A schedule can fail the conflict test without the system being deadlocked.
The exam method in five steps
- Number the operations from left to right.
- Create one node for each transaction, even an isolated transaction.
- Compare every same-item pair from different transactions. If at least one is a write, draw an edge from the earlier transaction to the later one.
- Keep one copy of each directed edge. Look for cycles of any length.
- If acyclic, repeatedly choose a node with no incoming edges, remove it and continue. Any resulting topological order is valid. If cyclic, write the cycle and conclude that the schedule is not conflict-serializable.
Do not inspect only adjacent operations. A conflict may span several other operations.
1. Two transactions, one valid order
r1(A) w1(A) r2(A) w2(A)
Operation numbers: 1 = r1(A), 2 = w1(A), 3 = r2(A), 4 = w2(A).
| Earlier operation | Later operation | Required edge |
|---|---|---|
| 1: r1(A) | 4: w2(A) | T1 → T2 |
| 2: w1(A) | 3: r2(A) | T1 → T2 |
| 2: w1(A) | 4: w2(A) | T1 → T2 |
Distinct edges: T1 → T2.
All cross-transaction conflicts point from T1 to T2. The second transaction must follow the first in a conflict-equivalent serial order.
Conclusion: Acyclic, so conflict-serializable. Valid serial order: T1 → T2. Each listed order respects every edge.
2. The opposite-item trap
r1(A) w1(A) r2(A) w2(A) r2(B) w2(B) r1(B) w1(B)
Operation numbers: 1 = r1(A), 2 = w1(A), 3 = r2(A), 4 = w2(A), 5 = r2(B), 6 = w2(B), 7 = r1(B), 8 = w1(B).
| Earlier operation | Later operation | Required edge |
|---|---|---|
| 1: r1(A) | 4: w2(A) | T1 → T2 |
| 2: w1(A) | 3: r2(A) | T1 → T2 |
| 2: w1(A) | 4: w2(A) | T1 → T2 |
| 5: r2(B) | 8: w1(B) | T2 → T1 |
| 6: w2(B) | 7: r1(B) | T2 → T1 |
| 6: w2(B) | 8: w1(B) | T2 → T1 |
Distinct edges: T1 → T2, T2 → T1.
A requires T1 before T2, but B requires T2 before T1. Checking only A would give the wrong answer.
Conclusion: Cyclic, so not conflict-serializable. Cycle: T1 → T2 → T1. There is no serial order that respects all these constraints.
3. Three transactions form a chain
w1(A) r2(A) w2(B) r3(B) w3(C)
Operation numbers: 1 = w1(A), 2 = r2(A), 3 = w2(B), 4 = r3(B), 5 = w3(C).
| Earlier operation | Later operation | Required edge |
|---|---|---|
| 1: w1(A) | 2: r2(A) | T1 → T2 |
| 3: w2(B) | 4: r3(B) | T2 → T3 |
Distinct edges: T1 → T2, T2 → T3.
T1 constrains T2, and T2 constrains T3. T1 does not need a direct edge to T3: the path already forces their order.
Conclusion: Acyclic, so conflict-serializable. Valid serial order: T1 → T2 → T3. Each listed order respects every edge.
4. Several serial orders are possible
r1(A) w1(A) r2(A) r3(A) w2(B) w3(C)
Operation numbers: 1 = r1(A), 2 = w1(A), 3 = r2(A), 4 = r3(A), 5 = w2(B), 6 = w3(C).
| Earlier operation | Later operation | Required edge |
|---|---|---|
| 2: w1(A) | 3: r2(A) | T1 → T2 |
| 2: w1(A) | 4: r3(A) | T1 → T3 |
Distinct edges: T1 → T2, T1 → T3.
T1 must come first, but T2 and T3 do not conflict with each other. Shared reads of A do not create an edge between them.
Conclusion: Acyclic, so conflict-serializable. Valid serial orders: T1 → T2 → T3; T1 → T3 → T2. Each listed order respects every edge.
5. A cycle across three different items
w1(A) r2(A) w2(B) r3(B) w3(C) r1(C)
Operation numbers: 1 = w1(A), 2 = r2(A), 3 = w2(B), 4 = r3(B), 5 = w3(C), 6 = r1(C).
| Earlier operation | Later operation | Required edge |
|---|---|---|
| 1: w1(A) | 2: r2(A) | T1 → T2 |
| 3: w2(B) | 4: r3(B) | T2 → T3 |
| 5: w3(C) | 6: r1(C) | T3 → T1 |
Distinct edges: T1 → T2, T2 → T3, T3 → T1.
No single item shows a two-way conflict. The combined graph still has the cycle T1 to T2 to T3 to T1. Check the entire graph, not each item in isolation.
Conclusion: Cyclic, so not conflict-serializable. Cycle: T1 → T2 → T3 → T1. There is no serial order that respects all these constraints.
Why a cycle matters
A serial order cannot put T1 before T2 and also T2 before T1. A longer cycle has the same problem: each transaction must precede the next, but the final edge requires the last to precede the first. Without a cycle, topological sorting finds an order that preserves all conflicting pairs.
Common mistakes that lose the answer
- Adding read-read edges: r1(A) and r2(A) do not conflict.
- Missing distant writes: compare all relevant pairs, not only neighbours or the last write.
- Reversing arrows: earlier conflicting operation points to later, regardless of transaction number.
- Rejecting multiple orders: an acyclic graph can have several valid topological orders.
- Calling every cycle a deadlock: a precedence graph records conflicting operation order; a wait-for graph records waiting for locks. They answer different questions.
- Claiming not serializable without a qualifier: this test proves conflict serializability. A cyclic precedence graph does not by itself rule out view serializability.
Try these three schedules
Write the full edge set and every valid serial order. Open each answer only after checking your graph.
Practice 1
r1(A) r2(A) w2(B) r1(C)
Show checked answer
Only reads share A. B and C are different items.
Edges: No edges. Acyclic. Valid orders: T1 → T2; T2 → T1
Practice 2
w2(A) r1(A) w1(B) r3(B)
Show checked answer
Read the transaction subscripts carefully: the schedule starts with T2.
Edges: T1 → T3, T2 → T1. Acyclic. Valid orders: T2 → T1 → T3
Practice 3
r1(A) w2(A) w1(A)
Show checked answer
The first read forces one direction and the final write forces the reverse.
Edges: T1 → T2, T2 → T1. Cyclic: T1 → T2 → T1. Not conflict-serializable.
Run the eight schedules yourself
This checker was executed against all five worked examples and all three practice schedules. It compares every later pair and enumerates every transaction permutation, including isolated nodes. Numbers 1-5 are the worked examples; 6-8 are Practice 1-3. No valid order means a cycle in this model.
import re
from itertools import permutations
def check(schedule):
ops=[]
for token in schedule.split():
m=re.fullmatch(r'([rw])(\d+)\(([A-Z])\)',token)
if not m: raise ValueError(token)
ops.append((m[1],int(m[2]),m[3]))
nodes=sorted({t for _,t,_ in ops}); edges=set()
for i,(op,t,item) in enumerate(ops):
for op2,u,item2 in ops[i+1:]:
if t!=u and item==item2 and 'w' in (op,op2):
edges.add((t,u))
orders=[]
for order in permutations(nodes):
pos={t:i for i,t in enumerate(order)}
if all(pos[t]<pos[u] for t,u in edges): orders.append(order)
return sorted(edges),orders
schedules=[
'r1(A) w1(A) r2(A) w2(A)',
'r1(A) w1(A) r2(A) w2(A) r2(B) w2(B) r1(B) w1(B)',
'w1(A) r2(A) w2(B) r3(B) w3(C)',
'r1(A) w1(A) r2(A) r3(A) w2(B) w3(C)',
'w1(A) r2(A) w2(B) r3(B) w3(C) r1(C)',
'r1(A) r2(A) w2(B) r1(C)',
'w2(A) r1(A) w1(B) r3(B)',
'r1(A) w2(A) w1(A)']
for i,s in enumerate(schedules,1):
edges,orders=check(s)
print(f'{i}: edges={edges}; orders={orders or "none (cycle)"}')Executed output:
1: edges=[(1, 2)]; orders=[(1, 2)]
2: edges=[(1, 2), (2, 1)]; orders=none (cycle)
3: edges=[(1, 2), (2, 3)]; orders=[(1, 2, 3)]
4: edges=[(1, 2), (1, 3)]; orders=[(1, 2, 3), (1, 3, 2)]
5: edges=[(1, 2), (2, 3), (3, 1)]; orders=none (cycle)
6: edges=[]; orders=[(1, 2), (2, 1)]
7: edges=[(1, 3), (2, 1)]; orders=[(2, 1, 3)]
8: edges=[(1, 2), (2, 1)]; orders=none (cycle)This small teaching checker is not a database scheduler. Pair checking is quadratic in the number of operations; permutation enumeration is factorial in the number of transactions. Use a topological-sort algorithm for larger graphs.
Exam and interview quick answers
- Do two reads conflict? No, even on the same item in different transactions.
- Does a write on A conflict with a read on B? No. The data item must be the same.
- Which way does an edge point? From the earlier conflicting operation's transaction to the later one's transaction.
- Should repeated edges be counted many times? Keep one directed edge, but show the relevant pairs if the question asks for working.
- Does every acyclic graph have only one serial order? No. Example 4 has two; unrelated transactions can swap.
- Can a three-transaction cycle exist without a two-way edge? Yes: T1 to T2 to T3 to T1.
- Does this graph prove strictness or recoverability? No. Commit, abort and read-from relationships need separate analysis.
- Does a cycle rule out view serializability? Not by itself. State the conclusion as not conflict-serializable.
A short answer you can adapt
"The conflicting pairs give edges [write your edges]. The precedence graph is [acyclic / cyclic]. Therefore the schedule is [conflict-serializable / not conflict-serializable]. A valid serial order is [your topological order], or the cycle is [your cycle]." Include the pair table or labelled graph when the question asks for working.
Continue the DBMS cluster
- Transactions and ACID: understand what a transaction promises
- Concurrency, isolation and locking: the surrounding theory
- Exam Numericals Hub: choose the next worked topic
- DBMS SQL lab: practise queries separately from schedule analysis
References and checking
Definitions and the acyclic-graph theorem were checked against Emory University's precedence-graph lesson and Stanford CS245 concurrency-control slides. The eight schedules, explanations and diagram on this page are original TechVani practice. Every cross-transaction same-item pair and every possible transaction permutation was independently enumerated to check the answers. This is the named-item read/write model, not a vendor-specific SQL isolation guarantee.
Comments
Post a Comment