Database Systems: The Complete Book Solutions for Chapter 14

Solutions for Section 14.1
Solutions for Section 14.2
Solutions for Section 14.3
Solutions for Section 14.4

Solutions for Section 14.1

Exercise 14.1.1(a)

     SELECT id
     FROM Rectangles
     WHERE xur >= 10.0 AND yur >= 20.0 AND
           xll <= 40.0 AND yll <= 30.0;

Exercise 14.1.2(a)

     SELECT color, COUNT(*)
     FROM Sales
     WHERE item = 'shirt'
     GROUP BY color
     HAVING COUT(*) > 1000;

Exercise 14.1.4

Because the data file is assumed sorted by x, the pointers in the intersection, of which there are n^2/1,000,000, are spread over fraction n/1000 of the blocks of the data file or 10n blocks. Thus, the total number of block accesses is 20n+2.

This number can be mor or less than reading all 10,000 data blocks. It is less, and therefore offers an advantage over a scan of the entire data file, if n < 500.

Exercise 14.1.5(a)

There is a useful approximation for small x, that (1-x)^{a/x} = e^{-a}. Thus, the approximate probability of failure is e^{-pi*d^2}, and the probability of success, i.e., that we shall find a point within radius d is 1 - e^{-pi*d^2}.

Return to Top

Solutions for Section 14.2

Exercise 14.2.1(a)

Exercise 14.2.4(a)

Exercise 14.2.5(b)

Exercise 14.2.6(a)

Exercise 14.2.9

Interestingly if we ignore the ceiling function, then the product of buckets per query and blocks per bucket is about 25, independent of m. However, because of the ceiling, we can never do this well. First, it doesn't make sense to pick m below 10, because the ceiling function tells us that we shall still require one block per bucket, no matter how small we make m.

At m = 10, the product is one block per bucket times 36 buckets/query = 36. We cannot do better than 36 by increasing m. To see why, remove the ceiling function to get a lower bound on the number of blocks per query: (m^2/100)(50/m + 1)^2 = 25 + m + m^2/100. Since m >= 10, the above expression is at least 36.

Thus, we conclude that m = 10, and 36 blocks per query is the best we can do.

Return to Top

Solutions for Section 14.3

Exercise 14.3.3(a)

For the index on x we need 10 first-level index blocks to hold all 100 values of x and their corresponding pointers to indexes on y. Thus, for x we need a second-level index with one block. Finding the y-index for the x-value x=C thus requires two disk I/O's.

Now, we must enter the y-index for this x-value. Since there are 100 y-values for each x-value, each y-index looks just like the x-index. We thus need two more disk I/O's to access the record with the proper x and y if there is one. If there is indeed a record with x=C and y=D, then a fifth disk I/O is needed to retrieve the z-value.

Exercise 14.3.5(a)

Exercise 14.3.10

Return to Top

Solutions for Section 14.4

Exercise 14.4.1(a)

Exercise 14.4.5(a)

Exercise 14.4.6

We must thus compare 2log_2n with k+p, since these are the multipliers of n in the formulas for space taken by bitmap indexes and B-trees, respectively. The contribution of k is a little tricky. If the key has many bits, but there are few different values of the key in the file (a common situation), then the space for listing the different key values in the bitmap index, which we ignored in Section 5.4.2, is much less than the space for representing keys in the B-tree. However, if the number of actual key-values in the file approximates the 2^k, then the term nk in the formula for B-tree space can be deleted, since to be fair we should have added the same term into the cost of the bitmap index.

Let us, to be conservative, compare only p with 2log_2n. If there are n records in the file, surely pointers must take at least log_2n bits. However, in practice, pointers must do more than distinguish among records of one file; they must distinguish locations on many disks, and therefore 32 bits is a minimum for pointers, with considerably higher values possible. If p = 32, then the bitmap index will take less space if 2log_2n < 32, or log_2n < 16, or n < 65,536.

Thus, for a reasonable sized file, the space required by the bitmap and B-tree are comparable under our assumptions above. The advantage goes to the bitmap index in a number of situations, including:

1. Pointers larger than 32 bits.

2. Keys require many bits, but the number of different key values is small.

There are a number of advantages to the B-tree, even when it takes more space, including the ability to handle range queries efficiently and the speed with which access to single records is provided.

Return to Top