Course contentsShow
← Computer Science
Lesson 1628 of 2,87237. Database Design and NormalizationFree lesson

Closure of Attribute Sets

Computing the closure X+ to find all attributes functionally determined by a set X using inference rules iteratively.

Closure of Attribute Sets

What you'll learn: How to compute the closure X⁺ to discover all attributes that can be functionally determined from a given set X.

The Core Idea

The closure of an attribute set X (written as X⁺) is the complete set of attributes that can be functionally determined from X using all known functional dependencies. Think of it as answering: "If I know values for attributes in X, what else can I figure out?"

Computing the closure is like following a chain of implications. You start with what you know (X), then repeatedly apply inference rules (Armstrong's Axioms and derived rules) to discover new attributes until no more can be found.

The Algorithm

Here's the iterative process:

  1. Initialize: Start with X⁺ = X (you always know X from itself)
  2. Iterate: For each functional dependency A → B in your set:
    • If A is a subset of your current X⁺, add all attributes from B to X⁺
  3. Repeat: Keep scanning all FDs until no new attributes can be added
  4. Done: The final X⁺ is your closure

Example Walkthrough

Given FDs: {A → B, B → C, CD → E}

To find the closure of {A}:

  • Start: {A}⁺ = {A}
  • Since A is in our set and A → B, add B: {A}⁺ = {A, B}
  • Since B is in our set and B → C, add C: {A}⁺ = {A, B, C}
  • Check CD → E: We don't have D, so we can't use this rule
  • No more attributes can be added
  • Result: {A}⁺ = {A, B, C}

Why This Matters

Closure computation is foundational for finding candidate keys, testing if one FD is implied by others, and verifying normal forms during database design.

Key Takeaway: The closure X⁺ is computed iteratively by starting with X and repeatedly applying all functional dependencies until no new attributes can be determined.