>HW #7

CS245A PROBLEM SET #7
Due by 5pm, Thursday, March 12, 1998.
4 problems, equal credit. 100 pts.

Problem 1: Group Modes in Lock Tables

Consider the shared/exclusive/warning scheme described in class and in the lecture notes. In the table below you are given six different cases of simultaneously held locks on some object. In each case, give the group mode that is stored in the lock table, or explain briefly why the situation is impossible.

Case Locks

i S, S, IS

ii SIX, S, SIX

iii IX, IS, IS

iv IX, X

v S, IX

vi SIX, IS

Case	Locks
i	S, S, IS
ii	SIX, S, SIX
iii	IX, IS, IS
iv	IX, X
v	S, IX
vi	SIX, IS

Problem 2: Tree locking

Suppose we have three transactions, T, U, and V that obey the tree protocol described in class and in the notes. Transaction T locks A, B, C, and E; U locks C and F; V locks B and E. In how many ways can T, U, and V be scheduled legally if A, B, C, D, E, and F are organized in the following hierarchy.

Problem 3: Timestamps vs. 2PL

Show that neither two-phase locking nor timestamp-based concurrency control is more general than the other by giving an example of a schedule that is 2PL but not timestamp compliant and an example of a schedule that is timestamp compliant but not 2PL. Make your two examples as simple as possible.

Problem 4: View-Serializability

Consider the following schedule of three transaction, T, U, and V:

T: rB wC

U: wB wC

V: wB rC

Show the polygraph for this schedule. Is this schedule view-serializable? Briefly explain your answer.