Computer Engineering - Data Bases 2

Full exam

Check if 30% reduction: ◻ Last name:First name: Pers. code: Signature:Databases 2 - exam - January 15, 2025 -Dur. 2h S. Comai, P. Fraternali, D. Martinenghi Students with 30% reduction can omit: Exercise 2: point 3 Exercise 1: VSR classification - Exercise 3: point 3 A. Concurrency control (11 points) Consider the followingarrival sequenceAS, decorated with lock and unlock requests: AS=S 1( b)S 1( c)r 1( b)X 2( b)w 2( b)X 2( a)r 2( a)w 2( a)r 1( c)U 1( c)U 1( b)X 2( c)r 2( c)w 2( c)U 2( c)U 2( b)U 2( a)S 1( a)r 1( a)U 1( a), whereS i( z)indicates a shared lock request by transactionion resourcez, and similarly forX i( z)(exclusive lock) andU i( z)(unlock). LetHbe thehistoryora-posteriori sequence(without the indication of lock and unlock requests) derived fromASby a scheduler that grants locks whenever possible, or else puts the requesting transaction on hold until the requested resource becomes free. Every request inASmust be processed, regardless of whether the transaction issuing the request is currently waiting on other resources. 1.ShowH. IsHguaranteed to avoid all anomalies? Explain. [2 points] 2.ClassifyHwith respect to VSR, CSR, 2PL, Strict 2PL, TS Mono, and TS Multi (with the conventions adopted for TS Multi under Snapshot Isolation, used for the exercises). Justify your answers concisely (determine membership via class inclusion wherever possible). [up to 1.5 points per class]If more space is needed, use the extra space (last page) B. Ranking (10 points) Consider the following datasetDof hotels with their distances to points of interest (train stationtsand concert hallch).ts ch a0.300.80 b0.550.45 c0.700.30 d0.400.90 e0.600.20 f0.600.90 g0.900.15 h0.500.70 i0.800.101.Compute the skyline of Dwith SFS. Indicate all dominance tests. [4 points] 2.Indicate the 2-skyband ofD. [2 points] 3.Which hotels can be top-1 according to functionsinL 1(i.e., linear scoring functions)? [2 points] 4.LetFbe the set of functions of the formf(x, y)= w1x +w 2y , wherew 1> w 2, i.e., linear combina- tions giving more importance to the train sta- tion. Which hotels can be top-1 according to some function inF? [2 points] C. Physical DB (11 points) A bus travel system includes the following tables:Ticket (TicketId, RouteFrom, RouteTo, PassengerId, TravelDate, DepartureTime, ArrivalTime)containing 300K tickets in 45K blocks in an entry-sequenced primary storage. TablePassenger(PassengerId, Name, Email, City)stores 40K tuples in a B+ tree built onPassengerIdwith 3 levels and 2.5K leaf nodes. Val(RouteTo) = 250 and val(City) = 500. Evaluate the cost in terms of I/O accesses of the following query SELECT PassengerId FROM Ticket NATURAL JOIN Passenger WHERE RouteTo = ’New York’ AND City="Los Angeles"; in the three following scenarios:1.The query runs without any additional indexes on the tables. (3 points) 2.Both tables have secondary hash indexes:Ticket, built onPassengerId(4K blocks), with no overflow chains.Passenger, built onCity(600 blocks), with no overflow chains. (4 points) 3.In addition to the two previous indexes,Tickethas a composite B+ tree index built on(RouteTo, PassengerId)with 3 levels, and 6K leaf nodes. (4 points) For each scenario,•Briefly explain the plan (the join method, scan&look up, etc.). •Clearly explain the number of blocks/leaf nodes that need to be retrieved; report all the needed computations to understand the total cost. •Write the complete formula of the cost. Extra space