Schedules & Concurrency
In a busy database, thousands of transactions happen at the same time. To maximize throughput and utilize the CPU efficiently, the database management system (DBMS) interleaves their operations.
The specific sequence of execution for these interleaved operations is called a Schedule.
Serial vs Non-Serial Schedules
- Serial Schedule: Transactions execute sequentially, one after the other, with ZERO interleaving. T1 completely finishes before T2 even starts. This ALWAYS maintains database consistency, but it's incredibly slow because it offers no parallel processing.
- Non-Serial Schedule: Operations from multiple transactions are interleaved. T1 does a Read, then T2 does a Write, then T1 does a Write. This is fast and leverages concurrency, but it requires strict control mechanisms to prevent data corruption.
Serializability (Ensuring Consistency)
Serializability is the concept used to determine if a fast, non-serial schedule is actually safe. A non-serial schedule is considered Serializable if it produces the exact same results as SOME serial execution of those same transactions.
Conflict Serializability
A schedule is Conflict Serializable if it can be safely transformed into an equivalent serial schedule simply by swapping adjacent, non-conflicting operations.
For interviews, you MUST know exactly what a 'Conflict' is. Two operations conflict if they meet ALL THREE of these conditions:
- Different Transactions: They belong to different transactions (e.g., T1 and T2).
- Same Data Item: They both target the exact same data item (e.g., variable 'A').
- At Least One Write: At least one of the operations is a Write. This gives us three specific conflict types: Read-Write (RW), Write-Read (WR), and Write-Write (WW).
Example: Swapping Operations
| Time | T1 | T2 |
|---|---|---|
| 1 | Read(A) | |
| 2 | Read(A) |
| Time | T1 | T2 |
|---|---|---|
| 1 | Write(A) | |
| 2 | Read(A) |
In the first schedule, Read-Read is safe. Swapping their execution order changes nothing. In the second schedule, if we swap them, T2 will read the OLD value of A instead of T1's new value. We cannot swap conflicting operations!
View Serializability & Blind Writes
A schedule is View Serializable if its final visible behavior is equivalent to a serial schedule.
Every conflict serializable schedule is automatically view serializable. However, some schedules that contain Blind Writes (writing a variable without ever reading it first) might not be conflict serializable, but can still be view serializable.
Recoverability (Dealing with Failures)
Serializability ensures data is mathematically correct. But what happens if a transaction crashes halfway through? The database must be able to roll back its changes. This brings us to Recoverability.
The Dirty Read Anomaly (Irrecoverable Schedules)
An irrecoverable schedule occurs when Transaction T2 reads a value modified by an uncommitted Transaction T1 (this is called a Dirty Read), and then T2 COMMITS before T1 commits.
Why is a Dirty Read a disaster?
| Time | T1 | T2 |
|---|---|---|
| 1 | Write(A=500) | |
| 2 | Read(A=500) | |
| 3 | Write(Fee based on A) | |
| 4 | COMMIT (Permanently saved!) | |
| 5 | System Crash! | |
| 6 | ABORT (Rolls A back to 100) |
Notice what happened at Time 6. T1 crashed and rolled back its changes. However, T2 had already committed its calculations based on the fake $500 at Time 4! Because T2 is committed, the DBMS cannot undo it. The database is now permanently corrupted.
Types of Recoverable Schedules
- Recoverable Schedule: To prevent irrecoverable corruption, we force a rule: T2 must delay its commit until T1 (who provided the data) has committed. If T1 aborts, T2 can also abort safely.
- Cascading Schedule: While safe, basic recoverability has a flaw: the domino effect. If T1 aborts, T2 must abort. If T3 read from T2, T3 must abort. Aborting one transaction can cause a massive cascade of aborted transactions, wasting huge amounts of CPU time.
- Cascadeless Schedule: To stop the domino effect, we enforce a stricter rule: Transactions are completely PROHIBITED from reading uncommitted data. T2 must wait for T1 to commit before it even reads the variable.
- Strict Schedule: The strictest rule. Transactions can neither read NOR write a data item until the transaction that last modified it has committed or aborted. This makes rolling back incredibly simple, as the system just restores the 'old image' of the data.
Schedule Summary Matrix
| Schedule Type | Key Structural Characteristic | System Recovery Impact |
|---|---|---|
| Serial | Transactions execute sequentially with no interleaving. | Always safe and recoverable, but offers no concurrency. |
| Conflict Serializable | Equivalent to a serial schedule by swapping non-conflicting ops. | Guarantees consistency while allowing concurrent execution. |
| Recoverable | Delay commits until all source transactions commit. | Prevents data loss but can still suffer from cascading aborts. |
| Cascadeless | Transactions can ONLY read committed data. | Eliminates cascading aborts, greatly simplifying recovery. |
| Strict | Transactions can neither read nor write uncommitted data. | Simplifies recovery by allowing updates to be cleanly restored using old images. |
Placement Takeaways
For written rounds, you will almost certainly be given a schedule diagram (e.g., R1(A), W2(A), R2(B), W1(B)) and asked if it is Conflict Serializable.
Fill in the Blank
Sort the Concepts
Drag the scheduling rule into its proper Recoverability bucket: