---
title: "Conflict serializability precedence graph"
subject: "Database Management System"
chapter: 7
key: "semester_6/database_management_system:precedence-graph-three-transactions"
source: https://www.bctengineer.com/q/semester_6/database_management_system/precedence-graph-three-transactions
site: BCT Engineering
---

# Conflict serializability precedence graph

Database Management System · Chapter 7: Transaction Processing

- Asked in: year not given
- Video: [Lec-98: Conflict Serializability | Precedence Graph | Transaction | DBMS](https://www.youtube.com/watch?v=zv0ba0Iok1Y) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/database_management_system/precedence-graph-three-transactions
- Whole chapter: https://www.bctengineer.com/md/semester_6/database_management_system/chapter-7

## Question

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.

## 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.

## Answer

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)

| Item | Operations in order | Edges |
|---|---|---|
| x | r1(x), w1(x), r2(x), w2(x) | T1 → T2 (w1(x) before r2(x), w2(x)) |
| y | r2(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)) |
| z | r2(z), r3(z), w3(z) | T2 → T3 (r2(z) before w3(z)) |

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

#### Precedence graph

```text
        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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. When is an edge Ti -> Tj added in a precedence graph?
   A. When an operation of Ti conflicts with a later operation of Tj on the same item (at least one a write)
   B. When Ti commits before Tj
   C. When Ti and Tj access any items
   D. When Ti reads and Tj reads the same item
   Answer: A. Conflicting operations (r-w, w-r, w-w) on the same item from different transactions create an edge in schedule order. (Key point: Precedence graph edge)

2. What edge comes from item x?
   A. T2 -> T1
   B. T1 -> T2
   C. T3 -> T1
   D. T1 -> T3
   Answer: B. w1(x) comes before r2(x) and w2(x), so T1 -> T2. (Key point: Edge on x)

3. Which edge pair causes the cycle with x?
   A. T1 -> T2 from x and T2 -> T1 from y
   B. T3 -> T2 and T2 -> T3
   C. T1 -> T3 only
   D. No edges arise from y
   Answer: A. On y, T2 operates before T1 (w2(y) before r1(y)/w1(y)), giving T2 -> T1, which with T1 -> T2 forms a cycle. (Key point: Edges on y)

4. What is the conclusion for S1?
   A. Conflict serializable, order T2, T3, T1
   B. Not conflict serializable because the graph has a cycle
   C. Conflict serializable, order T1, T2, T3
   D. Cannot be decided
   Answer: B. A schedule is conflict serializable iff its precedence graph is acyclic; this graph has cycles. (Key point: Serializability test)

## Related in Database Management System

- [View serializability check of schedule](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Aview-serializable-schedule-q) — Database Management System, chapter 7

## Related in other subjects

- [Show i1 = i2 = -V/(R1+R2+R3) at t=0+](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_circuit_theory%3Aswitch-a-to-b-initial-values) — Electrical Circuit Theory, chapter 2
- [3rd order Butterworth LPF, R1 = 1 Ω, R2 = 4 Ω](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Abutterworth-lp-third-order-unequal-termination) — Filter Design, chapter 5, asked 4×
- [IDMT grading: R1, R2 with 1000/5 CTs](https://www.bctengineer.com/question.md?key=semester_6%2Fswitchgear_and_protection%3Aidmt-r1-r2-1000-5) — Switchgear and Protection, chapter 7, asked 2×
- [Significance of reflection coefficient; R1 = 1 Ω, R2 = 4 Ω](https://www.bctengineer.com/question.md?key=semester_5%2Ffilter_design%3Areflection-significance-unequal-termination) — Filter Design, chapter 5