Functional Dependency And Normalization

Functional Dependency And Normalization

Database System Concepts

1.1

©Silberschatz, Korth and Sudarshan

motivasi Tabel : Film 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

What your comment ………..


Is a “good” design .. ??

1.2



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 125

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

Update Anomaly Update informasi pada satu tupel tidak mengubah pada tupel yang lain


Redundancy Informasi diulang-ulang dalam beberapa tupel

1.3



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

Delete Anomaly Jika Emilio Estavez dihapus, akan kehilangan informasi tentang Mighty Ducks


1.4



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

Star Wars

1977

124

Color

MGM

James Earl Jones

Insertion Anomaly Jika kita sisipkan tupel baru (Star Wars, 177, 124, color, MGM, James Earl Jones) maka akan terjadi inkonsistensi pada atribut studio


1.5


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


1.6


motivasi Goals :

Problems With :   

Integrity - redundansi - ambiguitas Performance - kecepatan akses - efisiensi storage Maintainability - update - delete - insert


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)

1.7


we discuss before …

Teori Dasar :  Dekomposisi Relasi  Ketergantungan Fungsional  Key


1.8


dekomposisi relasi 

Dekomposisi : memecah relasi/tabel menjadi relasi/tabel yang lebih kecil untuk mendapatkan skema yang tidak mengandung anomali dan redundansi



Diketahui skema relasi R. Gugus relasi {R1, R2, ,…, Rn} disebut Dekomposisi dari R jika :

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


1.9


dekomposisi relasi Film

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

idfilm

title

year

length

filmType

idstudio

studioName

F001

Star Wars

1977

124

color

STD01

F002

Mighty Ducks

1991

104

color

F003

Wayne’s World

1992

95

color


BintangFilm idstar

starName

Fox

STR01

Carrie Fisher

STD02

Disney

STR02

Mark Hamill

STD03

Paramount

STR03

Harrison Ford

STR04

Emilio Estevez

STR05

Dana Carvey

STR06

Mike Meyers

Decomposition result

1.10

original


dekomposisi relasi 

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 : n

atau

r   ri n

i 1

r   ri atau r   ri i 1



n

i 1

Dekomposisi relasi R menjadi gugus relasi {R1, R2, …, Rn} yang menyebabkan hilangnya informasi disebut Lossy-Join Decomposition. Lossless Join digunakan untuk menjamin keutuhan data untuk operasi gabungan (join) dan merupakan fokus dalam desain basis data relasional


1.11


dekomposisi relasi 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

Oopss !!!


there is Anomaly !! Decompose it ……

1.12


dekomposisi relasi Film

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

idfilm

title

year

length

filmType

idstudio

studioName

F001

Star Wars

1977

124

color

STD01

F002

Mighty Ducks

1991

104

color

F003

Wayne’s World

1992

95

color

Andaikan di dekomposisi Menjadi 3 tabel tsb ….


BintangFilm idstar

starName

Fox

STR01

Carrie Fisher

STD02

Disney

STR02

Mark Hamill

STD03

Paramount

STR03

Harrison Ford

STR04

Emilio Estevez

STR05

Dana Carvey

STR06

Mike Meyers

Lossless or Lossy ? 1.13


dekomposisi relasi Dengan ke-3 tabel hasil dekomposisi, misal ditanyakan informasi : “Di studio manakah Star Wars dibuat ?” Pasti kita akan membutuhkan tabel DaftarFilm dan StudioFilm. Tapi dapatkah diperoleh informasi yang kita inginkan dari kedua skema relasi tersebut ? Tampaknya : TIDAK. Karena kita harus melakukan operasi gabungan terlebih dahulu dari Ke-2 tabel. Misal kita lakukan operasi “cross product” antara Daftar_Film dan StudioFilm. DaftarFilm


 StudioFilm

1.14


Kehilangan LOSSY Informasi !! DECOMPOSITION

dekomposisi relasi DaftarFilm idfilm

title

F001

 StudioFilm year

length

filmType

idstudio

studioName

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)


1.15




functional dependencies (FD)  Functional Dependencies (FD) / Ketergantungan Fungsional (KF) digunakan untuk menggambarkan atau mendeskripsikan bentuk normal atas suatu relasi  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


1.16


functional dependencies (FD) definisi 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


1.17


functional dependencies (FD) R = (A, B, C)

contoh

R = (A,B,C,D)

A

B

C

A

B

C

