Module 11: Transaction and Recovery Management¶

Concurrency Control¶

Basics of Transaction Processing¶

DML processing converts interactions with sets of tuples into sequences of operations that read and write physical objects in the database.

Database objects can correspond to:

Individual record fields
Records
Physical pages
Entire files (typically for concurrency control purposes)
Predicates qualifying one or more records, parts of records, etc.

Transaction and recovery management includes:

Ensuring correct and concurrent execution of operations for reading and writing physical objects originating from DML commands of client transactions.
Guaranteeing that acknowledged client transaction commits are reliably recorded and that acknowledged client transaction aborts are reliably undone.

Transactions¶

In a DBMS, transaction and recovery management are implemented through two subsystems:

Concurrency Control Management

Responsible for scheduling the execution of reads and writes on physical objects to ensure transaction isolation.
Recovery Management

Ensures transaction atomicity and durability.

Note: DML processing ensures transaction consistency as defined by integrity constraints.

Concurrency Control: Assumptions¶

A database consists of a finite set of independent physical objects \(x_j\) read and written by transactions \(T_i\).

Denoted as:
1. \(r_i[x_j]\): Transaction \(T_i\) reads object \(x_j\).
2. \(w_i[x_j]\): Transaction \(T_i\) writes (modifies) object \(x_j\).
3. A transaction \(T_i\) is a sequence of read and write operations:
\[ T_i = r_i[x_1], r_i[x_2], w_i[x_1], \dots, r_i[x_4], w_i[x_2], c_i \]

where \(c_i\) is the commit request of \(T_i\).
For a set of transactions \(\{T_1, \dots, T_k\}\), we aim to produce an execution order of operations \(S\), called a schedule, such that:
1. Every operation \(o_i \in T_i\) appears in \(S\).
2. \(T_i\)'s operations in \(S\) maintain the order of \(T_i\).

Goal: Produce a correct schedule with maximal parallelism.

Transactions and Schedules¶

If \(T_i\) and \(T_j\) are concurrent transactions, it is always correct to schedule their operations such that:

\(T_i\) precedes \(T_j\):

\(T_j\) sees all updates made by \(T_i\), and \(T_i\) does not see any updates made by \(T_j\).
\(T_i\) follows \(T_j\):

\(T_i\) sees \(T_j\)'s updates, and \(T_j\) does not see \(T_i\)'s updates.

Idea

Define a schedule \(S\) to be correct if it appears to clients that the transactions are executed sequentially, that is, in some strictly serial order.

Serializable Schedule

A schedule \(S\) is serializable if it is equivalent to some serial execution of the same transactions.

Note

❗

Concept Explanation from ChatGPT:

A serializable schedule ensures the consistency of a database by mimicking the behavior of a serial schedule.

Serial Schedule: Transactions are executed one after another without interleaving.
Serializable Schedule: Although transactions may execute concurrently (with interleaving), their outcome is equivalent to a serial schedule in terms of the final state of the database.

Serializable Schedules¶

How do we determine if two schedules are equivalent?

Cannot be based on any particular database instance.

Conflict Equivalence

Two operations conflict if they:

Belong to different transactions.
Access the same data item \(x\).
At least one of them is a write operation \(w[x]\).

Two schedules \(S_1\) and \(S_2\) are conflict equivalent when all conflicting operations are ordered the same way.

A schedule \(S_1\) is a conflict serializable schedule if it is conflict equivalent to some serial schedule \(S_2\).

Note

❗

Concept Explanation from ChatGPT:

Conflict Equivalence refers to a relationship between two schedules based on how they handle conflicting operations.

Conflicting operations arise between different transactions when:
1. They access the same data item.
2. At least one of them is a write operation.

Two schedules, \(S_1\) and \(S_2\), are conflict equivalent if they maintain the same relative order for all pairs of conflicting operations.

For example:

If \(w[x]\) (write on \(x\)) from \(T_1\) precedes \(r[x]\) (read on \(x\)) from \(T_2\) in \(S_1\), the same order must hold in \(S_2\) for \(S_1\) and \(S_2\) to be conflict equivalent.

