PROSES NORMALISASI

BENTUK NORMAL PERTAMA

Kadangkala, selama proses pembuatan database kita mungkin perlu melakukan transformasi ke dalam relasi terhadap tabel yang diketahui beberapa entrinya (perpotongan baris dan kolom) mungkin memiliki lebih dari satu nilai Untuk mengacu ke tipe tabel ini dan bagaimana tabel – tabel ini akan berhubungan dengan relasi kita memerlukan beberapa terminologi baru. Entri- entri tabel yang memiliki lebih dari satu nilai dinamakan multivalue. Tabel dengan entri multivalue dinamakan tabel unnormalized.

Di dalam tabel unnormalized, kita akan menamakan repeating group  atau kelompok pengulangan untuk sebuah atribut atau kelompok atribut yang mungkin memliki entri multivalue untuk peristiwa tunggal dari identifikasi tabel. Bentuk terakhir ini mengacu ke atribut yang memperbolehkan kita untuk membedakan baris – baris dari tabel unnormalized.

Untuk dapat mempresentasikan tabel ini sebagai sebuah relasi dan untuk mengimplementasikannya ke dalam RDBMS, kita perlu menormalisasikan tabelnya. Tujuan dari menormalkan tabel adalah untuk membuang grup pengulangan dan memastikan bahwa seluruh entri tabel hasil memiliki maksimal satu nilai tunggal.

ANOMALI DATA DALAM RELASI 1NF 

Redundansi dalam tabel 1NF menuntuk kita pada beragam anomali data. Anomali data kita artikan sebagai efek samping yang dialami data dari hasil beberapa operasi relasional. Anomali data dibagi menjadi tiga kategori umum : anomali insertion,deletion,dan update. Ketiganya masing – masing dinamai sesuai operasi relasional INSERT, DELETE , dan UPDATE karena dari setiap operasi – operasi ini dapa menyebabkan relasi mengalami anomali.Pada kenyataanya , hanya ada dua tipe anomali : anomali update dan insertiom/deletion. Kategori terakhir dapat dianggap hanya sebagai satu kategori karena relasi yang mengalami anomali deletion juga akan mengalami anomali insertion. Yang satunya tidak dapat berlangsung tanpa yang lainnya. Namun, untuk keperluan penjelasan, kita akan memperhatikan anomali data ini dengan membaginya menjadi tiga kategori. 

DEPENDENSI PARSIAL

Diketahui relasi r(R), himpunan atribut X dan Y (X,Y Є R), dan X -> Y, kita akan mengatakan bahwa atribut Y adalah sepenuhnya dependen pada atribut X jika dan hanya jika tidak ada subhimpunan W dari X, yang cocok sedemikian sehingga W -> Y. Jika terdapat subhimpunan W dari X yang cocok sehingga W -> Y, maka atribut Y dikatakan dependen secara parsial pada atribut X.

Seperti yang ditunjukkan sebelumnya, PK dari relasi ini dibentuk oleh atribut – atribut Proj-ID dan Emp-ID. Hal ini mengimplikasikan bahwa Proj-ID,Emp-ID secara fungsional menentukan setiap atribut individu atau setiap kombinasi dari atribut relasi. Namun kita hanya membutuhkan atribut Emp-ID untuk menetukan atribut – atribut berikut ini secara fungsional : Emp-Name,Emp-Hrly-Rate, dan Total-Hrs. Dengan kata lain, atribut – atribut Emp-Name, Emp-Dpt, dan Emp-Hrly-Rate adalah dependen secara parsial pada key.

BENTUK NORMAL KEDUA

Sebuah relasi r(R) berada dalam bentuk normal kedua atau second normal form (2NF) jika dan hanya jika kedua kondisi berikut ini dipenuhi secara simultan :

 

  (1) r(R) telah ada dalam 1NF.

  (2) Tidak ada atribut nonprima yang dependen secara parsial di setiap key            atau, secara ekuivalen, setiap atribut nonprima di dalam R adalah               dependen secara penuh terhadap setiap key (termasuk candidate key).

Perhatikan bahwa dalam upaya mencari atribut nonprima R, kita perlu mengidentifikasi seluruh atribut prima dari R. Sebagai konsekuensinya, kita perlu untuk mengidentifikasi seluruh kemungkina key relasi yang pertama. Atribut – atribut nonprima kemudian dihitung sebagai R – P dengan P adalah himpunan seluruh atribut prima dan R adalah skema relasi R.

