Transaction Processing Study Guide and Homework 5

CSE444

You should be able to do all of the following problems for the final exam. So, you can use this as a study guide to test your understanding of transaction processing.

To Turn In: Select 3 of the 8 problems to write up and turn in for the final homework.

Due: Wednesday, December 10

  1. Find all conflicts in the following schedule:
  2. S: r2(X); r1(X); w1(X); r1(Y); w2(X); c2; w1(Y); c1;

    Conflicts: r2(x) conflicts with w1(x); r1(x) conflicts with w2(x); w1(x) conflicts with w2(x). 

  3. In the following schedule, tell which transactions read from other transactions:
  4. S: r1(X); r2(Y); w1(X); r3(X); w2(Y); c2; w3(X); c3; r1(Y); w1(Y); c1;

    T3 reads from T1

    T1 reads from T2

    Is this schedule recoverable? No, because T1 commits after T3 and T3 reads from T1.

  5. Are the following 2 schedules conflict equivalent?
  6. S1: r1(X); r2(Y); w2(Y); r1(Y); w1(X); w1(Y); r2(X); w2(X); c2; c1;

    Conflicts: w1(x),r2(x) & r1(x),w2(x) & w1(x),w2(x) & w2(y),r1(y) & r2(y),w1(y) & w2(y),w1(y)

    S2: r2(Y); r3(Z); w3(Z); w2(Y); r1(X); w1(X); r1(Y); w1(Y); r2(X); w2(X); c2; c1; c3;

    Conflicts: r2(y),w1(y) & w2(y),r1(y) & w2(y),w1(y) & r1(x),w2(x) & w1(x),w2(x) & w1(x),r2(x)

    The schedules are conflict equivalent because the order of all conflicting operations is the same in both schedules.

  7. Is this schedule conflict serializable?
  8. S: r1(X); r2(Y); w1(X); r3(X); w2(Y); c2; w3(X); c3; r1(Y); w1(Y); c1;

    Use algorithm on page 545

    T1

    T3 T2

    There are no cycles in the precedence graph, so the schedule is conflict serializable.

  9. Does the following schedule follow the 2 phase locking protocol?
  10. T1

    T2

    Read_lock(Y)

     

    Read_item(Y)

     

    Unlock(Y)

     

     

    Read_lock(X)

     

    Write_lock(Y)

     

    Y = Y + X

     

    Write_item(Y)

     

    Unlock(Y)

     

    Unlock(X)

    Write_lock(X)

     

    Read_item(X)

    X = X * Y

     

    Write_item(X)

    Unlock(X)

     

    No. T2 follows the protocol but T1 does not -- it doesn't make all its locks before any item is unlocked. Note that to determine if a schedule follows 2PL, you only have to look at what each T does individually; how they are intertwined is not relevant.

  11. Give an example of a schedule with a deadlock.
  12. T1

    T2

    Read_Lock(y)

     

    Read_item(y)

     

     

    Read_lock(x)

     

    Read_item(x)

    Write_Lock(x)

     

     

    Write_lock(y)

  13. Give an example of a schedule in which the basic Timestamp ordering algorithm would cause a transaction to abort.
  14. Let's say T1 has timestamp 1, and T2 has timestamp 2. The sequence W2(X);R1(X) would cause T1 to abort (whereas the sequence W1(X);R2(X) is OK).

    (page 565) Basic idea is to order all of the transactions with a timestamp (just a uid used to identify transactions within the database). Schedules are serializable with the transactions in the order of their TS. With each item, x, in the database, we associated a read_TS(x) which is the largest timestamp of all transactions that have read from x, and a write_TX(x) which is the largest timestamp of all transactions that have written to x. If some transaction T tries to issue a read_item(x) or write_item(x), we compare its TS with read_TS(x) and write_TS(x). If the TS ordering is violated, we abort T and resubmit it to the system with a new timestamp.

  15. Given a schedule with locks, what technique would you use to detect deadlocks?

Construct a wait-for graph (page 564). Whenever transaction TI is waiting to lock an item locked by TJ, create a directed edge TI->TJ. When TJ releases the lock on the item TI was waiting for, drop the edge. We have a deadlock if there is a cycle in the graph.