CS609  Database Systems
Fall 2016

Assignment 1

 

 

Solution

Due:  Monday, Sept. 12 during class (turn in hard copy)
Mode:  INDIVIDUAL

1)  Are the following schedules conflict serializable?  If so, indicate to which schedules they are equivalent.
     
    a)  W0(A) W0(B) W0(C) W0(D) C0 W2(A) R3(A) W3(B) R1(C) R1(D) W1(D) W2(C) C2 R3(D) C3 C1
    b)  W0(X) W0(Y) W0(Z) C0 R1(X) R2(Y) R2(X) W1(X) C1 R3(Z) W3(Z) C3 W2(X) C2   

    c)  W0(A) W0(B) W0(C) C0 W3(A) R1(A) W1(A) R2(A) W3(C) R2(C) R2(B) W2(B) W3(B) C3 C1 C2

 

2)  For each schedule in 1) above indicate its type of recoverability (if any). Justify your answer.

3)  Apply the following concurrency control techniques to the schedule:

         R2(X) W2(X) R1(X) R3(Y) W3(Y) W1(X) R3(Y) R3(X) W2(X) W2(Y) C2 C1 C3

        a)  Strict 2PL 

        b)  2PL and Wait-Die
        c)  2PL and Wound-Wait

Show just the Ri, Wi, Ai (Abort), Bi (Blocked), Ci (committed) operations. Assume TS(T1) < TS(T2) < TS(T3); assume strong strict transactions; and any transactions aborted are restarted and executed serially at the end of the schedule.  

4) Assume this tree and:
    Suppose T21 reads record ra2 in file Fa.  To do so, T21 needs to lock the database, A1 and Fa in IS mode (in that order) and finally to lock ra2 in S mode.
    Suppose T22 modifies ra9 in Fa.  T22 needs to lock the database, A1 and Fa (in that order) in IX mode and finally to lock ra9 in X mode
    Suppose T23 reads all the records in Fa.   T23 needs to lock the database and A1 (in that order) in IS mode and finally to lock Fa in S mode.
    Suppose T24 reads the entire database.  It can do so after locking the database in S mode.
 Which of the above transactions can access the database concurrently?  Justify your answer.  Note - give all possible concurrent execution combinations.

5) Apply the following concurrency control techniques to the schedule:

       R2(X) W2(X) R1(X) R3(Z) W3(X) W3(Z) W1(X) R5(X) R4(Z) W4(X) C2 C3 C1 C5 C4

        a)  timestamp ordering
        b)  multiversions

Please show all read/write timestamp changes and versions.  Assume TS(T1) < TS(T2) < TS(T3) < TS(T4).   Also, assume any transactions aborted are restarted and executed serially at the end of the schedule.  For multiversion, show which version was read and for a write indicated on which version it was based.

6)   a)  To the following schedule apply the optimistic concurrency control (where V indicates validation phase):  Note: V3 and V4 are in the validation phase at the same time.

R1(A) R1(B)     W1(D) V1
                           R2(Z) R2(D)      W2(Z) V2
                                                  R3(A) W3(A)               V3
                                                  R4(C) R4(D) W5(A)     V4
                                                              R5(A) W5(A)             V5

  b)  Determine if optimistic guarantees view or conflict serializability.  Justify your answer using an example.