============
Assignment 5
============

Solve the following exercises. Unlike previous assignments, this should be done
individually.

Submit your solutions in person to Mateusz Pawlik by 12.02.2016.

The solutions must be hand-written.

-----------------------------------------------
1. (1 Point) Exercise 14.19 from the text book.
-----------------------------------------------

Explain why the read-committed isolation level ensures that schedules are 
cascade-free.

------------------------------------------------
2. (2 Points) Exercise 14.15 from the text book.
------------------------------------------------

Consider the following two transactions:

T13:
read(A)
read(B)
if A = 0 then B := B+1
write(B)

T14:
read(B)
read(A)
if B = 0 then A := A+1
write(A)

Let the consistency requirement be A = 0 or B = 0, with A = B = 0 the initial 
values.

  (a) Show that every serial execution involving these two transactions 
      preserves the consistency of the database.
  (b) Show a concurrent execution of T13 and T14 that produces a nonserializable
      schedule.
  (c) Is there a concurrent execution of T13 and T14 that produces a serializable
      schedule?

------------------------------------------------
3. (2 Points) Exercise 15.27 from the text book.
------------------------------------------------

The multiple-granularity protocol rules specify that a transaction Ti can lock 
a node Q in S or IS mode only if Ti currently has the parent of Q locked in 
either IX or IS mode. Given that SIX and S locks are stronger than IX or IS 
locks, why does the protocol not allow locking a node in S or IS mode if the 
parent is locked in either SIX or S mode?

------------------------------------------------
4. (2 Points) Exercise 15.31 from the text book.
------------------------------------------------

As discussed in Exercise 15.19, snapshot isolation can be implemented using a 
form of timestamp validation. However, unlike the multiversion timestamp-ordering 
scheme, which guarantees serializability, snapshot isolation does not guarantee
serializability. Explain what is the key differ- ence between the protocols that
results in this difference.

----------------------------------------------------------
5. [Optional] (1 Point) Exercise 14.20 from the text book.
----------------------------------------------------------

For each of the following isolation levels, give an example of a schedule that 
respects the specified level of isolation, but is not serializable:
  
  (a) Read uncommitted
  (b) Read committed
  (c) Repeatable read