I have a relation schema R = {A, B, C} and the following functional dependencies:

  • A → B
  • A → C
  • B → A
  • B → C
  • C → A
  • C → B

How many different minimal covers can I derive from this relation schema? I have found the following, but I am not really sure if those are all:

  • A → C
  • B → C
  • C → A
  • C → B

Also, I am not sure if there is some rule on how to know if one has found all possible minimal covers.

Thanks a lot for any help!

  • Why not A->B, B->C, C->A? and backward... R = {A, B, B} Maybe R = {A, B, C}? – Akina Oct 10 at 7:01
  • @Akina What do you mean with backwards? I am a little bit confused on how to find out how many different covers can be derived from this relation. Thank you. – BlackPearl Oct 10 at 8:02
  • A->C, C->B, B->A, of course. Your scheme consists from two rings, each of them is a minimal cover. – Akina Oct 10 at 8:04
  • @Akina does that mean that basically every FD can be seen as a minimal cover since they all would cover the whole relation because the FDs are basically a loop? – BlackPearl Oct 10 at 8:11
  • FDs are basically a loop ?? why? A->B, B->C, B->D, C->D. No loop. Minimal cover is A->B, B->C, C->D only. – Akina Oct 10 at 8:29

In general, there are different canonical covers of a set of functional dependencies, and a canonical cover is called minimal if it has less dependencies of any equivalent cover.

So, for instance, in your example the cover:

A → B
B → C
C → A

is minimal, because it has 3 dependencies and it is not possible to find a cover with less dependencies.

There are several definitions and algorithms of cover. For instance, the Chapter 5 of "The Theory of Relational Databases" of Maier, D. Computer Science Press, 1983, describes several kinds of cover (nonredundant, canonical, minimal, optimal, annular), and different algorithms to find them, but for what I know nobody has given a formal algorithm to find all the possible minimal cover.

  • Thank you very much. Does that mean that all possible covers are simply the different combinations? Because of the specific FDs of the Relation I thought that using any one of them could result in a minimal cover. So having A -> B would also cover C by having B -> C. I might be wrong but then any singly FD could be a minimal cover by itself? – BlackPearl Oct 10 at 8:04
  • I made a mistake in my question. The attributes are ABC not ABB. – BlackPearl Oct 10 at 8:31
  • @BlackPearl, to find a canonical cover one should use one of the algorithms. Those algorithms examines the FDs in a certain order. If you change the order you can obtain different canonical covers. Maybe changing the order of the FDs in all the possible ways can produce all the possible canonical covers, but this algorithm would be exponential. – Renzo Oct 10 at 16:15
  • 1
    What is "equivalent" for covers here? Having the same closure? Perhaps, per typical use of the modifier "canonical", having the same canonical cover? (Begging "having" of course.) – philipxy Oct 11 at 2:07
  • 1
    @BlackPearl What does "the different combinations" mean? Or "using any one" or "can be seen as"? Etc. (Rhetorical.) You write in your comments so fuzzily that it's not clear what you are trying to say. It is very important to be clear & precise. That includes memorizing definitions exactly & using defined terms according to them. And using enough words, phrases & sentences referring to exact things & exact parts of them. Otherwise, one can't understand, reason or communicate. – philipxy Oct 11 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.