University of Toronto CSC343 Winter 2021
In-class Exercises: The Chase Test
Throughout these solutions, I use boldface letters to show values whose presence we can infer from the structure of the decomposition, and non-boldface letters to show values whose presence we can then infer from the FDs.
1. Suppose we have a relation on attributes NFLCG with these FDs: N → FL,NC → G
(a) Suppose we decompose into relations NF, FLC and LCG. Use the Chase Test to determine whether this is a lossless-join decomposition.
Solution: The following valid instance of the relation demonstrates that it is not a lossless-join decomposition. If we choose n2 ̸= n3 ̸= n ̸= n2, then both of the FDs are respected. If we also choose l1 ̸= l,c1 ̸= c,g1 ̸= g, then none of the tuples is < n,f,l,c,g >
NFLCG n f l1 c1 g1 n2 f l c g2
n3 f3 l c g
If we were to project this instance onto the relations NF, FLC and LCG and then natural join the results back
together, the result would include the spurious tuple < n, f, l, c, g >, which does not appear above.
(b) Suppose we decompose into relations NF, NL and NCG. Use the Chase Test to determine whether this is a lossless-join decomposition.
Solution: The chase test demonstrates that it is a lossless-join decomposition:
NFLCG n f l c1 g1 n f l c2 g2 nflcg
(c) Suppose we decompose into relations NFC, and NLG. Use the Chase Test to determine whether this is a lossless- join decomposition.
Solution: The following valid instance of the relation demonstrates that it is not a lossless-join decomposition. Provided we choose c2 ̸= c and g1 ̸= g, then both FDs are respected, but no row contains < n, f, l, c, g >:
NFLCG n f l c g1 n f l c2 g
2. Suppose we have a relation on attributes ABCDEF and it is to be decomposed into relations ABCD and DEF. (a) Invent a set of FDs that would make this a lossless-join decomposition.
Solution: There are many solutions to this question. A simple solution is the single functional dependency D → ABC. The set of functional dependencies
D→BF, F→C, BC→A
is a more complicated solution.
(b) Invent a set of three FDs that would make this is a lossy-join decomposition.
Solution: Again, there are many solutions to this question. The simplest is just the empty set. It is perhaps
more fun to come up with a solution that has a bunch of FDs. The set
D→AB, E→C, F→EA
is one such solution.
(c) If there were no FDs at all, is it possible that the decomposition is lossless?
Solution: This particular decomposition is lossy if there are no functional dependencies. And in fact this holds for any non-trivial decomposition, that is, any decomposition into 2 or more relations, none of which includes all the attributes of the original relation.
Important: In practise, one never invents FDs! They are facts about the domain that either hold or don’t hold. So this question is completely unrealistic, but if you can solve it, you really understand the Chase Test.