Transactions, concurrency control and recovery notes — Unit 5

A database must remain in a consistent mathematical state at all times. However, user operations often require multiple separate SQL statements to complete a logical task.

Consider a bank transfer of $100 from Account A to Account B. 1. Read A's balance. 2. Deduct$100 from A.
3. Read B's balance.
4. Add $100 to B.

If the server loses power exactly after step 2, Account A loses money, but Account B never receives it. The money is destroyed, and the database is corrupt.

⇒1.1 The Definition

A Transaction is a logical unit of work consisting of one or more SQL statements. The DBMS treats a transaction as a single, indivisible operation.

To guarantee database integrity, the DBMS must ensure every transaction rigorously follows four absolute rules, known as the ACID properties.

• Atomicity (All or Nothing): The entire transaction executes completely, or it doesn't execute at all. If it fails halfway, the DBMS automatically undoes (Rolls Back) any partial changes.
• Consistency: A transaction must transform the database from one valid, consistent state to another valid, consistent state, adhering to all constraints (e.g., money cannot be created from thin air).
• Isolation: When hundreds of transactions execute concurrently, the intermediate, incomplete state of one transaction must remain entirely invisible to all other transactions. They should execute as if they were running sequentially in absolute isolation.
• Durability: Once a transaction successfully completes (Commits), its changes are permanent. They must survive any subsequent hardware crash, power outage, or system failure. The data is safely written to the physical disk.

A transaction goes through a strict lifecycle.

• Active: The initial state. The transaction is currently executing its read/write statements.
• Partially Committed: Executed the final statement, but the data is still in RAM buffers, not permanently written to disk.
• Committed: The transaction completed successfully, and all changes are permanently saved to the hard drive. It can no longer be rolled back.
• Failed: The transaction encountered an error (e.g., divide by zero, constraint violation, or deadlock) and cannot proceed.
• Aborted: The DBMS has successfully rolled back all changes made by the Failed transaction. The database is restored to the exact state it was in before the transaction started.

When millions of users access a database simultaneously, transactions overlap. If the DBMS does not control this concurrency, disastrous anomalies occur.

⇒4.1 The Three Classic Problems

• Lost Update Problem: Transaction T1 and T2 both read Account A ($100). T1 adds$50, making it $150, and writes it. A millisecond later, T2 subtracts$20 from its original read value of $100, making it$80, and writes it. T1's deposit is completely overwritten and permanently lost.
• Dirty Read (Uncommitted Dependency): T1 updates Account A to $200. T2 reads the new value of$200. Then, T1 encounters an error and Aborts (rolling back A to $100). T2 is now working with "dirty" data that mathematically never existed in the database.
• Unrepeatable Read: T1 reads Account A ($100). T2 updates Account A to$150 and Commits. T1 reads Account A again later in its logic and gets $150. T1 got two different answers for the exact same query within the same transaction.

A Schedule is the chronological execution order of the read/write operations of multiple concurrent transactions.

⇒5.1 Serial vs. Concurrent Schedules

A Serial Schedule runs transactions one after the other. T1 finishes completely, then T2 starts. This guarantees absolute consistency, but destroys performance. Users would wait hours for their queries.

A Concurrent Schedule interleaves the operations of T1 and T2 for maximum performance. However, some interleavings cause the anomalies mentioned earlier.

⇒5.2 Serializability

The ultimate goal of the DBMS. A concurrent schedule is Serializable if and only if its final mathematical outcome is perfectly identical to the outcome of some Serial schedule.

If a schedule is serializable, it is guaranteed to be 100% safe and consistent, while still providing the high performance of concurrency.

How does the DBMS test if a schedule is serializable? It checks for conflicts.

Two operations belonging to different transactions conflict if they access the exact same data item and at least one of them is a Write.

• Read-Read: No conflict. Safe.
• Read-Write: Conflict. Order matters.
• Write-Read: Conflict. Order matters.
• Write-Write: Conflict. Order matters.

⇒6.1 Precedence Graph Testing

To test for Conflict Serializability, we draw a Precedence Graph (Serialization Graph).

1. Draw a node for each transaction (T1, T2).
2. Draw a directed arrow from T1 to T2 if T1 executes a conflicting operation before T2 does on the same data.
3. The Rule: If the resulting graph contains a Cycle (a loop, T1 $\rightarrow$ T2 $\rightarrow$ T1), the schedule is NOT conflict serializable and must be aborted.

Instead of testing schedules after the fact, the DBMS uses protocols to ensure non-serializable schedules can never be generated in the first place. The most common method is Locking.

⇒7.1 Types of Locks

• Shared Lock (S-Lock): Allows a transaction to only Read the data. Multiple transactions can hold an S-Lock on the same data item simultaneously.
• Exclusive Lock (X-Lock): Allows a transaction to both Read and Write the data. If a transaction holds an X-Lock, absolutely no other transaction can hold any lock on that data item. They must wait.

Just having locks is not enough. If T1 locks A, and T2 locks B, the schedule might still be non-serializable. We need a strict protocol.

