Questions:

(Please submit your final exam in MS word and name your file with your name!)

A. Please answer the following questions as detailed as possible:

a. For a B-tree of order 4 consisting of 3 levels, what is the maximum amount of records which may be stored?

b. For a B+-tree of order 3 consisting of 3 levels for the index part, what is the maximum amount of records which may be stored assuming that a data block for data records can hold 100 of them?

c. A PARTS file with Part# as hash key includes records with the following Part# values: 2369, 3760, 4692, 4871, 5659, 1821, 1074, 7115, 1620, 2428, 3943, 4750, 6975, 4981, 9208. The file use eight buckets, number from 0 to 7. Each bucket is one disk block and holds two records. Load these records into the file in the given order, using the hashing function h(K) = K mod 8. Calculate the average number of block accesses for a random retrieval on Part#.

B. Given universal schema R(A,B,C,D,E,F,G,H,I} and a set of functional dependencies as follows:

AB → CD
A → E
B → FH
C → G
D → B
G → C
H → I

a. What is the key for the universal schema R?

b. What is the highest normal form of the universal schema R? Please explain.

c. If the universal schema R is not in 3NF (the third normal form), please make lossless join decomposition of schema R into a set of 3NF schemas with the property of functional dependency preservation.

d. List all the keys (include candidate keys) in all the schemas (tables) achieved in c.

e. List all the foreign keys in each schema (table) if any.

f. Prove that the decomposition in c. is lossless join decomposition.

g. Is the decomposition you have created a BCNF decomposition? (That is, is each of the schemas (tables) achieved in c. in BCNF?

C. Assume one file has r =106 records. Each record takes R = 100 bytes, of which 10 bytes are for the key of the record. Suppose the key values range from 1 through 1,000,000, inclusive. Assume the block size B is 1000 bytes for all files, and that an address (block pointer, tree node pointer, or data record pointer) takes 10 bytes.

1. Sequential file:
a. What is the blocking factor bfr for the file?
b. How many data blocks b are needed to hold records?
c. How many data blocks accesses on the average are needed to fetch a record by using linear search?
d. How many data blocks accesses are needed to fetch a record by using binary search?

2. Single Level Index:
e. What is the blocking factor bfri for the index?
f. How many index blocks bi are needed to build the single level primary index?
g. How many block accesses on the average are needed to fetch a record by using single level primary index and by doing linear search?
h. What is the least number of block accesses to fetch a record by using single level primary index?

3. Multilevel Index:
i. What is the fan-out value if multi-level index is used?
j. How many levels are there so that top level index fits on a single block in multilevel index?
k. How many block accesses are needed to fetch a record by using multilevel index?
l. What is the key value of the 4th index record on the top level, assuming each index record points to the record with the highest key value in a block of the next level down?

4. B+-tree Structure:
m. What is the order P of the B+-tree if B+-tree access structure on the key is constructed?
n. What is the number of leaf-level blocks needed if blocks are approximately 69% full (round up for convenience)?
o. What is the number of levels needed if internal nodes also 69% full (round up for convenience)?
p. What is the total number of blocks required by the B+-tree?
q. What is the number of block accesses needed to search for and retrieve a record from the file -- given its key value by using B+-tree?

D. Given the relational tables as follows:

SHIP(Shipname, Captain)
CREW(Crewname, Hometown, Shipname)
GROWS(Hometown, Flower)
ALLERGIES(Crewname, Flower)

Please use SQL statement to construct the following queries:
(You are not supposed to use any aggregation functions such as count(), sum(), etc.; you are assumed that you do not know the data values of Shipname, Captain, Crewname, Hometown, Flower, etc. in the database table when you query the database table).

a. For each crew, if the crew is allergic to no flowers that grow on his/her hometown, then list the crew's name.

b. For each crew, if the crew is allergic to all flowers that grow on his/her hometown, then list the crew's name.

c. For each crew, if the crew is allergic only to the flowers that grow on their hometown, then list the crew's name.

d. For each crew, if the crew is allergic to exactly the same flowers that his/her captain is allergic to, then list the crew's name.

E. Explain how functional dependencies can be used to indicate that:

a.) A one-to-one relationship set exists between entity sets advisor and student.

b.) A one-to-many relationship set exists between entity sets advisor and student.

F. Given the relational schema R, where X and Y are attribute sets such as: X ⊆ R and Y ⊆ R, please elaborate the meaning of the functional dependencies such as: Φ → Y and X → Φ.