Consider the expression

Question

Suppose that there are the following access paths:

(a) An unclustered hash index on StudId

(b) An unclustered hash index on Semester

(c) An unclustered hash index on Grade



Which of these access paths has the best selectivity and which has the worst? Compare the selectivity of the worst access path (among the above three) to the selectivity of the file scan.

Answer 1

With the unclustered hash index on StudId, we will nd exactly the bucket that contains all the transcript records for student with the Id 666666666. Since the index is unclustered, this access method will fetch (in the worst case) as many pages as the number of transcript records for that student. In our sample relation in Figure 4.5, this would be 3 pages. In a typical university, an undergraduate student would have to earn 120-150 credits. With 3 credits per course it would make 40-50 transcript records and, thus, the selectivity would be this many pages of data.

With the unclustered hash index on Semester, we jump to the bucket for the transcript records in the F1995 semester and then we need to fetch all these records from the disk to check the other conditions. In a university with enrollment 20,000, selectivity of this access path can be as high as that. In our sample database, however, there are only two transcript records for Fall 1995.

With the unclustered hash index on Grade, we get into the bucket of the transcript records where the student received the grade A. If only 10% of the students get an A, the bucket woud hold 2,000 records per semester. In 20 years (2 semesters a year), the university might accumulate as many as 80,000 transcript records in that bucket. In our sample database, we have 5 transcript records where the student got an A.

Thus, in a typical university, the third access path has the worst selectivity and the rst has the best. In the sample database of Figure 4.5, the second method has the best selectivity and the third the worst.