COMP9315 14s2

The University of New South Wales COMP9315 DBMS Implementation Final Exam 14s2

DBMS Implementation

Question 7 (8 marks)

Consider a relation R(a,b,c) implemented as a multi-attribute hashed file, with the following properties:

• the file has b = 256 pages, so the least significant 8-bits of the hash values are used
• choice vector: (bit 0 is the least significant bit)
  • bit 0 in the tuple hash comes from bit 0 of the hash of attribute a
  • bit 1 in the tuple hash comes from bit 0 of the hash of attribute b
  • bit 2 in the tuple hash comes from bit 0 of the hash of attribute c
  • bit 3 in the tuple hash comes from bit 1 of the hash of attribute a
  • bit 4 in the tuple hash comes from bit 2 of the hash of attribute a
  • bit 5 in the tuple hash comes from bit 1 of the hash of attribute b
  • bit 6 in the tuple hash comes from bit 1 of the hash of attribute c
  • bit 7 in the tuple hash comes from bit 3 of the hash of attribute a
• query distribution:
  • Q₁:   select * from R where a = k,     P_Q1 = 0.3
  • Q₂:   select * from R where b = j,     P_Q2 = 0.2
  • Q₃:   select * from R where a = k and b = j,     P_Q3 = 0.2
  • Q₄:   select * from R where b = j and c = m,     P_Q4 = 0.1
  • Q₅:   select * from R where a = k and c = m,     P_Q5 = 0.2
  where k, j and m are constants of the appropriate type

Based on the above, answer the following:

1. How many pages are accessed in answering queries of type Q₁?

2. How many pages are accessed in answering queries of type Q₂?

3. How many pages are accessed in answering queries of type Q₃?

4. How many pages are accessed in answering queries of type Q₄?

5. How many pages are accessed in answering queries of type Q₅?

6. What is the weighted average cost of answering a query on this relation?

Instructions:

• Type your answer to this question into the file called q7.txt
• Submit via:   submit q7