Ujilah
dekomposisi dari skema relasi R, apakah lossless atau lossy ?
Ujilah
pula dependency preservation nya untuk masing-masing soal tsb.
1. R = (A,B,C,D,E,F,G,H)
didekomposisi menjadi :
R1 =
(A,B,C,D,E) dan R2 = (C,D,F,G,H),
dengan FD
:
(1) C → (A,B,D)
(2)
F → (G,H)
(3)
D → (E,F)
Jawab :
- Uji Dekomposisi
R1 ∪ R2 = (A, B, C, D, E) ∪ (C, D, F, G, H)
= (A, B, C, D, E, F, G, H)
= R
.:. Terbukti
bahwa {R1,R2} adalah dekomposisi dari R.
- Uji Lossless / Lossy
R1 ∩ R2 = (A, B, C, D, E) ∩ (C, D, F, G, H)
= (C, D)
Akan dibuktikan
bahwa paling sedikit satu kondisi berikut dipenuhi :
R1 ∩ R2 → R1 atau R1 ∩ R2 → R2
R1 ∩ R2 → R1
(A, B, C, D, E) ∩ (C, D, F, G, H) → (A, B, C, D, E)
CD → ABCDE
Dari
(1) C → ABD, maka (4) CD → ABD (augmentasi)
Dari
(3) D → EF, maka (5) D → E dan (6) D → F (dekomposisi)
Dari
(5) D → E, maka (7) CD → CE (augmentasi)
Dari
(4) CD → ABD dan
(7) CD → CE
maka CD → ABCDE (union)
.:.
Terbukti bahwa {R1,R2} adalah LOSSLESS
R1 ∩ R2 → R2
(A, B, C, D, E) ∩ (C, D, F, G, H) → (C, D, F, G, H)
CD → CDFGH
Dari
(3) D → EF, maka (4) D → E dan (5) D → F (dekomposisi)
Dari
(5) D → F dan (2) F → GH maka (6) D → GH (transitif)
Dari
(6) D → GH, maka (7) CD → CGH (augmentasi)
Dari CD, maka (8) CD → CD (refleksif)
Dari
(5) D → F, maka (9) CD → CF (augmentasi)
Dari
(7) CD → CGH
(8) CD → CD dan
(9) CD → CF
maka CD → CDFGH (union)
.:.
Terbukti bahwa {R1,R2} adalah LOSSLESS
- Uji Dependency Preservation
R =
(A,B,C,D,E,F,G,H) dan F = { C → ABD, F → GH, D → EF }
Maka dapat
dibentuk closure :
F+ = {
C → ABD, F → GH, D → EF }
R1 = (A,B,C,D,E)
dan F1 = { C →
ABD }, karena hanya C →
ABD yang berlaku di R1
R2 = (C,D,F,G,H)
dan F2 = { F →
GH }, karena hanya F →
GH yang berlaku di R2
F1 ∪ F2 = { C → ABD, F → GH }
Sehingga
(F1 ∪ F2 )+ = { C → ABD, F → GH }
≠ F+
.:. Jadi dekomposisi tersebut tidak memenuhi Dependency Preservation.
NB : meski dari (F1 ∪ F2 )+ = { C → ABD, F → GH } diturunkan berdasar sifat-sifat FD, tetap tidak
memenuhi Dependency Preservation, karna ada 1 FD yaitu D → EF yang tidak berlaku di R1
maupun R2. Yang penting adalah semua FD berlaku dahulu baru diturunkan.
2. R = (A,B,C,D,E) didekomposisi
menjadi :
R1 = (A,B,C,D) dan R2 = (C,D,E),
dengan FD :
(1) A → B
(2) (C,D) → E
(3) B → D
(4) E → A
Jawab :
- Uji Dekomposisi
R1 ∪ R2 = (A, B, C, D) ∪ (C, D, E)
= (A, B, C, D, E)
= R
.:. Terbukti
bahwa {R1,R2} adalah dekomposisi dari R.
- Uji Lossless / Lossy
R1 ∩ R2 = (A, B, C, D) ∩ (C, D, E)
= (C, D)
R1 ∩ R2 → R1
(A, B, C, D) ∩ (C, D, E) → (A, B, C, D)
CD → ABCD
Dari
(2) CD → E dan (4) E → A, maka (5) CD → A (transitif)
Dari
(5) CD → A dan (1) A → B, maka (6) CD → B (transitif)
Dari CD, maka (7)
CD → CD (refleksif)
Dari
(5) CD → A
(6) CD → B dan
(7) CD → CD,
maka CD → ABCD (union)
.:.
Terbukti bahwa {R1,R2} adalah LOSSLESS
R1 ∩ R2 → R2
(A, B, C, D) ∩ (C, D, E) → (C, D, E)
CD → CDE
Dari CD, maka (5)
CD → CD (refleksif)
Dari
(2) CD → E dan
(5) CD → CD,
maka CD → CDE (union)
.:.
Terbukti bahwa {R1,R2} adalah LOSSLESS
- Uji Dependency Preservation
R = (A,B,C,D,E)
dan F = { A →
B, CD → E, B → D, E → A }
Dari A → B dan B → D bisa dibentuk A → D (transitif)
Dari CD → E dan E → A bisa dibentuk CD → A (transitif)
Maka dapat
dibentuk closure :
F+ = {
A → B, CD → E, B → D, E → A, A → D, CD → A }
R1 = (A,B,C,D)
dan F1 = { A →
B, B → D }, karena A → B dan B → D yang berlaku di R1
R2 = (C,D,E) dan F2
= { CD → E }, karena hanya CD → E yang berlaku di R2
F1 ∪ F2 = { A → B, B → D, CD → E }
Dari A → B dan B → D bisa dibentuk A → D (transitif)
Sehingga
(F1 ∪ F2 )+ = { A → B, B → D, CD → E, A → D }
≠ F+
.:. Jadi
dekomposisi tersebut tidak memenuhi Dependency Preservation.
NB : ada 1 FD
yaitu E → A yang tidak berlaku di R1
maupun R2.
3. R = (X,Y,Z,W,U,V) didekomposisi
menjadi :
R1 = (X,Y,Z,W) dan R2 = (W,U,V),
dengan FD :
(1) W → X
(2) X → Z
Jawab :
- Uji Dekomposisi
R1 ∪ R2 = (X, Y, Z, W) ∪ (W, U, V)
= (X, Y, Z, W, U, V)
= R
.:. Terbukti
bahwa {R1,R2} adalah dekomposisi dari R.
- Uji Lossless / Lossy
R1 ∩ R2 = (X, Y, Z, W) Ç (W, U, V)
= (W)
R1 ∩ R2 → R1
(X, Y, Z, W) ∩ (W, U, V) → (X, Y, Z, W)
W → XYZW
Dari
(1) W → X dan (2) X → Z, maka (3) W → Z (transitif)
Dari CD, maka (4)
W → W (refleksif)
Dari
(1) W → X
(3) W → Z dan
(4) W →W
maka W → XZW (union)
W → XZW ≠ W → XYZW
.:.
Terbukti bahwa {R1,R2} adalah LOSSY
R1 ∩ R2 → R2
(X, Y, Z, W) ∩ (W, U, V) → (W, U, V)
W → WUV
Dari CD, maka (4)
W → W (refleksif)
W → W ≠ W → XYZW
.:.
Terbukti bahwa {R1,R2} adalah LOSSY
- Uji Dependency Preservation
R = (X,Y,Z,W,U,V)
dan F = { W →
X, X → Z }
Dari W → X dan X → Z bisa dibentuk W → Z (transitif)
Maka dapat
dibentuk closure :
F+ = {
W → X, X → Z, W → Z }
R1 = (X,Y,Z,W)
dan F1 = { W →
X, X → Z }, karena W → X dan X → Z yang berlaku di R1
R2 = (W,U,V) dan F2
= { }, karena tidak ada FD berlaku di R2
F1 ∪ F2 = { W → X, X → Z }
Dari W → X dan X → Z bisa dibentuk W → Z (transitif)
Sehingga
(F1 ∪ F2 )+ = { W → X, X → Z, W → Z }
= F+
.:. Jadi
dekomposisi tersebut memenuhi Dependency Preservation.
NB : meskipun
tidak ada FD yang berlaku di R2, namun semua FD sudah masuk dalam himpunan F+
4. R = (A,B,C,D,E,F) didekomposisi
menjadi :
R1 = (A,B,C), R2 = (A,D,F) dan R3 = (E,D),
dengan FD :
A → (B,C)
D → (F,A)
Jawab :
- Uji Dekomposisi
R1 ∪ R2 ∪ R3 = (A, B, C) ∪ (A, D, F) ∪ (E, D)
= (A, B, C, D, E, F)
= R
.:. Terbukti
bahwa {R1,R2} adalah dekomposisi dari R.
- Uji Lossless / Lossy
R1 ∩ R2 ∩ R3 = (A, B, C) ∩ (A, D, F) ∩ (E, D)
= ( )
Akan dibuktikan bahwa paling
sedikit satu kondisi berikut dipenuhi :
R1 ∩ R2 ∩ R3 → R1 atau R1 ∩
R2 ∩ R3 → R2 atau R1 ∩
R2 ∩ R3 → R3
Tapi ternyata R1 ∩ R2 ∩ R3 = ( ), artinya dari hasil
dekomposisi R, yaitu R1, R2, R3 tidak memiliki irisan, maka Uji Lossless /
Lossy tidak dapat dilakukan.
- Uji Dependency Preservation
R = (A,B,C,D,E,F)
dan F = { A →
BC, D → FA }
Maka dapat
dibentuk closure :
F+ = {
A → BC, D → FA }
R1 = (A, B, C)
dan F1 = { A →
BC }, karena hanya A →
BC yang berlaku di R1
R2 = (A, D, F)
dan F2 = { D → FA }, karena hanya D →
FA yang berlaku di R2
R3 = (E, D) dan F3
= { }, karena tidak ada FD berlaku di R3
F1 ∪ F2 = { A → BC, D → FA }
Sehingga
(F1 ∪ F2 )+ = { A → BC, D → FA }
= F+
.:. Jadi
dekomposisi tersebut memenuhi Dependency Preservation.
Tidak ada komentar:
Posting Komentar