Data Base 2 — Practice

World Cup victories by discipline (SL, GS, SG, DH, AC — higher is better) for top male skiers: | Skier | SL | GS | SG | DH | AC | |---|---|---|---|---|---| | MG Girardelli | 16 | 7 | 9 | 3 | 11 | | MH Hirscher | 32 | 31 | 1 | 0 | 3 | | HM Maier | 0 | 14 | 24 | 15 | 1 | | BM Miller | 5 | 9 | 5 | 8 | 6 | | MO Odermatt | 0 | 28 | 16 | 6 | 0 | | IS Stenmark | 40 | 46 | 0 | 0 | 0 | | AS Svindal | 0 | 4 | 17 | 14 | 1 | | GT Thöni | 8 | 11 | 0 | 0 | 5 | | AT Tomba | 35 | 15 | 0 | 0 | 0 | | PZ Zurbriggen | 2 | 7 | 10 | 10 | 11 | 1. (2 pts) In which sense is a skyline item "potentially optimal"? Check all that apply: (a) ∃f ∈ L1 ∀s: f(t) ≥ f(s); (b) ∃f ∀s ≠ t: f(t) > f(s); (c) ∃f ∈ M (monotone functions) ∀s ≠ t: f(t) > f(s); (d) ∃f ∈ L1 ∀s ≠ t: f(t) > f(s). 2. (2 pts) Compute sky(D) (initials only) and list two dominance relationships holding in D. 3. (2 pts) D′ removes columns SL and DH. What is sky(D′)? 4. (2 pts) D′′ further removes SG. What is sky(D′′)? 5. (2 pts) Compare the three skylines — does removing columns increase/reduce the skyline, in this case and in general?

Men's ice-hockey team statistics (higher is better): A = NHL roster players, B = goals per game, C = power-play efficiency (%), D = Olympic appearances. ca(25, 4.8, 25.0, 24), cz(13, 5.0, 23.4, 10), fi(24, 3.1, 19.5, 19), de(7, 2.8, 18.2, 22), it(0, 1.4, 14.2, 10), lv(6, 2.4, 16.0, 6), sk(7, 1.2, 12.5, 9), se(25, 4.0, 21.0, 24), ch(10, 4.8, 24.1, 19), us(25, 4.8, 22.5, 25). 1. (3 pts) Compute the skyline on (A,B,C,D) using SFS, showing the dominance tests of your execution. 2. (5 pts) On the distributed version without A (lists B, C, D sorted best first — B: cz 5.0, ca 4.8, ch 4.8, us 4.8, se 4.0, fi 3.1, …; C: ca 25.0, ch 24.1, cz 23.4, us 22.5, se 21.0, …; D: us 25, ca 24, se 24, de 22, ch 19, …), find the top-2 teams with TA using f(B,C,D) = 10B + 10C + D. Show buffer, depth, sorted and random accesses. 3. (2 pts) Is there a monotone function of B, C, D for which Italy is among the top-3 teams?

Classify the schedule $$S = r_1(x)\; r_3(x)\; w_1(x)\; r_2(y)\; w_2(y)\; r_1(y)\; r_3(z)\; w_3(z)\; w_1(y)$$ with respect to VSR (listing view-equivalent schedules if any), CSR, 2PL, Strict 2PL, and TS Multi (Snapshot-Isolation conventions used in the exercises). Justify exhaustively; for 2PL, Strict 2PL and TS Multi show the result using the tables.

Given the resource hierarchy X(Y(A,B), Z(S,T)), describe the behaviour of the arrival sequence $$r_1(S)\; w_1(A)\; w_2(Z)\; r_2(A)\; r_3(X)\; w_1(Y)\; w_3(X)\; w_1(B)$$ under a scheduler applying hierarchical locking. Locks are released after each transaction's commit, which occurs immediately after its last operation. Show the step-by-step lock-state table for every resource.

Consider the schedule $$S = r_1(y)\; w_2(x)\; r_1(x)\; r_1(z)\; w_1(x)\; r_2(z)\; r_3(x)\; w_1(z)\; w_3(y)$$ a) (10 pts) Classify S with respect to VSR (listing view-equivalent schedules if any), CSR, 2PL, Strict 2PL, and TS Multi (Snapshot-Isolation conventions). Justify exhaustively, use class inclusion wherever possible, and show the 2PL and TS Multi results using tables. b) (2 pts) Suppose T2 aborts immediately after r2(z). Explain why this abort may compromise isolation, and which concurrency-control mechanism prevents it.

Nodes A, B, C, D of a distributed transactional system know these waiting conditions: - A: $E_D \to T_4 \to T_3 \to E_D$; $E_B \to T_5 \to E_D$; $E_D \to T_2 \to E_C$ - B: $E_C \to T_5 \to E_A$; $E_C \to T_8$ - C: $E_D \to T_8 \to T_5 \to E_B$; $E_A \to T_2 \to T_3 \to T_8 \to E_B$ - D: $E_A \to T_5 \to T_4 \to E_A$; $E_A \to T_3 \to T_2 \to E_A$; $T_8 \to E_C$ 1. (7 pts) Execute Obermarck's algorithm sending messages $E_X \to T_i \to T_j \to E_Y$ (toward node Y) only if $i < j$. Report the messages of every iteration (no graphs needed). 2. (4 pts) Can a different convention (send only if $i > j$) terminate in a different number of steps? Show it on this example.

Eight project proposals are scored in [0,10] on Merit, Potential, Feasibility, Impact (higher is better): AURIX(9,10,7,8), CIVIS(6,6,6,10), ECHO(7,7,8,8), LUMEN(9,8,8,8), NOVA(9,8,6,8), ORBIT(8,7,8,7), QUANTA(9,8,7,7), VERDE(8,7,9,9). 1. (3 pts) Compute the skyline with SFS, showing all dominance tests (initials suffice). 2. (4 pts) On the vertically distributed version (four best-first lists), compute the best proposal using TA with Mer + Pot + Fea + 10·Imp. Show every round's accesses and buffer, plus depth and access counts. 3. (2 pts) The funding agency wants ORBIT to win and asks for new non-negative weights (not all zero) of the weighted sum. Can any weights work? 4. (2 pts) Keeping only Pot and Fea, the director wants LUMEN to win by STRICTLY outscoring all others, yet no weighted sum works. Why? 5. (bonus) Is there a different monotone scoring function that satisfies the director?

