Canonical Cover - Learning Module

Loading content...

0/252

Extraneous Attributes: Identifying Unnecessary Elements

The Hidden Bloat in Functional Dependencies

Functional dependencies don't always express constraints as concisely as they could. Consider the FD ABC → D. At first glance, this seems to say that attributes A, B, and C together determine D. But what if AB → D is also true? Then including C on the left-hand side is unnecessary—C is extraneous.

Extraneous attributes are attributes that can be removed from an FD without changing the closure of the FD set. They represent hidden bloat—unnecessary complexity that obscures the true structure of your data's constraints. Identifying and removing extraneous attributes is a crucial step in computing a canonical cover.

This page provides a rigorous treatment of extraneous attributes: what they are, how to detect them, and why their removal is essential for database design.

What You Will Learn

By the end of this page, you will understand the formal definitions of extraneous attributes on both the left-hand side and right-hand side of FDs. You will master the algorithms for detecting extraneous attributes, work through multiple examples, and understand why this process is essential for canonical cover computation.

What Are Extraneous Attributes?

An extraneous attribute is an attribute in a functional dependency that can be removed without changing the closure of the FD set. There are two distinct cases:

Extraneous Attribute on the Left-Hand Side (LHS):

Attribute A is extraneous on the LHS of X → Y if:

A ∈ X (A is part of the determinant)
Y can still be derived using (X - {A}) under the original FD set

Formally: A is extraneous in X → Y on the LHS if Y ⊆ (X - {A})⁺ under F.

Extraneous Attribute on the Right-Hand Side (RHS):

Attribute A is extraneous on the RHS of X → Y if:

A ∈ Y (A is part of the dependent)
A can be derived from X using the remaining FDs

Formally: A is extraneous in X → Y on the RHS if A ⊆ X⁺ under (F - {X → Y}) ∪ {X → (Y - {A})}.

Alternatively: A is extraneous in X → Y on the RHS if A ⊆ X⁺ under (F - {X → A}) when RHS is already decomposed to single attributes.

Key Insight

The fundamental question is always the same: 'Can I derive the same things without this attribute?' If yes, the attribute is extraneous. If no, the attribute is essential.

Extraneous Attributes Summary
Type	Example	Condition for A Being Extraneous	Intuition
LHS Extraneous	`ABC → D` where `AB → D` holds	D ⊆ (AB)⁺ under F	C isn't needed to determine D
RHS Extraneous	`A → BC` where `A → C` is derivable elsewhere	C ⊆ A⁺ under F - {A → C}	C is determined through other FDs

Left-Hand Side Extraneous Attributes

An attribute A is extraneous on the left-hand side of an FD X → Y if removing A from X still allows Y to be determined—either by the reduced determinant directly or through inference using other FDs in the set.

Formal Definition:

Let F be a set of FDs, and let X → Y be an FD in F where A ∈ X.

A is extraneous in X → Y (on the LHS) if:

Y ⊆ (X - {A})⁺ under F

Intuition:

Compute the closure of X without A, using all FDs in F (including X → Y itself). If Y is in this closure, then A is extraneous—it's not contributing anything that can't be derived without it.

Example 1:

F = {A → C, AB → C}

Is B extraneous in AB → C?

