Re: ? Finding Functional dependancies and Keys

netguru <netguru_at_swlink.net> wrote in message news:9tpta60jnu_at_enews3.newsguy.com...
>
> I have a question on methodology of working with FD's (functional
> dependancies) and their notation.
>
> Given the relation R (A,B,C,D,E) and the following FD's
>
> AB -> C
> AC -> D
> CDE -> AB
> BD -> ?
>
> (1) find ?

This is usually determined by computing the socalled closure of BD which is the set of all attributes that functionally depend upon BD. Determining this closure X+ of a set of attributes X is done with the following algorithm:

1. Let X+ be equal to X
2. If the dependency Y -> Z holds and Y is a subset of X+ then add Z to X+
3. repeat step 2 until X+ stays the same

For example, if you want to find the closure of AB you find

  X+ = AB  (step 1)
  X+ = ABC (step 2 with AB -> C)
  X+= ABCD (step 2 with AC -> D)  *stop*

If we try this for BD we find

  X+ = BD *stop*

So we conclude that BD -> BD

> (2) what are the keys to the relation

This is a bit more difficult but essentially you apply the same rules except now backwards. You start with all columns (ABCDE) and determine what the minimal sets are on which all these columns functionally depend. If we look at your example we start with

  ABCDE (superkey by definition)

and then find the following smaller superkeys

  ABDE  (because ABCDE is superkey and AB -> C)
  ABCE  (because ABCDE is superkey and AC -> D)
  CDE  (because ABCDE is superkey and CDE -> AB)

from these superkeys we then find

  ABE (because ABCE is superkey and AB -> C)

Of all the superkeys we find this way we then only choose the smallest ones, which gives:

  ABE, CDE and these are indeed the candidate keys.

• Jan Hidders