# Concurrency Control

This is concurrency in terms of databases? Learned in CS348.

Assumptions

We consider a database to be a finite set of independent physical objects $x_{j}$ that are read and written by transactions $T_{i}$ , and write:

- $r_{i}[x_{j}]$ to say that transaction $T_{i}$
readsobject $x_{j}$ , and- $w_{i}[x_{j}]$ to say that transaction $T_{i}$
writes(modifies) object $x_{j}$.

Transaction

A Transaction $T_{i}$ is a sequence of read and write operations on a database $T_{i}=r_{i}[x_{1}],r_{i}[x_{2}],w_{i}[x_{1}],…,r_{i}[x_{4}],w_{i}[x_{2}],c_{i}$

where $c_{i}$ is the commit request of $T_{i}$

Schedule

For a set of transactions ${T_{1},...,T_{k}}$, we want to produce an execution order of operations $S$, called a schedule, such that

- every operation $o_{i}∈T_{i}$ appears also in $S$, and
- $T_{i}$ ’s operations in S are ordered the same way as in $T_{i}$.

**Goal**: Produce a correct schedule with maximal parallelism.

If $T_{i}$ and $T_{j}$ are concurrent transactions, then it is always correct to schedule the operations in such a way that:

- $T_{i}$ will appear to precede $T_{j}$ meaning that $T_{j}$ will “see” all updates made by $T_{i}$ , and $T_{i}$ will not see any updates made by $T_{j}$ , or
- $T_{i}$ will appear to follow $T_{j}$ , meaning that $T_{i}$ will see $T_{j}$ ’s updates and $T_{j}$ will not see $T_{i}$ ’s.

Idea

Define a schedule $S$ to be correct if it appears to clients that the transactions are executed sequentially, that is, in some strictly serial order.

Serializable Schedule

A schedule $S$ is said to be

serializableif it isequivalentto some serial execution of the same transactions.

Serializable Schedules Examples: An interleaved execution of two transactions: $S_{a}=w_{1}[x],r_{2}[x],w_{1}[y],c_{1},r_{2}[y],c_{2}$

An equivalent serial execution ($T_{1},T_{2}$): $S_{b}=w_{1}[x],w_{1}[y],c_{1},r_{2}[x],r_{2}[y],c$

An interleaved execution with no equivalent serial execution: $S_{c}=w_{1}[x],r_{2}[x],r_{2}[y],c_{2},w_{1}[y],c_{1}$

Theorem

A schedule $S$ is serializable if and only if the Serialization Graph $SG$ for $S$ is acyclic.

Serializability guarantees correctness. But we’d like to avoid other undesirable situations:

Conflict Serializable

A schedule $S_{1}$ is conflict serializable if it is conflict equivalent to some serial schedule $S_{2}$, i.e. like $T_{1},T_{2}$.

Conflict Serializable is a GOOD thing