Answer the following questions related to concurrency control and transaction schedules. (solutions)

Consider the following transaction schedule of accesses to Amazon’s inventory database to purchase unspecified copies of a CD, DVD, and book. Assume that the transactions run without the benefit of isolation.

\(T_1\) \(T_2\)
Read (# CDs)  
  Read (# Books)
Write (# CDs - 1)  
Read (# Books)  
Write (# Books - 2)  
  Write (# Books - 1)
  Read (# DVDs)
  Write (# DVDs - 1)

These questions are adapted from CS 40: Database Management Systems at Furman University (Treu 2005).

  1. Explain how this schedule violates the requirement of data consistency (i.e., what data anomaly exists?).

    The transaction schedule exemplifies the lost update problem. Transaction \(T_2\) overwrites the update to the number of books made by transaction \(T_1\), causing the inventory to be two books more than are actually available.

  2. Write a serializable schedule for the two transactions that is not simply serial. Justify that it is serializable and that it fixes the aforementioned data anomaly.

    \(T_1\) \(T_2\)
    Read (# CDs)  
    Write (# CDs - 1)  
      Read (# Books)
      Write (# Books - 1)
    Read (# Books)  
    Write (# Books - 2)  
      Read (# DVDs)
      Write (# DVDs - 1)

    This schedule is serializable because there are no cycles in the dependency graph between the transactions. More specifically, \(T_2\) reads the number of books before \(T_1\) writes that value, \(T_2\) writes the number of books before \(T_1\) reads that value, and \(T_2\) writes the number of books before \(T_1\) writes that value.

  3. Add explicit locking instructions (using shared and exclusive locks) to the initial schedule. Note that inserting locks may cause some existing operations to be reordered. What is the outcome of the two transactions?

    \(T_1\) \(T_2\)
    Shared Lock (# CDs)  
    Read (# CDs)  
      Shared Lock (# Books)
      Read (# Books)
    Exclusive Lock (# CDs)  
    Write (# CDs - 1)  
    Unlock (# CDs)  
    Shared Lock (# Books)  
    Read (# Books)  
    Exclusive Lock (# Books) fails  
      Exclusive Lock (# Books) fails
      deadlock – abort transaction (and release locks)
    Exclusive Lock (# Books)  
    Write (# Books - 2)  
    Unlock (# Books)  
      Shared Lock (# Books)
      Read (# Books)
      Exclusive Lock (# Books)
      Write (# Books - 1)
      Unlock (# Books)
      Shared Lock (# DVDs)
      Read (# DVDs)
      Exclusive Lock (# DVDs)
      Write (# DVDs - 1)
      Unlock (# DVDs)

    The initial schedule deadlocks when \(T_2\) attempts to acquire an exclusive lock on the number of books. That transaction is aborted, which allows \(T_1\) to continue.

  4. Does the transaction schedule with locking satisfy the requirements of two-phase locking (2PL)?

    No, two-phase locking (2PL) requires a transaction to have a growing (i.e., acquiring locks) and shrinking (i.e., releasing locks) phase. In the prior example, \(T_1\) releases its lock on the number of CDs prior to acquiring the lock for the number of books.

  5. Create a strict two-phase locking (strict 2PL) schedule for the two transactions.

    \(T_1\) \(T_2\)
    Shared Lock (# CDs)  
    Read (# CDs)  
      Shared Lock (# Books)
      Read (# Books)
    Exclusive Lock (# CDs)  
    Write (# CDs - 1)  
    Shared Lock (# Books)  
    Read (# Books)  
    Exclusive Lock (# Books) fails  
      Exclusive Lock (# Books) fails
      deadlock – abort transaction (and release locks)
    Exclusive Lock (# Books)  
    Write (# Books - 2)  
    Unlock (# Books)  
    Unlock (# CDs)  
    Commit  
      Shared Lock (# Books)
      Read (# Books)
      Exclusive Lock (# Books)
      Write (# Books - 1)
      Shared Lock (# DVDs)
      Read (# DVDs)
      Exclusive Lock (# DVDs)
      Write (# DVDs - 1)
      Unlock (# DVDs)
      Unlock (# Books)
      Commit