DATABASE
Uji Dekomposisi, Uji Lossless/Lossy, Uji Depedency Preservation
SLIDE 31
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 : C à (A,B,D), F à (G,H), 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)
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 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 dan (8) CD à CD dan (9) CD à CF maka CD à CDFGH (union)
Terbukti 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.
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 dan (6) CD à B dan (7) CD à CD, maka CD à ABCD (union)
Terbukti 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 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.
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 dan (3) W à Z dan (4) W à W, maka W à XZW (union)
W
à XZW ¹ W à XYZW
Terbukti 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 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.
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)
= ( )
R1, R2, R3 tidak
memiliki irisan, maka tidak dapat diuji.
Ø 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.
SLIDE 43
1. Diberikan R(A,B,C,D) dengan
FD : AàB, AàC, AàD
Apakah A candidate key dari R ?
Jawab :
(4) A à A (refleksif)
Dari (1) AàB, (2) AàC, (3) AàD, dan (4) A à A
Maka A à ABCD
A à R, jadi A adalah
superkey
Jika A adalah superkey dan hanya sendiri, maka A juga adalah
candidate key
2. Diberikan R(A,B,C,D) dengan
FD : AàB
a. Apakah ACD superkey
dari R
b. Apakah A candidate key
dari R
Jawab :
a. Dari (1) AàB, maka (2) ACD à BCD (augmentasi)
Dari ACD, maka (3) ACD à ACD (refleksif)
Dari (1) AàB, dan (3) ACD à ACD maka ACD à ABCD (union)
ACD à R, ACD
adalah superkey
b. A à A (refleksif)
Dari AàB, dan AàA maka A à AB (union)
A à AB ¹ A à ABCD / A à R
A bukan superkey,
bukan candidate key
3. Diberikan
R(A,B,C,D,E,F) dengan FD : Cà(AB), Bà(DE), EàF, AàBC
a. Carilah superkey dari R
b. Carilah candidate key
dari R
Jawab :
a. Untuk mencari superkey,
maka dari FD yang diketahui semua harus dibuktikan
u Untuk Cà(AB)
Dari CàAB, maka C à A dan C à B (dekomposisi)
Dari C à B, dan B à DE maka C à DE (transitif)
Dari C à DE, maka C à D dan C à E (dekomposisi)
Dari C à E, dan E à F maka C à F (transitif)
C à C (refleksif)
Dari C à A, C à B, C à DE, C à F, C à C, maka C à ABCDEF (union)
Terbukti. C à R, C adalah superkey
u Untuk FD (2) : Bà(DE)
Dari BàDE, maka B à D dan B à E (dekomposisi)
Dari B à E, dan E à F maka B à F (transitif)
Dari B à D, B à E, dan B à F, maka B à DEF (union)
tidak terbukti. B à DEF ¹ B à R, maka B bukan
superkey
u Untuk FD (3) : E à F
tidak terbukti. E à F ¹ E à R, E bukan superkey
u Untuk FD (4) : A à BC
Dari A à BC, maka A à B dan A à C (dekomposisi)
Dari A à C, diketahui bahwa C adalah
superkey C à R, maka A à R (transitif)
terbukti. A à R, maka A
adalah superkey
A & C adalah
superkey
b. A dan C
masing-masing sendirian, maka A & C juga adalah candidate key.
4. Diberikan R(A,B,C,D,E) dengan FD : Aà(BC), (CD)àE, BàD, EàA
a. Carilah superkey dari R
b. Carilah candidate key
dari R
Jawab :
a. Semua FD dibuktikan :
u Untuk Aà(BC)
Dari AàBC, maka A à B dan A à C (dekomposisi)
Dari A à B dan B à D maka A à D (transitif)
A à A (refleksif)
Dari A à B, A à C, A à D, dan A à A, maka A à ABCD (union)
tidak terbukti. A à ABCD ¹ A à R, maka A
bukan superkey
u Untuk FD (2) : (CD)àE
Dari CDàE, dan EàA maka CD à A (transitif)
Dari CD à A, dan AàBC maka CD à BC (transitif)
CD à CD (refleksif)
Dari CDàE, CD à A, CD à BC dan CD à CD, maka CD à ABCDE (union)
terbukti. CD à R, maka CD adalah superkey
u Untuk BàD
tidak terbukti. BàD ¹ BàR, maka B
bukan superkey
u Untuk EàA
Dari EàA, dan AàBC maka E à BC (augmentasi)
Dari AàBC maka A à B dan A à C (dekomposisi)
Dari A à B dan BàD maka A à D (transitif)
E à E (refleksif)
Dari EàA, E à BC, A à D dan E à E, maka E à ABCDE (union)
terbukti. E à R, maka E
adalah superkey
CD dan E adalah
superkey
b. ada 2
superkey yaitu CD dan E, maka E yang diambil sebagai candidate key.
5. Diberikan R(A,B,C) dengan
FD : AàB, BàC, CàA
Apakah A
merupakan satu-satunya candidate key dari R
u Untuk FD (1) : AàB
Dari (1) AàB, dan (2) BàC maka (4) A à C (transitif)
(5) A à A (refleksif)
Dari (1) AàB, (4) A à C, dan (5) A à A, maka A à ABC (union)
terbukti. A à R, maka A
superkey
u Untuk BàC
Dari BàC, dan CàA maka B à A (transitif)
B à B (refleksif)
Dari BàC, B à A dan B à B, maka B à ABC (union)
terbukti. B à R, maka B
superkey
u Untuk CàA
Dari CàA, dan AàB maka C à B (transitif)
C à C (refleksif)
Dari CàA, C à B dan C à C, maka C à ABC (union)
FD terbukti. C à ABC = C à R, maka C
superkey
A, B, dan C adalah
superkey. A, B, dan C juga candidate key. A tidak satu-satunya candidate key
dari R