Conflict Serializable Schedule: A schedule is conflict serializable if it is conflict equivalent to a serial schedule (a schedule where transactions are executed one after the other without interleaving). This ensures that the non-serial schedule produces the same result as the serial schedule, preserving correctness.

Note

❗

Concept Explanation from ChatGPT: (How to find the Equivalent Serial Order)?

A topological sort is an ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge \(u \to v\), vertex \(u\) appears before vertex \(v\) in the ordering.

Key Points:

Applies to DAGs: Topological sort is only defined for directed graphs with no cycles.
Order Constraints: It respects the dependency structure of the graph, ensuring that each vertex \(v\) is processed only after all vertices pointing to \(v\) (its prerequisites) are processed.

Steps to Perform Topological Sort:

Identify Nodes with No Incoming Edges: Start with vertices that have no incoming edges (i.e., vertices with in-degree 0).
Remove the Vertex: Remove this vertex from the graph and update the in-degrees of its neighbors.
Repeat Until All Nodes Are Processed: Continue selecting vertices with in-degree 0, removing them, and updating neighbors' in-degrees.
Output the Order: The order in which the vertices are removed forms the topological sort.

Example:

Graph:

Vertices: \(A, B, C, D\)
Edges: \(A \to B\), \(A \to C\), \(B \to D\), \(C \to D\)

Process:

\(A\) has no incoming edges → Start with \(A\).
Remove \(A\), update in-degrees:
- \(B\) and \(C\) now have no incoming edges.
Process \(B\), then \(C\), and finally \(D\).

Topological Sort:

\[ A \to B \to C \to D \]

View Equivalence

Preserves initial reads and final writes; allows more schedules, but is harder (NP-hard) to diagnose.

Note

❗

Concept Explanation from ChatGPT:

View Equivalence focuses on preserving the following aspects of transactions across schedules:

