Tugas Basis Data 3 - Dependensi Fungsional

TUGAS BASIS DATA III DEPENDENSI FUNGSIONAL

Oleh: 1. Phie Chyan (631) 2. Rajim Laymond.S. (633) 3. Sherly Jayanti (635)

UNIVERSITAS GADJAH MADA JOGJAKARTA

1

Bab 4. DEPENDENSI FUNGSIONAL SOAL – SOAL SUPPLEMEN DARI BUKU FUNDAMENTALS OF RELATIONAL DATABASES 4.13. Untuk setiap FD dibawah ini berikanlah instance dari relasi r (R) yang menunjukkan bahwa FD tersebut bukan merupakan aturan inferensi yang valid a. Jika A  B maka B  A Jawaban: FD di atas bukan merupakan aturan inferensi yang valid, seperti yang ditunjukkan oleh instance dari relasi r dibawah, kota  negara tapi tidak benar bahwa negara  kota r kota

negara

jakarta

Indonesia

bandung

Indonesia

b. Jika AB  C maka A  C Jawaban: FD di atas bukan merupakan aturan inferensi yang valid,seperti yang ditunjukkan oleh instance dari relasi r dibawah bahwa benar nama_depan ∪ nama_belakang  jurusan akan tetapi tidak benar bahwa nama_depan  jurusan dengan asumsi tidak ada seorang pun yang memiliki nama lengkap yang sama dalam satu jurusan akan tetapi mungkin saja seseorang memiliki nama depan yang sama r nama_depan

nama_belakang

jurusan

Adi

Chandra

ILKOM

Hendra

Yusuf

MMI 2

c Jika AB  C maka B  C Jawaban: FD di atas bukan merupakan aturan inferensi yang valid,seperti yang ditunjukkan oleh instance dari relasi r dibawah bahwa benar nama_depan ∪ nama_belakang  jurusan akan tetapi tidak benar bahwa nama_belakang jurusan dengan asumsi tidak ada seorang pun yang memiliki nama lengkap yang sama dalam satu jurusan akan tetapi mungkin saja seseorang memiliki nama belakang yang sama r nama_depan

nama_belakang

jurusan

Adi

Chandra

ILKOM

Hendra

Yusuf

MMI

4.14. Asumsikan bahwa ada sekumpulan FD yang memenuhi untuk sebuah relasi r(A,B,C). sebuah instansi dari relasi ini ditunjukkan dibawah. cari dependensi fungsional yang dipenuhi oleh r A

B

C

f

e

e

d

e

e

b

c

e

a

c

d

a

b

c

Jawaban: untuk menentukan dependensi fungsional bila diketahui sebuah relasi r(R) dengan attribut A dan B (A dan B dapat berupa atribut komposit), dapat dikatakan bahwa atribut A secara fungsional menentukan atribut B dalam r (dinotasikan dengan A  B) , jika dan hanya jika untuk sembarang dua tuple t1 dan t2 maka jika t1(A) = t2(A) maka t1(B) = t2(B). Untuk mencari dependensi fungsional yang dipenuhi oleh r kita dapat mencoba beberapa dari kombinasi yang memungkinkan sebagai berikut : 3

A  B (tidak memenuhi) karena t4(A) = t5(A) = a, tetapi t4(B) = c ≠ t5(B) = b A  C ( tidak memenuhi) karena t4(A) = t5(A) = a, tetapi t4(C) = d ≠ t5(C) = c B  A (tidak memenuhi) karena t1(B) = t2(B) = e, tetapi t1(A) = f ≠ t2(A) = d B  C (tidak memenuhi) karena t3(B) = t4(B) = c, tetapi t3(C) = e ≠ t4(C) = d C  A (tidak memenuhi) karena t1(C) = t2(C) = e, tetapi t1(A) = f ≠ t2(A) = d C  B (tidak memenuhi) karena t1(C) = t2(C) = e, tetapi t1(B) = f ≠ t2(B) = d AB  C (memenuhi) karena tidak terdapat tuple yang identik pada kolom ( A ∪ B) AC  B (memenuhi) karena tidak terdapat tuple yang identik pada kolom ( A ∪ C) BC  A (tidak memenuhi) karena t1(BC) = t2(BC) = ee, tetapi t1(A) = f ≠ t2(A) = d jadi dependensi fungsional yang memenuhi untuk relasi r adalah AB  C dan AC B

4.15. Carilah kandidate key untuk relasi r (X, Y,Z,W,P) jika seluruh FD dari himpunan F = {Y  Z, Z  Y, Z  W, Y  P} berlaku untuk seluruh anggota r. Jawaban: XY dan XZ adalah satu-satunya candiate key dari relasi r XY menjadi kandidate key, dimana tidak ada atribut dari relasi r yang berfungsi sebagai determinan untuk atribut XY, malah sebaliknya atribut XY berfungsi sebagai determinan, secara fungsional menentukan atribut seluruh anggota r. XZ menjadi kandidate key, berfungsi sebagai determinan, secara fungsional menentukan atribut Y dan W dan juga P ( Y  Z, Z  Y, Y  P).

