# Redundant functional dependencies

A functional dependency in the set is redundant if it can be derived from the other functional dependencies in the set. A redundant FD can be detected using the following steps:

**Step 1: ** Start with a set of **S** of functional dependencies (FDs).

**Step 2:** Remove an FD f and create a set of FDs** S' = S - f** .

**Step 3: **Test whether f can be derived from the FDs in **S'**; by using the set of Armstrong's axioms and derived rules.

**Step 4: ** If f can be so derived, it is redundant , and hence **S' = S**. Otherwise replace f into **S'**; so that now ** S' = S + f**.

**Step 5: **Repeat steps 2 to 4 for all FDs in** S**.

Armstrong's axioms and derived rules, as discussed in the previous section, can be used to find redundant FDs.

For example, suppose the following set of FDs is given in the algorithm:

Z -> A B -> X AX -> Y ZB -> Y

Because ZB -> Y Can be derived from other FDs in the set, it can be shown to be redundant.

The following argument can be given:

- Z -> A by augmentation rule will yield ZB -> AB.
- B -> X and AX -> Y by pseudo-transitivity rule will yield AB -> Y.
- ZB -> AB and AB -> Y by transitivity rule will yield ZB -> Y.

An algorithm (called

** membership algorithm**) can be developed to find redundant FDs, that is, to determine whether an

**FD f(A -> B) **can be derived from a set of FDs

**S**. Using the algorithm the redundant functional dependency can be checked.

### Algorithm: Membership algorithm to find redundant functional dependency

```
```**Input:** Let F be a set of FDs for relation R.
**Steps:**
1. **F' = F - f** //find out new set of
FDs by removing f from F.
2. T = ** A ** //set T = determinant of A -> B
3. for each FD:X -> yin F' Do
a) If** X **⊆** T **Then //if X is contained in T
T = T ∪ Y //add Y to T

End if
4. if **B **⊆ **T** then //if B is contained in T
f : A -> B is redundant. //given FD f: A -> B is redundant.
End if
**Output:** Decision Whether a given FD f: A -> B is redundant or not.

### Example:

suppose a relation R is given with attributes A, B, C, D, E.

Also, a set of functional dependencies F is given with following FDs.

**F = {A -> B, C -> D, BD -> E, AC -> E}**
```
1.Find out whether a FD f : AC -> E is redundant or not.
```** Step 1 :** F' = {A -> B, C -> D, BD -> E}
** Step 2 :** T = AC
** Step 3 :** T = AC + B = ACB
T = ACB + D = ACBD
T = ACBD + E = ACBDE
** Step 4 : **f:AC -> E is redundant.
2.Find out whether a FD f : BD -> E is redundant or not.
** Step 1 :** F' = {A -> B,C -> D, AC -> E}
** Step 2 :** T= BD
** Step 3 :** Nothing can be added to T, As there
is no other FD : X -> Y
such that X⊆ T
**Step 4 :**f:BD -> E is not Redundant. ```
```

` `

## Ask Question