[6.4)](b) Violates FDs (1), (2) and (4).

(d) Violates FD (4).

[6.6] We first consider FDs with a singleton attribute on the left. Because the D values are all different, we have D -> A, D -> B and D -> C; at the same time D is not Functonally Dependent on anything else since all other columns have at least two duplicate values: A -/-> D, B -/-> D, and C -/-> D are the FDs derived. Column B has two agreements on which C agrees, so B -> C, but A disagrees, so B -/-> A. Column A has a pair and a triple of rows in agreement, on which no other rows agree, so A -/-> B, A -/-> C , A -/-> D. Summarizing what we have so far:

A -/-> B	B -/-> A	C -/-> A	D -> A
A -/-> C	B -> C	C -> B	D -> B
A -/-> D	B -/-> D	C -/-> D	D -> C

 

Now we turn to FDs with pairs of attributes on the left. Any column paired with D disagrees on all rows, so DX -> A B C D for any X = A, B, or C. This is nothing new since it follows from the above FDs and augmentation. Pairs not including D are A B, B C, and A C. B C agrees on the same rows as B or C alone. So B C -> B and B C -> C, but these are not new either. A B disagrees on all rows, so A B -> C and A B -> D, but the latter, along with D -> C above, implies A B -> C by transitivity, so only A B -> D is new. Similarly, A C disagrees on all rows, so A C -> D. Summarizing again:

A B -> D
A C -> D
B -> C
C -> B
D -> A B C

Now we turn to FDs with triples of attributes on the left. Any triple containing D disagrees on all rows, but again this gives us nothing new. Triple A B C is the only other one. Since AB disagrees on all rows, so does ABC, so A B C -> D, but this is not new. Thus the FDs immediately above this paragraph give the final set.

[6.12] Here is a list of Armstrong's Axioms and results of Theorem 5.6.8 for use in proving the desired results. Let W, X, Y, and Z be arbitrary sets of columns.

1. Reflexivity.	If Y is a subset of X, then X -> Y
2. Augmentation	If X -> Y, then WX -> WY
3. Transitivity.	If X -> Y and Y -> Z, then X -> Z
4. Union.	If X -> Y and X -> Z, then X -> YZ
5. Decomposition.	If X -> YZ then X -> Y and X -> Z
6. Pseudotransitivity.	If X -> Y and WY -> Z, then XW -> Z

(b) AC -> BD

(1.) By FD (2) given, C -> B. (2.) Therefore by Augmentation, AC -> AB. (3.) From this, by Decomposition, AC -> B. (4.) Now by FD (4) given, AC -> D. (5.) Putting this together with AC -> B, we get by Union that AC -> BD. (Note that steps (1.) through (3.) were needed to go from C -> B to AC -> B. This seems as simple as some of Armstrong's axioms, but we need to prove it. More generally, we could prove a Theorem: if X -> Y, then WX -> Y, and call this result Weak Augmentation or whatever.)

(c) AC -> ABCD

(1.) By FD (4), AC -> D. (2.) Using the result of (a) above, D -> ABCD. Now by Transitivity, (1.) and (2.) give AC -> ABCD.

[6.20] (a) Step 1. G = {BCD->A, BC->E, A->F, F->G, C->D, A->G}

Step 2. BCD->A: J = G - {BCD->A}, X+ = BCDE, not containing A, so keep this FD.
BC->E: J = G - {BC->E}, X+ = BCDAFG, not containing E, so keep.
A->F: J = G - {A->F}, X+ = AG, not containing F, so keep.
F->G: J = G - {F->G}, X+ = F, not containing G, so keep.
C->D: J = G - {C->D}, X+ = C, not containing D, so keep.
A->G: J= G - {A->G}, X+ = AFG, containing G, so drop.

G = {BCD->A, BC->E, A->F, F->G, C->D}

Step 3. BCD->A, we need to loop through B, C, and D, trying to drop each in turn:
B: Y=CD, J is G with BCD->A replaced by CD->A, Y+ under J = CDAFG, Y+ under H = CD, not equal, so keep B.
C: Y=BD, J is G with BCD->A replaced by BD->A, Y+ under J = BDAFG, Y+ under H = BD, not equal, so keep C.
D: Y=BC, J is G with BCD->A replaced by BC->A, Y+ under J = BCAEFGD, Y+ under H = BCEDAFG, same, so drop D.

New G = {BC->A, BC->E, A->F, F->G, C->D} BC->E, so now we loop through B and C:
B: Y=C, J is G with BC->E replaced by C->E, Y+ under J = CED, Y+ under H = CD, different, so keep B.
C: Y=B, J is G with BC->E replaced by B->E, Y+ under J = BE, Y+ under H = B, different, so keep C.
New G = {BC->A, BC->E, A->F, F->G, C->D}

Step 4. G = {BC->AE, C->D, A->F, F->G}

(c) To get to 3NF, we need to factor out the transitive dependencies as well. FDs A->F and F-> G imply that we must factor out two other tables, to get: (B, C, A, E), ( C, D), (A, F), and (F, G). This decomposition is BCNF.

6.23] (a) S = {ABCD, AE, BFH, CG, HI}, where T1 = ABCD, T2=AE, etc. Candidate keys: Need A in key, since it shows up only on lhs's of FDs. A+ = AE(2), so need others too. AB+ = ABCD(1)E(2)FH(3)G(4)I(7) OK, a cand. key, and since it's in a table in S, we're done. Underlined keys: S = {ABCD, AE, BFH, CG, HI},

(b) Since G->C, G is also a candidate key for CG. Since D->B, AD is also a candidate key for ABCD.

(c) Head(T1) INTERSECT Head(T2) = A, key for T2, so lossless. Let T12 = T1 JOIN T2. Head(T12) INTERSECT Head(T3) = B, key for T3, so the join is lossless. Let T123 = T12 JOIN T3, Head(T123) = ABCDEFH. Head(T123) INTERSECT Head(T4) = C, key for T4, so lossless. Let T1234 = T123 JOIN T4. Head(T1234) = ABCDEFHG. Head(T1234) INTERSECT Head(T5) = H, key for T5, so lossless. We have shown that ((((T1 JOIN T2) JOIN T3) JOIN T4) JOIN T5) is lossless this way, and since JOINs are associative, we can now drop the parentheses.

(d) The decomposition is not BCNF, because table T1 is not in BCNF form. It has FDs AB->CD and D->B lying in it. The first one is OK because AB is a key for the table, but the second is not because its lhs, D is not a superkey for the table. (Table T4 also has two FDs, but it is in BCNF, since both lhs's are superkeys.)