A university manages rolling admissions with tables COURSE(courseName, availablePlaces), RANKING(studentId, courseName, position, status) — (courseName, position) unique, position 1 = top —, and ANOMALYLOG(id, courseName, availablePlaces, occupiedPlaces, timestamp). status ∈ {ASSIGNED, WAITING, ENROLLED, WITHDRAWN}; initially the top availablePlaces students per course are ASSIGNED, the rest WAITING; ENROLLED places are permanent. Assume no student/course insertions or deletions, courseName/position never updated, ENROLLED never becomes WITHDRAWN, and no multi-row ASSIGNED→WITHDRAWN statements. Write triggers guaranteeing (use WHEN wherever applicable, and state each trigger's event): 1. (4 pts) When an ASSIGNED student withdraws (ASSIGNED → WITHDRAWN), the place goes to the best-ranked WAITING student of the same course. 2. (4 pts) Per course, #(ASSIGNED ∪ ENROLLED) must never exceed availablePlaces; violating operations are rejected. 3. (4 pts) A single UPDATE may change availablePlaces for several courses. Write an AFTER UPDATE FOR EACH STATEMENT trigger that logs into ANOMALYLOG every updated course whose ASSIGNED/ENROLLED count now exceeds the new capacity (current timestamp), and raises an exception if any anomaly exists.

An academic application has tables Author(id, name, email, country), AuthorProfile(author_id, orcid, institution, bio), Article(article_id, title, publicationDate, main_author_id), Keyword(keyword_id, name), Article_keywords(article_id, keyword_id). An author optionally has one profile (owned 1:1); each article has exactly one main author; articles carry many keywords and vice versa. Scale — 50K authors, ≤50K profiles, 200K articles, 2K keywords; 1–50 articles per author; 5–10 keywords per article; popular keywords tag tens of thousands of articles. Access patterns — (1) author id → author + profile + articles; (2) keyword name → articles + each article's main author; (3) article id → article + main author + keywords. a) (6 pts) For the directions Author→AuthorProfile, AuthorProfile→Author, Keyword→Article and Author→Article, give: Required? (motivated), Owner, FetchType, CascadeType, and the COMPLETE annotation. b) (4 pts) Write the JPA entity mapping Article, justifying owners, fetch policies and cascade types against the access patterns and cardinalities.

Athlete(AthleteId, Firstname, Lastname, Age, CountryCode) — 40K tuples in a primary hash table on AthleteId, 2K blocks + 0.4K overflow blocks (chain length 0.2). Result(ResultId, Discipline, Event, Stage, AthleteId, Score, Ranking) — 120K tuples in 6K blocks, primary sequentially-ordered by (Discipline, Score), supported by a B+ index on (Discipline, Score) with 3 levels and 600 leaf nodes. val(CountryCode) = 100, val(Discipline) = 20, 70% of scores are ≥ 90. Query: ```sql SELECT * FROM Athlete JOIN Result ON Athlete.AthleteId = Result.AthleteId WHERE Discipline = 'ski jumping' AND Score >= 90 AND CountryCode = 'ITA'; ``` No caching. 1. (4 pts) Plan starting from the B+ tree. 2. (4 pts) Plan starting from the Athlete hash table. 3. (3 pts) Adding a hash index on Result(AthleteId) (no overflow, same hash organisation as Athlete, 2K blocks) — plan starting from a hash join.

Hotel(HotelID, HotelName, City, Country, Stars) — 500K tuples, primary hash on HotelID, 12K blocks, average lookup 1.2 I/O. Booking(BookingID, HotelID, CustomerID, CheckInDate, Nights, RoomType, Channel) — 20M tuples, entry-sequenced, 200K blocks. val(Country) = 100, val(Stars) = 5, val(RoomType) = 10, val(Channel) = 4; 3% of bookings are in July 2025; all distributions uniform. No caching. Query: ```sql SELECT * FROM Hotel H JOIN Booking B ON H.HotelID = B.HotelID WHERE H.Country = 'Italy' AND H.Stars = 4 AND B.CheckInDate BETWEEN '2025-07-01' AND '2025-07-31' AND B.RoomType = 'Suite' AND B.Channel = 'Online'; ``` 1. (4 pts) No secondary structures — cost the plan starting from Hotel and the plan starting from Booking. 2. (4 pts) Three secondary B+ indexes exist on Booking, each with 4 levels and 10K leaf nodes: Idx1(CheckInDate, HotelID, Channel), Idx2(RoomType, Channel, CheckInDate), Idx3(Channel, RoomType, CustomerID). For each, estimate (a) index blocks accessed and (b) candidate pointers followed; choose the best index and write the full plan. 3. (3 pts) An additional secondary B+ on Booking(HotelID) (4 levels, 10K leaves) exists — cost the plan exploiting it.

An industrial procurement application manages Manufacturers, Products, Optionals and Configurations. Users browse manufacturers → their products; each product has several compatible optional items; predefined configurations package ONE product plus a few of its optionals; for each product one can see all configurations packaging it. Scale — manufacturers: thousands; products: tens of thousands (uniform over manufacturers); optionals: hundreds of thousands (uniform over products); configurations: hundreds of thousands. a) (2 pts) Explain the fetch policy of associations and its default values. b) (4 pts) For Configuration→Optional and Optional→Configuration give: Required? (motivated), Owner, FetchType, CascadeType and the annotation. c) (4 pts) Write the JPA entity mapping Product, justifying owner, fetch and cascade choices against the access patterns and cardinalities.

Consider the following arrival sequence AS, decorated with lock and unlock requests ($S_i(z)$ = shared lock request, $X_i(z)$ = exclusive lock request, $U_i(z)$ = unlock by transaction $i$ on resource $z$): $$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)$$ Let H be the history derived from AS by a scheduler that grants locks whenever possible, else puts the requesting transaction on hold until the resource is free. Every request in AS is processed, even while its transaction waits on other resources. 1. (2 pts) Show H. Is H guaranteed to avoid all anomalies? Explain. 2. (9 pts) Classify H with respect to VSR, CSR, 2PL, Strict 2PL, TS Mono, and TS Multi (Snapshot-Isolation conventions). Justify concisely, using class inclusion wherever possible.

A distributed system has three nodes with these wait-for conditions: - Node A: $E_B \to t_4$; $t_4 \to t_7$; $t_7 \to t_5$; $t_5 \to E_C$ - Node B: $E_C \to t_1$; $t_1 \to t_3$; $t_3 \to t_2$; $t_3 \to t_4$; $t_4 \to E_A$ - Node C: $E_A \to t_5$; $t_5 \to t_6$; $t_6 \to t_8$; $t_6 \to t_1$; $t_1 \to E_B$ Apply the Obermarck algorithm and determine whether a deadlock is detected: 1. (4 pts) when a node transmits the arc $t_j \to t_i$ if $j > i$; 2. (4 pts) when a node transmits the arc $t_j \to t_i$ if $j < i$. 3. (3 pts) Considering schedules that include abort requests, explain why long-duration write locks (strict-2PL locks for writes) are required.

