Compgen Tool Suite

Problem Set #4

mcmillan / Version 13

Comp 521: Files and Databases -- Fall 2012
Problem Set #4
Issued: 10/31/2012 Due: In class 11/20/2012

Homework Information: Some of the problems are probably too long to attempt the night before the due date, so plan accordingly. Late homework will penalized by a factor of 70.71% for each late class period. Feel free to work with others, but the work you hand in should be your own.

Question 1.

Consider the following B+ tree:

A) Show the resulting tree after inserting the search key 12 into the given tree.

B) Show the resulting tree after inserting the search key 32 into the given tree.

C) Show the resulting tree after inserting the search key 32, and then deleting the key 64 from the given tree.

D) Show the resulting tree after deleting the search key 64, and then inserting the key 32 into the given tree.

Question 2.

Use extendible hashing with the initial hash function h(x) = x mod 4 and a bucket size of 3 to create an index on a relation with the following search keys:

2, 3, 5, 7, 11, 17, 19, 23, 29, 31

A) Show the final directory and data pages after inserting the given keys.

B) Show the result of deleting 11 from the hash index that you derived in part A.

C) Show the result of deleting 31 from the hash index that you derived in part A.

D) Show the result of inserting 1 into the hash index that you derived in part A.

E) Show the result of inserting 15 into the hash index that you derived in part A.

Question 3.

The following query finds those actors who played a title role in a movie that was made since 2003.

SELECT A.name,M.title
FROM Actors A, Casts C, Movies M 
WHERE A.aid=C.aid AND C.mid=M.mid AND C.role=M.title AND year > 2003;

This query can be evaluated using any of the following evaluation plans:

The Actors relation occupies 100 pages, the Casts relation occupies 250 pages, and the Movies relation occupies 50 pages. The catalog maintains statistics for the year field of the movie relation. In particular, the minimum value is 1914 and the maximum value is 2005.

A) Assume there are no indices. Estimate the number of blocks read for each of the three given plans using simple nested loops.

B) Estimate the number of blocks read for each of the plans using Sort-Merge-Joins (once again assuming no indices).

C) Estimate the number of blocks read for each plan if one takes advantage of a hash index built over the mid attribute of the Casts relation.

Question 4.

Suppose you have a file with 20,000 pages and you have five buffer pages. Answer the following questions for given scenario, assuming that the most general external sorting algorithm is used:

A) How many runs will you produce in the first pass?

B) How many passes will it take to sort the file completely?

C) What is the total I/O cost of sorting the file?

D) How many buffer pages would be needed to sort the file completely in just two passes?