Database Systems Chapter 21 Quiz

Fundamentals of Database Systems - Chapter 21: Concurrency Control Techniques

• Concurrency control protocols are sets of rules to guarantee serializability during concurrent access.
• Two-phase locking protocols manage concurrent access by locking data items.
• Timestamps provide unique identifiers for each transaction.

21.1 Two-Phase Locking Techniques

• A lock is a variable associated with a data item.
• It describes the status of the data item for the operations performed.
• Binary locks use two states (values): locked (1) and unlocked (0).
• A locked item cannot be accessed.
• Unlock operations allow accessing items.

Two-Phase Locking Techniques (cont'd.)

• Transactions request access by issuing lock_item(X) operations.
• If a lock is available, the item is locked.
• If the lock is unavailable, the transaction waits.
• unlock_item(X) releases a lock.
• A lock table specifies which database items have locks.
• The lock manager subsystem manages locks.

Two-Phase Locking Techniques (cont'd.)

• Shared/exclusive (read/write) locks allow reading simultaneously without conflicts.
• Exclusive locks are needed for writing.
• The operations are read_lock(X), write_lock(X), and unlock(X).
• For read_lock(X): if the lock is unlocked, set it to read-locked, otherwise, increment the read count.
• For write_lock(X): if the lock is unlocked, set it to write-locked; otherwise, wait until unlocked.

Two-Phase Locking Techniques (cont'd.)

• Transactions can convert locks from one state to another.
• Upgrading converts read to write.
• Downgrading converts write to read.

Guaranteeing Serializability by Two-Phase Locking

• Two-phase locking protocol ensures all locking operations precede the first unlock operation in each transaction.
• It consists of expanding (growing) and shrinking phases.
• Expanding phase: acquiring new locks, allowing lock conversions, and no lock releases.
• Shrinking phase: releasing existing locks, and allowing downgrades.

Variations of Two-Phase Locking

• Basic 2PL: described in previous slides.
• Conservative 2PL: requires predeclaring all accessed items by a transaction before it starts.
• Strict 2PL: exclusive locks are released only after the transaction commits or aborts.
• Rigorous 2PL: no lock release until the transaction commits or aborts.

Dealing with Deadlock and Starvation

• Deadlock occurs when two or more transactions are waiting indefinitely for each other to release locks.
• Deadlock prevention protocols require transactions to lock all required resources in advance, or to order resource requests.
• Deadlock detection algorithms check for deadlock states and resolve them.
• Starvation occurs if a transaction waits indefinitely, while other transactions get processed.
• Timeouts and victim selection resolve starvation.

21.2 Concurrency Control Based on Timestamp Ordering

• Timestamps are unique identifiers for transactions, assigned in the order they are submitted.
• Timestamp ordering avoids using locks.
• Deadlocks are not possible.

Timestamp Ordering (cont'd.)

• Generating timestamps: the DBMS assigns timestamps to transactions based on the order of their submission.
• Timestamp ordering enforces equivalent serial order based on transaction timestamps.
• Each database item has read_TS(X) and write_TS(X) timestamps.

Timestamp Ordering (cont'd.)

• Basic TO algorithm: if a conflict arises, the later operation is rejected.
• Strict TO algorithm ensures schedules are both strict and conflict serializable.