Given the resource hierarchy X(Y(A,B), W(C,D)), describe the behaviour of the arrival sequence $$r_1(C)\; r_2(D)\; w_1(A)\; w_2(W)\; r_2(A)\; r_3(X)\; w_1(Y)$$ under a scheduler applying hierarchical locking. Locks are released after each transaction's commit, which occurs immediately after its final operation. A waiting transaction does not proceed with subsequent operations. Present a step-by-step table (one row per operation or commit, one column per resource) showing the lock state of every resource.

Consider the schedule $$S = r_1(X)\; w_2(X)\; w_3(Z)\; w_1(X)\; w_5(X)\; r_6(Z)\; r_5(Y)\; r_3(Y)\; r_3(Z)\; r_5(X)\; r_2(Y)\; w_5(Y)\; r_5(Z)$$ Establish membership of S in VSR, CSR, 2PL, TS Mono, TS Mono with Thomas Rule, and TS Multi (usual conventions used in the exercises). Justify tersely, using class inclusion whenever possible.

City(CountryName, CityName, Population) has 10K tuples in a primary B+ tree on the composite key (CountryName, CityName) — 4 levels, 1.3K leaf nodes. Event(EventID, EventName, CityName, CountryName, Date, Category) has 1M tuples in 5K blocks of entry-sequenced storage. val(Category) = 25; 1% of events fall between 2023-12-01 and 2024-01-31; val(CountryName) = 100; cities uniform across countries. Query: ```sql SELECT * FROM City JOIN Event ON City.CityName = Event.CityName AND City.CountryName = Event.CountryName WHERE City.CountryName = 'Italy' AND Event.Date BETWEEN '2023-12-01' AND '2024-01-31' AND Event.Category = 'New Year Festival'; ``` 1. No auxiliary structures — cost two plans: (i) starting from City (3 pts), (ii) starting from Event (3 pts). 2. (4 pts) A secondary B+ on Event(Date) exists (3 levels, 1.2K leaf nodes); write a plan starting from this index. 3. (2 pts) Do the plans change if the SELECT list becomes `Event.*`? Explain. Ignore page caching and materialisation of intermediate results.

Consider the dataset D of hotels with distances (lower = better) to the train station (ts) and concert hall (ch): a(0.30, 0.80), b(0.55, 0.45), c(0.70, 0.30), d(0.40, 0.90), e(0.60, 0.20), f(0.60, 0.90), g(0.90, 0.15), h(0.50, 0.70), i(0.80, 0.10). 1. (4 pts) Compute the skyline of D with SFS, indicating all dominance tests. 2. (2 pts) Indicate the 2-skyband of D. 3. (2 pts) Which hotels can be top-1 according to linear scoring functions ($L_1$ combinations of the two distances)? 4. (2 pts) Let F be the functions $f(x,y) = w_1 x + w_2 y$ with $w_1 > w_2$ (train station matters more). Which hotels can be top-1 for some f in F?

Dataset D is vertically distributed over three sources with values in [0,1]. Find the top-2 items according to $f(t) = 4\,t.A + 2\,t.B + t.C$. | A | B | C | |---|---|---| | 1: 1.00 | 2: 0.80 | 2: 0.60 | | 7: 0.80 | 1: 0.65 | 7: 0.60 | | 2: 0.70 | 3: 0.55 | 3: 0.50 | | 3: 0.20 | 4: 0.50 | 1: 0.15 | | 6: 0.15 | 5: 0.30 | 5: 0.10 | | 4: 0.10 | 6: 0.30 | 4: 0.00 | | 5: 0.10 | 7: 0.30 | 6: 0.00 | 1. (4 pts) Apply FA. 2. (5 pts) Apply NRA, showing the buffer after each round. 3. (3 pts) Could NRA ever make fewer sorted accesses than FA? Explain. Indicate depth, number of accesses, results, and enough detail to follow each round and the stopping criterion.

Given the schema EMP(empID, name, deptID), PROJECT(projID, funding, deptID), DEPT(deptID, name, address), PROJECTS-INCOME(deptID, totAmt, perCapitaAmt). An employee belongs to a single department; a project is associated with a single department. Assume: primary keys are never updated; a project's funding and deptID cannot be NULL or modified; projects and departments cannot be deleted. Write the set of triggers that incrementally maintain totAmt (sum of the funds of all the department's projects) and perCapitaAmt (totAmt / number of employees in the department). List all the events the triggers must process and define the code of each trigger.

