01 09 2022 E TS

Page 1

Databases 2 - exam S. Comai, P. Fraternali, D. Martinenghi September 1, 2022 A. Concurrency Control (8 points) Given the resource hierarchy X(Y(A,B), Z(S,T)), describe the behavior of the following arrival sequence of requests managed by a scheduler that applies hierarchical locking. Suppose that locks are released after the commit of each transaction, which occurs immediately after the last operation of each transaction. r1(S) w1(A) w2(Z) r2(A) r3(X) w1(Y) Solution. Op. X Y A B Z S T r1(S) ISL1 - - - ISL1 SL1 - w1(A) IXL1 (upgr) IXL1 XL1 - ISL1 SL1 - w2(Z) IXL1,2 IXL1 XL1 - ISL1 (Conflict - T2 waits!) SL1 - r2(A) T2 is waiting r3(X) IXL1,2 Conflict - T3 waits! IXL1 XL1 - ISL1 (Conflict - T2 waits!) SL1 - w1(Y) IXL1,2 XL1 (upgr) XL1 - ISL1 SL1 - T1 commits IXL2 - - - - - - w2(Z) IXL2 - - - XL2 - - r2(A) IXL2 ISL2 SL2 - XL2 - - T2 commits - - - - - - - r3(X) SL3 - - - - - - T3 commits - - - - - - - 1 B. Physical Databases (8 points) A table FILE(fid, name, mediaType, description) stores 100K tuples on 1K blocks in a primary entry sequenced storage. A table HYPERLINK(source, target , rel) stores 1M tuples on 10K blocks in a primary hash built on the primary key with negligible overflow chains. The relation is not symmetric: if A→B is in HYPERLINK B→A may or may not be in HYPERLINK. We also know that • val(mediaType)=200; • only 5% of the hyperlinks correspond to a relation of type “alternate”. Consider the query that finds pairs of HTML files, one of which is an alternative version of the other: select F1.fid, F2.fid from (FILE F1 join HYPERLINK on F1.fid=source) join FILE F2 on F2.fid = target where F1.mediaType="HTML" and F2.mediaType="HTML" and rel="alternate" and source <> target Describe briefly (but precisely) a reasonable query plan and estimate its cost in the…