Data Base Management System (IT-405) - Unit 4 Short Notes

UNIT 4: CONCURRENCY CONTROL

1. Need for Concurrency Control

• Definition: Mechanism to manage simultaneous transactions accessing shared data to maintain consistency and isolation.

• Problems without Concurrency Control:

  • Lost Update: Two transactions read same value, update based on it, and one update is lost.

  • Dirty Read: Transaction reads data written by an uncommitted (dirty) transaction.

  • Unrepeatable Read: Transaction reads same data twice and gets different values because another transaction modified it.

  • Phantom Read: Transaction re-executes a query returning a set of rows and finds new rows (phantoms) inserted by another transaction.

• Impact on Performance: Concurrency control introduces overhead (locking, validation, etc.) but is essential for data integrity in multi-user systems. The goal is to maximize concurrency while ensuring correctness.

[!TIP] Exam Focus: Be prepared to illustrate each anomaly (lost update, dirty read, etc.) with a simple schedule example (e.g., two transactions T1 and T2 on account balance).

2. Locking Techniques

Basic Lock Modes:

Two-Phase Locking (2PL) Protocol:

• Definition: A transaction requests locks in two distinct phases:

  1. Growing Phase: Transaction acquires locks (no release).

  2. Shrinking Phase: Transaction releases locks (no new acquisition).

• Guarantee: Conflict-serializable schedule.

• Variants:

  • Basic 2PL: Locks released after final operation.

  • Rigorous 2PL (Strict 2PL): All locks (S & X) held until COMMIT/ABORT. Ensures cascadeless and strict schedules.

  • Conservative 2PL (Static): Transaction acquires all required locks before starting. Prevents deadlock but reduces concurrency.

Lock Conversion & Lock Manager:

• Lock Conversion: Upgrading S-lock to X-lock (or downgrading X to S) during a transaction's lifetime.

• Lock Manager: System component that grants/denies lock requests, maintains a lock table (data item -> list of granted/requested locks).

[!TIP] Common Pitfall: 2PL guarantees conflict serializability but NOT cascadelessness unless it's Strict 2PL.

3. Timestamp Ordering (T/O)

• Principle: Each transaction Ti gets a unique timestamp TS(Ti) (e.g., system clock value). Scheduler orders operations based on timestamps to avoid conflicts.

• Timestamp Types per Data Item Q:

  • WTS(Q): Timestamp of last write(Q).

  • RTS(Q): Timestamp of last read(Q).

• Algorithm Rules (for read(Q) / write(Q) by Ti):

  • Read: If TS(Ti) < WTS(Q), reject (Ti too old, read invalid) → rollback Ti. Else, allow read and set RTS(Q) = max(RTS(Q), TS(Ti)).

  • Write: If TS(Ti) < RTS(Q) or TS(Ti) < WTS(Q), reject (Ti too old, write obsolete) → rollback Ti. Else, perform write and set WTS(Q) = TS(Ti).

• Schedule Example:

  
  T1(TS=10): R(A), W(A)
  
  T2(TS=20): R(A), W(A)
  
  

  • T1's W(A) succeeds (TS=10 > RTS/WTS=0 initially).

  • T2's R(A) succeeds (TS=20 > WTS=10).

  • T2's W(A) succeeds (TS=20 > RTS=20, WTS=10).

  • Result: T1 → T2 (conflict-serializable order).

[!TIP] Key Point: T/O can cause cascading rollbacks (unlike Strict 2PL) because it may abort older transactions reading newer data.

4. Optimistic Concurrency Control (Validation-Based)

• Assumption: Conflicts are rare; transactions execute without locking.

• Three Phases:

  1. Read Phase: Transaction reads/writes to private workspace (no locks on DB).

  2. Validation Phase: Transaction Ti requests validation. Check if its read set conflicts with writes of committed transactions that finished after Ti started.

     • Serializability Test: If Ti's read set intersects with write set of any Tj where TS(Ti) < finish(Tj) < TS(Ti), then conflict → abort Ti.

  3. Write Phase: If validated, apply private writes to DB atomically.

• When to Use: Low conflict environments (read-heavy workloads).

5. Deadlock

Definition: A set of transactions is in deadlock if each transaction waits for a resource held by another in the set, forming a cycle in the wait-for graph.

Deadlock Handling Strategies:

Wait-For Graph (WFG): Nodes = transactions. Edge Ti → Tj if Ti waits for a lock held by Tj. Cycle = Deadlock.

[!TIP] Exam Alert: Be ready to draw WFG for a given schedule and identify deadlock. Know victim selection criteria (e.g., rollback transaction with least elapsed time).

6. Multiple Granularity Locking (MGL)

• Purpose: Allow locking at different levels (database, table, page, row) to reduce lock overhead.

• Locking Hierarchy: Database > Table > Page > Row (coarse to fine).

• Intention Locks: Indicate a transaction intends to acquire locks at a lower level.

  • IS (Intention Shared): Will request S-lock on some lower node.

  • IX (Intention Exclusive): Will request X-lock on some lower node.

  • SIX (Shared & Intention Exclusive): Has S-lock on this node, will request X-lock on some lower node.

• Compatibility Matrix: Intention locks are compatible with each other and with S-locks at higher levels, but not with X-locks.

• Protocol: To lock a node in S/X, its parent must be locked in IS/IX/SIX appropriately.

Example: To lock a row in X-mode:

1. Lock its table in IX.

2. Lock its page in IX.

3. Lock the row in X.

[!TIP] Key Benefit: MGL allows a transaction to lock an entire table (e.g., for a report) while others lock individual rows, improving concurrency.

\boxed{\text{Core Goal of Concurrency Control: Ensure schedules are Conflict-Serializable while maximizing concurrency.}}