CS336 - HOMEWORK 5 - Solved

1.Is the corona table from BarBeerDrinker database in BCNF?  

Yes/No?  Either way you have to prove your answer (BCNF or not) using nontrivial functional dependencies. If you find one dependency f which violates BCNF, you do not have to find other functional dependencies. But you have to prove that f violates BCNF.   Since there are so many attributes, you can group attributes, say into country attributes and corona stats and use notation X->Y where Y is a set of attributes. 

2. Is original TripAdvisor table that we used in class in BCNF?  

Yes/No? Either way you have to prove your answer (BCNF or not) using nontrivial functional dependencies.  In this case, since there are fewer attributes than for corona data set, you should find as many functional dependencies as you can (as long as they are not implied by these you found already).This is requested even if you find a functional dependency which violates BCNF. 

3) Write SQL query which will check if functional dependency  f= User -> User_reviews is satisfied by the table TripAdvisor. The query should return “Yes” if  f is satisfied, and  “No”  if f is violated in our Tripadvisor table instance. 

In case the functional dependency  f is violated,  write an SQL query which will return at least  two tuples in Trip Advisor table  which violate f– in other words, counterexample (it takes two tuples to demonstrate that fd is violated) 

4*.  Write SQL query which will verify if decomposition of table Sells from BarBeerDrinker database into two tables Sells1[Bar, Beer] and Sells2[Beer, Price]  is lossless.  

Sells1 and Sells2 are simple projections of Sell table onto their respective attribute sets. The query should return “Lossless” in case the decomposition is in fact lossless and “Lossy” if it is not. This check is performed against specific instance of Sells table which we have in our practice db. 

*) Extra credit 

 

THEORY
 

5)     Let R=ABCDEGHK and F= {ABK→C, A→DG, B→K, K→ADH, H→GE} .  

Is it in BCNF?  Prove your answer. 

 

6)     Let R(ABCDEFG) be a relation and F={A -> C, A-> D,  B->F, E->F, F->G} 

 

a.     Show example of lossless join decomposition of R into three tables R1, R2 and R3 and demonstrate that this decomposition is lossless using chase algorithm 

b.    Find one key for this scheme and prove that it is a key using closure algorithm and definition of a key. 

 

7)     Consider R = ABCDEG, with the set of
dependencies F={AB → D, AB → C, AC → E, B → D, BE → A, E → G}. Suppose we have decomposed it into relations with set of attributes R1={ABD}, R2={ACE}, R3={ADEG}. Show using chase algorithm if this decomposition has lossless join property. 

 

 

8)     Let R(ABCD)  be a relation and  F={A->B, C->D, BC->A}.   Apply chase algorithm to test if decomposition of R onto R1(AB), R2(AC), R3(BCD)  is lossless. 

 

9)     Let R(ABCDE)  be a relation and  F={A→B, BC→E, and ED →A}. Decompose R into BCNF using BCNF decomposition algorithm. Remember that you need to compute projections of F to check if the decomposed tables are in BCNF. 

 

10)           Let  R(ABCDEFGH) be a relation and F= {AB→E, C→D, D→E, FG→A}. Decompose R in BCNF using BCNF decomposition algorithm. Remember that you need to compute projections of F to check if the decomposed tables are in BCNF.   Using Chase algorithm demonstrate if the decomposition you obtained is in fact lossless.