Computing $F^+$ and Candidate Keys for $R(A,B,C,D,E)$

We are given relation schema $R=(A,B,C,D,E)$ and a set of functional dependencies (FDs)
$F=\{A\rightarrow BC,\; CD\rightarrow E,\; B\rightarrow D,\; E\rightarrow A\}$.

We will:

1. Compute the attribute closure for sets of attributes using the standard FD-closure procedure (based on Armstrong-style reasoning).
2. Use closures to derive the full closure $F^+$ (i.e., all FDs implied by $F$).
3. List all candidate keys of $R$.

Key notions: attribute closure, functional dependency closure, superkey, candidate key.

Note: Exact computation of $F^+$ can be large; we will compute systematically by finding which single attributes imply which others, then expanding via transitivity.

From the step-by-step closures:

• $A$ is a superkey because $A^+=ABCDE$.
• $E$ is also a superkey because $E^+=ABCDE$.
• $B$ is not a superkey since $B^+$ misses $A,C,E$.
• $C$ and $D$ are not superkeys.

This already suggests candidate keys will be among minimal subsets of $\{A,E\}$.

1) Compute the closure $F^+$ (all implied FDs)

We proceed by deriving, from each relevant determinant, which attributes it forces.

A. All FDs with left side $A$

We know $A^+=ABCDE$, so $A$ determines every other attribute:

• $A\rightarrow B$
• $A\rightarrow C$
• $A\rightarrow D$
• $A\rightarrow E$

Additionally, because $A\rightarrow BC$ is given, we keep:

• $A\rightarrow BC$ and we can combine:
• $A\rightarrow BCD$
• $A\rightarrow BCE$
• $A\rightarrow BDE$
• $A\rightarrow CDE$
• $A\rightarrow BCDE$ (Any superset on the right that does not add new info beyond $ABCDE$ is implied.)

A compact way: since $A^+=ABCDE$, for any $Y\subseteq \{B,C,D,E\}$, we have $A\rightarrow Y$.

B. All FDs with left side $E$

Similarly $E^+=ABCDE$, so $E$ determines every other attribute:

• $E\rightarrow A$ (given)
• $E\rightarrow B$
• $E\rightarrow C$
• $E\rightarrow D$

And combinations:

• $E\rightarrow BC$
• $E\rightarrow CD?$ (careful: $E$ determines $C$ and $D$ separately, hence $E\rightarrow CD$ is implied)
• In general, for any $Y\subseteq \{A,B,C,D\}$, $E\rightarrow Y$ holds (and $E\rightarrow$ any nonempty subset of $ABCDE\setminus\{E\}$ is implied).

C. FDs with left side $B$

We found $B^+=\{B,D\}$. Therefore:

• $B\rightarrow D$ (given)
• $B\rightarrow BD$ is redundant; the meaningful ones are: $B\rightarrow D$. No other attribute is forced by $B$ alone, so there are no implied FDs like $B\rightarrow A$ or $B\rightarrow E$ (unless $A$ or $E$ are derivable—which they are not from $B^+$).

So the only nontrivial right-side implications from $B$ are those involving $D$:

• $B\rightarrow D$ (and thus $B\rightarrow D$ is the only new FD with left $B$).

D. FDs with left side $C$

$C^+=\{C\}$, so there are no nontrivial FDs of the form $C\rightarrow X$ with $X\not\subseteq\{C\}$.

E. FDs with left side $D$

$D^+=\{D\}$, so there are no nontrivial FDs of the form $D\rightarrow X$ with $X\not\subseteq\{D\}$.

F. FDs with left side $CD$

We have $CD\rightarrow E$ (given). From that:

• Since $E\rightarrow A$, we get $CD\rightarrow A$.
• Since $A\rightarrow BC$, we get $CD\rightarrow B$ and $CD\rightarrow C$ (already have $C$).
• Since $B\rightarrow D$, we get $CD\rightarrow D$ (already have $D$).

Therefore $CD^+=ABCDE$, meaning:

• $CD\rightarrow E$ (given)
• $CD\rightarrow A$
• $CD\rightarrow B$
• $CD\rightarrow$ (any subset of $ABCDE\setminus\{C,D\}$) In particular, $CD\rightarrow ABCE$ etc. are implied.

Also note: $CD\rightarrow E$ is the “seed” that makes $CD$ a superkey.

G. FDs with left side $ACD$, $ABD$, etc.

In principle, once the closure of a left-hand set is $ABCDE$, then any FD from that left-hand set to any subset of the remaining attributes is implied. For example:

• $(A,D)^+$ is already $ABCDE$ because $A$ already closes everything. Hence $AD\rightarrow BCDE$ etc. But enumerating every possible left-hand set would be exhaustive; typically in database courses, $F^+$ is described by the closure computation rules plus all derived FDs at the level of single attributes and given minimal determinants.

To keep the course section precise, we’ll list the core implied FDs (single-attribute and the original multi-attribute ones) that arise necessarily from the closures above.

Core implied dependencies (a practical representation of $F^+$)

From the closure results:

1. From $A^+=ABCDE$:

• $A\rightarrow B$
• $A\rightarrow C$
• $A\rightarrow D$
• $A\rightarrow E$
• plus the given $A\rightarrow BC$ (and therefore $A\rightarrow BCDE$ is implied, etc.)

2. From $E^+=ABCDE$:

• $E\rightarrow A$ (given)
• $E\rightarrow B$
• $E\rightarrow C$
• $E\rightarrow D$
• plus any combined forms such as $E\rightarrow AB$ etc. (implied)

3. From $B^+=\{B,D\}$:

• $B\rightarrow D$ (given)
• no implied $B\rightarrow A,C,E$

4. From $CD^+=ABCDE$:

• $CD\rightarrow E$ (given)
• $CD\rightarrow A$
• $CD\rightarrow B$
• and thus $CD\rightarrow$ any subset of $\{A,B,E\}$

5. No nontrivial implications from $C$ or $D$ alone:

• no additional FDs of the form $C\rightarrow X$ ($X\neq C$)
• no additional FDs of the form $D\rightarrow X$ ($X\neq D$)

2) List the candidate keys for $R$

A candidate key is a minimal superkey.

We already computed:

• $A^+=ABCDE$ so $A$ is a superkey.
• $E^+=ABCDE$ so $E$ is a superkey.
• Any set containing $A$ is a superkey, but $A$ itself is minimal (cannot remove $A$).
• Any set containing $E$ is a superkey, but $E$ itself is minimal.

Also, sets without $A$ or $E$:

• $B^+=\{B,D\}$ cannot reach $A$ or $E$.
• $C^+=\{C\}$, $D^+=\{D\}$.
• $CD$ is a superkey (because $CD\rightarrow E$ then closure reaches all), but it is not minimal because neither $C$ nor $D$ alone is a superkey, and for candidate key minimality, we check whether $CD$ can be reduced to a smaller superkey. Any smaller subset of $CD$ is either $\{C\}$ or $\{D\}$, neither of which is a superkey. So $CD$ is minimal among its subsets—however, candidate keys are minimal superkeys overall: since neither $\{C\}$ nor $\{D\}$ is a superkey, $CD$ qualifies as a candidate key.

So candidate keys are:

• $\{A\}$
• $\{E\}$
• $\{C,D\}$