Method to find candidate key given FD:s?

Niklas R. picture Niklas R. · Jun 4, 2012 · Viewed 7.2k times · Source

I'm practicing taking as input a set of functional dependencies and output candidate key(s). Is there an algorithm and how come in such case there is no web-based implementation where I can input my FD:s and as output get a list of superkeys / candidate keys?

I practice on what I find here on SO and a suitable question is how to find the highest normal form for a given relation where the functional dependencies mentioned are

B->G

BI->CD

EH-> AG

G-> DE

Please check if I'm doing this right when I try to find that the candidate key is BFHI:

The FD B->G can be rewritten as ABCDEFHI->ABCDEFGHI and therefore ABCDEFHI is a superkey. The FD BI->CD can be rewritten as ABEFGHI->ABCDEFGHI and therefore ABEFGHI is a superkey. The FD EH->AG can be rewritten as BCDEEFHI->ABCDEFGHI and therefore BCDEEFHI is a superkey. The FD G->DE can be rewritten as ABCFGHI->ABCDEFGHI and therefore ABCFGHI is a superkey.

In our superkeys, BFHI is in every one. Therefore BFHI is the candidate key and it cannot be reduced further which can be seen from inspection(?)

Am I reasoning this the right way?

There is another question the augmenting algorithm can handle, if it works, Database extraneous attributes and decomposition

Here, the FD:s are

A->BCD

BC->DE

B->D

D->A

Here the FB A->BCD can be written as AEF->ABCDEF and therefore AEF is a superkey. The FD BC->DE can be rewritten as ABCF->ABCDEF and therefore ABCF is a superkey. The FD B->D can be rewritten as ABCEF->ABCDEF and therefore ABCEF is a superkey. The FD D->A can be rewritten as BCDEF->ABCDEF and therefore BCDEF is a superkey. For all superkeys, F is the only member(s) that is in every superkey and therefore F is the only candidate key.

Does this work?

Thanks for any answer/comment

Answer

Serafim Dahl picture Serafim Dahl · Jun 4, 2012
No, but as F is not in any of the FD:s then it has to be a member of every candidate key.

Also, A->BCD, BC->DE, B->D, D->A give us 
A+ (the cover of A) = ABCDE
B+ = ABCDE
C+ = C
D+ = ABCDE so the 
E+ = E
F+ = F.

The combinations giving ABCDEF are
AF
BF
DF
and hence the candidate keys are {AF, BF, DF}
and every enhancement of any of those three are the superkeys