Consider the relation scheme R = {A, B, C, D, E, G} and the set of functional de
ID: 3860156 • Letter: C
Question
Consider the relation scheme R = {A, B, C, D, E, G} and the set of functional dependencies for the relation R are F = {AB C, AC B, ABD E, D B, BC A, E G}.
a) Find all candidate keys of F.
b) Derive a canonical cover for F in a systematic manner.
c) Find a 3NF decomposition for R that is lossless and dependency preserving.
d) is R in BCNF? if it is not in BCNF, find a BCNF Decomposition that is lossless. Is your BCNF decomposition in (c) dependency-preserving?
e) If R is decomposed into {ABC, ACDE, ADG}, will the decomposition lead to a lossless-join? Is the dependency preserved (if-any)?
Explanation / Answer
a) Find all candidate keys of F.
Solution
********
AB C,
AC B,
ABD E,
D B,
BC A,
E G
Attribute which is not present in right hand side is the candidate Key.
so here D is the candidate Key.
b) Derive a canonical cover for F in a systematic manner.
Solution
**********
A canonical cover of a set of functional dependencies F is a simplified set of functional dependencies that has the same closure as the original set F.
A canonical cover F_{c} of a set of functional dependencies F such that ALL the following properties are satisfied.
Each left side of a functional dependency in F_{c} is unique.
F = {
AB C,
AC B,
ABD E,
D B,
BC A,
E G
}.
Steps to find canonical cover:
Step1 : There are two functional dependencies with the same set of attributes on the left
AB C
AC B
These two can be combined to get
AB->C
Now, the revised set F becomes:
F={
AB->C
AC->B
ABD->E
D->B
BC->A
E->G
}
Step2
There is an extraneous attribute in AB -> C because even after removing AB-> C from the set F, we get the same closures.
This is because AC->B is already a part of F.
Now, the revised set F becomes:
F={AB->C
ABD->E
D->B
BC->A
E->G
}
AB->C
BC->A
Thesw two can be combined to get
BA->C
Now the revised set becomes
F={
AB->C
ABD->E
D->B
E->G
}
After this step, F does not change anymore. So,
Hence the required canonical cover is,
F={
AB->C
ABD->E
D->B
E->G
}
c) Find a 3NF decomposition for R that is lossless and dependency preserving.
Solution
**********
R1 = {A,B,C,D} R2 ={A,D,E,G}
Since R1 R2 = A, and A is a key for R1, the decomposition is loseless join.
The decomposition of a relation scheme R with FDs F is a set of tables (fragments) Ri with FDs Fi
Fi is the subset of dependencies in F+ (the closure of F) that include only attributes in R.
The decomposition is dependency preserving iff
(UiFi)+ = F+
d) is R in BCNF? if it is not in BCNF, find a BCNF Decomposition that is lossless. Is your BCNF decomposition in (c) dependency-preserving?
Solution
**********
First, find all the keys of R: AD,CD
(The core of all the keys is D.)
Thus, R is not in BCNF yet.Then, decompose R into BCNF:
ABCDEG
| AB C
ABDEG and ABC
|D B
ADEG and BD
|E G
ADE and EG
So the BCNF decomposition is: ADE, EG, BD, and ABC.
e) If R is decomposed into {ABC, ACDE, ADG}, will the decomposition lead to a lossless-join? Is the dependency preserved (if-any)?
Solution
********
Since we have:
ABCDEG
| ACB
ACDEG and ABC
which is lossless -join.
And the decomposition of
ACDEG into ACDE, ADG is also lossless -join (because AD is a key).Thus the decomposition of {ABC, ACDE, ADG}is lossless-join.
It is not dependency preserving since EG is not preserved.