Discussion Session on Functional Dependency
Discussion Session on Functional Dependency
Himel Dev
Q1
Consider the following FDs for relation R(A, B, C, D, E).
A->C
C->B
B->D
D->E
List all the keys for R (make sure they are minimal, i.e. not a superset of some other key).
Q1 Solution
A+ = A
= AC [A->C]
= ABC [C->B]
= ABCD [B->D]
= ABCDE [D->E]
closure(A) = {A,C,B,D,E}
A->C
C->B
B->D
D->E
Q1 Solution (Cont.)
closure(A) = {A,C,B,D,E}
closure(C) = {C,B,D,E}
closure(B) = {B,D,E}
closure(D) = {D,E}
A is a candidate key for the given relation R
A->C
C->B
B->D
D->E
Q2
Consider the following FDs for relation R(A, B, C, D, E).
A->C
B->D
AB->E
List all the keys for R (make sure they are minimal, i.e. not a superset of some other key).
Q2 Solution (Cont.)
closure(A) = {A,C}
closure(B) = {B,D}
closure(AB) = {A, B, C, D, E}
AB is a candidate key for the given relation R
A->C
B->D
AB->E
Q3
Consider the following FDs for relation R(A, B, C, D, E).
A->C
B->AD
AB->E
List all the keys for R (make sure they are minimal, i.e. not a superset of some other key).
Q3 Solution (Cont.)
closure(A) = {A,C}
closure(B) = {A, B, C, D, E}
closure(AB) = {A, B, C, D, E}
B is a candidate key for the given relation R
A->C
B->AD
AB->E
Q4
Consider the following sets of FDs for relation R(A, B, C, D, E, F).
FD1 = {A->C, AC->D, E->AD , E->F}
FD2 = {A->CD, E->AF}.
Are these two set of FDs equivalent?
FD Equivalence
Two sets of functional dependencies F1 and F2 are equivalent if:
Every functional dependency in F2 can be inferred from the functional dependency in F1 (F1 covers F2)
Every functional dependency in F1 can be inferred from the functional dependency in F2 (F2 covers F1)
Step 1: F1 covers F2
A+ = A
= AC [A->C]
= ACD [AC->D]
CD ⊆ ACD
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Step 1: F1 covers F2
E+ = E
= ADE [E->AD]
= ADEF [E->F]
= ACDEF [A->C]
AF ⊆ ACDEF
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Step 2: F2 covers F1
A+ = A
= ACD [A->CD]
C ⊆ ACD
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Step 2: F2 covers F1
AC+ = AC
= ACD [A->CD]
D ⊆ ACD
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Step 2: F2 covers F1
E+ = E
= AEF [E->AF]
= ACDEF [A->CD]
AD ⊆ ACDEF
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Step 2: F2 covers F1
E+ = E
= AEF [E->AF]
= ACDEF [A->CD]
F ⊆ ACDEF
F1 and F2 are equivalent.
F2
A->CD
E->AF
F1
A->C
AC->D
E->AD
E->F
Q5
Consider the following set F1 of FDs for relation R(A, B, C).
F1 = {A -> B, B -> C}
Now, compute the closure for set F1.
Q5 Solution
The closure set of a set F1 of Functional Dependencies (FDs) is the set of all FDs implied by F1. This closure set is denoted by F1+.
F1+ = {A -> A, B -> B, C -> C, AB -> AB, AC -> AC, BC -> BC, ABC -> ABC, (all from reflexivity), A -> B (given), B -> C (given), and A -> C (transitivity), and A -> BC(union)}
/docProps/thumbnail.jpeg