(TAKE HOME PORTION) WINTER 2017
1. B Tree Construction (10 Points)
Consider a B Tree where each node contains at most two key values and pointers to at most three child nodes. Suppose values less than or equal to a key value are stored in the appropriate left subtree and values greater than a key value are stored in the appropriate right subtree.
Draw the tree which results after inserting the following integer keys in the given order: 1, 5, 9, 13, 4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14, 17, 18, 19, 20.
Date: March 9, 2017.
1
2. Extendible Hashing (10 Points)
Consider a hashing function, h, which produces the following binary values for the keys,
key1, to key10 as shown below:
h(key1) = 000000 h(key2) = 000111 h(key3) = 101010 h(key4) = 010101 h(key5) = 110011 h(key6) = 001100 h(key7) = 111000 h(key8) = 000111 h(key9) = 000011 h(key10) = 111100
Suppose each disk block can store 2 keys (and their associated records). Draw the directory structure and the referenced disk blocks which result from inserting the keys in the order shown above.
2
3. k-d Tree Construction (10 points)
Consider a k-d Tree which stores 3-dimensional data (i.e. triples (x,y,z) where x, y, and z are integers. The levels in the tree alternate splitting on each dimension starting with the first (so the first split is on x, the second on y, the third split is on z, and the next level starts again with x). Values which are less than or equal to the split value should be stored in the left subtree and values which are larger than the split value should be stored in the right subtree.
Draw the tree which results after inserting the following values in the listed order:
(1, 2, 3) (2, 1, 3) (1, 3, 2) (2, 3, 1) (3, 1, 2) (3, 2, 1) (4, 2, 3) (2, 4, 3) (4, 3, 2) (2, 3, 4) (3, 4, 2) (3, 2, 4)
3
4. Functional Dependencies
Note that in the following questions, T, U, V, W, X, Y, and Z represent individual
attributes.
4.1. Minimal Cover (5 points). Let F = {T → XY, U → YZ, V → W, W → TU }.
Compute the minimal cover of F.
4.2. Closure T+ (5 points). For the same set of functional decompositions F shown
above, compute T+.
4.3. Closure V + (5 points). For the same set of functional decompositions F shown
above, compute V +.
4.4. Closure W+ (5 points). For the same set of functional decompositions F shown
above, compute W+.
5.1. Decomposition (10 points).
Assume
R = (S T U V W X Y Z)
and
F = {S → TV , T → U, W → XY , SW → Z}
Where S, T, U, V , W, X, Y and Z represent individual attributes.
Decompose R into BCNF, lossless, dependency preserving.
If this is not possible, decompose R into 3NF, lossless, dependency preserving. Show
your decomposition and state whether is it BCNF or 3NF.
5.2. Decomposition (10 points).
Assume
R = (S T U V W X Y Z)
and
F = {S → TUV W, T → UV , W → XY , V → Z }.
Where S T, U, V , W, X, Y and Z represent individual attributes.
Decompose R into BCNF, lossless, dependency preserving.
If this is not possible, decompose R into 3NF, lossless, dependency preserving. Show
your decomposition and state whether it is BCNF or 3NF.