How to obtain a minimal key from functional dependencies?

Question

I need some help and guidelines. I have the following relation: `R = {A, B, C, D, E, F}` and the set of functional dependencies ``` F = { {AB -> C}; {A -> D}; {D -> AE}; {E -> F}; } ``` What is the primary key for R ? If i apply inference rules i get these additional Function dependencies: ``` D -> A D -> E D -> F D -> AEF A -> E A -> F A -> DEF ``` How do I continue?

Accepted Answer

There is a well known algorithm to do this. I don't remember it, but the excercise seems to be simple enough not to use it.

I think this is all about transitivity:

```
CurrentKey = {A, B, C, D, E, F}
```

You know D determines E and E determines F. Hence, D determines F by transitivity. As F doesn't determine anything, we can remove it and as E can be obtained from D we can remove it as well:

```
CurrentKey = {A, B, C, D}
```

As AB determines C and C doesn't determine anything we know it can't be part of the key, so we remove it:

```
CurrentKey = {A, B, D}
```

Finally we know A determines D so we can remove the latter from the key:

```
CurrentKey = {A, B}
```

If once you have this possible key, you can recreate all functional dependencies it is a possible key.

PS: If you happen to have the algorithm handy, please post it as I'd be glad to re-learn that :)

How to obtain a minimal key from functional dependencies?

Solution

Problem