Recitation #2

System Exercise:

Students must be able to individually answer the book problems and may work in groups at most 4 students on the system part. The system part will require you to install postgresql on your laptops and then tune brainz to make query answering as fast as possible. 

get 'em here!

I will list several queries that you must be able to answer. 

1. List the names of the members of 'The Beatles'
2. List the albums of 'The Beatles'
3. How many bands are called Nirvana?
4. When did Pete Best leave The Beatles?
5. Names of artists that died at age 27 between 1965 and 1995? 

If you are unable to have super-user access to a lap-top, let me know and I will try to arrange something. Whatever you do, DO NOT run this system exercise on the school's database server. You will certainly cause a lot of unintended consequences if you (even try to) do so. 

Paper Exercise:

It is supposed that through time, 107 billion individual human beings have lived. Let us assume that each of these people have an 8 byte id, a 3 byte encoding of their date of birth, a 3 byte encoding of their date of death, an 8 byte foreign key to their mother and an 8 byte foreign key to their father. Then we have 10 bytes to encode the characteristics of the persons life (their outlook, tastes, cause of death, basic life trajectory, etc.). Assume that disk blocks are 8K and with 64-bit addresses. Further assume that B+tree pointers are 64-bits and main memory pages are also 8K.

1. For person data, what is the blocking factor for a B+ tree leaf node with forward and backward pointer to sequential blocks.

2. How many disk blocks do we need to represent every person who ever lived?

3. What is the order of an internal B+tree node? 

4. Assuming that we cluster on person ids with completely filled leaf blocks. What is the maximum height B+tree for an index built over id as the search key. 

5. For 3 above, what is the minimum height tree?