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)


Functional Dependency

And

Normalization


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 .. ??









Redundancy Informasi diulang-ulang

dalam beberapa tupel

125

Update Anomaly Update informasi pada

satu tupel tidak

mengubah pada tupel

yang lain

motivasi

Tabel : Film









Tabel : Film

motivasi

Delete Anomaly Jika Emilio Estavez dihapus,

akan kehilangan informasi

tentang Mighty Ducks


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









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


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


Teori Dasar :

Dekomposisi Relasi

Key

Ketergantungan Fungsional

we discuss before …


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


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


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.


Film = (idfilm, title, year, length, filmType, idstudio, studioName, idstar, starName)

there is Anomaly !! Decompose it ……








dekomposisi relasi

Oopss !!!


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








dekomposisi relasi

Lossless or

Lossy ?

DaftarFilm StudioFilm BintangFilm

Film

Andaikan di dekomposisi Menjadi 3 tabel tsb ….


“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


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


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


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


definisi


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


Film = (idfilm, title, year, length, filmType, idstudio, studioName, idstar, starName)








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


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


Contoh :

X X X,Y X X,Y Y

X,Y,Z X,Z X,Y,Z Z X,Y,Z X,Y,Z


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


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


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


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.


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)


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.


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+


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



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.


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



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


KEYS


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


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


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


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


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


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


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.


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



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 ?




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


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



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


End Session Today Tomorrow We’ll Discuss About

Normalization ……


Normalization


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)


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)


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



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



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)


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).


Note : Jika suatu relasi memenuhi 1NF dan hanya memiliki tepat satu atribut kunci utama maka relasi tsb memenuhi 2NF


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.



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




(NIM,Modul) = key (NIM,Modul) Biaya (partial) (NIM,Modul) Grade (full)

Eliminate


Make Decomposition :

Works1 = (NIM,Modul,Grade) Works2 = (Modul,Biaya)

Fully Dependency




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



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 :



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.


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.



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



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



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



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


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


TPS1-1 TPS1-2 TPS2 1NF 2NF 3NF

1NF 2NF 3NF 1NF

2NF 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


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.


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.


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.



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.



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



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



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


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


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


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)


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


No_fa

k

Tgl_faktur Nm_kons Almt_kons Kota_kons Kode_brg Nama_brg Jml Hrg_sat bayar


1110 Sepatu 7 100000 700000

1112 Kaos 15 30000 450000


1113 Jaket 4 200000 800000

Bentuk Tidak Normal (Unnormalized Form)

Bentuk Tidak Normal

Tidak Normal

Pertama, Karena

ada multivalued

attribute


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 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 1113 Jaket 4 200000 800000

Bentuk Normal Pertama

Tidak ada multivalued

attribute. Tetapi masih

ada Anomali


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.


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


Bentuk Normal Ketiga


1101 Sandal 15000

1110 Sepatu 100000

1112 Kaos 30000

1113 Jaket 200000

Barang

KF :


√

√

√

1 NF

2 NF

3 NF

Analisis……………….




memenuhi 3NF? Jika belum


dekomposisi





konsumen


KF :


√

√

√

1 NF

2 NF

3 NF


101 Ali 10-01-2008

102 Rudi 11-01-2008

faktur

KF :

No_fak -> nm_kons, kota_kons

√

√

√

1 NF

2 NF

3 NF









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







1101 Sandal 15000

1110 Sepatu 100000

1112 Kaos 30000

1113 Jaket 200000

Barang

KF :


√

√

√

1 NF

2 NF

3 NF





memenuhi BCNF? Jika belum


dekomposisi

√ BCNF Analisis……………….





konsumen


KF :


√

√

√

1 NF

2 NF

3 NF


101 Ali 10-01-2008

102 Rudi 11-01-2008

faktur

KF :

No_fak -> nm_kons, kota_kons

√

√

√

1 NF

2 NF

3 NF










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


Berdasarkan formulir tersebut, • Rancanglah tabel penyimpanan datanya (unnormalized form) • Lakukan normalisasi hingga 3NF atau BCNF


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)


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)


Additional Material (Normal Form Other)


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.


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


MVD : Mata Kuliah Instruktur Mata Kuliah Pustaka


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 ?



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



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


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.


R1=(A,B)

R21=(C,D,E,F)

R22=(C,D,A)

Memenuhi 4NF


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.


R1=(A,B)

R21=(C,G,H)

R221=(A,I)

R222=(A,C,G)

Memenuhi 4NF


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



4NF

4NF

Mata KuliahPustaka

Mata KuliahInstruktur


Refference : Toby J. Teorey, Database Modeling & Design, page 112-116


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



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.


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




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


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



4NF

5NF

BCNF

3NF

2NF

1NF

LEVEL NORMALISASI

SUMMARY


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

basis data (database)dinus.ac.id/repository/docs/ajar/sbd-bab5-2018_revisi.pdf · database system...

Documents