Re: Functional dependencies

Papastefanos Serafeim wrote:
> Let's say that I have a relation with
> the attributes A,B,C,D,E.
> Is there a standard way to find the
> candidate keys of that relation if I
> am given a set of functional
> dependencies for those attributes,
> like A->B, BC->E, ED->A ?
> I don't want the answer, I want to
> know if there is a standard way to
> find it.

Yes, there is. The algorithm is described on

http://en.wikipedia.org/wiki/Database_normalization

The page is a mess but you can find it under the header "Algorithm (deriving candidate keys from FDs)". Basically it amounts to using the following rule to derive smaller superkeys:

    if C is a superkey and the FD X->Y holds     then (C - Y) + X is also a superkey

The algorithm starts with a set singleton set that contains the superkey that contains all columns, and then applies this rule to derive smaller superkeys. If it finds a smaller superkey that is a strict subset then the original superkey is removed from the set. Once you obtain a superkey for which you cannot derive a superkey that is a strict subset, you have found a candidate key.

Good luck,

• Jan Hidders