If the following functional dependencies holds on a selection R : $A \rightarrow B$, $A \rightarrow C$, $BC \rightarrow D$, $C \rightarrow F$, $B \rightarrow E$ then which of the following dependency does not hold on R?

Question

Accepted Answer

The correct option is (4):
The dependency that does not hold on relation R is $BD \rightarrow EF$. In Relational Algebra, to verify if a functional dependency $X \rightarrow Y$ holds, we must calculate the closure of $X$, denoted $X^+$, using the given set of functional dependencies $F$. The dependency holds if and only if all attributes in $Y$ are present in $X^+$. For $BD \rightarrow EF$, we calculate $BD^+$. Starting with $BD$, we can apply $B \rightarrow E$ to get ${B, D, E}$. No other given dependencies can be applied because they require $A$ or $C$ as the determinant, which are not present in ${B, D, E}$. Since $F$ is not in $BD^+$, the dependency $BD \rightarrow F$ does not hold, and therefore the larger dependency $BD \rightarrow EF$ does not hold.

The incorrect option is (1):
The dependency $A \rightarrow DE$ holds because $D$ and $E$ are included in the closure of $A$. To demonstrate, $A^+$ includes $B$ (from $A \rightarrow B$) and $C$ (from $A \rightarrow C$). Once $B$ is present, we can use $B \rightarrow E$ to derive $E$. With both $B$ and $C$ present, we can use $BC \rightarrow D$ to derive $D$. Since $A^+ = {A, B, C, D, E, F}$, both $D$ and $E$ are found, validating the dependency $A \rightarrow DE$.

The incorrect option is (2):
The dependency $BC \rightarrow DEF$ holds. Calculating the closure $BC^+$, we start with ${B, C}$. The given dependency $BC \rightarrow D$ directly gives us $D$. Also, $B \rightarrow E$ gives us $E$, and $C \rightarrow F$ gives us $F$. Thus, $BC^+$ contains ${B, C, D, E, F}$. Since the right-hand side ${D, E, F}$ is fully contained within $BC^+$, the functional dependency $BC \rightarrow DEF$ is logically implied by the original set $F$.

The incorrect option is (3):
The dependency $A \rightarrow EF$ holds, as $E$ and $F$ are part of the closure of $A$. As established when checking Option 1, $A^+$ includes $B$ (from $A \rightarrow B$) and $C$ (from $A \rightarrow C$). The presence of $B$ allows us to derive $E$ using $B \rightarrow E$. The presence of $C$ allows us to derive $F$ using $C \rightarrow F$. Since both $E$ and $F$ are derived from $A$, the dependency $A \rightarrow EF$ is valid under the given set of dependencies.