Friday, September 12, 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.



6 comments:

  1. Did you mean to say F' in example 2 step 1 when you said "from F, if you know P, then you know Q"?

    ReplyDelete
    Replies
    1. Thanks for your comment. Now I have changed to F' in example 2.

      Delete
  2. Here is a list of functional dependencies:
    ABC → D
    CDE → F
    DE → A
    DE → B
    CF → B
    BDF → E
    AE → C
    BC → F
    AB → E
    AB → F
    BF → C

    Find ALL minimal covers for this set of FD's.
    how to find for this?

    ReplyDelete
    Replies
    1. Hi, please try these pages to find an answer. If you are not able to solve, please comment. Thanks.
      http://www.exploredatabase.com/2016/12/canonical-cover-or-minimal-cover-in-dbms-home-page.html
      http://www.exploredatabase.com/2017/10/minimal-cover-canonical-cover-solved-exercises.html

      Delete
    2. this is what I could come up
      AB -> DE
      DE ->ABF
      CF -> B
      BDF ->E
      AE → C
      BC → F
      BF → C
      Since I dont know how to validate.. Can you think of any other minimal cover set?

      Delete
  3. This is the minimal cover;
    AB->DF, DE->AB, CF->B, BDF->E, AE->C, BC->F, BF->C

    ReplyDelete

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

data recovery