ANOMALI – ANOMALI DATA DI RELASI 2NF

Relasi – relasi di dalam 2NF masih terpengaruh anomali data. Untuk keperluan penjelasan, kita asumsikan bahwa department tempat employee bekerja secara fungsional menetukan tarif per jam yang dibebankan oleh empolyee tersebut.Jelasnya, Emp-Dpt -> Emp-Hrly-Rate. Kenyataan ini tidak diperhatikan dalam penjelasan bentuk normal sebelumnya tetapi ini bukanlah situasi yang tidak realistis.Anomali Insertion terjadi di dalam relasi EMPLOYEE. Sebagai contoh, bayangkanlah situasi bahwa ketika kita ingin mengatur lebih lanjut tarif yang akan dibebankan oleh employee di suatu department baru. Perhatikan bahwa tarif yang department bebankan tidak tergantung pada apakah ada employee atau tidak. Relasi EMPLOYEE juga peka terhadap anomali deletion. Jenis anomali ini terjadi pada saat kita menghapus tupel milik seorang employee yang merupakan satu – satunya employee yang tersisa di suatu department. Dala kasus ini, kita juga akan kehilangan informasi mengenai tarif yang department bebankan. Anomali update juga akan terjadi di dalam relasi EMPLOYEE karena di sana mungkin terdapat beberapa employee dari department sama yang bekerja dalam project berbeda. Jika tarif department berubah, kita perlu meyakinkan bahwa tarif yang berhubungan dengannya telah diubah untuk seluruh employee yang bekerja di department tersebut. Jika sebaliknya, maka database mungkin berakhir dalam kondisi inkonsisten.

DEPENDENSI TRANSITIF

Asumsikan bahwa A,B, dan C adalah himpunan atribut dari relasi r(R). Asumsi selanjutnya bahwa dependensi fungsional berikut inin dipengaruhi secara simultan: A -> B, B -> A , B -> C, C -> A dan A -> C. Amatilah bahwa C -> B tidak diperlukan maupun dilarang. Jika seluruh kondisi ini bernilai benar, maka kita akan mengatakan bahwa atribut C adalah dependen secara transitif terhadap atribut A.

BENTUK NORMAL KETIGA

Suatu relasi r(R) berada dalam Bentuk Normal Ketiga atau Third Normal Form (3NF) jika dan hanya jika kondisi – kondisi berikut ini dipenhi secara stimultan:

  (1)  r(R) telah ada dalam 2NF.

    (2)  Tidak ada atribut nonprima yang dependen secara transitif   pada key.

Cara lain untuk mengekspresikan kondisi – kondisi Bentuk Normal Ketiga ini sebagai berikut :

    (1)   r(R) telah ada di dalam 2NF.

    (2)   Tidak ada atribut nonprima yang secara fungsional menentukan   atribut nonprima lainnya.

Karena kedua himpunan kondisi ini ekuivalen, kita akan menggunakan suatu satu himpunan yang lebih sesuai untuk memecahkan problem tertentu yang dihadapi.

ANOMALI – ANOMALI DATA DI RELASI 3NF

Bentuk Normal Ketiga membantu kita untuk membersihkan anomali data yang ditimbulkan baik oleh dependensi transitif dalam PK maupun oleh dependensi atribut nonprima dalam atribut nonprima lainnya. Namun, relasi di dalam 3NF masih peka terhadap anomali data, khususnya ketika relasi – relasi memiliki dua candidate key yang saling tumpang-tindih atau ketika suatu atribut nonprima secara fungsional menentukan atribut prima.

BENTUK NORMAL BOYCE-CODD

Untuk mengeleminasi anomali – anomali di dalam relasi 3NF ,kita perlu membawa proses normalisasi ini ke tingkat yang lebih tinggi, yaitu Bentuk Normal Boyce-Codd (Boyce-Codd Normal Form).

Sebuah relasi r(R) berada dalam Boyce-Codd Normal Form (BCNF) jika dan hanya jika kondisi – kondisi berikut dipenuhi secara simultan :

  (1)   Relasi tersebut berada dalam 1NF.

  (2)   Untuk setiap dependensi fungsional berbentuk X -> A , kita dapat   mendapati bahwa A Є X atau X adalah superkey dari r. Dengan kata lain,   setiap dependensi fungsional adalah dependensi trivial atau dalam kasus   bahwa dependensi fungsionalnya bukan trivial maka X harus merupakan   superkey.

