Question on Dependency Preserving Decomposition
Question 1:
R(ABCD)
F = {A → B, B → C, C → D, D → A}
D = {AB, BC, CD}
Check whether the decomposition is preserving dependency or not ?
Solution :
The following dependencies can be projected into the following decomposition :
| R1(AB) |
R2(BC) |
R3(CD) |
| A→B |
B→C |
C → D |
|
Inferring reverse FDs which fits into the decomposition-
B+ w.r.t F = {BCDA} ⇒ B → A
C+ w.r.t F = {CDAB} ⇒ C → B
D+ w.r.t F = {DABC} ⇒ D → C
So, the table will be updated as -
| R1(AB) |
R2(BC) |
R3(CD) |
| A→B
B→A |
B→C
C→B |
C → D
D→C |
|
Checking D → A preserves dependency or not -
Compute D+ w.r.t updated table FDs :
D+ = {DCBA}
as closure of D w.r.t updated table FDs contains A. So D→A preserves dependency.
Question 2:
R(ABCDEF)
F = {AB → CD, C → D, D → E, E → F}
D = {AB, CDE, EF}
Check whether the decomposition is preserving dependency or not ?
Solution :
The following dependencies can be projected into the following decomposition :
| R1(AB) |
R2(CDE) |
R3(EF) |
|
C→D
D→E |
E → F |
|
Inferring reverse FDs which fits into the decomposition-
D+ w.r.t F = {DEF}
E+ w.r.t F = {EF}
F+ w.r.t F = {F}
No reverse FDs can be derived.
Checking AB → CD preserves dependency or not -
Compute AB+ w.r.t table FDs :
AB+ = {AB}
as closure of AB w.r.t table FDs does not contains CD. So AB→CD preserves dependency.
Question 3:
R(ABCDEG)
F = {AB → C, AC → B, BC → A, AD → E, B → D, E → G}
D = {ABC, ACDE, ADG}
Check whether the decomposition is preserving dependency or not ?
Solution :
The following dependencies can be projected into the following decomposition :
| R1(ABC) |
R2(ACDE) |
R3(ADG) |
| AB→C
AC→B
BC→A |
AD→E |
|
|
Inferring reverse FDs which fits into the decomposition-
C+ w.r.t F = {C}
B+ w.r.t F = {BD}
A+ w.r.t F = {A}
E+ w.r.t F = {EG}
No reverse FDs can be derived.
Checking B → D preserves dependency or not -
Compute B+ w.r.t updated table FDs :
B+ = {B}
as closure of B w.r.t table FDs doesn't contains D. So B→D doesn't preserves dependency.
Checking E → G preserves dependency or not -
Compute E+ w.r.t updated table FDs :
E+ = {E}
as closure of E w.r.t table FDs doesn't contains G. So E→G doesn't preserves dependency.
Question 4:
Let R(ABCD) be a relational schema with the following functional dependencies :
F = {A → B, B → C, C → D, D → B}. The decomposition of R into
D = {AB, BC, BD}
Check whether the decomposition is preserving dependency or not ?
Solution :
The following dependencies can be projected into the following decomposition :
| R1(AB) |
R2(BC) |
R3(BD) |
| A→B |
B→C |
D → B |
|
Inferring reverse FDs which fits into the decomposition-
B+ w.r.t F = {BCD} ⇒ B → D
C+ w.r.t F = {CDB} ⇒ C → B
So, the table will be updated as -
| R1(AB) |
R2(BC) |
R3(CD) |
| A→B |
B→C
C→B |
D→B
B→D |
|
Checking C → D preserves dependency or not -
Compute C+ w.r.t updated table FDs :
C+ = {CBD}
as closure of C w.r.t updated table FDs contains D. So C→D preserves dependency.
Question 5:
R(ABCDE)
F = {A → BC, CD → E, B → D, E → A}
D = {ABCE, BD}
Check whether the decomposition is preserving dependency or not ?
Solution :
The following dependencies can be projected into the following decomposition :
| R1(ABCE) |
R2(BD) |
| A→B
A→C
E→A |
B→D |
|
Inferring reverse FDs which fits into the decomposition-
B+ w.r.t F = {BD}
C+ w.r.t F = {C}
A+ w.r.t F = {ABCDE} ⇒ A → E
D+ w.r.t F = {D}
So, the table will be updated as -
| R1(AB) |
R2(BC) |
| A→B
A→C
E→A
A→E |
B→D |
|
Checking CD → E preserves dependency or not -
Compute CD+ w.r.t updated table FDs :
CD+ = {CD}
as closure of D w.r.t updated table FDs doesn't contains E. So CD→E doesn't preserves dependency.
]]>