The classical "CPU" ML dataset reports MYCT (machine cycle time, ns — LOWER is better), MMIN, MMAX, CACH (KiB — HIGHER is better). An ML algorithm estimates relative performance as $erp(t) = -100\,t.MYCT + 10\,t.MMIN + t.MMAX + t.CACH$. The four lists are sorted from best to worst value: | MYCT | MMIN | MMAX | CACH | |---|---|---|---| | g: 25 | b: 8000 | b: 32000 | a: 256 | | b: 29 | d: 2000 | d: 8000 | g: 131 | | h: 50 | g: 1310 | a: 6000 | d: 65 | | d: 60 | c: 1000 | h: 4000 | b: 32 | | a: 125 | h: 1000 | c: 3000 | f: 8 | | f: 167 | f: 524 | g: 2620 | h: 8 | | e: 350 | a: 256 | f: 2000 | c: 0 | | c: 400 | e: 64 | e: 64 | e: 0 | 1. (6 pts) If possible, apply TA (adapting it if needed) to find the top-1 CPU; if not possible, explain why. Show depth, accesses, rounds and the stopping criterion. 2. (4 pts) Show the skyline of the dataset (no steps required).

Classify the schedule $$S = r_1(x)\; w_4(t)\; r_5(x)\; w_1(y)\; r_2(y)\; r_3(t)\; w_5(y)\; r_4(y)\; w_2(z)\; r_3(z)\; w_3(y)$$ with respect to VSR (listing the view-equivalent schedules if any), CSR, 2PL, Strict 2PL, and TS Multi (Snapshot-Isolation conventions used in the exercises). Justify exhaustively; for 2PL and TS show the result using the tables.

Ticket(TicketId, RouteFrom, RouteTo, PassengerId, TravelDate, DepartureTime, ArrivalTime) contains 300K tickets in 45K blocks of entry-sequenced primary storage. Passenger(PassengerId, Name, Email, City) stores 40K tuples in a primary B+ tree on PassengerId with 3 levels and 2.5K leaf nodes. val(RouteTo) = 250, val(City) = 500. Evaluate the I/O cost of ```sql SELECT PassengerId FROM Ticket NATURAL JOIN Passenger WHERE RouteTo = 'New York' AND City = 'Los Angeles' ``` 1. (3 pts) With no additional indexes. 2. (4 pts) With secondary hash indexes on Ticket(PassengerId) (4K blocks, no overflow) and Passenger(City) (600 blocks, no overflow). 3. (4 pts) Additionally, Ticket has a composite B+ index on (RouteTo, PassengerId) with 3 levels and 6K leaf nodes. For each scenario explain the plan, justify every block count, and write the complete cost formula.

An e-commerce catalog has categories (tens), brands (hundreds), devices (tens of thousands) and users (millions). Every brand belongs to exactly one category. Users browse category → brands → devices, can go from a device back to its brand, and can mark preferred brands. For each relationship direction below, state whether mapping it is required (with motivation), its annotation, the owner side, the fetch policy and the cascade policy appropriate for the access patterns: Category→Brand (Comprises), Brand→Category (ComprisedIn), Brand→Device (hasDevices), Device→Brand (hasBrand), User→Brand (Preference), Brand→User (Preference). Then show the code of the JPA entity mapping Brand, and comment on the design choices.

Ticket(TicketId, PurchaseDate, ConcertName, SeatSection, Customer, Price) holds 500K tickets sold over 8 years in a sequential structure of 20K blocks. Concert(ConcertName, Singer, Genre, Organizer, Description) holds 800 rows in a small primary B+ tree on ConcertName (2 levels, 30 leaf nodes). val(PurchaseDate) = 2000, val(Singer) = 100. Evaluate the I/O cost of ```sql SELECT ConcertName, COUNT(*) AS TicketsSold FROM Ticket JOIN Concert ON Ticket.ConcertName = Concert.ConcertName WHERE Singer = 'Taylor Swift' AND PurchaseDate BETWEEN '2024-01-01' AND '2024-12-31' GROUP BY ConcertName ORDER BY TicketsSold ASC LIMIT 1; ``` 1. (4 pts) No additional indexes; start from a scan of the concerts. 2. (4 pts) A hash index on Concert(Singer), 5 blocks, no overflow. 3. (4 pts) As in 1, plus a B+ index on Ticket(PurchaseDate, ConcertName) with 3 levels and 4K leaf nodes. For each scenario describe the strategy, justify every block count, explain how GROUP BY and ORDER BY are executed, and give cost formulas with and without caching.

