MINIMAL COVER presentation for class.pptx

Minimalist cover ppt

1. Steps to Find Minimal Cover Singleton attributes in Right Hand Side [RHS] Identify Extraneous Attributes and remove it Remove redundant dependencies

2. Singleton in RHS AB -> CD The above functional dependency should be decomposed to singleton attributes in the RHS as below. AB -> C and AB -> D

3. Finding Redundancy Dependency and Minimal Cover – Ex 1 Now we have to identify the redundant dependencies from the below New FDs A->B A->C D-AC D->E 1. Remove A->B and find the attribute closure for A A + = AC [Since A->C] – Here if we don’t consider A->B, B cannot be found in A + . So A->B cannot be a redundant dependency. 2. Remove A->C and find the attribute closure for A A + = AB [Since A->B] – Here if we don’t consider A->C, C cannot be found in A + . So A->C cannot be a redundant dependency. 3. Remove D->A and find the attribute closure for D D + = DCE [Since D->C, D->E] – Here if we don’t consider D->A, A cannot be found in D + . So D->A cannot be a redundant dependency. 4. Remove D->C and find the attribute closure for D D + = DAEBC [Since D->C, ] – Here if we don’t consider D->C, Could be found in D + . So D->C is the redundant dependency and should be removed. A->B A->C D->A D->C D->E Applying Singleton to RHS

4. Finding Redundancy Dependency and Minimal Cover A->B A->C D->A D->C D->E 5. Remove D->E and find the attribute closure for D D + = DACB [Since D->A, A->C, A->B] – Here if we don’t consider D->E, E cannot be found in D + . So D->E cannot be a redundant dependency. So, Minimal Cover will be after removing a) Extraneous Attributes b) Redundant Dependencies Minimal Functional Dependencies are A -> B A -> C D -> A D -> E A->B A->C D->A D->E New FD’s after removing Redundancy

5. Finding Redundancy Dependency and Minimal Cover – Ex 2 Consider the Functional Dependencies A -> B B -> C A -> C Remove A -> B and find attribute Closure for A A + = AC [B is not issued – Not redundant] Remove B -> C and find attribute Closure for B. B + = B [C is not issued – Not redundant] Remove A -> C and find attribute Closure for A. A + = ABC [A->B, B->C. C is issued – So, Redundant] Final FDs without redundancy are A->B and B->C

6. Finding Extraneous, Redundant Dependency, Minimal Cover R(A,B,C,D,E) F = {A->D, BC->AD, C->B, E->A, E->D} Step1: Singleton RHS Step2: Remove Extraneous Attribute Step3: Redundant Dependency Step1: Singleton RHS A->D BC->A BC->D C->B E->A E->D

7. Finding Extraneous, Redundant Dependency, Minimal Cover Step2: Remove Extraneous Attribute A->D BC->A BC->D C->B E->A E->D Consider BC->A and BC->D B + = B C + =BCAD so B is Extraneous in BC->A and BC->D. Remove it. After removing Extraneous in LHS, F => A->D C->A C->D C->B E->A E->D

8. Finding Extraneous, Redundant Dependency, Minimal Cover Step3: Remove Redundant Dependency A->D C->A C->D C->B E->A E->D Remove A->D, A + = A – Not Redundant [D not arrived] Remove C->A, C + = CDB – Not Redundant [A not arrived] Remove C->D, C + = CABD – Redundant [D arrived] New F= {A->D, C->A, C->B, E->A, E->D}

9. Finding Extraneous, Redundant Dependency, Minimal Cover Step3: Remove Redundant Dependency A->D C->A C->B E->A E->D Remove C->B, C + = CAD – Not Redundant [B not arrived] Remove E->A, E + = ED – Not Redundant [A not arrived] Remove E->D, E + = EAD – Redundant [D arrived] Final – Minimal Cover F= {A->D, C->A, C->B, E->A,} EC + = ECADB EC will be the candidate Key