Skip to content
CampusPrep
ME-606 · RDBMS Lab/Quick Revision Short Notes

RDBMS Lab (ME-606) - Unit 3 Short Notes

UNIT 3: TRANSACTION MANAGEMENT, CONCURRENCY CONTROL & RECOVERY

3.0 Introduction to Transactions & System Failures

  • Transaction: A logical unit of work (LUW) that accesses and possibly updates a database. It must be treated as a single, indivisible entity.

  • ACID Properties:

    • Atomicity: Transaction executes all or nothing. Either all its operations are reflected in the database or none are.

    • Consistency: Transaction must preserve database consistency. It transforms the database from one valid state to another, respecting all integrity constraints.

    • Isolation: Concurrent transactions are executed as if serially. Intermediate states of one transaction are not visible to others.

    • Durability: Once a transaction commits, its effects persist permanently, even in the event of a system crash.

  • Transaction States:

    Active → Partially Committed → Committed / Failed → Aborted → Terminated.

  • Types of Failures:

    • System Crash: Power failure, OS crash.

    • Transaction Failure: Logical error, integrity constraint violation, deadlock.

    • Media Failure: Disk crash, corruption.

  • Need for: Concurrency Control (to maintain Isolation) and Recovery (to maintain Atomicity & Durability).

[!TIP] Exam Focus: Be prepared to define ACID with a one-line example for each. Know the state transition diagram.

3.1 Transaction Scheduling & Serializability

  • Schedule (History): A sequence of operations from a set of transactions. The order of operations from different transactions determines the schedule's concurrency.

  • Serial Schedule: Operations of each transaction are executed consecutively. No interleaving. Always correct (preserves consistency) but inefficient.

  • Concurrent Schedule: Operations from multiple transactions are interleaved. Can lead to anomalies if not controlled.

  • Problems in Concurrent Execution:

    • Lost Update: T1 reads X, T2 reads X, T1 writes X, T2 writes X → T1's update lost.

    • Dirty Read: T1 modifies X, T2 reads X (uncommitted), T1 aborts → T2 reads invalid data.

    • Unrepeatable Read: T1 reads X, T2 modifies & commits X, T1 reads X again → gets different value.

    • Phantom Read: T1 reads set S (e.g., SELECT * FROM Emp WHERE salary>5000), T2 inserts new row satisfying condition & commits, T1 reads set S again → new row appears.

  • Conflict Serializability:

    • Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write.

    • Conflict-Equivalent: If one schedule can be transformed into another by swapping non-conflicting operations.

    • Conflict-Serializable: A schedule is conflict-serializable if it is conflict-equivalent to some serial schedule.

    • Testing via Precedence Graph (Serializability Graph):

      • Nodes: Transactions.

      • Edges: Ti → Tj if an operation of Ti conflicts with and appears before an operation of Tj in the schedule.

      • Result: Schedule is conflict-serializable iff the precedence graph is acyclic.

      • Serial Order: Any topological sort of the acyclic graph gives an equivalent serial schedule.

      

      DiagramCANVAS: Draw nodes T1, T2, T3. Show edges like T1->T2 (on X), T2->T3 (on Y). Indicate cycle means NOT serializable.

  • View Serializability:

    • View-Equivalent: Schedules produce the same initial read values, same final write values, and same read-from relationships.

    • View-Serializable: Schedule is view-equivalent to some serial schedule.

    • Intuition: Focuses on the logical outcome (what values are read/written), not the exact conflict order. Harder to test algorithmically (NP-complete).

[!TIP] Common Pitfall: Confusing Conflict (based on operation order) with View (based on read/write relationships). Exams often ask to draw a precedence graph and determine serializability.

3.2 Concurrency Control - Lock-Based Protocols

  • Lock Modes:

    | Lock Mode | Purpose | Compatible With | | :--- | :--- | :--- | | Shared (S) | Read lock | S | | Exclusive (X) | Read/Write lock | None |

  • Two-Phase Locking (2PL) Protocol:

    • Growing Phase: Transaction acquires locks (cannot release any).

    • Shrinking Phase: Transaction releases locks (cannot acquire new ones).

    • Guarantee: Conflict-serializable schedules.

    • Drawback: Does not guarantee recoverability or cascadelessness.

  • Strict 2PL (Strong Strict 2PL):

    • Transaction holds all exclusive (X) locks until it commits or aborts.

    • Guarantees: Recoverable and cascadeless schedules. Most widely used in practice.

  • Cascadeless Schedule: For any pair Ti → Tj (Ti reads data written by Tj), Tj must commit before Ti reads that data. Prevents cascading aborts.

  • Locking Granularity: Can lock at Database, Table, Page, Row/Tuple, Field level. Trade-off: Coarse-grained (less overhead, more contention) vs. Fine-grained (more overhead, less contention).

  • Lock Table: Central data structure storing:

    (Data-item, Lock-mode, List-of-locked-transactions, Pointer-to-next-lock-on-same-item).

    Managed by the concurrency control manager.

  • Deadlocks:

    • Definition: A set of transactions are mutually waiting for each other to release locks → permanent blocking.

    • Necessary Conditions (Coffman Conditions):

      1. Mutual Exclusion: Locks are non-shareable (X-mode).

      2. Hold & Wait: Transaction holds a lock while waiting for another.

      3. No Preemption: Locks cannot be forcibly taken.

      4. Circular Wait: A circular chain of transactions exists, each waiting for the next.

    • Deadlock Handling:

      • Prevention: Design protocol to eliminate one Coffman condition.

        • Wait-Die: Older transaction (TS) waits for younger (TY). Younger dies if requests lock held by older. (TY waits for TS → TY dies).

        • Wound-Wait: Older transaction (TS) wounds (forces abort) younger (TY) if it holds the lock. Younger waits if requests lock held by older. (TY holds lock → TS wounds TY).

      • Detection & Resolution: Allow deadlocks, then break them.

        • Wait-For Graph (WFG): Nodes = transactions. Edge Ti → Tj if Ti is waiting for a lock held by Tj.

        • Detection: Periodically check WFG for cycles.

        • Resolution: Victim selection (e.g., youngest, least progress) → Rollback victim transaction.

      • Avoidance: (Less common) Requires knowledge of future lock requests (e.g., using timestamps like in wound-wait is often classified as prevention).

[!TIP] Exam Favorite: Compare Wait-Die vs. Wound-Wait. Both use timestamps, but one waits and one wounds. Know that Strict 2PL is needed for recoverability alongside serializability.

3.3 Concurrency Control - Non-Lock Based & Multi-Version Protocols

  • Timestamp Ordering (TO) Protocol:

    • Each transaction Ti gets a unique timestamp TS(Ti) when it starts.

    • Each data item X has two timestamps: ReadTS(X) (largest TS of any transaction that read X), WriteTS(X) (largest TS of any transaction that wrote X).

    • Rules:

      • Read: If TS(Ti) < WriteTS(X), reject (too old). Else, read & set ReadTS(X) = max(ReadTS(X), TS(Ti)).

      • Write: If TS(Ti) < ReadTS(X) or TS(Ti) < WriteTS(X), reject (too old). Else, write & set WriteTS(X) = TS(Ti).

    • Thomas's Write Rule (Optimization): If TS(Ti) < WriteTS(X) on a write, ignore the write (it's an outdated overwrite) instead of rejecting. Allows more schedules.

    • Guarantee: Conflict-serializable (order by timestamps). No deadlocks (no waiting).

    • Drawback: Starvation possible for long-running old transactions.

  • Multi-Version Concurrency Control (MVCC):

    • Core Idea: Maintain multiple versions (<value, TS_written>) of each data item. Readers don't block writers, writers don't block readers.

    • Snapshot Isolation (SI): Common MVCC implementation.

      • Transaction Ti sees a snapshot of the database as of its start time.

      • It reads from versions where TS_written <= TS(Ti) and the version is not overwritten by a committed transaction with TS > TS(Ti) before Ti's commit.

      • Write Validation at Commit: Ti can commit only if no other transaction has written a new version of any item Ti has written since Ti's snapshot. If conflict, Ti aborts.

    • Advantages: Excellent for read-heavy workloads. No reader-writer blocking. Provides snapshot consistency.

    • Anomalies: Can allow write-skew (two transactions read same snapshot, write disjoint items, both commit, violating invariant).

[!TIP] Key Difference: Timestamp Ordering orders all operations by TS and may reject. MVCC (SI) allows readers to see old versions and validates writes only at commit.

3.4 Recovery Systems - Log-Based Recovery

  • Recovery Manager & Log:

    • Log: Sequential, write-only file of log records.

    • Log Record Types:

      • <T, start>

      • <T, X, old_value, new_value> (Update log - physical or logical)

      • <T, commit>

      • <T, abort>

    • Write-Ahead Logging (WAL) Protocol: CRITICAL RULE. Before a modified page is written to disk (by buffer manager), the corresponding log record must be flushed to stable storage.

$$\boxed{\text{Log write before data write}}$$

  • Buffer Management Policies:

    • Steal: Buffer pool may write a dirty page (with uncommitted changes) to disk. → Requires Undo on crash.

    • No-Force: A page need not be written to disk upon transaction commit. → Requires Redo on crash.

    • Typical System: Steal + No-Force. Needs both Undo and Redo.

  • Recovery from System Crash (using ARIES-like simple approach):

    1. Analysis Phase: Scan log backwards from last checkpoint to find:

      • Winner (committed) transactions after checkpoint.

      • Loser (uncommitted at crash) transactions.

      • Set of dirty pages in buffer pool at crash.

    2. Redo Phase: Scan log forwards from the earliest recLSN (smallest LSN of a dirty page). For each update log record, reapply the change (new_value) if the page is in the dirty page set or the transaction is a winner. Idempotent (safe to repeat).

    3. Undo Phase: Scan log backwards from end. For each update by a loser transaction, undo the change (old_value). Write compensation log records (CLRs) for undone actions.

  • Checkpoints:

    • Purpose: Reduce recovery time by providing a starting point closer to the crash.

    • Checkpoint Record Contains:

      • List of dirty pages in buffer pool.

      • List of active (uncommitted) transactions.

    • Action: Flush all dirty pages to disk, then write checkpoint log record.

