Exercise 3.1.1
Answers for this exercise may vary because of different interpretations.
Some possible FDs: Social Security number ? name Area code ? state Street address, city, state ? zipcode
Possible keys: {Social Security number, street address, city, state, area code, phone number}
Need street address, city, state to uniquely determine location. A person could have multiple addresses. The same is true for phones. These days, a person could have a landline and a cellular phone
Exercise 3.1.2
Answers for this exercise may vary because of different interpretations
Some possible FDs: ID ? x-position, y-position, z-position ID ? x-velocity, y-velocity, z-velocity x-position, y-position, z-position ? ID
Possible keys: {ID} {x-position, y-position, z-position}
The reason why the positions would be a key is no two molecules can occupy the same point.
Exercise 3.1.3a
(n-1)
The superkeys are any subset that contains A1. Thus, there are 2 such subsets, since each of the n-1 attributes A2 through An may independently be chosen in or out.
Exercise 3.1.3b
(n-1)
The superkeys are any subset that contains A1 or A2. There are 2 such subsets when
(n-2)
considering A1 and the n-1 attributes A2 through An. There are 2 such subsets when considering A2 and the n-2 attributes A3 through An. We do not count A1 in these subsets because they are already counted in the first group of subsets. The total number of
(n-1) (n-2)
subsets is 2+ 2.
Exercise 3.1.3c
The superkeys are any subset that contains {A1,A2} or {A3,A4}. There are 2 such subsets
(n-2) (n-4)
when considering {A1,A2} and the n-2 attributes A3 through An. There are 2– 2 such subsets when considering {A3,A4} and attributes A5 through An along with the individual
(n-4)
attributes A1 and A2. We get the 2 term because we have to discard the subsets that
(n-2)
contain the key {A1,A2} to avoid double counting. The total number of subsets is 2 + (n-2) (n-4)2– 2.
Exercise 3.1.3d
(n-2)
The superkeys are any subset that contains {A1,A2} or {A1,A3}. There are 2 such subsets
(n-3)
when considering {A1,A2} and the n-2 attributes A3 through An. There are 2 such subsets when considering {A1,A3} and the n-3 attributes A4 through An We do not count A2 in these subsets because they are already counted in the first group of subsets. The total number
(n-2)(n-3)
of subsets is 2 + 2.
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 only new dependency we get with a single attribute on the left is C?A.
Now consider pairs of attributes:
+++
{AB} = ABCD, so we get new dependency AB?D. {AC} = ACD, and AC?D is nontrivial. {AD}
++
= AD, so nothing new. {BC} = ABCD, so we get BC?A, and BC?D. {BD} = ABCD, giving us
+
BD?A and BD?C. {CD} = ACD, giving CD?A.
+
For the triples of attributes, {ACD} = ACD, but the closures of the other sets are each ABCD. Thus, we get new dependencies ABC?D, ABD?C, and BCD?A.
+
Since {ABCD} = ABCD, we get no new dependencies.
The collection of 11 new dependencies mentioned above are:
C?A, AB?D, AC?D, BC?A, BC?D, BD?A, BD?C, CD?A, ABC?D, ABD?C, and BCD?A.
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
The superkeys are all those that contain one of those three keys. That is, a superkey that is not a key must contain B and more than one of A, C, and D. Thus, the (proper) superkeys are ABC, ABD, BCD, and ABCD.
(n-2)
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} = CD. Thus the new dependencies are AB?C, AB?D, AC?B, AC?D, AD?B, AD?C, BC?D and BD?C.
+
For the triples of attributes, {BCD} = BCD, but the closures of the other sets are each ABCD. Thus, we get new dependencies ABC?D, ABD?C, and ACD?B.
+
Since {ABCD} = ABCD, we get no new dependencies.
The collection of 13 new dependencies mentioned above are:
A?C, A?D, AB?C, AB?D, AC?B, AC?D, AD?B, AD?C, BC?D, BD?C, ABC?D, ABD?C and ACD?B.
++++
ii) For the single attributes we have {A} = A, {B} = B, {C} = C, and {D} = D. Thus, there are no new dependencies.
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.
+
Since {ABCD} = ABCD, we get no new dependencies.
The collection of 8 new dependencies mentioned above are: AB?D, AD?C, BC?A, CD?B, ABC?D, ABD?C, ACD?B and BCD?A.
++++
iii) For the single attributes we have {A} = ABCD, {B} = ABCD, {C} = ABCD, and {D} = ABCD. Thus, the new dependencies are A?C, A?D, B?D, B?A, C?A, C?B, D?B and D?C.
Since all the single attributes’ closures are ABCD, any superset of the single
attributes will also lead to a closure of ABCD. Knowing this, we can enumerate the rest of the new dependencies.
The collection of 24 new dependencies mentioned above are:
A?C, A?D, B?D, B?A, C?A, C?B, D?B, D?C, AB?C, AB?D, AC?B, AC?D, AD?B, AD?C, BC?A, BC?D, BD?A, BD?C, CD?A, CD?B, ABC?D, ABD?C, ACD?B and BCD?A.
Exercise 3.2.2b