Prev   Next
Functional Dependency (FD): It is a relationship that exists when one attribute uniquely determines another attribute. If A and B are attributes of relation R then functional dependency between the attributes is represented by A->B, specifies that B is functional dependent on A where A is determinant set and B is a dependent attribute. E.g. FD: A -> B Note: If there is FD: A -> B in a relation R, shows that for the given value of A, we can search the value of B. Que1. Find out the correct functional dependency A -> B (FD holds as there is distinct values for each value a, b, c, d) B -> A (FD doesn't hold as there are three different values when B = 2 i.e. 2 determines b, c, d) Que 2: Find out correct functional dependency A -> B   X (there are two different values (B = 1,2) when A = 1 and three different values (B= 1, 2, 4) when A = 2) B -> C   X (there are two different values (C= 4, 3) when B = 1 and two different values (C = 4, 3) when B = 2) B -> A   X (there are two different values (A = 1, 2) when B = 1 and three different values (A= 1, 2) when B = 2) C -> B   X (there are two different values (B = 1, 2) when C = 4 and three different values (B= 1, 2, 4) when C = 3) C -> A   FD holds (there are distinct values of A for each value of C) A -> C   FD holds Theory: 1. functional-dependency-and-attribute-closure 2. functional-dependency Video: 1. functional-dependency 2. practice problem on functional-dependency 3. practice problem on functional-dependency2 Inference rules used in FD: 1. Reflexive: A -> B if B ⊆ A 2. Transitive: A -> B and B -> C then A -> C 3. Decomposition: If A -> BC, then A -> B and A -> C 4. Augmentation: If A -> B, then AC -> BC 5. Union: If A -> B and A -> C, then A -> BC 6. Composition: If A -> B and C -> D, then AC -> BC 7. Pseudo transitivity: If X -> Y and WY -> Z, then WX -> Z Armstrong's Axioms in FD: Armstrong's Axioms Armstrong's axioms are a set of axioms or inference rules. These are used to infer all the functional dependencies on relational database. Video on Armstrong's axioms: Armstrong's Axioms Closure sets/ Attribute closure: Attribute Closure of an attribute can be defined as set of attributes which we can identified from it. Closure set of an attribute: Closure set of an attribute e.g. Find Closure FD: A ->B B -> D C -> DE CD -> AB Solution:
##### (A)+ = {A, B, D} (B)+ = {B, D} (C)+ = {C, D, E, A, B} (D)+= {D} (E)+ = {E} (AB)+ = {A, B, D} (CD)+ = {C, D, E, A, B} (ABD)+ = {A, B, D}
Equivalence of Functional Dependency: Theory: equivalence-of-functional-dependencies Video: 1. equivalence-of-functional-dependencies 2. practice problem on equivalence-of-functional-dependencies Suppose F and G are two functional dependencies for a relation R. If F ⊆ G and G ⊆ F, then they are equal. Que: R (ACDEH) F: A -> C, AC -> D, E -> AD, E -> H G: A -> CD, E -> AH Step 1: F ⊆ G ? Find closure of A, AC and E using production rule of G
##### (A)+ = {ACD} (AC)+ = {ACD} (E)+ = {EAHCD}
Therefore, F ⊆ G holds Step 2: G ⊆ F ? Find closure of A and E using production rule of F
##### (A)+ = {ACD} (E)+= {EADHC}
Therefore, G ⊆ F holds Conclusion: F and G functional dependencies are equal. Minimal Set of Functional Dependencies: Canonical Cover: canonical-cover Video: canonical-cover irreducible practice problem on canonical-cover-irreducible Steps to find minimal set: Split the FDs in such a way that RHS contain single attribute e.g. FD: A -> BC then split them as A -> B and A -> C Find the redundant FDs and remove them from the set. e.g. FD: A -> B, B -> C, A -> C then remove redundant productions (here A -> C, as this production can be derived from first two productions) now productions are: A -> B and B -> C Find the redundant attributes on the LHS and remove them Que: R (A, C, D, E, H) FD: A -> C AC -> D E -> A E -> D E -> H Step 1. Ignore A -> C and find (A)+
##### (A)+= {A}
Therefore, A -> C is required Step 2. Ignore AC -> D and find (AC)+
##### (AC)+ = {AC}
Therefore, AC -> D is required Step 3. Ignore E -> A and find (E)+
##### (E)+= {EDH}
Therefore, E -> A is required Step 4. Ignore E -> D and find (E)+
##### (E)+ = {EAHCD}
Therefore, E -> D is redundant as it is equal to R So, remove this redundant production Step 5. Ignore E -> H and find (E)+
##### (E)+ = {EAC}
Therefore, E -> H is required After removing redundant productions, new production set is: A -> C AC -> D E -> A E -> H Step 6. Find redundant attributes on LHS AC -> D Find (AC)+
##### (AC)+= {ACD}
Now find closure of A and C separately
##### (A)+ = {ACD} (C)+ = {C}
[Note if (A)+ = (AC)+ then C is redundant and if (C)+ = (AC)+ then A is redundant] Here, (A)+ = (AC)+ then C is redundant here Final FD is after removing all redundant productions is: A -> C A -> D E -> A E -> H Find keys: Keys : Keys How to find Super Key, Candidate key, Primary key: How to find Super Key, Candidate key, Primary key find number of Candidate key in a relation Practice questions to find Super Key, Candidate key, Primary key Que: R (A, B, C, D, E, F) FD: C -> F E -> A EC -> D A -> B Find candidate key? Solution: Number of possible candidate key: 2n - 1 Here, n = 6 (number of attributes in a relation) 26 - 1 = 63 If (A)+ = R, then A is a candidate key Step 1. Find the attributes that are not present in RHS i.e. attribute which is not having incoming edge So, attributes with no incoming edge are: C, E Step 2. Find closure of attributes C and E
##### (C)+ = {CF} (Not equal to R) (F)+ = {F} (Not equal to R)
Now find closure of CE