Initial Reads: If a transaction \(T_i\) reads a value \(x\) (whether it's the initial value or written by another transaction) in one schedule, the same read must occur in the other schedule.
Final Writes: The last transaction that writes a value \(x\) in one schedule must also be the last to write \(x\) in the other schedule.
Same Initial Value: If a transaction reads the initial value of a data item \(x\) in one schedule, it must do the same in the other schedule.

A schedule is view equivalent to another schedule if these conditions are satisfied.

While view equivalence allows a broader set of schedules compared to conflict equivalence, determining whether two schedules are view equivalent is computationally more challenging, as it is an NP-hard problem.

How does one diagnose if a schedule \(S\) is a conflict serializable schedule?

Serialization Graph

A serialization graph \(SG(N, E)\) for a schedule \(S\) is a directed graph with:

Nodes \(T_i \in N\), corresponding to the transactions of \(S\).
Edges \(T_i \to T_j \in E\), whenever an operation \(o_i[x]\) for transaction \(T_i\) occurs prior to an operation \(o_j[x]\) for transaction \(T_j\) in \(S\), where \(o_i[x]\) and \(o_j[x]\) are conflicting operations.

Theorem

A schedule \(S\) is serializable if and only if the serialization graph \(SG\) for \(S\) is acyclic.

Other Properties of Schedules¶

Serializability guarantees correctness. However, some undesirable situations need to be avoided:

Recoverable Schedules (RC)

The situation: Transaction \(T_j\) reads a value \(T_i\) has written. Then, \(T_j\) commits, but \(T_i\) attempts to abort.

Aborting \(T_i\) makes it necessary to undo the effects of a committed transaction \(T_j\).

The repair: Allow committing only in the order of the read-from dependency between transactions.

Cascadeless Schedules (ACA)

The situation: Transaction \(T_j\) reads a value \(T_i\) has written. Then, \(T_i\) attempts to abort.

Aborting \(T_i\) makes it necessary to abort \(T_j\), which may lead to a cascade of further aborts of other transactions.

The repair: Do not allow transactions to read uncommitted objects.

Two Phase Locking¶

How does a DBMS admit ultimate schedules for executing operations of transactions that are conflict serializable and cascade-free?

The DBMS scheduler is responsible for this.

It receives requests to execute operations from the query processor(s).
For each operation, it chooses one of the following actions:
- Execute it (by sending it to a lower module).
- Delay it (by inserting it in some queue).
- Reject it (thereby causing an abort of the transaction).
- Ignore it (since it has no effect).

Types of Schedulers:

Conservative schedulers favor delaying operations.
Aggressive schedulers favor rejecting operations.

Conservative schedulers are lock-based.

A simple lock-based scheduler requires transactions to have a lock on objects before accessing them:

Shared lock: Required to read an object.
- A shared lock is a type of lock in database systems that allows multiple transactions to read a data item at the same time, but it prevents any transaction from writing to the data item while the shared lock is held.
Exclusive lock: Required to write an object. An exclusive lock on an object \(x\) by a transaction disallows any other lock on \(x\) by any other transaction.

It is insufficient for a scheduler to just acquire a lock, access the data item, and then release it immediately.

Note

❗

Concept Explanation from ChatGPT:

It is insufficient for a scheduler to acquire a lock, access a data item, and then release it immediately because it compromises transaction isolation and serializability, which are essential for maintaining the consistency and correctness of database transactions. Here’s why:

Loss of Isolation:
- Problem: If a transaction releases the lock immediately after accessing a data item, other transactions can access or modify the same data item before the first transaction completes.
- Example:
  - Transaction T1 reads data \(x\) and releases its lock.
  - Transaction T2 then writes a new value to \(x\).
  - When T1 tries to access \(x\) again, it might read an inconsistent value (the updated value from T2), violating isolation.
Non-Repeatable Reads:
- Problem: A transaction may read the same data item multiple times and get different values if another transaction modifies the data in between reads.
- Example:
  - T1 acquires a lock on \(x\), reads its value (10), and releases the lock.
  - T2 acquires the lock, writes a new value to \(x\) (20), and releases the lock.
  - When T1 reads \(x\) again, it sees the updated value (20), leading to non-repeatable reads.
Lost Updates:
- Problem: If two transactions update the same data item without holding locks until they complete, one transaction's update may overwrite the other's.
- Example:
  - T1 reads \(x\) = 10, computes a new value (\(x\) = 15), and releases the lock.
  - T2 reads \(x\) = 10, computes another new value (\(x\) = 20), and releases the lock.
  - Both transactions then write their updates. If T2 writes after T1, T1’s update is lost, and \(x\) becomes 20 instead of 15.
Dirty Reads:
- Problem: If a transaction reads data written by another transaction that is not yet committed, and that transaction is rolled back, the data read by the first transaction becomes invalid.
- Example:
  - T1 writes a value to \(x\) but hasn’t committed yet.
  - T2 reads the value of \(x\), relying on T1’s uncommitted data.
  - If T1 is rolled back, T2 has used invalid data.
Cascading Aborts:
- Problem: If one transaction depends on the results of another uncommitted transaction that later aborts, it may need to be aborted as well, leading to a cascade of rollbacks.
- Example:
  - T1 writes to \(x\) and releases the lock before committing.
  - T2 reads the new value of \(x\) and uses it in its calculations.
  - If T1 is rolled back, T2 must also be rolled back, even if T2 has already performed additional operations.

Correct Approach: Locks (shared or exclusive) must be held until the transaction commits (successfully completes all its operations) or aborts (rolls back its changes due to failure or conflict). This prevents conflicts between transactions and ensures correctness.

Two Phase Locking

A scheduler follows the two phase locking protocol (2PL) if it allows no lock to be acquired by a transaction \(T\) on any object after the first lock by \(T\) on some other (not necessarily distinct) object is released by \(T\).

Note

❗

Concept Explanation from ChatGPT:

Two Phase Locking (2PL) is a concurrency control protocol ensuring conflict serializability by managing when locks are acquired and released by transactions. The protocol works as follows:

A transaction \(T\) operates in two distinct phases:
1. Growing Phase: \(T\) can acquire locks (shared or exclusive) but cannot release any locks.
2. Shrinking Phase: \(T\) can release locks but cannot acquire any new locks.

Key Rule:

Once a transaction \(T\) releases its first lock, it cannot acquire any additional locks on any object, regardless of whether it’s the same or a different object.

Benefits:

Ensures that the schedule generated is conflict serializable, meaning it behaves as though the transactions were executed in some serial order.

Drawbacks:

May lead to deadlocks if multiple transactions are waiting for each other to release locks.

Example:

Transaction \(T_1\) locks \(x\), then locks \(y\) (growing phase), and later releases the lock on \(x\) (shrinking phase). After releasing \(x\), \(T_1\) cannot acquire any further locks (e.g., \(z\)).

Theorem

Any execution order of operations admitted by a scheduler following the two phase locking protocol will be a prefix of an ultimate schedule that is a conflict serializable schedule.

Note

❗

Concept Explanation from ChatGPT:

This theorem asserts that any partial execution (prefix) of operations under the Two Phase Locking (2PL) protocol will eventually lead to a complete schedule that is conflict serializable. Let’s break it down:

Key Concepts

Two Phase Locking Protocol:
- Transactions have two distinct phases:
  - Growing Phase: Locks can only be acquired.
  - Shrinking Phase: Locks can only be released.
- Once a transaction releases a lock, it cannot acquire any more locks.
Conflict Serializable Schedule:
- A schedule is conflict serializable if it is equivalent (in terms of conflicting operations) to some serial schedule.
Prefix of an Ultimate Schedule:
- A prefix is the set of operations executed so far, before all transactions complete.
- The ultimate schedule is the final schedule once all transactions have completed.

Explanation

Conflict Serializability Guarantee:
- The 2PL protocol ensures that no conflicting operations can happen in a way that creates cycles in the serialization graph. This is because the protocol enforces an order among transactions by controlling when locks are acquired and released.
- Therefore, any complete schedule produced under 2PL is conflict serializable.
Prefix Property:
- At any intermediate point in execution (i.e., before all transactions finish), the executed operations form a prefix of the ultimate schedule.
- Since 2PL prevents conflicting operations from occurring out of order, this prefix cannot violate conflict serializability. It is always consistent with the rules of 2PL.
Ultimate Schedule:
- Once all transactions complete under 2PL, the ultimate schedule is a conflict serializable schedule. The prefix you observe during execution will always align with this final serializable schedule.

Intuition:

Imagine transactions as runners in a race with strict rules about overtaking:

Each runner (transaction) must acquire a baton (lock) before running and must hand it off (release the lock) when finished.
The order of passing the baton enforces a dependency between runners.
At any point during the race, the order of completed baton passes (prefix) respects the ultimate outcome (finish line order), ensuring no violations of the rules.

Conclusion:

The 2PL protocol enforces conflict serializability, and any partial execution (prefix) is guaranteed to align with a valid final schedule. This makes the theorem true.

Strict Two Phase Locking¶

The 2PL locking protocol can still allow operations that lead to:

Cascading aborts.
Deadlock.

A refinement of 2PL addresses the first problem.

Strict Two Phase Locking

A scheduler follows the strict two phase locking protocol (strict 2PL) if it allows no lock for a transaction \(T\) to be released until \(T\) requests either a commit or abort operation.

Theorem

Any execution order of operations admitted by a scheduler following the strict two phase locking protocol will:

Be a prefix of an ultimate schedule that is a conflict serializable schedule.
Have the ACA property, ensuring there are no cascading aborts.

Note

❗

Concept Explanation from ChatGPT:

No Cascading Aborts (ACA Property)

Problem with Cascading Aborts:
- In standard 2PL, a transaction might read or write a value that is modified by another uncommitted transaction. If the modifying transaction aborts, all dependent transactions must also abort (cascade).
How Strict 2PL Prevents This:
- Since locks are released only after a transaction commits or aborts, no other transaction can access the data modified by an uncommitted transaction.
- This ensures that if a transaction aborts, no other transaction has to abort as a result of dependency on the aborted transaction.

Deadlocks¶

Either 2PL or strict 2PL may lead to a deadlock involving a sequence of transactions \((T_1, \dots, T_n)\) where \(T_i\) must wait for \(T_{i+1}\) to release locks, \(1 \leq i < n\), and where \(T_n\) must wait for \(T_1\) to release locks.

There are two general ways to resolve deadlocking:

deadlock prevention
- locks granted only if they can’t lead to a deadlock
- all objects are ordered, and locks granted in this order
deadlock detection
- use wait for graphs and cycle detection
- resolution: the system aborts one of the offending transactions; called an involuntary abort

In practice, some schedulers detect a lock request timeout instead of a deadlock and resolve by aborting.

Inserts and Deletes¶

We have been assuming a database consists of a fixed set of physical objects.

Consider where DML processing requires creating or deleting physical objects, such as records in an index.

Neither 2PL nor strict 2PL correctly handles such cases.

This situation is called the phantom tuple problem.

Note

❗

Concept Explanation from ChatGPT:

Problem: Phantom Tuple The phantom tuple problem occurs when a transaction reads a set of records based on a query condition, but another transaction modifies the dataset by adding or deleting rows that match the query condition. This violates isolation and leads to inconsistent results.

Example:

Transaction T1 reads all employees and applies bonuses based on a fixed budget.
Transaction T2 inserts a new employee during T1’s execution.
T1 may incorrectly include the new employee when finalizing the bonus allocation.

Why It Happens:

This inconsistency arises because standard row-level locks in protocols like 2PL or strict 2PL lock only the existing rows, not the range of rows that might qualify based on query conditions.
New rows inserted or deleted by other transactions are not protected by existing locks.

Solution:

Predicate Locks: Lock the range of records matching the query condition to prevent modifications.
Index Locks: Lock relevant parts of an index to prevent new inserts or deletes.
Serializable Isolation Level: Use a stricter isolation level to ensure consistent views of the data (e.g., MVCC or range-based locking mechanisms).

How Row-level Locks Work

When a transaction operates on a row (e.g., reads, updates, or deletes), the database places a lock on that row.
The type of lock determines what other transactions can do:
1. Shared Lock (S-lock): Allows other transactions to read the row but prevents them from modifying it.
2. Exclusive Lock (X-lock): Prevents any other transaction from reading or modifying the row.

Resolution: DML requests that modify the database according to the results of a query need larger-scale locks, such as:

locks on entire indices, or}
predicate locks on tables

