Basis Data (Database)dinus.ac.id/repository/docs/ajar/sbd-bab5-2018_revisi.pdf · Database System...
Transcript of Basis Data (Database)dinus.ac.id/repository/docs/ajar/sbd-bab5-2018_revisi.pdf · Database System...
©Silberschatz, Korth and Sudarshan 1.1 Database System Concepts
Basis Data (Database)
Tujuan Instruksional Umum :
Mahasiswa mampu merancang Basis Data yang baik sesuai
Kaidah-kaidah perancangan Basis Data yang benar
dan mengimplemntasikan dengan SQL.
(3 SKS)
©Silberschatz, Korth and Sudarshan 1.2 Database System Concepts
Functional Dependency
And
Normalization
©Silberschatz, Korth and Sudarshan 1.3 Database System Concepts
title year length filmType studioName starName
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Estevez
Wayne’s World 1992 95 color Paramount Dana Carvey
Wayne’s World 1992 95 color Paramount Mike Meyers
Tabel : Film
motivasi
What your comment ………..
Is a “good” design .. ??
©Silberschatz, Korth and Sudarshan 1.4 Database System Concepts
title year length filmType studioName starName
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Estevez
Wayne’s World 1992 95 color Paramount Dana Carvey
Wayne’s World 1992 95 color Paramount Mike Meyers
Redundancy Informasi diulang-ulang
dalam beberapa tupel
125
Update Anomaly Update informasi pada
satu tupel tidak
mengubah pada tupel
yang lain
motivasi
Tabel : Film
©Silberschatz, Korth and Sudarshan 1.5 Database System Concepts
title year length filmType studioName starName
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Estevez
Wayne’s World 1992 95 color Paramount Dana Carvey
Wayne’s World 1992 95 color Paramount Mike Meyers
Tabel : Film
motivasi
Delete Anomaly Jika Emilio Estavez dihapus,
akan kehilangan informasi
tentang Mighty Ducks
©Silberschatz, Korth and Sudarshan 1.6 Database System Concepts
Star Wars 1977 124 Color MGM James Earl Jones
Tabel : Film
motivasi
Insertion Anomaly Jika kita sisipkan tupel baru
(Star Wars, 177, 124, color, MGM, James Earl Jones)
maka akan terjadi inkonsistensi pada atribut studio
title year length filmType studioName starName
Star Wars 1977 124 color Fox Carrie Fisher
Star Wars 1977 124 color Fox Mark Hamill
Star Wars 1977 124 color Fox Harrison Ford
Mighty Ducks 1991 104 color Disney Emilio Estevez
Wayne’s World 1992 95 color Paramount Dana Carvey
Wayne’s World 1992 95 color Paramount Mike Meyers
©Silberschatz, Korth and Sudarshan 1.7 Database System Concepts
Masalah Anomali :
Redundancy: Pengulangan informasi dalam beberapa tupel yang sebenarnya tidak diperlukan.
Update anomalies: Pengubahan informasi dalam satu tupel yang tidak kompak (inkonsistensi).
Deletion anomalies: Kehilangan informasi akibat penghapusan informasi.
Insertion anomalies: Penambahan tupel baru yang tidak konsisten.
motivasi
©Silberschatz, Korth and Sudarshan 1.8 Database System Concepts
Integrity - redundansi - ambiguitas Performance - kecepatan akses - efisiensi storage Maintainability - update - delete - insert
Problems With :
Tabel Database yang baik (Good Design) : Mampu merepresentasikan informasi. Jika ada dekomposisi maka dekomposisinya adalah aman (Lossless, not Lossy) Terpeliharanya ketergantungan fungsional Mempunyai skema relasi yang baik, kemudahan update data tanpa anomali (Dependency Preservation) Tidak terjadi pengulangan data - Tidak melanggar Boyce Codd Normal Form (BCNF) - Jika tidak dapat diupayakan memenuhi BCNF, maka minimal memenuhi bentuk 3NF (No Redundancy, anything say once)
Goals :
motivasi
©Silberschatz, Korth and Sudarshan 1.9 Database System Concepts
Teori Dasar :
Dekomposisi Relasi
Key
Ketergantungan Fungsional
we discuss before …
©Silberschatz, Korth and Sudarshan 1.10 Database System Concepts
dekomposisi relasi
Diketahui skema relasi R. Gugus relasi {R1, R2, ,…, Rn} disebut Dekomposisi dari R jika :
Dekomposisi : memecah relasi/tabel menjadi relasi/tabel yang lebih kecil untuk mendapatkan skema yang tidak mengandung anomali dan redundansi
R1 R2 … Rn = R
Artinya {R1, R2, …, Rn} dekomposisi dari R jika setiap atribut dalam R muncul paling sedikit di salah satu Ri untuk 1 i n
©Silberschatz, Korth and Sudarshan 1.11 Database System Concepts
idfilm title year length filmType
F001 Star Wars 1977 124 color
F002 Mighty Ducks 1991 104 color
F003 Wayne’s World 1992 95 color
idstudio studioName
STD01 Fox
STD02 Disney
STD03 Paramount
idstar starName
STR01 Carrie Fisher
STR02 Mark Hamill
STR03 Harrison Ford
STR04 Emilio Estevez
STR05 Dana Carvey
STR06 Mike Meyers
idfilm title year length filmType idstudio studioName idstar starName
F001 Star Wars 1977 124 color STD01 Fox STR01 Carrie Fisher
F001 Star Wars 1977 124 color STD01 Fox STR02 Mark Hamill
F001 Star Wars 1977 124 color STD01 Fox STR03 Harrison Ford
F002 Mighty Ducks 1991 104 color STD02 Disney STR04 Emilio Estevez
F003 Wayne’s World 1992 95 color STD03 Paramount STR05 Dana Carvey
F003 Wayne’s World 1992 95 color STD03 Paramount STR06 Mike Meyers
DaftarFilm StudioFilm BintangFilm
Film original
Decomposition result
dekomposisi relasi
©Silberschatz, Korth and Sudarshan 1.12 Database System Concepts
dekomposisi relasi
Lossless Join digunakan untuk menjamin keutuhan data untuk operasi gabungan (join) dan merupakan fokus dalam desain basis
data relasional
Dekomposisi relasi R menjadi gugus relasi {R1, R2, …, Rn} yang tidak menyebabkan hilangnya informasi disebut Lossless-Join Decomposition.
Jadi, jika r R dan ri = Ri(R) dimana 1 i n maka akan
selalu memenuhi kondisi berikut :
i
n
ii
n
irrataurr
11
i
n
irr
1
atau
Dekomposisi relasi R menjadi gugus relasi {R1, R2, …, Rn} yang menyebabkan hilangnya informasi disebut Lossy-Join Decomposition.
©Silberschatz, Korth and Sudarshan 1.13 Database System Concepts
Film = (idfilm, title, year, length, filmType, idstudio, studioName, idstar, starName)
there is Anomaly !! Decompose it ……
idfilm title year length filmType idstudio studioName idstar starName
F001 Star Wars 1977 124 color STD01 Fox STR01 Carrie Fisher
F001 Star Wars 1977 124 color STD01 Fox STR02 Mark Hamill
F001 Star Wars 1977 124 color STD01 Fox STR03 Harrison Ford
F002 Mighty Ducks 1991 104 color STD02 Disney STR04 Emilio Estevez
F003 Wayne’s World 1992 95 color STD03 Paramount STR05 Dana Carvey
F003 Wayne’s World 1992 95 color STD03 Paramount STR06 Mike Meyers
dekomposisi relasi
Oopss !!!
©Silberschatz, Korth and Sudarshan 1.14 Database System Concepts
idfilm title year length filmType
F001 Star Wars 1977 124 color
F002 Mighty Ducks 1991 104 color
F003 Wayne’s World 1992 95 color
idstudio studioName
STD01 Fox
STD02 Disney
STD03 Paramount
idstar starName
STR01 Carrie Fisher
STR02 Mark Hamill
STR03 Harrison Ford
STR04 Emilio Estevez
STR05 Dana Carvey
STR06 Mike Meyers
idfilm title year length filmType idstudio studioName idstar starName
F001 Star Wars 1977 124 color STD01 Fox STR01 Carrie Fisher
F001 Star Wars 1977 124 color STD01 Fox STR02 Mark Hamill
F001 Star Wars 1977 124 color STD01 Fox STR03 Harrison Ford
F002 Mighty Ducks 1991 104 color STD02 Disney STR04 Emilio Estevez
F003 Wayne’s World 1992 95 color STD03 Paramount STR05 Dana Carvey
F003 Wayne’s World 1992 95 color STD03 Paramount STR06 Mike Meyers
dekomposisi relasi
Lossless or
Lossy ?
DaftarFilm StudioFilm BintangFilm
Film
Andaikan di dekomposisi Menjadi 3 tabel tsb ….
©Silberschatz, Korth and Sudarshan 1.15 Database System Concepts
“Di studio manakah Star Wars dibuat ?”
Karena kita harus melakukan operasi gabungan terlebih dahulu dari Ke-2 tabel. Misal kita lakukan operasi “cross product” antara Daftar_Film dan StudioFilm.
Pasti kita akan membutuhkan tabel DaftarFilm dan StudioFilm.
Dengan ke-3 tabel hasil dekomposisi, misal ditanyakan informasi :
Tapi dapatkah diperoleh informasi yang kita inginkan dari kedua skema relasi tersebut ?
Tampaknya : TIDAK.
dekomposisi relasi
DaftarFilm StudioFilm
©Silberschatz, Korth and Sudarshan 1.16 Database System Concepts
idfilm title year length filmType idstudio studioName
F001 Star Wars 1977 124 color STD01 Fox
F001 Star Wars 1977 124 color STD02 Disney
F001 Star Wars 1977 124 color STD03 Paramount
F002 Mighty Ducks 1991 104 color STD01 Fox
F002 Mighty Ducks 1991 104 color STD02 Disney
F002 Mighty Ducks 1991 104 color STD03 Paramount
F003 Wayne’s World 1992 95 color STD01 Fox
F003 Wayne’s World 1992 95 color STD02 Disney
F003 Wayne’s World 1992 95 color STD03 Paramount
Ternyata kita tidak mendapatkan informasi yang dibutuhkan, karena film Star Wars dibuat oleh 3 studio (Fox, Disney, Paramount)
dekomposisi relasi Kehilangan Informasi !!
DaftarFilm StudioFilm
LOSSY DECOMPOSITION
©Silberschatz, Korth and Sudarshan 1.17 Database System Concepts
Functional Dependencies (FD) / Ketergantungan Fungsional (KF) digunakan untuk menggambarkan atau mendeskripsikan bentuk normal atas suatu relasi
functional dependencies (FD)
FD adalah batasan terhadap gugus relasi yang berlaku. Diperoleh berdasarkan hubungan antar atribut data.
Kegunaan FD : 1. Untuk memeriksa keabsahan apakah semua relasi sesuai dengan ketergantungan fungsional yang diberikan 2. Untuk menetapkan batasan gugus relasi yang berlaku 3. Untuk menentukan kunci relasi 4. Untuk melakukan normalisasi atas suatu tabel relasional
©Silberschatz, Korth and Sudarshan 1.18 Database System Concepts
Misalkan R adalah suatu skema relasional, atribut x R dan y R
maka x dikatakan secara fungsional menentukan y
(atau y bergantung secara fungsional pada x), ditulis x y pada R, jika :
1. Semua tupel ti [x], 1 i n adalah unik/tunggal
2. Semua pasangan tupel dimana ti [x] = tj [x], i j, terjadi juga ti [y] = tj [y]
dengan kata lain :
Untuk setiap nilai x terdapat hanya satu nilai y (x menentukan secara tunggal
nilai y). Jadi apabila terdapat 2 tuple t1 dan t2 mempunyai nilai atribut x yang
sama, maka juga akan mempunyai nilai atribut y yang sama.
t1[x] = t2 [x] t1[y] = t2 [y] pada skema relasi R
functional dependencies (FD)
definisi
©Silberschatz, Korth and Sudarshan 1.19 Database System Concepts
R = (A, B, C)
A B
1 4
1 5
2 7
A B ?
t1(A)=t2(A), tetapi t1(B) t2(B)
A B C D
A1 B1 C1 D1
A1 B2 C1 D2
A2 B2 C2 D2
A2 B3 C2 D3
A3 B3 C2 D4
R = (A,B,C,D)
A C ? C A ? (A,B) C ? (A,B) D ?
C
C1
C1
C2
Maka A B
A C ?
t1(A)=t2(A) dan t1(C) = t2(C)
Maka A C
functional dependencies (FD) contoh
Yes
No Yes Yes
©Silberschatz, Korth and Sudarshan 1.20 Database System Concepts
functional dependencies (FD)
©Silberschatz, Korth and Sudarshan 1.21 Database System Concepts
Film = (idfilm, title, year, length, filmType, idstudio, studioName, idstar, starName)
idfilm title year length filmType idstudio studioName idstar starName
F001 Star Wars 1977 124 color STD01 Fox STR01 Carrie Fisher
F001 Star Wars 1977 124 color STD01 Fox STR02 Mark Hamill
F001 Star Wars 1977 124 color STD01 Fox STR03 Harrison Ford
F002 Mighty Ducks 1991 104 color STD02 Disney STR04 Emilio Estevez
F003 Wayne’s World 1992 95 color STD03 Paramount STR05 Dana Carvey
F003 Wayne’s World 1992 95 color STD03 Paramount STR06 Mike Meyers
F004 My Hearts 1992 101 color STD04 MGM STR01 Carrie Fisher
F004 My Hearts 1992 101 color STD04 MGM STR02 Harrison Ford
functional dependencies (FD) contoh
©Silberschatz, Korth and Sudarshan 1.22 Database System Concepts
FD dirumuskan berdasarkan batasan dari dunia nyata suatu atribut. Contoh : - Nomor Induk mahasiswa menentukan NamaMahasiswa NIM NamaMhs - Kode Matakuliah menentukan Nama Mata Kuliah dan SKS KodeMK (NamaMK, SKS) - NIM dan Kode Mata Kuliah menentukan Nilai Matakuliah (NIM,KodeMK) NilaiMK
Suatu FD : x y disebut trivial jika y x
functional dependencies (FD)
Contoh :
X X X,Y X X,Y Y
X,Y,Z X,Z X,Y,Z Z X,Y,Z X,Y,Z
©Silberschatz, Korth and Sudarshan 1.23 Database System Concepts
functional dependencies (FD) Armstrong’s Rule
A1. Reflexive Jika y x maka x y A2. Augmentation Jika x y maka (x,z) (y,z) A3. Transitive Jika x y dan y z maka x z A4. Decomposition Jika x (y,z) maka x y dan x z A5. Union Jika x y dan x z maka x (y,z) A6. Pseudotranstivity Jika x y dan (z,y) w maka (x,z) w
Diketahui x y Dari A2 (x,z) (y,z) Diketahui (z,y) w Dari A3 (x,z) w
©Silberschatz, Korth and Sudarshan 1.24 Database System Concepts
Manfaat FD pada dekomposisi
Untuk : 1. Lossless Join Decomposition Mendapatkan dekomposisi yang tidak kehilangan data/informasi 2. No Redundancy Mendapatkkan skema relasi yang tidak mengandung redundansi 3. Dependency Preservation Terjaminnya pemeliharaan ketergantungan sehingga dapat mengatasi masalah update anomali
©Silberschatz, Korth and Sudarshan 1.25 Database System Concepts
uji lossless-join decomposition
Misal diketahui skema relasi R didekomposisi menjadi gugus relasi {R1, R2, R3, R4, …, Rn}, maka dekomposisi ini disebut Lossless Join Decomposition jika kondisi R1 R2 R3 … Rn Ri dipenuhi sekurang-kurangnya untuk 1 nilai i, dimana 1 i n.
Dengan kata lain, jika diketahui skema relasi R didekomposisi menjadi gugus relasi {R1, R2}, maka dekomposisi ini disebut Lossless Join Decomposition jika dipenuhi salah satu kondisi : R1 R2 R1 atau R1 R2 R2
Langkah-2 Uji Lossless-joint Decomposition : 1. Uji Dekomposisi
R1 R2 … Rn = R
2. Uji Lossless-join Menggunakan sifat ketergantungan fungsional
©Silberschatz, Korth and Sudarshan 1.26 Database System Concepts
uji lossless-join decomposition contoh
Diketahui skema relasi R=(A,B,C,D,E,F,G,H) didekomposisi menjadi : R1=(A,B,C,D,G) dan R2=(B,D,E,F,H). FD pada R yang berlaku adalah : (1) B A,G (2) E D,H (3) A E,C (4) D F Ujilah apakah dekomposisi {R1,R2} tersebut lossless atau lossy ?
1. Uji Dekomposisi
R1 R2 = (A,B,C,D,G) (B,D,E,F,H) = (A,B,C,D,E,F,G,H) = R
.:. Terbukti bahwa {R1,R2} adalah dekomposisi dari R.
©Silberschatz, Korth and Sudarshan 1.27 Database System Concepts
uji lossless-joint decomposition contoh
2. Uji Lossless
Dari (1) B A,G maka : (5) B,D A,G,D (augmentasi) (6) B,D B,D (refleksif) Jadi (7) B,D A,B,D,G (1) B A,G maka (8) B A dan (9) B G Dari (3) A E,C maka (10) A E dan (11) A C maka :
R1 R2 = (A,B,C,D,G) (B,D,E,F,H) = (B,D) Akan dibuktikan bahwa paling sedikit satu kondisi berikut dipenuhi :
R1 R2 R1 ; (B,D) (A,B,C,D,G) atau R1 R2 R2 ; (B,D) (B,D,E,F,H)
Dari (8) B A dan (11) A C Maka (12) B C (transitif) Dan (13) B,D C,D (augmentasi) Dari (7) dan (13) didapat : B,D A,B,C,D,G
terbukti {R1,R2} Lossless
Dari contoh di atas, tunjukkan pula bahwa (B,D) (B,D,E,F,H)
©Silberschatz, Korth and Sudarshan 1.28 Database System Concepts
Dependency preservation
Dependency preservation (dapat di Indonesia-kan sebagai Pemeliharaan Ketergantungan) merupakan kriteria yang harus dicapai untuk mendapatkan tabel dan basis data yang baik.
Dependency Preservation (Pemeliharaan Ketergantungan) merupakan kriteria yang menjamin keutuhan relasi ketika suatu relasi didekomposisi menjadi beberapa tabel. Sehingga diharapkan tidak terjadi inkonsistensi atau anomali ketika dilakukan update data.
©Silberschatz, Korth and Sudarshan 1.29 Database System Concepts
uji dependency preservation
Misal skema relasi R dengan himpunan ketergantungan fungsional F didekomposisi menjadi R1,R2,R3,…,Rn. Dan F1,F2,F3,…,Fn adalah himpunan ketergantungan fungsional yang berlaku di R1,R2,R3,…,Rn maka dekomposisi tersebut dikatakan memenuhi sifat Dependency Preservation apabila berlaku :
(F1 F2 F3 … Fn)+ = F+
©Silberschatz, Korth and Sudarshan 1.30 Database System Concepts
Armstrong’s rule dapat dimanfaatkan untuk menentukan F+
functional dependencies (FD) Closure FD (F+)
Misal F adalah gugus ketergantungan fungsional pada skema relasi R, maka semua FD yang mungkin dapat diturunkan dari F dengan
hukum-hukum FD disebut : Closure dari F, ditulis F+.
Contoh : Diketahui R = (A, B, C, D) F = { A B, B C, A C, C D} maka : A D sebab A C dan C D, dari sifat transitif (A3) didapat A D B D sebab B C dan C D, dari sifat transitif (A3) didapat B D Sehingga {A B, B C, A C, C D, A D, B D} F+.
Kita dapat menurunkan anggota-anggota F+ yang lain berdasarkan FD yang diketahui menggunakan Armstong’s rule.
Closure FD (F+) berguna untuk Uji Dependency Preservation
©Silberschatz, Korth and Sudarshan 1.31 Database System Concepts
uji dependency preservation
Contoh : Diketahui skema relasi R=(A,B,C) dengan FD : A B ; B C Didekomposisi menjadi R1=(A,B) dan R2=(B,C) a. Apakah dekomposisi tsb Lossless-Joint ? b. Apakah dekomposisi tsb memenuhi Dependency Preservation ?
a. R1 R2 = (A,B) (B,C) = (A,B,C) = R R1 R2 = (A,B) (B,C) = B Lossless jika B (A,B) atau B (B,C). Karena diketahui B C maka BB BC atau B BC (Augmentasi). Jadi dekomposisi tsb Lossless.
©Silberschatz, Korth and Sudarshan 1.32 Database System Concepts
b. R=(A,B,C) dan F = {AB, BC}. Karena AB dan BC maka AC. Maka dapat dibentuk closure F+={AB, BC,AC}. R1=(A,B) dan F1={AB}. Karena hanya AB yang berlaku di R1. R2=(B,C) dan F2={BC}. Karena hanya BC yang berlaku di R2. F1 F2 = {AB,BC}. Karena AB dan BC maka AC. Sehingga (F1 F2 )+={AB,BC,AC}=F+
Jadi dekomposisi tsb memenuhi Dependency Preservation.
Ujilah dekomposisinya apakah Lossless dan Dependency Preservation Apabila R di atas didekoposisi menjadi R1=(A,B) dan R2=(A,C). Bagaimana bila R1=(A,B) dan R2=(B,C) tetapi FD : BC, ACB
uji dependency preservation
©Silberschatz, Korth and Sudarshan 1.33 Database System Concepts
Ujilah dekomposisi dari skema relasi R, apakah lossless atau lossy ? 1. R = (A,B,C,D,E,F,G,H) didekomposisi menjadi : R1 = (A,B,C,D,E) dan R2 = (C,D,F,G,H) dengan FD : C (A,B,D) ; F (G,H) ; D (E,F) 2. R = (A,B,C,D,E) didekomposisi menjadi : R1 = (A,B,C,D) dan R2 = (C,D,E) dengan FD : A B ; (C,D) E ; B D ; E A 3. R = (X,Y,Z,W,U,V) didekomposisi menjadi : R1 = (X,Y,Z,W) dan R2 = (W,U,V) dengan FD : W X ; X Z 4. R = (A,B,C,D,E,F) didekomposisi menjadi : R1 = (A,B,C), R2 = (A,D,F) dan R3 = (E,D) dengan FD : A (B,C) ; D (F,A) Uji pula dependency preservation nya untuk masing-masing soal tsb.
soal latihan
©Silberschatz, Korth and Sudarshan 1.34 Database System Concepts
KEYS
©Silberschatz, Korth and Sudarshan 1.35 Database System Concepts
atribut kunci (key)
Kunci (key) adalah kolom/atribut atau kombinasi kolom/atribut yang dapat digunakan untuk mengidentifikasi baris dalam tabel (entitas) secara unik. Penentuan Key suatu tabel didasarkan pada sifat “determinasi”. Determinan : gugus atribut dimana satu atau lebih atribut lain tergantung secara fungsional. “A determinan B” artinya apabila nilai atribut A akan menentukan nilai-nilai atribut B. “A determinan B” dapat dituliskan sebagai suatu ketergantungan fungsional A B. Jika A menentukan B,C dan D maka dituliskan A B,C,D. Contoh : Relasi Mahasiswa=(NIM,Nama,Agama,TglLhr) Bila nilai NIM seorang mahasiswa diketahui maka dapat digunakan untuk melihat nilai-nilai atribut Nama, Agama dan Tanggal Lahirnya. Dituliskan NIM Nama,Agama,TglLhr
©Silberschatz, Korth and Sudarshan 1.36 Database System Concepts
superkey
Superkey (key) : - gugus atribut entitas yang dapat digunakan untuk mengidentifikasikan entitas/obyek secara unik. - satu atau lebih atribut yang membedakan setiap baris secara unik. Misal R skema relasi, dan K adalah satu atau lebih atribut dari R dimana K R maka K disebut Superkey jika dan hanya jika K R. Catatan : Suatu skema relasi dapat memiliki lebih dari 1 superkey. Bila K adalah superkey maka semua atribut gabungan yang mengandung K juga merupakan superkey
Contoh : Relasi Sopir=(NoKTP,NoSIM,Nama,Alamat). Alternatif superkey : NoKTP superkey ; NoKTP Sopir NoSIM superkey ; NoSIM Sopir (NoKTP,NoSIM) superkey ; (NoKTP,NoSIM) Sopir (NoKTP,Nama) superkey ; (NoKTP,Nama) Sopir (NoKTP,NoSIM,Nama) superkey ; (NoSKTP,NoSIM,Nama) Sopir (NoKTP,NoSIM,Nama,Alamat) dengan sendirinya juga superkey Nama bukan superkey. Demikian juga (Nama,Alamat) juga bukan superkey
©Silberschatz, Korth and Sudarshan 1.37 Database System Concepts
Candidate Key : - Superkey dengan jumlah atribut minimal - Superkey tanpa redundansi (tidak memuat subset superkey yang lain) K adalah Candidate Key dari skema relasi R jika dan hanya jika : K R dan tidak terdapat K dengan R
Contoh : Skema relasi Sopir=(NoKTP,NoSIM,Nama,Alamat). Alternatif superkey : NoKTP superkey ; NoKTP Sopir NoSIM superkey ; NoSIM Sopir (NoKTP,NoSIM) superkey ; (NoKTP,NoSIM) Sopir (NoKTP,Nama) superkey ; (NoKTP,Nama) Sopir (NoKTP,NoSIM,Nama) superkey ; (NoSKTP,NoSIM,Nama) Sopir (NoKTP,NoSIM,Nama,Alamat) dengan sendirinya juga superkey Sebagai Candidate Key nya adalah NoKTP atau NoSIM
candidate key
©Silberschatz, Korth and Sudarshan 1.38 Database System Concepts
Primary Key adalah candidate key yang dipilih untuk digunakan sebagai kunci identitas tabel secara unik (kunci indeks tabel) dan tidak boleh bernilai NULL. Dasar pemilihan Candidate Key sebagai Primary Key : Key tsb menjamin keunikan baris data Key tsb bersifat natural atau universal (lazim dipakai sebagai acuan) Key tsb mudah dan ringkas untuk dipakai sebagai acuan
Contoh : Skema relasi Sopir=(NoKTP,NoSIM,Nama,Alamat). Alternatif superkey : NoKTP superkey ; NoKTP Sopir NoSIM superkey ; NoSIM Sopir (NoKTP,NoSIM) superkey ; (NoKTP,NoSIM) Sopir (NoKTP,Nama) superkey ; (NoKTP,Nama) Sopir (NoKTP,NoSIM,Nama) superkey ; (NoSKTP,NoSIM,Nama) Sopir (NoKTP,NoSIM,Nama,Alamat) dengan sendirinya juga superkey Sebagai Candidate Key nya adalah NoKTP atau NoSIM Maka NoSIM lebih baik dipilih sebagai Primary Key untuk skema relasi Sopir
primary key
©Silberschatz, Korth and Sudarshan 1.39 Database System Concepts
Secondary Key adalah atribut (atau kombinasinya), yang digunakan sebagai perantara untuk mendapatkan kembali data asal. Biasanya dipakai pada pencarian data (data retrieval).
Contoh : Skema relasi Sopir=(NoKTP,NoSIM,Nama,Alamat) dengan NoSIM sebagai Primary Key. Walaupun atribut ini lazim dipakai sebagai identitas seorang Sopir, tapi apakah seorang sopir dijamin hapal nomor SIM nya ketika misalnya ada transaksi yang berkaitan dengan penggunaan identitas No SIM ?. Untuk memudahkan proses pencarian data sopir tersebut maka dapat digunakan atribut lain yang lebih mudah diingat misalnya “nama” dan/atau “alamat”. Penggunaan secondary key ini tentu saja tidak menjamin ditemukannya data uang unik, karena memang tidak ditujukan untuk kepentingan keunikan data. Tetapi sebagai alternatif atau fasilitas untuk membantu mengidentifikasi data. Analogikan ketika kita lupa akan ID atau password account email kita. Fasilitas apa yang bisa kita manfaatkan ?
secondary key
©Silberschatz, Korth and Sudarshan 1.40 Database System Concepts
Foreign Key adalah satu atau lebih atribut dalam satu tabel yang merupakan primary key tabel lain (kunci penghubung).
IDSls NmSls AlamatAsal KotaAsal
S001 Anita Jl. Nakula 9 Kendal
S002 Vicky Jl. Arjuna I/6 Semarang
S003 Roni Jl. Bima II/3 Semarang
IDProd NamaProduk Harga QtyStock
F001 TV 14” 1500000 12
F002 TV 21” 2100.000 4
F003 TV 21” Flatron 2700000 24
Sales
Produk
NoOrder Date IDProd QtyOrder IDSls
120301 12/11/04 P001 2 S001
120302 13/11/04 P001 2 S003
120303 22/11/04 P003 6 S001
Order
Tabel Name : Produk Primary key : IDProd Foreign Key : -
Tabel Name : Order Primary key : NoOrder Foreign Key : IDProd,IDSls
Tabel Name : Sales Primary key : IDSls Foreign Key : -
foreign key
link link
©Silberschatz, Korth and Sudarshan 1.41 Database System Concepts
hubungan FD dengan key
Amstrong’s rule dapat digunakan untuk menurunkan superkey tabel, berdasarkan 1 atau lebih superkey yang diketahui
Rule 1 : Apabila diketahui FD yang memuat semua atribut pada tabel, maka atribut-atribut yang terdapat pada ruas kiri dari FD adalah superkey Contoh : Diketahui tabel R = (W,X,Y,Z) dan FD : XY WZ maka XY superkey Sebab : XY WZ maka XY XY (refleksif) XY XYWZ (union) XY R Karena XY R maka XY superkey. Jadi ruas kiri dari FD merupakan superkey.
©Silberschatz, Korth and Sudarshan 1.42 Database System Concepts
Rule 2 : Atribut yang secara fungsional menentukan superkey dari tabel maka atribut tersebut juga merupakan superkey Contoh : Diketahui W superkey dari tabel R = (W,X,Y,Z) dan FD : Z W maka Z superkey Sebab : Z W dan W WXYZ (karena W superkey), maka Z WXYZ (transitif) Z R Karena Z R maka Z superkey
hubungan FD dengan key
©Silberschatz, Korth and Sudarshan 1.43 Database System Concepts
A B C D
A1 B1 C1 D1
A1 B2 C1 D2
A2 B2 C2 D2
A2 B3 C2 D3
A3 B3 C2 D4
R = (A,B,C,D) Apakah (A,B) superkey dari R ?
Akan dibuktikan apakah (A,B) R. Jika Ya maka (A,B) superkey dari R.
Karena semua tupel ti[A,B] untuk 1 i 5
adalah unik, t1[A,B]=(A1,B1) t2[A,B]=(A1,B2) t3[A,B]=(A2,B2) t4[A,B]=(A2,B3) t5[A,B]=(A3,B3) Maka (A,B) (A,B,C,D) atau (A,B) R Jadi (A,B) superkey dari R
Apakah A superkey dari R ? Bukan, sebab A R. Mengapa ?
hubungan FD dengan key
©Silberschatz, Korth and Sudarshan 1.44 Database System Concepts
hubungan FD dengan key
Diketahui S = (A,B,C,D,E,F) dan FD : A BC ; B D ; C EF ; BF A Carilah superkey dan candidate key dari S menggunakan FD
A BC A B A C karena A B dan B D maka A D karena A C dan C EF maka A EF A A Sehingga A ABCDEF atau A S (superkey)
BF A A ABCDEF maka BF ABCDEF BF S (superkey)
Superkey dari S A, BF serta gabungan atribut yang mengandung A, BF, AB, …… Candidate key dari S A
Tips !! Fokuskan
perhatian Anda pada atribut-2 di ruas kiri dari FD untuk mencari
superkey
©Silberschatz, Korth and Sudarshan 1.45 Database System Concepts
Latihan : 1. Diberikan R(A,B,C,D) dengan FD : AB,AC dan AD Apakah A candidate key dari R ? 2. Diberikan R(A,B,C,D) dengan FD : AB a. Apakah ACD superkey dari R b. Apakah A candidate key dari R 3. Diberikan R(A,B,C,D,E,F) dengan FD : C(AB);B(DE);EF;ABC a. Carilah superkey dari R b. Carilah candidate key dari R 4. Diberikan R(A,B,C,D,E) dengan FD : A(BC);(CD)E;BD;EA a. Carilah superkey dari R b. Carilah candidate key dari R 5. Diberikan R(A,B,C) dengan FD : AB;BC;CA Apakah A merupakan satu-satunya candidate key dari R
hubungan FD dengan key
©Silberschatz, Korth and Sudarshan 1.46 Database System Concepts
No_fak Tgl_faktur Nm_kons Almt_kons Kota_kons Kode_brg Nama_brg Jml Hrg_sat bayar
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1101 Sandal 10 15000 150000
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1110 Sepatu 7 100000 700000
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1112 Kaos 15 30000 450000
102 11-01-08 Rudi Jl. Seroja Raya 1 Solo 1101 Sandal 20 15000 300000
102 11-01-08 Rudi Jl. Seroja Raya 1 Solo 1113 Jaket 4 200000 800000
Perhatikan Tabel berikut :
a b c d e f g h I j
©Silberschatz, Korth and Sudarshan 1.47 Database System Concepts
End Session Today Tomorrow We’ll Discuss About
Normalization ……
©Silberschatz, Korth and Sudarshan 1.48 Database System Concepts
Normalization
©Silberschatz, Korth and Sudarshan 1.49 Database System Concepts
normalisasi
Normalisasi : Teknik/pendekatan yang digunakan dalam membangun
disain lojik database relasional melalui organisasi himpunan data dengan
tingkat ketergantungan fungsional dan keterkaitan yang tinggi sedemikian
sehingga menghasilkan struktur tabel yang normal.
Tujuan : Minimalisasi redundansi (pengulangan data) Memudahkan identifikasi entitas Mencegah terjadinya anomali
Beberapa bentuk normal (normal forms, NF) : 1NF, 2NF, 3NF, BCNF based on keys and functional dependencies 4NF, 5NF based on keys and multi-valued dependencies)
©Silberschatz, Korth and Sudarshan 1.50 Database System Concepts
Suatu relasi disebut memenuhi bentuk normal pertama (1NF) jika dan hanya jika setiap atribut dari relasi tersebut hanya memiliki nilai tunggal dan tidak ada pengulangan grup atribut dalam baris. Bentuk 1NF tidak boleh mengandung grup atribut yang berulang. Tujuan membentuk 1NF : ::. semantik tabel menjadi lebih eksplisit (say anything once). ::. semua operator aljabar relasional dapat diaplikasikan pada tabel.
First Normal Form (1NF)
©Silberschatz, Korth and Sudarshan 1.51 Database System Concepts
IDSales NamaSales Telepon
ADN006 Yeni, SE 3517261, 3520165
ADN007 Memey 4744621,08122861427
ADN008 Tina 08566241521
ADN009 Ir. Yanto 7265122, 7123910
ADN010 Made 6723192
Tabel : Sales
non-atomic
Unnormalized Not 1NF
IDSales NamaSales Telepon
ADN006 Yeni, SE 3517261
ADN006 Yeni, SE 3520165
ADN007 Memey 4744621
ADN007 Memey 08122861427
ADN008 Tina 08566241521
ADN009 Ir. Yanto 7265122
ADN009 Ir. Yanto 7123910
ADN010 Made 6723192
1NF
First Normal Form (1NF)
©Silberschatz, Korth and Sudarshan 1.52 Database System Concepts
Tabel : Buku repeated
ISBN Thn_Terbit ID_Pengarang Nama_Pengarang ID_Pengarang Nama_Pengarang
12-1202-19222 1992 K0121 Aris M K1021 Kosim P
11-1090-29101 2001 K1021 Kosim P
11-1090-29102 2001 K2091 K Odelia K0121 Aris M
12-1201-90871 2002 K2092 Renaldi K2091 K Odelia
13-2089-12910 2001 K2019 Samsuri J
Unnormalized Not 1NF
ISBN Thn_Terbit ID_Pengarang Nama_Pengarang
12-1202-19222 1992 K0121 Aris M
12-1202-19222 1992 K1021 Kosim P
11-1090-29101 2001 K1021 Kosim P
11-1090-29102 2001 K2091 K Odelia
11-1090-29102 2001 K0121 Aris M
12-1201-90871 2002 K2092 Renaldi
12-1201-90871 2002 K2091 K Odelia
13-2089-12910 2001 K2019 Samsuri J
1NF
First Normal Form (1NF)
©Silberschatz, Korth and Sudarshan 1.53 Database System Concepts
Suatu relasi disebut memenuhi bentuk normal kedua (2NF) jika dan hanya jika : 1. memenuhi 1NF 2. setiap atribut yang bukan kunci utama tergantung secara fungsional terhadap semua atribut kunci dan bukan hanya sebagian atribut kunci (fully functionally dependent). Untuk normalisasi ke bentuk 2NF, maka tabel 1NF didekomposisi menjadi beberapa tabel yang masing-masing memenuhi 2NF. Bila terdapat ketergantungan parsial maka : eliminate. Tujuan membentuk 2NF : :: semantik tabel 2NF menjadi lebih eksplisit (fully FD) :: mengurangi update anomali yang masih mungkin terjadi pada 1NF
Second Normal Form (2NF)
©Silberschatz, Korth and Sudarshan 1.54 Database System Concepts
Contoh : Diketahui tabel R=(A,B,C,D,E) ; A,B kunci utama (primary key) dengan FD : A,B C,D,E maka tabel R memenuhi 2NF sebab : A,B C,D,E berarti : A,B C, A,B D dan A,B E Jadi semua atribut bukan kunci utama tergantung penuh pada (A,B).
Second Normal Form (2NF)
Note : Jika suatu relasi memenuhi 1NF dan hanya memiliki tepat satu atribut kunci utama maka relasi tsb memenuhi 2NF
©Silberschatz, Korth and Sudarshan 1.55 Database System Concepts
Bagaimana bila R = (A,B,C,D,E) tetapi dengan FD : (A,B) (C,D) dan B E. Apakah memenuhhi 2NF ? Jelas bahwa R bukan 2NF karena ada atribut E yang bergantung hanya pada atribut B saja dan bukan terhadap (A,B). Dari FD : (A,B) (C,D) juga mencerminkan bahwa hanya C dan D saja yang bergantung secara fungsional terhadap (A,B), tidak untuk E. Jadi bukan 2NF. Untuk mengubah menjadi 2NF, lakukan dekomposisi menjadi : R1 = (A,B,C,D) dan R2 = (B,E). Tampak R1 dan R2 memenuhi 2NF.
Second Normal Form (2NF)
©Silberschatz, Korth and Sudarshan 1.56 Database System Concepts
Diketahui Workshop = (NIM,Modul,Biaya,Grade)
NIM
Peserta Workshop
Modul Biaya Key : NIM+Modul
FD : Modul Biaya
NIM Modul Biaya Grade
P11.2004.0129 VB.Net 250000 A
P11.2004.0130 Prolog 100000 A
P11.2004.0129 Prolog 100000 B
P11.2004.0201 Delphi 6 150000 A
P11.2004.0250 VB.Net 250000 B
(Biaya ditentukan oleh Modul yang diambil mahasiswa)
1NF Not 2NF Sebab dalam tabel ini, Biaya tidak bergantung penuh pada atribut kunci (NIM,Modul)
Tabel biaya peserta workshop
Grade
Second Normal Form (2NF)
©Silberschatz, Korth and Sudarshan 1.57 Database System Concepts
NIM Modul Biaya Grade
(NIM,Modul) = key (NIM,Modul) Biaya (partial) (NIM,Modul) Grade (full)
Eliminate
NIM Modul Biaya Grade
Make Decomposition :
Works1 = (NIM,Modul,Grade) Works2 = (Modul,Biaya)
Fully Dependency
Second Normal Form (2NF)
©Silberschatz, Korth and Sudarshan 1.58 Database System Concepts
NIM Modul Biaya Grade
P11.2004.0129 VB.Net 250000 A
P11.2004.0130 Prolog 100000 A
P11.2004.0129 Prolog 100000 B
P11.2004.0201 Delphi 6 150000 A
P11.2004.0250 VB.Net 250000 B
Workshop NIM Modul Grade
P11.2004.0129 VB.Net A
P11.2004.0130 Prolog A
P11.2004.0129 Prolog B
P11.2004.0201 Delphi 6 A
P11.2004.0250 VB.Net B
Modul Biaya
VB.Net 250000
Prolog 100000
Delphi 6 150000
Works1
Works2
More Better Then 1NF
Second Normal Form (2NF)
©Silberschatz, Korth and Sudarshan 1.59 Database System Concepts
Suatu relasi disebut memenuhi bentuk normal ketiga (3NF) jika dan hanya jika : 1. memenuhi 2NF 2. setiap atribut yang bukan kunci tidak tergantung secara fungsional terhadap atribut bukan kunci yang lain dalam relasi tsb (tidak terdapat ketergantungan transitif pada atribut bukan kunci).
Third Normal Form (3NF)
Suatu relasi disebut memenuhi bentuk normal ketiga (3NF) jika dan hanya jika setiap FD nontrivial : X A, dimana X dan A atribut (atau kompositnya), memenuhi salah satu kondisi : 1. X adalah superkey 2. A merupakan anggota candidate key (A disebut prime attribute)
Another Definition :
©Silberschatz, Korth and Sudarshan 1.60 Database System Concepts
Third Normal Form (3NF)
Note : Jika suatu relasi memenuhi 2NF dan hanya memiliki tepat satu atribut yang bukan kunci utama maka relasi tsb memenuhi 3NF
Jika suatu relasi sudah memenuhi 2NF tapi tidak memenuhi 3 NF, maka untuk normalisasi ke bentuk 3NF, tabel 2NF didekomposisi menjadi beberapa tabel hingga masing-masing memenuhi 3NF. Tujuan membentuk 3NF : :: semantik tabel 3NF menjadi lebih eksplisit (fully FD hanya pada primary key). :: menghindari update anomali yang masih mungkin terjadi pada 2NF.
©Silberschatz, Korth and Sudarshan 1.61 Database System Concepts
Contoh : Diketahui tabel R=(A,B,C,D,E) ; A,B kunci utama (primary key) dengan FD : A,B C,D,E dan C D,E maka R bukan 3NF sebab : Atribut D dan E (bukan kunci utama) bergantung secara fungsional pada C (yang juga bukan kunci utama). Melalui FD : Diketahui A,B C,D,E. Karena sifat refleksif maka A,BA,B. Sehingga A,BA,B,C,D,E (A,B) : Superkey. Diketahui CD,E. Karena sifat refleksif maka CC. Sehingga CC,D,E. Karena C A,B,C,D,E maka C bukan superkey. Tidak memenuhi definisi 3NF. Jadi R bukan 3NF. Agar R memenuhi 3NF maka didekomposisi menjadi : R1=(A,B,C) dan R2=(C,D,E) sehingga R1 dan R2 memenuhi 3NF.
Third Normal Form (3NF)
©Silberschatz, Korth and Sudarshan 1.62 Database System Concepts
FD : A,B C,D,E berarti A,B C ; C D,E ; A,B D,E A,B D reduce A,B E reduce
Dekomposisinya : R1=(A,B,C) ; FD : (A,B)C R2=(C,D,E) ; FD : CD,E
A B C D E
A B C C D E
R1 R2
R
Third Normal Form (3NF)
©Silberschatz, Korth and Sudarshan 1.63 Database System Concepts
Misal diketahui struktur informasi dari suatu dokumen supplier :
Akan dibentuk suatu tabel dengan skema TPS=(S,Status,City,P,Qty) dengan (S,P) = primary key dan berlaku FD : S,P Qty S Stat, City City Status Lakukan normalisasi dari 1NF hingga 3NF.
S Status City
P Qty
S1 20 LONDON P1 300
P2 200
P3 400
P4 200
P5 100
P6 100
S2 10 PARIS P1 300
P2 400
S3 10 PARIS P2 200
S4 20 LONDON P2 200
P4 399
P5 400
PQ
Third Normal Form (3NF)
©Silberschatz, Korth and Sudarshan 1.64 Database System Concepts
1NF Not 2NF
Problem : Redundansi inconsistency low speed process Anomaly : S(Status,City) tapi kita tidak bisa insert data (S5,30,JAKARTA) tanpa diikuti data P (khususnya) dan Q. Menghapus 1 baris data akan jg merusak keutuhan informasi. Solusi : Dekomposisi menjadi : TPS1 dan TPS2
TPS
S Status City P Qty
S1 20 LONDON P1 300
S1 20 LONDON P2 200
S1 20 LONDON P3 400
S1 20 LONDON P4 200
S1 20 LONDON P5 100
S1 20 LONDON P6 100
S2 10 PARIS P1 300
S2 10 PARIS P2 400
S3 10 PARIS P2 200
S4 20 LONDON P2 200
S4 20 LONDON P4 399
S4 20 LONDON P5 400
Third Normal Form (3NF)
©Silberschatz, Korth and Sudarshan 1.65 Database System Concepts
TPS1 TPS2
Sekarang kita dapat menambah data (S5,30,JAKARTA) dgn aman Tapi masih ada anomaly : Karena CityStatus maka kita tidak bisa entry data City baru sebelum Status punya nilai. Penghapusan 1 baris sebagian data City juga bisa merusak keutuhan informasi S. Selain itu, masih ada redundansi pada Status dan City
1NF 2NF Not 3NF (trans.) SCity CityStatus
1NF 2NF 3NF
Third Normal Form (3NF)
S Status City
S1 20 LONDON
S2 10 PARIS
S3 10 PARIS
S4 20 LONDON
S P Qty
S1 P1 300
S1 P2 200
S1 P3 400
S1 P4 200
S1 P5 100
S1 P6 100
S2 P1 300
S2 P2 400
S3 P2 200
S4 P2 200
S4 P4 399
S4 P5 400
©Silberschatz, Korth and Sudarshan 1.66 Database System Concepts
TPS1-1 TPS1-2 TPS2 1NF 2NF 3NF
1NF 2NF 3NF 1NF
2NF 3NF
Third Normal Form (3NF)
S P Qty
S1 P1 300
S1 P2 200
S1 P3 400
S1 P4 200
S1 P5 100
S1 P6 100
S2 P1 300
S2 P2 400
S3 P2 200
S4 P2 200
S4 P4 399
S4 P5 400
S City
S1 LONDON
S2 PARIS
S3 PARIS
S4 LONDON
City Status
LONDON 20
PARIS 10
©Silberschatz, Korth and Sudarshan 1.67 Database System Concepts
Third Normal Form (3NF) Try it … !!
1.Diberikan skema relasi R = (A,B,C,D,E,F,G,H,I,J,K) dengan ketergantungan fungsional : A B,C,D ; C D ; E F ; A,E G,H,I,J,K ; I J,K Apakah R memenuhi 3NF ? Jika tidak, rancanglah skema relasi R sedemikian sehingga memenuhi bentuk 3NF. Bila Saudara melakukan dekomposisi tabel, lengkapi dengan uji dekomposisi dan uji lossless. 2.Diketahui R=(A,B,C,D,E,F,G) dimana (A,B) : primary key Ketergantungan fungsional yang berlaku (FD) : A C,D,F ; B C,D,E,G ; E G Jika diketahui bahwa R memenuhi 1NF, apakah R memenuhi 2NF dan 3NF ? Jika tidak, rancanglah skema relasi R sedemikian sehingga memenuhi bentuk 3NF. Bila Saudara melakukan dekomposisi tabel, lengkapi dengan uji dekomposisi dan uji lossless.
©Silberschatz, Korth and Sudarshan 1.68 Database System Concepts
Boyce Codd Normal Form (BCNF)
Suatu relasi disebut memenuhi BCNF jika dan hanya jika setiap determinan yang ada pada relasi tersebut adalah candidate key. Definisi yang lain : Suatu relasi disebut memenuhi BCNF jika untuk setiap FD nontrivial : X A atribut X adalah superkey. Untuk normalisasi ke bentuk BCNF, maka tabel 3NF didekomposisi menjadi beberapa tabel yang masing-masing memenuhi BCNF. Tujuan membentuk BCNF : :: semantik multiple candidate key menjadi lebih eksplisit (FD hanya pada candidate key). :: menghindari update anomali yang masih mungkin terjadi pada 3NF.
Dari definisi 3NF dan BCNF, maka apabila suatu relasi memenuhi BCNF pasti memenuhi 3NF, tetapi belum tentu sebaliknya.
ketergantungan funsional Trivial adalah suatu atribut yang bergantung secara fungsional
terhadap kunci primer, mungkin saja merupakan kunci primer bagi atribut yang lain.
©Silberschatz, Korth and Sudarshan 1.69 Database System Concepts
Contoh : Diketahui tabel R=(A,B,C) dengan FD : A B dan B C maka R bukan BCNF, sebab : A superkey ? AB (diketahui) AB dan BC maka AC (transitif) AA (refleksif) Sehingga A(A,B,C) atau AR. Jadi A superkey. B superkey ? BC (diketahui) BB (refleksif) Tapi BA. Sehingga BA,B,C atau B bukan superkey. Agar R memenuhi BCNF maka didekomposisi menjadi : R1=(A,B) ; FD : A B dan R2=(B,C) ; FD : B C. sehingga R1 dan R2 masing-masing memenuhi BCNF. Sebab A dan B dua-duanya sekarang menjadi superkey.
Boyce Codd Normal Form (BCNF)
©Silberschatz, Korth and Sudarshan 1.70 Database System Concepts
Contoh : Diketahui tabel R=(A,B,C) dengan FD : AB C dan C B. Apakah : 3NF ? BCNF ? R memenuhi 3NF karena : ABC ; maka AB ABC, atau AB R. Jadi AB superkey dari R CB ; maka AC AB, atau AC ABC dan AC R. Jadi AC juga superkey (sekaligus juga candidate key) dari R Karena AB superkey dan C subset candidate key maka R memenuhi 3NF R bukan BCNF karena : AB superkey tetapi C bukan superkey.
Boyce Codd Normal Form (BCNF)
©Silberschatz, Korth and Sudarshan 1.71 Database System Concepts
Students=(sid, name, age) FD : sid name, age • BCNF, sebab sid superkey
Books=(bid, title, year) FD : bid title, year • BCNF, sebab bid superkey
Pinjam=(idpinjam, sid, bid, date) FD : idpinjam bid, date • Bukan BCNF, sebab idpinjam bukan superkey idpinjam sid
Students sid name age
53666 Jones 18
53668 Smith 18
53669 Melissa 17
53670 Hilden 19
Books bid title year
B001 MySQL 2002
B002 Algorithm 2003
B003 Visual Foxpro 6.0 2003
B004 Visual basic 6.0 2005
Pinjam idpinjam sid bid date
P-01 53666 B002 10/11/2005
P-02 53668 B001 10/11/2005
P-03 53668 B004 11/12/2005
P-04 53670 B002 14/11/2005
Boyce Codd Normal Form (BCNF)
©Silberschatz, Korth and Sudarshan 1.72 Database System Concepts
Pinjam idpinjam sid bid date
P-01 53666 B002 10/11/2005
P-02 53668 B001 10/11/2005
P-03 53668 B004 11/12/2005
P-04 53670 B002 14/11/2005
Didekomposisi menjadi :
Pinjam1 idpinjam sid
P-01 53666
P-02 53668
P-03 53668
P-04 53670
Pinjam2 idpinjam bid date
P-01 B002 10/11/2005
P-02 B001 10/11/2005
P-03 B004 11/12/2005
P-04 B002 14/11/2005
FD trivial BCNF
idpinjam bid, date idpinjam superkey BCNF
Boyce Codd Normal Form (BCNF)
©Silberschatz, Korth and Sudarshan 1.73 Database System Concepts
It is always possible to decompose a relation into relations in 3NF and
the decomposition is lossless
the dependencies are preserved
It is always possible to decompose a relation into relations in BCNF and
the decomposition is lossless
it may not be possible to preserve dependencies.
Comparison of BCNF And 3NF
©Silberschatz, Korth and Sudarshan 1.74 Database System Concepts
Contoh kasus redundansi pada 3NF Jadwal = (Nim,Modul,Dosen) FD = {Dosen Modul} Relasi ini memenuhi 3NF, karena tidak ada ketergantungan transitif. Tetapi tidak memenuhi BCNF karena dari Dosen Modul maka Dosen bukan candidate key. Alternatif yang dilakukan adalah dekomposisi tabel menjadi :
Comparison of BCNF And 3NF
NIM Modul Dosen
P11.2004.0129 VB.Net Ajib
P11.2004.0130 Prolog Aris
P11.2004.0201 VB Net Budi
P11.2004.0250 Prolog Jono
P11.2004.0260 VB.Net Budi
NIM Dosen
P11.2004.0129 Ajib
P11.2004.0130 Aris
P11.2004.0201 Budi
P11.2004.0250 Jono
P11.2004.0260 Budi
Dosen Modul
Ajib VB.Net
Aris Prolog
Jono Prolog
Budi VB.Net
BCNF NOT BCNF
©Silberschatz, Korth and Sudarshan 1.75 Database System Concepts
Goal for a relational database design is:
BCNF.
Lossless join.
Dependency preservation.
If we cannot achieve this, we accept one of
Lack of dependency preservation
Redundancy due to use of 3NF
Design Goals
©Silberschatz, Korth and Sudarshan 1.76 Database System Concepts
Entity Set (doesn’t meet the
definition of a relation)
First Normal Form
Second Normal Form
Third Normal Form
Boyce-Codd Normal Form
Remove multivalued & repeating attributes. Meet definition of relation
Remove partial dependencies
Remove transitive dependencies
Select relation where all determinants are candidate key
Design Steps
Praktisi database kebanyakan menganggap bahwa tingkatan normalisasi hingga BCNF atau 3NF dianggap sudah cukup untuk meminimalisasi masalah dalam desain database (redundansi,lossless,dependency preservation)
©Silberschatz, Korth and Sudarshan 1.77 Database System Concepts
Contoh
Untuk Tuan Ali
Jl, A. Yani No. 10
Semarang
Faktur : 101
Tanggal : 10-01-2008
No Kode
Barang
Nama
Barang
Harga
Satuan
Jumlah Jumlah
Bayar
1 1101 Sandal 15.000 10 150.000
2 1110 Sepatu 100.000 7 700.000
3 1112 Kaos 30.000 15 450.000
Total 1.300.000
©Silberschatz, Korth and Sudarshan 1.78 Database System Concepts
No_fa
k
Tgl_faktur Nm_kons Almt_kons Kota_kons Kode_brg Nama_brg Jml Hrg_sat bayar
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1101 Sandal 10 15000 150000
1110 Sepatu 7 100000 700000
1112 Kaos 15 30000 450000
102 11-01-08 Rudi Jl. Seroja Raya 1 Solo 1101 Sandal 20 15000 300000
1113 Jaket 4 200000 800000
Bentuk Tidak Normal (Unnormalized Form)
Bentuk Tidak Normal
Tidak Normal
Pertama, Karena
ada multivalued
attribute
©Silberschatz, Korth and Sudarshan 1.79 Database System Concepts
No_fak Tgl_faktur Nm_kons Almt_kons Kota_kons Kode_brg Nama_brg Jml Hrg_sat bayar
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1101 Sandal 10 15000 150000
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1110 Sepatu 7 100000 700000
101 10-01-08 Ali Jl. A. Yani No. 10 Semarang 1112 Kaos 15 30000 450000
102 11-01-08 Rudi Jl. Seroja Raya 1 Solo 1101 Sandal 20 15000 300000
102 11-01-08 Rudi Jl. Seroja Raya 1 Solo 1113 Jaket 4 200000 800000
Bentuk Normal Pertama
Tidak ada multivalued
attribute. Tetapi masih
ada Anomali
©Silberschatz, Korth and Sudarshan 1.80 Database System Concepts
Bentuk Normal Kedua
Ketergantungan Fungsional tabel tersebut :
Kode_brg -> nama_brg, hrg_sat
Nm_kons -> almt_kons, kota_kons
No_fak -> nm_kons, tgl_faktur
No_fak, kode_brg -> jml, bayar
Kode_brg
Nama_brg
Hrg_sat
No_fak
Kode_brg
Jml
bayar
Nm_kons
Almt_kons
Kota_kons
No_fak
Nm_kons
Tgl_faktur
barang
konsumen
detil
faktur
Lakukan Uji Lossless, untuk memastikan
bahwa proses dekomposisinya adalah benar.
Berdasarkan KF di atas, maka tabel
Belum 2NF karena ………….
Sehingga harus didekomposisi
menjadi beberapa tabel
(seperti diagram relasi tabel
disamping kanan) sesuai dengan
KF diatas.
©Silberschatz, Korth and Sudarshan 1.81 Database System Concepts
Bentuk Normal Kedua
Kode_brg Nama_brg Hrg_sat
1101 Sandal 15000
1110 Sepatu 100000
1112 Kaos 30000
1113 Jaket 200000
No_fak Kode_brg Jml Bayar
101 1101 10 150000
101 1110 7 700000
101 1112 15 450000
102 1101 20 300000
102 1113 4 800000
Nm_kons Almt_kons Kota_kons
Ali Jl. A. Yani No. 10 Semarang
Rudi Jl. Seroja Raya 1 Solo
Barang
konsumen
detil
No_fak Nm_kons Tgl_faktur
101 Ali 10-01-2008
102 Rudi 11-01-2008
faktur
Setiap tabel diuji apakah sudah
memenuhi 2NF? Jika belum
maka harus dilakukan
dekomposisi lagi
©Silberschatz, Korth and Sudarshan 1.82 Database System Concepts
Bentuk Normal Ketiga
Kode_brg Nama_brg Hrg_sat
1101 Sandal 15000
1110 Sepatu 100000
1112 Kaos 30000
1113 Jaket 200000
Barang
KF :
Kode_brg -> nama_brg, hrg_sat
√
√
√
1 NF
2 NF
3 NF
Analisis……………….
Analisis……………….
Analisis……………….
Setiap tabel diuji apakah sudah
memenuhi 3NF? Jika belum
maka harus dilakukan
dekomposisi
©Silberschatz, Korth and Sudarshan 1.83 Database System Concepts
Nm_kons Almt_kons Kota_kons
Ali Jl. A. Yani No. 10 Semarang
Rudi Jl. Seroja Raya 1 Solo
konsumen
Bentuk Normal Ketiga
KF :
Nm_kons -> almt_kons, kota_kons
√
√
√
1 NF
2 NF
3 NF
No_fak Nm_kons Tgl_faktur
101 Ali 10-01-2008
102 Rudi 11-01-2008
faktur
KF :
No_fak -> nm_kons, kota_kons
√
√
√
1 NF
2 NF
3 NF
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
©Silberschatz, Korth and Sudarshan 1.84 Database System Concepts
Bentuk Normal Ketiga
No_fak Kode_brg Jml Bayar
101 1101 10 150000
101 1110 7 700000
101 1112 15 450000
102 1101 20 300000
102 1113 4 800000
detil
KF :
No_fak, kode_brg -> jml, bayar
√
√
√
1 NF
2 NF
3 NF
Analisis……………….
Analisis……………….
Analisis……………….
©Silberschatz, Korth and Sudarshan 1.85 Database System Concepts
Bentuk Normal Ketiga
Kode_brg Nama_brg Hrg_sat
1101 Sandal 15000
1110 Sepatu 100000
1112 Kaos 30000
1113 Jaket 200000
Barang
KF :
Kode_brg -> nama_brg, hrg_sat
√
√
√
1 NF
2 NF
3 NF
Analisis……………….
Analisis……………….
Analisis……………….
Setiap tabel diuji apakah sudah
memenuhi BCNF? Jika belum
maka harus dilakukan
dekomposisi
√ BCNF Analisis……………….
©Silberschatz, Korth and Sudarshan 1.86 Database System Concepts
Nm_kons Almt_kons Kota_kons
Ali Jl. A. Yani No. 10 Semarang
Rudi Jl. Seroja Raya 1 Solo
konsumen
Bentuk Normal Ketiga
KF :
Nm_kons -> almt_kons, kota_kons
√
√
√
1 NF
2 NF
3 NF
No_fak Nm_kons Tgl_faktur
101 Ali 10-01-2008
102 Rudi 11-01-2008
faktur
KF :
No_fak -> nm_kons, kota_kons
√
√
√
1 NF
2 NF
3 NF
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
Analisis……………….
√ BCNF Analisis……………….
√ BCNF Analisis……………….
©Silberschatz, Korth and Sudarshan 1.87 Database System Concepts
Diagram Relasi
Diagram Relasi setelah proses normalisai :
Kode_brg
Nama_brg
Hrg_sat
No_fak
Kode_brg
Jml
bayar
Nm_kons
Almt_kons
Kota_kons
No_fak
Nm_kons
Tgl_faktur
barang
konsumen
detil
faktur
©Silberschatz, Korth and Sudarshan 1.88 Database System Concepts
Berdasarkan formulir tersebut, • Rancanglah tabel penyimpanan datanya (unnormalized form) • Lakukan normalisasi hingga 3NF atau BCNF
©Silberschatz, Korth and Sudarshan 1.89 Database System Concepts
The Callenge of Database Design
Designers must make design compromises that are triggered by conflicting goals :
design standards (design elegance or faithfulness),
to develop “good” design : Lossless, No Redundant, Dependency Preservation
processing speed (performance), and
high processing speeds is “top” priority (efficiency)
minimizing the number and complexity of relationships or table
information requirements
capablility for delivering all specified query and reporting
of user requirements timely
Contoh bentuk kompromi yang populer :
Denormalisasi (pelanggaran normalisasi)
©Silberschatz, Korth and Sudarshan 1.90 Database System Concepts
Denormalisasi
Normalisasi hanyalah merupakan teknik pendekatan yang digunakan untuk mendapatkan desain database (lojik) yang baik dan bukan sebagai “aturan baku” DBMS yang harus digunakan. Bersifat “Normatif”, memungkinkan untuk dilanggar dengan alasan : Kecepatan Proses (Efisiensi) dan Pelayanan Informasi Tepat Waktu Bentuk-bentuk Denormalisasi : - Membuat Atribut Turunan pada Tabel, mis : Cost=Qty*Price - Atribut yang Berlebihan, mis : NIM mahasiswa sudah mencerminkan program studi mahasiswa, tetapi dalam tabel mahasiswa dibuat atribut Program Studi. - Summary Table (mis : summary table for report) - Membiarkan relasi transitif dalam satu tabel untuk kemudahan proses Konsekuensi Denormalisasi : Redundancy, Not Atomic, Worst Space dll
Design Standards Vs (proceessing speed,information requirements)
©Silberschatz, Korth and Sudarshan 1.91 Database System Concepts
Additional Material (Normal Form Other)
©Silberschatz, Korth and Sudarshan 1.92 Database System Concepts
Multivalued Dependency (MVD)
Beberapa bentuk normal (normal forms, NF) : 1NF, 2NF, 3NF, BCNF based on keys and functional dependencies 4NF, 5NF based on keys and multi-valued dependencies)
Multivalued Dependencies (MVD)
Misal R adalah skema relasi. A, B dan C adalah subset atribut dari R maka A disebut multidependensi pada B, ditulis AB, jika untuk setiap nilai A terdapat sekumpulan nilai B dan sekumpulan nilai C, tetapi nilai B dan nilai C independen.
©Silberschatz, Korth and Sudarshan 1.93 Database System Concepts
Relasi MVD melibatkan minimal 3 atribut relasi, misal A-B-C Untuk setiap nilai A, terdapat sekumpulan nilai B dan sekumpulan nilai C. Sekumpulan nilai B independen dengan sekumpulan nilai C, semikian juga sebaliknya.
Penawaran Mata Kuliah
Mata KuliahInstruktur Pustaka
Basis Data Himawan CJ Date
Purwanto HF Korth
Aris Marjuni
Matematika M Sidiq C Liu
MT Lang
Multivalued Dependency (MVD)
MVD : Mata Kuliah Instruktur Mata Kuliah Pustaka
©Silberschatz, Korth and Sudarshan 1.94 Database System Concepts
Dalam contoh lain :
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 2 2
3 3 3
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
X Y Z
1 1 1
1 1 2
1 2 1
2 2 1
2 2 2
R1 R2 R3
XY ?
XZ ?
YX ? ZX ?
MVD Exist
No MVD Why ?
No MVD Why ?
Multivalued Dependency (MVD)
©Silberschatz, Korth and Sudarshan 1.95 Database System Concepts
Refleksif : xx Augmentation : Jika xy maka xzyz Transitif : Jika xy dan yz maka xz-y Pseudotransitif : Jika xy dan ywz maka xwz-yw Union : Jika xy dan xz maka xyz Dekomposisi : Jika xy dan xz maka xyz dan xz-y Komplemen : Jika xy dan z=R-x-y maka xz
Multivalued Dependency (MVD)
©Silberschatz, Korth and Sudarshan 1.96 Database System Concepts
Fourth Normal Form (4NF)
Skema relasi R disebut 4NF jika dan hanya jika BCNF dan Tidak terdapat MVD. Apabila terdapat MVD dalam R, misal XY maka harus memenuhi salah satu : - MVD adalah trivial atau - X adalah superkey
©Silberschatz, Korth and Sudarshan 1.97 Database System Concepts
Misal diketahui R = (A, B, C, D, E, F) MVD : AB dan CDEF. Bila diasumsikan R memenuhi BCNF, apakah memenuhi 4NF ? Jika belum upayakan menjadi 4NF. • Bukan 4NF sebab terdapat MVD dan nontrivial. • Dekomposisi R : Dari AB, dibentuk R1=(A,B) Karena AB maka A C,D,E,F dan dibentuk R2=(A,C,D,E,F) • R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial • R2=(A,C,D,E,F) Bukan 4NF, karena MVD : CDEF nontrivial • Dekomposisi R2 : Dari CDEF dibentuk R21=(C,D,E,F) Karena CDEF dan CDA, dibentuk R22=(C,D,A) • R21=(C,D,E,F) 4NF, karena MVD : CDEF trivial • R22=(C,D,A) 4NF, karena tidak ada MVD.
Fourth Normal Form (4NF)
R1=(A,B)
R21=(C,D,E,F)
R22=(C,D,A)
Memenuhi 4NF
©Silberschatz, Korth and Sudarshan 1.98 Database System Concepts
Misal diketahui R = (A, B, C, G, H, I) MVD : AB, BHI dan CGH. Bila diasumsikan R memenuhi BCNF, apakah memenuhi 4NF ? Jika belum upayakan menjadi 4NF. • Bukan 4NF sebab terdapat MVD, nontrivial dan bukan superkey. • Dekomposisi R : Dari AB, dibentuk R1=(A,B) Karena AB maka A C,G,H,I dan dibentuk R2=(A,C,G,H,I) • R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial • R2=(A,C,G,H,I) Bukan 4NF, karena MVD : CGH nontrivial • Dekomposisi R2 : Dari CGH dibentuk R21=(C,G,H) Karena CGH maka CGA,I dan dibentuk R22=(C,G,A,I) • R21=(C,G,H) 4NF, karena MVD : CGH trivial, tetapi R22=(C,G,A,I) bukan 4NF, karena ada MVD : AI (dari AB, BHI maka A-->HI
dan AI). • Dekomposisi R22 menjadi R221=(A,I) dan R222=(A,C,G) dan masing-masing merupakan bentuk 4NF.
Fourth Normal Form (4NF)
R1=(A,B)
R21=(C,G,H)
R221=(A,I)
R222=(A,C,G)
Memenuhi 4NF
©Silberschatz, Korth and Sudarshan 1.99 Database System Concepts
BCNF, sebab : - 1NF, Yes - 2NF, Yes. Sebab semua atribut mrpk atribut kunci. - 3NF, Yes. Sebab tidak ada ketergantungan transitif. - BCNF, Yes. Tidak ada FD pada atribut bukan kunci. - 4NF, No. Sebab terdapat MVD yang nontrivial. Dekomposisi ……………………
MVD : Mata Kuliah Instruktur Mata Kuliah Pustaka
Fourth Normal Form (4NF)
©Silberschatz, Korth and Sudarshan 1.100 Database System Concepts
4NF
4NF
Mata KuliahPustaka
Mata KuliahInstruktur
Fourth Normal Form (4NF)
Refference : Toby J. Teorey, Database Modeling & Design, page 112-116
©Silberschatz, Korth and Sudarshan 1.101 Database System Concepts
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 2 2
3 3 3
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
X Y Z
1 1 1
1 1 2
1 2 1
2 2 1
2 2 2
R1 R2 R3
4NF ? No. - MVD nontrivial - Bukan Superkey
4NF ? Yes
4NF ? Yes
Fourth Normal Form (4NF)
©Silberschatz, Korth and Sudarshan 1.102 Database System Concepts
Fifth Normal Form (5NF)
S P J
S1 P1 J2
S1 P2 J1
S2 P1 J1
S1 P1 J1
SPJ
SP SJ 4NF ? No
S P
S1 P1
S1 P2
S2 P1
SP
P J
P1 J2
P2 J1
P1 J1
PJ
SP 4NF ? Yes
SJ 4NF ? Yes
Misal SPJ berisi data-data Supplier (S) yang memasok barang (P) untuk suatu Project (J). Satu supplier dapat memasok banyak barang, supplier juga Dapat berpartisipasi pada banyak proyek.
Key : S, P, J MVD :
Jika SP dan PJ di-project join-kan kembali on P akan diperoleh :
S P J
S1 P1 J2
S1 P1 J1
S2 P1 J2
S2 P1 J1
S1 P2 J1
SP join PJ
Tupel asing
Ternyata projection-join dari dekomposisinya tidak mengembalikan Ke relasi asal.
©Silberschatz, Korth and Sudarshan 1.103 Database System Concepts
S P J
S1 P1 J2
S1 P1 J1
S2 P1 J2
S2 P1 J1
S1 P2 J1
SP join PJ
Relasi hasil project-join tsb akan kembali ke bentuk relasi asal SPJ setelah di project-join Kan dengan SJ pada S dan J
S J
S1 J2
S1 J1
S2 J1
SJ
Project-join on (S,J)
S P J
S1 P1 J2
S1 P1 J1
S2 P1 J1
S1 P2 J1
SPJ (Original)
Dekomposisi Akhir
S P
S1 P1
S1 P2
S2 P1
SP
P J
P1 J2
P2 J1
P1 J1
PJ
S J
S1 J2
S1 J1
S2 J1
SJ
Fifth Normal Form (5NF)
©Silberschatz, Korth and Sudarshan 1.104 Database System Concepts
Fifth Normal Form (5NF)
Disebut juga Projection-Join Normal Form (PJ/NF) Skema relasi R disebut memenuhi 5NF jika tidak dapat dibuat menjadi beberapa tabel kecil yang lossless melalui operasi projection- join atau Skema relasi R disebut memenuhi 5NF jika setiap join dependency (JD) nontrivial pada R diimplikasikan oleh Candidate key dari R Join Dependency Batasan dekomposisi yang lossless pada sejumlah operasi project-join
©Silberschatz, Korth and Sudarshan 1.105 Database System Concepts
S P J
S1 P1 J2
S1 P2 J1
S2 P1 J1
S1 P1 J1
SPJ
SP SJ 4NF ? No
S P
S1 P1
S1 P2
S2 P1
SP
P J
P1 J2
P2 J1
P1 J1
PJ
SP 4NF ? Yes 5NF ? Yes
SJ 4NF ? Yes 4NF ? Yes
Key : S, P, J MVD :
5NF ? Yes, tidak dapat didekomposisi lagi
Trivial pada candidate key
S J
S1 J2
S1 J1
S2 J1
SJ
4NF ? Yes, tidak ada MVD 5NF ? Yes
Refference : C.J. Date, An Introduction To Database Systems, page 394-399
Fifth Normal Form (5NF)
©Silberschatz, Korth and Sudarshan 1.106 Database System Concepts
4NF
5NF
BCNF
3NF
2NF
1NF
LEVEL NORMALISASI
SUMMARY
©Silberschatz, Korth and Sudarshan 1.107 Database System Concepts
It is best to find a database design that meet the 3-criteria : • NF (Normal-Form)note
• Dependency Preservation • Lossless-Join note If we only have functional dependencies (FD), the first criteria is just BCNF. If we only have multivalued dependency (MVD), the first criteria is just 4NF. If we only have join dependency (JD), the first criteria is just 5NF. If we cannot meet all 3-criteria, we compromise on 4NF, and accept BCNF, or even 3NF if necessary, to ensure dependency preservation.
SUMMARY