BASIS DATA JURUSAN TEKNIK INFORMATIKA - ITS
Dibuat oleh: Tim Pengajar Basis Data 8 t h
w e e k
Normalisasi
BCNF, 4NF, 5NF
Tahap
Normalisasi dimulai dari tahap paling ringan (1NF) hingga paling ketat (5NF) Biasanya hanya sampai pada tingkat 3NF atau BCNF karena sudah cukup memadai untuk menghasilkan tabel-tabel yang berkualitas baik. Urutan: 1NF, 2NF, 3NF, BCNF, 4NF, 5NF
Sebuah tabel dikatakan baik (efisien) atau normal jika memenuhi 3 kriteria sbb: 1.
2. 3.
Jika ada dekomposisi (penguraian) tabel, maka dekomposisinya harus dijamin aman (Lossless-Join Decomposition). Artinya, setelah tabel tersebut diuraikan / didekomposisi menjadi tabel-tabel baru, tabel-tabel baru tersebut bisa menghasilkan tabel semula dengan sama persis. Terpeliharanya ketergantungan fungsional pada saat perubahan data (Dependency Preservation). Tidak melanggar Boyce-Codd Normal Form (BCNF) (-akan dijelaskan kemudian-)
Jika kriteria ketiga (BCNF) tidak dapat terpenuhi, maka paling tidak tabel tersebut tidak melanggar Bentuk Normal tahap ketiga (3rd Normal Form / 3NF).
Bentuk BCNF terpenuhi dalam sebuah tabel, jika untuk setiap functional dependency terhadap setiap atribut atau gabungan atribut dalam bentuk: X Y maka X adalah super key tabel tersebut harus di-dekomposisi berdasarkan functional dependency yang ada, sehingga X menjadi super key dari tabel-tabel hasil dekomposisi Setiap tabel dalam BCNF merupakan 3NF. Akan tetapi setiap 3NF belum tentu termasuk BCNF . BCNF merupakan perbaikan bagi 3NF yang anomali.
BASIS DATA TEKNIK INFORMATIKA - ITS
7
BCNF
merupakan kelanjutan dari 3 NF BCNF menangani kasus khusus berupa relasi dengan multiple candidate key. BCNF terpenuhi jika tidak ada functional dependency diantara candidate key.
Boyce Codd Normal Form (BCNF) Suatu relasi disebut memenuhi BCNF jika dan hanya jika setiap determinan yang ada pada relasi tersebut adalah candidate key. Definisi yang lain : Suatu relasi disebut memenuhi BCNF jika untuk setiap FD : X A atribut X adalah superkey. Untuk normalisasi ke bentuk BCNF, maka tabel 3NF didekomposisi menjadi beberapa tabel yang masing-masing memenuhi BCNF. Tujuan membentuk BCNF : :: semantik multiple candidate key menjadi lebih eksplisit (FD hanya pada candidate key). :: menghindari update anomali yang masih mungkin terjadi pada 3NF. Dari definisi 3NF dan BCNF, maka apabila suatu relasi memenuhi BCNF pasti memenuhi 3NF, tetapi belum tentu sebaliknya.
9
Boyce Codd Normal Form (BCNF) Contoh : Diketahui tabel R=(A,B,C) dengan FD : A B dan B C maka R bukan BCNF, sebab : A superkey ? AB (diketahui) AB dan BC maka AC (transitif) AA (refleksif) Sehingga A(A,B,C) atau AR. Jadi A superkey. B superkey ? BC (diketahui) BB (refleksif) Tapi BA. Sehingga BA,B,C atau B bukan superkey. Agar R memenuhi BCNF maka didekomposisi menjadi : R1=(A,B) ; FD : A B dan R2=(B,C) ; FD : B C. sehingga R1 dan R2 masing-masing memenuhi BCNF. Sebab A dan B dua-duanya sekarang menjadi superkey.
10
Boyce Codd Normal Form (BCNF) Contoh : Diketahui tabel R=(A,B,C) dengan FD : AB C dan C B. Apakah : 3NF ? BCNF ? R memenuhi 3NF karena : ABC ; maka AB ABC, atau A R. Jadi AB superkey dari R CB ; maka AC AB, atau AC ABC dan AC R. Jadi AC juga superkey (sekaligus juga candidate key) dari R Karena AB superkey dan C subset candidate key maka R memenuhi 3NF R bukan BCNF karena : AB superkey tetapi C bukan superkey.
11
Boyce Codd Normal Form (BCNF) Books
Students sid
name
age
bid
title
year
53666
Jones
18
B001
MySQL
2002
53668
Smith
18
B002
Algorithm
2003
53669
Melissa
17
B003
Visual Foxpro 6.0
2003
53670
Hilden
19
B004
Visual basic 6.0
2005
Students=(sid, name, age) FD : sid name, age • BCNF, sebab sid superkey Pinjam idpinjam
sid
bid
date
P-01
53666
B002
10/11/2005
P-02
53668
B001
10/11/2005
P-03
53668
B004
11/12/2005
P-04
53670
B002
14/11/2005
Books=(bid, title, year) FD : bid title, year • BCNF, sebab bid superkey Pinjam=(idpinjam, sid, bid, date) FD : idpinjam bid, date • Bukan BCNF, sebab idpinjam bukan superkey idpinjam sid
12
Boyce Codd Normal Form (BCNF) Pinjam idpinjam
sid
bid
date
P-01
53666
B002
10/11/2005
P-02
53668
B001
10/11/2005
P-03
53668
B004
11/12/2005
P-04
53670
B002
14/11/2005
Didekomposisi menjadi : Pinjam1 Pinjam2 idpinjam
sid
idpinjam
bid
date
P-01
53666
P-01
B002
10/11/2005
P-02
53668
P-02
B001
10/11/2005
P-03
53668
P-03
B004
11/12/2005
P-04
53670
P-04
B002
14/11/2005
FD trivial BCNF
idpinjam bid, date idpinjam superkey BCNF 13
Kedua kandidat keynya adalah {SupplierID,ProductID} dan {SupplierName,ProductID} Functional dependensinya Functional dependensi {SupplierID SupplierName} melanggar BCNF
Pelanggaran terhadap BCNF sangat mudah dihindari jika kita memperhatikan logika relasinya.
Siswa
Kursus
Tutor
Anwar
Bahasa Perancis
Pierre
Anwar
Bahasa Inggris
Richard
Budi
Bahasa Perancis
Pierre
Cecep
Bahasa Inggris
Suzanne
Tabel tersebut tidak melanggar 3NF Seorang siswa dapat mengambil sejumlah kursus Tutor hanya mengajar pada sebuah kursus, satu kursus bisa diajar oleh banyak tutor Kunci kandidat:
Siswa + Kursus Kursus + Tutor
Solusi: dekomposisi tabel BASIS DATA TEKNIK INFORMATIKA - ITS
SISWA TUTOR KURSUS Hubungan ketergantungan Jika baris Cecep dihapus, Informasi suzanne sebagai tutor bahasa inggris akan hilang
16
Siswa
Tutor
Anwar
Pierre
Anwar
Richard
Budi
Pierre
Cecep
Suzanne
Tutor
Kursus
Pierre
Bahasa Perancis
Richard
Bahasa Inggris
Pierre
Bahasa Perancis
Suzanne
Bahasa Inggris
Solusi: dekomposisi tabel BASIS DATA TEKNIK INFORMATIKA - ITS
17
4 NF terpenuhi jika: Telah memenuhi bentuk BCNF “Independent repeating groups” seharusnya tidak dijadikan dalam satu relasi.
Contoh: let's assume that the own-brand products sold by Northwind Traders come in multiple package sizes, that they are sourced from multiple suppliers, and that all suppliers provide all pack sizes
Independent repeating groups
Penyelesaian: 1. Mengeliminasi nonscalar packsize attribute non scalar
scalar
Memenuhi BCNF karena semua adalah “key”, tetapi terjadi problem dengan redundancy.
Solusinya dengan menggunakan konsep: Multivalued dependency pairs 4 NF Contoh multivalued dependency: {ProductName} {PackSize}|{SupplierName} dibaca “Product multidetermines PackSize and Supplier” Secara informal, 4 NF mengatakan bahwa Fourth normal form states, informally, that multivalued dependencies must be divided into separate relations
4 NF Cont.
4NF terpenuhi jika Telah memenuhi bentuk BCNF, Semua multivalued dependencies juga functional
dependencies terhadap candidate keys .
Misal, tabel berikut tidak memenuhi 4NF: Nama Pegawai
Proyek
Skill
Jim
11, 6
Komunikasi, pemrogram mahir, negosiasi
Mary
5, 11
Analisis, Desain
Setiap pegawai dapat bekerja di lebih dari satu proyek dan dapat memiliki lebih dari satu skill. Untuk kasus seperti ini tabel tersebut harus di-dekomposisi menjadi: (Nama Pegawai, Proyek) (Nama Pegawai, Skill)
BASIS DATA TEKNIK INFORMATIKA - ITS
23
Suatu
tabel dikatakan tidak memenuhi 5NF jika ia atributnya saling bergantung dengan atribut lain Bentuk normal 5NF terpenuhi jika data yang ada padanya tidak dapat didekomposisi lagi menjadi tabel yang lebih kecil Jika 4 bentuk normal sebelumnya dibentuk berdasarkan functional dependency, 5NF dibentuk berdasarkan konsep join dependence. Yakni apabila sebuah tabel telah di-dekomposisi menjadi tabel-tabel lebih kecil, harus bisa digabungkan lagi (join) untuk membentuk tabel semula BASIS DATA TEKNIK INFORMATIKA - ITS
24
Dealer
Distributor
Kendaraan
PT Sumber Jaya
Nissan
Truk Nissan
PT Sumber Jaya
Toyota
Toyota Kijang
PT Sumber Jaya
Toyota
Truk Dyna
PT Asterindo
Nissan
Sedan Nissan
•Pecah menjadi 3 tabel: •Deal_dist(Dealer, Distributor) •Dist_kend(Distributor,Kendaraan) •Deal_kend(Dealer, kendaraan) •Jika digabung menjadi satu akan kembali menjadi tabel diatas
BASIS DATA TEKNIK INFORMATIKA - ITS
Tidak memenuhi 5NF
memenuhi 5NF
25
1.
2.
Konsep & Tuntunan Praktis Basis Data, Abdul Kadir, penerbit Andi Yogyakarta Rebecca M. Riordan. 2005. Designing Effective Database System. Addison Wesley Proffesional Chapter 2.
BASIS DATA TEKNIK INFORMATIKA - ITS
26
