Modul Basis Data / Database
Download Modul Basis Data Bab 12 - Ketergantungan Fungsional Dalam Normalisasi
Bab 12 - Ketergantungan Fungsional Dalam Normalisasi
Abstract
"Modul ini mempelajari ketergantungan fungsional dalam normalisasi & bentuk normal 1, 2 dan 3."
Kompetensi
"Mahasiswa mampu memahami konsep dari ketergantungan fungsional dengan mengidentifikasi jenis normalisasi serta mampu memahami aturan pembentukan bentuk normal 1, 2 dan 3 dengan
melakukan proses normalisasi."
Tujuan
Mengupayakan untuk memperoleh skema relasi yang ”baik’ yaitu untuk mengukur secara formal
mengapa satu set pengelompokan attribute menjadi sejumlah skema relasi adalah lebih baik dari yang
lain.
Petunjuk Informal Dalam Desain Skema
Relasi
Empat ”ukuran informal” mengenai kualitas desain skema relasi :
- Semantik dari attributes
- Reduksi nilai-nilai yang redundan (rangkap) dalam tuples
- Reduksi nilai-nilai null dalam tuples (record)
- Tidak mempunyai tuples yang aneh (spurious tuples)
Semantik dari Attribute
Berkaitan dengan asumsi mengenai arti (semantic) tertentu yang diasosiakan terhadap sejumlah
attribute yang membentuk suatu skema relasional.
Semantik (arti) menjelaskan bagaimana mengiterprestasikan nilai-nilai attribute yang disimpan
dalam suatu tuples dari suatu relasi (bagaimana nilai-nilai attribute dala suatu tuples berkaitan
dengan yang lain).
PETUNJUK 1:
Desain suatu skema relasional sedemikian rupa sehingga semantik yang dikandungnya mudah
untuk untuk dijelaskan.
Jangan mengkombinasikan attribute-attribute dari sejumlah entity type dan relationship types
menjadi satu relasi tunggal.
Secara intuitif, jika suatu skema berkorespondensi dengan satu entity type atau satu relatioship
type saja, maka arti yang dikandungnya akan cenderung menjadi lebih jelas.
Skema-skema relasi dalam basis data COMPANY yang diberikan dalam contoh-contoh kuliah
sebelumnya, merupakan skema relasi yang memenuhi petunjuk-1 di atas.
Dibawah ini diberikan contoh penurunan skema relasional yang menyalahi petunjuk-1 di atas :
a) EMP_DEPT (EName, SSN , BDate, DNumber, DName, DMgrSSN)
---- mengkombinasikan relasi-2 EMPLOYEE dan DEPARTMENT
b) EMP_PROJ (SSN, PNumber, Hours, EName, PName, PLocation)
---- mengkombinasikan relasi-2 WORKS_ON dan PROJECT
Informasi yang Redundan dan Update
Anomalies
Salah satu tujuan dari desain skema adalah untuk meminimumkan pemakaian storage yang
dipakai oleh base relations (files).
Pengelompokan sejumlah attribute menjadi skema-2 relasi yang baik mempunyai dampak yang
berarti dalam mengurangi pemakaian storage.
EMP_DEPT (EName, SSN, Bdate. Dnumber, Dname, DMgrSSN)
Yang merupakan hasil NATURAL JOIN dari sebagian attribute EMPLOYEE dan DEPARTMENT, dan relasi :
EMP_PROJ (SSN, PNumber, Hours, EName, PName, PLocation)
Yang merupakan modifikasi dari relasi WORKS_ON dengan tambahan attribute dari PROJECT dan
EMPLOYEE, akan membutuhkan pemakaian storage yang lebih besar, karena adanya pengulangan
(repeating group) dari :
(DName, DNumber, DMgrSSN)
dalam relasi EMP_DEPT (untuk setiap employee dalam satu department
Yang sama)
(PName, PLocation)
dalam relasi EMP_PROJ (untuk setiap employee yang bekerja dalam satu project yang
sama)
Persoalan lain yang lebih serius dari kedua relasi di atas bilamana dijadikan sebagai base relations
adalah timbulnya “Update Anomalies”, yang meliputi : (3)
- Insertion anomalies
- Deletion anomalies
- Modification anomalies
** Insertion Anomalies.
Terdiri dari dua :
Persoalan kecenderungan terjadinya inkonsistensi data.
Sebagai contoh, dalam relasi EMP_DEPT, setiap kali suatu tuple baru ditambahkan, maka
attribute-2 dari Department dimana seorang employee bekerja HARUS dituliskan secara tepat.
Jika tidak maka akan terjadi nilai-2 yang inkonsisten untuk sejumlah nomor Department yang
sama.
Persoalan kesulitan penyisipan tuple yang baru
Sebagai contoh, masih untuk relasi EMP_DEPT, jika suatu Department telah ada (didefinisikan)
tapi belum ada employee di dalamnya, maka satu-satunya cara adalah dengan mengisi nilai-nilai
NULL pada sejumlah attribute untuk employee. Tetapi cara ini menyalahi entity integrity
constraint, dimana key dari suatu relasi tidak boleh bernilai NULL.
** Deletion Anomalies.
Anomali ini berkaitan erat dengan persoalan kedua dalam insertion anomalies; dimana untuk kasus
relasi EMP_DEPT, jika suatu tuple employee yang merupakan satu-satunya employee untuk suatu
Department dihapus, maka informasi mengenai Department akan terhapus dari basis data.
** Modification Anomalies.
Dalam relasi EMP_DEPT, jika nilai dari salah satu attribute employee untuk suatu Department tertentu
diubah (misalnya nama department diubah), maka semua tuple employee yang bekerja pada
Department tersebut juga harus diubah. Jika ada tuple yang tertingal tidak diubah, maka akn terdapat
dua nama yang berbeda untuk satu department yang sama (yang seharusnya tidak boleh terjadi)
PETUNJUK-2:
Desain suatu skema relasi dasar (base relation schema) sedemikian rupa sehingga ketiga jenis
anomali (insertion, deletion dan modification) tidak akan terjadi.
Nilai-nilai NULL dalam tuples
Dalam hasil desain suatu skema relasi, mungkin saja terdapat pengelompokan sejumlah attribute
menjadi suatu relasi dengan jumlah attribute yang “besar”. Jika terdapat sejumlah sub-set
attributes yang tidak berlaku untuk semua tuple dalam relasi, maka akan terdapat sejumlah nilai-2
NULL dalam sejumlah tuples tersebut yang mengakibatkan:
Pemborosan storage
Timbulnya persoalan semantik dari attribute
Kesulitan dalam merealisasikan operasi Join (kosong dengan kosong)
Kesulitan dalam merealisasikan fungsi – fungsi agregate (seperti SUM, COUNT, dan AVERAGE)
Selain kesulitan-2 di atas, nilai – nilai NULL dapat memberikan interpretasi jamak (multiple,
intepretations) terhadap tuple yang dalamnya terdapat attribute – attribute dengan nilai null :
Attribute – 2 tersebut tidak terpakai untuk tuple
Nilai – nilai attribute untuk tuple tidak diketahui
Nilai – nilainya diketahui, tapi belum tercatat atau tersedia
PETUNJUK 3:
Sedapat mungkin, hindari penempatan attribute – attribute dalam suatu base relation yang
memungkinkan timbulnya nilainya null. Jika nilai – nilai null tidak dapat dihindari, yakinkan
bahwa hal tersebut hanya berlaku untuk kasus – kasus khusus dan jangan diberlakukan terhadap
sebagaian besar dari tuple dalam suatu relasi
Sebagai contoh, jika hanya terdapat 10% dari keseluruhan employee yang mempunyai
kantor pribadi, maka merupakan suatu cara perancangan yang beralasan apabila satu
attribute OFFICE_NUMBER dimasukkan dalam relasi EMPLOYEE; tetapi akan lebih baik
apabila dibuatkan satu relasi baru yang terdiri dari dua attribute (ESSN, OFFICE_NUMBER)
yang dipakai untuk menyimpan data employee yang mempunyai kantor pribadi.
Tuples yang Tidak Dikehendaki (Spurious
Tuples)
Untuk ini, seandainya relasi:
EMP_PROJ (SSN, PNumber, Hours, EName, PLocation)
Didekomposisi menjadi dua relasi:
EMP_LOCS (ENama, PLocation)
EMP_PROJ1 (SSN, PNUMBER, Hours, PName, PLocation)
Maka, jika kedua relasi hasil dekomposisi di atas diupayakan untuk dilakukan NATURAL JOIN
(lewat attribute ”Plocation”), akan diperoleh sejumlah tuple yang melebihi (tidak ada) dalam
EMP_PROJ.
Keadaan ini dapat terjadi karena terdapat sejumlah tuple hasil JOIN utuk “PLOCATION” yang sama,
pasangan tuple “SSn” dan “EName” yang dihasilkan bukan merupakan pasangan yang valid.
Sejumlah tuple yang ada dalam hasil JOIN tetapi tidak ada dalam relasi EMP_PROJ disebut
Spurious tuples, yaitu tuples yang tidak dikehendaki dan tidak valid.
PETUNJUK 4:
Dalam mendesain skema-skema relasi harus diupayakan sehingga skema-skema yang dihasilkan
dapat dilakukan JOIN dengan kondisi keamanan (EQUI JOIN atau NATURAL JOIN) pada attributeattribute
yang berupa primary key atau foreign key, dengan cara yang menjamin bahwa
squrious tuples tidak akan dihasilkan.
KETERGANTUNGAN FUNGSIONAL
(FUNCTIONAL DEPENENCIES)
Konsep Ketergantungan Fungsional merupakan salah satu konsep yang angat penting dalam desain
skema relasional, karena ini dapat secara formal mendefinisikan bentuk-bentuk relasi yang normal
(normalisasi data).
Definisi Ketergantungan Fungsional
Ketergantungan fungsional merupakan satu constraint antara dua set attribute suatu basis data.
Jika suatu skema basis data relasional dengan n buah attribute dinyatakan dala bentuk unversal:
R = {A1, A2, ................, An-1, An, }
Maka ketergantungan fungsional (disingkat FD) antara dua set attribute X dan Y (keduanya subset
dari R), dinotasikan X Y, menyatakan suatu constraint pada sejumlah tuples yang yang
meungkinkan dapat membentuk ”relation instance” r dari R; yaitu:
Untuk sembarangan pasangan tupoles t1 dan t2 dalam r sedemikian rupa sehingga berlaku t1[X]
= t2[X], maka juga harus berlaku t[Y] = t[Y]. (menyatakan konsep key (FK, PK))
Dari contraint di atas, dapat dikatakan bahwa nilai-nilai komponen tuple dari X dapat secara unik
(atau secara fungsional) menentukan nilai-nilai dari komponen Y. Sebaliknya, dapat juga dikatakan
bahwa Y secara fungsional tergantung pada X.
Jadi, X secara fungsoional menentukan Y dalam suatu skema relasi R dan hanya jika, bilamana dua
tuples dari r(R) mempunyai nilai X yang sama, maka kedua tuples ini juga harus mempunyai nilai Y
sama
Perlu diingat bahwa:
Jika suatu constraint pada R berlaku bahwa tidak boleh ada lebih dari satu tuple untuk suatu
nilai X dalam sembarang relation instance r(R) (yaitu X merupakan candidate key dari R)
mengisyaratkan bahwa X Y untuk sembarang subset attribute Y dari R.
Jika berlaku X Y dalam R, hal ini tidak menyatakan bahwa apakah berlaku atau tidak Y X
dalam R.
Penggunaan utama dari konsep ketergantungan fungsional adalah untuk memberikan
penjelasan lebih jauh suatu skema relasi R dengan menyatakan constraint pada sejumlah
attributenya yang harus berlaku pada setiap saat.
Sebagai contoh, perhatikan skema relasi EMP_PROJ:
EMP_PROJ (SSN, Pnumber, Hours, EName, Pname, Plocation)
Yang dari semantik attributenya berlaku ketergantungan fungsional berikut:
(a) SSN EName
(b) Pnumber {Pname, Plocation}
(c) {SSN, Pmumber} Hours
Ketergantungan fungsional merupakan sifat dari skema (intension) relasi R, bukan
merupakan keadaan relasi tertentu(extension). Dengan demikian, suatu FD tidak dapat
diturunkan secara otomatis dari suatu relasi, tetapi harus didefinisikan secara eksplisit
oleh mereka yang mengerti semantik attribute dari relasi R.
Aturan-Aturan Penurunan (Inference Rules)
Utk. Fd.
Suatu FD XY diturunkan dari satu set dependencies F dalam R jika XY berlaku dalam setiap keadaan
relasi r ; yaitu bilamana r memenuhi semua dependencies dalam. F, maka XY juga berlaku dalam r.
Satu set dari semua functional dependencies yang dapat diturunkan dari F disebut: “Closure F+ dari F”.
Untuk memperoleh cara yang sistematik dalam menurunkan dependencies, diperlakukan satu
set ”INFERENCE RULES” yang dapat digunakan untuk menurunkan dependencies yang baru dari satu set
dependencies yang diberikan.
Notasi F ╞ XY digunakan untuk menyatakan bahwa functional dependency XY diturunkan dari
satu set FDF.
Untuk tujuan mempersingkatkan penulisan variable-variabel attribute, digunakan notasi:
FD{X, Y} Z disingkat XYZ
FD{X, Y, Z}{U,V} disingkat XYZUV
Terdapat 6 aturan(rumus) untuk functional dependencies:
1. Rumus Reflexive:
Jika X ≥ Y , maka XY
2. Rumus Augmentation:
{XY} ╞ XZ YZ
3. Rumus Transitif;
{XY, YZ} ╞ XZ
4. Rumus Decomposition(Projection):
{XYZ} ╞ XY
5. Rumus Union(Additive):
{XY, XZ} ╞ XYZ
6. Rumus Pseudotransitive:
{XY, WXZ} ╞ WXZ
Rumus 1 s/d 3 dikenal sebagai ‘Armstrong’s Inference Rules’, dimana set dependence F dapat
diturunkan hanya dengan menggunakan rumus-rumus.
1s/d3 di atas (telah dibutuhkan oleh Armstrong pada 1974)
Pembuktian keenam rumus diatas dibahas dikelas!
Algoritma mencari X+
(X + : closure of X under F)
Biasanya, perancang basis data pertama mendifinisikan functional dependencies F yang dapat
ditentukan dari semantik attribute dalam R
Functional dependencies tambahan yang juga berlaku dalam R dapat diturunkan dengan
menggunakan Armstrong’s rule pada F
secara sistematik dapat diperoleh dengan cara, pertama menentukan setiap set
attribute X yang muncul disisi sebelah kiri dari FD dalam F yang kemudian dengan
menggunakan Armstrong’s rule cari semua attribute yang tergantung pada X.
Algoritmanya:
X+ := X;
REPEAT
Oldx+ := x+ ;
FOR each FD YZ dalam F DO
IF Y ≤ X+ THEN X+ :=X+ UZ;
UNTIL (oldx+ = x+);
Attribute-attribute yang bisa ditentukan disuatu attribute
CONTOH:
Perhatikan skema EMP_PROJ yang mempunyai satu set FD F berikut :
F = { SSN EName,
Pnumber {Pname, Plocation},
{SSN, PNumber} Hours
}
Dengan menggunakan algoritma untuk menghitung X+ dengan berdasarkan pada F, maka diperoleh:
{SSN}+ = {SSN, EName}
{Pnumber}+ = {Pnumber, Pname, Plocation}
{SSN, PNumber}+ = {SSN, PNumber, EName, PName, PLocation, Hours}
EMP_PROJ = { SSN, EName, PNumber, PName, PLocation, Hours}
1. SSN+ = {SSN}
Ssn Ename SSN ≤ SSN+ SSN+ = {SSN}U{Ename}={SSN, Ename}
2. Pnumber+ = {Pnumber}
Pnumber{Pname, Plocation} Pnumber ≤ Pnumber+ Pnumber+ = {Pnumber, Pname,
Plocation}
3. {SSN, Pnumber}+ = {SSN, PNumber}
a. SSN Ename x+ = {SSN, Ename, Pnumber}
b. Pnumber {Pname, Plocation} x+ = {SSN, Ename, Pnumber, Pname, Plocation}
c. {SSN, Pnumber} Hours x+ = {SSN, Ename, Pnumber, Pname, Plocation}
Set Functional Dependencies Yang Ekivalen
DEFINISI:
Satu set FD E dilingkup (covered) oleh satu set FD F (F melingkupi E), jika setiap FD dalam E juga
ada dalam F+; yaitu E dilingkup oleh F jika setiap dependency dalam E dapat diturunkan dari F.
Dua set functional dependencies E dan F dikatakan ekivalen (E=F) jika E+ = F+. ekivalen berarti
bahwa setiap FD dalam E dapat diturunkan dari F, dan setiap FD dalam F dapat diturunkan dari E.
Jadi E=F jika kedua kondisi, yaitu E melingkupi F dan F melingkupi E terpenuhi.
Untuk menentukan apakah F melingkupi E dapat dilakukan dengan ;
1. Menghitung x+ dengan berdasarkan pada F untuk setiap FD XY dalam E, maka dikatakan F
melingkupi E.
2. Periksa apakah attribute – attribute dalam Y ada dalam X+. Jika ”Ya” untuk setiap FD dalam D
maka, dikatakan F melingkupi E.
Set Functional Depedencies Yang Minimal
Satu set functional dependencies F dikatakan minimal apabila memenuhi kondisi-kondisi:
a) Setiap dependency dalam F mempunyai satu atribute tunggal pada sisi kanannya (canonical form).
b) Sembarang dependency dalam F tidak dapat dihapus dan tetap mempertahankan bahwa satu set
FD yang dihasilkan adalah ekivalen dengan F.
c) Sembarang dependency XA tidak dapat diganti dengan satu dependency YA (di mana YCX),
dan tetap menghasilkan FD yang ekivalen dengan F.
Set FD yang minimal di atas dapat dipandang sebagai satu set dependencies dalam bentuk standar (atau
canonical) tanpa redundansi.
kondisi b) dan c) menjamin bahwa tidak ada redundansi dalam dependencies.
kondisi a) menjamin bahwa setiap dependency ada dalam bentuk canonical dengan satu atribut
tunggal pada sisi kanannya.
Sumber :
Modul Perkuliahan - Basis Data - Program Studi Sistem Informasi - Fakultas Ilmu Komputer - Universitas Mercu Buana
