Finding candidate keys for given relation

Question

R = (A, B, C, D, E)

The functional dependencies are:

A -> B
ED -> A
BC -> E

It then lists the candidate keys as:

ACD, BCD, CDE

How are these candidate keys derived from the above FDs?

Similarly,

R = (A, B, C, D)

The functional dependencies are:

D -> B 
AB -> D 
AB -> C 
C -> A

It then lists the candidate keys as:

AB, BC, CD, AD

Again, my issue here is that I'm not sure how the candidate keys have been derived from the FDs.

Obbard

Answer 1

This article describes how canditate keys are derived from a given relation.
http://en.wikipedia.org/wiki/Candidate_key.
Also take a look at: candidate keys from functional dependencies
functional-dependencies.
This is also a good one, I think:
http://www.cs.newpaltz.edu/~pletcha/BuildingCandidateKeys.html.
so it's basically:
A => B(first case):
ED => A
BC => E
Because C and D dont depend in any fd, obviously CD is a part of every candiate key.

ACD, BCD, CDE
The second:
D => B
AB => D
AB => C
C=> A

All singles depend in one of the fd, so none of them is included in all candiate keys.
A depends not on D and not on B, neither explicit nor implicit. SO AD and AB is one
candiate key. B doesn't depend on C and A, therefor AB and BC. C doesn't depend on D,
therefor CD.

AB, BC, CD, AD

this one is also usefull: http://csc.lsu.edu/~jianhua/fd_slide2_09.pdf

Holmgren

Answer 2

This is a bit old, but has a lot of views, so I thought it might help to add my own explanations.

For the first problem:

R = (A, B, C, D, E)
A => B
ED => A
BC => E

Basically, a candidate key must satisfy two criteria:

1) A candidate key must be able to determine all other variables. What this basically means is that using the variables in the candidate key, you should be able to find every other variable by following the arrows in the functional dependencies.

2) A candidate key must be minimal. For example, we can find every variable from ABCDE, because ACBDE is every variable already. However, we could take some variables off. For example, it can be found that ACD is a candidate key. Since ACD is a valid candidate key, and ACD is a subset of ABCDE, we know that ABCDE can't be a candidate key. In other words, we can talk variables off of ABCDE and still have a candidate key, so ABCDE is not minimal.

If you're new to finding candidate keys using functional dependencies, a good place to start is to just try random variables and see if they satisfy the two above criteria.

Let's start with just the variable A. Our first functional dependency tells us that A determines B, so now we have two variables, A and B. However, AB don't satisfy either of the other functional dependencies, so we're out of luck. We've determined that A by itself is not a candidate key (and neither is AB, too, logically, since we already figured out we can't derive C, D and E with AB).

Next, let's try ABC. Since we know that we can always get B with A (from A => B), it doesn't really make sense to have A and B in the same candidate key. This is because if ABC works, then AC must work, because we can get ABC from AC.

Let's try again with AC instead of ABC. A determines B, so now we have variables A, B and C. BC determines E (BC => E), so now we have A, B, C, and E. However, we have no way to get variable D! In fact, logically, because C and D aren't the result of any functional dependency (they're never on the right side), we know that C and D must be a part of every candidate key (as pointed out in the other post).

We could try seeing if CD is a candidate key, but logically, since C doesn't functionally determine anything by itself, D doesn't determine anything by itself, and CD doesn't determine anything, CD can't be a candidate key.

Let's try ACD. First of all, as we know, A determines B, so we have variables A, B, C and D. BC determines E (BC => E), so we have all 5 variables, so we have a candidate key!

However, multiple candidate keys are a possibility, so we're not done. Remember that every key must include C and D, so let's try BCD. BC determines E, so we have B, C, D and E. ED determines A (ED => A), so we have all 5 variables. We have another candidate key!

Let's try the last possible answer: CDE. ED determines A, so we have A, C, D and E. A determines B, so we have all 5 variables and we have a candidate key.

Our 3 possible candidate keys are ACD, BCD, and CDE. We know that if we take any variable away from one of these keys, it won't be a valid key, so we know that all of these keys are also minimal.

Let's go to the second problem:

R = (A, B, C, D)
D => B 
AB => D 
AB => C 
C => A

Since we have our basic knowledge down now, let's do less trial-and-error and more analytical reasoning.

First, AB determines both C and D. Also, A and B obviously aren't candidate keys, so we know that AB is minimal. AB is our first candidate key.

CD determines A and B, and C and D obviously aren't keys by themselves, so CD is our second candidate key.

Looking at our functional dependencies, we know that if we get either A and B OR C and D, we can find every other variable. Knowing this, we see that because D gives us B, all we are missing is A. Therefore, AD is a candidate key.

Using the same logic, since C determines A, if we add B, we'll have AB and be able to find everything missing. Therefore BC is also a key. Again, like the other candidate keys for this exercise, BC is trivially minimal.

Our final possible candidate keys are AB, CD, AD, and BC.

Exhibitor

Thank you so much. I have been looking for help on this exact question for the past hour, and this really clarified things 👍 you rock! – Martinez