Remove B: reduced determinant is {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → C: {A, C}
Is C in {A, C}? Yes!
Conclusion: B is extraneous in AB → C.

Example 2:

F = {A → B, BC → D, AC → D}

Is C extraneous in AC → D?

Remove C: reduced determinant is {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → B: {A, B}
Is D in {A, B}? No!
Conclusion: C is NOT extraneous in AC → D.

lhs_extraneous_algorithm.txt
ALGORITHM: Test if attribute A is extraneous on LHS of X → Y in F
 
INPUT:
  F: set of functional dependencies
  X → Y: an FD in F
  A: an attribute in X
 
OUTPUT:
  true if A is extraneous, false otherwise
 
PROCEDURE:
1. Let X' = X - {A}           // Remove A from determinant
2. Compute (X')⁺ under F      // Closure includes ALL FDs in F
3. If Y ⊆ (X')⁺:
     return true              // A is extraneous
   Else:
     return false             // A is essential
 
NOTE: We use the ORIGINAL F (including X → Y) for closure computation.
This is critical—other FDs in F might contribute to deriving Y.

Common Mistake

When testing LHS extraneous attributes, use the full F (including the FD being tested). The question is whether the attribute is needed given the entire FD set, not whether the FD itself is redundant.

Right-Hand Side Extraneous Attributes

An attribute A is extraneous on the right-hand side of an FD X → Y if removing A from Y doesn't change the overall closure—meaning A can be derived from X through other FDs in the set.

Formal Definition:

Let F be a set of FDs, and let X → Y be an FD in F where A ∈ Y.

A is extraneous in X → Y (on the RHS) if:

A ∈ X⁺ under F' where F' = (F - {X → Y}) ∪ {X → (Y - {A})}

This is equivalent to: we replace X → Y with X → (Y - {A}) and check if A is still in the closure of X.

When RHS Has Single Attribute (canonical form):

If we've already decomposed to single-attribute RHS, then:

A is extraneous in X → A if A ∈ X⁺ under (F - {X → A})

This simpler form asks: can we derive A from X without using X → A?

Example 1:

F = {A → B, B → C, A → C}

Is C extraneous in A → C? (Assuming single-attribute RHS)

Consider F' = F - {A → C} = {A → B, B → C}
Compute A⁺ under F':
- Start: {A}
- Apply A → B: {A, B}
- Apply B → C: {A, B, C}
Is C in {A, B, C}? Yes!
Conclusion: C is extraneous in A → C. The FD is redundant.

Example 2:

F = {A → B, A → C}

Is B extraneous in A → B?

Consider F' = F - {A → B} = {A → C}
Compute A⁺ under F':
- Start: {A}
- Apply A → C: {A, C}
Is B in {A, C}? No!
Conclusion: B is NOT extraneous in A → B.

rhs_extraneous_algorithm.txt
ALGORITHM: Test if attribute A is extraneous on RHS of X → Y in F
 
INPUT:
  F: set of functional dependencies
  X → Y: an FD in F
  A: an attribute in Y
 
OUTPUT:
  true if A is extraneous, false otherwise
 
PROCEDURE:
1. Let F' = (F - {X → Y}) ∪ {X → (Y - {A})}
   // Replace original FD with reduced version
2. Compute X⁺ under F'
3. If A ∈ X⁺:
     return true              // A is extraneous
   Else:
     return false             // A is essential
 
SIMPLIFIED (when Y has single attribute A):
1. Let F' = F - {X → A}       // Simply remove the FD
2. Compute X⁺ under F'
3. If A ∈ X⁺:
     return true              // FD is redundant
   Else:
     return false             // FD is essential
 
NOTE: We use the MODIFIED F' (without the FD or with reduced FD).
This checks if the attribute can be derived through OTHER paths.

Critical Difference from LHS Testing

For LHS extraneous testing, use the ORIGINAL F. For RHS extraneous testing, use the MODIFIED F'. This difference is crucial—mixing them up leads to incorrect results.

Detailed Worked Examples

Let's work through comprehensive examples that illustrate both LHS and RHS extraneous attribute detection.

Example Set:

F = {
  A → BC,
  B → C,
  AB → D,
  D → E,
  CE → A
}

First, let's decompose to single-attribute RHS:

F = {
  A → B,      (1)
  A → C,      (2)
  B → C,      (3)
  AB → D,     (4)
  D → E,      (5)
  CE → A      (6)
}

Testing if A is extraneous in AB → D:

Remove A from determinant: X' = {B}
Compute B⁺ under F:
- Start: {B}
- Apply B → C (3): {B, C}
Is D in {B, C}? No
Conclusion: A is NOT extraneous in AB → D.

Testing if B is extraneous in AB → D:

Remove B from determinant: X' = {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → B (1): {A, B}
- Apply A → C (2): {A, B, C}
- Apply B → C (3): {A, B, C} (no change)
- Apply AB → D (4): {A, B, C, D}
- Apply D → E (5): {A, B, C, D, E}
Is D in {A, B, C, D, E}? Yes!
Conclusion: B IS extraneous in AB → D.

We can replace AB → D with A → D without losing any derivable FDs!

Systematic Testing Procedure

To find all extraneous attributes in an FD set, we must systematically test each attribute in each FD. Here's a structured approach:

Step 1: Decompose to Single-Attribute RHS

Replace each FD X → Y₁Y₂...Yₙ with n FDs:

X → Y₁
X → Y₂
...
X → Yₙ

This simplifies RHS extraneous testing to testing FD redundancy.

Step 2: Test Each LHS Attribute in Each FD

For each FD X → A where |X| > 1:

For each B ∈ X:
- Compute (X - {B})⁺ under F
- If A is in the closure, B is extraneous
- If found extraneous, remove B from X in the FD

Step 3: Test Each FD for Redundancy (RHS Extraneous)

For each FD X → A:

Compute X⁺ under (F - {X → A})
If A is in the closure, the FD is redundant
If redundant, remove the entire FD from F

Important: Order Matters

Removing one extraneous attribute may make another attribute extraneous (or essential) that wasn't before. Therefore:

Continue testing until no more extraneous attributes are found
Different orderings may produce different (valid) minimal covers

systematic_extraneous_removal.txt
ALGORITHM: Remove All Extraneous Attributes
 
INPUT: F (set of functional dependencies)
OUTPUT: F with all extraneous attributes removed
 
// Step 1: Decompose RHS to single attributes
FOR each (X → Y) in F where |Y| > 1:
    Remove (X → Y) from F
    FOR each A in Y:
        Add (X → A) to F
 
// Step 2: Remove extraneous LHS attributes
changed = true
WHILE changed:
    changed = false
    FOR each (X → A) in F where |X| > 1:
        FOR each B in X:
            X' = X - {B}
            IF A ∈ closure(X', F):
                Replace (X → A) with (X' → A) in F
                changed = true
                BREAK  // Restart outer loop
 
// Step 3: Remove redundant FDs
changed = true
WHILE changed:
    changed = false
    FOR each (X → A) in F:
        F' = F - {X → A}
        IF A ∈ closure(X, F'):
            F = F'
            changed = true
            BREAK  // Restart loop
 
RETURN F

Efficiency Tip

In practice, test LHS extraneous attributes first (Step 2) before testing FD redundancy (Step 3). Simplifying determinants often makes it easier to detect redundant FDs, as the simplified FDs are more likely to be derivable from others.

Why Processing Order Affects the Result

A subtle but important point: the order in which you test and remove extraneous attributes can affect which minimal cover you obtain. Different orderings produce different (but equivalent) results.

Example:

F = {A → B, B → A, B → C, A → C}

Both A → C and B → C might appear redundant, depending on which you test first:

Order 1: Test A → C first

Test A → C for redundancy
F' = {A → B, B → A, B → C}
Compute A⁺ under F': {A} → {A, B} → {A, B, C}
C is in closure! A → C is redundant.
Remove it. Minimal cover: {A → B, B → A, B → C}

Order 2: Test B → C first

Test B → C for redundancy
F' = {A → B, B → A, A → C}
Compute B⁺ under F': {B} → {B, A} → {B, A, C}
C is in closure! B → C is redundant.
Remove it. Minimal cover: {A → B, B → A, A → C}

Both results are valid minimal covers!

The closure (A → B, B → A, A ↔ B, A → C, B → C, etc.) is identical for both. The difference is merely in representation.

Order 1 Result

•A → B
•B → A
•B → C

Order 2 Result

•A → B
•B → A
•A → C

Both Are Correct

Since A ↔ B (A and B determine each other), both 'A → C' and 'B → C' express the same constraint. Either minimal cover is valid. For normalization purposes, both lead to equivalent schema designs.

Edge Cases and Subtle Situations

Several edge cases require careful handling when identifying extraneous attributes.

Edge Case 1: Reflexive FDs

By reflexivity, if Y ⊆ X, then X → Y is trivially true. For example, AB → A is always true.

Testing: Is A extraneous in AB → A?
Compute B⁺: {B} (typically just B if no other FDs)
Is A in {B}? Usually no.
But wait! AB → A is trivial—it should be removed entirely.

Resolution: Remove trivial FDs (where RHS ⊆ LHS) before testing for extraneous attributes.

Edge Case 2: Single-Attribute Determinant

If X has only one attribute, we can't remove any LHS attribute (would make it empty). Only test for RHS redundancy.

A → B  // Can't remove A from LHS; can only test if FD is redundant

Edge Case 3: Cascading Extraneousness

Removing one attribute may make another extraneous:

F = {A → B, B → C, ABC → D}

Test ABC → D: Is C extraneous?
Compute (AB)⁺ = {A, B, C, D, ...} (via A → B, B → C, then ABC → D applies)
Yes! C is extraneous. Remove it: AB → D
Now test AB → D: Is B extraneous?
Compute A⁺ = {A, B, C, ...} then need to reach D
Actually, with AB → D simplified, need A → B before AB → D
Depends on whether the simplified FD is still usable

This cascading requires iterative testing until no more changes occur.

Edge Cases in Extraneous Attribute Detection
Edge Case	Problem	Solution
Trivial FDs	`AB → A` is always true	Remove trivial FDs before testing
Single-attribute LHS	Can't remove from `A → B`	Only test for FD redundancy
Cascading changes	Removing A makes B extraneous	Iterate until stable
Self-loops	`A → A` is trivial	Remove or ignore as trivial
Empty result	All attributes extraneous?	At least candidate key remains

Always Validate Results

After removing extraneous attributes, verify that the closure of the original FD set equals the closure of the simplified set. This guards against algorithm errors.

Running Example: Course Registration Continued

Continuing our course registration example from Page 1, let's identify all extraneous attributes.

Original FD Set (after decomposition to single-attribute RHS):

F = {
  StudentID → StudentName,                     (1)
  CourseID → CourseTitle,                      (2)
  CourseID → DepartmentID,                     (3)
  InstructorID → InstructorName,               (4)
  DepartmentID → DepartmentName,               (5)
  CourseID → DepartmentName,                   (6) - suspected redundant
  StudentID, CourseID → Grade,                 (7)
  StudentID, CourseID, Semester → Grade,       (8) - suspected extraneous LHS
  StudentID, CourseID → InstructorID,          (9)
  StudentID, CourseID → Semester,              (10)
}

Testing FD (8): Is Semester extraneous in (StudentID, CourseID, Semester → Grade)?

Let X' = {StudentID, CourseID}
Compute X'⁺ under F:
- Start: {StudentID, CourseID}
- Apply (1): {StudentID, CourseID, StudentName}
- Apply (2): {..., CourseTitle}
- Apply (3): {..., DepartmentID}
- Apply (5): {..., DepartmentName}
- Apply (6): {...} (DepartmentName already present)
- Apply (7): {..., Grade} ← Found!
Grade ∈ X'⁺? Yes!
Conclusion: Semester IS extraneous.

Testing FD (6): Is CourseID → DepartmentName redundant?

F' = F - {CourseID → DepartmentName}
Compute CourseID⁺ under F':
- Start: {CourseID}
- Apply (2): {CourseID, CourseTitle}
- Apply (3): {CourseID, CourseTitle, DepartmentID}
- Apply (5): {..., DepartmentName} ← Found!
DepartmentName ∈ CourseID⁺? Yes!
Conclusion: FD (6) IS redundant.

Extraneous Attribute Analysis Results
FD	Test Performed	Result	Action
(1) StudentID → StudentName	RHS redundancy	Essential	Keep
(2) CourseID → CourseTitle	RHS redundancy	Essential	Keep
(3) CourseID → DepartmentID	RHS redundancy	Essential	Keep
(4) InstructorID → InstructorName	RHS redundancy	Essential	Keep
(5) DepartmentID → DepartmentName	RHS redundancy	Essential	Keep
(6) CourseID → DepartmentName	RHS redundancy	Redundant	Remove
(7) StudentID, CourseID → Grade	LHS & RHS	Essential	Keep
(8) StudentID, CourseID, Semester → Grade	LHS extraneous	Semester extraneous	Remove Semester
(9) StudentID, CourseID → InstructorID	LHS & RHS	Essential	Keep
(10) StudentID, CourseID → Semester	LHS & RHS	Essential	Keep

After removing extraneous elements:

F' = {
  StudentID → StudentName,
  CourseID → CourseTitle,
  CourseID → DepartmentID,
  InstructorID → InstructorName,
  DepartmentID → DepartmentName,
  StudentID, CourseID → Grade,
  StudentID, CourseID → InstructorID,
  StudentID, CourseID → Semester,
}

Wait—after removing Semester from FD (8), we have StudentID, CourseID → Grade, which is the same as FD (7). This creates a duplicate! In the next page on the canonical cover algorithm, we'll see how to handle this.

Summary: Extraneous Attributes

We've covered the critical concept of extraneous attributes—a key step in computing canonical covers. Let's consolidate:

Key Takeaways

•Extraneous attributes are removable without changing closure: They represent redundancy that obscures essential dependencies.
•LHS extraneous uses original F: Compute (X - {A})⁺ under F to test if A is extraneous in X → Y.
•RHS extraneous uses modified F: Compute X⁺ under (F - {X → A}) to test if FD is redundant.
•Processing order matters: Different orderings yield different (but equivalent) minimal covers.
•Iterate until stable: Removing one extraneous element may create new ones; continue until no changes.
•Handle edge cases carefully: Trivial FDs, single-attribute LHS, and cascading changes require attention.

What's Next:

Now that you can identify extraneous attributes, the next page presents the complete canonical cover algorithm—the systematic procedure that combines all these techniques to compute a minimal cover for any FD set.

Page Complete

You now understand how to identify extraneous attributes on both the left-hand side and right-hand side of functional dependencies. You can apply the testing algorithms and understand why processing order affects results.

Extraneous Attributes: Identifying Unnecessary Elements

The Hidden Bloat in Functional Dependencies

This page provides a rigorous treatment of extraneous attributes: what they are, how to detect them, and why their removal is essential for database design.

What You Will Learn

What Are Extraneous Attributes?

An extraneous attribute is an attribute in a functional dependency that can be removed without changing the closure of the FD set. There are two distinct cases:

Extraneous Attribute on the Left-Hand Side (LHS):

Attribute A is extraneous on the LHS of X → Y if:

A ∈ X (A is part of the determinant)
Y can still be derived using (X - {A}) under the original FD set

Formally: A is extraneous in X → Y on the LHS if Y ⊆ (X - {A})⁺ under F.

Extraneous Attribute on the Right-Hand Side (RHS):

Attribute A is extraneous on the RHS of X → Y if:

A ∈ Y (A is part of the dependent)
A can be derived from X using the remaining FDs

Formally: A is extraneous in X → Y on the RHS if A ⊆ X⁺ under (F - {X → Y}) ∪ {X → (Y - {A})}.

Alternatively: A is extraneous in X → Y on the RHS if A ⊆ X⁺ under (F - {X → A}) when RHS is already decomposed to single attributes.

Key Insight

The fundamental question is always the same: 'Can I derive the same things without this attribute?' If yes, the attribute is extraneous. If no, the attribute is essential.

Extraneous Attributes Summary
Type	Example	Condition for A Being Extraneous	Intuition
LHS Extraneous	`ABC → D` where `AB → D` holds	D ⊆ (AB)⁺ under F	C isn't needed to determine D
RHS Extraneous	`A → BC` where `A → C` is derivable elsewhere	C ⊆ A⁺ under F - {A → C}	C is determined through other FDs

Left-Hand Side Extraneous Attributes

Formal Definition:

Let F be a set of FDs, and let X → Y be an FD in F where A ∈ X.

A is extraneous in X → Y (on the LHS) if:

Y ⊆ (X - {A})⁺ under F

Intuition:

Compute the closure of X without A, using all FDs in F (including X → Y itself). If Y is in this closure, then A is extraneous—it's not contributing anything that can't be derived without it.

Example 1:

F = {A → C, AB → C}

Is B extraneous in AB → C?

Remove B: reduced determinant is {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → C: {A, C}
Is C in {A, C}? Yes!
Conclusion: B is extraneous in AB → C.

Example 2:

F = {A → B, BC → D, AC → D}

Is C extraneous in AC → D?

Remove C: reduced determinant is {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → B: {A, B}
Is D in {A, B}? No!
Conclusion: C is NOT extraneous in AC → D.

lhs_extraneous_algorithm.txt
ALGORITHM: Test if attribute A is extraneous on LHS of X → Y in F
 
INPUT:
  F: set of functional dependencies
  X → Y: an FD in F
  A: an attribute in X
 
OUTPUT:
  true if A is extraneous, false otherwise
 
PROCEDURE:
1. Let X' = X - {A}           // Remove A from determinant
2. Compute (X')⁺ under F      // Closure includes ALL FDs in F
3. If Y ⊆ (X')⁺:
     return true              // A is extraneous
   Else:
     return false             // A is essential
 
NOTE: We use the ORIGINAL F (including X → Y) for closure computation.
This is critical—other FDs in F might contribute to deriving Y.

Common Mistake

Right-Hand Side Extraneous Attributes

An attribute A is extraneous on the right-hand side of an FD X → Y if removing A from Y doesn't change the overall closure—meaning A can be derived from X through other FDs in the set.

Formal Definition:

Let F be a set of FDs, and let X → Y be an FD in F where A ∈ Y.

A is extraneous in X → Y (on the RHS) if:

A ∈ X⁺ under F' where F' = (F - {X → Y}) ∪ {X → (Y - {A})}

This is equivalent to: we replace X → Y with X → (Y - {A}) and check if A is still in the closure of X.

When RHS Has Single Attribute (canonical form):

If we've already decomposed to single-attribute RHS, then:

A is extraneous in X → A if A ∈ X⁺ under (F - {X → A})

This simpler form asks: can we derive A from X without using X → A?

Example 1:

F = {A → B, B → C, A → C}

Is C extraneous in A → C? (Assuming single-attribute RHS)

Consider F' = F - {A → C} = {A → B, B → C}
Compute A⁺ under F':
- Start: {A}
- Apply A → B: {A, B}
- Apply B → C: {A, B, C}
Is C in {A, B, C}? Yes!
Conclusion: C is extraneous in A → C. The FD is redundant.

Example 2:

F = {A → B, A → C}

Is B extraneous in A → B?

Consider F' = F - {A → B} = {A → C}
Compute A⁺ under F':
- Start: {A}
- Apply A → C: {A, C}
Is B in {A, C}? No!
Conclusion: B is NOT extraneous in A → B.

rhs_extraneous_algorithm.txt
ALGORITHM: Test if attribute A is extraneous on RHS of X → Y in F
 
INPUT:
  F: set of functional dependencies
  X → Y: an FD in F
  A: an attribute in Y
 
OUTPUT:
  true if A is extraneous, false otherwise
 
PROCEDURE:
1. Let F' = (F - {X → Y}) ∪ {X → (Y - {A})}
   // Replace original FD with reduced version
2. Compute X⁺ under F'
3. If A ∈ X⁺:
     return true              // A is extraneous
   Else:
     return false             // A is essential
 
SIMPLIFIED (when Y has single attribute A):
1. Let F' = F - {X → A}       // Simply remove the FD
2. Compute X⁺ under F'
3. If A ∈ X⁺:
     return true              // FD is redundant
   Else:
     return false             // FD is essential
 
NOTE: We use the MODIFIED F' (without the FD or with reduced FD).
This checks if the attribute can be derived through OTHER paths.

Critical Difference from LHS Testing

For LHS extraneous testing, use the ORIGINAL F. For RHS extraneous testing, use the MODIFIED F'. This difference is crucial—mixing them up leads to incorrect results.

Detailed Worked Examples

Let's work through comprehensive examples that illustrate both LHS and RHS extraneous attribute detection.

Example Set:

F = {
  A → BC,
  B → C,
  AB → D,
  D → E,
  CE → A
}

First, let's decompose to single-attribute RHS:

F = {
  A → B,      (1)
  A → C,      (2)
  B → C,      (3)
  AB → D,     (4)
  D → E,      (5)
  CE → A      (6)
}

Testing if A is extraneous in AB → D:

Remove A from determinant: X' = {B}
Compute B⁺ under F:
- Start: {B}
- Apply B → C (3): {B, C}
Is D in {B, C}? No
Conclusion: A is NOT extraneous in AB → D.

Testing if B is extraneous in AB → D:

Remove B from determinant: X' = {A}
Compute A⁺ under F:
- Start: {A}
- Apply A → B (1): {A, B}
- Apply A → C (2): {A, B, C}
- Apply B → C (3): {A, B, C} (no change)
- Apply AB → D (4): {A, B, C, D}
- Apply D → E (5): {A, B, C, D, E}
Is D in {A, B, C, D, E}? Yes!
Conclusion: B IS extraneous in AB → D.

We can replace AB → D with A → D without losing any derivable FDs!

Systematic Testing Procedure

To find all extraneous attributes in an FD set, we must systematically test each attribute in each FD. Here's a structured approach:

Step 1: Decompose to Single-Attribute RHS

Replace each FD X → Y₁Y₂...Yₙ with n FDs:

X → Y₁
X → Y₂
...
X → Yₙ

This simplifies RHS extraneous testing to testing FD redundancy.

Step 2: Test Each LHS Attribute in Each FD

For each FD X → A where |X| > 1:

For each B ∈ X:
- Compute (X - {B})⁺ under F
- If A is in the closure, B is extraneous
- If found extraneous, remove B from X in the FD

Step 3: Test Each FD for Redundancy (RHS Extraneous)

For each FD X → A:

Compute X⁺ under (F - {X → A})
If A is in the closure, the FD is redundant
If redundant, remove the entire FD from F

Important: Order Matters

Removing one extraneous attribute may make another attribute extraneous (or essential) that wasn't before. Therefore:

Continue testing until no more extraneous attributes are found
Different orderings may produce different (valid) minimal covers

systematic_extraneous_removal.txt
ALGORITHM: Remove All Extraneous Attributes
 
INPUT: F (set of functional dependencies)
OUTPUT: F with all extraneous attributes removed
 
// Step 1: Decompose RHS to single attributes
FOR each (X → Y) in F where |Y| > 1:
    Remove (X → Y) from F
    FOR each A in Y:
        Add (X → A) to F
 
// Step 2: Remove extraneous LHS attributes
changed = true
WHILE changed:
    changed = false
    FOR each (X → A) in F where |X| > 1:
        FOR each B in X:
            X' = X - {B}
            IF A ∈ closure(X', F):
                Replace (X → A) with (X' → A) in F
                changed = true
                BREAK  // Restart outer loop
 
// Step 3: Remove redundant FDs
changed = true
WHILE changed:
    changed = false
    FOR each (X → A) in F:
        F' = F - {X → A}
        IF A ∈ closure(X, F'):
            F = F'
            changed = true
            BREAK  // Restart loop
 
RETURN F

Efficiency Tip

Why Processing Order Affects the Result

A subtle but important point: the order in which you test and remove extraneous attributes can affect which minimal cover you obtain. Different orderings produce different (but equivalent) results.

Example:

F = {A → B, B → A, B → C, A → C}

Both A → C and B → C might appear redundant, depending on which you test first:

Order 1: Test A → C first

Test A → C for redundancy
F' = {A → B, B → A, B → C}
Compute A⁺ under F': {A} → {A, B} → {A, B, C}
C is in closure! A → C is redundant.
Remove it. Minimal cover: {A → B, B → A, B → C}

Order 2: Test B → C first

Test B → C for redundancy
F' = {A → B, B → A, A → C}
Compute B⁺ under F': {B} → {B, A} → {B, A, C}
C is in closure! B → C is redundant.
Remove it. Minimal cover: {A → B, B → A, A → C}

Both results are valid minimal covers!

The closure (A → B, B → A, A ↔ B, A → C, B → C, etc.) is identical for both. The difference is merely in representation.

Order 1 Result

•A → B
•B → A
•B → C

Order 2 Result

•A → B
•B → A
•A → C

Both Are Correct

Edge Cases and Subtle Situations

Several edge cases require careful handling when identifying extraneous attributes.

Edge Case 1: Reflexive FDs

By reflexivity, if Y ⊆ X, then X → Y is trivially true. For example, AB → A is always true.

Testing: Is A extraneous in AB → A?
Compute B⁺: {B} (typically just B if no other FDs)
Is A in {B}? Usually no.
But wait! AB → A is trivial—it should be removed entirely.

Resolution: Remove trivial FDs (where RHS ⊆ LHS) before testing for extraneous attributes.

Edge Case 2: Single-Attribute Determinant

If X has only one attribute, we can't remove any LHS attribute (would make it empty). Only test for RHS redundancy.

A → B  // Can't remove A from LHS; can only test if FD is redundant

Edge Case 3: Cascading Extraneousness

Removing one attribute may make another extraneous:

F = {A → B, B → C, ABC → D}

Test ABC → D: Is C extraneous?
Compute (AB)⁺ = {A, B, C, D, ...} (via A → B, B → C, then ABC → D applies)
Yes! C is extraneous. Remove it: AB → D
Now test AB → D: Is B extraneous?
Compute A⁺ = {A, B, C, ...} then need to reach D
Actually, with AB → D simplified, need A → B before AB → D
Depends on whether the simplified FD is still usable

This cascading requires iterative testing until no more changes occur.

Edge Cases in Extraneous Attribute Detection
Edge Case	Problem	Solution
Trivial FDs	`AB → A` is always true	Remove trivial FDs before testing
Single-attribute LHS	Can't remove from `A → B`	Only test for FD redundancy
Cascading changes	Removing A makes B extraneous	Iterate until stable
Self-loops	`A → A` is trivial	Remove or ignore as trivial
Empty result	All attributes extraneous?	At least candidate key remains

Always Validate Results

After removing extraneous attributes, verify that the closure of the original FD set equals the closure of the simplified set. This guards against algorithm errors.

Running Example: Course Registration Continued

Continuing our course registration example from Page 1, let's identify all extraneous attributes.

Original FD Set (after decomposition to single-attribute RHS):

F = {
  StudentID → StudentName,                     (1)
  CourseID → CourseTitle,                      (2)
  CourseID → DepartmentID,                     (3)
  InstructorID → InstructorName,               (4)
  DepartmentID → DepartmentName,               (5)
  CourseID → DepartmentName,                   (6) - suspected redundant
  StudentID, CourseID → Grade,                 (7)
  StudentID, CourseID, Semester → Grade,       (8) - suspected extraneous LHS
  StudentID, CourseID → InstructorID,          (9)
  StudentID, CourseID → Semester,              (10)
}

Testing FD (8): Is Semester extraneous in (StudentID, CourseID, Semester → Grade)?

Let X' = {StudentID, CourseID}
Compute X'⁺ under F:
- Start: {StudentID, CourseID}
- Apply (1): {StudentID, CourseID, StudentName}
- Apply (2): {..., CourseTitle}
- Apply (3): {..., DepartmentID}
- Apply (5): {..., DepartmentName}
- Apply (6): {...} (DepartmentName already present)
- Apply (7): {..., Grade} ← Found!
Grade ∈ X'⁺? Yes!
Conclusion: Semester IS extraneous.

Testing FD (6): Is CourseID → DepartmentName redundant?

F' = F - {CourseID → DepartmentName}
Compute CourseID⁺ under F':
- Start: {CourseID}
- Apply (2): {CourseID, CourseTitle}
- Apply (3): {CourseID, CourseTitle, DepartmentID}
- Apply (5): {..., DepartmentName} ← Found!
DepartmentName ∈ CourseID⁺? Yes!
Conclusion: FD (6) IS redundant.

Extraneous Attribute Analysis Results
FD	Test Performed	Result	Action
(1) StudentID → StudentName	RHS redundancy	Essential	Keep
(2) CourseID → CourseTitle	RHS redundancy	Essential	Keep
(3) CourseID → DepartmentID	RHS redundancy	Essential	Keep
(4) InstructorID → InstructorName	RHS redundancy	Essential	Keep
(5) DepartmentID → DepartmentName	RHS redundancy	Essential	Keep
(6) CourseID → DepartmentName	RHS redundancy	Redundant	Remove
(7) StudentID, CourseID → Grade	LHS & RHS	Essential	Keep
(8) StudentID, CourseID, Semester → Grade	LHS extraneous	Semester extraneous	Remove Semester
(9) StudentID, CourseID → InstructorID	LHS & RHS	Essential	Keep
(10) StudentID, CourseID → Semester	LHS & RHS	Essential	Keep

After removing extraneous elements:

F' = {
  StudentID → StudentName,
  CourseID → CourseTitle,
  CourseID → DepartmentID,
  InstructorID → InstructorName,
  DepartmentID → DepartmentName,
  StudentID, CourseID → Grade,
  StudentID, CourseID → InstructorID,
  StudentID, CourseID → Semester,
}

Summary: Extraneous Attributes

We've covered the critical concept of extraneous attributes—a key step in computing canonical covers. Let's consolidate:

Key Takeaways

•Extraneous attributes are removable without changing closure: They represent redundancy that obscures essential dependencies.
•LHS extraneous uses original F: Compute (X - {A})⁺ under F to test if A is extraneous in X → Y.
•RHS extraneous uses modified F: Compute X⁺ under (F - {X → A}) to test if FD is redundant.
•Processing order matters: Different orderings yield different (but equivalent) minimal covers.
•Iterate until stable: Removing one extraneous element may create new ones; continue until no changes.
•Handle edge cases carefully: Trivial FDs, single-attribute LHS, and cascading changes require attention.

What's Next:

Page Complete