1
$\begingroup$

In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a single attribute but in our book it gives the following example of more complex functional dependencies. Let's say that I have the following relationship:

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

with the following functional dependencies:

$$f_1: \{A,B,C\} \to \{D,F\}$$ $$f_2: \{D,E,F\} \to \{A,C,E\}$$ $$f_3: \{D\} \to \{B\}$$

and I need to find all the candidate keys. Because we need at least $3$ of the attributes to make candidate keys. Through writing out each of the tuples made up of $3$ or more attributes, I found that $\{A, D,E,F\}$, $\{A,B,C,E\}$, $\{D,E,F\}$ and $\{A,C,D,E\}$ are all candidate keys. However the catch is that either $\{A, D,E,F\}$, $\{A,B,C,E\}$ or $\{D,E,F\}$,$\{A,C,D,E\}$, $\{A,B,C,E\}$ are the candidate keys.

I think that because the definition of a candidate key is that there can't be a subset of it that's also a candidate key. Using this logic, $\{A, D,E,F\}$ would also not be candidate key as $\{D,E,F\}$ is already a candidate key. Therefore, the final candidate keys would be:

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

Is my understanding of the topic correct or have I gone of the rails?

$\endgroup$
  • 1
    $\begingroup$ You are correct that the only three candidate keys are {A B C E}, {A C D E} and {D E F}. $\endgroup$ – Renzo May 28 at 20:23
3
$\begingroup$

Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the following one:

{ A B C → D
  A B C → F
  D E F → A
  D E F → C
  D → B }

From these dependencies we can see that E must belong to all the candidate keys, since it does not appear in any right part.

We can start now from the left hand parts of the dependencies to see if their closure contains all the attributes:

ABC+ = ABCDF

by adding E (that must be present in every candidate key) we discover the first candidate key, since ABCE+ = ABCDEF.

Then from DEF:

DEF+ = ACBDEF

so this is already a candidate key.

Finally, starting from D we found that:

D+ = DB

trying again to add E, we find:

DE+ = BDE

we can now try to add A:

ADE+ = ABDE

which is still not a candidate key, and finally adding C we find the last candidate key:

ACDE+ = ABCDEF
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.