In an ER schema, employees are either administrative staff or professors (total, exclusive specialisation). An admin assists exactly one employee; an employee may report to a supervising professor on multiple dates. The logical schema collapses everything into: EMP(ID, isProf, name, supervisor*, role*, assistedEmp*, level*) — starred attributes nullable, isProf true iff professor — and ReportsTo(EmpID, date). Write a trigger system enforcing coherence: (1) professors have a level and no role, admins the opposite (and an assistedEmp); (2) the supervisor FK must reference a professor; (3) a ReportsTo tuple must reference an EMP whose supervisor is not null. Handle insertions and deletions on both tables (not updates). Constraints may alternatively be handled in the table definitions — if so, include the CREATE TABLE statements. First list all violations to prevent and how each is handled.

A digital library manages Books, Authors, Readers, and the Countries of both authors and readers. Users browse author → books, country → authors, search books by title (seeing data + authors), read books and view their own read list. Operators see each book's readers with their data, books and country. Scale — authors: thousands; countries: tens; books: tens of thousands; readers: millions. a) (2 pts) Explain the meaning and usage of @JoinColumn and mappedBy. b) (4 pts) For the directions Country→Reader, Reader→Country, Book→Author and Reader→Book, state: Required? (motivated), Owner, FetchType, CascadeType, and the full annotation. c) (4 pts) Write the JPA entity mapping Author (with attributes), explicitly specifying and justifying owners, fetch policies and cascade types.

Consider the schedule $$S = w_3(x)\; r_2(y)\; r_1(x)\; w_3(z)\; w_2(x)\; r_3(y)\; w_1(x)\; w_1(z)$$ Classify $S$ with respect to VSR (if it is in VSR, list a view-equivalent serial schedule), 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 exhaustively but concisely, determining membership using class inclusion wherever possible.

Apply the distributed deadlock detection algorithm to the following wait-for conditions using two conventions: (1) a dependency $t_i \to t_j$ can be transmitted (forward) if $i > j$; (2) it can be transmitted if $i < j$. - Node A: $E_C \to t_4$; $t_4 \to t_7$; $t_7 \to t_5$; $t_5 \to E_B$ - Node B: $E_A \to t_5$; $t_5 \to t_6$; $t_6 \to t_1$; $t_1 \to E_C$ - Node C: $E_B \to t_1$; $t_1 \to t_3$; $t_3 \to t_2$; $t_3 \to t_4$; $t_4 \to E_A$ For each convention, execute all the steps, reporting all the messages that are sent during the process.

Classify the following schedule with respect to VSR, CSR, 2PL, Strict 2PL, and TS Multi (with the conventions adopted for TS Multi under Snapshot Isolation, used for the exercises). Motivate all your answers. If it is VSR, provide all the possible serializations; if it is not 2PL / Strict 2PL, explain which lock/unlock requests cause this. $$r_1(Z)\; r_2(X)\; w_2(Y)\; w_3(Y)\; w_4(Z)\; w_2(Z)\; w_5(X)\; r_5(Y)\; w_4(X)\; r_6(Y)\; w_6(X)$$

Consider the schedule $$S = r_4(x)\; w_3(x)\; r_4(z)\; w_4(y)\; r_2(x)\; r_1(x)\; w_2(z)\; w_3(y)\; r_2(y)\; w_1(x)\; w_1(y)$$ First, classify $S$ with respect to 2PL and TS Multi (with the conventions adopted for TS Multi under Snapshot Isolation, used for the exercises). Then also classify it with respect to VSR, CSR, Strict 2PL, and TS Mono, using class inclusion to determine membership wherever possible.

1. (3 pts) Given the view-serializable schedule $S = r_4(x)\; r_4(z)\; w_4(y)\; r_2(x)\; r_1(x)\; w_5(z)\; w_2(z)\; w_3(y)\; r_2(y)\; w_1(x)\; w_1(y)$, list all the possible equivalent serial schedules. 2. (3 pts) Explain why a view-serializable schedule may not be conflict-serializable, and provide an example. 3. (3 pts) Explain the notion of update lock and why it is useful. 4. (3 pts) Provide an example of a schedule that is not view-serializable but is in TS Multi, showing both properties on the example.

