 Database Systems: The Complete
Book
 Solutions for Chapter 12 

Solutions for Section 12.2
Solutions for Section 12.3
Solutions for Section 12.4
Solutions for Section 12.5
Solutions for Section 12.2
Exercise 12.2.1
SQL dates require 10 bytes, and SQL times require 8
bytes if there is no decimal point (See Section 12.1.3).
 a)

The bytes required by each of the fields is 15 + 2 + 10 + 8 = 35.
 b)

Round each of the four field lengths up to a multiple of 4, to get
16 + 4 + 12 + 8 = 40.
 c)
Round up again, to a multiple of 8, to get 16 + 8 + 16 + 8 = 48.
Exercise 12.2.3
The elements in the header also require rounding upward in (b) and (c).
Thus, the lengths including header fields and adding the lengths for the
bodies as calculated in Exercise 12.2.1 are:
 a)

4 + 4 + 1 + 35 = 44.
 b)

4 + 4 + 4 + 40 = 52.
 c)

8 + 8 + 8 + 48 = 72.
Exercise 12.2.5
For parts (a) and (b), the header takes 40 bytes, while for (c) it takes
80 bytes.
The calculations are thus:
 a)

(409640)/44 = 92.
 b)

(409640)/52 = 78.
 c)

(409680)/72 = 55.
Return to Top
Solutions for Section 12.3
Exercise 12.3.1
The Megatron 747 has 16,384 cylinders, so we require 2 bytes for the
cylinder.
There are 16 surfaces, or 16 tracks per cylinder, so 1 byte suffices for
the track.
The average number of sectors per track is 128, and we have typically
assumed
4 sectors per block (which is not a property of the disk itself).
If we used blocks consisting of a single sector, and the track with
the greatest number of sectors had more than 256, then we would need 2
bytes for the sector.
However, at 4 sectors/block, we could have wildly differing numbers of
sectors per track, and still not get close to 256 blocks/track.
Since 256 integers can be represented in 1 byte, we think that 1 byte
is sufficient for the block within a track, and we think the correct
answer is 4 bytes for the block address on a Megatron 747.
Exercise 12.3.3(a)
Assuming 16Kbyte blocks, we need another 2 bytes for the position
within a block, or 6 bytes total.
Exercise 12.3.7
On the first day, since the deletion occurs before any insertions, there
really isn't a deletion, and there are two records and two pointers, for
a total of 204 bytes (this number could be slightly higher if you make
the assumption that pointers must be aligned at a multiple of 4 or 8).
At each subsequent day, the deletion leaves a tombstone in the offset
table, but one of the 100byte record areas can be reused.
Thus, the space occupied grows by 104 bytes (one record area plus two
pointers).
On day 39, the requirement for space will exceed 4096.
We shall then require 204 + 38*104 = 4156 bytes and be unable to make
the second insertion.
Exercise 12.3.10
Suppose c is the cost of swizzling an individual pointer.
This question asks for what values of p is the cost of swizzling
fraction p of the pointers at cost c greater than swizzling them all at
cost c/2?
That is, pc > c/2, or p > 1/2.
Return to Top
Solutions for Section 12.4
Exercise 12.4.1
The fixedlength fields require 30 bytes.
For the variablelength fields we need in the header a record length and
pointers to all but the first of the three variablelength fields, or
another 12 bytes.
Thus, we need 42 bytes plus whatever space the variablelength fields
themselves take.
Exercise 12.4.2
The average name field takes 30 bytes, the average address 50 bytes, and
the average history 500 bytes.
Thus, the average length of a record is 42 + 30 + 50 + 500 = 622 bytes.
Exercise 12.4.5
To start, when r is much smaller than 1000, we can surely save by
utilizing the extra space in blocks for split records.
However, let's see how close to r = 1000 we can still save.
Without splitting records, we can only fit one record per block.
Thus, we can save if we can fit two fragments in less than 1000 bytes,
i.e., r + 2*16 < 1000, or r < 968.
To check, suppose r = 967.
Then the first record leaves 33 bytes, so we can take a 16byte fragment
header and 17 bytes of the next record, and put it in the first block.
That leaves 950 bytes plus a 16byte header for the next block, leaving
34 bytes.
Similarly, each split record leaves one more empty byte, until
eventually there are 967 bytes free on a block and we can slip an extra
record into an alreadyused block, thus saving (a very small amount of)
space.
Return to Top
Solutions for Section 12.5
Exercise 12.5.1(a)
Method (i) requires only one disk read if we know the proper block for a
record, while method (ii), with its addition of overflow blocks,
requires more than one read if the desired record is on an overflock
block.
Thus, (i) is ``better'' than (ii).
However, in the long run, (i) keeps blocks between full and halffull,
so the average space utilization will be 75%.
Method (ii) can keep all but the first block in a chain full, so for
long chains the space utilization of (ii) is better while its average
retrieval time goes down.
In addition, (i) requires more index entries, and thus eventually more
space for the index and more time to examine the index during each
record lookup.
Return to Top