Functional-Dependency Analysis and Normalization of R(A, B, C, D, E, F)

This section develops a systematic solution for

$$R(A,B,C,D,E,F)$$

with functional dependencies

$$\mathcal{F}=\{ABC\to D,\ ABD\to E,\ CD\to F,\ CDF\to B,\ BF\to D\}.$$

A functional dependency $X\to Y$ means that any two tuples agreeing on $X$ must also agree on $Y$. The central tool is the Attribute closure:

$$X^+_{\mathcal F}.$$

If $X^+$ contains every attribute of $R$, then $X$ is a superkey. If no proper subset of $X$ is a superkey, then $X$ is a candidate key.

The analysis has three goals:

1. Find every candidate key.
2. Determine whether $R$ is in BCNF or 3NF.
3. Find a smaller equivalent dependency set, or minimal cover.

Footnotes

1. Functional Dependencies and Finding a Minimal Cover - Defines functional dependencies and discusses equivalent dependency sets. ↩

2. Functional Dependencies: Part 2 - Defines attribute closure, candidate keys, and minimality. ↩

1. Structural observations before computing keys

The right-hand sides of the dependencies are:

• $D$ from $ABC\to D$
• $E$ from $ABD\to E$
• $F$ from $CD\to F$
• $B$ from $CDF\to B$
• $D$ from $BF\to D$

Thus, attribute $A$ never appears on the right-hand side of any dependency. Therefore, no set that omits $A$ can derive $A$. Every key must contain $A$.

Also, $C$ never appears on the right-hand side. Therefore, every key must contain $C$.

Consequently, every candidate key contains $AC$. We only need to determine which additional attributes must accompany $AC$.

This “attributes absent from all right-hand sides” observation is a standard key-search shortcut: such attributes must occur in every candidate key.

Footnotes

1. Functional Dependencies: Part 2 - Defines attribute closure, candidate keys, and minimality. ↩

2. Detailed closure derivations

Closure of $ABC$

Start with

$$(ABC)^+=\{A,B,C\}.$$

Apply $ABC\to D$:

$$\{A,B,C\}\Rightarrow \{A,B,C,D\}.$$

Apply $CD\to F$:

$$\{A,B,C,D\}\Rightarrow \{A,B,C,D,F\}.$$

Apply $ABD\to E$:

$$\{A,B,C,D,F\}\Rightarrow \{A,B,C,D,E,F\}.$$

Therefore,

$$(ABC)^+=\{A,B,C,D,E,F\}=R.$$

So $ABC$ is a superkey. Its proper subsets cannot be superkeys:

• $(AB)^+=\{A,B\}$
• $(AC)^+=\{A,C\}$
• $(BC)^+=\{B,C\}$

Hence $ABC$ is a candidate key.

Closure of $ACD$

Start with

$$(ACD)^+=\{A,C,D\}.$$

Apply $CD\to F$:

$$\{A,C,D\}\Rightarrow \{A,C,D,F\}.$$

Apply $CDF\to B$:

$$\{A,C,D,F\}\Rightarrow \{A,B,C,D,F\}.$$

Apply $ABD\to E$:

$$\{A,B,C,D,F\}\Rightarrow \{A,B,C,D,E,F\}.$$

Therefore,

$$(ACD)^+=R.$$

Its proper subsets are not superkeys:

• $(AC)^+=\{A,C\}$
• $(AD)^+=\{A,D\}$
• $(CD)^+=\{C,D,F,B\}$

In particular, $CD$ cannot derive $A$ or $E$. Thus $ACD$ is a candidate key.

Why there are no other candidate keys

Every candidate key must contain $A$ and $C$. The possible minimal supersets of $AC$ are obtained by adding one or more of $B,D,E,F$.

• Adding $B$ gives $ABC$, which is a key.
• Adding $D$ gives $ACD$, which is a key.
• Adding only $E$ gives $ACE$, which is not a key.
• Adding only $F$ gives $ACF$, which is not a key.

