Normalisasi Database

Pengantar Penyempurnaan Skema: Persoalan yang Ditimbulkan oleh Redundansi

Redundansi ruang penyimpanan: beberapa data disimpan secara berulang

Update anomaly: Jika satu copy data terulang tsbdiubah, inkonsistensi data dpt terjadi kecuali kalausemua copy dari data tsb diubah dengan cara yang sama

Insertion anomaly: Mungkin dpt terjadi kesulitan utkmenyisipkan data tertentu kecuali kalau beberapa data tidak terkait lainnya juga ikut disisipkan

Deletion anomaly: Mungkin dpt terjadi kesulitan utkmenghapus data tertentu tanpa harus kehilanganbeberapa data tidak terkait lainnya

Persoalan yang Ditimbulkan olehRedundansi: Contoh

Redundansi ruang penyimpanan: nilai rating 8 yang berkorespondensi dg wages 10 diulang tiga kali

Update anomaly: Nilai wages (yg terkait dengan nilairating) dlm baris pertama dpt diubah tanpa membuatperubahan yg sama pada baris kedua dan kelima

Persoalan yang Ditimbulkan olehRedundansi: Contoh (cont’d)

Insertion anomaly: Kesulitan utk menyisipkan employee baru kecuali nilai wage untuk rating dari employee tsb sudah diketahui

Deletion anomaly: Jika semua baris yang terkait dg nilai rating tertentu dihapus (misalnya baris utk employee ‘Smethurst’ dan ‘Guldu’ dihapus), maka kita akan kehilangan informasi ketergantungan antara nilai rating dan nilai wages yang diasosiasikan dengan nilai rating tsb (yaitu rating = 5 dan wages = 7)

5

PenyebabPenyebab AnomaliAnomali

MengapaMengapa anomalianomali -- anomalianomali iniini terjaditerjadi ??

KarenaKarena menggabungkanmenggabungkan duadua tematema ((konsepkonsep entitasentitas))dalamdalam satusatu relasirelasi.. IniIni mengakibatkanmengakibatkan duplikasiduplikasi –– duplikasiduplikasisebagaisebagai akibatakibat daridari ketergantunganketergantungan antarantar atributatribut yangyangtidaktidak padapada tempatnyatempatnya..

SolusiSolusi :: NormalisasiNormalisasi

Normalisasi

Normalisasi adalah proses pembentukan struktur basis data sehingga sebagian besar ambiguity bisa dihilangkan.

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.

Normalisasi

Sebuah tabel dikatakan baik (efisien) atau normal jikamemenuhi 3 kriteria sbb:

1. Jika ada dekomposisi (penguraian) tabel, makadekomposisinya harus dijamin aman (Lossless-Join Decomposition). Artinya, setelah tabel tersebut diuraikan / didekomposisi menjadi tabel-tabel baru, tabel-tabel barutersebut bisa menghasilkan tabel semula dengan samapersis.

2. Terpeliharanya ketergantungan fungsional pada saatperubahan data (Dependency Preservation).

3. Tidak melanggar Boyce-Code Normal Form (BCNF) (-akandijelaskan kemudian-)

Normalisasi

Jika kriteria ketiga (BCNF) tidak dapat terpenuhi,maka paling tidak tabel tersebut tidak melanggarBentuk Normal tahap ketiga (3rd Normal Form /3NF).

Sistem / Teknologi Basis Data 9

LangkahLangkah –– LangkahLangkah NormalisasiNormalisasi

Contoh Tabel Universal

Tabel Universal (Universal / Star Table) sebuah tabelyang merangkum semua kelompok data yang salingberhubungan, bukan merupakan tabel yang baik.

Tabel Universal

Functional Dependency Notasi: A B

A dan B adalah atribut dari sebuah tabel. Berarti secara fungsional A menentukan B atau B tergantung pada A, jika dan hanya jika ada 2 baris data dengan nilai A yang sama, maka nilai B juga sama

• Notasi: A B atau A x BAdalah kebalikan dari notasi sebelumnya.

Functional Dependency

Contoh tabel nilai

Functional Dependency

Functional Dependency dari tabel nilai

• Nrp namaMhsKarena untuk setiap nilai nrp yang sama, maka nilai namaMhs juga sama.

• {Namakul, nrp} NiHurufKarena attribut Nihuruf tergantung pada Namakul dan nrp secara bersama-sama. Dalam arti lain untuk Namakul dan nrp yang sama, maka NiHuruf juga sama, karena Namakul dan nrp merupakan key (bersifat unik).

• NamaKul nrp• Nrp NiHuruf

Bentuk-bentuk Normal

1. Bentuk Normal Tahap Pertama (1st Normal Form / 1NF)

2. Bentuk Normal Tahap Kedua (2nd Normal Form / 2NF)

3. Bentuk Normal Tahap (3rd Normal Form / 3NF)4. Boyce-Code Normal Form (BCNF)5. Bentuk Normal Tahap (4th Normal Form / 4NF)6. Bentuk Normal Tahap (5th Normal Form / 5NF)

Bentuk Normal Tahap Pertama(1st Normal Form / 1NF)