D

1

4

C1

A1

B1

C1

D1

1

5

C1

A1

B2

C1

D2

2

7

C2

A2

B2

C2

D2

A2

B3

C2

D3

A3

B3

C2

D4

AB? t1(A)=t2(A), tetapi t1(B)  t2(B) Maka A  B AC?

   

t1(A)=t2(A) dan t1(C) = t2(C) Maka A  C


1.18

AC? CA? (A,B)  C ? (A,B)  D ?

Yes No Yes Yes


functional dependencies (FD)


1.19



contoh

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

Apakah : idfilm  title ? idstudio  studioName ? (idfilm,idstar)  starName ? Database System Concepts

1.20


functional dependencies (FD) 

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,Y,Z  X,Z XX X,Y,Z  Z X,Y  X X,Y,Z  X,Y,Z X,Y  Y


1.21



Armstrong’s Rule

Diketahui A1. Reflexive Dari A2 Jika y  x maka x  y Diketahui A2. Augmentation Dari A3 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


1.22

xy (x,z)  (y,z) (z,y)  w (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


1.23


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


1.24


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.


1.25


uji lossless-joint decomposition

contoh

terbukti {R1,R2} Lossless

2. Uji Lossless 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

Jadi

Dari

(1) (5) (6) (7) (1) (8) (9) (3) (10) (11)


B  A,G maka : B,D  A,G,D (augmentasi) B,D  B,D (refleksif) B,D  A,B,D,G B  A,G maka B  A dan BG A  E,C maka A  E dan A  C maka :

Dari dan Maka Dan

(8) (11) (12) (13)

BA AC B  C (transitif) B,D  C,D (augmentasi)

Dari (7) dan (13) didapat : B,D  A,B,C,D,G Dari contoh di atas, tunjukkan pula bahwa (B,D)  (B,D,E,F,H)

1.26


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.


1.27


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+


1.28



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+.  Armstrong’s rule dapat dimanfaatkan untuk menentukan 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 Database System Concepts

1.29


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.


1.30


uji dependency preservation b. R=(A,B,C) dan F = {AB, BC}. Karena AB dan BC maka AC. Maka dapat dibentuk closure F+={AB, BC,AC}. R1=(A,B) dan F1={AB}. Karena hanya AB yang berlaku di R1. R2=(B,C) dan F2={BC}. Karena hanya BC yang berlaku di R2. F1  F2 = {AB,BC}. Karena AB dan BC maka AC. Sehingga (F1  F2 )+={AB,BC,AC}=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 : BC, ACB


1.31


soal latihan 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.


1.32


KEYS


1.33


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


1.34


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


1.35


candidate key  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


1.36


primary 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


1.37


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


1.38


foreign key  Foreign Key adalah satu atau lebih atribut dalam satu tabel yang merupakan primary key tabel lain (kunci penghubung).

Produk IDProd

NamaProduk

Harga

QtyStock

F001

TV 14”

1500000

12

F002

TV 21”

2100.000

4

F003

TV 21” Flatron

2700000

24

link

Tabel Name : Produk Primary key : IDProd Foreign Key : -

Order

NoOrder

Date

IDProd

QtyOrder

IDSls

120301

12/11/04

P001

2

120302

13/11/04

P001

120303

22/11/04

P003

link

IDSls

NmSls

AlamatAsal

KotaAsal

S001

S001

Anita

Jl. Nakula 9

Kendal

2

S003

S002

Vicky

Jl. Arjuna I/6

Semarang

6

S001

S003

Roni

Jl. Bima II/3

Semarang

Tabel Name : Order Primary key : NoOrder Foreign Key : IDProd,IDSls


Sales

Tabel Name : Sales Primary key : IDSls Foreign Key : -

1.39


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.


1.40


hubungan FD dengan key 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


1.41


hubungan FD dengan key R = (A,B,C,D) A

B

C

D

A1

B1

C1

D1

A1

B2

C1

D2

A2

B2

C2

D2

A2

B3

C2

D3

A3

B3

C2

D4

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


1.42


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

1.43


hubungan FD dengan key Latihan : 1. Diberikan R(A,B,C,D) dengan FD : AB,AC dan AD Apakah A candidate key dari R ? 2. Diberikan R(A,B,C,D) dengan FD : AB 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);EF;ABC 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;BD;EA a. Carilah superkey dari R b. Carilah candidate key dari R 5. Diberikan R(A,B,C) dengan FD : AB;BC;CA Apakah A merupakan satu-satunya candidate key dari R


