For each, compute the ’follow from’ for each given FD
o Make a list of all BCNF violations with one attribute on the right-hand side
o Decompose each relation into a set of equivalent BCNF relations
1.
R = (A,B, C, D, E)
Fds: A→B
C→D
2.
R = (A, B, C, D, E)
Fds: A→B,C
C,D→E
B→D
E→A
3.
R = (A, B, C, D, E)
Fds: A→ C,D
B → C,E
E → B
4.
R = (A, B, C, D, E)
Fds: A→ B
C,D → E
5.
R = (A, B, C, D, E, F, G, H, I, J, K, L, M)
Fds: A → B,C,D,E
E →F,G,H
I →J
A ,I → K
A, L → M
To compute the "follow from" for each given FD, you need to identify all the attributes that can be determined by the given FD. Here's how you can calculate the "follow from" for each FD:
1. R = (A, B, C, D, E)
Fds: A→B, C→D
- Follow from A→B: Since A determines B, we add B to the follow set of A. Similarly, since C determines D, we add D to the follow set of C.
Follow from A→B: {B}
Follow from C→D: {D}
2. R = (A, B, C, D, E)
Fds: A→B,C, C,D→E, B→D, E→A
- Follow from A→B,C: Since A determines B and C, we add B and C to the follow set of A.
Follow from A→B,C: {B, C}
- Follow from C,D→E: Since C and D determine E, we add E to the follow set of C and D.
Follow from C,D→E: {E}
- Follow from B→D: Since B determines D, we add D to the follow set of B.
Follow from B→D: {D}
- Follow from E→A: Since E determines A, we add A to the follow set of E.
Follow from E→A: {A}
3. R = (A, B, C, D, E)
Fds: A→C,D, B→C,E, E→B
- Follow from A→C,D: Since A determines C and D, we add C and D to the follow set of A.
Follow from A→C,D: {C, D}
- Follow from B→C,E: Since B determines C and E, we add C and E to the follow set of B.
Follow from B→C,E: {C, E}
- Follow from E→B: Since E determines B, we add B to the follow set of E.
Follow from E→B: {B}
4. R = (A, B, C, D, E)
Fds: A→B, C,D→E
- Follow from A→B: Since A determines B, we add B to the follow set of A.
Follow from A→B: {B}
- Follow from C,D→E: Since C and D determine E, we add E to the follow set of C and D.
Follow from C,D→E: {E}
5. R = (A, B, C, D, E, F, G, H, I, J, K, L, M)
Fds: A→B,C,D,E, E→F,G,H, I→J, A,I→K, A,L→M
- Follow from A→B,C,D,E: Since A determines B, C, D, and E, we add B, C, D, and E to the follow set of A.
Follow from A→B,C,D,E: {B, C, D, E}
- Follow from E→F,G,H: Since E determines F, G, and H, we add F, G, and H to the follow set of E.
Follow from E→F,G,H: {F, G, H}
- Follow from I→J: Since I determines J, we add J to the follow set of I.
Follow from I→J: {J}
- Follow from A,I→K: Since A and I determine K, we add K to the follow set of A and I.
Follow from A,I→K: {K}
- Follow from A,L→M: Since A and L determine M, we add M to the follow set of A and L.
Follow from A,L→M: {M}
To make a list of all BCNF violations with one attribute on the right-hand side:
- For each FD, if there is a single attribute on the right-hand side that is not a superkey of the relation, then it is a BCNF violation.
- A superkey is a set of attributes that uniquely identifies each tuple in the relation.
To decompose each relation into a set of equivalent BCNF relations:
- Identify the BCNF violations with one attribute on the right-hand side.
- For each violation, decompose the relation by creating a new relation with the violating FD and the attributes necessary to make it a superkey.
- Repeat this process until all violations have been resolved and you have a set of BCNF relations.