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.