semoga bermanfaat buat pembaca sekalian......
Tugas Basis Data
Dekomposisi
SOAL
Ujilah dekomposisi dari skema relasi R, apakah lossless atau lossy ?
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)
2. R =
(A,B,C,D,E) didekomposisi menjadi :
R1 = (A,B,C,D) dan R2 =
(C,D,E) dengan FD :
A à B ; (C,D) à E ; B à D ; E à A
3. R =
(X,Y,Z,W,U,V) didekomposisi menjadi :
R1 = (X,Y,Z,W) dan R2 =
(W,U,V) dengan FD :
W à X ; X à Z
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)
Ujilah pula
dependency
preservation nya untuk masing-masing soal tsb
JAWABAN
1.
1. R=(A,B,C,D,E,F,G,H)
R1=(A,B,C,D,E) &
R2=(C,D,F,G,H)
FD= C à (A,B,D),
F à(G,H),D à (E,F)
*Uji Dekomposisi
R1 È R2=(A,B,C,D,E) È (C,D,F,G,H)
=(A,B,C,D,E,F,G,H)
=R
*Uji LOSSLESS/LOSSY
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)
C,D à A,B,C,D,E
C à A,B,D
(aug) maka C,D à A,B,D
D à E,F
maka
D à E
(decom)
D à F(decom)
C,D à C,E
(aug)
C,D à A,B,D
dan C,D à C,E maka
C,D à A,B,C,D,E terbukti
LOSSLESS
R1 Ç R2 à R2
(A,B,C,D,E) Ç (C,D,F,G,H) à (C,D,F,G,H)
C,D à (C,D,F,G,H)
D à E,F
maka D à E (decom)
D à F(decom)
D à F
dan F à G,H maka
D à G,H(trans)
C,D à C,G,H
(aug)
D à F
maka C,D à C,F(aug)
C,D à C,D
(reflek)
C,D àC,G,H
C,DàC,F
C,D à C,D maka C,D à C,D,F,G,H terbukti LOSSLESS
*Uji Dependency
preservation
R1=(A,B,C,D,E) dan
F1={C à (A,B,D)}
R2=(C,D,F,G,H) dan
F2={F à (G,H)}
jadi ada FD yang tidak
berlaku di R1 maupun R2 yaitu D à (E,F),maka terbukti R bukan
merupakan Dependency preservation
2. R=(A,B,C,D,E)
R1=(A,B,C,D) &
R2=(C,D,E)
FD= A à B,
C,D àE, B à D,
E à A
*Uji Dekomposisi
R1 È R2=(A,B,C,D) È (C,D,E)
=(A,B,C,D,E)
=R
*Uji LOSSLESS/LOSSY
R1 Ç R2 à R1 atau R1 Ç R2 à R2
R1 Ç R2 à R1
(A,B,C,D) Ç (C,D,E) à (A,B,C,D)
C,D à A,B,C,D
C,D à E
E à A (trans)
C,D à A
A à B
C,D à B
C,D à C,D (reflex)
jadi C,D à A,B,C,D terbukti
LOSSLESS
R1 Ç R2 à R2
(A,B,C,D) Ç (C,D,E) à(C,D,E)
C,D à C,D,E
C,D à E
C,D à C,D (reflex)
jadi C,D à C,D,E
terbukti LOSSLESS
*Uji Dependency
preservation
R1=(A,B,C,D) dan F1={A àB,
B à D)}
R2=(C,D,F,G,H) dan F2={(C,D )à E}
jadi ada FD yang tidak
berlaku di R1 maupun R2 yaitu E à A,maka terbukti R bukan
merupakan Dependency preservation
3. R=(X,Y,Z,W,U,V)
R1=(X,Y,Z,W) &
R2=(W,U,V)
FD= W à X,
X à Z
*Uji Dekomposisi
R1 È R2=(X,Y,Z,W) È (W,U,V)
=(X,Y,Z,W,U,V)
=R
*Uji LOSSLESS/LOSSY
R1 Ç R2 à R1
atau R1 Ç R2 à R2
R1 Ç R2 à R1
(X,Y,Z,W) Ç (W,U,V) à(X,Y,Z,W)
W à X,Y,Z,W
W à X dan X à Z
maka X à Z (trans)
W à X, W à Z
jadi W à Z
W à X,Y,Z,W
R1 Ç R2 à R1
(X,Y,Z,W) Ç (W,U,V) à (W,U,V)
W à (W,U,V)
W à W (reflek)
hanya ada W à W maka
W à
(W,U,V) terbukti LOSSY
*Uji Dependency
preservation
R1=(X,Y,Z,W) dan F1={W à X, X à Z}
F1 È F2 = W à X
dan X à Z
= W à Z
(F1 È F2)+ ={W à X,
X à Z, W à Z}
= F+
Jadi R terbukti
memenuhi Dependency preservation
4. R=(A,B,C,D,E,F)
R1=(A,B,C), R2=(A,D,F)
& R3=(E,D)
FD= A à (B,C),
D à (F,A)
*Uji Dekomposisi
R1 È R2 È R3=(A,B,C) È (A,D,F) È(E,D)
=(A,B,C,D,E,F)
=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.
1. Diberikan R(A,B,C,D) dengan FD
: AàB,AàC dan AàD
Apakah A candidate
key dari R ?
2. Diberikan R(A,B,C,D) dengan FD
: AàB
a. Apakah ACD superkey dari R
b. Apakah A candidate
key dari R
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
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
5. Diberikan R(A,B,C) dengan FD
: AàB;BàC;CàA
Apakah A merupakan satu-satunya candidate
key dari R
JAWABAN
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
Perhatikan Tabel berikut
