algorithm for computing closure of a set of FDs

dbmonster picture dbmonster · Jun 11, 2013 · Viewed 7.6k times · Source

I'm looking for an easy to understand algorithm to compute (by hand) a closure of a set of functional dependencies. Some sources, including my instructor says I should just play with Armstrong's axioms and see what I can get at. To me, that's not a systematic way about doing it (i.e. easy to miss something).

Our course textbook (DB systems - the complete book, 2nd ed) doesn't give an algorithm for this either.

Answer

Max.Mirkia picture Max.Mirkia · Feb 7, 2014

To put it in more "systematic" fashion, this could be the algorithm you are looking for. Using the first three Armstrong's Axioms:

  • Closure = S
  • Loop
    • For each F in S, apply reflexivity and augmentation rules
    • Add the new FDs to the Closure
    • For each pair of FDs in S, apply the transitivity rule
    • Add the new Fd to Closure
  • Until closure doesn't change any further`

Which I took from this presentation notes. However, I found the following approach way easier to implement:

  • /*F is a set of FDs */
  • F⁺ = empty set
  • for each attribute set X
    • compute the closure X⁺ of X on F
    • for each attribute A in X⁺
      • add to F⁺ the FD: X -> A
  • return F⁺

which is taken from here