Consider the following three ranked lists of travel destinations (each entry is destination: score): | Landscape | Cultural experience | Availability of activities | |---|---|---| | A: 0.9 | B: 0.9 | F: 1.0 | | B: 0.8 | D: 0.8 | D: 0.9 | | C: 0.8 | F: 0.8 | G: 0.9 | | D: 0.7 | A: 0.6 | A: 0.8 | | E: 0.6 | C: 0.6 | B: 0.7 | | F: 0.6 | G: 0.5 | E: 0.6 | | G: 0.5 | E: 0.5 | C: 0.5 | 1. (4 pts) Determine the top-2 destinations using Fagin's Algorithm (FA) for two scoring functions — the maximum and the minimum of the three scores. Quantify the number of sorted accesses (s.a.) and random accesses (r.a.) required. In both cases the top destinations are those with the highest scoring-function values. 2. (4 pts) Same as above with the Threshold Algorithm (TA). 3. (2 pts) TA is instance optimal. Among the algorithms discussed in the lectures, are there any that incur lower cost than TA (s.a. + r.a.) on this particular instance?

Consider the relational schema PROJECT(PID, name, duration), EMP(EID, name, salary), ASSIGNMENT(PID, EID), where PID and EID in ASSIGNMENT are foreign keys to PROJECT and EMP. Define a set of triggers that maintain a table BUDGET(PID, cost) with the same content as the view: ```sql CREATE VIEW budget AS SELECT P.PID, COALESCE(SUM(salary), 0) AS cost FROM project P LEFT JOIN assignment A ON P.PID = A.PID LEFT JOIN emp E ON E.EID = A.EID GROUP BY P.PID; ``` Assume primary-key values are never updated and each employee is assigned to at most one project. 1. (3 pts) For each event (INSERT/UPDATE/DELETE) and table, state whether a trigger is needed for maintaining BUDGET; name the needed triggers and justify the others. 2. (9 pts) Write the code of the triggers.

A group from Milan and Como seeks a meeting point minimizing the mean travel time and keeping times balanced. For a place with travel time $x$ to Milan and $y$ to Como they score $f(x,y) = m + s$, with $m = \frac{x+y}{2}$ and $s = \sqrt{(x-m)^2 + (y-m)^2}$ (geometrically, $s$ is the distance of $\langle x,y \rangle$ from the bisector $x = y$). Lower is better. Three options A, B, C are distributed over two ascending rankings (use $f(20,100) \approx 116.57$): | x (to Milan) | y (to Como) | |---|---| | B: 20 | A: 20 | | A: 100 | B: 100 | | C: 110 | C: 110 | 1. (2 pts) What is the skyline of this dataset? Just the result. 2. (2 pts) Compute the top-1 meeting point with TA according to f. Show depth and accesses. 3. (3 pts) The result found by TA is not a skyline point. Explain how this is possible. 4. (2 pts) Compute the top-1 meeting point with FA according to f. Show depth and accesses. 5. (3 pts) The result found by FA is wrong. Explain how this is possible. 6. (2 bonus pts) Draw the shape of the iso-score curves of f.

Consider a dataset with attributes x, y, z where HIGH values are better. T1 (sorted by x): D(10,2,4), E(6,1,5), A(4,1,2), F(2,2,3), H(2,7,4), I(2,0,5), J(2,3,1), C(1,0,5), B(0,6,0), G(0,0,4). 1. (4 pts) Use SFS to compute the skyline of T1, indicating ALL dominance tests made by the algorithm. 2. (4 pts) T2 contains the same tuples sorted by z instead: C, E, I, D, G, H, F, A, J, B. Compute the skyline of T2 with SFS (no need to show all steps) and comment on the result. 3. (4 pts) T3 has the same data with every value approximated to the closest multiple of 5: D(10,0,5), E(5,0,5), A(5,0,0), H(0,5,5), J(0,5,0), B(0,5,0), F(0,0,5), I(0,0,5), C(0,0,5), G(0,0,5). Compute its skyline, and state in general whether after such an approximation (a) a non-skyline point can become skyline; (b) a skyline point can become non-skyline.

