Assignment 3

 

Preliminaries

·       Read Chapter 6, Sections 1 – 3.

 

Problems

1.       A transaction is strict two-phase locked if it is two-phase locked and it holds all of its write locks until after it commits. (This is a standard term.) It is very-strict two-phase locked if it is strict two-phase locked and it holds all of its read locks until after it commits. (Not a standard term. It’s invented for this assignment.) Notice that strict two-phase locking is what results from the automatic locking approach described on slide 24 of Chapter 3 of the lecture notes.

a)      For each of the following histories is it possible that all transactions executed using very-strict two-phase locking?

b)      If not, what about strict two-phase locking?

c)      If not, what about ordinary two-phase locking?

d)      If not, is the history serializable?

For (a) – (c), add lock operations to the history to demonstrate your point. For (d) draw the serialization graph for the history.

 

In each history, changes from the previous history are noted in boldface.

H1 = w0[x,y,z] c0 r1[x] r1[y] w1[y] r2[x] w2[z] r1[y] c2 w1[z] c1

 

H2 = w0[x,y,z] c0 r1[x] r1[y] w1[y] r2[x] w2[z] r1[y] w1[z] c2 c1

 

H3 = w0[x,y,z] c0 r1[x] r1[y] w1[y] r2[y] w2[z] r1[y] c2 w1[z] c1

 

H4 = w0[x,y,z] c0 r1[x] r1[y] w1[y] r2[x] w2[x] r1[y] c2 w1[z] c1

 

H5 = w0[x,y,z] c0 r1[x] r1[y] w1[y] r3[z] r2[x] w2[x] c2 w3[z] w1[z] c3 c1

 

2.       Suppose each transaction is a sequential program with no internal concurrency (i.e., no multi-threading). Consider the following three transactions:
T1 = r1[x,y] w1[x]    T2 = r2[x] w2[z]     T3 = r3[z] r3[y] w3[y]

a)      Suppose the data manager is using two-phase locking, as in Section 6.1.4 of the textbook or slide 24 of the lecture slides. Suppose it receives the transactions’ reads and writes in the following sequence (i.e., the operations may execute in a different order than this):

r1[x,y] r2[x] w1[x]  w2[z] r3[z] r3[y] w3[y]

The transactions also submitted commit operations but the commits are not shown in the above sequence. Add each transaction’s commit operation to the earliest spot in the sequence where the data manager could have received that commit.

b)      Answer the same question for this sequence (the difference is highlighted in bold):

r1[x,y] r2[x] w1[x]  r3[z] w2[z] r3[y] w3[y]