Attribute Closure, Step by Step

Concept

The closure of an attribute set X under a set of dependencies F, written X+, is the set of all attributes that can be determined from X using F.

Closure is the workhorse of this entire phase. Three separate exam questions reduce to it:

The algorithm

  COMPUTE X+ under F

  1. result := X                      start with X itself
  2. repeat
       for each dependency  A -> B  in F
         if A is a SUBSET of result
           result := result union B
     until result stops changing
  3. return result

  The only condition to check is: is the ENTIRE left hand
  side already inside result? If yes, add the right hand
  side. If any part of the left hand side is missing, that
  dependency cannot be used yet.

Worked example 1

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

  COMPUTE A+

    start          A+ = { A }

    pass 1
      A -> B       A is in result        add B    -> { A, B }
      B -> C       B is in result        add C    -> { A, B, C }
      C D -> E     D is MISSING          skip
      E -> A       E is missing          skip
      changed, so go round again

    pass 2
      A -> B       already have B
      B -> C       already have C
      C D -> E     D still missing       skip
      E -> A       E still missing       skip
      no change -> STOP

    A+ = { A, B, C }

  A+ is not all of R, so A is NOT a super key.

Worked example 2

  Same R and F.  COMPUTE (A D)+

    start                AD+ = { A, D }

    pass 1
      A -> B      A present       add B    -> { A, B, D }
      B -> C      B present       add C    -> { A, B, C, D }
      C D -> E    BOTH present    add E    -> { A, B, C, D, E }
      E -> A      already have A
      changed -> go again

    pass 2
      nothing new -> STOP

    (A D)+ = { A, B, C, D, E } = R

  So { A, D } IS a super key.

  Is it a candidate key? Check minimality by removing one
  attribute at a time:

    A+ = { A, B, C }        not all of R
    D+ = { D }              not all of R

  Neither subset is a super key, so { A, D } is MINIMAL
  and therefore a CANDIDATE KEY.

Worked example 3 — using closure to test a dependency

  Does  A D -> E  follow from F?

    (A D)+ = { A, B, C, D, E }
    Is E inside it?  YES
    -> the dependency A D -> E is implied by F.

  Does  B -> A  follow from F?

    B+ :  start { B }
          B -> C   add C     -> { B, C }
          C D -> E D missing, skip
          no change -> STOP
    B+ = { B, C }
    Is A inside it?  NO
    -> B -> A does NOT follow from F.

  This is the whole technique for "is this dependency
  implied?" questions. No axioms needed - just closure.

Worked example 4 — a longer one

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

  COMPUTE (A B)+

    start                { A, B }
    A B -> C   present   { A, B, C }
    C -> D E   present   { A, B, C, D, E }
    E -> F     present   { A, B, C, D, E, F }
    D -> B     already have B
    (A B)+ = all of R    -> SUPER KEY

    minimal?  A+ = { A }      no
              B+ = { B }      no
    -> { A, B } is a CANDIDATE KEY

  COMPUTE (A D)+

    start                { A, D }
    A B -> C   B missing, skip
    C -> D E   C missing, skip
    E -> F     E missing, skip
    D -> B     present   { A, B, D }
    changed, go again
    A B -> C   NOW present  { A, B, C, D }
    C -> D E   present      { A, B, C, D, E }
    E -> F     present      { A, B, C, D, E, F }
    (A D)+ = all of R    -> SUPER KEY

    minimal?  A+ = { A }  no
              D+ = { B, D }  no
    -> { A, D } is ALSO a candidate key

  Two candidate keys. Note how the second pass mattered:
  D -> B supplied the B that unlocked A B -> C. Stopping
  after one pass is the most common error in this topic.

Properties worth knowing

• X is always a subset of X+. Closure never loses attributes.
• If X is a subset of Y then X+ is a subset of Y+. Adding attributes never determines less.
• (X+)+ = X+. Closure applied twice adds nothing.
• X -> Y follows from F exactly when Y is a subset of X+.
• X is a super key exactly when X+ = R.

Common mistakes

• Stopping after one pass. Keep looping until nothing changes; example 4 shows why.
• Using a dependency with only part of its left hand side present. C D -> E needs both C and D.
• Forgetting to include X itself. Closure starts with X.
• Claiming a super key is a candidate key without testing minimality. Remove each attribute and recompute.
• Applying the arrow backwards. E -> A lets you add A when you already have E, never the reverse.

Exam and interview questions

1. Define attribute closure and write the algorithm.
2. Compute A+ and (A D)+ for the set in worked example 1.
3. How do you test whether X -> Y is implied by F, using closure?
4. How do you test whether X is a super key, and then a candidate key?
5. Why must the algorithm repeat until no change occurs?

Practice

1. R(A,B,C,D) with F = { A -> B, B -> C, C -> D }. Compute A+, B+, C+ and D+.
2. R(A,B,C,D,E) with F = { A -> B C, C D -> E, B -> D, E -> A }. Compute (A)+ and (C D)+.
3. Using set 2, decide whether C D -> A is implied.
4. Using set 2, find one candidate key and prove its minimality.

Conclusion

Closure is one short loop that answers three different exam questions. Start with X, repeatedly add the right hand side of any dependency whose entire left hand side you already hold, and stop only when a full pass adds nothing.