Determining candidate keys with functional dependencies simple

Question

Let R(A,B,C,D,E) be a relation schema and F = {A→C, B→D, C→E, E→A}, Find all candidate keys.

I believe that there exists no CK's in this set due to not being able to map. B or D to any other relation besides B -> D . Does this mean that that there are no Candiate Keys? Although I am able to map A to all other entities besides B and D.

Answer 1

There are three candidate keys.

B doesn't appear on the right-hand side of any functional dependency. That means B must be part of every candidate key. I think that alone doesn't guarantee there is at least one candidate key, but it should be clear from inspection that AB is one of the three candidate keys here.

Your textbook should include at least one algorithm for determining the set of all candidate keys. If you're lucky, it includes one algorithm suitable for paper and pencil, and another suitable for automation by programming.

Answer 2

The first step in normalization is to find all of the keys of a relation. Here are some facts that can help find the keys:

1. If an attribute is in none of the FDs, then it is in every key.

2. If an attribute occurs on the right-hand side of an FD, but never occurs on the left-hand side, then it is never in a key.

3. If an attribute occurs on the left-hand side of an FD, but never occurs on the right-hand side, then it is in every key.

4. If an attribute occurs both on the right-hand side an FD and the left-hand side of an FD, then one cannot say anything about the attribute.

To find the keys, identify which attributes are in each of the cases above. The ones in the first and third cases must be in every key. Call this set of attributes the core. Compute the attributes that are determined by the core. This is called the closure of the core. If all of the attributes are in the closure of the core, then the core is not only a key, it is also the only key. If the closure of the core is not the entire set of attributes, then some will be missing. Write down this set of attributes, and remove any attribute that is in the second set above (i.e., it occurs on the right-hand side of an FD, but never occurs on the left-hand side). These are the exterior attributes. To get a key one must add one or more exterior attributes to the core. Accordingly, add them to the core, first one at a time, then two at a time, and so on, until every key has been found.

Answer 3

Since B doesn't come on right hand side so B should be the part of candidate key, and A and C occur on both sides so they can form a super key with B. on mapping AB and BC are super keys and as candidate key is minimal super key so AB and BC are candidate key.

Answer 4

Every attribute that is strictly only on the left hand side across all the functional dependencies, is an attribute that must form part of each of the candidate keys.

The next step is to realise whether such an attribute alone can generate, or determine all the attributes inside the schema or not. If yes, then that attribute is a candidate key in it's original stand-alone form. If not, group that attribute with each of the other attributes, one at a time, two at a time and so on. All such minimal sets that traverse the entire set of attributes can be called as the candidate keys.