Authors: PA Berstein, N Goodman

Summary

Survey paper on database concurrency control that puts the myriad algorithms into one mathematical basis for easier digestion.

In order to set up the foundation of discussion, the authors decompose the problem into dealing with read write conflicts and write-write conflicts. Correctness criteria for concurrency control

  • each transaction will eventually be executed
  • computation is the same as if it were in a single dedicated system

The transaction processing model contains a transaction manager (TM) and data manager (DM), along with the transactions and the data. The interface of TM-DM is the core of transaction processing module.

The processing model looks like the following

  • Centralized: begin, read(x), write(x,v), end. DBMS could avoid partial results by using 2PC.
  • Distributed: different in the handling of private workspace and 2PC.

Note that > The DBMS may restart T any time before a dm-write has been processed. The effect of restarting T is to obliterate its private workspace and to reexecute T from the beginning. As we will see, many concur- rency control algorithms use transaction restarts as a tactic for attaining correct executions.

Problem Decomposition

serial execution: Let E denote an execution of transactions T1….. T,. E is a serial execution if no transactions execute concurrently in E; that is, each transaction is executed to completion before the next one begins.

serializability: An execution is serializable if it is computationally equivalent to a serial exe- cution, that is, if it produces the same out- put and has the same effect on the database as some serial execution.

execution of a transaction: formally model an execution of transactions by a set of logs, each of which indicates the order in which dm-reads and dm-writes are processed at one DM.

Timestamp Ordering

WIP but basically went into a lot of detail to discus how timestamp ordering works and how it interacts with 2PL and combinations.

Misc:

  • Mutual exclusion problem is OS is similar to concurrency in DBs but it’s lower level (threads, processes)