together with appropriate lock compatibility rules.

Note

❗

Concept Explanation from ChatGPT:

To prevent the phantom tuple problem, larger-scale locks must be used:

Locks on Entire Indices:
- Instead of locking individual rows, lock the entire index used for range queries.
- For example, if T₁ queries salary > 5000, it locks the entire range of the salary index to prevent insertions within this range.
Predicate Locks:
- Lock query conditions instead of specific rows or indices.
- For example, a predicate lock might lock all potential rows that satisfy salary > 5000, including those that do not yet exist.
Appropriate Lock Compatibility Rules:
- Ensure that locks on indices or predicates are applied and managed correctly to maintain consistency and avoid unnecessary blocking.

The difference between predicate locks and locks on entire indices lies in how they handle locking and their granularity. Let me clarify both concepts:

1. Predicate Locks

What It Does:
- A predicate lock locks all current rows that satisfy a given condition (e.g., salary > 5000) and also potential future rows that could satisfy this condition if they were inserted or updated.
- This is a logical lock based on the query condition itself rather than physical structures like indices or existing rows.
How It Works:
- A transaction holding a predicate lock on salary > 5000 prevents any other transaction from:
  - Inserting a new row where salary > 5000.
  - Updating a row to make salary > 5000 if it did not previously meet the condition.
