Explain what are bitmap indexes, under what circumstances they are used, and what advantages they yield.

Question #1
Consider the relationship R(ABCDEF) with functional dependencies
F = { BD -> CE , BE -> A , BA->DF , EF -> D }.
(a) What normal form is this relationship in?
(b) A friend of you claims that the following set of relations is a lossless join decomposition of R with functional dependencies F:
S1(BCD), S2(BDE), S3(BEA), S4(BAD), S5(BAF)
You are a bit suspicious, since EF -> D is missing. Determine whether the
decomposition is indeed lossless join or not.
Question #2
Consider the relation R(ABCDE) and the set of functional dependencies F over R:
F = { AC -> DE , BC -> AD , DA -> BE , DE -> CA ,
BD -> A }.
(a) Find a minimal cover (basis) for F. Show the steps involved in arriving at your
answer.
(b) List all the candidate keys for F.
(c) Obtain a (lossless join) 3NF decomposition of R.
Question #3
Consider the following set of FDs on R(ABCDEFG) :
FDs= { AC -> BE ;
AF -> CDG ;
B -> DG;
CG -> BEF;
E -> ABF; }
R(ABCDEFG) has the following candidate keys: AC, AF, BC, CG, E.
(a) Find a lossless-join BCNF decomposition of this schema.
(b) Is your BCNF decomposition dependency preserving? Explain.

Question #4
For the extensible hashing mechanism, we usually use leftmost i bits of the binary sequence corresponding to the hash value produced by the underlying hash function to determine the placement of records in buckets. For example, the leftmost 2 bits of the binary sequence 11001 are 11. Alternatively, we could use rightmost i bits of the binary sequence corresponding to the hash value produced by the underlying hash function to determine the placement of records in buckets. For example, the rightmost 2 bits of the binary sequence 11001 are 01. In the following, assume that we use the rightmost i bits of the binary sequence to determine the placement of records. Further, assume that for simplicity, h(k) = k is the hash function and that each bucket can hold up to four records. Given the extensible hash structure depicted below as the base, show the final extensible hash structure after a sequence of six records with the following key values are inserted in the order shown. (Note that you only need to show the final result, not the intermediate results after each individual insertion.)
a) 11 (1011)
b) 11 (1011)
c) 8 (1000)
d) 3 (0011)
e) 13 (1101)
f) 9 (1001)

Question #7-a Explain what are bitmap indexes, under what circumstances they are used, and what advantages they yield.
Question #7-b Identify two drawbacks associated with using an index.