Any larger set containing $ABC$ or $ACD$ is not minimal. Therefore, the complete set of candidate keys is

$$\boxed{\{ABC,\ ACD\}}.$$

The prime attributes are

$$\boxed{A,\ B,\ C,\ D}.$$

The non-prime attributes are

$$\boxed{E,\ F}.$$

3. Visualizing the dependency propagation

The key derivations can be viewed as two principal routes:

The two candidate keys exploit different dependency chains:

• $ABC$ first produces $D$, then $F$ and $E$.
• $ACD$ first produces $F$, then $B$ and $E$.

The dependency $BF\to D$ is not needed for either candidate-key derivation, but it remains relevant when testing normal forms and when constructing an equivalent minimal cover.

4. BCNF analysis

A relation is in Boyce–Codd normal form (BCNF) if, for every nontrivial dependency

$$X\to Y$$

that holds in the relation, $X$ is a superkey.

Check the given dependencies:

The first dependency has a superkey determinant. However, $ABD\to E$ is also not a superkey dependency because $ABD$ cannot derive $C$. More importantly, $CD\to F$, $CDF\to B$, and $BF\to D$ have determinants that are not superkeys.

For example,

$$(CD)^+=\{B,C,D,F\}\neq R.$$

Therefore,

$$\boxed{R\text{ is not in BCNF}.}$$

A single valid counterexample, such as $CD\to F$, is sufficient to disprove BCNF.

Footnotes

1. Boyce-Codd Normal Form (BCNF) - Describes the BCNF requirement that every determinant be a superkey. ↩

5. 3NF analysis

A relation is in third normal form (3NF) if, for every nontrivial dependency $X\to A$, at least one condition holds:

1. $X$ is a superkey; or
2. $A$ is a prime attribute.

The prime attributes are $A,B,C,D$. The non-prime attributes are $E,F$.

Check each dependency:

The dependency

$$ABD\to E$$

violates 3NF because:

• $ABD$ is not a superkey, since $C\notin (ABD)^+$;
• $E$ is non-prime because it belongs to no candidate key.

The dependency $CD\to F$ also violates 3NF because:

• $CD$ is not a superkey;
• $F$ is non-prime.

Therefore,

$$\boxed{R\text{ is not in 3NF}.}$$

Since BCNF is stricter than 3NF, failure of 3NF also implies failure of BCNF. In this case, the relation is not even in 3NF.

Footnotes

1. Third Normal Form - States the 3NF condition involving superkeys and prime attributes. ↩

6. Simplifying the dependency set

The original set is

$$\mathcal F= \{ ABC\to D,\ ABD\to E,\ CD\to F,\ CDF\to B,\ BF\to D \}.$$

To simplify it without changing $\mathcal F^+$, test:

1. Whether any left-hand-side attribute is extraneous.
2. Whether any entire dependency is redundant.

A dependency set $G$ is equivalent to $\mathcal F$ when

$$G^+=\mathcal F^+.$$

The usual procedure is to replace right-hand sides by single attributes, test left-side attributes using closures, and then test each dependency for redundancy.

Footnotes

1. Minimal Cover - Explains extraneous attributes and tests for dependency simplification. ↩

7. Closure calculations for extraneous attributes

7.1 Reducing $ABD\to E$

Test whether $A$ is extraneous by computing $(BD)^+$ under the original dependencies.

Start with

$$(BD)^+=\{B,D\}.$$

Apply the original dependency $ABD\to E$? Its left side requires $A$, so it cannot be applied. No other dependency can fire. Thus, under the original set alone, $(BD)^+$ would not contain $E$.

However, the correct extraneous-attribute test must be performed against the dependency set with the target dependency removed and the proposed reduced dependency inserted, or equivalently by checking whether the dependency is implied by the remaining dependencies after the reduction process. Here, we must be precise: $A$ is not extraneous in $ABD\to E$ under the original set because $BD$ does not derive $E$ from the remaining dependencies.