Why It's Special:
- Predicate locks conceptually lock the query condition rather than a physical structure.
- For example, even if there are no rows with salary > 5000 at the time of the query, the lock ensures no other transaction can insert or modify rows to meet this condition while the lock is held.

2. Locks on Entire Indices

What It Does:
- Locks an entire index related to the query, preventing any changes to rows covered by that index during the transaction.
- If salary > 5000 is part of an index, locking the index prevents:
  - Any insertions of rows into this range.
  - Any updates to rows already in the range.
How It Works:
- It is a physical lock on the index structure itself (e.g., a B-Tree index on salary).
- Prevents insertions, deletions, or updates within the index range while the lock is active.

Key Differences

Aspect	Predicate Locks	Locks on Entire Indices
Scope	Logical lock based on a condition (`salary > 5000`).	Physical lock on an index structure (e.g., B-Tree).
Covers Future Rows	Yes, includes rows that might be added or updated to meet the condition.	Yes, but only because the index range is locked.
Granularity	More flexible: locks only rows satisfying the condition, no matter where they exist.	Coarser: locks the entire index range even if some rows do not meet the condition.
Applicability	Can work even if there is no index on the queried field.	Requires an index on the queried field for effectiveness.
Performance	Higher conceptual overhead; more difficult to implement efficiently.	Easier to implement with existing indexing mechanisms.

