Ungraded Homework COSC 6340 (Dr. Eick)

Due Th., March 23, noon

Look at 6340-homepage for further instructions
last updated: Tu., March 21, 9a

Problem1
Consider a relation R(a,b,c,d,e) with FD's: ab->c, bc->d, e->ad, d->b, and cd->e

(a): Find all the candidate keys for R.
(b): How many superkeys are there (including the keys)? Explain your reasoning for partial credit.
(c): Which of the given FD's violates BCNF?
(d): 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.

Problem 2
Suppose we have a relation schema ABCD and the dependencies A->->B and B->C (i.e., A multidetermines B, while B functionally determines C). Which of the following dependencies must hold? For each, either give a reason why, or give a counterexample relation instance for ABCD.

(a): B->->AD
(b): A->->C
(c): B->->D

Problem 3
Assume that the following relation person(ssn, name, address, phone-nr, father, mother) is given. Additionally, you can assume that persons have a unique and non-optional ssn and that persons have one address, one name, but might have several phone numbers. Furthermore, man (woman) might have children with several women (men). Moreover, different persons might live at the same address.
Write down all functional dependencies that hold for the relation person. What is/are the candidate key(s) of relation person?

Problem 4
Exercise 12.4 from page 356 of our textbook

Problem 5
Assume a relation R(A,B,C) is stored using unordered file organization. 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. Moreover, we assume that node pointer require 2 byte of storage and index pointer require 4 byte of storage. How many block accesses are needed for the following queries:


(Q1) Select A
     from R
     where B=34 returns 12 answers at an average

(Q2) Select A
     from R
     where B>17 returns 300 answers at an average

assuming that

a hashed index on attribute B is used that is implemented with static hashing, and buckets of the hashtable are assumed to be 80% filled.
a B+ tree index on atttribute B is used.

Compute the number of block accesses of the best implementation as precisely as possible!

Problem 6
Problem 16.3 of our textbook

Problem 7
Your instructor made at least one incorrect statement in the March 7 class. What is the incorrect statement. If you think you know what the incorrect statement is, correct it and prove that the corrected statement is true.