1.44


Perhatikan Tabel berikut : a

b

c

No_fak

Tgl_faktur

Nm_kons

Almt_kons

Kota_kons

Kode_brg

101

10-01-08

Ali

Jl. A. Yani No. 10

Semarang

101

10-01-08

Ali

Jl. A. Yani No. 10

101

10-01-08

Ali

102

11-01-08

102

11-01-08


d

e

g

h

I

j

Nama_brg

Jml

Hrg_sat

bayar

1101

Sandal

10

15000

150000

Semarang

1110

Sepatu

7

100000

700000

Jl. A. Yani No. 10

Semarang

1112

Kaos

15

30000

450000

Rudi

Jl. Seroja Raya 1

Solo

1101

Sandal

20

15000

300000

Rudi

Jl. Seroja Raya 1

Solo

1113

Jaket

4

200000

800000

1.45

f


End Session Today Tomorrow We’ll Discuss About

Normalization ……


1.46


Normalization


1.47


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  1NF, 2NF, 3NF, based on keys  4NF, 5NF based on keys


normal (normal forms, NF) : BCNF and functional dependencies and multi-valued dependencies)

1.48


First Normal Form (1NF)  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.


1.49


First Normal Form (1NF) Tabel : Sales IDSales ADN006 ADN007 ADN008 ADN009 ADN010

NamaSales Yeni, SE Memey Tina Ir. Yanto Made

Telepon 3517261, 3520165 4744621,08122861427 08566241521 7265122, 7123910 6723192

1NF


IDSales ADN006 ADN006 ADN007 ADN007 ADN008 ADN009 ADN009 ADN010

1.50

non-atomic Unnormalized Not 1NF NamaSales Yeni, SE Yeni, SE Memey Memey Tina Ir. Yanto Ir. Yanto Made

Telepon 3517261 3520165 4744621 08122861427 08566241521 7265122 7123910 6723192


Unnormalized Not 1NF

First Normal Form (1NF) Tabel : Buku ISBN Thn_Terbit ID_Pengarang 12-1202-19222 1992 K0121 11-1090-29101 2001 K1021 11-1090-29102 2001 K2091 12-1201-90871 2002 K2092 13-2089-12910 2001 K2019

repeated Nama_Pengarang Aris M Kosim P K Odelia Renaldi Samsuri J

ISBN Thn_Terbit ID_Pengarang 12-1202-19222 1992 K0121 12-1202-19222 1992 K1021 11-1090-29101 2001 K1021 11-1090-29102 2001 K2091 11-1090-29102 2001 K0121 12-1201-90871 2002 K2092 12-1201-90871 2002 K2091 13-2089-12910 2001 K2019


1.51

ID_Pengarang Nama_Pengarang K1021 Kosim P K0121 K2091

Aris M K Odelia

Nama_Pengarang Aris M Kosim P Kosim P K Odelia Aris M Renaldi K Odelia Samsuri J

1NF


Second Normal Form (2NF)  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


1.52


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


1.53


Second Normal Form (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.


1.54


Second Normal Form (2NF) Diketahui Workshop = (NIM,Modul,Biaya,Grade)

Peserta Workshop NIM

Modul

Biaya

Grade

(Biaya ditentukan oleh Modul yang diambil mahasiswa)

Tabel biaya peserta workshop 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


Key : NIM+Modul FD : Modul  Biaya

1.55

 1NF  Not 2NF Sebab dalam tabel ini, Biaya tidak bergantung penuh pada atribut kunci (NIM,Modul)


Second Normal Form (2NF)

NIM

Modul

Biaya

Grade

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

NIM

Modul

Biaya

Eliminate

Grade

Make Decomposition : Works1 = (NIM,Modul,Grade) Works2 = (Modul,Biaya)

Fully Dependency


1.56


Second Normal Form (2NF) Workshop

NIM

Modul

Grade

P11.2004.0129

VB.Net

A

NIM

Modul

Biaya

Grade

P11.2004.0129

VB.Net

250000

A

P11.2004.0130

Prolog

A

P11.2004.0130

Prolog

100000

A

P11.2004.0129

Prolog

B

P11.2004.0129

Prolog

100000

B

P11.2004.0201

Delphi 6

150000

A

P11.2004.0201

Delphi 6

A

P11.2004.0250

VB.Net

250000

B

P11.2004.0250

VB.Net

B

Works1

More Better Then 1NF

Modul

Biaya

VB.Net

250000

Prolog

100000

Delphi 6

150000

Works2


1.57


Third Normal Form (3NF)  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). Another Definition :  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)


