Database Management Systems Chapter 19

Concurrency Control

• Conflict Serializable Schedules: Two schedules are conflict equivalent if they involve the same actions from the same transactions and maintain the same order for all conflicting actions.
• Conflict Serializable Definition: A schedule is conflict serializable if it is equivalent to some serial schedule.

Example of Non-Conflict Serializable Schedule

• A cycle in the dependency graph illustrates the issue, where the output of Transaction T1 depends on T2 and vice versa.

Dependency Graph

• Definition: Each node represents a transaction; there is an edge from Ti to Tj if Tj reads or writes an object that was last written by Ti.
• Theorem: A schedule is conflict serializable if and only if its dependency graph is acyclic.

Strict Two-Phase Locking (Strict 2PL)

• Protocol Requirements: Obtain S (shared) or X (exclusive) locks on objects before reading or writing.
• Locks are released only after a transaction completes. No other transaction can acquire a lock on an object held with an X lock.
• Constraint: Only schedules where the precedence graph is acyclic are permitted.

Two-Phase Locking (2PL)

• Protocol Mechanics: Tasks follow similar locking rules as Strict 2PL; however, a transaction cannot request additional locks after releasing any.
• Ensures no other transaction can obtain a lock on an object held with an X lock.

View Serializability

• Two schedules are view equivalent if:
  • Transaction Ti reads the initial value of A in both S1 and S2.
  • If Ti reads a value of A written by Tj in S1, Ti reads the same in S2.
  • If Ti writes the final value of A in S1, it writes the final value in S2 as well.

Lock Management

• Lock Manager Responsibilities: Handles requests to lock and unlock objects.
• Lock Table Entry: Keeps track of the number of transactions holding a lock, the type of lock, and points to the queue of lock requests.

Atomic Lock Operations

• Locking and unlocking must occur as atomic operations.
• Lock Upgrade: A transaction with a shared lock can be upgraded to an exclusive lock.

Deadlocks

• Defined as a cycle of transactions waiting for locks from each other.
• Handling Methods:
  • Deadlock Prevention: Avoid deadlocks from occurring.
  • Deadlock Detection: Identify deadlocks after they occur.

Deadlock Prevention Strategies

• Prioritize transactions based on timestamps:
  • Wait-Die Policy: If Ti has higher priority, it waits for Tj; if not, Ti aborts.
  • Wound-Wait Policy: If Ti has higher priority, Tj aborts; otherwise, Ti waits.

Deadlock Detection Methodology

• Construct a waits-for graph:
  • Nodes represent transactions.
  • An edge exists from Ti to Tj if Ti is waiting for Tj to release a lock.
• Regularly check for cycles in the waits-for graph to identify deadlocks.

Test your knowledge on Concurrency Control in Database Management Systems with this quiz focusing on conflict serializable schedules. Explore the concept of conflict equivalence and understand the implications of dependency cycles in transaction schedules. Ideal for students learning about database theories.