Example

Predicate Lock Example:
- Query: SELECT * FROM Employees WHERE salary > 5000.
- If a predicate lock is used:
  - Prevents inserting a new row with salary = 6000 even if no index exists.
  - Prevents updating an existing row with salary = 4000 to salary = 5500.
Index Lock Example:
- Query: SELECT * FROM Employees WHERE salary > 5000.
- If the index on salary is locked:
  - Prevents modifications to the indexed range that overlaps with salary > 5000.
  - The physical range of the index controls locking behavior.

Summary

Predicate locks are logical locks tied to the query condition, protecting even potential changes to rows satisfying that condition, regardless of the presence of an index.
Locks on entire indices are physical locks on the index structure, preventing changes to rows within the indexed range.

Predicate locks are more flexible but harder to implement and less common in practice, while index locks are simpler and rely on existing index mechanisms.

Isolation Levels in SQL¶

Scheduling with only conflict serializable schedules may lead to performance issues due to blocked transactions and deadlocks. SQL provides four isolation levels to balance concurrency and consistency:

Level 3: Serializable
- Achieves strict serializability using table-level locks with strict 2PL.
- Most restrictive but ensures no anomalies.
Level 2: Repeatable Read
- Uses tuple-level locks with strict 2PL.
- Prevents most anomalies but allows phantom tuples.
Level 1: Cursor Stability
- Applies exclusive tuple locks during access.
- May result in different results for the same query executed twice within a transaction.
Level 0: Read Uncommitted (Dirty Read)
- No locking applied.
- Transactions may read uncommitted updates, leading to dirty reads.
- Only allowable for read-only queries

Key Points:

Higher isolation levels (e.g., Level 3) ensure better consistency but can reduce transaction throughput.
Lower isolation levels improve performance but allow anomalies like dirty reads or phantom tuples.

Note

❗

Concept Explanation from ChatGPT:

Comparison of Isolation Levels

Isolation Level	Dirty Reads	Non-repeatable Reads	Phantom Reads	Concurrency	Consistency
Serializable	Prevented	Prevented	Prevented	Lowest	Highest
Repeatable Read	Prevented	Prevented	Allowed	Medium	High
Read Committed	Prevented	Allowed	Allowed	High	Medium
Read Uncommitted	Allowed	Allowed	Allowed	Highest	Lowest

Summary

The choice of isolation level depends on the trade-off between consistency requirements and performance goals:

Use Serializable for maximum consistency but expect poor concurrency.
Use Repeatable Read to prevent most anomalies except phantom tuples.
Use Read Committed for a balance of consistency and concurrency.
Use Read Uncommitted for maximum concurrency in scenarios where occasional inconsistencies are acceptable.

Failure Recovery¶

The DBMS recovery module must satisfy two key requirements:

Atomicity:
- Ensure each transaction is either:
  - Committed: Database changes are permanent.
  - Aborted: No database changes are made.
Reliability:
- Enable recovery of the database to a consistent state in case of hardware or software failure.

Interaction with Recovery Management:

Input: A 2PL and ACA schedule of operations produced by the transaction manager.
Output: A schedule of:
- Object reads,
- Object writes,
- Object forced writes.

Approaches to Recovery¶

Two main approaches to database recovery:

Shadowing:
- Implements copy-on-write and merge-on-commit strategies.
- Results in poor clustering, leading to inefficient data access.
- Historically used in System R, but not in modern systems due to inefficiencies.
Logging:
- Utilizes log files stored on separate, stable media.
- Provides efficient buffer utilization and better resource management.
- Ensures original data clusters are preserved, improving performance.

Logging Approaches to Recovery¶

A log is a read/append-only data structure stored on stable media that supports recovery processes:

The recovery manager appends transaction log records.
Logs are read during transaction abortion or failure recovery.

Types of Information in Log Records:

