Attribute Closure and Candidate-Key Reasoning

Learning outcomes

Attribute closure is a practical algorithm for answering: “Given this set of attributes and these functional dependencies, what else can I determine?” Closure lets us test superkeys, find candidate keys, and reason about whether one dependency follows from others.

Definition of attribute closure

Given a set of functional dependencies F, the closure of X, written \(X^+\), is the set of all attributes functionally determined by X under F.

The closure algorithm

1. Start with \(X^+ = X\).
2. Find any dependency \(A \rightarrow B\) where \(A \subseteq X^+\).
3. Add B to \(X^+\).
4. Repeat until no new attributes can be added.

Simple example

Relation:

\[ R(A,B,C,D) \]

Dependencies:

\[ A \rightarrow B \]

\[ B \rightarrow C \]

\[ C \rightarrow D \]

Compute \(A^+\):

Start: {A}A -> B  => {A,B}B -> C  => {A,B,C}C -> D  => {A,B,C,D}

Therefore A determines every attribute in R and is a superkey.

Testing a superkey

X is a superkey of R if:

\[ X^+ = R \]

meaning its closure contains every attribute in the relation.

Testing minimality

A candidate key is a minimal superkey. If X is a superkey, remove one attribute at a time and recompute closure. If a smaller subset still determines all attributes, X was not minimal.

Composite-key example

Relation:

\[ R(Student, Course, Term, Grade, Instructor) \]

Dependencies:

\[ (Student,Course,Term) \rightarrow Grade \]

\[ (Course,Term) \rightarrow Instructor \]

Closure of \((Student,Course,Term)\):

{Student, Course, Term}+ Grade+ Instructor= all attributes

It is a superkey.

Can Course + Term be the key?

\[ (Course,Term)^+ \]

contains Course, Term, Instructor—but not Student or Grade. Therefore it is not a superkey.

Attributes that never appear on a right-hand side

A useful candidate-key heuristic: if an attribute never appears on the right side of any non-trivial dependency, nothing else can derive it. Therefore every candidate key must include it unless another dependency omitted from the set determines it.

WorkshopHub example

Suppose relation:

RepairRecord(  work_order_id,  technician_id,  started_at,  employee_number,  technician_name,  asset_id)

Dependencies:

\[ (work\_order\_id, technician\_id, started\_at) \rightarrow employee\_number, technician\_name, asset\_id \]

\[ technician\_id \rightarrow employee\_number, technician\_name \]

\[ work\_order\_id \rightarrow asset\_id \]

Closure of the assignment key

Start with:

{work_order_id, technician_id, started_at}

Using technician_id gives employee_number and technician_name. Using work_order_id gives asset_id. Therefore the closure includes every attribute. The triple is a superkey.

Why the closure exposes redundancy

The closure calculation shows that some attributes are determined by only subsets of the composite key:

technician_id -> employee_number, technician_namework_order_id -> asset_id

This is exactly the dependency structure that normalization will separate.

Testing whether a dependency is implied

To test whether \(X \rightarrow Y\) follows from F:

1. Compute \(X^+\) under F.
2. If \(Y \subseteq X^+\), then the dependency is implied.

Armstrong's axioms

Functional dependencies can be derived using three fundamental inference rules:

• Reflexivity: if \(Y \subseteq X\), then \(X \rightarrow Y\).
• Augmentation: if \(X \rightarrow Y\), then \(XZ \rightarrow YZ\).
• Transitivity: if \(X \rightarrow Y\) and \(Y \rightarrow Z\), then \(X \rightarrow Z\).

Closure provides an operational way to use the consequences of these rules.

Derived inference rules

Common consequences include:

• Union: if \(X \rightarrow Y\) and \(X \rightarrow Z\), then \(X \rightarrow YZ\).
• Decomposition: if \(X \rightarrow YZ\), then \(X \rightarrow Y\) and \(X \rightarrow Z\).
• Pseudotransitivity: if \(X \rightarrow Y\) and \(WY \rightarrow Z\), then \(WX \rightarrow Z\).

Candidate-key workflow

1. List all relation attributes.
2. List trustworthy business functional dependencies.
3. Identify attributes not derivable from others.
4. Build candidate determinant sets.
5. Compute closures.
6. Remove unnecessary attributes to establish minimality.

Practice: closure computation

Summary and next lesson

Attribute closure turns dependency reasoning into a repeatable algorithm. It lets you test superkeys, candidate keys, and implied dependencies. The final lesson of Chapter 7 uses those ideas to judge decompositions: can the original relation be reconstructed without spurious rows, and can important dependencies still be enforced efficiently?

References

• Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems.
• Jeffrey Ullman and Jennifer Widom, A First Course in Database Systems.
• C. J. Date, Database Design and Relational Theory.