BEBERAPA BENTUK ALGORITMA 4. 1
KETERGANTUNGAN BERLEBIHAN
MODIFIKASI
FUNGSIONAL
YANG
Keluaran dari Database dengan Algoritma di bagian 3.4 sedikit agak mudah tetapi sebenarnya dia mempunyai beberapa masalah tersembunyi. satu persoalan adalah proses pembusuknnya akan menjadi sulit akibat adanya ketergantungan fungsional yang berlebihan. Sebuah ketergantungan fungsional yang berlebihan adalah sesuatu ketergantungan fungsional yang tidak memiliki informasi yang tidak dapat ditemukan pada ketergantungan fungsionallainnya dalam himpunan kelompok yang dapat dipakai untuk merancang Database. Karena sebuah ketergantungan fungsional yang berlebihan tidak memiliki informasi, dia dapat dihilangkan dari sekelompok fungsional yang dipakai dalam proses perancangan, tanpa mempengaruhi hasilnya. Ketergantungan fungsional yang berlebihan dihilangkan sejak dari awal proses perancangan, sebelum kesalahan algoritma digunakan.
38
_ _ _ __
4.2
n
KETERGANTUNGAN
.--------
TRANSITIF
Salah satu eara yang tennudah yang dapat membuat sebuah ketergantungan fungsional yang berlebihan muneul dalam sekelompok fungsional yang berlebihan adalah jika fungsional itu telah dibuat melalui konsep dari ketergantungan transitif. Ketergantuhgan transitif didefinisikan sebagai berikut: Jika A ~ B dan B ~ C, maka A ~ C adalah transitif Dua hal harns dibuat di sini. Pertama, ketergantungan transitif A ->B, yang telah diberikan di atas, adalah ketergantungan yang benar. Tak ada yang tidak benar dengannya, kedua, jika A -> B dan B -> C dan A -> C adalah seluruh bagian dan sekelompok FD, maka A -> C adalah redundan dan tidak perlu digunakan dalam proses peraneangan. Tentu saja, ketergantungan transitif itu, A -> C, tidak akan mengganggu selama proses peraneangan, dan harus dihilangkan dari himpunan raneangan FD sebelum dekomposisi dimulai. Gambar 4.1 adalah sebuah contoh tentang bagaimana sekumpulan FD, dan diselenggarakan dengan menghilangkan FD yang transitif. Gambar 4.1(a) adalah himpunan dari FD yang tidak nonredundan yang didapat dengan menghilangkan semua ketergantungan transitif dari himpunan asal. Gmb. 4.2 memperlihatkan dekomposisi yang menghasilkan himpunan dari hubungan BCNF.
(a)
(b)
A ~ A ~ A ~ B ~ B ~ C ~
B C E C E E
A ~ A ~ B ~ B ~ C ~
B C C E E
The original set of FD's.
A~
E is removed, since A ~ C and C ~ E.
39
A
(c)
B ~
E is removed, since B ~
C and C
~
E.
A ~ B ~ C ~
A
(d)
A ~ C is removed, since A ~
Band
B ~ C, giving the non-redudant
B C E
set ofFD's
Gambar 4. 1 Penghilangan ketergantungan transitive 1. The FD diagram with no redundant FD's B
A
C
E
R(A, B, C, E)
2. Project out C ~ E, since it is the end of a chain of dependencies Rl (L, E)
R2 (A..., B, C) 2. Project out B ~
Cfrom R2(A, B, C). R1(C, E) R3(B, C,) R4(A, B)
R1, R3, and R4 are all in BCNF. With a little practice, the BCNF relations in part 3 can be written down directly from part 1.
Gambar 4. 2 Reduksi relasi dari gambar 4. 1 ke set dari relasi BCNF.
40
4.3
TAMBAHAN ATRIBUT PADA SEBUAH FD
Cara kedua untuk menghasilkan redundan FD adalah melalui konsep augmentasi. Bentuk dari redundan mempunyai beberapa variasi, dan hanya dua termudah, tetapi sangat berguna, dari bentuk-bentuk itu akan dibahas di sini. Variasi satu dapat dinyatakan sebagai berikut, di mana A, B, dan Z adalah atribut, salah satunya dapat berbentuk gabungan. Jika A ~ B, dan maka A< Z ~ B adalah benar, tapi adalah redundan FD. Atribut Z telah ditambahkan untuk menen-
tukan A, tanpamenambahinformasibarndalamproses.
.
Variasi kedua dari augmentasi teIjadi bila atribut yang sarnaditambahkan pada kedua bagian dari FD yang diberikan yang untuk membentuk FD yang barn. Jika A~ B, maka A, Z ~ B, Z adalah benar, tapi adalah redundan FD.
cgmentation
FD (redundant)
Gambar 4. 3 contoh-contoh dari Augmentation
41
4. 4
KAIDAH DARI INFERENSI
Definisi dari ketergamungan transitif dan augrnemasi di atas dibahas hanya rnengenai 2 dari 6 kaidah kesirnpulan. Kaidah-kaidah ini dapat dipakai untuk rnenolong rnengurangi, atau merubah, sekumpulan FD menjadi sekurnpulan FD yang lain, tapi sarna. Tiga lagi dari kaidah ini akan didiskusikan di sini secara singkat. Diskusi yang lengkap dari kaidah-kaidah kesirnpulanitu dapat ditemukan pada harnpir semua buku yang lebih rnendalarn rnernbahas database. Dua kaidah kesimpulan yang termudah untuk dipaharni berhubungan dengan hirnpunan dan pernecahan dari FD. Himpunan dan pernecahan didefinisikan sebagai : Hirnpunan dari FD: jika A -> B dan A:-> C, rnaka A -> B,C. Pernecahan dari FD: jika A -> B,C maka A -> B dan A -> C. Garnbar 4.4 rnemberikan garnbaran secara grafis dari setiap konsep ini dan Garnbar 4.5 memperlihatkan kita tentang bagairnana FD asal dapat dikurangi rnenjadi sekelompok nonredundan FD yang lebih rnudah mempergunakan konsep hirnpunan pernecahan dan augmentasi. Kaidah dari kesimpulan terakhir adalah PSEUDOTRANSITIVITY. Jika Xrn -> Y dan X, W -> Z adalah redundan akibat dari pseudotransitif. IF: Customer name
THEN:
(City)
Customer name
(State) (a)
IF:
THEN:
(Class) (Room) (b)
Gambar 4. 4 Contoh Gabungan & Dekornposisi 42
Contoh grafis dari pseudotransitif diberikan pada Gambar 4.6. Tipe dari redundant timbul pada kasus di mana gabungan dari determinan ditemukan pada FD yang dibuat. Contoh nyata diperlihatkan pada studi kasus di bab berikut.
B
C (a)
~ ~ ~ ~ ~ ~
B,C D K C D D
A A A K B
~ ~ ~ ~ ~
B,C D K C D
The original set of FDs.
B
c (b)
A A A K B B,C
B, C ~
D is removed (augmentation with B ~ D)
Gambar 4. 5 Reduksi Diagram FD menggunakan inferensi. 43
Untuk sebagian besar orang, bentuk grafts daTidiagram ketergantungan biasanya mempennudah untuk menemukan redundan FD, sebenarnya jika beberapa buah atribut dan FD terlihat menjadi benar, dan pendekatan grafis dapat menjadi tidak praktis uotuk dipegang. Pada kasus ini, terdapat algoritma matematis yang tersedia untuk mendapatkan redundan FD. Tidak terlalu sulit untuk digunakan, jika anda cenderung suka matematika.
44
