Closure of Attributes

Definition

The closure of an attribute set X, written X+, is the set of all attributes functionally determined by X — directly or transitively — given a set of functional dependencies F. Computing closures is the core mechanical tool used to derive candidate keys (21.10) and minimal covers (21.11).

Algorithm: Start with result = X. Repeatedly scan the FD set: whenever some FD's left-hand side is already a subset of result, add its right-hand side to result. Stop when a full pass adds nothing new.

The FD Set for the Running Example

F1: StudentID -> StudentName
F2: CourseID -> CourseName
F3: CourseID -> InstructorID
F4: InstructorID -> InstructorName
F5: InstructorID -> InstructorOffice
F6: {StudentID, CourseID} -> EnrollmentDate

Worked Computation 1: {CourseID}+

• Start: result = {CourseID}
• F2 applies (CourseID subset of result) -> add CourseName: result = {CourseID, CourseName}
• F3 applies -> add InstructorID: result = {CourseID, CourseName, InstructorID}
• F4 applies (InstructorID now in result) -> add InstructorName: result = {CourseID, CourseName, InstructorID, InstructorName}
• F5 applies -> add InstructorOffice: result = {CourseID, CourseName, InstructorID, InstructorName, InstructorOffice}
• No more FDs apply (F1 needs StudentID, F6 needs StudentID too). Stop.

{CourseID}+ = {CourseID, CourseName, InstructorID, InstructorName, InstructorOffice} — five attributes, missing StudentID, StudentName, EnrollmentDate. Not all eight attributes, so CourseID alone does not determine everything.

Worked Computation 2: {StudentID, CourseID}+

• Start: result = {StudentID, CourseID}
• F1 applies -> add StudentName
• F2 applies -> add CourseName
• F3 applies -> add InstructorID
• F4 applies -> add InstructorName
• F5 applies -> add InstructorOffice
• F6 applies (both StudentID and CourseID now in result) -> add EnrollmentDate
• result = {StudentID, CourseID, StudentName, CourseName, InstructorID, InstructorName, InstructorOffice, EnrollmentDate} — all eight attributes.

{StudentID, CourseID}+ = the entire attribute set of the relation.

Worked Computation 3: {StudentID, InstructorID}+

• Start: result = {StudentID, InstructorID}
• F1 applies -> add StudentName
• F4 applies -> add InstructorName
• F5 applies -> add InstructorOffice
• No FD has a left-hand side that is a subset of {StudentID, InstructorID, StudentName, InstructorName, InstructorOffice} and yields something new — CourseID is never produced because nothing in F determines CourseID from InstructorID (one instructor can teach multiple courses in general; only F3 goes CourseID -> InstructorID, not the reverse). Stop.

{StudentID, InstructorID}+ = {StudentID, InstructorID, StudentName, InstructorName, InstructorOffice} — missing CourseID, CourseName, EnrollmentDate. Not all attributes.

Why This Matters

Closure computation is exactly how you prove, rather than guess, whether an attribute set is a candidate key (21.10): X is a candidate key if and only if X+ equals the full attribute set, and no proper subset of X also has that property.

Edge Cases

• Order of applying FDs during the scan doesn't affect the final result — closure is deterministic regardless of the sequence in which applicable FDs are triggered, only requiring you repeat passes until nothing new is added.
• A common mistake is stopping too early — you must keep re-scanning the entire FD list on every pass, because an FD that didn't apply initially (like F4, F5 needing InstructorID) may become applicable only after an earlier FD (F3) adds InstructorID to the result.

Key Takeaways / Interview Angle

• Q: What is X+? The complete set of attributes functionally determined by X, directly or transitively, under a given FD set.
• Q: What does it mean if X+ equals all attributes of the relation? X is a superkey — enough to identify every attribute in the relation uniquely (candidate-key status additionally requires minimality, see 21.10).
• Q: Compute {CourseID}+ for the running example. {CourseID, CourseName, InstructorID, InstructorName, InstructorOffice} — it reaches the instructor chain transitively but never reaches StudentID/StudentName/EnrollmentDate.