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;

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.