4.16. Dengan menggunakan aksioma inferensi perlihatkan bahwa F = XY  Q, dengan F = {XY  W, Y  Z, WZ  P, WP  QR, Q  X} Jawaban : a.Dari WZ  P di (ketahui) dan WP  QR (diketahui) menghasilkan WWZ  QR (aksioma Pseudotransivitas). FD yang terakhir dapat ditulis ulang sebagai WZ  QR (Perangkaian berlaku untuk union dan W ∪ W = W). b.Dari WZ  QR (langkah sebelumnya) dan Y  Z (diketahui) menghasilkan WY  QR (Aksioma Pseudo transivitas). 4

c.Dari WY  QR (langkah sebelumnya) dan XY  W (diketahui) menghasilkan XYY  QR (aksioma Pseudotransivitas) FD yang terakhir dapat di tulis ulang sebagai XY  QR (Perangkaian berlaku untuk union da Y ∪ Y = Y). d.Dari XY  QR (langkah sebelumnya) menghasilkan XY  Q (aksioma Projektivitas)

4.17. Dengan menggunakan (XY) + perlihatkan bahwa F = XY  Q dengan F = {XY  W, Y  Z, WZ  P, WP  QR, Q  X}. Carilah bentuk asal dari XY  Q menggunakan aksioma inferensi. Yakinkan bahwa bentuk asal ini berbeda dari bentuk yang diperoleh dari soal sebelumnya. Jawaban: (XY)+ = {XYWZPQR}. Q ∈ (XY)+, oleh karena itu F = XY  Q Dengan menggunakan Y  Z (diketahui) dan WZ  P (diketahui) kita memperoleh WY  P (aksioma Pseudotransivitas). Dengan menggunakan hasil terakhir WP  QR (diketahui), kita memperoleh WWY  QR. Mengetahui bahwa W ∪ W = W, kita dapat menulis ulang FD terakhirnya sebagai berikut : WY  QR. Dengan hasil terakhir ini dan XY  W (diketahui), kita mendapati bahwa XYY  QR. Determinan dari FD ini dapat di tulis sebagai XY  QR ketika Y ∪ Y. Dengan menggunakan XY  QR dan aksioma Projektivitas kita mendapatkan XY  Q

4.18. Hilangkan extraneous left attributes yang ada dari F ={ A  BC, E C, D  AEF, ABF  BD }. Jawaban: untuk mencari extranous left attribute pada set F diatas kita dapat mengabaikan FD yang determinannya terdiri dari attribut tunggal seperti ABC, EC, DEF karena tidak mungkin mengandung extranous left attribute, sehingga yang perlu kita uji hanya satu FD yaitu ABF  BD Langkah (1) Set G ={ A  BC, E C, D  AEF, ABF  BD} Langkah (2.1) Pilih ABF  BD dan lanjut ke langkah berikutnya Langkah (3.1) Dari FD sebelumnya pilih salah satu attribut dari determinan, pertama kita pilih A dan menguji jika sisi kanan dari FBD ada dalam klosur dari F terhadap G. karena {BD} ⊄ F maka A bukan extranous left attribute Langkah(3.1.1) Dari FD sebelumnya pilih salah satu attribut dari determinan, pertama kita pilih A dan menguji jika sisi kanan dari BBD ada dalam klosur dari B terhadap G. kita memiliki B = (BD). karena {B} ⊃ B, maka attribut B merupakan extranous left attribute sehingga atribut ini dapat dihilangkan dari FD 5

sehingga kita memiliki left-reduce cover untuk F adalah : G = { A  BC, E C, D  AEF, AF  BD}.

4.19. Cari Canonical cover untuk set F dari soal 4.18 Jawaban: Canonical cover yang dinotasikan dengan Fc adalah sekumpulan FD dimana semua kondisi dibawah ini terpenuhi secara simultan : (1)Setiap FD dari Fc bersifat ringkas, artinya sisi kanan dari setiap dependensi fungsional dari Fc hanya memiliki satu attribut (2)Fc dalam keadaan left-reduced (3)Fc non redundan Dari soal sebelumnya kita mendapatkan bentuk left-reduced dari set F sebagai berikut Fc { A  BC, E C, D  AEF, AF  BD}. dengan menggunakan projectivity axiom, kita dapat menuliskan: Fc {A  B, A  C, E  C, D  A , D  E, D  F, AF B, AF  D} dari set Fc diatas, dapat kita lihat bahwa AF  B merupakan FD yang redundan, karena dapat kita turunkan dari A  B dengan menggunakan inference axioma augmentasi, sehingga kita dapat mengeliminasi AF  B dari Fc . Maka hasil dari canonical cover dari F yang memenuhi persyaratan ringkas, left-reduced dan non redundan adalah : Fc {A  B, A  C, E  C, D  A , D  E, D  F, AF  D}

6