BAB IV PERANCANGAN BASIS DATA RELASIONAL
1.1
KETERGANTUNGAN FUNGSIONAL & MULTI NILAI
1.1.1
Ketergantungan Fungsional (Functional Dependency (FD))
Adalah ketergantungan nilai-nilai dari satu atau beberapa atribut terhadap satu atribut atau himpunan atribut lainnya. Notasi : Y ➔ X Biasa digunakan untuk menunjukkan bahwa X tergantung secara fungsional terhadap Y. Atribut Y dikenal sebagai determinant dari FD Y ➔ X Contoh :
Person_ID, Project ➔ Time_Spent_By, Person_On_Project
Notasi X ↔ Y berarti X ➔ Y dan Y ➔ X
Contoh diagram functional dependency : Project
Project Budget
Person-ID Project
1.1.2
Time_spent_By_ person_on_project
Functional Dependency Penuh
Atau Full Functional Dependency, biasa digunakan untuk mengindikasikan himpunan atribut minimum dalam sebuah determinant dari satu FD. Himpunan atribut x akan bergantung secara fungsional penuh (fully functionally dependent) pada himpunan atribut y jika : 1.
x bergantung secara fungsional pada y
2.
x tidak bergantung secara fungsional pada suatu sub-himpunan dari y.
contoh :
-
Person_ID, Project, Project_budget ➔Time_spent_By_Person_on_Project ➔ Bukan suatu FD penuh
-
Person_ID, Project ➔ Time_spent_by_Person_on_Project ➔ suatu FD penuh karena : Person_ID ➔ Time_spent_By_Person_on_Project maupun Project ➔ Time_spent_By_Person_on_Project, Tidak memenuhi syarat sebagai FD penuh.
Contoh diagram FD yang lebih kompleks :
Manager_Name
Warehouse_address
warehouse_name
part_no
QTY_in_store_on_date
supplier_name
delivery_number
inventory_date
QTY_delivered
Sifat-sifat FD : 1. Redundan FD Sebuah FD dalam himpunan FD dikatakan redundan jika FD tersebut dapat diturunkan dari FD lainnya dalam himpunan FD. Cara untuk mendeteksi sebuah FD redundan dengan langkah-langkah sebagai berikut : 1.
tentukan S sebagai himpunan dari FD.
2.
hapus satu FD misal f dan susun himpunan FD S’ = S – f
3.
test apakah f dapat diturunkan dari DS-FD dalam S’ dengan menggunakan himpunan rule
4.
jika f dapat diturunkan, berarti f redundan, ➔ S = S’. Jika tidak, masukkan f ke dalam himpunan S’ sedemikian sehingga S = S’ + f.
5.
ulangi langkah ke-2 sampai 4 semua FD dalam S.
himpunan rule-relu digunakan untuk menghindari looping pada langkah ke-3.
Himpunan rule-rule (set of rule) (Amstrong,1974 & Beeri at.al 1978) terdiri dari : -
jika Y ⊆ X, maka X → Y (refleksi)
-
jika Z ⊆ W, dan X → Y, maka XW → YZ ( augmentasi)
-
jika X → Y dan Y → Z, maka X → Z (transitive)
Dalam prakteknya, terdapat aturan-aturan tambahan yaitu : -
jika X → Y dan YW → Z, maka XW → Z (pseudotransitive)
-
jika X → Z dan X → YZ (union)
-
jika X → YZ, maka X → Y dan Y → Z ( dekomposisi)
contoh : Himpunan FD : { Z → A, B → X, AX →Y, ZB → Y} Akan ditunjukkan bahwa ZB → Y adalah redundan. 1.
Z →A dengan augmentasi menghasilkan ZB →AB
2.
B → X dan AX →Y dengan pseudotransitive menghasilkan AB → Y
3.
ZB → AB dengan transitive menghasilkan ZB → Y
1.1.3
Algoritma Keanggotaan
Digunakan untuk menentukan apakah suatu FD, f(A → B), dapat diturunkan dari satu himpunan FD, sbb : 1. T = A, T adalah variable yang mengandung satu himpunan atribut-atribut A adalah determinant dari f. 2. lihat FD yang lain untuk melihat apakah sebuah FD X →Y ditemukan, tambahkan atribut-atribut dalam pada himpuanan atribut-atribut dalam T ( aturan union & transitive)
3. Ulangi langkah-langkah setiap kali T dirubah hingga tidak ada lagi atribut-atribut yang dapat ditambahkan pada T. 4. Jika pada akhir algoritma B berada dalam T, maka A → B dapat diturunkan dari FD lain dalam S ( aturan dekomposisi).
Contoh : Himpunan FD : { Z → A, B → X, AX →Y, ZB → Y} 1.
T = ZB
2.
T = ZB + A = ZBA, karena Z → A berada dalam sisa himpunan FD dan Z⊆T. T = ZBA + X = ZBAX, karena B → X berada dalam sisa himpunan FD dan B⊆T. T = ZBAX + Y = ZBAXY karena AX → Y berada dalam sisa himpuanan FD dan AX ⊆ T.
4.1.4 Closure Sebuah closure mendefinisikan semua fungsional dependency yang dapat diturunkan dari satu himpunan FD yang diberikan. Notasi F+ digunakan untuk menunjukkan closure dari himpuanan dependensi. Contoh
:
F = { X → Y, Y → Z, YZ → W, WX → Y} Dari himpunan FD di atas diturunkan FD yang lain, seperti : X → Z dengan transitive dari X → Y dan Y → Z Atau XZ → W dengan pseudotransitive dari X → W dan YZ → W
Untuk memastikan /menentukan apakah semua FD yang mungkin diturunkan dari satu himpunan FD dapat digunakan algoritma sebagai berikut :
T=A While (changes to T) do
For each functional dependency X → Y in F do Begin If X is in T then Add Y to T End
Contoh : 1. T = x 2. kemudian tambahkan Y ke T karena X → Y berada dalam himpunan FD. 3. tambahkan Z ke T, karena Y →Z berada dalam himpunan FD dan sekarang T = XYZ. 4. tambahkan W ke T, karena YZ → W jadi F+ untuk X : X → X, X → Y, X → Z, X → W, X →YZ, X → YW, X → ZW, X → YWZ Untuk melihat F+ dan Y, algoritma dapat diulang dengan memulai T =Y demikian seterusnya.
1.2
NORMALISASI (1..3)
Untuk menentukan apakah suatu relasi tertentu sudah dalam bentuk normal, harus diuji FD antara atribut-atribut dalam relasi. Dalam definisi relasi yang diusulkan oleh C. Beeri dan Cowokers (1978), bahwa relasi terdiri dari dua komponen yaitu : atribut-atribut dan FD antara atribut-atribut tersebut.
Sebuah relasi mempunyai bentuk :
R1 = ({X,Y,Z}, {X → Y, X → Z}) Atribut
FD
Contoh : Relasi ASSIGN { Person_ID, PROJECT, PROJECT_BUDGET, Time_Spent_By_Person_On_Project} → atribut-atribut {Person_ID, Project → Time_Spent_By_Person_On_Project, Project → Project_Budget} → FD
Functional Dependencies dapat digunakan dalam mendesain suatu basis data relasional untuk menghilangkan property-properti yang tidak diinginkan sehingga didapatkan desain yang baik yang disebut dalam bentuk normal. Terdapat sejumlah bentuk normal dimana yang dikenal (sangat popular) sebanyak 3 macam bentuk normal, yaitu : bentuk normal pertama, kedua dan ketiga.
Bentuk Normal Pertama Sebuah relasi berada dalam bentuk normal pertama jika semua domaun adalah simple Contoh : Relasi :
Person
Jack
Martha
LIVED_IN
Residence City Date_Move_In New York 030371 Boston 070780 Washington 080889 City Date_Moved_In Boston 040573 Philadelphia 070675 Chicago 080877 Gambar Relasi yang tidak normal
Relasi-relasi yang tidak/belum mempunyai domain yang simple (tidak berada dalam bentuk normal pertama) disebut relasi tidak normal (unnormalized relations). Bentuk normal dari relasi LIVED_IN sebagai berikut : Relasi
: LIVED_IN Person
City
Date_Moved_In
Jack
New York
030381
Jack
Boston
070780
Jack
Washington
080881
Martha
Boston
040583
Martha
Philadelphia
070685
Martha
Chicago
080887
Bentuk Normal Kedua : Sebuah relasi R berada dalam bentuk normal kedua jika setiap atribut dari R Functional Depencies (FD) penuh pada setiap kunci (key) relasi. Dengan kata lain ada atribut yang bergantung pada subset kunci. Contoh relasi ASSIGN.
Bentuk Normal Ketiga Suatu relasi berada dalam bentuk normal ketiga jika : 1.
relasi tersebut berada dalam bentuk normal kedua.
2.
tidak terdapat atribut-atribut bukan kunci yang saling tergantung.
Contoh : Relasi :
PROJECT
Project
Project-Budget
Department
Department Address
P1
32
Construct
20 Main
P2
40
Construct
20 Main
P3
27
Construct
20 Main
P4
17
Build
8 Fifth
FD
pada relasi PROJECT :
Project_Budget
Project
Department
Department_Address
Relasi project masih belum berada dalam bentuk normal ketiga karena ada atribut
bukan
kunci
(Department
_Address)
bergantung
pada
atribut
Department. Relasi PROJECT dapat menjadi bentuk normal ke-3 dengan memecah relasi Project dalam dua relasi yaitu : PROJECT Projects
Project_Budget
Department
P1
32
Construct
P2
40
Construct
P3
27
Construct
P4
17
Build
DEPARTMENT Department Dep. Address Construct
20 Main
Build
8 Fifth
1.3
METODOLOGI PERANCANGAN DIAGRAM E-R Definisi basis data relasional adalah kumpulan relasi-relasi yang mengandung
semua informasi yang akan disimpan dalam basis data. Tiap relasi dalam basis data disimpan dalam sebuah file tersendiri. Struktur file yang digunakan untuk menyimpan relasi cukup sederhana, karena tiap record dalam file memiliki format yang sama. Perancangan basis data merupakan salah satu bagian terpenting dalam proses pengembangan sistem. Perancangan basis data mempunyai beberapa tujuan yaitu : 1.
menghilangkan redundansi data
2.
meminimumkan jumlah relasi di dalam basis data
3.
membuat relasi berada dalam bentuk normal, sehingga dapat meminimumkan
permasalahan
berkenaan
dengan
pembaharuan dan penghapusan. Teknik perancangan yang dilakukan dapat dilihat pada gambar berikut :
penambahan,