Perhatikanlah bahwa definisi BCNF tidak memunculkan referensi terhadap konsep dependensi penuh atau parsial. Namun, dari definisi ini kita dapat memunculkan keutamaan berikut ini mengenai atribut prima dan nonprima dari skema relasional :

     

•Seluruh atribut nonprima harus dependen secara penuh di dalam setiap key.

•Seluruh atribut prima harus dependen secara penuh di dalam seluruh key yang bukan merupakan bagian darinya.

DEKOMPOSISI LOSSLESS ATAU LOSSY

Sejauh ini kita telah melakukan dekomposisi terhadap suatu relasi menggunakan prosedur umum atau metode ad-hoc. Namun, sewaktu – waktu relasi mengalami dekomposisi maka kita perlu memastikan bahwa data di dalam rekasi aslinya telah direpresentasikan secaa benar oleh data di dalam relasi yang merupakan hasil dari dekomposisi; jelasnya, kita perlu meyakinkan bahwa kita dapat memulihkan kembali relasi aslinya dari relasi baru yang telah menggantikannya. Secara umum, relasi asli dapat dipulihkan kembali melalui pembentukan join natural di relasi baru. Jika kita dapat memulihkan kembali relasi aslinya. Kita katakan bahwa dekomposisinya adalah lossless terhadap D atau bahwa relasi  mengalami dekomposisi join lossless terhadap D, dengan D adalah himpunan FD yang dipenuhi oleh relasi asli. Jika relasi tidak dapat dipulihkan kembali, kita katakan bahwa dekomposisinya lossy. Kita dapat memformalkan konsep ini sebagai berikut:

  Asumsikan bahwa relasi r(R) telah digantikan oleh kumpulan atau relasi r1(R1), r2(R2),...,rn(Rn) sesemikian hingga =  R1 U  R2 U .... U Rn dan D adalah himpunan dari dependensi yang dipenuhi oleh r. Kita katakan bahwa dekomposisi adalah lossless terhadap D atau merupakan dekomposisi terhadap join-lossless terhadap D jika dan hanya jika r = πR1(r) join πR2(r) join .... join πRn(r) . Jelasnya, relasi r adalah lossless jika merupakan join natural dari projeksinya terhadap Ri . Jika relasi tersebut tidak dapt dipulihkan kembali dari projeksi natural maka dekomposisinya dikatakan menjadi lossy terhadap D.

A.MEGUJI JOIN LOSSLESS

Baaimana telah ditunjukka sebelumnya, dekomposisi join-lossless dibutuhkan untuk meyakinkan bahwa relasi dapat dipulihkan kembali. Menentukan apakah dekomposisi adalh lossless atau lossy terhadap suatu himpunan FD adalah suatu prosedur mudah yang cukup baik dilakukan jika kita menggunakan algoritma jon lossless.

  B.  ALGORITMA JOIN LOSSLESS

Algoritma ini memiliki dua input . Input pertama adalah himpunan relasi r1(R1), r2(R2),...,rn(Rk) yang mengantikan relasi r(A1,A2,A3,....,An) dengan R = {A1,A2,A3,....,An} R1∪R2 ∪ … ∪Rk . Input kedua terhadap algoritma adalah himpunan F dari dependensi fungsional yang dipenuhi oleh r. Output dari algoritma ini adah keputusan yang menetapkan apakah dekomposisinya merupakan lossless atau lossy.

MEMELIHARA DEPENDENSI FUNGSIONAL

Sebagaimana yang telah ditunjukkan di subbab sebelumnya, agar relasi r dapat dipulihkan kembalu dari projeksinya, maka sekomposisinya haruslah lossless. Selain itu, dekomposisi tersebut harus memenuhi sifat yang lain yang dikenal sebagai pemeliharaan dependensi (dependensi preservation). Apa yang disyaratkan sifat ini adalah bahwa dekomposisi memenuhi seluruh FD yang dipenuhi oleh relasi asli. Alasan dibutuhkannya hal ini adalah bahwa himpunan dependensi fungsional dipenuhi oleh relasi mendefinisikan batasan integritas yang diperlukan oleh relasi. Setiap dekomposisi yang tidak memelihara dependensinya dari relasi asli akan menimbulkan beban yang tidak perlu di dalam RDBMS. Pada kenyataannya, updaate apa pun yang dilakukan terhadap setiap relasi dekomposisi akan meminta join seluruh relasi ini untuk memeriksa apakah batasan tidak dilanggar. Ini sebenarnya adalah operasi yang menyita waktu sehingga mengurangi efisien sistem. 