2PL is the industry-standard algorithm used by nearly all relational databases (like MySQL InnoDB) to guarantee serializability.

⇒8.1 The Two Phases

Every transaction must follow a strict lifecycle of locking:

• 1. Growing Phase: A transaction may obtain new locks as needed, but it is strictly forbidden from releasing any lock it holds.
• 2. Shrinking Phase: Once a transaction releases its very first lock, it enters the shrinking phase. It may release remaining locks, but it is strictly forbidden from acquiring any new locks.

Mathematical Guarantee: Any schedule generated by transactions that obey the 2PL protocol is mathematically guaranteed to be Conflict Serializable.

⇒8.2 The Deadlock Flaw

While 2PL prevents inconsistency, it is highly susceptible to Deadlocks. T1 locks A, T2 locks B. T1 wants B, T2 wants A. They both wait forever. The DBMS must actively monitor for deadlocks and abort one of the transactions.

An alternative to locking. It completely eliminates the possibility of deadlocks because it never forces a transaction to wait.

⇒9.1 The Mechanism

When a transaction starts, the OS gives it a unique Timestamp (TS). Older transactions have smaller timestamps.

Every piece of data (e.g., Account A) stores two timestamps on the disk:
- `Read_TS(A)`: The timestamp of the youngest transaction to read it.
- `Write_TS(A)`: The timestamp of the youngest transaction to write it.

When T1 tries to read or write A, the protocol checks the timestamps. If T1 is attempting an operation that logically conflicts with something a "younger" transaction has already done, T1 is rejected, aborted, and restarted with a new timestamp.

Thomas Write Rule: A specific optimization for timestamp ordering that allows the DBMS to safely ignore outdated writes, improving concurrency.

The 'D' in ACID is Durability. A system crash (power failure, OS panic) destroys all data in RAM. If a transaction committed seconds before the crash, its data must survive.

The DBMS Recovery Manager guarantees this using specialized disk logging techniques.

⇒10.1 The System Log

The Log (or Journal) is a highly secure, append-only file kept on stable storage (a separate physical hard drive). Before the DBMS modifies the actual database files, it writes a record of the intended change to the Log.

Log records contain:
`<Transaction_ID, Data_Item, Old_Value, New_Value>`

WAL is the absolute golden rule of database recovery.

⇒11.1 The Protocol

A data block in RAM cannot be written to the physical database disk until the corresponding log record has been safely written to the physical log disk.

Furthermore, when a transaction issues a `COMMIT` command, the DBMS does not immediately force the massive data files to disk (too slow). Instead, it forces a tiny `<T1 COMMIT>` record to the Log disk. Once the log hits the disk, the transaction is considered officially committed.

If power is lost instantly after this, the data is lost from RAM. But upon reboot, the Recovery Manager reads the Log, sees the COMMIT, and replays the new values into the database (Redo).

⇒12.1 Deferred Update (No-Undo / Redo)

The transaction performs all its writes entirely in RAM buffers. The physical database on disk is NEVER modified until after the transaction officially commits.

If the system crashes before commit, the RAM is wiped, and the database remains untouched. No "Undo" is ever required. However, large transactions consume massive amounts of RAM.

⇒12.2 Immediate Update (Undo / Redo)

The DBMS is allowed to write uncommitted, intermediate changes directly to the physical database disk (to save RAM), provided it follows the WAL rule.

If the system crashes before commit, the physical database now contains garbage data. Upon reboot, the Recovery Manager must read the Log backwards, find the `Old_Value`, and overwrite the garbage data in the database (Undo).

If a database runs for a year and crashes, reading the entire year-long Log file line-by-line to perform recovery would take days. We need a way to truncate the log.

⇒13.1 The Checkpoint Process

Periodically (e.g., every 5 minutes), the DBMS performs a Checkpoint:

• 1. Temporarily pauses accepting new transactions.
• 2. Forces all modified data buffers in RAM to be written permanently to the database disk.
• 3. Writes a `<CHECKPOINT>` record to the Log disk.
• 4. Resumes operations.

When a crash occurs, the Recovery Manager scans backwards in the log to find the most recent `<CHECKPOINT>`. It knows with absolute mathematical certainty that any transaction that committed before that checkpoint is safely on disk. The system only needs to Redo/Undo transactions that were active after the checkpoint, reducing recovery time from days to seconds.

Unit 5 covers the high-end architecture that makes enterprise databases reliable.

⇒14.1 University Exam Checklist

• Define a Transaction. Explain the four ACID properties in detail.
• Draw the state transition diagram of a transaction.
• Explain the Lost Update, Dirty Read, and Unrepeatable Read concurrency problems with examples.
• What is a Schedule? Define Conflict Serializability.
• Given a schedule of Read/Write operations, draw the Precedence Graph and determine if it is conflict serializable.
• Explain the Two-Phase Locking (2PL) protocol (Growing and Shrinking phases). Does it prevent deadlocks?
• What is the system Log? Explain the strict rule of Write-Ahead Logging (WAL).
• Explain the difference between Deferred Update and Immediate Update recovery techniques.
• What is Checkpointing? Why is it absolutely necessary for crash recovery?