27 - Serializability

🎯 Learning Objectives

• Determine if two operations conflict
• Build a precedence graph and test conflict serializability
• Distinguish conflict from view serializability
• Understand recoverability and cascadeless schedules

📖 Core Content

27.1 Conflict Serializability

Conflicting Operations

1. They belong to different transactions
2. They operate on the same data item
3. At least one is a write

Precedence Graph

1. Create a node for each transaction
2. Add edge $T_i \rightarrow T_j$ if an operation in $T_i$ conflicts with and precedes an operation in $T_j$
3. If the graph has a cycle, the schedule is NOT conflict serializable
4. If acyclic, conflict serializable (any topological ordering gives an equivalent serial schedule)

27.2 Worked Example

• $w_1(A) \rightarrow r_2(A)$: T1→T2
• $w_1(A) \rightarrow w_2(A)$: T1→T2
• $r_2(A) \rightarrow w_1(B)$? No (different data)
• $w_2(A) \rightarrow w_1(B)$? No
• $w_1(B) \rightarrow r_2(B)$: T1→T2 Graph: T1→T2 (no cycle). Schedule is conflict serializable (equivalent to T1 then T2).

27.3 View Serializability

1. Same initial reads: Each data item's first read is from the same transaction
2. Same final writes: Each data item's last write is by the same transaction
3. Same reads from writes: If Tj reads a value written by Ti in S1, the same holds in S2 View serializability: A schedule is view serializable if it's view equivalent to some serial schedule. Key fact: Every conflict serializable schedule is view serializable, but NOT vice versa. View serializable schedules that aren't conflict serializable involve blind writes (write without prior read).

27.4 Recoverability

• T1: write(A), T2: read(A), T2: commit, T1: abort
• T2 read uncommitted data from T1, then committed, then T1 aborted → T2's read is now invalid! This database is inconsistent.

📐 Key Formula

⚠️ Common Pitfall

📝 Practice Questions

Q1. What makes two operations conflict?

Answer

Three conditions: (1) different transactions, (2) same data item, (3) at least one is a write.

Q2. Draw the precedence graph for: r1(A), w2(A), w1(A), r2(A)

Answer

Conflicts:

• r1(A) → w2(A): T1→T2 (read-write)
• w2(A) → w1(A): T2→T1 (write-write)
• w2(A) → r2(A): Same transaction, ignore
• w1(A) → r2(A): T1→T2 (write-read)

Edges: T1→T2, T2→T1. This is a CYCLE! Schedule is NOT conflict serializable.

Q3. What's the difference between recoverable and cascadeless schedules?

Answer

• Recoverable: If Ti reads from Tj, Ti commits after Tj. No dirty reads from uncommitted transactions.
• Cascadeless: Ti reads from Tj only AFTER Tj commits. Prevents cascading rollbacks entirely.

Q4. Find the number of possible concurrent schedules for T1(2 ops), T2(2 ops), T3(1 op).

Answer

Total operations = 5. Number of schedules = $\frac{5!}{2!2!1!} = \frac{120}{4} = 30$. (All permutations divided by internal order within each transaction.)

🔗 Cross-References

• Next Topic: 28 - Concurrency Control
• Previous Topic: 26 - Transactions & ACID
• Related: 28 - Concurrency Control (protocols to ensure serializability)
• Textbook: Chapter 14 (Transactions), Chapter 15 (Concurrency Control) Join Discord Previous26 - Transactions & ACIDNext28 - Concurrency Control