COMP9315 19T2 Quiz 4Sample Solutions DBMS Implementation

1. Characteristics of Employee table:

• # data pages = b = ceil(r/c), where c = floor(B/R)
• c = 8192/200 = 40, b = ceil(10000/40) = 250
• since it's a sparse index, there's one index entry per data page
• # index entries per index page = c_i = floor(B/R_i) = 1024
• b_i = ceil(b/c_i) = ceil(250/1024) = 1
• so, the answer is (250,1)

2. Key values in root node of B-tree after new index results in promote/split all the way to the root.

This was ambiguous, since there are a several ways of interpreting B-tree splitting.

A simple view would be to say 21 overfills the (19,20,22) node, so we promote 20. This causes (7,13,19) to overfill, so we promoted 13. Thus 13 ends up in the root node (13,25).

An alternative view (not really valid for this question, but reasonable) is that we "temporarily" insert the new key into the node and then work out the "middle" node. If the node becomes (19,20,21,22) then we could choose either 20 or 21. If we choose 21 and push it to (7,13,19,21), then we're likely to choose 19 (for consistency with the choice below), so 19 ends up in the root node (19,25).

I accepted both as correct.

3. Multi-attribute hashing query. How many pages are accessed to answer a query?

• known attributes contribute 5+2 = 7 bits
• unknown attribute gives 3 unknown bits ⇒ need to examine 23 pages

4. Storage requirements for a bitmap index

• each bitstring contains 16384 bits = 2048 bytes
• one bitstring for each colour ⇒ 8 bitstrings
• each page can hold floor(B/2048) bitstrings
• B wasn't given in the question, so assume 8192
• this means 4 bitstrings can fit (exactly) in each page
• so we have ceil(8/4) = 2 pages of bitstrings + header page ⇒ 3 pages