How to find extraneous attribute? An example.

To find Extraneous attribute in a given functional dependency / How to find extraneous attribute? / Example for finding extraneous attributes

Finding Extraneous Attributes

Let us consider a set of functional dependencies F and any functional dependency of the form α → β. Assume that α and β are set of one or more attributes. [For example, A → BC or AB → CE etc.]

Case 1 (LHS): To find if an attribute A in α is extraneous or not. That is, to test if an attribute of Left Hand Side of a functional dependency is Extraneous or not.

Step 1: Find ({α} – A)⁺ using the dependencies of F.

Step 2: If ({α} – A)⁺ contains all the attributes of β, then A is extraneous.

Case 2 (RHS): To find if an attribute A in β is extraneous or not. That is, to test if an attribute of Right Hand Side of a functional dependency is Extraneous or not.

Step 1: Find α⁺ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.

Step 2: If α⁺ contains A, then A is extraneous.

Example 1 for LHS:

Given F = {P→Q, PQ→R}. Is Q extraneous in PQ→R?

In this example, we are looking for a LHS attribute. Hence, let us use Case 1 discussed above.

Step 1: Find ({α} – A)⁺ using the dependencies of F.

Here, α is PQ. So find (PQ – Q)⁺, ie., P+ (closure of P).

From F, if you know P, then you know Q (from P→Q).

If you know both P and Q then you know R (from PQ→R).

Hence, the closure of P is PQR.

Step 2: If ({α} – A)⁺ contains all the attributes of β, then A is extraneous.

(PQ – Q)⁺ contains R. Hence, Q is extraneous in PQ→R.

Example 2 for RHS:

Given F = {P→QR, Q→R}. Is R extraneous in P→QR?

In this example, we are looking for a RHS attribute. Hence, let us use the Case 2 given above.

Step 1: Find α⁺ using the dependencies in F’ where F’ = (F – {α → β}) U { α → (β – A) }.

Let us find F’ as stated above.

F’ = (F – {α → β}) U { α → (β – A) } = ({P→QR, Q→R} – {P→QR}) U {P→(QR-R)}

   = ({Q→ R} U {P→Q})

F’ = {Q→R, P→Q}

Here, α is P. So find (P)⁺, ie., closure of P using the F’ which we found.

From F’, if you know P, then you know Q (from P→Q).

If you know Q then you know R (from Q→R).

Hence, the closure of P is PQR.

Step 2: If α⁺ contains A, then A is extraneous.

P+ contains R. Hence, R is extraneous in P→QR.