CSEP 545 Transaction Processing for E-Commerce, Winter 2005                       University of Washington	1/18/05

Assignment 3

Preliminaries

·      Read Chapter 6, Sections 1 – 3. (Read the revision of the chapter that was handed out, not the version in the textbook.)

Problems

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

For each transaction in each of the following histories:

a)      Is it strict two-phase locked?

b)      If not, is it semi-strict two-phase locked? If so, add the lock operations that demonstrate it.

c)      If not, is it two-phase locked? If so, add the lock operations that demonstrate it.

d)      If not, is it serializable? Draw a serialization graph to demonstrate whether it’s serializable. If so, does it preserves transaction handshakes?

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

i. r₁[x,y] r₂[y] w₂[x] r₃[v] w₁[v] c₂ c₁ w₃[x] c₃

ii. r₁[x,y] r₂[y] w₂[x] c₂ r₃[v] w₁[v] c₁ w₃[z] c₃

iii. r₁[x,y] r₂[y] w₂[x] r₃[x] w₁[v] c₂ c₁ w₃[z] c₃

iv. r₁[x,y] r₂[y] w₂[x] c₂ r₃[x] w₁[v] c₁ w₃[z] c₃

v. r₁[x,y] r₂[y] w₁[v]  c₁ w₂[x] c₂ r₃[x] w₃[z] c₃

 2.      Suppose each transaction is a sequential program (i.e. with no internal concurrency).
 

a)      Suppose the database system uses two-phase locking. Could transactions issue the following sequence of operations?: r₁[x,y] r₂[y] w₂[x] c₂  r₃[v] w₁[v]  c₁ w₃[x] c₃

b)      Reconsider 2(a) assuming the database system uses strict two-phase locking.

c)      Now answer the question for the following sequence, again assuming strict two-phase locking: r₁[x,y] r₂[y] w₂[x] r₃[v] w₁[v] w₃[x] c₂ c₁ c₃