Therefore, the initial apparent reduction

$$ABD\to E \quad\not\Rightarrow\quad BD\to E$$

is invalid.

7.2 Corrected minimal-cover testing

The left-side reductions must be recomputed carefully:

• For $ABD\to E$, testing $A$ requires $(BD)^+$ under $\mathcal F-\{ABD\to E\}$. This is $\{B,D\}$, so $A$ is not extraneous.
• Testing $B$ requires $(AD)^+$. This is $\{A,D\}$, so $B$ is not extraneous.
• Testing $D$ requires $(AB)^+$. This is $\{A,B\}$, so $D$ is not extraneous.

Thus, $ABD\to E$ cannot be reduced.

7.3 Reducing $CDF\to B$

Test $F$ by computing $(CD)^+$ using the other dependencies, excluding $CDF\to B$:

$$(CD)^+=\{C,D\}.$$

From $CD\to F$, add $F$:

$$(CD)^+=\{C,D,F\}.$$

Without $CDF\to B$, there is no way to derive $B$. Therefore, $F$ is not extraneous under the standard test.

Likewise:

• $(DF)^+=\{D,F\}$, which does not derive $B$;
• $(CF)^+=\{C,F\}$, which does not derive $B$.

Therefore, $CDF\to B$ cannot be reduced.

7.4 Redundant dependency testing

Now test each complete dependency by removing it:

• Without $ABC\to D$, $ABC$ cannot derive $D$.
• Without $ABD\to E$, $ABD$ cannot derive $E$.
• Without $CD\to F$, $CD$ cannot derive $F$.
• Without $CDF\to B$, $CDF$ cannot derive $B$.
• Without $BF\to D$, $BF$ cannot derive $D$.

Therefore, no dependency is redundant.

The original set is already a minimal cover, apart from the conventional step of splitting right-hand sides—which is unnecessary here because every right-hand side already contains one attribute.

Hence,

$$\boxed{\mathcal F\text{ cannot be simplified by removing dependencies or left-side attributes}.}$$

It is already a minimal equivalent cover.

8. Final answer to part (iii)

The answer is no: there is no proper simplification of the given set that preserves the full closure $\mathcal F^+$.

The set

$$\boxed{ \{ABC\to D,\ ABD\to E,\ CD\to F,\ CDF\to B,\ BF\to D\} }$$

is already minimal because:

• Every right-hand side is a single attribute.
• No attribute on any left-hand side is extraneous.
• No entire dependency is implied by the remaining dependencies.

For example:

$$(CD)^+_{\mathcal F-\{CD\to F\}}=\{C,D\},$$

so $CD\to F$ is necessary.

Similarly,

$$(CDF)^+_{\mathcal F-\{CDF\to B\}}=\{C,D,F\},$$

so $CDF\to B$ is necessary.

And

$$(BF)^+_{\mathcal F-\{BF\to D\}}=\{B,F\},$$

so $BF\to D$ is necessary.

Thus, removing any listed dependency changes the closure.

9. Consolidated solution

(i) All keys

The candidate keys are

$$\boxed{ABC\text{ and }ACD}.$$

The prime attributes are

$$\boxed{A,B,C,D}.$$

The non-prime attributes are

$$\boxed{E,F}.$$

(ii) Normal forms

The relation is not in BCNF because, for example,

$$CD\to F$$

holds while $CD$ is not a superkey.

The relation is not in 3NF because, for example,

$$ABD\to E$$

holds while $ABD$ is not a superkey and $E$ is non-prime. The dependency $CD\to F$ independently gives another 3NF violation.

Therefore,

$$\boxed{R\text{ is neither in BCNF nor in 3NF}.}$$

(iii) Simplification

No dependency can be removed, and no attribute can be removed from a left-hand side without changing $\mathcal F^+$. Therefore,

$$\boxed{\mathcal F\text{ is already a minimal cover}.}$$