Attribute Closure $X^+$ with Respect to Functional Dependencies $F$: Definition and Algorithm

In relational database theory, the attribute closure $X^+$ (also written as $X_F^+$ when emphasizing dependence on $F$) is the set of all attributes that are functionally determined by a starting set of attributes $X$ using a set of functional dependencies (FDs) $F$. Formally, $X^+$ is the set of attributes $A$ such that $F \models X \to A$ (i.e., $X \to A$ is logically implied by $F$).

A core motivation is that once you compute $X^+$, you can answer common reasoning tasks:

• Does $F \models X \to Y$? (Equivalent to $Y \subseteq X^+$)
• Find implied dependencies and support lossless reasoning for keys.
• Test candidate keys by checking whether some $X^+$ contains all attributes.

Key terms introduced here:

• Attribute closure
• Functional dependency (FD)
• Logical implication of FDs
• Key
• FD implication test

Definition (what $X^+$ means)

Given:

• attribute sets $X, Y, Z,\dots$
• a set of FDs $F$

the attribute closure $X^+$ is:

In other words, $X^+$ contains exactly those attributes $A$ that you can derive as consequences of applying FDs in $F$, starting from the assumption that $X$ holds.

A practical corollary:

• $F \models X \to Y$ iff $Y \subseteq X^+$.

This equivalence is the main “reasoning hook” for closure-based algorithms.

[CalloutBlock]
type: "tip"
title: "How to think about closure"
content: "Compute $X^+$ as “everything you can force to be equal (determined) if you know $X$.” If $Y$ is inside $X^+$, then $X$ determines $Y$ under $F$."

Why the closure algorithm works (intuition)

The standard closure computation repeatedly applies FDs whose left-hand sides are already “known” to be determined. Concretely:

1. Start with $X^+$ containing the initially known attributes $X$.
2. If an FD $U \to V$ in $F$ has $U \subseteq X^+$, then you can conclude $V \subseteq X^+$.
3. Repeat until no more attributes can be added.

This is essentially computing a fixed point of repeated rule application, matching the semantics of logical implication for FDs (via Armstrong-style derivations).

Key terms:

• Fixed point
• Repeated application
• Termination
• Minimal augmentation step
• Monotonicity

“Commuting” $X^+$ for $X$ (order-independence / correctness idea)

In many courses, “commuting” here refers to the fact that the order in which FDs are applied does not affect the final closure: regardless of which eligible FD you apply first, you still reach the same fixed point $X^+$.

You can view the algorithm as follows:

• At any time, the current working set $S$ (initially $S=X$) satisfies $S \subseteq X^+$.
• Each time you apply an FD $U \to V$ with $U \subseteq S$, you enlarge $S$ to $S \cup V$ while preserving $S \subseteq X^+$.
• Because $S$ only grows and there are finitely many attributes, the algorithm terminates.
• Once you reach a fixed point (no FD left with LHS contained), that fixed point must equal the least such fixed point—i.e., the true closure $X^+$.

This yields the “commuting” property:

• Different application orders of eligible FDs commute to the same final closure.

[CalloutBlock]
type: "warning"
title: "Common mistake"
content: "Do not stop after a single pass over $F$. Newly added attributes can enable additional FDs later, so you must iterate until no more attributes can be added."

Worked micro-example (closure computation)

Suppose:

• $F = \{ A \to B,\; B \to C,\; A \to D \}$
• $X = \{A\}$

Compute:

• Start: $X^+ = \{A\}$
• Apply $A \to B$: $X^+ = \{A,B\}$
• Apply $B \to C$: $X^+ = \{A,B,C\}$
• Apply $A \to D$: $X^+ = \{A,B,C,D\}$
  No further FDs add attributes, so $X^+ = \{A,B,C,D\}$.

Thus $F \models A \to C$ and $F \models A \to D$, and so on.