Labs 4 - Schedules, lock-based protocols.
=========================================

Exercises
=========

(1) Consider the following schedules.

    Schedule 1
    ---------------------------
    T1:       T2:       T3:
                        read(Z)
                        read(X)
              read(Z)
              write(Z)
    read(X)
    read(Y)
    write(X)
              read(X)
              read(Y)

    Schedule 2
    ---------------------------
    T1:       T2:       T3:
    read(X)
              read(Y)
              read(Z)
                        read(Y)
    write(X)
              write(Z)
                        write(Y)
              write(Y)

    (a) Draw the precedence graph of both schedules.
    (b) Give all possible serializability orders of both schedules. Explain why 
        the list is complete.
    (c) For Schedule 1 add two commits and an abort command such that the 
        resulting schedule is not recoverable.
    (d) Are both schedules valid two-phase locking schedules? If yes, give lock
        and unlock instructions. If no, explain why.

(2) Consider the following schedule.

    T1:       T2:
    read(X)
    write(X)
              read(A)
              read(B)
    read(B)
    write(B)

    (a) Is the schedule conflict serializable?
    (b) Is the schedule recoverable if both transactions commit immediately 
        after the last operation?
    (c) Is the schedule cascadeless?

(3) Consider the following schedule.

    T1:       T2: 
    read(Y)
              read(Y)
    Y:=Y-50
    write(Y)
              read(X)
    read(X)
              show(X+Y)
    X:=X+50 
    write(X) 
    show(X+Y)

    (a) Show the conflict graph of the schedule.
    (b) Is the schedule conflict serializable? Explain your answer.
    (c) Add lock and unlock instructions such that T1 and T2 conform to the 
        two-phase locking protocol.
    (d) Is the schedule possible under the two-phase locking protocol? Explain 
        your answer.

(4) Draw the conflict graph of the following schedule and show whether the 
    schedule is conflict serializable or not.

    T1:       T2:       T3:
              read(Z)
              read(Y)
              write(Y)
                        read(Y)
                        read(Z)
    read(X)
    write(X)
                        write(Y)
                        write(Z)
              read(X)
    read(Y)
    write(Y)
              write(X)

(5) Consider the following two transactions.

    T1:                   T2:
    read(X)               read(Y)
    read(Y)               read(X)
    if X=0 then Y:=Y+1    if Y=0 then X:=X+1
    write(Y)              write(X)
    
    (a) Add lock and unlock instructions to T1 and T2 such that they conform 
        to the two-phase locking protocol.
    (b) Show a concurrent schedule of T1 and T2 that results in a deadlock. 
        Show also the evolution of the wait-for graph.
    (c) For the schedule in (b) what happens under the wait-die deadlock 
        prevention protocol?

(6) Consider the following schedule.

    T1:       T2:
    read(X)
              write(Y)
    read(Y)

    (a) Is this schedule possible under the tree protocol if the order of data 
        items is X->Y? If yes, add lock and unlock instructions.
    (b) Is this schedule possible under the tree protocol if the order of data 
        items is Y->X? If yes, add lock and unlock instructions.
    (c) Is this schedule cascadeless? If no, where to place the commits in order 
        to make it cascadeless?

(7) Consider the following schedule.

    T1:       T2:       T3:       T4:
    read(X)
              write(X)
                        read(X)
    read(Y)
              write(Y)
    read(Z)
                        write(Z)
                                  read(Z)
                                  write(Z)

    (a) Is the following schedule conflict serializable? Explain why.
    (b) If it is serializable, give an equivalent serial schedule.

(8) Consider the following schedule.

    T1:       T2:       T3:
    read(X)
    read(Y)
              read(X)
                        read(X)
                        write(X)
    read(Z)
    write(Z)
    COMMIT
              write(Y)
              COMMIT
                        read(V)
                        COMMIT

    (a) Is this schedule a valid strict two-phase locking schedule? If yes, add 
        all required lock and unlock instructions. If no, explain why.
    (b) Assume read(X) in T2 is moved immediately after write(X) in T3. Is it
        then a valid strict two-phase locking schedule? If yes, add 
        all required lock and unlock instructions. If no, explain why.