[!TIP] Golden Rule: WAL is non-negotiable. Always remember: Log on stable storage first, then data pages. Recovery phases order: Analysis → Redo → Undo.

3.5 Recovery with Concurrent Transactions & Advanced Topics

  • Recovery with 2PL: Strict 2PL is essential. It ensures that when a transaction Tj reads data written by Ti, Ti must have committed. This prevents cascading aborts and simplifies recovery (only losers need undo).

  • ARIES (Algorithm for Recovery and Isolation Exploiting Semantics): Industry-standard recovery algorithm (used in IBM DB2, SQL Server, etc.).

    • Key Innovations:

      • Repeating History: During redo, reapply all updates (committed and uncommitted) to bring DB to state at crash. Then undo losers. Ensures idempotence.

      • Log Sequence Number (LSN): Unique, monotonically increasing number for each log record.

      • PageLSN: LSN of the last update log record flushed to that page. Used to skip pages during redo.

      • Dirty Page Table (DPT): (PageID, recLSN) where recLSN is LSN of first update to that page since it became dirty. Used to start redo.

    • ARIES Phases:

      1. Analysis: Build DPT and set of loser transactions (Tx). Start from last checkpoint LSN.

      2. Redo: From min(recLSN in DPT), repeat history by reapplying all updates where LSN >= PageLSN.

      3. Undo: For each loser in reverse commit order, walk log backwards undoing its updates. Write CLRs (which have undo_next_LSN pointer) to allow future redo of undo actions if crash occurs during undo.

  • Database Backup & Media Recovery:

    • Backup Types:

      • Full Backup: Entire database.

      • Incremental Backup: Only data changed since last full backup.

      • Differential Backup: Data changed since last full backup.

    • Restore: Restore latest full backup, then apply incremental/differential backups, then apply all log records (archived logs) from after last backup until point of failure (or desired point-in-time).

3.6 Practical Implementation & SQL Support

  • SQL Transaction Statements:

    
BEGIN TRANSACTION; -- or START TRANSACTION

-- SQL operations

SAVEPOINT sp1; -- Create savepoint

-- More operations

ROLLBACK TO sp1; -- Rollback to savepoint

COMMIT; -- Make permanent

ROLLBACK; -- Abort entire transaction

  • SQL Isolation Levels (from weakest to strongest):

    | Level | Dirty Read | Non-Repeatable Read | Phantom Read | Guarantees | | :--- | :---: | :---: | :---: | :--- | | READ UNCOMMITTED | Possible | Possible | Possible | No locks (dirty reads). | | READ COMMITTED | Prevented | Possible | Possible | S-locks released after read. Default in many DBs (e.g., Oracle, PostgreSQL). | | REPEATABLE READ | Prevented | Prevented | Possible | S-locks held until commit (or uses MVCC snapshot). | | SERIALIZABLE | Prevented | Prevented | Prevented | Full serializability (e.g., via predicate locks or strict serializable snapshot). |

    Phantom Prevention: Requires range locks or predicate locking in lock-based systems; MVCC SI may allow phantoms (use SERIALIZABLE SI in PostgreSQL for true serializable).

  • Cursor Usage in Transactions: Cursors are transaction-sensitive. Their position and result set are defined at cursor open time. Under READ COMMITTED, subsequent fetches may see new data if not using FOR UPDATE or holdable cursors.

  • Lab Implementation Focus:

    1. Serializability Testing: Write a program that reads a schedule (list of operations with transaction IDs), builds a precedence graph, and checks for cycles (using DFS).

    2. Lock Simulation: Simulate a lock manager that grants S/X requests, queues waiters, and detects deadlocks by building a Wait-For Graph periodically.

    3. Log & Recovery Simulation: Implement a simple in-memory log. Simulate buffer pool with steal/no-force. On "crash," run analysis/redo/undo phases using the log.

    4. Isolation Level Demo: Use two concurrent SQL sessions to demonstrate:

      • READ UNCOMMITTED: Dirty read (Session 1 updates, Session 2 reads uncommitted, Session 1 rolls back).

      • READ COMMITTED: Non-repeatable read (Session 1 reads, Session 2 updates & commits, Session 1 reads again sees change).

      • REPEATABLE READ: Prevents non-repeatable read but may show phantom (insert new row in range).

      • SERIALIZABLE: Prevents phantoms (second insert in range blocks or aborts).

[!TIP] Practical Exam: You may be asked to write pseudocode for deadlock detection (cycle in WFG) or trace recovery phases on a given log sequence. Always apply WAL rule when analyzing recovery scenarios.

Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in