Exam1COSC 6340 (Data Management)March 30, 2000Your Name:Your SSN:I agree that my grades are posted using the last 4 digits of my ssn………………….(signature, if you like us to post your grades)Problem 1 [18]:Problem 2 [14]:Problem 3 [15]: Problem 4 [18]:Problem 5 [7]:Problem 6 [8]::Grade:The exam is “open books” and you have 75 minutes to complete the exam. The exam is slightly too long; I expect you to complete 85-90% of the problems in the available time.11) Relational Database Design [18]Consider the following relation R(A,B,C,D,E) with the following functional dependencies is given ( denotes a functional dependency):(1) CDE  A(2) DE  B(3) AB  C(4) B  EWhat is (are) the candidate key(s) of R? [5]Is R in BCNF? If not, which functional dependencies are bad (violate BCNF)? [2]Transform the relational schema into a relational schema that is in BCNF and does not have any lost dependencies; if this is not possible decompose R into a schema that is in BCNF and has the fewest number of lost functional dependencies. [11]22) Multi-valued Dependencies and 4th Normalform [14]a) Assume the following relation R(A,B,C,D) is given and the following multivalued dependencies hold: A B and B C Assume the relation R contains the following two tuples R(A B C D) (1 2 3 4) … (1 2 5 3) …What other tuples must R contain so that A B and B C hold for R (said differently, give an example of a relational relation that contains the two tuples and does not violate the two multi-valued dependencies). [7]Assuming that the two multivalued dependencies hold; does also B AD hold? Give reasons for your answer! [3]b) Why is it desirable that a relation is in 4th normalform and not only in BCNF? What problems are avoided when a relation is in 4th normalform. [4]33) B+-Trees & Cost Prediction [15]Assume a relation R(A,B,C) is stored using a B+-tree using attribute A as the search key of the B+-tree (the intermediate nodes only contain attribute A and node pointers, whereas the leafs contain the tuples of the relation). A is R's primary key. Attribute A requires 4 Byte of storage, attribute B requires 4 Byte of storage and attribute C requires 8 byte of storage; R contains 100000 tuples and we assume that one block can store 4096 Byte. a. What parameters p and m would be chosen for the B+-tree and what will be the height of the B+-tree assuming that each node of the tree are filled 2/3 (66.7%)? Give reasons for your answer! [6]b. Now assume that the following query Q1 is given that returns 1111 answers: Select B, C from R where A>23 Compute the number of block accesses of the best implementation of the query as precisely as possible, and explain your computations! [6]c. Now assume that we store R as an unordered file. Is it possible to speed up Q1 by creating a B+-tree index on A? Give reasons for your answer! [3]44) Implementing Joins [18]Assume we have to implement a natural join between two relations R1(A, B, C) and R2(A, D). A is the primary key for R1 and A is also the primary key for R2. R1 contains100000 tuples that are stored in 2000 blocks, and R2 has 200000 tuples stored in 1000 blocks; blocks are assumed to be 100% full. At an average the answer relation contains only 10 tuples; that is, very few A-values occur in both relations. Moreover, assume that only a small buffer size of 12 blocks is available. Based on these assumptions answer the following questions (indicate, if you assume in your computations that the output relationis written back to disk or not): a. What are the cost for implementing the join using the block-nested loop join? What relation would you choose as the outer relation? [3]b. Is it possible to implement the basic block-nested loop join more intelligently taking advantage of the fact that the join attribute is a primary key in both relations? What are the cost of your "more intelligent" implementation? [4]c. Now assume that either a hashed index on A of R1 or a hashed index on A of R2 is available. Is it possible to speed up the join implementation using this index (compute thecost, if an index is used!)? [4]d. Is it possible to apply the hash-join in this case (explain your answer!)? [2]e. Now assume that relation R1 and R2 are both stored as a B+-tree using A as the key (with no additional index structures). How would you implement the join in this case? How many block access does the best implementation of the query take in this case (assume that the B+ has height 4 for both relations and that leafs are 80% full)? [5]55) XML [7]What is XML? How is it different from HTML? What can it be used for and why is it important?6) Extendible Hashing [8]Turn your attention to page 282 of our textbook. Assume that keys 20, 64, 128, 256, and 9 are inserted into the hash-table of Fig. 10.4. How does the hash-table look like after the insertions?