COMP9315 21T1
Exercises 06
Implementing Selection on Multiple Attributes (N-d)
DBMS Implementation
[Show with no answers] [Show with all answers]
1.
2. 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:
a.
b. select * from R where w=5432 and x=3 [show answer]
c. select * from R where w=4523 and x=9 and y=12 [show answer]
d. select * from R where x=3 [show answer]
e. select * from R where z=3 [show answer]
f. select * from R where w=9876 and x>5 [show answer]
3.
4. Consider a file of r=819,200 Part records (C=100):
CREATE TABLE Parts (
5. id# number(10) primary key,
6. name varchar(10),
7. colour varchar(5) check value in (‘red’,’blue’,’green’),
8. onhand integer
9. );
10.
Used only via the following kinds of pmr queries:
11. Query Type
12. pQ
13. < id#, ?, ?, ? >
14. 0.25
15. < ?, name, colour, ? >
16. 0.50
17. < ?, ?, colour, ? >
18. 0.25
19.
Give and justify values for d and the dis and suggest a suitable choice vector.
[show answer]
20.
21. Consider the student relation:
Student(id:integer, name:string, address:string,
22. age:integer, course:string, gpa:real);
23.
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;
24.
for the following file organisations:
a. record signatures
b. block signatures
c. bit-sliced block signatures
25. Use the following to compute signature properties:
 
[show answer]
26.
27. 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.)
28. 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)
29.
[show answer]