Skip to content

Concurrency Control

Introduction

Definition

  • A schedule is said to be Serial if it executes actions within a transaction in a serial order meaning that there is no interchanging operations from different transactions.
  • A schedule is said to be Serializable if there is a reordering of this schedule that produce consistent output regardless of the input.
  • A schedule is said to be Conflict-Serializable if it can be serialized through swapping non-conflicting actions.

Note: Conflict-Serializable schedules belong to be a subset of Serializable schedules.

Precedence Graph Algorithm

Precedence graph can be used to check whether a schedule is conflict serializable.

Lock

Definition and Notation

Lock vs Latch

Lock under this context is not the same as locks mentioned in operating systems class. Instead, Latch is equivalent to lock mentioned in OS classes. Lock referrs to the overall protection mechanism for individual table elements.

Note: This definition is given in CMU's database system course

Notation

\(sl_{i}(X)\): Transaction Ti requests a read lock on element X
\(xl_{i}(X)\): Transaction Ti requests a write lock on element X
\(ul_{i}(X)\): Transaction Ti requests an update lock on element X
\(il_{i}(X)\): Transaction To requests an increment lock on element X
\(u_{i}(X)\): Transaction Ti releases the lock it held on element X

Conditions

  • Two Phase Lock: In every transaction, all lock actions precede all unlock actions

If this condition is satisfied, then conflict serializable

Two Phase Lock

Two phase lock works because there is at least one conflict serializable order which is the order that transactions are first unlocked1

Variations of Two Phase Lock

  1. Strict 2PL: locks are only released after

Timestamp

  1. The complete database book, chapter 18.3 page 901. ↩

Back to top