Database Design – How to Find Minimal Cover with Equal Attribute Chances

database-designnormalization

I have the schema which consists of 6 attributes: t,s,r,w,e,g.

For the schema I have the following functional dependencies:

s,w --> r;t,w,g --> r,e;s,r --> t,g; e -->w; g --> t,s;r,w,e --> s

I'm not quite sure how to go about the dependencies where one side has 3 attributes. For example, for t,w,g --> r,e should I check for all possible combinations of t,w,g (2^3-2=6 cases to check in total)?

For example I choose the case where I want to check if t is not necessary in t,w,g --> r,e.
Indeed the closure of {w,g} is {w,g,t,s,r,e} which contains {r,e}.

If I continue to look for unnecessary attributes in w,g --> r,e then I have:

w,g --> r OR w,g --> e. So can I choose a random result here or there's some rule on whether r is not necessary or e?

Best Answer

In a functional dependency, both the left part and the right part are sets, so the order of the attributes does not matter.

To find the canonical (or minimal) cover of a set of functional dependencies, the classical algorithm (presented in almost all books on databases) consists of three steps:

  1. First, rewrite the dependencies so that they have a single attribute on the right part (for instance, t,w,g -> r,e is replaced by t,w,g -> r and t,w,g -> e).

  2. Then, for each attribute on the left part, see if the closure of the remaining attributes includes the right attribute. In this case the attribute is not necessary and should be eliminated.

  3. Finally, eliminate the superfluous dependencies, if present. A dependency is superfluous if its right part is contained in the closure of the left part, calculated with respect to all the other dependencies.

For instance, in your example, a possible minimal cover can be computed in this way.

At the end of the first step, we have:

{ e → w
  e r w → s
  g t w → e
  g t w → r
  g → s
  g → t
  r s → g
  r s → t
  s w → r }

At the end of the second step:

{ e r → s
  e → w
  g → t
  g → s
  g w → r
  g w → e
  r s → t
  r s → g
  s w → r }

Finally, a minimal cover is:

{ e → w
  e r → s
  g w → e
  g → s
  g → t
  r s → g
  s w → r }
Related Question