[SOLVED] CS336 Homework 7

HW7

1. Consider the schedule given below in Table below. R(·) and W(·) stand for ‘Read’ and ‘Write’, respectively. T stands for transactions and t stands for time stamps.

t1 t2 t3 t4 t5 t6 t7 t8 t9 t10

T1 T2 T3

i. ii.

iii.

R(A)
R(C)

W(B) W(D)

W(E)

R(H) R(I) W(A) R(K) W(F) W(J)

W(G) R(D) W(H) R(B) R(E) R(G)

Give the dependency graph of this schedule.
Is this schedule conflict serializable? If you answer “yes”, provide the equivalent serial schedule. If you answer “no”, briefly explain why.
Is this schedule possible under 2PL?

2. Consider the following schedule that involves transactions T1, T2, and T3.
   S: r1(X), r2(Y), r3(Y), w2(Y), w1(X), w3(X), r2(X), w2(X)
   Is this schedule possible under 2PL? If yes, then write the corresponding serial schedule.
   If no, then provide an equivalent non-serial schedule that is possible under 2PL with minimum swapping of operations.
3. Consider the following schedules of transactions T1, T2, T3.
   S1: r2(A), w2(A), r3(C), w2(B), w3(A), w3(C), r1(A), r1(B), w1(A), w1(B) S2: r3(C), r2(A), w2(A), w2(B), w3(A), r1(A), r1(B), w1(A), w1(B), w3(C) S3: r2(A), r3(C), w3(A), w2(A), w2(B), w3(C), r1(A), r1(B), w1(A), w1(B)
   1. Which of the above schedules are conflict equivalent to each other?
   2. Which of these schedules are possible in 2PL?
   3. For the schedules that are not possible in 2PL, show whether it is possible to swap the

      operations to get equivalent schedule that is possible under 2PL.

4. S: r1(Y), w1(Y), r2(Y), w2(Y), r1(X), w1(X), r2(X), w2(X). Is this schedule possible in 2PL? Explain your answer. Produce a schedule with the same set of operations that will cause a deadlock.
5. T1= read(A), A:=A+5, write(A), read(B), B:=B-10 T2= read(A), A:=A-10, write(A), read(B), B:=B+5 T3= read(A), A:=A+3, write(A), read(B), B:=B-2

   A schedule is equivalent (not conflict equivalent, just equivalent) to a serial schedule S if it leaves the database in the same state as S (items have the same values)

   IsthereascheduleSforT1,T2andT3whichisnotequivalenttosomeserialschedule? Ifso,show such schedule. If not, explain why.

6. Suppose beers by

Bar Tavern Tavern Tavern Tavern

for the new bar New Tavern has a remote order system which allows customers order themselves. The inventory information of New Tavern is shown in the table:

Beer Inventory Budweiser 13 Heineken 22
Pabst Blue Ribbon 3

Corona 9

There are three customers A, B and C ordering beers remotely, they start their transactions in the given order:

1. 1)  Customer A orders two Budweisers:

   𝑇 = 𝑟1(𝐵𝑢𝑑)𝑤1(𝐵𝑢𝑑) 1

2. 2)  Customer B orders one Budweiser and one Pabst Blue Ribbon:

   𝑇 = 𝑟2(𝐵𝑢𝑑)𝑤2(𝐵𝑢𝑑)𝑟2(𝑃𝐵𝑅)𝑤2(𝑃𝐵𝑅) 2

3. 3)  Customer C orders two Coronas:

   𝑇 = 𝑟3(𝐶𝑜𝑟)𝑤3(𝐶𝑜𝑟) 3

4. 4)  Customer D orders three Pabst Blue Ribbons:

   𝑇 = 𝑟4(𝑃𝐵𝑅)𝑤4(𝑃𝐵𝑅) 4

Let

1. 𝑆1 = r1(Bud)r2(PBR)r3(Cor)w1(Bud)r2(Bud)w2(PBR)r4(PBR)w4(PBR)w2(Bud)w3(Cor)
2. 𝑆2 = r3(Cor)r1(Bud)r2(Bud)w1(Bud)w2(Bud)r2(PBR)w3(Cor)r4(PBR)w2(PBR)w4(PBR)

Q1: For schedules 𝑆1 and 𝑆2, which one is conflict-serializable? Which one is not conflict-

serializable? Please justify your answer with Precedence Graph.
Q2: For the schedule that is not conflict-serializable, show it will not be granted under 2PL protocol. Q3:Schedulethatisnotconflict-serializable,whattroubleswould itcauseforNewTavern?