Concurrency

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:

1. $r_i[x_j]$ to say that transaction $T_i$ reads object $x_j$ , and
2. $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],\dots ,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

1. every operation $o_i\in T_i$ appears also in $S$, and
2. $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 serializable if it is equivalent to 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

• https://www.geeksforgeeks.org/conflict-serializability-in-dbms/

Related

• Two Phase Locking
• Deadlock