12 09 2023 E TS

Page 1

Databases 2 - exam - September 12, 2023 - Dur. 2h S. Comai, P. Fraternali, D. Martinenghi A. Concurrency Control (7 points) Classify the following schedule S with respect to VSR, CSR, 2PL, Strict 2PL, TS-mono, and TS-multi. Motivate all your answers. • If it belongs to VSR, provide all the possible serializations. • If it does not belong to 2PL and/or 2PL-strict, explain which lock/unlock requests cause this. S = r3(X) w3(Y ) w2(Y ) w1(Z) r3(Z) w4(X) r4(Y ) w1(X) r5(Y ) w5(X) If additional space is required, please use the last page. Solution. Detailed analysis for the CSR class Not CSR: there are cycles in the resource graph. (2) (2) T2 T5 T4 T3 T1 Detailed analysis for the VSR class Not VSR: the schedule is not CSR and no permutation/relocation of its blind writes{w4(X), w 1(X), w 3(Y ) } makes it CSR. Detailed analysis for the 2PL and Strict 2PL classes Not 2PL or Strict 2PL as S is not CSR. In particular, w1(X) cannot anticipate the lock before w4(X) and w1(Z) must release the lock before r3(Z). Similarly, r3(Z) cannot anticipate the lock request and w3(Y ) must release the lock before w2(Y ). The table below shows a pair of incompatible requests (circled in red). 1 2 3 4 5 6 7 8 9 10 X ↑3 r3 ↓3↑4w4 ↓4 ↑1 w1 ↓1↑5w5 ↓5 Y ↑3w3 ↓3↑2w2 ↓2 ↑4 r4 ↓4 ↑5 r5 ↓5 Z ↑1w1 ↓1 ↑3 r3 ↓3 2 4 5 Legend ↑: read lock request ↑: write lock request ↓: unlock request For Strict 2PL, pairs of incompatible mandatory unlock requests and commit times are shown below. 1 2 3 4 5 6 7 8 9 10 X r 3 w4 w1●∣1 w5 Y w 3 ↓3w2 r4 r5 Z w 1 ↓1r3●∣3 Legend ↓: mandatory unlock request ●∣: commit time Detailed analysis for the TS Mono class Not TS-mono, since w1(X) occurs after w4(X) and w2(Y ) after w3(Y ). Operation RTM(X) WTM(X) RTM(Y ) WTM(Y ) RTM(Z) WTM(Z) Killed transactions r3(X) 3 (0) 0 0 (0) 0 0 (0)…