CS336 - HOMEWORK 6 - Solved

1. Let T be Tripadvisor table with the following attributes. Each tuple represents one review of a restaurant by a user.

Restaurant

Address (of the restaurant)

Cuisine (what type of cuisine, offered, Italian, French etc)

Rating  (overall average rating of restaurant, say 4.56)

Rank  (what is the ranking of a given restaurant)

User_name   

#User_reviews  (total reviews by user by the date)

Date

Stars (stars that the user have in review)

 

Number of user reviews is computed per user till a given date which is also the date when the user awarded stars (1-5) to given restaurant. Thus, the number of user reviews changes with date.

 

a)      Identify all non-trivial functional dependencies for the scheme T

b)      Identify all keys of the table T

c)      Pre-process all dependencies.

d)      Is T in BCNF? If not, show BCNF decomposition using the BCNF decomposition algorithm from class.

e)      Using Chase algorithm show that the BCNF decomposition obtained in (d) is in fact lossless  

 

2.      Projection of functional dependencies

 

Let R(ABCDE) be a database scheme with the following functional dependencies F = {A->B, B->C, C->D, CD_>E  and D->A}

 

Project F onto ACD, by pre-processing F first and using the process described in class. Show the preprocessed dependencies and projected fds as well.

 

Is ACD in BCNF?  Justify your answer.

 

3.      Assume that A is the key of the relational scheme R(ABCDEF). How many superkeys will R(ABCDEF) have? Explain your answer

4.      Prove that each step of BCNF decomposition,  when a scheme R is decomposed into XY and R-Y (where X->Y violated BCNF) has lossless join property. Use Chase algorithm.

5.      In relation Sells(Bar, Beer, Price), lets assume that Beer is foreign key with the parent table being the table Beers.  Assume that DELETE CASCADE option has been selected for this foreign key. What will be the consequences of deleting a beer from the table Beers?  What are consequences of deleting a tuple from Sells?  What are possible scenarios following insertion of a tuple into Sells?  

 

6.      For each of the following schedules, state whether it is conflict-serializable. Draw Precedence Graph.  If  it is serializable, provide all equivalent serial schedules. If no, state why it is not conflict-serializable. (ri(X) denotes a read on object X for transaction Ti. wj(Y) denotes a write on object Y for transaction Tj.)  

a.          r1(X), r3(Y), r2(Y), w3(Y), r3(X), r2(Z), w1(X), w2(Z), r1(Z), w1(Z)

b.          r1(X), r2(Y), r3(Y), w3(Y), r2(Z), w1(X), r3(X), r1(Z), w2(Z), w1(Z)  

c.          r1(X), w1(X), r3(Y), r1(Z), w3(Y), r2(Y), r2(Z), r3(X), w1(Z), w2(Z)

d.          w1(X), r3(Y)), r1(Z), w3(Y), r2(Y), r2(Z), r3(X), w2(Z), w2(Y), w1(Z)