Functional Dependencies: Determining Which FD Is Not Implied (R(A,B,C,D,E))

Functional Dependencies: Determining Which FD Is Not Implied (R(A,B,C,D,E))

Verified Sources

Sep 14, 2026

We are given a relation schema $R(A,B,C,D,E)$ with the following functional dependencies (FDs):

$A \to B$
$A \to C$
$CD \to E$
$B \to D$
$E \to A$

We must determine which of the candidate FDs is not implied by the given set:

(i) $CD \to AC$
(ii) $BD \to CD$
(iii) $BC \to CD$
(iv) $AC \to BC$

We will use attribute closure and Armstrong’s axioms to check implication.

Key idea

An FD $X \to Y$ is implied iff $Y \subseteq X^+$ , where $X^+$ is the attribute closure of $X$ under the given FD set.

We will compute closures for the relevant left-hand sides: $CD, BD, BC, AC$ .

type="tip" title="Pro Tip" content="When you see a cycle like $E \to A$ , combine it with any rules that produce $A$ to derive additional FDs (often yielding closures that grow quickly)."

Compute closures and test each candidate FD

1
Step 1
Start with $\{C,D\}$ . Use $CD \to E$ to get $E$ . Then use $E \to A$ to get $A$ . From $A \to B$ and $A \to C$ , obtain $B$ and confirm $C$ . Use $B \to D$ to confirm $D$ . So $CD^+ = \{C,D,E,A,B\}$ , which includes $A$ and $C$ .
2
Step 2
Since $A \in CD^+$ and $C \in CD^+$ , we have $CD \to AC$ implied.
3
Step 3
Start with $\{B,D\}$ . From $B \to D$ we get $D$ (already). Then $D \to ?$ none directly, but use $B$ to ensure $D$ exists. More importantly, we need $C$ and $E$ and then $CD$ . Derive $A$ : we can get $E$ only via $CD \to E$ , but we can get $CD$ if we first get $C$ . So we compute systematically: from $B$ we can get $D$ only; however $E \to A$ is one-way. This means we must try a different route by deriving $A$ from $E$ —so we check whether $A$ (or $C$ ) is implied by $BD$ .
4
Step 4
Notice the only way to get $E$ is via $CD \to E$ . The only way to get $C$ is via $A \to C$ (since no rule gives $C$ from $B$ or $D$ alone). The only way to get $A$ is via $E \to A$ . Therefore, unless $BD$ can imply $E$ or $C$ , $BD$ cannot imply $CD$ . So $BD^+$ cannot contain $C$ or $E$ .
5
Step 5
Since $C \ otin BD^+$ , $BD \to CD$ is not implied.
6
Step 6
Start with $\{B,C\}$ . From $B \to D$ , infer $D$ . Now we have $C$ and $D$ , so $CD \to E$ gives $E$ . Then $E \to A$ gives $A$ . With $A \to B$ and $A \to C$ , we confirm $B$ and $C$ . Thus $BC^+ = \{A,B,C,D,E\}$ includes $D$ and therefore implies $CD$ .
7
Step 7
We have $C \in BC^+$ and $D \in BC^+$ , hence $CD \subseteq BC^+$ and $BC \to CD$ is implied.
8
Step 8
Start with $\{A,C\}$ . From $A \to B$ , infer $B$ . From $B \to D$ , infer $D$ . Now $C$ and $D$ are present, so $CD \to E$ gives $E$ . Finally $E \to A$ confirms $A$ . Thus $AC^+ = \{A,B,C,D,E\}$ , which contains $BC$ .
9
Step 9
Since $B \in AC^+$ and $C \in AC^+$ , $AC \to BC$ is implied.

Detailed closure reasoning (clean derivations)

1) Candidate (i): $CD \to AC$

From the given FD $CD \to E$ ,

$(CD)^+ \supseteq \{C,D,E\}$ From $E \to A$ ,
$(CD)^+ \supseteq \{C,D,E,A\}$ From $A \to B$ and $A \to C$ ,
$(CD)^+ \supseteq \{A,B,C,D,E\}$

So $A$ and $C$ are in $CD^+$ , hence (i) is implied.

2) Candidate (ii): $BD \to CD$

Start with $BD$ . What can we infer immediately?

From $B \to D$ , we get $D$ (already). There is no rule of the form $B \to C$ , nor $D \to C$ , nor $B \to A$ , nor $D \to A$ .

To get $C$ we must use $A \to C$ . To get $A$ we must use $E \to A$ . To get $E$ we must use $CD \to E$ — but that needs $D$ and $C$ already.

So there is no derivation chain that produces $C$ from $BD$ alone. Therefore $C \notin (BD)^+$ , hence $CD \nsubseteq (BD)^+$ .

So (ii) is not implied.

3) Candidate (iii): $BC \to CD$

From $B \to D$ ,

$BC \Rightarrow D$

Now we have $C$ and $D$ , so:

$CD \to E$ gives $E$
$E \to A$ gives $A$ So indeed $C$ and $D$ are both in $(BC)^+$ , hence (iii) is implied.

4) Candidate (iv): $AC \to BC$

From $A \to B$ ,

$AC \Rightarrow B$

So $B$ and $C$ are already included on the right side:

therefore $BC \subseteq (AC)^+$ Hence (iv) is implied.

Implication Check Results

Whether each candidate FD is implied by the given FD set.

Why the answer is (ii) BD → CD

FD Implication Workflow

Pick candidate

For $X \to Y$ , compute $X^+$ using the FD set."

Run derivations

Repeatedly apply $U \to V$ when $U \subseteq X^+$ ."

Test inclusion

If $Y \subseteq X^+$ , then the FD is implied."

Conclude for all options

Exactly one option fails: (ii) $BD \to CD$ ."

Functional Dependency Mastery (Quick Checks)

1 / 3

Question · Term

FD implication test

Click to reveal

Answer · Definition

To check whether $X \to Y$ is implied, compute $X^+$ and verify $Y \subseteq X^+$ .

Knowledge Check

Question 1 of 3

Q1Single choice

Which FD is NOT implied by {A→B, A→C, CD→E, B→D, E→A}?

CD → AC

BD → CD

BC → CD

AC → BC

Explore Related Topics

Closure Properties of Turing-Language Classes: Identifying False Statements

Lossless vs Lossy Decomposition for Given Functional Dependencies (D1 and D2)

Attribute Closure $X^+$ with Respect to Functional Dependencies $F$: Definition and Algorithm

Browse all research articles