COMP9315 24T1 Exercises 06
Implementing Selection on Multiple Attributes (N-d) 		DBMS Implementation

  1. Consider a file of n=50000 tuples allocated across b=1024 pages using a multi-attribute hash function giving d=10 hash bits. The tuples in this file have four fields R(w,x,y,z) and a choice vector that allocates hash bits to fields as follows: dw=5, dx=2, dy=3, dz=0. Assuming that there are no overflow pages, compute how many pages each of the following queries would need to access:


    1. select * from R where w=5432 and x=3
    2. select * from R where w=4523 and x=9 and y=12
    3. select * from R where x=3
    4. select * from R where z=3
    5. select * from R where w=9876 and x>5

  2. Consider a file of r=819,200 Part records (C=100): 

    CREATE TABLE Parts (
       id#     number(10) primary key,
       name    varchar(10),
       colour  varchar(5) check value in ('red','blue','green'),
       onhand  integer
);

    Used only via the following kinds of pmr queries:

    Query Type pQ
    < id#, ?, ?, ? > 0.25
    < ?, name, colour, ? > 0.50
    < ?, ?, colour, ? > 0.25

    Give and justify values for d and the dis and suggest a suitable choice vector.


  3. Consider the student relation: 

    Student(id:integer, name:string, address:string,
        age:integer, course:string, gpa:real);

    with the following characteristics: r = 40,000,   B = 1024,   C = 20

    If the relation is accessed via a superimposed codeword signature file with false match probability pF=10-4, compute the costs of answering the query: 

    select * from Student where course='BSc' and age=20;

    for the following file organisations:

    1. record signatures
    2. block signatures
    3. bit-sliced block signatures

    Use the following to compute signature properties:

    k = \frac{1}{\log_e2} . \log_e \left( \frac{1}{p_F} \right)        m = \left( \frac{1}{\log_e 2} \right)^2 . n . \log_e \left( \frac{1}{p_F} \right)

  4. Consider a multi-attribute hashed relation with the following properties:

    • schema R(a,b,c), where all attributes are integers
    • a file with pages b=2, depth d=1, split pointer sp=0, records/page C=2
    • a split occurs after every 3 insertions
    • an initially empty overflow file
    • choice vector = < (1,0), (2,0), (3,0), (1,1), (1,2), (2,1), (2,2), (3,1), ... >
    • the hash value for each attribute is simply the binary version of the value
      (e.g. hash(0) = ...0000, hash(1) = ...0001, hash(4) = ...0100, hash(11) = ...1011, etc.)

    Show the state of the data and overflow files after the insertion of the following tuples (in the order given): 

    (3,4,5)   (2,4,6)   (2,3,4)   (3,5,6)   (4,3,2)   (2,6,5)   (4,5,6)   (1,2,3)