UNDO Information:
- Stores old versions of objects modified by a transaction.
- Used to undo changes made by transactions that abort.
REDO Information:
- Records new versions of objects modified by a transaction.
- Used to redo changes made by transactions that commit.
BEGIN/COMMIT/ABORT Information:
- Records transaction lifecycle events:
  - BEGIN: Transaction start.
  - COMMIT: Transaction successfully completes.
  - ABORT: Transaction is rolled back.

Note

❗

Concept Explanation from ChatGPT:

How to abort a transaction using a log:

To abort a transaction, the system performs the following steps using the log:
- Identify the transaction to abort: Check the log to find all the operations performed by the transaction.
- Undo operations: For each action recorded in the log (starting from the most recent entry and working backward), apply the corresponding UNDO operation. This restores the previous state of the data item as recorded in the log.
- Record the abort: Add a log entry indicating the transaction has been aborted (e.g., T2, ABORT).
Example:

For transaction T2 (already aborted in the log):
- From the log, T2 performed operations on x3.
- The UNDO operation (x3 = 51) restores the state of x3 to its value before T2 modified it.

How to recover from a failure using a log (assuming active transactions should be aborted):

After a system failure, recovery is performed in two steps using the log:
- Redo committed transactions:
  1. Identify transactions marked as committed in the log (T1 and T3 in this case).
  2. Reapply all REDO operations for committed transactions in the order they appear in the log. This ensures the database reflects all committed changes.
- Undo active transactions:
  1. Identify transactions that were active at the time of failure (T0 and T4).
  2. For each active transaction, perform UNDO operations in reverse order of their log entries. This rolls back all incomplete changes made by the active transactions.
  3. Add an abort entry to the log for these transactions (e.g., T0, ABORT and T4, ABORT).
Example for recovery:
- Redo operations for committed transactions T1 and T3:
  - Apply T1's REDO on x2 and x4.
  - Apply T3's REDO on x2.
- Undo operations for active transactions T0 and T4:
  - For T0, reverse its REDO and apply its UNDO (e.g., restore x1 to 99).
  - For T4, reverse its REDO and apply its UNDO (e.g., restore x4 to 10).

Write-Ahead Logging (WAL)¶

Updating indices on stable storage before recording a log can cause inconsistency. The Write-Ahead Logging (WAL) protocol ensures consistency by enforcing two rules:

Undo Rule:
- A log record for an update must be written to the log file before the corresponding data page is updated in stable storage.
- Guarantees: Atomicity.
Redo Rule:
- All log records for a transaction must be written to the log file before acknowledging a commit to the client.
- Guarantees: Durability.

Note

❗

Concept Explanation from ChatGPT:

1. Undo Rule:

What it means:

Before a change is written to the database (stable storage), the corresponding log entry describing how to undo that change must be written to the log file.
Why it matters:

If the system crashes after a change is written to the database but before the transaction completes, the undo information in the log ensures the system can roll back the change and restore the database to its previous consistent state.
Guarantee:

This rule ensures atomicity: either all changes of a transaction are applied, or none of them are.

2. Redo Rule:

What it means:

All log entries describing the changes made by a transaction must be written to the log before the transaction is marked as committed.
Why it matters:

If the system crashes after the transaction commits but before all changes are written to the database, the redo information in the log ensures that the system can reapply those changes during recovery to maintain consistency.
Guarantee:

This rule ensures durability: once a transaction commits, its changes are permanent, even if a failure occurs.

Summary

The undo rule guarantees that the database can be rolled back to its previous state if a transaction fails (atomicity).
The redo rule guarantees that committed changes are not lost in the event of a crash (durability).
- Even if a transaction is committed, the changes made by the transaction might not have been written to the stable storage (disk) yet at the time of a crash. When a transaction modifies the database, the changes are often made to in-memory buffers first for better performance. Writing data from memory to stable storage (e.g., disk) is a slow process, so databases may delay writing changes until later. If the system crashes before these changes are flushed to disk, the in-memory changes are lost.

In Write-Ahead Logging (WAL), every REDO operation must be accompanied by a preceding UNDO operation in the log. This ensures the database can handle both rollback (undoing changes) and recovery (redoing changes) correctly.

Note

❗

Concept Explanation from ChatGPT:

Here’s a simple example of how Write-Ahead Logging (WAL) works in a transaction processing scenario:

