normalization
DESCRIPTION
1. Aris Marjuni, S.Si, M.Kom [email protected]. Normalization. 2. normalisasi. - PowerPoint PPT PresentationTRANSCRIPT
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)
22
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)
33
IDSales NamaSales Telepon
ADN006 Yeni, SE 3517261, 3520165ADN007 Memey 4744621,08122861427ADN008 Tina 08566241521ADN009 Ir. Yanto 7265122, 7123910ADN010 Made 6723192
Tabel : Sales
non-atomic
UnnormalizedNot 1NF
IDSales NamaSales Telepon
ADN006 Yeni, SE 3517261ADN006 Yeni, SE 3520165ADN007 Memey 4744621ADN007 Memey 08122861427ADN008 Tina 08566241521ADN009 Ir. Yanto 7265122ADN009 Ir. Yanto 7123910ADN010 Made 6723192
1NF
First Normal Form (1NF)
44
Tabel : Buku repeated
ISBN Thn_Terbit ID_Pengarang Nama_Pengarang ID_Pengarang Nama_Pengarang
12-1202-19222 1992 K0121 Aris M K1021 Kosim P11-1090-29101 2001 K1021 Kosim P11-1090-29102 2001 K2091 K Odelia K0121 Aris M12-1201-90871 2002 K2092 Renaldi K2091 K Odelia13-2089-12910 2001 K2019 Samsuri J
UnnormalizedNot 1NF
ISBN Thn_Terbit ID_Pengarang Nama_Pengarang
12-1202-19222 1992 K0121 Aris M12-1202-19222 1992 K1021 Kosim P11-1090-29101 2001 K1021 Kosim P11-1090-29102 2001 K2091 K Odelia11-1090-29102 2001 K0121 Aris M12-1201-90871 2002 K2092 Renaldi12-1201-90871 2002 K2091 K Odelia13-2089-12910 2001 K2019 Samsuri J
1NF
First Normal Form (1NF)
55
Suatu relasi disebut memenuhi bentuk normal kedua (2NF) jika dan hanya jika :1. memenuhi 1NF2. 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)
66
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 danA,B EJadi semua atribut bukan kunci utama tergantung penuh pada (A,B).
Second Normal Form (2NF)
77
Bagaimana bila R = (A,B,C,D,E) tetapi dengan FD : (A,B) (C,D) dan B E. Apakah memenuhhi 2NF ?
Jelas bahwa R bukan 2NF karena ada atribut E yang bergantung hanya pada atribut B saja dan bukan terhadap (A,B). Dari FD : (A,B) (C,D) juga mencerminkan bahwa hanya C dan D saja yang bergantung secara fungsional terhadap (A,B), tidak untuk E. Jadi bukan 2NF.
Untuk mengubah menjadi 2NF, lakukan dekomposisi menjadi :R1 = (A,B,C,D) dan R2 = (B,E). Tampak R1 dan R2 memenuhi 2NF.
Second Normal Form (2NF)
88
Diketahui Workshop = (NIM,Modul,Biaya,Grade)
NIM
Peserta Workshop
Modul BiayaKey : NIM+ModulFD : 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 yangdiambil mahasiswa)
1NF Not 2NF
Sebab dalam tabel ini, Biaya tidak bergantung penuhpada atribut kunci (NIM,Modul)
Tabel biaya peserta workshop
Grade
Second Normal Form (2NF)
99
NIM Modul Biaya Grade
(NIM,Modul) = key(Modul) Biaya (partial)(NIM,Modul) Grade (full)
Eliminate
NIM Modul Biaya Grade
Make Decomposition :
Works1 = (NIM,Modul,Grade)Works2 = (Modul,Biaya)
Fully Dependency
Second Normal Form (2NF)
1010
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
WorkshopNIM Modul Grad
e
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 BModul Biaya
VB.Net 250000
Prolog 100000
Delphi 6
150000
Works1
Works2
Better Then1NF
Second Normal Form (2NF)
1111
Suatu relasi disebut memenuhi bentuk normal ketiga (3NF) jika dan hanya jika :1. memenuhi 2NF2. 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 atau2. A merupakan anggota candidate key
Another Definition :
1212
Third Normal Form (3NF)
Note : Jika suatu relasi memenuhi 2NF dan hanya memiliki tepat satu atribut yang bukan kunci utama maka relasi tsb memenuhi 3NF
Jika suatu relasi sudah memenuhi 2NF tapi tidak memenuhi 3 NF, maka untuk normalisasi ke bentuk 3NF, tabel 2NF didekomposisi
menjadi beberapa tabel hingga masing-masing memenuhi 3NF. Tujuan membentuk 3NF :
:: semantik tabel 3NF menjadi lebih eksplisit (fully FD hanya pada primary key).:: menghindari update anomali yang masih mungkin terjadi pada 2NF.
1313
Contoh : Diketahui tabel R=(A,B,C,D,E) ; A,B kunci utama (primary key)dengan FD : A,B C,D,E dan C D,E maka R bukan 3NF sebab :Atribut D dan E (bukan kunci utama) bergantung secara fungsional pada C (yang juga bukan kunci utama).
Melalui FD : Diketahui A,B C,D,E.
Karena sifat refleksif maka A,BA,B. Sehingga A,BA,B,C,D,E (A,B) : Superkey.
Diketahui CD,E.Karena sifat refleksif maka CC. Sehingga CC,D,E. Karena C A,B,C,D,E maka C bukan superkey.
Tidak memenuhi definisi 3NF. Jadi R bukan 3NF.
Agar R memenuhi 3NF maka didekomposisi menjadi :R1=(A,B,C) dan R2=(C,D,E) sehingga R1 dan R2 memenuhi 3NF.
Third Normal Form (3NF)
1414
FD : A,B C,D,E berarti A,B C ; C D,E ; A,B D,EA,B D reduceA,B E reduce
Dekomposisinya : R1=(A,B,C) ; FD : (A,B)CR2=(C,D,E) ; FD : CD,E
A B C D E
A B C C D E
R1 R2
R
Third Normal Form (3NF)
1515
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 :
SStatusSCityCityStatus
Lakukan normalisasi dari 1NF hingga 3NF.
S Status CityP Qty
S1 20 LONDON P1 300P2 200P3 400P4 200P5 100P6 100
S2 10 PARIS P1 300P2 400
S3 10 PARIS P2 200S4 20 LONDON P2 200
P4 399P5 400
PQ
Third Normal Form (3NF)
1616
1NF Not 2NF
Problem : Redundansi inconsistency
low speed process Anomaly :
S(Status,City) tapi kita tidak bisa insertdata (S5,30,JAKARTA) tanpa diikuti dataP (khususnya) dan Q. Menghapus 1 barisdata akan jg merusak keutuhan informasi.
Solusi :Dekomposisi menjadi :TPS1 dan TPS2
TPSS Status City P QtyS1 20 LONDON P1 300S1 20 LONDON P2 200S1 20 LONDON P3 400S1 20 LONDON P4 200S1 20 LONDON P5 100S1 20 LONDON P6 100S2 10 PARIS P1 300S2 10 PARIS P2 400S3 10 PARIS P2 200S4 20 LONDON P2 200S4 20 LONDON P4 399S4 20 LONDON P5 400
Third Normal Form (3NF)
1717
TPS1 TPS2S P QtyS1 P1 300S1 P2 200S1 P3 400S1 P4 200S1 P5 100S1 P6 100S2 P1 300S2 P2 400S3 P2 200S4 P2 200S4 P4 399S4 P5 400
S Status CityS1 20 LONDONS2 10 PARISS3 10 PARISS4 20 LONDON
Sekarang kita dapat menambahdata (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 barissebagian data City juga bisa merusak keutuhan informasi S.
Selain itu, masih ada redundansipada Status dan City
1NF 2NF Not 3NF (trans.) SCity CityStatus
1NF 2NF 3NF
redundansi partial not potensial better then previous redundantWe may not eliminateall redundant but wemake its minimize
Third Normal Form (3NF)
1818
S CityS1 LONDONS2 PARISS3 PARISS4 LONDON
City StatusLONDON 20PARIS 10
TPS1-1 TPS1-2 TPS2S P QtyS1 P1 300S1 P2 200S1 P3 400S1 P4 200S1 P5 100S1 P6 100S2 P1 300S2 P2 400S3 P2 200S4 P2 200S4 P4 399S4 P5 400
1NF 2NF 3NF
1NF 2NF 3NF 1NF
2NF 3NF
Third Normal Form (3NF)
1919
Third Normal Form (3NF) Try it … !!
1.Diberikan skema relasi R = (A,B,C,D,E,F,G,H,I,J,K) dengan ketergantunganfungsional :A B,C,D ; C D ; E F ; A,E G,H,I,J,K ; I J,KApakah 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,H) dimana (A,B) : primary keyKetergantungan fungsional yang berlaku (FD) :A C,F ; B G,H ; A,B D,E dan D E Jika diketahui bahwa R memenuhi 1NF, apakah R memenuhi 2NF ? 3NF ? Jika tidak, rancanglah skema relasi R sedemikian sehingga memenuhi bentuk
2NF dan 3NF. Bila Saudara melakukan dekomposisi tabel, lengkapi dengan uji dekomposisi dan uji lossless.
2020
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.
2121
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 Bdua-duanya sekarang menjadi superkey.
Boyce Codd Normal Form (BCNF)
2222
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 A R. Jadi AB superkey dari RCB ; maka AC AB, atau AC ABC dan AC R. Jadi AC juga superkey (sekaligus juga candidate key) dari R Karena AB superkey dan C subset candidate key maka R memenuhi 3NF
R bukan BCNF karena :AB superkey tetapi C bukan superkey.
Boyce Codd Normal Form (BCNF)
2323
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 nameage
53666 Jones 18
53668 Smith 18
53669
Melissa 17
53670 Hilden 19
Books
bid titleyea
r
B001 MySQL200
2
B002 Algorithm200
3
B003Visual Foxpro 6.0
2003
B004Visual basic 6.0
2005
Pinjamidpinja
m sid bid date
P-01 53666 B00210/11/200
5
P-02 53668 B00110/11/200
5
P-03 53668 B00411/12/200
5
P-04 53670 B00214/11/200
5
Boyce Codd Normal Form (BCNF)
2424
Pinjamidpinja
m sid bid date
P-01 53666 B00210/11/200
5
P-02 53668 B00110/11/200
5
P-03 53668 B00411/12/200
5
P-04 53670 B00214/11/200
5
Didekomposisi menjadi :Pinjam1
idpinjam sid
P-01 53666
P-02 53668
P-03 53668
P-04 53670
Pinjam2idpinja
m bid date
P-01 B00210/11/200
5
P-02 B00110/11/200
5
P-03 B00411/12/200
5
P-04 B00214/11/200
5
FD trivial BCNF
idpinjam bid, dateidpinjam superkey BCNF
Boyce Codd Normal Form (BCNF)
2525
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
2626
Contoh kasus redundansi pada 3NFJadwal = (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
2727
NIM Modul Dosen
P11.2004.0129
VB.Net Ajib
P11.2004.0130
Prolog Aris
P11.2004.0129
VB Net Ajib
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.0129
Ajib
P11.2004.0201
Budi
P11.2004.0250
Jono
P11.2004.0260
Budi
Dosen
Modul
Ajib VB.Net
Aris Prolog
Jono Prolog
Budi VB.Net
BCNFNOT 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
2828
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 relationRemove partial dependencies
Remove transitive dependencies
Select relation where all determinants are candidate key
Design Steps
Praktisi database kebanyakanmenganggap bahwa tingkatannormalisasi hingga BCNF atau3NF dianggap sudah cukup untuk meminimalisasi masalahdalam desain database (redundansi,lossless,dependencypreservation)
2929
Berdasarkan formulir tersebut,• Rancanglah tabel penyimpanan
datanya• Lakukan normalisasi hingga 3NF
atau BCNF• Desain untuk datawarehouse
3030
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)
3131
Denormalisasi
Normalisasi hanyalah merupakan teknik pendekatan yang digunakanuntuk 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)
3232
Additional Material(Normal Form Other)
3333
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.
3434
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 KuliahMata KuliahInstruktur PustakaBasis Data Himawan CJ Date
Purwanto HF KorthAris Marjuni
Matematika M Sidiq C LiuMT Lang
Penawaran Mata KuliahMata Kuliah Instruktur PustakaBasis Data Himawan CJ DateBasis Data Purwanto CJ DateBasis Data Aris Marjuni CJ DateBasis Data Himawan HF KorthBasis Data Purwanto HF KorthBasis Data Aris Marjuni HF KorthMatematika M Sidiq C LiuMatematika M Sidiq MT Lang
Multivalued Dependency (MVD)
3535
MVD : Mata Kuliah InstrukturMata 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 MVDWhy ?
No MVDWhy ?
Multivalued Dependency (MVD)
3636
Refleksif : xxAugmentation : Jika xy maka xzyzTransitif : Jika xy dan yz maka xz-yPseudotransitif : Jika xy dan ywz maka xwz-ywUnion : Jika xy dan xz maka xyzDekomposisi : Jika xy dan xz maka xyz dan xz-yKomplemen : Jika xy dan z=R-x-y maka xz
Multivalued Dependency (MVD)
3737
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
3838
Misal diketahui R = (A, B, C, D, E, F)MVD : AB dan CDEF. Bila diasumsikan R memenuhi BCNF, apakah memenuhi 4NF ? Jika belum upayakan menjadi 4NF.
• Bukan 4NF sebab terdapat MVD dan nontrivial.• Dekomposisi R :
Dari AB, dibentuk R1=(A,B)Karena AB maka A C,D,E,F dan dibentuk R2=(A,C,D,E,F)
• R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial
• R2=(A,C,D,E,F)Bukan 4NF, karena MVD : CDEF nontrivial
• Dekomposisi R2 :Dari CDEF dibentuk R21=(C,D,E,F)Karena CDEF dan CDA, dibentuk R22=(C,D,A)
• R21=(C,D,E,F)4NF, karena MVD : CDEF trivial
• R22=(C,D,A)4NF, karena tidak ada MVD.
Fourth Normal Form (4NF)
R1=(A,B)
R21=(C,D,E,F)
R22=(C,D,A)
Memenuhi 4NF
3939
Misal diketahui R = (A, B, C, G, H, I)MVD : AB, BHI dan CGH. Bila diasumsikan R memenuhi BCNF, apakah memenuhi 4NF ? Jika belum upayakan menjadi 4NF.
• Bukan 4NF sebab terdapat MVD, nontrivial dan bukan superkey.• Dekomposisi R :
Dari AB, dibentuk R1=(A,B)Karena AB maka A C,G,H,I dan dibentuk R2=(A,C,G,H,I)
• R1=(A,B) memenuhi 4NF, sebab MVD : AB trivial
• R2=(A,C,G,H,I)Bukan 4NF, karena MVD : CGH nontrivial
• Dekomposisi R2 :Dari CGH dibentuk R21=(C,G,H)Karena CGH maka CGA,I dan dibentuk R22=(C,G,A,I)
• R21=(C,G,H) 4NF, karena MVD : CGH trivial, tetapi R22=(C,G,A,I)bukan 4NF, karena ada MVD : AI (dari AB, BHI maka A-->HI dan AI).
• Dekomposisi R22 menjadi R221=(A,I) dan R222=(A,C,G)dan masing-masing merupakan bentuk 4NF.
Fourth Normal Form (4NF)
R1=(A,B)
R21=(C,G,H)
R221=(A,I)
R222=(A,C,G)
Memenuhi 4NF
4040
Penawaran Mata KuliahMata Kuliah Instruktur PustakaBasis Data Himawan CJ DateBasis Data Purwanto CJ DateBasis Data Aris Marjuni CJ DateBasis Data Himawan HF KorthBasis Data Purwanto HF KorthBasis Data Aris Marjuni HF KorthMatematika M Sidiq C LiuMatematika M Sidiq MT Lang
BCNF, sebab : - 1NF, Yes - 2NF, Yes. Sebab semua atribut mrpk atribut kunci. - 3NF, Yes. Sebab tidak ada ketergantungan transitif. - BCNF, Yes. Tidak ada FD pada atribut bukan kunci. - 4NF, No. Sebab terdapat MVD yang nontrivial. Dekomposisi ……………………
MVD : Mata Kuliah Instruktur Mata Kuliah Pustaka
Fourth Normal Form (4NF)
4141
InstMata Kuliah InstrukturBasis Data HimawanBasis Data PurwantoBasis Data Aris MarjuniMatematika M Sidiq
PustMata Kuliah PustakaBasis Data CJ DateBasis Data HF KorthMatematika C LiuMatematika MT Lang
Penawaran Mata KuliahMata Kuliah Instruktur PustakaBasis Data Himawan CJ DateBasis Data Purwanto CJ DateBasis Data Aris Marjuni CJ DateBasis Data Himawan HF KorthBasis Data Purwanto HF KorthBasis Data Aris Marjuni HF KorthMatematika M Sidiq C LiuMatematika M Sidiq MT Lang
4NF
4NF
Mata KuliahPustaka
Mata KuliahInstruktur
Fourth Normal Form (4NF)
Refference :Toby J. Teorey, Database Modeling & Design, page 112-116
4242
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 2 2
3 3 3
X Y Z
1 1 1
1 1 2
1 2 1
1 2 2
2 2 1
2 1 2
X Y Z
1 1 1
1 1 2
1 2 1
2 2 1
2 2 2
R1 R2 R3
4NF ? No.- MVD nontrivial- Bukan Superkey
4NF ? Yes
4NF ? Yes
Fourth Normal Form (4NF)
4343
Fifth Normal Form (5NF)
S P J
S1 P1 J2
S1 P2 J1
S2 P1 J1
S1 P1 J1
SPJ
SPSJ4NF ? No
S P
S1 P1
S1 P2
S2 P1
SP
P J
P1 J2
P2 J1
P1 J1
PJ
SP4NF ? Yes
SJ4NF ? Yes
Misal SPJ berisi data-data Supplier (S) yang memasok barang (P) untuk suatu Project (J). Satu supplier dapat memasok banyak barang, supplier jugaDapat berpartisipasi pada banyak proyek.
Key : S, P, JMVD :
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.
4444
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-joinKan dengan SJ pada S dan J
S J
S1 J2
S1 J1
S2 J1
SJ
Project-joinon (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
4545
Fifth Normal Form (5NF)
Fifth Normal Form (5NF)
Disebut juga Projection-Join Normal Form (PJ/NF) Skema relasi R disebut memenuhi 5NF jika tidak dapat dibuat menjadi beberapa tabel kecil yang lossless melalui operasi projection- join atau
Skema relasi R disebut memenuhi 5NF jika setiap join dependency (JD) nontrivial pada R diimplikasikan oleh Candidate key dari R Join Dependency
Batasan dekomposisi yang lossless pada sejumlah operasi project-join
4646
S P J
S1 P1 J2
S1 P2 J1
S2 P1 J1
S1 P1 J1
SPJ
SPSJ4NF ? No
S P
S1 P1
S1 P2
S2 P1
SP
P J
P1 J2
P2 J1
P1 J1
PJ
SP4NF ? Yes5NF ? Yes
SJ4NF ? Yes5NF ? Yes
Key : S, P, JMVD :
5NF ? Yes, tidak dapat didekomposisi lagi
Trivial pada candidate key
S J
S1 J2
S1 J1
S2 J1
SJ
4NF ? Yes, tidak ada MVD5NF ? Yes
Refference :C.J. Date, An Introduction To Database Systems, page 394-399
Fifth Normal Form (5NF)
4747
4NF
5NF
BCNF
3NF
2NF
1NF
LEVEL NORMALISASI
4848
SUMMARY
It is best to find a database design that meet the 3-criteria :• NF (Normal-Form)note
• Dependency Preservation• Lossless-Join
noteIf 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.
4949
SUMMARY
TUGAS(Menyusul)