University of Toronto CSC343 Winter 2021
In-class Exercises: BCNF
1. FD recap.
(a) Create an instance of relation R(A, B, C, D, E) that violates this functional dependency: ABC ¡ú DE.
Solutions: Here is one example
ABCDE a1 b1 c1 d1 e1 a1 b1 c1 d1 e2
(b) Suppose we have a relation R(A, B, C, D, E). Does the instance below violate the functional dependency DB ¡ú A?
ABCDE 53216 53312 58415
No.
2. Is a relation in BCNF?
(a) Suppose we have a relation Students(SID, email, course, term, prof), and that these FDs hold:
{ SID ¡ú email; course, term ¡ú prof; SID, course ¡ú grade. }. Is this relation in BCNF? Solution: No. SID+ = {SID, email} which is not all the attributes.
(b) Suppose we have a relation Customers(name, DOB, address, favouriteCar, manufacturer) and these FDs hold: { name ¡ú DOB, favouriteCar; favouriteCar ¡ú manufacturer }. Is this relation in BCNF?
Solution: No. Calculate the closure of name to see that it is not all the attributes. name+ = {name,DOB,favouriteCar,manufacturer}. It does not include address.
(c) Suppose we have a relation Parts(part, manufacturer, seller, price) and these FDs hold: { part ¡ú manufacturer; part, seller ¡ú price }. Is this relation in BCNF?
Solution: No. part+ = {part, manuf acturer} which does not include seller or price.
(d) Suppose we have a relation R(A, B, C, D, E) and these FDs hold:
{B¡úAC; CB¡úE; A¡úD}. IsthisrelationinBCNF?
Solution: No. A+ = {A, D}which is not the whole set of attributes of R.
3. How does BCNF help? Consider again the relation relation Parts(part, manufacturer, seller, price) with these FDs: { part ¡ú manufacturer; part, seller ¡ú price }.
(a) Keeping in mind the FDs, make an instance of this relation that has redundant information.
Solution: Here is one of an infinite number of possibilities part manufacturer seller price
p1 man1 seller1 45.99 p1 man1 seller2 30.49
(b) If we applied the decomposition step from BCNF decomposition, what attributes would each of the new relations have?
Solution:
R1(part, manufacturer) and R2(part, seller, price)
(c) Project the FDs onto each of the new relations
Solution:
R projected onto R1: T = {part ¡ú manufacturer} R projected onto R2: T = {part, seller ¡ú price}
(d) Put the same data as in part (a) into your new schema. Is there any redundancy? Solution: Do this with your own data. Here is the solution for the example answer above.
part manufacturer p1 man1
part p1 p1
seller seller1 seller2
price 45.99 30.49
(e) Is it possible to create redundancy with this new schema? Solution: No.