Example Scenario:

Initial Database State:
- Data item A = 100.
- Data item B = 200.
Transaction T1:
- T1 performs the following operations:
  1. Reads A = 100.
  2. Writes A = 150.
  3. Writes B = 250.
Steps with WAL:

Step 1: Perform an Update
- Action: T1 changes A from 100 to 150.
- Log Entry: Before the update is applied to the database, an UNDO log record is written:
```
T1, UNDO, A, 100
```
- Data Change in Memory: The value of A in the database (buffer) is now updated to 150 but not yet written to disk.
Step 2: Perform Another Update
- Action: T1 changes B from 200 to 250.
- Log Entry: Again, before the update is applied, an UNDO log record is written:
```
T1, UNDO, B, 200
```
- Data Change in Memory: The value of B in the database (buffer) is now updated to 250 but not yet written to disk.
Step 3: Commit the Transaction
- Action: T1 commits.
- 1. Before acknowledging the commit, all REDO log entries are written:
```
T1, REDO, A, 150
T1, REDO, B, 250
```
  Log Entries:
  1. The log now contains:
```
T1, UNDO, A, 100
T1, UNDO, B, 200
T1, REDO, A, 150
T1, REDO, B, 250
T1, COMMIT
```
- Disk State: The log is flushed to disk before the commit is acknowledged.

What Happens During a Crash:

Case 1: Crash Before Commit
- Problem: T1’s changes to A (150) and B (250) are in memory only; they were not written to disk.
- - Use the UNDO log entries to roll back changes:
```
UNDO A = 100
UNDO B = 200
```
  Solution Using WAL:
  - Result: The database is restored to its original state (A = 100, B = 200).
Case 2: Crash After Commit but Before Data Is Flushed
- Problem: The transaction is marked as committed, but the changes to A and B are still in memory, not on disk.
- - Use the REDO log entries to reapply the committed changes:
```
REDO A = 150
REDO B = 250
```
  Solution Using WAL:
  - Result: The database reflects the committed state (A = 150, B = 250).

Key Takeaways:

The UNDO rule ensures that changes can be reversed if the transaction is not committed.
The REDO rule ensures that committed changes can be reapplied if a crash occurs before they are written to the database.
WAL guarantees atomicity (all-or-nothing execution) and durability (committed changes are permanent).

Note

❗

Concept Explanation from ChatGPT:

When a system failure occurs, the database uses the log to recover and ensure consistency and durability, following the Write-Ahead Logging (WAL) protocol. Recovery involves two main phases: redo (to ensure committed changes are applied) and undo (to roll back uncommitted changes). Here's the order and rules for processing:

Steps in Recovery:

Analyze Phase:
- Identify all committed, uncommitted (active), and aborted transactions by scanning the log.
- Build information about dirty pages and transaction states to determine the work needed for recovery.
Redo Phase:
- Purpose: Reapply all operations of committed transactions to ensure durability.
- Order: Process the log from oldest to newest (forward).
- Rule: Redo changes for all transactions that were committed before the crash. Ignore changes from uncommitted or aborted transactions.
Undo Phase:
- Purpose: Roll back operations of uncommitted (active) transactions to ensure atomicity.
- Order: Process the log from newest to oldest (backward).
- Rule: Undo changes made by all uncommitted (active) transactions by reversing their operations. Use the compensation log record (CLR) mechanism to record undo actions in the log.

Summary of Transaction Handling:

Transaction State	Action	Reason
Committed	Redo	Ensure all changes are persisted in the database.
Uncommitted (Active)	Undo	Roll back incomplete changes for atomicity.
Aborted	Undo (if needed)	Roll back incomplete operations.

Order:

Redo: Old to New (to ensure all committed changes are applied).
Undo: New to Old (to reverse incomplete changes safely).

Summary¶

The ACID properties ensure the correctness of concurrent access to databases and data storage:

Consistency and Isolation:
- Based on serializability, which:
  1. Defines correct schedulers.
  2. Is managed by the transaction manager.
Durability and Atomicity:
- Ensured by the recovery manager.
Efficiency:
- Synchronous writing is inefficient and replaced by Write-Ahead Logging (WAL), which writes logs efficiently while maintaining consistency.