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: 2ⁿ - 1 Here, n = 6 (number of attributes in a relation) 2⁶ - 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

(CE)⁺= {CEFADB}

Since

(CE)⁺ = R

then CE is a candidate key.