Concurrency Control

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


We consider a database to be a finite set of independent physical objects that are read and written by transactions , and write:

  1. to say that transaction reads object , and
  2. to say that transaction writes (modifies) object .


A Transaction is a sequence of read and write operations on a database

where is the commit request of


For a set of transactions , we want to produce an execution order of operations , called a schedule, such that

  1. every operation appears also in , and
  2. ’s operations in S are ordered the same way as in .

Goal: Produce a correct schedule with maximal parallelism.

If and are concurrent transactions, then it is always correct to schedule the operations in such a way that:

  • will appear to precede meaning that will “see” all updates made by , and will not see any updates made by , or
  • will appear to follow , meaning that will see ’s updates and will not see ’s.


Define a schedule 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 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:

An equivalent serial execution ():

An interleaved execution with no equivalent serial execution:


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

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

Conflict Serializable

A schedule is conflict serializable if it is conflict equivalent to some serial schedule , i.e. like .

Conflict Serializable is a GOOD thing