Testing Serializability of a Schedule

 

🔍 Concept: Testing Serializability of a Schedule

---

📌 What is the Goal?

To determine whether a given schedule (interleaving of transactions) behaves like a serial execution.

---

🧠 Basic Idea

Instead of rearranging operations, we:

👉 Build a precedence graph
👉 Check for dependency cycles

---

📊 Precedence Graph

• Nodes → Transactions (T1, T2, …)
• Edges → Dependency due to conflicting operations

---

⚠️ What are Conflicts?

Two operations conflict if:

• They belong to different transactions
• They access the same data item
• At least one is a write

Types:

• Write → Read
• Read → Write
• Write → Write

---

🔗 Meaning of an Edge

If:

Ti → Tj

👉 Transaction Ti must execute before Tj

---

🔄 Final Decision

✅ No Cycle

• Schedule is conflict serializable
• Equivalent serial order exists

---

❌ Cycle Exists

• Schedule is not serializable
• No valid serial execution possible

---

🧩 Why Cycles Matter?

A cycle means:

Ti depends on Tj
AND
Tj depends on Ti

👉 Circular dependency → impossible ordering

---

🎯 Key Insight

The algorithm works by:

Build a dependency graph

If dependencies form a loop → impossible

If no loop → transactions can be ordered safely

---

🧾 Algorithm : Testing Conflict Serializability

Steps

1. For each transaction $T_i$ in schedule $S$, create a node labeled $T_i$ in the precedence graph.

2. For each case where $T_j$ executes read_item(X) after $T_i$ executes write_item(X), create an edge:

   $$T_i\to T_j$$

3. For each case where $T_j$ executes write_item(X) after $T_i$ executes read_item(X), create an edge:

   $$T_i\to T_j$$

4. For each case where $T_j$ executes write_item(X) after $T_i$ executes write_item(X), create an edge:

   $$T_i\to T_j$$
5. The schedule $S$ is conflict serializable if and only if the precedence graph has no cycles.

Step 1: Create nodes

For each transaction Ti in schedule S, create a node Ti.

✅ Meaning:

• Each transaction becomes a node in the graph
• Example: T1, T2, T3 → nodes

---

Step 2: Write → Read conflict

If Tj reads X after Ti writes X, add edge (Ti → Tj).

📌 Condition:

Ti: W(X) → Tj: R(X)

✅ Meaning:

• Tj is reading a value written by Ti
  👉 So Ti must come before Tj

---

Step 3: Read → Write conflict

If Tj writes X after Ti reads X, add edge (Ti → Tj).

📌 Condition:

Ti: R(X) → Tj: W(X)

✅ Meaning:

• Tj overwrites a value read by Ti
  👉 So Ti must come before Tj

---

Step 4: Write → Write conflict

If Tj writes X after Ti writes X, add edge (Ti → Tj).

📌 Condition:

Ti: W(X) → Tj: W(X)

✅ Meaning:

• Two writes on same data
  👉 Order must be preserved

---

🚫 Important:

• Ignore Read–Read (R–R) → no conflict

---

Step 5: Check for cycles

Schedule is serializable if and only if graph has no cycles.

---

🔄 What is a Cycle?

A cycle is a loop like:

T1 → T2 → T3 → T1

❌ Meaning:

• T1 must come before T2
• T2 before T3
• T3 before T1

👉 Impossible → Not Serializable

---

✅ If NO cycle:

• Schedule is conflict serializable
• We can find a valid serial order

🧩 If No Cycle → How to Find Serial Order?

Use the graph:

• Follow direction of edges

• Arrange transactions so that:

  Ti → Tj ⇒ Ti comes before Tj
  

👉 This is called topological ordering

---

Key Insight

👉 Each edge means:

Ti → Tj ⇒ Ti must execute before Tj

👉 If all such constraints can be satisfied → serializable

📊 Summary Table

Step	Action
1	Create node for each transaction
2	Add edges for conflicts (W-R, R-W, W-W)
3	Check graph
4	Cycle? → ❌ Not serializable
	No cycle? → ✅ Serializable

Example

Problem

(i) Schedule S1: check whether the schedule conflict serializable

R1(X), R2(X), R1(Y), R2(Y), R3(Y), W1(X), W2(Y)

---

🔹 Step 1: Transactions

T1, T2, T3

---

🔹 Step 2–4: Find conflicts and add edges

On data item X:

• R2(X) before W1(X) → Read–Write conflict
  → Edge: T2 → T1

---

On data item Y:

• R1(Y) before W2(Y) → Read–Write conflict
  → Edge: T1 → T2
• R3(Y) before W2(Y) → Read–Write conflict
  → Edge: T3 → T2

---

🔹 Step 5: Precedence Graph

Edges:

• T2 → T1
• T1 → T2
• T3 → T2

---

🔁 Check Cycle

We have:

T1 → T2 → T1  ❌ (cycle)

---

❌ Final Answer (S1):

Not conflict serializable

---

(ii) Schedule S2

R1(X), R2(X), R2(Y), W2(Y), R1(Y), W1(X)

---

🔹 Step 1: Transactions

T1, T2

---

🔹 Step 2–4: Find conflicts

On X:

• R2(X) before W1(X) → Read–Write conflict
  → Edge: T2 → T1

---

 On Y:

• W2(Y) before R1(Y) → Write–Read conflict
  → Edge: T2 → T1

---

🔹 Step 5: Precedence Graph

Edges:

• T2 → T1

---

🔁 Check Cycle

• No cycle

---

✅ Final Answer (S2):

Conflict serializable

Equivalent serial order:

T2 → T1

---