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:
- Initialize: Start with X⁺ = X (you always know X from itself)
- 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⁺
- Repeat: Keep scanning all FDs until no new attributes can be added
- 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
Ais in our set andA → B, addB:{A}⁺ = {A, B} - Since
Bis in our set andB → C, addC:{A}⁺ = {A, B, C} - Check
CD → E: We don't haveD, 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.