normalisasi dan fungsional dependensi · pdf fileab→bcd a→ ... • kode...
Post on 05-Feb-2018
241 Views
Preview:
TRANSCRIPT
Normalisasi dan FungsionalNormalisasi dan FungsionalDependensip
STMIK SwadharmaSTMIK SwadharmaDisebarluaskan oleh Abdul Aziz Efendy
NormalisasiNormalisasi
S d d I d i d l h 3 d N l F (NF)• Standard Industri adalah 3rd Normal Form (NF)• Anomali : Efek samping yang tidak diharapkan dalamb i d tbasisdata
• Normalisasi menghilangkan– Modification anomalies : Terjadi jika saat perubahan pada sejumlah data yang
b i i id k l h ik b b hmubazir, tetapi tidak seluruhnya ikut berubah.– Deletion anomaly: Terjadi jika suatu tuple (baris) yang tidak terpakai di hapus dan
akibatnya ada data lain yang ikut terhapus.– Insertion anomaly: Terjadi jika pada saat penyisipan pada baris, terdapat elemense t o a o a y: e jad j a pada saat pe y s pa pada ba s, te dapat e 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)Normalisasi (Definisi)
i k i k b l i d l i d• Dipakai untuk membuat Relasi dalam Basisdatadengan tujuan mengurangi kemubazirand t (E F C dd)data.(E.F. Codd)
• Juga dipakai sebagai perangkat verifikasi thd tabelyang dihasilkan metodologi lainnya.
• Mencegah penciptaan struktur tabel yang kurangatau mengurangi ketidak efisienan.
• Proses merubah suatu relasi yang bermasalah key gdalam dua atau lebih relasi yang tidakbermasalah (Kroenke). Masalah==Anomali( )
Disain database (Problems)Disain database (Problems)
I t it• Integritas– Menghindari redundansiMenghilangkan ambig itas– Menghilangkan ambiguitas
• PerformanceAkses– Akses
– Efisien dalam penyimpanan• Maintainability• Maintainability
– Mudah di remajakan– Mudah di sisipkan– Mudah di sisipkan– Mudah di hilangkan
Disain database (Good)Disain database (Good)
ik dil k k li i k• Jika dilakukan normalisasi maka :– 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(update,inser,del)( p , , )
– No Redundancy• 3rd NF or BCNF • Minimalisasi Perulangan
Contoh Tabel UniversitasContoh Tabel UniversitasStdSSN StdClass OfferNo OffYear EnrGrade CourseNo CrsDescS SSN S C O N O G C N CS1 JUN O1 2006 3.5 C1 DB S1 JUN O2 2006 3.3 C2 VB S2 JUN O3 2006 3 1 C3 OOS2 JUN O3 2006 3.1 C3 OOS2 JUN O2 2006 3.4 C2 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 courseD l t h b i k 3 i f d C3 hil (l )‐ Delete: hapus baris ke 3; info pada course C3 hilang (lossy)
Redundanciesmudah di query: tanpa join‐mudah di‐query: tanpa join
‐ Susah dirubah: dapat bekerja, tapi menyusahkan (dummy PK)
Modification Anomaly ExamplesModification Anomaly Examples• InsertionInsertion
– Insert data lebih dari yang di inginkan– Harus tahu student number dan offering number utk
l k k i t bmelakukan insert course baru• Update
– Merubah multiple rows : merubah satu faktaMerubah multiple rows : merubah satu fakta– Harus merubah 2 baris untuk merubah kelas student daristudent S1
• Deletion– Menghapus baris menyebabkan fakta lain hilang– Menghapus enrollment dari student S2 dalam offering O3– Menghapus enrollment dari student S2 dalam offering O3 menyebabkan hilangnya informasi tentang offering O3 dancourse C3
Update AnomaliUpdate AnomaliPemasok 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 seluruhnilai atribut kota milik pemasokCandra 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 AnomaliInsert AnomaliKuliah Ruang Tempat
Jarkom D.4.1 Gedung D
SBD D.4.3 Gedung D
Kalkulu s 1 D 4 5 Gedung EKalkulu s 1 D.4.5 Gedung E
Sistem Pakar D.4.10 Gedung E
AI D 4 1 Gedung DAI D.4.1 Gedung D
Bagaimana menambahkan infromasi ruangan baru ?Ruang ada di suatu gedungRuang ada di suatu gedung.
Delete AnomaliDelete Anomali
NoSiswa Kursus Biaya
10 Inggris 60000
10 Prancis 8000010 Prancis 80000
10 Mandarin 60000
25 Inggris 60000gg
20 Jepang 65000
Siswa no 10 yang ikut bahasa inggris dihapus ?
DependensiDependensi
d l d• Konsep yang mendasari normalisasi padarelasi.
• Menjelaskan hubungan antar atribut atausecara khusus menjelaskan nilai atribut yang j y gmenentukan nilai atribut lainnya– Fungsional DependensiFungsional Dependensi– Fungsional Dependensi SepenuhnyaFungsional Total– Fungsional Total
– Fungsional Tranfsitif
Fungsional Dependensi (FD)Konsep dasar
F i l D d l il i ib• Functional Dependency muncul saat nilai atribut pertama(himpunan atribut) menentukan nilai pada atribut (himpunanatribut) yang kedua.) y g
• Suatu Atribut Y mempunyai dependensi fungsional terhadapatribut X, JIKA DAN HANYA JIKA setiap NILAI X berhubungand SEBUAH il i Ydengan SEBUAH nilai Y
• Notasi X Y (X secara fungsional menentukan Y)• X Penentu (determinan) Y Tergantung (dependen)• X==Penentu (determinan), Y==Tergantung (dependen)• Contoh StdSSN ‐> StdClass
Ada setidaknya satu class bagi tiap student– Ada setidaknya satu class bagi tiap student– Tempatkan StdSSN dan StdClass sendri dalam tabel angsama StdSSN merupakan candidate keyp y
Contoh FDContoh FD
b li l hPembeli Kota Barang Jumlah
P1 Yogya B1 10
P1 Yogya B2 5P1 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 LanjFD Lanj.
• Atribut di sebelah kiri FD disebut determinant– SID DormName, Fee
(CustomerNumber ItemNumber Quantity) Price– (CustomerNumber, ItemNumber, Quantity) Price
• PK adalah selalu suatu determinant, tetapisuatu determinant tidak selalu suatu PKsuatu determinant tidak selalu suatu PK.– Apakah Candidate keys selalu suatu determinant?
FD lanjFD lanj.
• X → Y• X (secara fungsional) menentukan Y• X: left‐hand‐side (LHS) or determinan (penentu)• Untuk semua nilai X , ada setidaknya palingUntuk semua nilai X , ada setidaknya paling banyak satu nilai Y
• Mirip dengan candidate keys• Mirip dengan candidate keys.• FD Trivial X Y jika Y⊆X
X X X Y X X Y Y– X X ; X,Y X; X,Y Y;– X,Y,Z X,Z; X,Y,Z X,Z; X,Y,Z X,Y,Z
FD LanjFD Lanj.
• Diberikan α ⊆ R and β ⊆ R, maka FD adalahα→ β pada R, jikaβ p , j– ti(α) adalah unik, dengan 1≤i≤n adalah nilai padaindex tuple/record ke i dan α adalah atributindex tuple/record ke i dan α adalah atribut
– ti(α)= tj(α) , i≠j dan ti(β)= tj(β)
A B C A B ?t (A) t (A) ya
A C ?t1(A)= t2(A), ya
1 4 C1
1 5 C1
2 7 C2
t1(A)= t2(A), yat1(B)≠ t2(B), tidakMaka A B
T1(C)= t2(C), yaMaka A C
2 7 C2
Contoh lainContoh lain
DiK t h i R(A B C D)• DiKetahui R(A,B,C,D)• A C Y
A B C D
A1 B1 C1 D1
• C A N• (A,B) C Y(unik)
A1 B2 C1 D2
A2 B2 C2 D2
A2 B3 C2 D3• (A,B) B Y(unik)• A → B, ?
A2 B3 C2 D3
A3 B3 C2 D4
• A → D, ?• B → D, ?→ ,• AB → D, ?
Closure Set of FDClosure Set of FD
ib ik b f di hi l h dDiberikan F berupa set of FD dipenuhi oleh R, dan 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 kata lain bahwa Jika R memenuhi F, makag ,F+ merupakan set semua ALL FD yang dipenuhioleh R.
F+: ContohF+: Contoh
F {AB→ C C→ B} t d i FD di hi R(A B• F = {AB → C, C → B} set dari FD yang dipenuhi R(A, B, C).
F+ = {A→φ A→ A AB→φ AB→ A AB→ BF+ = {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, φ → φ }
ContohContoh
F
AB→ CAB→ CAB→ BCD
A→ D AB→ BD AB→ BCDE AB→ CDE
unionaug
transdecomp
D→ E BCD → BCDEaug
• Jadi AB→ BD AB→ BCD AB→ BCDE dan ABJadi, AB→ BD, AB → BCD, AB → BCDE, dan AB → CDE adalah semua elemen dari F+
Candidate Key & Trivial FDCandidate Key & Trivial FD
• F adalah set of FD yg dipenuhi R, dan K R. K adalah candidate key dari R JIKA,y ,– K → R berada dalam F+ (F implies K → R); and,
Tidak ada X K sdmk rupa shg X→ R juga berada– Tidak ada X K, sdmk rupa shg X → R juga beradadalam F+ (minimality).
l k• Suatu trivial FD X → Y, jika Y X. – contoh: AB → B, A → φ, φ → φ.
Penurunan FD dgAmstrong’s Rules
R fl i• Reflexive– Jika y⊆x maka x y
• Augmentation
jika x yAugmentation (x,z) (y,z)Jika (z,y) wAugmentation
– Jika x y maka (x,z) (y,z)• Transitive
( ,y)Transitive z w dan y w
(x,z) w
– Jika x y dan y z maka x z• Decomposition
Jika x (y z) maka x y dan x z– Jika 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
FD Diagram dan ListFD Diagram dan ListStdSSN StdClass OfferNo OffYear EnrGrade CourseNo CrsDescStdSSN StdClass OfferNo OffYear EnrGrade CourseNo CrsDescS1 JUN O1 2006 3.5 C1 DB S1 JUN O2 2006 3.3 C2 VB S2 JUN O3 2006 3 1 C3 OOS2 JUN O3 2006 3.1 C3 OOS2 JUN O2 2006 3.4 C2 VB
DiagramDiagram
StdSSN StdCity StdClass OfferNo OffTerm OffYear EnrGradeCourseNo CrsDesc
StdSSN→ StdCity, StdClass
OfferNo→ OffTerm, OffYear, CourseNo, CrsDescLIST
CourseNo→ CrsDesc
StdSSN, OfferNo→ EnrGrade
Fungsional Dependensi SepenuhnyaFungsional Dependensi Sepenuhnya
S t t ib t Y i d d i• Suatu atribut Y mempunyai dependensifungsional sepenuhnya terhadap atribut X, JIKA :
Y mempunyai FD thd X dan– Y mempunyai FD thd X, dan– Y tidak memiliki dependensi thd bagian dari X– Contoh :Contoh :Cust(kode,nama,kota,faks) maka tdpt :
• {kode,kota} faks• Kode faks
• Irreducible dependen (dependensi yang tak dapatdi b i) f ll f i l d d f lldi bagi) atau full functional dependen atau fully dependen
Dependensi TotalDependensi Total
• Suatu atribut Y mempunyai dependensi total terhadap X, JIKA :p ,– Y memiliki FD thd X, dan
X mempunyai FD thd Y– X mempunyai FD thd Y
• Notasi X YKode Nama KotaKode Nama Kota
K1 Kartika Jakarta
C1 Candra Bandung
C2 Manda Jakarta
Kode Nama
Dependensi TransitifDependensi Transitif• Atribut Z mempunyai dependensi transitifAtribut Z mempunyai dependensi transitifterhadap X bila :
l k hd– Y memiliki FD thd X
– Z memiliki FD thd Y
• Notasi X Z Y
Kuliah Ruang Tempat Waktu
Jarkom D.4.1 Gedung D Senin‐1
SBD D 4 3 G d D S l 2
Kuliah {ruang, waktu}R t tSBD D.4.3 Gedung D Selasa‐2
Kalkulu s 1 D.4.5 Gedung E Rabu‐2
Sistem Pakar D.4.10 Gedung E Selasa‐1
Ruang tempatKuliah ruang tempat
g
FD dalam DataFD dalam DataStdSSN StdClass OfferNo OffYear EnrGrade CourseNo CrsDesc S1 JUN O1 2006 3 5 C1 DBS1 JUN O1 2006 3.5 C1 DBS1 JUN O2 2006 3.3 C2 VB S2 JUN O3 2006 3.1 C3 OO S2 JUN O2 2006 3 4 C2 VB
• Buktikan bahwa tidak ada FD dengan melihat data
S2 JUN O2 2006 3.4 C2 VB
• 2 baris yang punya nilai sama pada X tetapi berbeda pada nilai Y
Jawab dengan Lihat Data:Jawab dengan Lihat Data:‐ Berguna pd saat menjelaskan pada user‐ Ada tool yang otomatis dapat menghilangkan FD pada baris data diatasContoh:
• OfferNo ‐> StdSSN: baris kontradiksi ( 2, 4) (OfferNo sama tetapi StdSSN berbeda)• StdSSN ‐> OfferNo: baris kontradiksi (<1,2>, <3,4>)• StdSSN ‐> OffYear: data tidak memiliki kontradiksi• StdSSN ‐> OffYear: data tidak memiliki kontradiksi• tambahkan baris utk proof. kontradiksi (enroll S1 pada offering year = 2001)
Identifikasi FDIdentifikasi FD
• Easy identification (Mudah)– Adanya keunikany
– PK dan CK dihasilkan dari konversi ERD
1 M relationship: FD dari child ke parent– 1‐M relationship: FD dari child ke parent
• Difficult identification (Sulit)– LHS bukan PK atau CK dalam tabel yang dikonversi
– LHS mrpk bagian dari kombinasi PK atau CKLHS mrpk bagian dari kombinasi PK atau CK
• Buat minimalitas pada LHS (Left Hand Side)
Key dan FDKey dan FD
• Rule 1– FD memuat atribut dimana LHS‐nya adalah SKy
– R(W,X,Y,Z);FD=XY WZ, jadi XY adalah SK
Bukti :– Bukti :• XY WZ
XY XY ( fl ti )• XY XY (reflextive)
• XY XYWZ (union)
XY R• XY R
• Karena XY R, maka XY=SK
Key dan FD lanjKey dan FD lanj.
• Rule 2– Atribut secara fungsional menentukan SK tabel, g ,jadi atribut tsb adalah SK
– R(WX YZ); FD=Z W jadi Z=SKR(W,X,Y,Z); FD=Z W, jadi Z=SK
– BuktiZ W• Z W
• W WXZY (sebab W = SK), maka
( i if)• Z WXYZ (transitif)
• Z R maka Z adalah SK
TrickTrick
• If an attribute never appears on the RHS of any FD, it must be part of the keyy , p f y
• If an attribute never appears on the LHS of any FD but appears on the RHS of any FD itmustFD, but appears on the RHS of any FD, it must not be part of any key
Contoh LainContoh Lain
( ) ( ) d (( ) )??• R(ABCD), (A,B)= SK dari R ((A,B) R)??• Karena tupel ti[A,B], 1≤i≤5, adalah unikp i[ , ], ,
– t1[A,B]=(A1,B1)– t2[A,B]=(A1,B2)
A B C D
A1 B1 C1 D1t2[A,B] (A1,B2)– t3[A,B]=(A2,B2)t [A B]=(A2 B3)
A1 B2 C1 D2
A2 B2 C2 D2
A2 B3 C2 D3– t4[A,B]=(A2,B3)– t5[A,B]=(A3,B3)
k ( ) ( C ) ( )
A2 B3 C2 D3
A3 B3 C2 D4
• Maka (A,B) (A,B,C,D) atau (A,B) R, sehingga (A,B) R
Contoh LainContoh Lain
S (A B C D E F) FD A BC B D C EF BF A• S=(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,Fb bJadi A S superkey
– B D, maka BC D,C (Aug)
– C EF, maka BC BEF (Aug)
•Jadi A,BC, BF dan gabungan atributyang mengandung A,BC dan BF merupakan SuperkeyC did t K d i S d l h A BCJadi BC B,C,D,E,F (Union)
– BC A,B,C,D,E,F dan B,C A, maka B A,B,C,D,E,F
Jadi BC S merupakan Superkey
•Candidate Key dari S adalah A,BC, dan BF
– BF A dan A A,B,C,D,E,F maka BF A,B,C,D,E,F
Jadi BF S
DekomposisiDekomposisi
• Lossy (ada informasi yang hilang pada saat terjadidekomposisi)
• Lossless (tidak ada informasi yang hilang padasaat terjadi dekomposisi)saat terjadi dekomposisi)
• Manfaat FD pada dekomposisi:l– Lossless Join Decomposition
– No Redundancy
– Dependecy Preservation (Terjaminya pemeliharaanketergantungan, utk mengatasi update Anomali)
Konsep Lossles join DecompositionKonsep 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 menjadi {R1 R2} makaJika R didekomposisi menjadi {R1,R2} makadisebut Lossless join decomposition jika :
R1∩R2 R1 atau R1∩R2 R2– R1∩R2 R1 atau R1∩R2 R2
• Lossless Join decomposition didapatkan dengan :– Uji Dekomposisi : R1∪R2∪R3∪ … ∪ Rn R– Uji Lossless join : FD
Contoh Lossless join DecompositionContoh Lossless join Decomposition
( ) d k d• R(A,B,C,D,E ,F,G), dekomposisi menjadiR1(A,B,C,D,G) dan R2(B,D,E,F,H) sedang FD‐nyaadalah :– (1)B A,G ;(2) E D,H ; (3)A E,C ; (4)D F– Apakah R1 dan R2 Lossless atau Lossy ?
• Uji DekomposisiUji Dekomposisi– R1∪R2 =(A,B,C,D,G)∪(B,D,E,F,H)
=(A B C D E FG H)=(A,B,C,D,E,F,G,H)=R , YES !
Contoh Lossless join DecompositionContoh Lossless join Decomposition
Uji L l d FD• Uji Lossless dengan 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) dari (8) B A
• (5) B,D A,G,D (Aug) dan• (6) B,D B,D (Refl) shg• (7) B,D A,B,D,G (union)
(1) B A G j di
dan (11) A Cmaka (12) B C (transitif)dan (13) B,D C,D (Aug)
– (1) B A,G menjadi• (8) B A dekomposisi• (9) B G
(3) A E C j diDari (7) dan (13) uniondidapat B D A B C D G YES– (3) A E,C menjadi
• (10) A E dekomposisi• (11) A C
didapat B,D A,B,C,D,G
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)Dekomposisi Tak Hilang (data)
• Terjadi pemecahan satu relasi menjadi 2 atau lebih(dekomposisi)
D k i i t k hil tid k d i f i hil k tik• Dekomposisi tak hilang : tidak ada informasi yang hilang ketikarelasi di pecah menjadi relasi‐relasi lain
NIM Nama
95001 Budi
95002 Edi
NIM Progdi
95001 TI
95002 MI
Dekomposisi Tak Hilang
NIM Nama Progdi
95001 Budi TI
95002 Edi
95003 Budi
95002 MI
95003 TI
95002 Edi MI
95003 Budi TI
NIM Nama
95001 Budi
95002 Edi
Nama Progdi
Budi TI
Edi MI95002 Edi
95003 Budi
Edi MI
Budi TIDekomposisi 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 F (ditulis F+)disebut Closure dari F (ditulis F+).
• Jika R=(A,B,C,D), F={A B, B C,A C,C D}, maka,
A D b b A C d C D ( i if)– A D, sebab A C dan C D (transitif)
– 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 set FDMenghitung Closure dari set FD
• Mulai F+ dengan yang diberikan dari set of FD, Ulangi terus dengan memakaig gReflexivity,Augmentation,Transitivity, tambahkan turunannya (FD baru) ke F+tambahkan turunannya (FD baru) ke F+, hingga tidak ada FD baru yang dapatditurunkanditurunkan.
contohcontoh
k ik { → } | { → → }• Buktikan: { X → YZ } |= { X → Y, X → Z } yang 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) secaratrans menjadi X → Z (3).
Closure of Attributes X+Closure of Attributes X
Q A k h t F d i FD b i lik i d X→ Y?Q: Apakah set F dari FD berimplikasi pada X → Y?• Method 1: Hitung F+ & test jika X → Y makaberada dalam F+berada dalam F+.– Problem: F+ susah di hitung !
• Method 2: Hitung closure X di dalam F yang• Method 2: Hitung closure X di dalam F., yang mana merupakan set attribute yang secarafungsional ditentukan oleh X dalam F ataufungsional ditentukan oleh X dalam F, atau
X+ = { A | X → A F+ }Theorem: X→ Y F+ jika dan hanya jika Y X+Theorem: X → Y F+ jika dan hanya jika Y X+.Bukti: Use Dekom & Union.
Menghitung Closure Atribut X +Menghitung Closure Atribut X
Al ith k X +Algorithm menemukan X +
Input: F: set FD yang dipenuhi RX: set atribut dari RX: set atribut dari R
Output: X + (= xplus).Method:Method:xplus := X;while xplus berubah dowhile xplus berubah do
for tiap FD Y → Z dalam F doif Y xplus then xplus := xplus Z;if Y xplus then xplus : xplus Z;
return xplus
ContohContoh
R (A B C D E F)R=(A,B,C,D,E,F)• F: AB → C, BC → AD, D → E, CE → BHit {A B}+?• Hitung {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 k X (d i BC AD X {A B C D}3. Tambah A,D ke X (dari BC → AD; X={A,B,C,D}4. Tambah E ke X (dari D → E); X={A,B,C,D,E}5 Tid k d l i t ib t d t di t b hk k X5. Tidak ada lagi atribut yang dapat di tambahkan ke X6. {A,B}+ = {A,B,C,D,E}
ContohContoh
Compute (AG)+ dalam {A → B, CG → HI,
B→H, A→ C}B →H, A → C}
Init: xplus := AG;
iterasi1: XPlus FD Xplus Baru
AG A B ABG
ABG CG HI ABG
ABG B H ABGH
ABGH A C ABCGHABGH A C ABCGH
Xplus berubah maka, ulangi loop.
LanjutanLanjutan
l l• Iterasi 2 XPlus FD Xplus Baru
ABCGH A B ABCGH
ABCGH CG HI ABCGHIABCGH CG HI ABCGHI
ABCGHI B H ABCGHI
ABCGHI A C ABCGHI
• Iterasi 3 XPlus FD Xplus BaruIterasi 3ABCGHI A B ABCGHI
ABCGHI CG HI ABCGHI
ABCGHI B H ABCGHI
ABCGHI A C ABCGHI
(AG)+ = ABCGHI
Check Candidate KeyCheck Candidate Key
ib ik hi d i dDiberikan R yang memenuhi set F dari FD dan 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 lagiContoh lagi
Hitung closure attribute dari AB (AB+) Dengan FD :
AB → C (a) A → D (b)D → E (c)AC → B (d)
Initi closure = {AB}dengan(a) closure = {ABC}dengan(b) closure = {ABCD}
Solusi
dengan(b) closure = {ABCD}dengan(c) closure = {ABCDE}
B bagian (d) tetap di hitung tetapi karena Closure tidak berubah,B bagian (d) tetap di hitung tetapi karena Closure tidak berubah, ABCDE U B=ABCDE, dan AB adalah CK dari R(ABCDE)
• R(A, B, C, D, E, F) dan S:A→ BCE→ CFB→ EB→ E
CD→ EFHitung closure {A B}+ dari set {A B} pada SHitung closure {A, B}+ dari set {A, B} pada S.
Contoh LagiContoh Lagi
• R( A, B, C, D, E ) F={AB→C,BC→AD,D→E,CF→B}, Hitung{ → , → , → , → }, gClosure {A, B}+ dari {A, B} di bawah S.
①①{A,B}{A,B}+ + = {A,B}= {A,B}②② AB→CAB→C {A,B}{A,B}+ + = {A,B,C}= {A,B,C}③③ BC→ADBC→AD {A,B}{A,B}+ + = {A,B,C,D}= {A,B,C,D}{ , }{ , } { , , , }{ , , , }④④ D→ED→E {A,B}{A,B}+ + = {A,B,C,D,E}= {A,B,C,D,E}⑤⑤ {{A,BA,B}}+ + == {A,B,C,D,E}{A,B,C,D,E}⑤⑤ {{A,BA,B}} {A,B,C,D,E}{A,B,C,D,E}
Contoh lagiContoh lagi• R = {A, B, C, D, E}• F = { B →CD, D → E, B → A, E → C, AD →B }
• Is AD a key for R? AD+ = AD
{ , , , , }• Is B → E in F+ ?
B+ = BAD+ = ABD dan B = key Yes!
• Is AD a candidate key B+ = BCDB+ = BCDA
! dfor R?A+ = A
B+ = BCDAE … Yes! danB = key bagi R !
• Is D a key for R?… A not a key, so Yes!
• Is ADE a candidate key
Is D a key for R?D+ = DD+ = DE
for R?… No! AD is a key, so ADE is a
k b t t d k
D+ = DEC … bukan!
superkey, but not a cand. key
Dependency Preservation (DP)Dependency Preservation (DP)
d l h k l d d• R adalah skema relasi, dimana R didekomposisi menjadi R1,R2,R3,…,Rn danF1,F2,F3,…,Fn adalah himpunan FD yang berlaku untuk R, maka dekomposisi tersbutdikatakan memenuhi DP jika :– (F1∪F2 ∪F3∪… ∪Fn)+=F+
• DP merupakan kriteria penjamin keutuhanrelasi, ketika suatu relasi di dekomposisi, jadirelasi, ketika suatu relasi di dekomposisi, jadidapat menghindari anomali dan inkonsistensi
Dependecy Preservation ContohDependecy Preservation Contoh
• R=(A,B,C) dan FD:A B, B C didekomposisikanmenjadi 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 Cmaka BB BC atau B C (Aug)
– Jadi dekomposisi‐nya lossless join
Dependecy Preservation lanjDependecy 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 padaR1R1
– R2=(B,C), F2={B C}, krn hanya B C yg berlaku padaR2R2
– F1∪F2={A B, B C}, krn A B dan B C maka A CS hi (F1∪F2)+ {A B B C A C} F+– Sehingga (F1∪F2)+={A B, B C,A C}=F+
– Jadi memenuhi DP
Relationships of Normal FormsRelationships of Normal Forms1NF2NF2NF
3NF/BCNF
4NF
5NF
DKNF
1NF ti t bl b d d 1NF1NF: tip table berada pada 1NF2NF: tiap tabel dalam 2NF juga dalam 1NF3NF/BCNF: BCNF adalah edisi revisi dari 3NF, 4NF: Mengurangi penggunaan M‐way relationship;Relationship independence and MVDs; does not involve FDs5NF tidak melibatkan FD Inappropriate sage of an M a relationship more speciali ed than 4NF5NF: tidak melibatkan FD; Inappropriate usage of an M‐way relationship; more specialized than 4NFDKNF: bentuk ideal secara teori
top related