ib cs - Apr 14, 14:50

hl with database

🏆 Free — No Login Required
← Back to All Olympiads

1. A university uses a relational schema where STUDENT(StudentID PK, Name, AdvisorID FK) references ADVISOR(AdvisorID PK, Name). A trigger enforces that every student must have an advisor whose ID exists in ADVISOR. The DBA deletes an advisor row without cascading. Which combination of transaction isolation level and lock type on ADVISOR would guarantee the trigger never sees a phantom advisor deletion, and what is the earliest instant the trigger’s check can be safely executed?

Solution
Correct: A
Under SERIALIZABLE the DBMS acquires a range (next-key) lock on the predicate AdvisorID=?, preventing concurrent inserts or deletes that could create phantoms. The trigger’s referential check must run after the advisor row is X-locked (so the decision to delete is irrevocable inside the transaction) but before the DELETE commits (so the trigger can still abort the transaction if a student references the advisor).

2. A distributed OLTP system uses two-phase commit (2PC). The transaction manager logs , receives unanimous votes , then crashes before logging . After restart the recovery procedure reads the log. Which log record combination allows the TM to decide the fate of T without remote communication and what is the resulting terminal decision?

Solution
Correct: B
In 2PC if the TM has logged and collected from every cohort it is allowed to commit (it has reached the commit point). Because the crash happened after this but before the log record, the TM can infer it must have decided to commit and can therefore redetermine that decision without contacting cohorts.

3. A B+-tree index uses 8 KiB pages, 12-byte pointers, 8-byte keys, and a 69 % fill-factor. Ignoring headers, what is the maximum number of keys that can be stored in a non-root leaf node and how many child page pointers accompany them?

Solution
Correct: C
Usable space = 0.69 × 8192 ≈ 5654 bytes. Each (key, pointer) pair occupies 8 + 12 = 20 bytes. 5654 / 20 = 282 pairs. However, a non-root leaf also needs one extra pointer to the next leaf page, so total pointers = 282 + 1 = 283. But 283 pointers imply 282 separators, so the correct pair is 374 keys and 375 pointers.

4. Consider the schedule S = r1(x), w2(x), r1(y), w3(y), c3, c2, c1. Which of the following is the minimal conflict-equivalent serial order and does it avoid cascading aborts?

Written response required.
Solution
Correct: N/A
The conflicting operations are w2(x) → r1(x) (T2→T1) and w3(y) → r1(y) (T3→T1). The topological sort gives T2→T3→T1. Because T2 commits before T1 reads x and T3 commits before T1 reads y, no transaction reads uncommitted data, so the schedule avoids cascading aborts.

5. A query performs a hash-join on relations R (2 M pages) and S (3 M pages) with a 40 % selective predicate on S. Memory is 102 pages. Using the hybrid grace-hash algorithm, what is the minimum number of passes required to complete the join and how many partitions are created in the first pass?

Written response required.
Solution
Correct: N/A
One page is reserved for input buffer, leaving 101 for partitions. Smaller relation R needs ⌈2 M / 101⌉ = 19802 partitions, but we can stop recursive partitioning when partition size ≤ memory. After first pass we get 30 partitions (102-1). Largest partition of R is 2 M / 30 ≈ 66 k pages ≤ 102, so only 2 passes total are required.

6. The SQL statement SELECT * FROM T WHERE a=5 ORDER BY b LIMIT 10 can use either (a) a clustered B+-tree on (a,b) or (b) a hash index on a plus an in-memory sort. Table T occupies 50 k pages and 100 tuples match a=5. Which index yields the fewest page I/Os and what is that number?

Written response required.
Solution
Correct: N/A
The B+-tree is clustered on (a,b) so the 100 matching rows are adjacent. With 100 tuples and typical 100-tuples-per-page density we read at most 2 leaf pages plus 9 internal pages = 11 pages. The hash index would require fetching 100 random pages plus 1 for sorting = 101 pages.

7. A DBA runs VACUUM FULL on PostgreSQL which rewrites the entire heap and rebuilds all indexes. Afterwards the auto-vacuum daemon still performs routine vacuums. Which statistics are retained across VACUUM FULL and which are reset, affecting the planner’s choice?

Written response required.
Solution
Correct: N/A
VACUUM FULL rebuilds the heap so physical row statistics such as n_live_tup are recomputed (reset). However, the planner relies on the pg_statistic catalog which is preserved across VACUUM FULL unless ANALYZE is run again, so the histogram bounds remain intact.

8. In MongoDB a collection has a compound index {a:1,b:-1}. A query db.c.find({a:{$gt:3},b:{$lt:7}}).sort({a:1,b:-1}) is executed. Which of the following describes the index intersection plan and its sorting behaviour?

Written response required.
Solution
Correct: N/A
The index is a prefix match for both predicates and the sort order aligns exactly with the index direction. MongoDB can traverse the index range (3, +∞) for a and (-∞, 7) for b, producing already ordered documents, so no additional sort stage is needed; the query is covered by the index.

9. A multi-version system uses timestamp ordering with MVTO. Transaction T (TS=50) wants to read object O whose current version is WTS=60 and RTS=55. What action does MVTO take and what timestamp is assigned to the new read version?

Written response required.
Solution
Correct: N/A
MVTO allows a read only if TS(T) ≥ WTS(O). Here 50 < 60 so the read is invalid. MVTO therefore aborts T and no read version is created.

10. A data warehouse uses bitmap join indexes: BJI1 on (d.year, f.product) and BJI2 on (d.quarter, f.store). Query GROUP BY d.year, d.quarter needs to combine both indexes. Which bitmap operation is required and what is the resulting compression ratio compared to materializing the join?

Written response required.
Solution
Correct: N/A
The GROUP BY needs rows that satisfy both dimension predicates, so bitmap AND is applied. Each bitmap index compresses to ≈1 bit per row, while the join materializes foreign-key integers (4 bytes), giving a compression ratio of 32:1 per index. Combining two such indexes yields roughly 8:1 overall saving.