Serializability & Schedules
Concurrent execution of transactions is necessary for performance, but it must be correct. A Schedule is the order in which operations of multiple transactions are executed.
Learning Objectives
After completing this chapter, you will be able to:
- Differentiate between serial and concurrent schedules.
- Explain serializability and why it matters.
- Identify conflicting operations.
- Check conflict serializability using a Precedence Graph.
- Understand view serializability.
- Answer interview questions on schedules and serializability.
Types of Schedules
Serial Schedule
Transactions execute one after another — T1 completely finishes, then T2 starts.
T1: Read(A) Write(A) Read(B) Write(B)
T2: Read(A) Write(A) Read(B) Write(B)
Time ─────────────────────────────────────────────────────────────→Pros: Always consistent (no interference). Cons: Slow — only one transaction runs at a time.
Concurrent Schedule
Operations of multiple transactions are interleaved.
T1: Read(A) Write(A) Read(B) Write(B)
T2: Read(A) Write(A) Read(B) Write(B)
Time ─────────────────────────────────────────────────────────────→Pros: Much faster — utilizes CPU and I/O better. Cons: Can lead to inconsistencies if not controlled.
Serializability
A concurrent schedule is Serializable if its final result is equivalent to some serial schedule (T1 then T2, or T2 then T1).
Why This Matters
If a concurrent schedule is equivalent to a serial one, we know it’s correct — because we know serial schedules are always correct.
Conflicting Operations
Two operations conflict if all three conditions hold:
- They belong to different transactions
- They access the same data item
- At least one of them is a Write
| Op1 | Op2 | Conflict? | Reason |
|---|---|---|---|
| Read(A) | Read(A) | No | Both read, order doesn’t matter |
| Read(A) | Write(A) | Yes | Different T, same data, one write |
| Write(A) | Read(A) | Yes | Different T, same data, one write |
| Write(A) | Write(A) | Yes | Different T, same data, both write |
| Read(A) | Write(B) | No | Different data items |
Conflict Serializability
A schedule is Conflict Serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.
Precedence Graph Method
Algorithm:
- Create a node for each transaction
- Draw an edge Ti → Tj if:
- Ti performs an operation that conflicts with a later operation of Tj
- AND Ti’s operation comes before Tj’s operation in the schedule
- If the graph has a cycle → NOT conflict serializable
- If the graph is acyclic → it IS conflict serializable
Example 1: Serializable Schedule
T1: Read(A) Write(A) Read(B) Write(B)
T2: Read(A) Write(A) Read(B) Write(B)Conflicts:
- T1 Write(A) → T2 Read(A) (T1 before T2, same data, one write)
- T1 Write(B) → T2 Read(B)
Graph: T1 → T2 (no cycle) → Serializable (equivalent to T1 then T2)
Example 2: Non-Serializable Schedule
T1: Read(A) Write(A) Read(B) Write(B)
T2: Read(A) Write(A) Read(B) Write(B)Conflicts:
- T1 Write(A) → T2 Read(A) → T1 → T2
- T2 Write(B) → T1 Read(B) → T2 → T1
Graph: T1 → T2 → T1 (CYCLE!) → NOT Serializable.
View Serializability
A broader concept. A schedule is View Serializable if it produces the same final result as some serial schedule — even if it’s not conflict serializable.
| Property | Conflict Serializability | View Serializability |
|---|---|---|
| Check method | Precedence Graph (O(N²)) | NP-Complete |
| Practical | Yes — used in DBMS | No — too slow to check |
| Coverage | Subset of view serializable | Superset (more schedules) |
Key insight: Every Conflict Serializable schedule is View Serializable, but not vice versa. DBMS use techniques (like 2PL) that guarantee Conflict Serializability.
Why Serializability Matters
| Without Serializability | With Serializability |
|---|---|
| Lost updates | Correct concurrent execution |
| Dirty reads | Isolation guaranteed |
| Inconsistent data | Data integrity preserved |
| Wrong final state | Equivalent to serial execution |
All DBMS concurrency control protocols (2PL, MVCC, Timestamp Ordering) aim to produce only serializable schedules.
Interview Deep Dive
Q: Which operations can we swap to check for Serializability?
A: We can swap any two consecutive operations from different transactions if they are non-conflicting. Read(A) and Read(A) → can swap. Read(A) and Write(B) → can swap (different data). Read(A) and Write(A) → CANNOT swap (conflict — same data, one write). Write(A) and Write(A) → CANNOT swap.
Q: How do you check for Conflict Serializability quickly?
A: Build a Precedence Graph. Create a node for each transaction. Draw an edge from Ti to Tj if Ti has a conflicting operation that occurs before Tj’s conflicting operation. If the graph has No Cycles, the schedule is Conflict Serializable. If there is a cycle, it’s not.
Q: Why is Conflict Serializability preferred over View Serializability in practice?
A: Testing for Conflict Serializability is fast (polynomial time — build and check a graph). Testing for View Serializability is NP-Complete — extremely slow for real-time use. Since all practical concurrency protocols (like Strict 2PL) guarantee Conflict Serializability, View Serializability is mainly a theoretical concept.
Q: What happens if a DBMS allows a non-serializable schedule?
A: The database can end up in an inconsistent state. Example: Two bank tellers simultaneously process transfers involving the same accounts. Without serializability, money can be created or lost. The final account totals won’t match what any serial execution would produce.
Key Takeaways
- Serial Schedule: One transaction at a time — always correct, slow.
- Concurrent Schedule: Interleaved operations — fast, but needs control.
- Serializability: A concurrent schedule is correct if it’s equivalent to some serial schedule.
- Conflicting Operations: Different T + same data + at least one write.
- Conflict Serializability: Checked via Precedence Graph — acyclic = serializable.
- View Serializability: Broader, but NP-Complete to check.
- Conflict serializability is the practical standard used in DBMS.
- Precedence Graph: Cycle = Non-serializable.
Premium Content
Unlock Serializability & Schedules and all premium lessons with a subscription.
From ₹199.99/year — See plans