Databases, Assignment 3
                        17 November, 2010
                      Due 26 November, 2010

1. Consider the following schedule of concurrent read and write
   operations.

     --------+-------+-------+-------+-------+--------
     |  T1   |  T2   |  T3   |  T4   |  T5   |  T6   |
     --------+-------+-------+-------+-------+--------
     | r(x1) |       |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       | r(x3) |       |       |       |
     --------+-------+-------+-------+-------+--------
     | r(x2) |       |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       | r(x4) |       |       |       |
     --------+-------+-------+-------+-------+--------
     | w(x2) |       |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       | r(x2) |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       | w(x3) |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       | r(x3) |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       | w(x4) |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       | r(x4) |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     | w(x1) |       |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       | r(x1) |       |       |
     --------+-------+-------+-------+-------+--------
     |       | w(x4) |       |       |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       | w(x1) |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       |       | r(x4) |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       |       | r(x1) |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       | w(x3) |       |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       |       |       | r(x3) |
     --------+-------+-------+-------+-------+--------
     |       |       |       |       | w(x1) |       |
     --------+-------+-------+-------+-------+--------
     |       |       |       |       |       | w(x3) |
     --------+-------+-------+-------+-------+--------

   Compute whether this schedule is conflict-serializable.  If so, list
   out all possible serial schedules that are consistent with this
   schedule.

2. Consider the following graph-based locking protocol, which
   allows only exclusive lock modes, and which operates on data
   graphs that are in the form a rotted directed acyclic graph:

   - A transaction can lock any vertex first.

   - To lock any other vertex, the transaction must be holding a
     lock on the majority of the parents of that vertex.

   Show that the protocol ensures serializability and deadlock
   freedom.

3. Consider a database system that includes an atomic increment
   operation in addition to the read and write operations.  Let V
   be the value of data item X.  The operation

      increment(X) by C

   sets the value of X to V+C in an atomic step.  The value of X
   is not available to the transction unless the latter executes
   a read(X).  The lock-compatibility matrix for three lock
   modes: share mode, exclusive mode and incrementation mode, is
   shown below.

                  S       X      I
            S    true   false  false
            X    false  false  false
            I    false  false  true

   a. Show that, if all transcation lock the data that they
      access in the corresponding mode, then two-phase locking
      ensures serializability.

   b. Show that the inclusion of increment mode locking allows
      for increased concurrency.