EQUIVALENCE OF FUNCTIONAL DEPENDENCY
Back to: Database Tutorial
EQUIVALENCE OF FUNCTIONAL DEPENDENCY
Definition: Two or more than two sets of functional dependencies are called equivalence if the right-hand side of one set of functional dependency can be determined using the second FD set, similarly the right-hand side of the second FD set can be determined using the first FD set.
Q 1: Given a relational schema R( X, Y, Z, W, V ) set of functional dependencies P and Q such that:
P = { X → Y, XY → Z, W → XZ, W → V} and Q = { X → YZ, W → XV } using FD sets P and Q which of the following options are correct?
- P is a subset of Q
- Q is a subset of P
- P = Q
- P ≠ Q
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of P using FD set Q.
Given P = { X → Y, XY → Z, W → XZ, W → V} and Q = { X → YZ, W → XV }
Let’s find closure of the left side of each FD of P using FD Q.
- X+ = XYZ (using X → YZ)
- XY+ = XYZ (using X → YZ)
- W+ = WXVYZ (using W → XV and X → YZ)
- W+ = WXVYZ (using W → XV and X → YZ)
Now compare closure of each X, XY, W and W calculated using FD Q with the right-hand side of FD P. Closure of each X, XY, W and W has all the attributes which are on the right-hand side of each FD of P. Hence, we can say P is a subset of Q———-1
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of Q using FD set P.
Given P = { X → Y, XY → Z, W → XZ, W → V} and Q = { X → YZ, W → XV }
Let us find closure of the left side of each FD of Q using FD P.
- X+ = XYZ (using X → Y and XY → Z)
- W+ = WXZVY (using W → XZ, W → V, and X → Y)
Now compare closure of each X, W calculated using FD P with the right-hand side of FD Q. Closure of each X and W has all the attributes which are on the right-hand side of each FD of Q. Hence, we can say Q is a subset of P———–2
From 1 and 2 we can say that P = Q, hence option C is correct.
Q 2: Given a relational schema R( A, B, C, D ) set of functional dependencies P and Q such that:
P = { A → B, B → C, C → D } and Q = { A → BC, C → D } using FD sets P and Q which of the following options are correct?
- a) P is a subset of Q
- b) Q is a subset of P
- c) P = Q
- d) P ≠ Q
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of P using FD set Q.
Given P = { A → B, B → C, C → D } and Q = { A → BC, C → D }
Let us find closure of the left side of each FD of P using FD Q.
- A+ = ABCD (using A → BC, C → D)
- B+ = B (no FD of Q has B on its left)
- C+ = CD (using C → D)
Now compare closure of each A, B and C calculated using FD Q with the right-hand side of FD P. Closure B is B while in FD set P, B → C (B determines C), since the closure of B determined using FD Q has no C. Hence, we can say P is not a subset of Q———-1
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of Q using FD set P.
Given P = { A → B, B → C, C → D } and Q = { A → BC, C → D }
Let us find closure of the left side of each FD of Q using FD P.
- A+ = ABCD (using A → B, B → C, C → D)
- C+ = CD (using C → D)
Now compare closure of each A and C calculated using FD P with the right-hand side of FD Q. Closure of each A and C has all the attributes which are on the right-hand side of each FD of Q. Hence, we can say Q is a subset of P———–2
From 1 and 2 we can say that only Q is a subset of P since from 1 condition violated, hence option B is correct.
Q 3: Given a relational schema R( X, Y, Z ) set of functional dependencies P and Q such that:
P = { X → Y, Y → Z, Z → X } and Q = { X → YZ, Y → X, Z → X } using FD sets P and Q which of the following options are correct?
- P is a subset of Q
- Q is a subset of P
- P = Q
- P ≠ Q
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of P using FD set Q.
Given P = {X → Y, Y → Z, Z → X} and Q = {X → YZ, Y → X, Z → X}
Let us find closure of the left side of each FD of P using FD Q.
- X+ = XYZ (using X → YZ)
- Y+ = YZX (using X → YZ, Y → X)
- Z+ = ZXY (using X → YZ, Y → X, Z → X)
Now compare closure of each X, Y, Z calculated using FD Q with the right-hand side of FD P. Closure of each X, Y, Z has all the attributes which are on the right-hand side of each FD of P. Hence, we can say P is a subset of Q———-1
→Using definition of equivalence of FD set, let us determine the right-hand side of the FD set of Q using FD set P.
Given P = { X → Y, Y → Z, Z → X } and Q = { X → YZ, Y → X, Z → X }
Let us find closure of the left side of each FD of Q using FD P.
- X+ = XYZ (using X → Y, Y → Z, Z → X)
- Y+ = YZX (using Y → Z, Z → X)
- Z+ = ZXY (using X → Y, Y → Z, Z → X)
Now compare closure of each X, Y and Z calculated using FD P with the right-hand side of FD Q. Closure of each X, Y and Z has all the attributes which are on the right-hand side of each FD of Q. Hence, we can say Q is a subset of P———–2
From 1 and 2 we can say that P = Q, hence option C is correct.
Conclusion: From the above three questions solved for equivalence of FD, we noticed the following steps which are as follows:
STEP 1: Suppose two FD sets P and Q are given, write FD of each set P and Q separately.
STEP 2: Take FD set P first and then find closure of each attribute of the left side of FD in P using FD set Q.
STEP 3: Now compare the closure of each attribute of P with the right-hand side of FD of P.
STEP 4: If closure of each attribute is equal to the right-hand side of FD of P, we say P is a subset of Q
STEP 5: Take FD set Q next and then find closure of each attribute of the left side of FD in Q using FD set P.
STEP 6: Now compare the closure of each attribute of Q with the right-hand side of FD of Q.
STEP 7: If closure of each attribute is equal to right-hand side of FD of Q, we say Q is a subset of P
STEP 8: IF P is a subset of Q and Q is a subset of P, we can say P = Q.