Bentuk normal 1NF terpenuhi jika sebuah tabel tidakmemiliki atribut bernilai banyak (multivalued attribute), atribut composite atau kombinasinya dalam domain data yang sama.

Setiap atribut dalam tabel tersebut harus bernilai atomic(tidak dapat dibagi-bagi lagi)

Contoh 1Misal data mahasiswa sbb:

AtauAtau::

TabelTabel--tabeltabel didi atasatas tidaktidak memenuhimemenuhi syaratsyarat 1NF1NF

Contoh 1

Didekomposisi menjadi:• Tabel Mahasiswa

• Tabel Hobi

Contoh 2 (composite)

JadwalKuliah

Kodekul NamaKul Dosen Kelas Jadwal

Kodekul NamaKul Dosen Kelas JadwalHari JadwalJam

• Dimana nilai pada atribut jadwal berisi gabungan antara Hari dan Jam.

• Jika asumsi hari dan jam memegang peranan penting dalam sistem basis data, maka atribut Jadwal perlu dipisah sehingga menjadi JadwalHari dan JadwalJam sbb:

JadwalKuliah

Bentuk Normal Tahap Kedua(2nd Normal Form)

Bentuk normal 2NF terpenuhi dalam sebuah tabel jikatelah memenuhi bentuk 1NF, dan semua atribut selainprimary key, secara utuh memiliki Functional Dependency pada primary key

Sebuah tabel tidak memenuhi 2NF, jika ada atribut yang ketergantungannya (Functional Dependency) hanyabersifat parsial saja (hanya tergantung pada sebagian dariprimary key)

Jika terdapat atribut yang tidak memiliki ketergantunganterhadap primary key, maka atribut tersebut harusdipindah atau dihilangkan

Contoh

Tabel berikut memenuhi 1NF tapi tidak termasuk 2NF:

Mhs_nrp mhs_nama mhs_alamat mk_kode mk_nama mk_sks nihuruf

• Tidak memenuhi 2NF, karena {Mhs_nrp, mk_kode} yang dianggap sebagai primary key sedangkan:{Mhs_nrp, mk_kode} mhs_nama{Mhs_nrp, mk_kode} mhs_alamat{Mhs_nrp, mk_kode} mk_nama{Mhs_nrp, mk_kode} mk_sks{Mhs_nrp, mk_kode} nihuruf

• Tabel di atas perlu didekomposisi menjadi beberapa tabel yang memenuhi syarat 2NF

Contoh

Functional dependencynya sbb:

{Mhs_nrp, mk_kode} nihuruf (fd1)Mhs_nrp {mhs_nama, mhs_alamat} (fd2)Mk_kode {mk_nama, mk_sks} (fd3)

fd1 (mhs_nrp, mk_kode, nihuruf) Tabel Nilaifd2 (Mhs_nrp, mhs_nama, mhs_alamat) Tabel Mahasiswafd3 (mk_kode, mk_nama, mk_sks) Tabel MataKuliah

Bentuk Normal Tahap Ketiga (3rd Normal Form /3NF)

Bentuk normal 3NF terpenuhi jika telah memenuhi bentuk 2NF, dan jika tidak ada atribut non primary key yang memiliki ketergantungan terhadap atribut non primary key yang lainnya.

Untuk setiap Functional Dependency dengan notasi X A, maka:

•• X X harusharus menjadimenjadi superkeysuperkey padapada tabeltabel tsbtsb..•• AtauAtau A A merupakanmerupakan bagianbagian daridari primary key primary key padapada tabeltabeltsbtsb..

Contoh

Tabel berikut memenuhi 2NF, tapi tidak memenuhi 3NF:

Nrp Nama Alm_Jalan Alm_Kota Alm_Provinsi Alm_Kodepos

Mahasiswa

karenakarena masihmasih terdapatterdapat atributatribut non primary key non primary key ((yakniyakni alm_kotaalm_kota dandanalm_Provinsialm_Provinsi) yang ) yang memilikimemiliki ketergantunganketergantungan terhadapterhadap atributatribut non non primary key primary key yang lain (yang lain (yakniyakni alm_kodeposalm_kodepos):):

alm_kodepos {alm_Provinsi, alm_kota}

SehinggaSehingga tabeltabel tersebuttersebut perluperlu didekomposisididekomposisi menjadimenjadi::Mahasiswa (Nrp, nama, alm_jalan, alm_kodepos)Kodepos (alm_kodepos, alm_provinsi, alm_kota)

Boyce-Code Normal Form (BCNF)

Bentuk BCNF terpenuhi dalam sebuah tabel, jika untuksetiap functional dependency terhadap setiap atributatau gabungan atribut dalam bentuk: X Y maka X adalah super key

tabel tersebut harus di-dekomposisi berdasarkanfunctional dependency yang ada, sehingga X menjadisuper key dari tabel-tabel hasil dekomposisi

Setiap tabel dalam BCNF merupakan 3NF. Akan tetapisetiap 3NF belum tentu termasuk BCNF . Perbedaannya, untuk functional dependency X A, BCNF tidakmembolehkan A sebagai bagian dari primary key.

