2

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!

Improve this question
0

1 Answer 1

Reset to default
0

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.

Improve this answer
2
  • 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
    Commented Oct 10, 2019 at 8:04
  • 2
    @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
    Commented Oct 10, 2019 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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