Search code examples
databasefunctional-dependencies

how to find the minimal cover for a set of functional dependencies?

I want to find the minimal cover for the following set of functional dependencies:

A -> BC

B -> C

A -> B

AB -> C

first step: Break down the RHS of each functional dependency into a single attribute:

A -> B

A -> C

B -> C

A -> B

AB -> C

then I will remove of the two A -> B, so we will get:

A -> B

A -> C

B -> C

AB -> C

second step: Trying to remove unnecessary attributes from the LHS of each functional dependency (whose LHS has 2 or more attributes):

for AB -> C , check if A is necessary by:

replace AB -> C with B -> C so if B+ contains C then A is unnecessary:

B+ = B (B -> C)

   = BC (so A is unnecessary)

check if B is necessary by:

replace AB -> C with A -> C so if A+ contains C then B is unnecessary:

A+ = A (A -> B)

   = AB (A -> C)

   = ABC (so B is unnecessary)

now we have:

A -> B

A -> C

B -> C

third step: Trying to remove unecessary functional dependencies:

for A -> B check if A+ contains B without using A -> B:

A+ = A (A -> C)

   = AC (so A -> B is necessary)

for A -> C check if A+ contains C without using A -> C:

A+ = A (A -> B)

   = AB (so A -> C is necessary)

for B -> C check if B+ contains C without using B -> C:

B+ = B (so B -> C is necessary)

now we have:

A -> B

A -> C

B -> C

Finally, group the functional dependencies that have common LHS together:

A -> BC

B -> C

so we can say that these functional dependencies are the minimal cover of the set, is that true ? and how we can deduce the key(s) of the set?

Solution

  • To compute a canonical cover for F:

    Use the union rule to replace any dependencies with common left-side.

    so Combine A ->BC and A -> B into A -> BC Set is now {A -> BC, B -> C, AB -> C}

    A is extraneous in AB -> C

    Check if the result of deleting A from AB -> C is implied by the other dependencies

    Yes: in fact, B -> C is already present!

    Set is now {A -> BC, B -> C}

    C is extraneous in A -> BC

    Check if A -> C is logically implied by A  B and the other dependencies

    Yes: using transitivity on A -> B and B -> C.

    Can use attribute closure of A in more complex cases

    The canonical cover is: A ->B, B -> C

    source:Korth,sudarshan DBMS book.