Bentuk Normal Tahap Keempat (4th Normal Form /4NF)

Bentuk normal 4NF terpenuhi dalam sebuah tabel jikatelah memenuhi bentuk BCNF, dan tabel tersebut tidakboleh memiliki lebih dari sebuah multivalued atribute

Untuk setiap multivalued dependencies (MVD) jugaharus merupakan functional dependencies

Contoh

Misal, tabel berikut tidak memenuhi 4NF:

SetiapSetiap employeeemployee dapatdapat bekerjabekerja didi lebihlebih daridari satusatu projectproject dandandapatdapat memilikimemiliki lebihlebih daridari satusatu skillskill.. UntukUntuk kasuskasus sepertiseperti iniinitabeltabel tersebuttersebut harusharus didi--dekomposisidekomposisi menjadimenjadi::

(Employee, Project)(Employee, Skill)

Bentuk Normal Tahap Keempat(5th Normal Form /5NF)

Bentuk normal 5NF terpenuhi jika tidak dapat memiliki sebuah lossless decomposition menjadi tabel-tabel yg 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

Latihan Normalisasi

Soal Latihan (1)NoOrder TglOrder Item1 Item2 Item3 Total

TR001 10/01/2006 P1 P2 P3 500.000

TR002 15/02/2006 P3 P5 300.000

TR003 18/03/2006 P1 P2 200.000

Bagaimana bentuk normalisasinya?

Pembahasan(1)

Bentuk Normal Pertama

NoOrder TglOrder Item TotalTR001 10/01/2006 P1 500.000TR001 10/01/2006 P2 500.000TR001 10/01/2006 P3 500.000TR002 15/02/2006 P3 300.000TR002 15/02/2006 P5 300.000TR003 18/03/2006 P1 200.000TR003 18/03/2006 P2 200.000

Pembahasan(1)

Bentuk Normal Kedua

NoOrder TglOrder Total

TR001 10/01/2006 500.000

TR002 15/02/2006 300.000

TR003 18/03/2006 200.000

NoOrder ItemTR001 P1TR001 P2TR001 P3TR002 P3TR002 P5TR003 P1TR003 P2

Relasi: Order1 Relasi: Order2

Soal Latihan(2)KodeProyek NamaPegawai Bagian

P001 Adi EDP

P002 Bima HRD

P002 Adi EDP

P003 Bima HRD

P003 Candra Produksi

• Apakah sudah memenuhi bentuk normal pertama• Bagaimana bentuk normalisasi tabel tersebut?

Pembahasan(2)

KodeProyek NamaPegawaiP001 AdiP002 BimaP002 AdiP003 BimaP003 Candra

NamaPegawai Bagian

Adi EDPBima HRDCandra Produksi

• Tabel soal latihan 2 sudah memenuhi normalisasi pertama• Bentuk normalisasi kedua dari tabel tersebut adalah

Relasi: Proyek1 Relasi: Proyek2

Pembahasan(2)

KodeProyek NamaProyek KodePegawai

P001 XXX N001P002 YYY N001P002 YYY N002P003 ZZZ N002P003 ZZZ N003

KodePegawai NamaPegawai

KodeBagian

N001 Adi B01

N002 Bima B02

N003 Candra B03

KodeBagian NamaBagianB01 EDPB02 HRDB03 Produksi

• Bentuk normalisasi ketiga dari tabel tersebut adalah

Relasi: Proyek1 Relasi: Proyek2

Relasi: Proyek3

Soal Latihan(3)NRP Nama MataKuliah NIP Dosen

5103100101 Ali Basis Data 320001123 Ir.X

5103100102 Sita Basis Data 320001123 Ir.X

5103100102 Sita RPL 320011133 Ir.Y

5103100103 Adi AI 320021010 Ir.Z

• Apakah sudah memenuhi bentuk normal pertama• Bagaimana bentuk normalisasi tabel tersebut?

Pembahasan (3)

NRP Nama

5103100101 Ali

5103100102 Sita

5103100103 Adi

NRP MataKuliah

5103100101 Basis data

5103100101 Basis data

5103100101 RPL

5103100102 AINRP NIP Dosen

5103100101 320001123 Ir. X

5103100102 320001123 Ir. Y

5103100102 320011133 Ir. Y

5103100103 320021010 Ir. Z

• Tabel soal latihan 3 sudah memenuhi normalisasi pertama• Bentuk normalisasi kedua dari tabel tersebut adalah

Relasi: Mahasiswa1 Relasi: Mahasiswa2

Relasi: Mahasiswa3

Pembahasan (3)

NRP Nama KodeMatkul

5103100101 Ali MT01

5103100102 Sita MT02

5103100102 Sita MT02

5103100103 Adi MT03

KodeMatkul MataKuliah

MT01 Basis data

MT02 RPL

Mt03 AI

NIP Dosen

320001123 Ir. X

320011133 Ir. Y

320021010 Ir. Z

• Bentuk normalisasi ketiga dari tabel tersebut adalah

Relasi: Mahasiswa1 Relasi: Mahasiswa2

Relasi: Mahasiswa3