*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.
##### (A)

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)
##### (A)

Therefore, F ⊆ G holds
##### (A)

Therefore, G ⊆ F holds
##### (A)

Therefore, A -> C is required
##### (AC)

Therefore, AC -> D is required
##### (E)

Therefore, E -> A is required
##### (E)

Therefore, E -> D is redundant as it is equal to R
So, remove this redundant production
##### (E)

Therefore, E -> H is required
After removing redundant productions, new production set is:
##### (AC)

Now find closure of A and C separately
##### (A)

[Note if (A)##### (C)

Now find closure of CE
##### (CE)

Since ##### (CE)

then CE is a candidate key.

**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)^{+} = {A__C__D}
(AC)^{+} = {AC__D__}
(E)^{+} = {E__AH__C__D__}

Therefore, F ⊆ G holds
**Step 2:**G ⊆ F ? Find closure of A and E using production rule of F##### (A)^{+} = {A__CD__}
(E)^{+}= {E__A__D__H__C}

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:**2**Here, n = 6 (number of attributes in a relation) 2^{n}- 1^{6 }- 1 = 63 If**(A)**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^{+}= R,