A.PROJEKSI HIMPUNAN DEPENDENSI KE DALAM HIMPUNAN ATRIBUT

Untuk memformalkan konsep preservasi dependensi dan untuk mendefinisikan algoritma yang memungkinkan kita untuk menguji preservasi dependensi, maka beberapa terminologi tambahan diperlukan. Asumsikan bahwa relasi r(R) telah didekomposisi menjadi serangkaian relasi ρ = (R1,R2,...,Rk) dan bahwa F adalah himpunan FD yang dipenuhi oleh r. Kita mendefinisikan projeksi F ke dalam himpunan atribut Z , dinotasikan dengan π(z)F , sebagai berikut :

π(z)F = { X -> Y ∈ F+/XY ∈ Z } dengan simbol “/” dibaca “sedemikian hingga”

 penting juga untuk mengamati bahwa definisi ini tidak mengharuskan X -> Y berada di dalam F tetapi di dalam F+ (dengan F+ adalah penutup F). Perhatikan pula bahwa baik X maupun Y bisa merupakan atribut campuran yang unionnya harus berupa subhimpunan dari atribut Z. FD dari π(z)F ini dikatakan telah dipenuhi oleh atribut Z.

Untuk menghitung projeksi π(z)F perhatikanlah subhimpunan X yang cocok di atribut – atribut Z ( X ∈ Z dan X ≠ Z ) yang muncul sebagai determinan dari dependensi fungsional atas merupakan bagian dari determinan dependensi fungsional F dan lakukanlah yang berikut ini :

  

  (1)   Hitunglah X+.

  (2)   Untuk setiap himpunan atribut Y dari X+ yang memenuhi secara simultan   kondisi – kondisi di bawah ini :

    a.   Y ∁ Z

    b.   Y ∁ X+

    c.   Y ∁ X ( Persyaratan ini tidak termasuk pengertian dependensi   trivial. Dependensi trivial bagaimanapun juga adalah benar   terhadap aksioma transitivitas.)

Masukkan X -> Y sebagai salah satu FD dari π(z)F. Himpunan FD di dalam π(z)F kita katakan telah terpenuhi oleh atribut Z.

B. MENGUJI PRESERVASI DEPENDENSI

Diketahui sebuah relasi r(R), sebuah dekomposisi ρ = (R1,R2,...,Rk) dari suatu relasi dan sebuah himpunan F dari FD yang dipenuhi oleh r(R), kita katakan bahwa dekomposisi ρ melindungi dependensi fungsional dari r jika dan hanya jika kondisi berikut ini dipenuhi secara simultan :

  (1)  G    = ∪π Ri(F)

  (2)   G+   = F+

Dengan kata lain, dekomposisi ρ melindungi himpunan dependensi F jika

union dari seluruh dependensi dalam ∪π Ri(F) secara logika

mengimplikasikan seluruh dependensi di F.Definisi ini juga menyediakan prosedur untuk menguji apakah ada atau tidak dekomposisi dari relasi yang diketahui yang melindungi himpunan F dari dependensi fungsional. Cobalah mempergunakan F+ ke dalam seluruh union Ri di himpunan – himpunan ini dan menguji apakah himpunan ini ekuivalen terhadap F.Menghitung F+, seperti yang ditunjukkan sebelumnya , adalah tugas yang sangat membosankan dan menghabiskan waktu. Untungnya, ada sebuah algoritma lebih pendek yang tidak memerlukan komputasi F+.

KESIMPULAN

Sejauh ini kita telah memahami prosedur sistematis untuk untuk menguji join-lossless dan properti preservasi dependensi dari suatu dekomposisi. Namun, pembaca perlu berhati – hati bahwa kedua properti tersebut jangan diimplikasikan satu sama lain. Jelasnya, dimungkinkan untuk melakukan dekomposisi lossless yang tidak melindungi dekomposisi fungsional dari relasi asli maupun sebaliknya.