CS 4347 — Database Systems, Homework 5

Download PDF

What is the difference between extendible and dynamic hashing? Provide an example to support your answer

In extendible hashing, the most significant bits of the hashed data are used as the index for storing the data. In this model, overflows of the hashed data are dealt with by splitting the bucket into two. In contrast, in dynamic hashing, the entirety of the hash value is used to position it within a tree structure . This means that there are no splitting or merging operations.

For example, imagine hash values and . In dynamic hashing, there is never a hash collision. In contrast, with extendible hashing, if the local depth starts at , after the insertion of , the index containing must be split before is inserted. This guarantees no space is wasted.

What are the differences among primary, secondary, and clustering indexes? Which of the indexes are dense, and which are not?

A primary index is a file consisting of two attributes: A primary key (of the same data type as the ordering field) and a pointer to a disk block. Primary indices are sparse. A clustering index is used for speeding up access to records for a certain field. This is a dense index, since all possible values for the field are reserved in memory. A secondary key is used as a secondary means of accessing a record. This is similar, but distinct from a primary key, since it is based on a nonordering field of the records. This is also a unique key (and thus a candidate key). This index is dense.

Consider the following relation instance

xyz
t1142
t2153
t3153
t4322
t5156

Which of the following functional dependencies may exist in the above relation instance? If the functional dependency cannot hold, specify the tuples that cause the violation.

The functional dependency cannot hold, becuase and conflict with

This functional dependency may hold

This functional dependency may hold

This functional dependcy many not hold conflict with each other. Although do not conflict

This funcitonal dependency may hold

Given the relation schema with key and the following set of functional dependencies, . Is R in the second normal form? Explain your answer, if yes explain way, if not explain why and normalize it to the second normal form.

No, because is a partial dependency. So we must now split this into two relations to normalize it

Given the relation schema with key and the following functional dependencies, Is R in the third normal form? Explain your answer. If not, explain why and normalize it to the second normal form.

This is not in the third normal form because are both transitive dependencies. To fix this, we must make new relations