Equivalence of FD Sets and Minimal Cover

Concept

Different sets of dependencies can say exactly the same thing. Being able to test that, and to reduce a set to its simplest equivalent form, is required before Phase 8 can decompose anything.

Equivalence of dependency sets

  F and G are EQUIVALENT  when  F covers G  and  G covers F.

  "F covers G" means every dependency in G is implied by F.

  TESTING F covers G
    for each  X -> Y  in G
      compute X+ using F ONLY
      check that Y is inside it
    if all pass, F covers G.

  Then repeat in the other direction.

Worked example

  F = { A -> B, B -> C, A -> C }
  G = { A -> B, B -> C }

  DOES F COVER G?
    A -> B :  A+ under F = { A, B, C }.  B present.  ok
    B -> C :  B+ under F = { B, C }.     C present.  ok
    -> yes

  DOES G COVER F?
    A -> B :  A+ under G = { A, B, C }.  B present.  ok
    B -> C :  B+ under G = { B, C }.     C present.  ok
    A -> C :  A+ under G = { A, B, C }.  C present.  ok
    -> yes

  EQUIVALENT. A -> C in F is redundant: transitivity
  already derives it from the other two.

Minimal cover

A minimal cover (also canonical cover) of F is an equivalent set that is as small as possible. It satisfies three conditions:

1. Every right hand side has exactly one attribute.
2. No dependency has a redundant attribute on the left.
3. No whole dependency is redundant.

The three step algorithm

  STEP 1  SPLIT right hand sides
            replace  X -> A B C  with
                     X -> A, X -> B, X -> C
            (valid by the decomposition rule)

  STEP 2  REMOVE redundant LEFT hand attributes
            for each  X -> A  where X has 2 or more attributes
              for each attribute b in X
                compute ( X minus b )+ using the CURRENT set
                if A is inside it, b was unnecessary - drop it

  STEP 3  REMOVE redundant DEPENDENCIES
            for each  X -> A  in the set
              temporarily remove it
              compute X+ using the REMAINING dependencies
              if A is still reachable, the dependency was
              redundant - leave it out permanently
              otherwise put it back

Order matters: split first, then reduce left sides, then remove whole dependencies. Doing step 3 before step 2 can leave a dependency that a shorter one would have made redundant.

Fully worked example

  R ( A, B, C, D )
  F = {  A    -> B C
      ,  B    -> C
      ,  A    -> B
      ,  A B  -> C
      ,  A C  -> D  }

  ---------------------------------------------------------
  STEP 1  split right hand sides

    A   -> B
    A   -> C
    B   -> C
    A   -> B          duplicate of the first, drop
    A B -> C
    A C -> D

  working set:
    1  A   -> B
    2  A   -> C
    3  B   -> C
    4  A B -> C
    5  A C -> D

  ---------------------------------------------------------
  STEP 2  remove redundant LEFT attributes

    dependency 4:  A B -> C
      try dropping B:  A+ = { A, B, C, D }  contains C
        -> B is redundant, becomes  A -> C
        which duplicates 2, so drop 4 entirely
      (had it not duplicated, we would keep the shorter form)

    dependency 5:  A C -> D
      try dropping C:  A+ = { A, B, C, D }  contains D
        -> C is redundant, becomes  A -> D
      try dropping A from the ORIGINAL: C+ = { C } - no D
        -> A was needed

  working set:
    1  A -> B
    2  A -> C
    3  B -> C
    5  A -> D

  ---------------------------------------------------------
  STEP 3  remove redundant DEPENDENCIES

    test 1  A -> B
      remove it. Using { A -> C, B -> C, A -> D }
      A+ = { A, C, D }.  B NOT reachable.
      -> keep it.

    test 2  A -> C
      remove it. Using { A -> B, B -> C, A -> D }
      A+ = { A, B, C, D }.  C IS reachable, via B.
      -> REDUNDANT, drop permanently.

    test 3  B -> C
      remove it. Using { A -> B, A -> D }
      B+ = { B }.  C not reachable.
      -> keep it.

    test 5  A -> D
      remove it. Using { A -> B, B -> C }
      A+ = { A, B, C }.  D not reachable.
      -> keep it.

  ---------------------------------------------------------
  MINIMAL COVER

    Fc = { A -> B, B -> C, A -> D }

  From five dependencies down to three.

  VERIFY equivalence: under Fc,
    A+ = { A, B, C, D }, which still gives A -> B C and
    A C -> D. Nothing was lost.

Why minimal cover matters

• 3NF decomposition uses it directly. The synthesis algorithm creates one relation per dependency in the minimal cover, so a smaller cover means fewer, cleaner relations.
• It reveals genuine redundancy in a stated rule set, which often exposes a misunderstanding in the requirement.
• Fewer constraints to enforce. Redundant dependencies cost checking effort for no benefit.

A minimal cover is not always unique

  F = { A -> B, B -> A, A -> C, B -> C }

  Removing A -> C gives  { A -> B, B -> A, B -> C }
  Removing B -> C gives  { A -> B, B -> A, A -> C }

  Both are minimal covers, and both are equivalent to F.
  The order in which step 3 tests dependencies decides
  which one you get. Either is a correct answer, and saying
  so earns the mark.

Common mistakes

• Using the original F in step 3. Redundancy must be tested against the remaining dependencies, updated as you go.
• Doing the steps out of order. Split, then left sides, then whole dependencies.
• Removing two dependencies at once. Test one at a time; removing one can make another necessary.
• Leaving multi attribute right hand sides. Step 1 is compulsory.
• Assuming the answer is unique. It often is not.
• Checking equivalence in one direction only. Both directions are required.

Exam and interview questions

1. How do you test whether two dependency sets are equivalent?
2. State the three conditions a minimal cover must satisfy.
3. Write the three step algorithm for computing a minimal cover.
4. Why must step 3 use the remaining dependencies rather than the original set?
5. Is a minimal cover unique? Give an example supporting your answer.

Practice

1. Find the minimal cover of F = { A -> B C, B -> C, A -> B, A B -> C }.
2. Find the minimal cover of F = { A -> B, A B C -> D, E F -> G, E F -> H, A C D -> B }.
3. Are F = { A -> B, B -> C } and G = { A -> B, A -> C, B -> C } equivalent? Show both directions.
4. Construct a dependency set with two different minimal covers.

Conclusion

Two sets are equivalent when each covers the other, tested with closure in both directions. A minimal cover splits right hand sides, trims left hand sides, then removes whole redundant dependencies — in that order — and it is the input Phase 8 needs for 3NF decomposition.