COMP9315 Final Exam The University of New South Wales
COMP9315 DBMS Implementation
Final Exam
DBMS Implementation
[Instructions] [Notes] [PostgreSQL] [C]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8]

Question 4 (6 marks)

Consider a table R(a,b,c,d) indexed by tuple-based superimposed codeword signatures. The data and signature files have the following properties:

Page Size4096 bytes
Number of records (rR)10000
Record size (RR)32 bytes
Signature size (m)58 bits
Bits/attribute (k)10 bits
False match probability (pF)1 in 1000

You can make the following (slightly unrealistic) assumptions:

Based on the above, answer the following:

  1. How many pages are there in the data file?

  2. How many pages are there in the signature file?

  3. How many pages are read in answering the query R(?,b,c,d)?
    (include both signature pages and data pages, as needed)

  4. How many pages are read in answering the query R(?,?,?,?)?
    (include both signature pages and data pages, as needed)

  5. What feature of the query signature would allow you to optimise the page reads for R(?,?,?,?)?

  6. What would be the values of m and k if we decided to use page-level signatures, rather than tuple-level signatures?

Show all working.

Instructions:

End of Question