Exercise 3.1.1
Answers for this exercise may vary because of different interpretations.
Some possible FDs:
Social Security number → name
Exercise 3.1.2
Answers for this exercise may vary because of different interpretations
Some possible FDs:
Exercise 3.1.3a
Exercise 3.1.3b
The superkeys are any subset that contains A1 or A2. There are 2(n–1) such subsets when
Exercise 3.1.3c
The superkeys are any subset that contains {A1,A2} or {A3,A4}. There are 2(n–2) such subsets
Exercise 3.1.3d
The superkeys are any subset that contains {A1,A2} or {A1,A3}. There are 2(n–2) such subsets
Exercise 3.2.1a
We could try inference rules to deduce new dependencies until we are satisfied we have them all.
A more systematic way is to consider the closures of all 15 nonempty sets of attributes.
For the single attributes we have {A}+ = A, {B}+ = B, {C}+ = ACD, and {D}+ = AD. Thus, the
Exercise 3.2.1b
From the analysis of closures above, we find that AB, BC, and BD are keys. All other sets either
do not have ABCD as the closure or contain one of these three sets.
Exercise 3.2.1c
Exercise 3.2.2a
i) For the single attributes we have {A}+ = ABCD, {B}+ = BCD, {C}+ = C, and {D}+ = D. Thus,
the new dependencies are A→C and A→D.
Now consider pairs of attributes:
{AB}+ = ABCD, {AC}+ = ABCD, {AD}+ = ABCD, {BC}+ = BCD, {BD}+ = BCD, {CD}+ =
Now consider pairs of attributes:
{AB}+ = ABCD, {AC}+ = AC, {AD}+ = ABCD, {BC}+ = ABCD, {BD}+ = BD, {CD}+ =
ABCD. Thus the new dependencies are AB→D, AD→C, BC→A and CD→B.
For the triples of attributes, all the closures of the sets are each ABCD. Thus, we get new
dependencies ABC→D, ABD→C, ACD→B and BCD→A.
Exercise 3.2.2b
i) From the analysis of closures in 3.2.2a(i), we find that the only key is A. All other sets either
Exercise 3.2.2c
i) The superkeys are all those sets that contain one of the keys in 3.2.2b(i). The superkeys are
Exercise 3.2.3a
Exercise 3.2.3b
From 3.2.3a, we know that A1A2…AnC→B. Using the concept of trivial dependencies, we can
show that A1A2…AnC→C. Thus A1A2…AnC→BC.
Exercise 3.2.3c
From A1A2…AnE1E2…Ej, we know that the closure contains B1B2…Bm because of the FD
Exercise 3.2.3d
Exercise 3.2.4a
Exercise 3.2.4b
Let attribute A represent Social Security Number, B represent gender and C represent name.
Exercise 3.2.4c
Exercise 3.2.5
Given a relation with attributes A1A2…An, we are told that there are no functional dependencies
Exercise 3.2.6
Let’s prove this by using the contrapositive. We wish to show that if X+ is not a subset of Y+,
then it must be that X is not a subset of Y.
Exercise 3.2.7
The algorithm to find X+ is outlined on pg. 76. Using that algorithm, we can prove that
Exercise 3.2.8a
If all sets of attributes are closed, then there cannot be any nontrivial functional dependencies.
Exercise 3.2.8b
If the only closed sets are ø and {A,B,C,D}, then the following FDs hold:
A→B A→C A→D
B→A B→C B→D
Exercise 3.2.8c
If the only closed sets are ø, {A,B} and {A,B,C,D}, then the following FDs hold:
A→B
B→A
Exercise 3.2.9
We can think of this problem as a situation where the attributes A,B,C represent cities and the
functional dependencies represent one way paths between the cities. The minimal bases are the
minimal number of pathways that are needed to connect the cities. We do not want to create
Exercise 3.2.10a
We need to compute the closures of all subsets of {ABC}, although there is no need to think
about the empty set or the set of all three attributes. Here are the calculations for the remaining
six sets:
Exercise 3.2.10b
We need to compute the closures of all subsets of {ABC}, although there is no need to think
about the empty set or the set of all three attributes. Here are the calculations for the remaining
Exercise 3.2.10c
We need to compute the closures of all subsets of {ABC}, although there is no need to think
about the empty set or the set of all three attributes. Here are the calculations for the remaining
Exercise 3.2.10d
We need to compute the closures of all subsets of {ABC}, although there is no need to think
about the empty set or the set of all three attributes. Here are the calculations for the remaining
Exercise 3.2.11
For step one of Algorithm 3.7, suppose we have the FD ABC→DE. We want to use Armstrong’s
Axioms to show that ABC→D and ABC→E follow. Surely the functional dependencies DE→D
and DE→E hold because they are trivial and follow the reflexivity property. Using the
Exercise 3.3.1a
In the solution to Exercise 3.2.1 we found that there are 14 nontrivial dependencies, including the
three given ones and eleven derived dependencies. They are: C→A, C→D, D→A, AB→D,
AB→ C, AC→D, BC→A, BC→D, BD→A, BD→C, CD→A, ABC→D, ABD→C, and
Exercise 3.3.1b
By computing the closures of all 15 nonempty subsets of ABCD, we can find all the nontrivial
FDs. They are B→C, B→D, AB→C, AB→D, BC→D, BD→C, ABC→D and ABD→C. From
Exercise 3.3.1c
In the solution to Exercise 3.2.2(ii), we found that there are 12 nontrivial dependencies, including
Exercise 3.3.1d
In the solution to Exercise 3.2.2(iii), we found that there are 28 nontrivial dependencies,
including the four given ones and the 24 derived ones. They are A→B, B→C, C→D, D→A,
Exercise 3.3.1e
By computing the closures of all 31 nonempty subsets of ABCDE, we can find all the nontrivial
FDs. They are AB→C, DE→C, B→D, AB→D, BC→D, BE→C, BE→D, ABC→D, ABD→C,
ABE→C, ABE→D, ADE→C, BCE→D, BDE→C, ABCE→D, and ABDE→C. From the
Exercise 3.3.1f
By computing the closures of all 31 nonempty subsets of ABCDE, we can find all the nontrivial
FDs. They are: C→B, C→D, C→E, D→B, D→E, AB→C, AB→D, AB→E, AC→B, AC→D,
AC→E, AD→B, AD→C, AD→E, BC→D, BC→E, BD→E, CD→B, CD→E, CE→B, CE→D,
Exercise 3.3.2
Yes, we will get the same result. Both A→B and A→BC have A on the left side and part of the
Exercise 3.3.3
Yes, we will still get the same result. Both A→B and A→BC have A on the left side and part of
Exercise 3.3.4
This is taken from Example 3.21 pg. 95.
Suppose that an instance of relation R only contains two tuples.
A
B
C
The projections of R onto the relations with schemas {A,B} and {B,C} are:
A
B
If we do a natural join on the two projections, we will get:
A
B
C
1
2
3
1
2
5
4
2
3
4
2
5
The result of the natural join is not equal to the original relation R.
Exercise 3.4.1a
This is the initial tableau:
A
B
C
D
E
a
b
c
d1
e1
a1
b
c
d
e1
a
b1
c
d1
e
This is the final tableau after applying FDs B→E and CE→A.
A
B
C
D
E
Since there is not an unsubscripted row, the decomposition for R is not lossless for this set of
FDs.
We can use the final tableau as an instance of R as an example for why the join is not lossless.
The projected relations are:
B
C
1
2
4
2
2
3
2
5
a
b1
c
B
C
D
The joined relation is:
A
B
C
D
E
a
b
c
d1
e1
a
b
c
d
e1
a
b1
c
d1
e1
a
b
c
d1
e
a
b
c
d
e
a
b1
c
d1
e
The joined relation has three more tuples than the original tableau.
Exercise 3.4.1b
This is the initial tableau:
A
B
C
D
E
a
b
c
d1
e1
a1
b
c
d
e1
a
b1
c
d1
e
This is the final tableau after applying FDs AC→E and BC→D
A
B
C
D
E
a
b
c
a1
b
c
d
e1
b
c
d1
b
c
d
b1
c
d1
A
C
E
a
c
e1
a
c
e
Exercise 3.4.1c
This is the initial tableau:
A
B
C
D
E
a
b
c
d1
e1
a1
b
c
d
e1
a
b1
c
d1
e
This is the final tableau after applying FDs A→D, D→E and B→D.
A
B
C
D
E
a
b
c
d
e
a1
b
c
d
e
a
b1
c
d
e
Exercise 3.4.1d
This is the initial tableau:
A
B
C
D
E
a
b
c
d1
e1
a1
b
c
d
e1
a
b1
c
d1
e
A
B
C
D
E
a
b
c
d
e
a1
b
c
d
e
a
b1
c
d
e
Exercise 3.4.2
When we decompose a relation into BCNF, we will project the FDs onto the decomposed
relations to get new sets of FDs. These dependencies are preserved if the union of these new sets
is equivalent to the original set of FDs.
Exercise 3.5.1a
In the solution to Exercise 3.3.1a we found that there are 14 nontrivial dependencies. They are:
Exercise 3.5.1b
In the solution to Exercise 3.3.1b we found that there are 8 nontrivial dependencies. They are
B→C, B→D, AB→C, AB→D, BC→D, BD→C, ABC→D and ABD→C.
Exercise 3.5.1c
In the solution to Exercise 3.3.1c we found that there are 12 nontrivial dependencies. They are
Exercise 3.5.1d
In the solution to Exercise 3.3.1d we found that there are 28 nontrivial dependencies. They are
Exercise 3.5.1e
In the solution to Exercise 3.3.1e we found that there are 16 nontrivial dependencies. They are
AB→C, DE→C, B→D, AB→D, BC→D, BE→C, BE→D, ABC→D, ABD→C, ABE→C,
Exercise 3.5.1f
In the solution to Exercise 3.3.1f we found that there are 41 nontrivial dependencies. They are: