University of Toronto CSC343 Winter 2021
In-class Exercises: Properties of Decompositions
1. A lossy join decomposition. Suppose we have a relation with attributes cdf, name, grade. Here is an instance of that relation:
(a) Suppose we were to decompose this into two new relations: R1(cdf, name) and R2(name, grade). Project the data onto those two new relations.
R1: R2:
(b) Now compute R1 ◃▹ R2 to rebuild the original table.
cdf
name
grade
g3tout g4foobar c0zhang
Amy David David
91 78 85
cdf
name
name
grade
cdf
name
grade
(c) What was lost?
Solution: The rebuilt table has 5 rows. New rows are in bold. We have lost the information that the grade of 78 is for g4foobar and the grade of 85 is for c0zhang.
cdf
name
grade
g3tout g4foobar c0zhang g4foobar c0zhang
Amy David David David David
91 78 85 85 78
2. A decomposition that fails to preserve dependencies [Example 3.25 from the text.] Suppose we have a relation with attributes movie, theatre, city and FDs { theatre → city; movie, city → theatre }. The FD theatre → city violates BCNF, and applying the BCNF decomposition algorithm, we get two new relations:
• R1(theatre, city) with one FD: theatre → city
• R2(theatre, movie) with no FDs
(a) Create small instances of R1 and R2 that satisfy their own FDs, but when natural-joined together, violate one of the original FDs.
Solution: Here is one example answer.
R1: R2:
theatre
city
Kingsway Theatre Varsity Cinema
Toronto Toronto
theatre
movie
Kingsway Theatre Varsity Cinema
The Matrix The Matrix
theatre
city
movie
Kingsway Theatre Varsity Cinema
Toronto Toronto
The Matrix The Matrix
R1 ◃▹ R2:
(b) In the original relation, with attributes movie, theatre, city, does the functional dependency theatre → city violate 3NF?
Solution:
No, city is part of the key (city, movie).
(c) In the original relation, with attributes movie, theatre, city, does the functional dependency theatre → city violate BCNF?
Solution:
Yes, because theatre is not a key. It does not functionally determine movie.