DRIVER(DriverID, LastName, FirstName, BirthYear, City, …) has 50K tuples over 5K blocks in a primary hash structure on DriverID (filling factor < 50%). TRIP(TripID, Date, OriginID, DestID, DriverID, TotalKM) has 15M tuples stored sequentially ordered by DriverID on 150K blocks. val(OriginID) = 5K, val(City) = 25. Describe a reasonably efficient plan and estimate the cost of ```sql SELECT * FROM DRIVER WHERE City = 'Milan' AND DriverID IN (SELECT DriverID FROM TRIP WHERE OriginID = 'Linate') ``` in three scenarios (when a plan uses the cache, also describe the uncached variant): 1. (3 pts) No secondary access structures — show nested loop, a plan scanning TRIP first, and a plan scanning DRIVER first. 2. (4 pts) TRIP has a secondary hash index on DriverID (same hash function as DRIVER's primary structure, no overflow cost, 5K blocks). 3. (4 pts) TRIP additionally has a B+ index on OriginID (3 intermediate levels, 50K leaf nodes).

An application manages multimedia user-generated content. Content items have a title, a description, a media file, and a creation date, and are associated with one or more categories. Creators may "like" content by other creators. Creators log in and access the list of their created contents, ordered by descending creation date; they can select a category and view its contents ordered by descending creation date; for each content they see the creator and the list of creators who liked it, in descending alphabetical order of surname. Creators are in the order of millions, contents in the order of tens of millions, categories in the order of tens; contents are uniformly distributed over creators and categories. The conceptual model has entities Creator (uid, firstname, lastname, username, password, photo, status), Content (cid, title, description, creationdate, mediafile) and Category (catid, name), with relationships: authorship (Creator 0:N — Content 1:1), genres (Content 1:N — Category 0:N), liking (Creator 0:N — Content 0:N). 1. (5 pts) Design the annotations for the relationships. Specify the owner side of each relationship, define the appropriate mapped-by attribute, and detail the fetch and cascading policies, justifying each choice against the required access patterns. 2. (5 pts) Show the JPA entities (with all their attributes) that map the domain objects, taking into account the access paths and data cardinalities.

Table Task(tId, title, completion, wp) contains 100K tuples stored in a primary hash structure built on tId, with 20K blocks and filling factor below 50%. Table Workpackage(wpId, title, allocatedHours) contains 5K tuples in 50 blocks stored in a primary entry-sequenced sequential structure. 70% of the tasks have completion > 90% and 25% of the work packages have fewer than 100 allocated hours. Tasks are indexed by a secondary B+ tree on wp (3 levels, 1000 leaf blocks). You can cache up to 15 blocks. Describe an efficient query plan for each query, estimate the execution costs (write the complete formula) and explain every step. Plan efficiency is part of the grade. 1. (6 pts) SELECT * FROM Task WHERE completion > 90 AND wp IN (SELECT wpId FROM Workpackage WHERE allocatedHours < 100) 2. (6 pts) SELECT w.title, AVG(t.completion) FROM Workpackage w LEFT JOIN Task t ON t.wp = w.wpId GROUP BY w.wpId, w.title

Customer(CUSTID, LastName, FirstName, Country) has 800K tuples; Purchase(PRODUCTID, CUSTID, DATE, Qty) has 8M tuples. For each scenario below, describe an efficient plan for the query, write the complete cost formula and explain every step (plan efficiency is graded): ```sql SELECT * FROM Customer C JOIN Purchase P ON C.CUSTID = P.CUSTID WHERE Country = 'Italy' OR Country = 'Spain' ``` 1. Purchase is entry-sequenced, 40K blocks. Customer is a hash table on the key, 8K blocks, negligible overflow. val(Country) = 160. 2. As in 1, plus Purchase has a secondary hash index on CustID (same hash function as Customer) with overflow access cost 1.3, occupying 10.5K blocks. 3. As in 2, plus Customer has a B+ index (3 levels, 1K leaf nodes) on Country.

An urban pollution monitoring system stores measurements from ground stations in the schema: STATION(SID, name, status), POLLUTANT(PID, name, threshold), RECORD(SID, PID, TIMESTAMP, value), STATS(SID, PID, average, peak), ALERT(SID, TIMESTAMP). Stations insert a record only when a value changes. Define triggers that react to record insertion as follows: 1. (2 pts) The average value at that station of the pollutant in the record is updated. 2. (3 pts) If the recorded value exceeds the station's maximum for that pollutant, the peak is updated. 3. (3 pts) If the peak of ANY pollutant exceeds its threshold, the station status becomes 'critical' and an alert tuple is created (or updated if it exists) with the last alert timestamp. 4. (3 pts) If 10 subsequent below-threshold values are recorded in a critical station after the last alert, the status is reset to 'normal' and the alert deleted. Assumptions: weekly monitoring with Monday cleanup (timestamps are distinct progressive integers within the week); at week start averages/peaks are 0 and all stations 'normal'.

Consider the Object-Relational Mapping of JPA. 1. (3 pts) Define the JPA concepts of entity, persistence unit, persistence context, and managed entity. 2. (3 pts) Define the concept of fetch mode for relationships, the annotations needed to express it, and the defaults provided by JPA. 3. (3 pts) Define the notion of relationship owner in JPA, provide an example, and motivate its importance.