CS245  Winter 2000

ASSIGNMENT 7

due in class on Tuesday February 29

PROBLEM 1

Consider the following two transactions:

 T0:  	read(A);
      	if (A = 0) then
          [ read(B); B = B + 1;	write(B) ]
 T1:	read(B);
	if (B = 0) then
          [	read(A);  A = A + 1; write(A);]

Let the consistency requirement be AB = 0
(A times B equals 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 T0 and T1 which produces a 
    nonserializable schedule.

(c) Is there a concurrent execution of T0 and T1 which produces a
    serializable schedule?



PROBLEM 2

Do problem 9.2.4 in textbook, parts (b) and (d) only.
Only answer questions (i) and (ii).


PROBLEM 3

Do problem 9.7.1 in textbook, parts (b) and (c) only.


PROBLEM 4

Do problem 9.9.1 in textbook, parts (b) and (c) only.


PROBLEM 5

In a lock table, the system keeps a "group mode" that records the 
"strongest" lock type of the transactions that have currently 
locked an object.  In particular, say object O is locked in 
modes M1, ... Mj and let the group mode of O be GM(O).  
Then, for any possible lock mode N,
(i)  GM(O) and N are not compatible if and only if there is an
     Mi element of {M1, ..., Mj} such that N and Mi are not 
     compatible; and
(ii) GM(O) and N are compatible if and only if for all Mi element of
     {M1, ..., Mj}, N and Mi are compatible.
When a new lock request arrives, for lock mode N, the system can simply
check if N is compatible with GM(O),
instead of checking N against all locks currently held on object O.

Consider the multiple granularity locking mechanism (Section 9.6).
In each of sub-problems (a) through (f) below, the modes of currently 
held locks on an object O are given.  (For instance, in case (a), 
object O is locked in mode IS by two transaction and in mode S by 
two transactions.)  For each case, give the group mode, if there is one. 
(Be careful, some of the cases below are impossible! In those cases, 
just say there is no group mode.)

(a)  S, IS, S, IS
(b)  IX, IS, IS
(c)  S, IS, IX
(d)  IS, SIX, S
(e)  IS, SIX
(f)  X, IS

END OF ASSIGNMENT 7