Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Friday, 12 September 2014

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 = {PQ, PQR}. Is Q extraneous in PQR?
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 PQ).
If you know both P and Q then you know R (from PQR).
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 PQR.

Example 2 for RHS:

Given F = {PQR, QR}. Is R extraneous in PQR?
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) } = ({PQR, QR} – {PQR}) U {P(QR-R)}
   = ({Q R} U {PQ})
F’ = {QR, PQ}
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 PQ).
If you know Q then you know R (from QR).
Hence, the closure of P is PQR.
Step 2: If α+ contains A, then A is extraneous.
P+ contains R. Hence, R is extraneous in PQR.



Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents