Normalisasi dan Fungsional Dependensi p STMIK Swadharma STMIK Swadharma Disebarluaskan oleh Abdul Aziz Efendy
Normalisasi • SStandard Industri d dI d i adalah d l h 3rdd Normal Form (NF) N lF (NF) • Anomali : Efek samping yang tidak diharapkan dalam b id t basisdata • Normalisasi menghilangkan – Modification anomalies : Terjadi jika saat perubahan pada sejumlah data yang mubazir, tetapi b i i tidak id k seluruhnya l h ik berubah. ikut b b h – Deletion anomaly: Terjadi jika suatu tuple (baris) yang tidak terpakai di hapus dan akibatnya ada data lain yang ikut terhapus. – Insertion anomaly: Terjadi se t o a o a y: e jad jjikaa pada saat pe penyisipan y s pa pada ba baris, terdapat s, te dapat eelemen e e (atribut) yang masih kosong dan elemen data tersebut menjadi kunci.
• Anomali dapat di hilangkan dengan memisah satu relasi menjadi dua atau lebih relasi, yang masing‐masing dalam tema yang berbeda dan unik. • Memecah relasi menciptakan (menghasilkan) referential integrity constraints • Normalisasi bekerja melalui kelas relasi yang dinamakan normal forms
Normalisasi (Definisi) • Dipakai i k i untukk membuat b Relasi l i dalam d l Basisdata id dengan tujuan mengurangi kemubaziran d t (E F C dd) data.(E.F. Codd) • Juga dipakai sebagai perangkat verifikasi thd tabel yang dihasilkan metodologi lainnya. • Mencegah penciptaan struktur tabel yang kurang atau mengurangi ketidak efisienan. • Proses merubah suatu relasi yyang bermasalah g ke dalam dua atau lebih relasi yang tidak bermasalah (Kroenke). Masalah==Anomali ( )
Disain database (Problems) database (Problems) • Integritas I t it – Menghindari redundansi – Menghilangkan ambiguitas ambig itas
• Performance – Akses – Efisien dalam penyimpanan
• Maintainability – Mudah di remajakan – Mudah di sisipkan – Mudah di hilangkan
Disain database (Good) database (Good) • Jika ik dilakukan dil k k normalisasi li i maka k : – Tetap dapat merepresentasikan Informasi • Dekomposisi tetap menjaga integritas • Informasi lain dalam elemen tidak hilang (lossy dan lossless)
– Dependency Preservation Dependency Preservation • Good relation (no anomali) , easy maintainance ( p (update,inser,del) , , )
– No Redundancy • 3rd NF or BCNF • Minimalisasi Perulangan
Contoh Tabel Universitas StdSSN S SSN S StdClass C OfferNo O N O OffYear EnrGrade G
CourseNo C N C CrsDesc
S1 S1 S2 S2
C1 C2 C3 C2
JUN JUN JUN JUN
O1 O2 O3 O2
2006 2006 2006 2006
3.5 3.3 31 3.1 3.4
DB VB OO VB
‐ Perkecualian utk penghilangan 2 kolom (StdCity and OffTerm) ‐ Kesalahan Typical pemula: menggunakan satu tabel utk seluruh database Anomali: ‐ PK: kombinasi dari StdSSN dan OfferNo ‐ Insert: Tdk dpt menyisipkan student baru tanpa enrolling pada offering (OfferNo bag dari PK) ‐ Update: perubahan pd desk. Course ; merubah tiap enrollment pada course ‐ Delete: hapus D l t h b i ke baris k 3; info pada 3 i f d course C3 hilang C3 hil (l (lossy) )
Redundancies ‐ mudah di‐query: tanpa di query: tanpa join ‐ Susah dirubah: dapat bekerja, tapi menyusahkan (dummy PK)
Modification Anomaly Examples Modification Anomaly Examples • Insertion – Insert data lebih dari yang di inginkan – Harus tahu student number dan offering number utk melakukan l k k insert course baru i t b • Update – Merubah multiple rows : merubah multiple rows : merubah satu fakta – Harus merubah 2 baris untuk merubah kelas student dari student S1 • Deletion – Menghapus baris menyebabkan fakta lain hilang – Menghapus enrollment dari enrollment dari student S2 dalam student S2 dalam offering O3 offering O3 menyebabkan hilangnya informasi tentang offering O3 dan course C3
Update Anomali Update Anomali Pemasok
Kota
Barang
Jumlah
Dewi
Jakarta
Monitor
10
Candra
Bandung
ZIP
4
Fanda
Jakarta
Keyboard
5
Candra
Bandung
Mouse
25
Jika Candra berpindah kota di Bogor, maka seluruh nilai atribut kota milik pemasok Candra harus di rubah semua Pemasok
Kota
Barang
Jumlah
Dewi
Jakarta
Monitor
10
Candra
Bogor
ZIP
4
Fanda
Jakarta
Keyboard
5
Candra
Bandung
Mouse
25
Insert Anomali Insert Anomali Kuliah
Ruang
Tempat
Jarkom
D.4.1
Gedung D
SBD
D.4.3
Gedung D
Kalkulu s 1 s1
D45 D.4.5
Gedung E
Sistem Pakar
D.4.10
Gedung E
AI
D41 D.4.1
Gedung D
Bagaimana menambahkan infromasi ruangan baru ? Ruang ada di suatu gedung. gedung
Delete Anomali Delete Anomali NoSiswa
Kursus
Biaya
10
Inggris
60000
10
Prancis
80000
10
Mandarin
60000
25
Inggris gg
60000
20
Jepang
65000
Siswa no 10 yang ikut bahasa inggris dihapus ?
Dependensi • Konsep yang mendasari d normalisasi l pada d relasi. • Menjelaskan hubungan antar atribut atau j nilai atribut yyang g secara khusus menjelaskan menentukan nilai atribut lainnya – Fungsional Dependensi – Fungsional Dependensi Sepenuhnya – Fungsional Total – Fungsional Tranfsitif
Fungsional Dependensi (FD) Konsep dasar • FFunctional Dependency i lD d muncull saat nilai il i atribut ib pertama (himpunan atribut) menentukan nilai pada atribut (himpunan atribut) yang kedua. )y g • Suatu Atribut Y mempunyai dependensi fungsional terhadap atribut X, JIKA DAN HANYA JIKA setiap NILAI X berhubungan d dengan SEBUAH il i Y SEBUAH nilai • Notasi XÎY (X secara fungsional menentukan Y) • X==Penentu X Penentu (determinan), Y==Tergantung (determinan) Y Tergantung (dependen) • Contoh StdSSN ‐> StdClass – Ada setidaknya satu class bagi class bagi tiap student – Tempatkan StdSSN dan StdClass sendri dalam tabel ang p candidate keyy sama Î StdSSN merupakan
Contoh FD Pembeli b li
Kota
Barang
Jumlah l h
P1
Yogya
B1
10
P1
Yogya
B2
5
P2
Solo
B1
7
P2
Solo
B2
6
P2
Solo
B3
6
P3
Semarang
B3
7
P3
Semarang
B4
6
Pembeli ÎKota {Pembeli,Barang}ÎJumlah { {Pembeli, Barang}ÎKota , g} {Pembeli,Barang}Î{Jumlah, Kota}
FD Lanj FD Lanj. • Atribut di sebelah kiri FD disebut determinant – SID Æ DormName, Fee – (CustomerNumber, ItemNumber, Quantity) Æ (CustomerNumber ItemNumber Quantity) Æ Price
• PK adalah selalu suatu determinant, tetapi suatu determinant tidak determinant tidak selalu suatu PK. PK – Apakah Candidate keys selalu suatu determinant?
FD lanj FD lanj. X → Y X (secara fungsional) menentukan Y X: left‐hand‐side (LHS) or determinan (penentu) Untuk semua nilai X , ada X , ada setidaknya paling paling banyak satu nilai Y • Mirip dengan candidate keys. candidate keys • FD Trivial XÎY jika Y⊆X • • • •
– XÎX XÎX ; – X,Y,ZÎ X,Z;
X,YÎX; X YÎX X YÎY X,YÎY; X,Y,ZÎ X,Z; X,Y,ZÎX,Y,Z
FD Lanj FD Lanj. • Diberikan α ⊆ R and β ⊆ R, maka FD adalah α→βp pada R, jika ,j – ti(α) adalah unik, dengan 1≤i≤n adalah nilai pada index tuple/record ke i dan α adalah atribut index tuple/record ke – ti(α)= tj(α) , i≠j dan ti(β)= tj(β) A
B
C
1
4
C1
1
5
C1
2
7
C2
AÎB ? t1(A)= t (A) t2(A), ya (A) ya t1(B)≠ t2(B), tidak Maka AÎB
AÎC ? t1(A)= t2(A), ya T1(C)= t2(C), ya Maka AÎC
Contoh lain • • • • • • • • •
DiKetahui DiK t h i R(A,B,C,D) R(A B C D) AÎC Y CÎA Î N (A,B)ÎC Y(unik) (A,B)ÎB Y(unik) A → B, ? A → D, ? B → D, ? → , AB → D, ?
A
B
C
D
A1
B1
C1
D1
A1
B2
C1
D2
A2
B2
C2
D2
A2
B3
C2
D3
A3
B3
C2
D4
Closure Set of FD Closure Set of FD Diberikan ib ik F berupa b set of FD dipenuhi f di hi oleh l h R, dan d X, Y, K mrp subset dari R. • F (logically) implies X → Y if setiap R memenuhi (semua FD dalam) F, R juga memenuhi X → Y. • Closure F, dinotasikan F+, adalah set dari FD yang diimplikasikan oleh F, dengan demikian F+ = {X → Y | F implies X → Y}. • Dengan g kata lain bahwa Jika R memenuhi F, maka , F+ merupakan set semua ALL FD yang dipenuhi oleh R.
F+: Contoh F+: Contoh • FF = {AB → C, C → B} set dari {AB → C C → B} t d i FD yang dipenuhi FD di hi R(A, B, R(A B C). F+ = {A → φ A → A AB → φ AB → A AB → B F+ = {A → φ, A → A, AB → φ, AB → A, AB → B, AB → C, AB → AB, AB → AC, AB → BC, AB →ABC, AC → φ, AC → A, AC → B, AB →ABC, AC → φ, AC → A, AC → B, AC → C, AC →AB, AC → AC, AC → BC, AC → ABC, ABC → φ,ABC → A, ABC → B, → , → φ, → , → , ABC → C, ABC → AB, ABC→ AC, ABC → BC, ABC → ABC, B → φ, B → B,BC → φ, , φ, , φ, BC → B, BC → C, BC → BC, C → φ, C →B, C → C, C → BC, φ → φ }
Contoh F AB→ C aug
union AB→ BCD
decomp
trans A→ D AB→ BD AB → BCDE AB→ CDE aug
D→ E BCD → BCDE
• Jadi Jadi, AB AB→ BD, AB BD AB → BCD, AB BCD AB → BCDE, dan BCDE dan AB AB → CDE adalah semua elemen dari F+
Candidate Key & Trivial FD Candidate Key & Trivial FD • F adalah set of FD yg dipenuhi R, dan K R. K adalah candidate key dari y R JIKA,, – K → R berada dalam F+ (F implies K → R); and, – Tidak ada X X K, sdmk K sdmk rupa shg X → R juga X → R juga berada dalam F+ (minimality).
• Suatu trivial FD X → Y, jika l k Y X. – contoh: AB → B, A → φ, φ → φ.
Penurunan FD dg Amstrong’s Rules • Reflexive R fl i – Jika y⊆x maka xÎy
• Augmentation – Jika xÎy maka (x,z)Î(y,z)
• Transitive – Jika xÎy dan yÎz maka xÎz
• Decomposition – Jika xÎ(y,z) maka xÎ(y z) maka xÎy dan xÎz
• Union – Jika xÎy dan xÎz maka xÎ(y,z)
• Psuedotransitive – Jika xÎy dan (z,y)Îw maka (x,z)Îw
jika xÎy Augmentation (x,z)Î(y,z) ,y) Jika ((z,y)Îw Transitive zÎw dan yÎw (x,z)Îw
FD Diagram dan List FD Diagram dan StdSSN StdClass OfferNo OffYear EnrGrade
CourseNo CrsDesc
S1 S1 S2 S2
C1 C2 C3 C2
JUN JUN JUN JUN
O1 O2 O3 O2
2006 2006 2006 2006
3.5 3.3 31 3.1 3.4
DB VB OO VB
Diagram
StdSSN StdCity
StdClass
OfferNo OffTerm OffYear CourseNo
StdSSN → StdCity, StdClass LIST
OfferNo → OffTerm, OffYear, CourseNo, CrsDesc CourseNo → CrsDesc StdSSN, OfferNo → EnrGrade
CrsDesc EnrGrade
Fungsional Dependensi Sepenuhnya • SSuatu t atribut t ib t Y mempunyai Y i dependensi d d i fungsional sepenuhnya terhadap atribut X, JIKA : – Y mempunyai Y mempunyai FD thd FD thd X, dan X dan – Y tidak memiliki dependensi thd bagian dari X – Contoh : Cust(kode,nama,kota,faks) maka tdpt : • {kode,kota}Îfaks • Kode Î faks
• Irreducible dependen (dependensi yang tak dapat di bagi) atau b i) f ll f full functional dependen i ld d atau fully f ll dependen
Dependensi Total • Suatu atribut Y mempunyai dependensi total terhadap p X, JIKA : , – Y memiliki FD thd X, dan – X mempunyai X mempunyai FD thd FD thd Y
• Notasi XÍÎ Y
Kode
Nama
Kota
K1
Kartika
Jakarta
C1
Candra
Bandung
C2
Manda
Jakarta
Kode ÍÎ Nama
Dependensi Transitif • Atribut Z mempunyai Z mempunyai dependensi transitif terhadap X bila : – Y memiliki l k FD thd hd X – Z memiliki FD thd Y
• Notasi XÎZÎY Kuliah
Ruang
Tempat
Waktu
Jarkom
D.4.1
Gedung D
Senin‐1
SBD
D43 D.4.3
G d Gedung D
S l Selasa‐2 2
Kalkulu s 1
D.4.5
Gedung E
Rabu‐2
Sistem Pakar
D.4.10
Gedungg E
Selasa‐1
Kuliah Î{ruang, waktu} R RuangÎtempat Ît t Kuliah Î ruang Î tempat
FD dalam Data FD dalam StdSSN S1 S1 S2 S2
StdClass JUN JUN JUN JUN
OfferNo O1 O2 O3 O2
OffYear 2006 2006 2006 2006
EnrGrade 35 3.5 3.3 3.1 34 3.4
CourseNo C1 C2 C3 C2
CrsDesc DB VB OO VB
•
Buktikan bahwa tidak ada FD dengan melihat data
•
2 baris yang punya nilai sama pada X tetapi berbeda pada nilai Y
Jawab dengan Lihat Data: ‐ Berguna pd saat menjelaskan pada user ‐ Ada tool yang otomatis dapat menghilangkan FD pada baris data diatas Contoh: • OfferNo ‐> StdSSN: baris kontradiksi ( 2, 4) (OfferNo sama tetapi StdSSN berbeda) • StdSSN ‐> OfferNo: baris kontradiksi (<1,2>, <3,4>) • StdSSN ‐> OffYear: data tidak ‐> OffYear: data tidak memiliki kontradiksi • tambahkan baris utk proof. kontradiksi (enroll S1 pada offering year = 2001)
Identifikasi FD • Easy identification (Mudah) – Adanya y keunikan – PK dan CK dihasilkan dari konversi ERD – 1‐M relationship: FD dari 1 M relationship: FD dari child ke child ke parent
• Difficult identification (Sulit) – LHS bukan PK atau CK dalam tabel yang dikonversi – LHS mrpk LHS mrpk bagian dari kombinasi PK atau PK atau CK CK
• Buat minimalitas pada LHS (Left Hand Side)
Key dan FD Key dan • Rule 1 – FD memuat atribut dimana LHS‐nya y adalah SK – R(W,X,Y,Z);FD=XYÎWZ, jadi XY adalah SK – Bukti : • • • • •
XYÎWZ XYÎXY ( fl ti ) XYÎXY (reflextive) XYÎXYWZ (union) XYÎR Karena XYÎR, maka XY=SK
Key dan FD lanj. Key dan FD lanj • Rule 2 – Atribut secara fungsional g menentukan SK tabel, , jadi atribut tsb adalah SK – R(W,X,Y,Z); FD=ZÎW, jadi R(W X Y Z); FD=ZÎW jadi Z=SK – Bukti • • • •
ZÎW WÎWXZY (sebab W = SK), maka ZÎWXYZ (transitif) Î ( i if) ZÎR maka Z adalah SK
Trick • If an attribute never appears on the RHS of any FD, it must be part of the key y , p f y • If an attribute never appears on the LHS of any FD but appears on the RHS FD, but appears on the RHS of any FD, it must of any FD it must not be part of any key
Contoh Lain • R(ABCD), (A,B)= SK dari ( ) ( ) d R ((A,B)ÎR)?? (( )Î )?? • Karena tupel p ti[[A,B], 1≤i≤5, adalah , ], , unik – t1[A,B]=(A1,B1) – t2[A,B] [A,B]=(A1,B2) (A1,B2) – t3[A,B]=(A2,B2) – t4[A,B]=(A2,B3) [A B]=(A2 B3) – t5[A,B]=(A3,B3)
A
B
C
D
A1
B1
C1
D1
A1
B2
C1
D2
A2
B2
C2
D2
A2
B3
C2
D3
A3
B3
C2
D4
• Maka k (A,B) ( )Î(A,B,C,D) atau ( C ) ( )ÎR, (A,B) sehingga (A,B)ÎR
Contoh Lain • •
SS=(A,B,C,D,E,F); FD=AÎBC; BÎD; CÎEF; BFÎA (A B C D E F) FD AÎBC BÎD CÎEF BFÎA Temukan SK dan CK dari S dengan FD ? – AÎBC dekomposisi menjadi AÎB dan AÎC Karena AÎB dan Î BÎD, maka Î AÎD Î Karena AÎC dan CÎEF maka AÎEF, – AÎA, sehingga AÎA,B,C,D,E,F •Jadi A,BC, BF dan gabungan b atribut b Jadi AÎS superkey yang mengandung A,BC dan BF – BÎD, maka BCÎD,C (Aug) merupakan Superkey – CÎEF, maka BCÎBEF (Aug) •Candidate Key dari C did t K d i S adalah S d l h A,BC, A BC Jadi BCÎB,C,D,E,F (Union) dan BF – BCÎA,B,C,D,E,F dan B,CÎA, maka BÎA,B,C,D,E,F Jadi BCÎS merupakan Superkey – BFÎA dan AÎA,B,C,D,E,F maka BFÎA,B,C,D,E,F Jadi BFÎS
Dekomposisi • Lossy (ada informasi yang hilang pada saat terjadi dekomposisi) • Lossless (tidak ada informasi yang hilang pada saat terjadi dekomposisi) • Manfaat FD pada dekomposisi: – Lossless Join Decomposition l – No Redundancy – Dependecy Preservation (Terjaminya pemeliharaan ketergantungan, utk mengatasi update Anomali)
Konsep Lossles‐join Decomposition Lossles join Decomposition • R{R1,R2,R3…..,Rn} merupakan Lossless‐join Decomposition Jika : – R1∩R2 ∩ R3 ∩ … ∩ Rn Î Ri, untuk 1≤ i ≤n
• Jika R didekomposisi R didekomposisi menjadi {R1,R2} maka {R1 R2} maka disebut Lossless join decomposition jika : – R1∩R2ÎR1 atau R1∩R2ÎR1 atau R1∩R2 ÎR2
• Lossless Join decomposition didapatkan dengan : – Uji Dekomposisi – Uji Lossless join
: R1∪R2∪R3 ∪ … ∪ Rn Î R : FD
Contoh Lossless join Decomposition Lossless join Decomposition • R(A,B,C,D,E ,F,G), dekomposisi ( ) d k menjadi d R1(A,B,C,D,G) dan R2(B,D,E,F,H) sedang FD‐nya adalah : – (1)BÎA,G ;(2) EÎD,H ; (3)AÎ E,C ; (4)DÎF – Apakah R1 dan R2 Lossless atau Lossy ?
• Uji Dekomposisi – R1∪R2 =(A,B,C,D,G)∪(B,D,E,F,H) =(A B C D E F G H) =(A,B,C,D,E,F,G,H) =R , YES !
Contoh Lossless join Decomposition Lossless join Decomposition • Uji Lossless dengan L l d FD – R1∩R2=(A,B,C,D,G) ∩ (B,D,E,F,H)=(B,D) – R1∩R2ÎR1 atau R1∩R2ÎR2 • (B,D)Î(A,B,C,D,G) atau (B,D)Î(B,D,E,F,H)
• (B,D)Î(A,B,C,D,G) – (1) BÎ(A,G) • (5) B,DÎA,G,D (Aug) dan • (6) B,DÎB,D (Refl) shg • (7) B,DÎA,B,D,G (union)
dari (8) BÎA dan (11) AÎC maka (12) dan (13)
BÎC (transitif) B,DÎC,D (Aug)
– (1) BÎA,G menjadi (1) BÎA G j di • (8) BÎA dekomposisi • (9) BÎG
– (3) AÎE,C menjadi (3) AÎE C j di • (10) AÎE dekomposisi • (11) AÎC
Dari (7) dan (13) union didapat B,DÎA,B,C,D,G B DÎA B C D G
YES
Kerjakan untuk (B,D)Î(B,D,E,F,H)
FD= (1)BÎA,G ;(2) EÎD,H ; (3)AÎ E,C ; (4)DÎF
Dekomposisi Tak Hilang (data) • Terjadi pemecahan satu relasi menjadi 2 atau lebih (dekomposisi) • Dekomposisi D k i i tak t k hilang hil : tidak tid k ada d informasi i f i yang hilang hil k tik ketika relasi di pecah menjadi relasi‐relasi lain Dekomposisi Tak Hilang
NIM
Nama
NIM
Progdi
95001
Budi
95001
TI
95002
Edi
95002
MI
95003
Budi
95003
TI
NIM
Nama
Progdi
95001
Budi
TI
95002
Edi
MI
NIM
Nama
Nama
Progdi
95003
Budi
TI
95001
Budi
Budi
TI
95002
Edi
Edi
MI
95003
Budi
Budi
TI
Dekomposisi Hilang
Closure dari F (F Closure dari F (F+) • Jika F himpunan FD dari relasi R, maka semua FD yang mungkin diturunkan dari F dengan hukum‐hukum FD disebut Closure dari Closure dari F (ditulis F (ditulis F+). ) • Jika R=(A,B,C,D), F={AÎB, BÎC,AÎC,CÎD}, maka, – AÎD, sebab AÎD b b AÎC dan AÎC d CÎD (transitif) CÎD ( i if) – BÎD, sebab BÎC dan CÎD (transitif) – Sehingga {AÎB, BÎC,AÎC,CÎD,AÎD, BÎD} ⊆ F+ • F+ berguna pada Uji Dependency Preservation
Menghitung Closure dari Closure dari set FD set FD • Mulai F+ dengan yang diberikan dari set of FD, Ulangi g terus dengan g memakai Reflexivity,Augmentation,Transitivity, tambahkan turunannya (FD baru) ke (FD baru) ke F+, F+ hingga tidak ada FD baru yang dapat diturunkan. diturunkan
contoh • Buktikan: { X → YZ } |= { X → Y, X → Z } yang k ik { → } | { → → } memenuhi R(XYZ) • bukti: xÎ YZ (1) ; xÎy (2) dan xÎz (3) • Fd1 (xÎy) ( y) – (Ref), kita punya YZ → Y (4) dan YZ → Z (5) • Ingat FD trivial xÆy jika y subset x
– dengan X → YZ (1), YZ → Y (4) dan dengan trans menjadi X → Y (2);
• Fd2 (xÎz) sama, X → YZ (1), YZ → Z (5) secara trans menjadi X → Z (3).
Closure of Attributes X Closure of Attributes X+ Q: Apakah Q A k h set F dari t F d i FD berimplikasi FD b i lik i pada d X → Y? X → Y? • Method 1: Hitung F+ & test jika X → Y maka berada dalam F+. F+ – Problem: F+ susah di hitung !
• Method Method 2: Hitung 2: Hitung closure X di closure X di dalam F., yang F yang mana merupakan set attribute yang secara fungsional ditentukan oleh X dalam X dalam F, atau F atau X+ = { A | X → A F+ } Theorem: X → Y F+ jika Theorem: X → Y F+ jika dan hanya jika Y Y X+. X+ Bukti: Use Dekom & Union.
Menghitung Closure Atribut Closure Atribut X + Algorithm menemukan Al ith k X+ Input: F: set FD yang dipenuhi R X: set atribut dari R X: set atribut Output: X + (= xplus). Method: xplus := X; while xplus berubah do while xplus for tiap FD Y → Z dalam F do if Y xplus then xplus if Y then xplus ::= xplus xplus return xplus
Z;
Contoh R=(A,B,C,D,E,F) R (A B C D E F) • F: AB → C, BC → AD, D → E, CE → B • Hitung Hit {A B}+? {A,B} 1. X={A,B} 1 X {A B} 2. Tambah C ke X (dari AB→ C); X={A,B,C} 3 T b h A,D ke 3. Tambah A D k X (dari X (d i BC → BC AD; X={A,B,C,D} AD X {A B C D} 4. Tambah E ke X (dari D → E); X={A,B,C,D,E} 5 Tid k ada 5. Tidak d lagi l i atribut t ib t yang dapat d t di tambahkan t b hk ke k X 6. {A,B}+ = {A,B,C,D,E}
Contoh Compute (AG)+ dalam {A → B, CG → HI, B →H, A → C} B →H, A → C} Init: xplus := AG; FD Xplus Baru iterasi1: XPlus AG
AÎB
ABG
ABG
CGÎHI
ABG
ABG
BÎH
ABGH
ABGH
AÎC
ABCGH
Xplus berubah maka, ulangi loop.
Lanjutan • Iterasi 2
• Iterasi 3
XPlus l
FD
Xplus l Baru
ABCGH
AÎB
ABCGH
ABCGH
CGÎHI
ABCGHI
ABCGHI
BÎH
ABCGHI
ABCGHI
AÎC
ABCGHI
XPlus
FD
Xplus Baru
ABCGHI
AÎB
ABCGHI
ABCGHI
CGÎHI
ABCGHI
ABCGHI
BÎH
ABCGHI
ABCGHI
AÎC
ABCGHI
(AG)+ = ABCGHI
Check Candidate Key Check Candidate Key Diberikan ib ik R yang memenuhi hi set F dari d i FD dan d K R. Apakah K suatu candidate key? Kita tahu bahwa K adalah candidate key JIKA – R memenuhi K → R; dengan dmk K+=R dalam F, dan – Untuk setiap subset X dari K, X+ ≠ R.
Dalam contoh tadi, karena , – (AG)+ = ABCGHI = R, dan – A+ = ABCH ≠ R, G+ = G ≠ R, , ,
AG adalah candidate key dari R(ABCGHI) dibawah F
Contoh lagi Hitung closure attribute dari AB (AB+) Dengan FD : AB → C A → D D → E AC → B
Solusi
(a) (b) (c) (d)
Initi closure = {AB} dengan(a) closure = {ABC} dengan(b) closure = {ABCD} dengan(b) closure = {ABCD} dengan(c) closure = {ABCDE}
B bagian B bagian (d) tetap (d) tetap di hitung tetapi karena Closure tidak Closure tidak berubah, berubah, ABCDE U B=ABCDE, dan AB adalah CK dari R(ABCDE)
• R(A, B, C, D, E, F) dan S: A → BC E → CF B→E CD → EF Hitung closure {A, B} closure {A B}+ dari set {A, B} pada set {A B} pada S. S
Contoh Lagi • R( A, B, C, D, E ) F={AB→C，BC→AD，D→E，CF→B}， { → ， → ， → ， → }， Hitungg Closure {A, B}+ dari {A, B} di bawah S. ①{A,B}+ = {A,B} ② AB→C {A,B}+ = {A,B,C} ③ BC→AD {{A,B} , }+ = {A,B,C,D} { , , , } ④ D→E {A,B}+ = {A,B,C,D,E} ⑤ {A,B A,B}}+ = {A,B,C,D,E}
Contoh lagi
• R = {A, B, C, D, E} • F = { B →CD, D → { , E, B → , A, E → , C, AD →B } , } • Is AD a key for R? • Is B → E in F+ ? AD+ = AD B+ = B
B+ = BCD AD+ = ABD dan B = key Yes! B+ = BCDA • Is AD a candidate key B+ = BCDAE … Yes! dan ! d for R? B = key bagi R ! A+ = A • Is D a key for R? Is D a key for R? … A not a key, so Yes! D+ = D • Is ADE a candidate key D+ = DE for R? D+ = DEC … bukan! … No! AD is a key, so ADE is a superkey, k b t nott a cand. but d key k
Dependency Preservation (DP) Dependency Preservation (DP) • R adalah d l h skema k relasi, dimana l d R di d dekomposisi menjadi R1,R2,R3,…,Rn dan F1,F2,F3,…,Fn adalah himpunan FD yang berlaku untuk R, maka dekomposisi tersbut dikatakan memenuhi DP jika : – (F1∪F2 ∪F3∪… ∪Fn)+=F+
• DP merupakan kriteria penjamin keutuhan relasi, ketika suatu relasi di dekomposisi, jadi relasi, ketika dekomposisi, jadi dapat menghindari anomali dan inkonsistensi
Dependecy Preservation Contoh Preservation Contoh • R=(A,B,C) dan FD:AÎB, BÎC didekomposisikan menjadi R1=(A,B) dan R2=(B,C) – Lossles join decomposition ?? – Dependency Preservation ?? p y
• R1∪R2=(A,B)∪(B,C)=(A,B,C)=R (dekomposisi) • R1∩R2=(A,B)∩(B,C)=(B) R1 R2 (A B) (B C) (B) – Jika BÎ(A,B) atau BÎ(B,C) maka lossless karenaBÎC maka BBÎBC atau BÎC (Aug) – Jadi dekomposisi‐nya lossless join
Dependecy Preservation lanj. Preservation lanj • R=(A,B,C), FD={AÎB,BÎC} ( ) { Î Î } – Karena AÎB dan BÎC maka AÎC, sehingga – F+={AÎB,BÎC, AÎC} – R1=(A,B), F1={AÎB}, krn hanya AÎB yg berlaku pada R1 – R2=(B,C), F2={BÎC}, krn hanya BÎC yg berlaku pada R2 – F1∪F2={AÎB, BÎC}, krn AÎB dan BÎC maka AÎC – Sehingga S hi (F1∪F2)+={AÎB, BÎC,AÎC}=F {AÎB BÎC AÎC} F+ – Jadi memenuhi DP
Relationships of Normal Forms Relationships of Normal Forms 1NF 2NF 3NF/BCNF 4NF 5NF DKNF
1NF: tip table berada 1NF ti t bl b d pada d 1NF 2NF: tiap tabel dalam 2NF juga dalam 1NF 3NF/BCNF: BCNF adalah edisi revisi dari 3NF, 4NF: Mengurangi penggunaan M‐way relationship;Relationship independence and MVDs; does not involve FDs 5NF tidak melibatkan FD; Inappropriate usage of an M‐way relationship; more specialized than 4NF 5NF: tidak FD Inappropriate sage of an M a relationship more speciali ed than 4NF DKNF: bentuk ideal secara teori
