In-Depth Notes on Attribute Closure and Functional Dependency Closure

Keys

  • Superkey

    • Definition: A set of one or more attributes that can uniquely identify the rest of the attributes of a relation.
    • Examples:
    • (EmpID, EmpName)
    • (Emp_ID, DOB)
    • (Emp_ID, Gender)
    • (EmpID, DeptNo)
    • (Emp_Name, DOB)
    • (Emp_Name, DOB, Gender)

  • Candidate Key

    • Definition: A minimal superkey, meaning no proper subset can uniquely identify a tuple.
    • Example: Emp_ID

  • Primary Key

    • Definition: A chosen candidate key that uniquely identifies tuples in a relation and cannot contain NULL values.
    • Examples: EmpID, InsuranceID, DrivingLicenceID

Attribute Closure

  • Definition: The attribute closure of a set of attributes X, denoted as X+, includes all attributes functionally determined by X based on a given set of functional dependencies (FDs) in a relational database.

  • Importance:

    • Checking Super Keys: Helps verify if a set of attributes qualifies as a super key.
    • Determining Candidate Keys: Aids in identifying candidate keys for a relation.
    • Functional Dependency Validation: Used to check if a functional dependency X→Y is valid in a relation.
    • Normalization: A benchmark for minimizing redundancy in database structures.

Attribute Closure Example

  • Example Relation: R(A, B, C) with FDs:
    • A→B
    • B→C
  • Finding Closure of A (A+):
    • Start: A+ = {A}
    • Add B due to A→B: A+ = {A, B}
    • Add C due to B→C: A+ = {A, B, C}
  • Conclusion: A+ = {A, B, C}, hence A is a super key.

Attribute Closure Algorithm

  1. Initialization: Begin with X+ = X
  2. Expansion: For each functional dependency A→B, if A is a subset of X+, append B to X+.
  3. Repeat: Keep repeating the process until no new attributes can be added.
  4. Output: The final output is X+, containing all attributes determined by X.

Further Examples

  • Consider R(A, B, C, D) with FDs:

    • A→B
    • B→C
    • AC→D

  • Finding A+:

    • Start: A+ = {A}
    • A→B: Add B → A+
    • B→C: Add C → A+
    • Result: A+ = {A, B, C}, hence A is not a super key.

  • Finding (AC)+:

    • Start: (AC)+ = {A, C}
    • A→B: Add B → (AC)+
    • AC→D: Add D → (AC)+
    • Result: (AC)+ includes all attributes, thus AC is a super key.

Functional Dependency Closure

  • Definition: The concept involves identifying the closure of functional dependencies within a set, ensuring no redundancy or extraneous attributes exist while maintaining the original dependencies.

  • Canonical Cover:

    • Definition: A simplified equivalent set of functional dependencies ensuring:
    • No redundant dependencies
    • No extraneous attributes
    • Each dependency has a single attribute on the right-hand side.

  • Approach to Canonical Cover:

    1. Make Right Side Atomic: Break down dependencies like A→BC into A→B and A→C.
    2. Remove Extraneous Attributes: Check if removing attributes from the left-hand side preserves dependencies.
    3. Remove Redundant FDs: If an FD can be implied by others, it should be removed. For instance, if A→B, B→C infers A→C, then A→C is redundant.