HW #1

HW #3 Answer Key

Points: Total 20

11.6 2

11.10 2

12.1 2

12.2 3

12.3 1

12.4 1

12.5 3

12.7 6

#11.6

Given the relational algebra expression borrower |X| customer for both examples:

a) MRU is preferable to LRU:

Suppose the join must be computed systematically without benefit of any sorting on the joining attribute.
Using a nested-loop strategy (pinning the active block in the outer loop) is an effective way to compute the join
For nested-loops joining on unsorted attributes MRU is more efficient than LRU.

b) LRU is preferable to MRU:

Suppose both relations are sorted on the joining attribute, with multiple tuples having the same value.
The most effective join on sorted relations is to run down both relations concurrently in a merge operation, with one page of each relation active at once.
When multiple tuples may have the same value it may be necessary to backtrack slightly when computing the join; the farther back (older) a page in the buffer is, the less likely it will be needed later on. As a result, LRU is more efficient than MRU for this operation.

#11.10 Give an example of a database application in which the pointer method of representing variable-length records is preferable to the reserved-space method. Explain your answer.

Answer:

Suppose we are trying to represent a record in which there is a variable-length field whose size can vary widely. Most tuples have a relatively small length in this field, but some can be quite large. For example, a geneological database where the "person" record includes a "cousin" field, with a 20-character name for each first cousin. Some people (whose parents are both only-children) will have zero first cousins; others (where both parents were part of large families, and all the uncles and aunts married and had large families) might have as many as forty or fifty first cousins.

If we want to store these records using the reserved-space method we would have to determine a maximum number of first-cousins (say 80 or 100), and each record would take up space accordingly. This is very inefficient, since in practice most people have ten or fewer first cousins, and the space for the unused 90 first-cousin names is entirely wasted.

If we store these records using a pointer method we will avoid the wasted space.

Key parts of the answer:

Variable length record with maximum size much larger than common size
Wasted space

Another common answer received had to do with the issues of joining on an attribute that is held within an anchor block of a pointer-method representation rather than joining on an attribute held in the linked list part, and the relative speed advantage of such joins over joins on the same attributes in fixed-size records. This answer is weaker, and was often poorly stated on the homework; unless the anchor-block join advantage was accurately stated I gave only 1 point for such answers.

#12.1

When is it preferable to use a dense index instead of a sparse index? Explain your answer.

A dense index is necessary when the file is not sorted on the search key field of the index (such as with a secondary index). A dense index may also be desirable if the index file is small compared to the size of memory (so the whole index can fit in relatively few disk pages, or in main memory).

#12.2

Since indices speed query processing, why might they not be kept on several search keys? List as many reasons as possible.

Insert/Delete overhead -- every index must be updated to reflect insertions and deletions; the more indices, the greater burden on each update
Update overhead -- updates (modifying an attribute value in an existing record) usually do not modify the primary key attributes, but if they modify an attribute used as the search key for a secondary index, that particular index must be modified
Space. Each index requires more space; secondary indices are dense indices and may be quite large.
Limited returns. Queries with conditions on several search keys can often be computed efficiently even if only some of the keys have indices on them. As such, adding additional indices will improve performance less and less as more indices already exist
Limited returns (2). Some queries are common; others are rare. Having indices to speed the common queries is useful. After the common search keys are indexed, adding indices to support the less common search attributes is less useful.

There were other possible answers as well; I gave credit for up to 3 correct answers. No credit was subtracted for wrong answers, although they may have been marked with an X

#12.3

What is the difference between a primary index and a secondary index?

The primary index is sorted in the same order as the file. A secondary index is sorted (ordered) in a different order as the file. There can be only one primary index; there may be multiple secondary indices.

#12.4

Is it possible in general to have two primary indices on the same relation for different search keys? Explain.

In general, no. If there is only one copy of the file, then there is only one order that it can be stored on disk, and therefore only one primary index. There are two unique circumstances where we could have two primary indices:

It is possible to have two primary indices on the same relation if we stored the whole relation twice -- one copy sorted in one order, and a second copy stored in another order. But that isn't a good tactic for a centralized system

It is also possible that two attributes have related values, similar (but not the same as) a functional dependency: if A, B are attributes in relation R and R is sorted on A to get a sequence 1…n, if Ai > Aj then Bi>Bj for all i,j. In that particular (very rare) case, it would be possible to have two primary indices, because sorting R on A would also cause R to be sorted on B.

Answers that simply said "No" were given full credit, because that is the heart of the matter, in spite of the two weird contrary examples. Answers that listed one of the two possible ways that it was possible were given full credit also.

#12.5 and #12.7

Three very important points:

These are B+-trees. That means every value must appear at the leaf-node level. If you created a tree that had some values only on interior nodes, that is a B-tree.
A B+-tree is balanced. Every path from the root to a leaf is the same length. If deletion causes your tree to look otherwise, you didn't handle it correctly.
Read the question carefully. 4 pointers stored in a node is not the same as 4 search-key values stored in a node.

Grading:

A properly constructed B+-tree in 12.5 was worth 1 pt, regardless of whether you computed its shape using split-merge with a sibling node on overflow or simply splitting.

In question 12.7, doing the 4-pointer tree correctly was worth 2 pts, similarly for the 6-pointer and 8-pointer trees. This was reduced to 1 pt if there was a minor error; 0 pts if there were several minor errors or a major error.

#12.5

Using the data (2, 3, 5, 7, 11, 17, 19, 23, 31)

Construct B+-trees where the following number of pointers will fit in one node:

(note: the following trees were constructed allowing shuffling of values with one adjacent leaf node to reduce the number of splits required. Answers that do not account for shuffling are also valid for this question)

a) 4