Recitation #2

**** NOTE THAT THIS IS NOT YET COMPLETE! MORE PROBLEMS WILL BE ADDED. ****

1.

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/blocks are also 8K.

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

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

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

d. 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.

e.. For d. above, what is the minimum height tree?

2. 

The system part will require you to install postgresql on your laptops and then tune
brainz to make query answering as fast as possible. You may work with one other partner on this system exercise.

First get the data here: brainz.zip

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.