Lossless Join Example

Lossless Join Example discussed in class Let R = ABCDE, R1 = AD, R2 = AB, R3 = BE, R4 = CDE, and R5 = AE. Let the functional dependencies be: A -> C, B -> C, C -> D, DE -> C, CE -> A Apply algorithm 7.2 from class handout to test if the decomposition of R into {R1,..,R5} is a lossless join decomposition. The initial table looks as follows: R1(AD) R2(AB) R3(BE) R4(CDE) R5(AE) A B C D E a1 a1 b31 b41 a1 b12 a2 a2 b42 b52 b13 b23 b33 a3 b53 a4 b24 b34 a4 b54 b15 b25 a5 a5 a5 Apply FD A -> C to the initial table to modify the violating dependencies. Rows 1, 2, 5 will need to change the values for the RHS attribute C – equate b13, b23, b53 to b13 (you might very well have picked b23 or b53 to equate all three). We won’t change the rows 3 & 4 yet because their symbols b31, b41 are different from a1. A a1 a1 b31 b41 a1 B b12 a2 a2 b42 b52 C b13 b13 b23 b13 b33 a3 b53 b13 D a4 b24 b34 a4 b54 E b15 b25 a5 a5 a5 Apply B -> C next to equate b33 with b13 A a1 a1 b31 b41 a1 B b12 a2 a2 b42 b52 C b13 b13 b23 b13 b33 b13 a3 b53 b13 D a4 b24 b34 a4 b54 E b15 b25 a5 a5 a5 Next, use C -> D to equate a4, b24, b34, and b54 A a1 a1 b31 b41 a1 B b12 a2 a2 b42 b52 C b13 b13 b23 b13 b33 b13 a3 b53 b13 D a4 b24 a4 b34 a4 a4 b54 a4 E b15 b25 a5 a5 a5 DE -> C helps us to equate b13 (all occurrences) with a3. The following table shows the corresponding changes. A a1 a1 b31 b41 a1 B b12 a2 a2 b42 b52 C b13 b13 a3 b23 b13 a3 b33 b13 a3 a3 b53 b13 a3 D a4 b24 a4 b34 a4 a4 b54 a4 E b15 b25 a5 a5 a5 Apply CE -> A to the table above to equate b31, b41, and a1. A a1 a1 b31 a1 b41 a1 a1 B b12 a2 a2 b42 b52 C b13 b13 a3 b23 b13 a3 b33 b13 a3 a3 b53 b13 a3 D a4 b24 a4 b34 a4 a4 b54 a4 E b15 b25 a5 a5 a5 The middle row in the table above is all a’s, and the decomposition has a lossless join. --------------------------------------------------------------------------------------------------------------------What happens if we apply FDs in a different order? Try any FD with the same symbols (a or b) on the LHS attribute in at least two rows. We have two choices: A -> B or B -> C. We tried A -> B in the previous test. Try B -> C here. A B C D E a1 a1 b31 b41 a1 b12 a2 a2 b42 b52 b13 b23 b23 b33 b23 a3 b53 a4 b24 b34 a4 b54 b15 b25 a5 a5 a5 Apply A -> C after that to get the following table. Notice I chose b23 to equate b13, b23, and b53. A B C D E a1 a1 b31 b41 a1 b12 a2 a2 b42 b52 b13 b23 b23 b23 b33 b23 a3 b53 b23 a4 b24 b34 a4 b54 b15 b25 a5 a5 a5 The table shown above is the similar to the one we got before after applying A -> C and B-> C to the initial table. To the current table we apply C -> D as before because we have the same symbol b23 in rows 1, 2, 3, and 5.