1.58


Third Normal Form (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. Note : Jika suatu relasi memenuhi 2NF dan hanya memiliki tepat satu atribut yang bukan kunci utama maka relasi tsb memenuhi 3NF


1.59


Third Normal Form (3NF) 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,BA,B. Sehingga A,BA,B,C,D,E (A,B) : Superkey.  Diketahui CD,E. Karena sifat refleksif maka CC. Sehingga CC,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.


1.60


Third Normal Form (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 : CD,E R

A

A

B

B

C

C

D

E

C

D

R2

R1


E

1.61


Third Normal Form (3NF) Misal diketahui struktur informasi dari suatu dokumen supplier : S S1

S2 S3 S4

Status City

PQ P Qty 20 LONDON P1 300 P2 200 P3 400 P4 200 P5 100 P6 100 10 PARIS P1 300 P2 400 10 PARIS P2 200 20 LONDON P2 200 P4 399 P5 400


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.

1.62


Third Normal Form (3NF) 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


 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

1.63


Third Normal Form (3NF) TPS1 S Status City S1 20 LONDON S2 10 PARIS S3 10 PARIS S4 20 LONDON

 1NF  2NF  Not 3NF (trans.) SCity CityStatus

 Sekarang kita dapat menambah data (S5,30,JAKARTA) dgn aman  Tapi masih ada anomaly : Karena CityStatus 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 Database System Concepts

1.64

TPS2 S S1 S1 S1 S1 S1 S1 S2 S2 S3 S4 S4 S4

P P1 P2 P3 P4 P5 P6 P1 P2 P2 P2 P4 P5

 1NF

Qty 300  2NF 200  3NF 400 200 100 100 300 400 200 200 399 400


Third Normal Form (3NF) TPS1-1

S City S1 LONDON S2 PARIS S3 PARIS S4 LONDON  1NF  2NF  3NF


TPS1-2

City Status LONDON 20 PARIS 10  1NF  2NF  3NF

1.65

TPS2 S S1 S1 S1 S1 S1 S1 S2 S2 S3 S4 S4 S4

P P1 P2 P3 P4 P5 P6 P1 P2 P2 P2 P4 P5

 1NF Qty  2NF 300  3NF 200 400 200 100 100 300 400 200 200 399 400 ©Silberschatz, Korth and Sudarshan

Try it … !!

Third Normal Form (3NF)

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.


1.66


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. Database System Concepts

1.67


Boyce Codd Normal Form (BCNF) Contoh : Diketahui tabel R=(A,B,C) dengan FD : A  B dan B  C maka R bukan BCNF, sebab :  A superkey ? AB (diketahui) AB dan BC maka AC (transitif) AA (refleksif) Sehingga A(A,B,C) atau AR. Jadi A superkey.  B superkey ? BC (diketahui) BB (refleksif) Tapi BA. Sehingga BA,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. Database System Concepts

1.68


Boyce Codd Normal Form (BCNF) Contoh : Diketahui tabel R=(A,B,C) dengan FD : AB  C dan C  B. Apakah :  3NF ?  BCNF ?  R memenuhi 3NF karena : ABC ; maka AB  ABC, atau AB  R. Jadi AB superkey dari R CB ; 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.


1.69


Boyce Codd Normal Form (BCNF) Books

Students sid

name

age

bid

title

year

53666

Jones

18

B001

MySQL

2002

53668

Smith

18

B002

Algorithm

2003

53669

Melissa

17

B003

Visual Foxpro 6.0

2003

53670

Hilden

19

B004

Visual basic 6.0

2005

Students=(sid, name, age) FD : sid  name, age • BCNF, sebab sid superkey

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


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

1.70


Boyce Codd Normal Form (BCNF) 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

Pinjam2

idpinjam

sid

idpinjam

bid

date

P-01

53666

P-01

B002

10/11/2005

P-02

53668

P-02

B001

10/11/2005

P-03

53668

P-03

B004

11/12/2005

P-04

53670

P-04

B002

14/11/2005

FD trivial  BCNF


idpinjam  bid, date idpinjam superkey  BCNF

1.71


Comparison of BCNF And 3NF

 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. Database System Concepts

1.72


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 : NIM

Modul

Dosen

NIM

Dosen

Dosen

Modul

P11.2004.0129

VB.Net

Ajib

P11.2004.0129

Ajib

Ajib

VB.Net

P11.2004.0130

Prolog

Aris

P11.2004.0130

Aris

Aris

Prolog

P11.2004.0201

VB Net

Budi

P11.2004.0201

Budi

Jono

Prolog

P11.2004.0250

Prolog

Jono

P11.2004.0250

Jono

Budi

VB.Net

P11.2004.0260

VB.Net

Budi

P11.2004.0260

Budi

NOT BCNF Database System Concepts

BCNF 1.73


Design Goals

 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


1.74


Design Steps (doesn’t meet the definition of a relation)

Entity Set

First Normal Form

Praktisi database kebanyakan menganggap bahwa tingkatan normalisasi hingga BCNF atau 3NF dianggap sudah cukup untuk meminimalisasi masalah dalam desain database (redundansi,lossless,dependency preservation)


Second Normal Form Third Normal Form Boyce-Codd Normal Form

1.75

Remove multivalued & repeating attributes. Meet definition of relation Remove partial dependencies Remove transitive dependencies Select relation where all determinants are candidate key


Contoh Untuk Tuan Ali Jl, A. Yani No. 10 Semarang

No

Faktur : 101 Tanggal : 10-01-2008

Kode

Nama

Harga

Barang

Barang

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


1.76


Tidak Normal Pertama, Karena ada multivalued attribute

Bentuk Tidak Normal

Bentuk Tidak Normal (Unnormalized Form) No_fa k

Tgl_faktur

Nm_kons

Almt_kons

Kota_kons

Kode_brg

101

10-01-08

Ali

Jl. A. Yani No. 10

Semarang

102

11-01-08


Rudi

Jl. Seroja Raya 1

Solo

1.77

Nama_brg

Jml

Hrg_sat

bayar

1101

Sandal

10

15000

150000

1110

Sepatu

7

100000

700000

1112

Kaos

15

30000

450000

1101

Sandal

20

15000

300000

1113

Jaket

4

200000

800000


Bentuk Normal Pertama

No_fak

Tgl_faktur

Nm_kons

Almt_kons

Kota_kons

Kode_brg

Nama_brg

Jml

101

10-01-08

Ali

Jl. A. Yani No. 10

Semarang

101

10-01-08

Ali

Jl. A. Yani No. 10

101

10-01-08

Ali

102

11-01-08

102

11-01-08

Hrg_sat

bayar

1101

Sandal

10

15000

150000

Semarang

1110

Sepatu

7

100000

700000

Jl. A. Yani No. 10

Semarang

1112

Kaos

15

30000

450000

Rudi

Jl. Seroja Raya 1

Solo

1101

Sandal

20

15000

300000

Rudi

Jl. Seroja Raya 1

Solo

1113

Jaket

4

200000

800000

Tidak ada multivalued attribute. Tetapi masih ada Anomali


1.78


Bentuk Normal Kedua Ketergantungan Fungsional tabel tersebut : barang

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

Berdasarkan KF di atas, maka tabel Belum 2NF karena …………. Sehingga harus didekomposisi menjadi : -

konsumen Nm_kons Almt_kons Kota_kons

detil No_fak Kode_brg Jml bayar

faktur No_fak Nm_kons Tgl_faktur

Uji Lossless ? ……………..


1.79


Perhatikan masing-masing tabel, Masih ada anomali?

Bentuk Normal Kedua detil

Barang Kode_brg

Nama_brg

No_fak

Hrg_sat

Kode_brg

Jml

Bayar

1101

Sandal

15000

101

1101

10

150000

1110

Sepatu

100000

101

1110

7

700000

1112

Kaos

30000

101

1112

15

450000

1113

Jaket

200000

102

1101

20

300000

102

1113

4

800000

konsumen faktur Nm_kons

Almt_kons

Kota_kons

Ali

Jl. A. Yani No. 10

Semarang

Rudi

Jl. Seroja Raya 1

Solo


1.80

No_fak

Nm_kons

Tgl_faktur

101

Ali

10-01-2008

102

Rudi

11-01-2008


Bentuk Normal Ketiga Barang Kode_brg

Nama_brg

Hrg_sat

1101

Sandal

15000

1110

Sepatu

100000

1112

Kaos

30000

1113

Jaket

200000

√

1 NF

Analisis……………….

√

2 NF


√

3 NF


KF : Kode_brg -> nama_brg, hrg_sat

Ketergantungan Transitif ?


1.81


Bentuk Normal Ketiga konsumen

√

1 NF


Nm_kons

Almt_kons

Kota_kons

Ali

Jl. A. Yani No. 10

Semarang

√

2 NF


Rudi

Jl. Seroja Raya 1

Solo

√

3 NF


KF : Nm_kons -> almt_kons, kota_kons faktur √

1 NF


No_fak

Nm_kons

Tgl_faktur

101

Ali

10-01-2008

√

2 NF


102

Rudi

11-01-2008

√

3 NF


KF : No_fak -> nm_kons, kota_kons Database System Concepts

1.82


Bentuk Normal Ketiga detil No_fak

Kode_brg

Jml

Bayar

√

1 NF


101

1101

10

150000

101

1110

7

700000

√

2 NF


101

1112

15

450000

√

102

1101

20

300000

3 NF


102

1113

4

800000

Ketergantungan Transitif ?

KF :

No_fak, kode_brg -> jml, bayar


1.83


Diagram Relasi Diagram Relasi setelah proses normalisai : barang Kode_brg Nama_brg Hrg_sat

konsumen Nm_kons Almt_kons Kota_kons


detil No_fak Kode_brg Jml bayar

faktur No_fak Nm_kons Tgl_faktur

1.84


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


1.85


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)


1.86


Denormalisasi Design Standards Vs (proceessing speed,information requirements)  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


1.87


Additional Material (Normal Form Other)


1.88


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 AB, jika untuk setiap nilai A terdapat sekumpulan nilai B dan sekumpulan nilai C, tetapi nilai B dan nilai C independen.


1.89


Multivalued Dependency (MVD)  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

MVD :

C Liu MT Lang

Mata Kuliah  Instruktur Mata Kuliah  Pustaka


1.90


Multivalued Dependency (MVD)  Dalam contoh lain :

R1

R2

R3

X

Y

Z

X

Y

Z

X

Y

Z

1

1

1

1

1

1

1

1

1

1

1

2

1

1

2

1

1

2

1

2

1

1

2

1

1

2

1

1

2

2

1

2

2

2

2

1

2

2

1

2

2

1

2

2

2

2

2

2

2

1

2

3

3

3

XY ? XZ ? YX ? ZX ? MVD Exist Database System Concepts

No MVD Why ?

No MVD Why ?

1.91


Multivalued Dependency (MVD) Refleksif Augmentation Transitif Pseudotransitif Union Dekomposisi Komplemen


: : : : : : :

xx Jika xy Jika xy Jika xy Jika xy Jika xy Jika xy

maka xzyz dan yz maka xz-y dan ywz maka xwz-yw dan xz maka xyz dan xz maka xyz dan xz-y dan z=R-x-y maka xz

1.92


Fourth Normal Form (4NF) Skema relasi R disebut 4NF jika dan hanya jika  BCNF dan  Tidak terdapat MVD.  Apabila terdapat MVD dalam R, misal XY maka harus memenuhi salah satu : - MVD adalah trivial atau - X adalah superkey


1.93


Fourth Normal Form (4NF) Misal diketahui R = (A, B, C, D, E, F) MVD : AB dan CDEF. Bila diasumsikan R memenuhi BCNF, apakah memenuhi 4NF ? Jika belum upayakan menjadi 4NF.

• Bukan 4NF sebab terdapat MVD dan nontrivial. • Dekomposisi R : Dari AB, dibentuk R1=(A,B) Karena AB maka A C,D,E,F dan dibentuk R2=(A,C,D,E,F) • R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial • R2=(A,C,D,E,F) Bukan 4NF, karena MVD : CDEF nontrivial R1=(A,B) • Dekomposisi R2 : Dari CDEF dibentuk R21=(C,D,E,F) R21=(C,D,E,F) Karena CDEF dan CDA, dibentuk R22=(C,D,A) R22=(C,D,A) • R21=(C,D,E,F) 4NF, karena MVD : CDEF trivial Memenuhi 4NF • R22=(C,D,A) 4NF, karena tidak ada MVD. Database System Concepts

1.94


Fourth Normal Form (4NF) Misal diketahui R = (A, B, C, G, H, I) MVD : AB, BHI dan CGH. 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 AB, dibentuk R1=(A,B) Karena AB maka A C,G,H,I dan dibentuk R2=(A,C,G,H,I) • R1=(A,B) R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial R21=(C,G,H) • R2=(A,C,G,H,I) R221=(A,I) Bukan 4NF, karena MVD : CGH nontrivial R222=(A,C,G) • Dekomposisi R2 : Dari CGH dibentuk R21=(C,G,H) Memenuhi 4NF Karena CGH maka CGA,I dan dibentuk R22=(C,G,A,I) • R21=(C,G,H) 4NF, karena MVD : CGH trivial, tetapi R22=(C,G,A,I) bukan 4NF, karena ada MVD : AI (dari AB, BHI maka A-->HI dan AI). • Dekomposisi R22 menjadi R221=(A,I) dan R222=(A,C,G) dan masing-masing merupakan bentuk 4NF. Database System Concepts 1.95 ©Silberschatz, Korth and Sudarshan

Fourth Normal Form (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


1.96


Fourth Normal Form (4NF)

 4NF

Mata KuliahInstruktur

 4NF

Mata KuliahPustaka Refference : J. Teorey, Database Modeling1.97 & Design, page 112-116 DatabaseToby System Concepts ©Silberschatz, Korth and Sudarshan

Fourth Normal Form (4NF) R1

R2

R3

X

Y

Z

X

Y

Z

X

Y

Z

1

1

1

1

1

1

1

1

1

1

1

2

1

1

2

1

1

2

1

2

1

1

2

1

1

2

1

1

2

2

1

2

2

2

2

1

2

2

1

2

2

1

2

2

2

2

2

2

2

1

2

3

3

3

4NF ? Yes

4NF ? Yes

4NF ? No. - MVD nontrivial - Bukan Superkey


1.98


Fifth Normal Form (5NF) 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. SP

SPJ

PJ

S

P

J

S

P

P

J

S1

P1

J2

S1

P1

P1

J2

S1

P2

J1

S1

P2

P2

J1

S2

P1

J1

S2

P1

P1

J1

S1

P1

J1

Key : S, P, J MVD : SP SJ 4NF ? No

SP 4NF ? Yes

Jika SP dan PJ di-project join-kan kembali on P akan diperoleh :

SJ 4NF ? Yes

SP join PJ S

P

J

S1

P1

J2

S1

P1

J1

S2

P1

J2

S2

P1

J1

S1

P2

J1

Tupel asing

Ternyata projection-join dari dekomposisinya tidak mengembalikan Ke relasi asal.


1.99


Fifth Normal Form (5NF) Relasi hasil project-join tsb akan kembali ke bentuk relasi asal SPJ setelah di project-join Kan dengan SJ pada S dan J

SJ

SP join PJ

SPJ (Original)

S

P

J

S

J

S

P

J

S1

P1

J2

S1

J2

P1

J2

S1

P1

J1

Project-join S1 on (S,J)

S1

J1

S1

P1

J1

S2

P1

J2

S2

J1

S2

P1

J1

S2

P1

J1

S1

P2

J1

S1

P2

J1

SP

PJ

SJ

S

P

P

J

S

J

S1

P1

P1

J2

S1

J2

S1

P2

P2

J1

S1

J1

S2

P1

P1

J1

S2

J1

Dekomposisi Akhir Database System Concepts

1.100


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 projectionjoin 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


1.101


Fifth Normal Form (5NF) SP

SPJ

SJ

PJ

S

P

J

S

P

P

J

S

J

S1

P1

J2

S1

P1

P1

J2

S1

J2

S1

P2

J1

S1

P2

P2

J1

S1

J1

S2

P1

J1

S2

P1

P1

J1

S2

J1

S1

P1

J1

Key : S, P, J MVD : SP SJ 4NF ? No

SP 4NF ? Yes 5NF ? Yes

SJ 4NF ? Yes 4NF ? Yes

4NF ? Yes, tidak ada MVD 5NF ? Yes

5NF ? Yes, tidak dapat didekomposisi lagi Trivial pada candidate key

Refference : Systems, page©Silberschatz, 394-399 DatabaseC.J. SystemDate, Concepts An Introduction To Database 1.102 Korth and Sudarshan

1NF

SUMMARY

2NF 3NF BCNF 4NF 5NF

LEVEL NORMALISASI


1.103


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.


1.104


Functional Dependency And Normalization

Recommend Documents