Perbedaan antara 3NF dan BCNF secara sederhana (harus dapat menjelaskan kepada anak berusia 8 tahun)

157

Saya telah membaca kutipan: data tergantung pada kunci [1NF], seluruh kunci [2NF] dan tidak ada apa-apa selain kunci [3NF] .

Namun, saya mengalami kesulitan memahami 3.5NF atau BCNF seperti namanya. Inilah yang saya mengerti:

  • BCNF lebih ketat dari 3NF
  • sisi kiri FD apa pun dalam tabel harus berupa superkey (atau setidaknya kunci kandidat)

Jadi mengapa kemudian, bahwa beberapa tabel 3NF tidak ada dalam BCNF? Maksud saya, kutipan 3NF secara eksplisit mengatakan "apa-apa selain kunci" yang berarti bahwa semua atribut hanya bergantung pada kunci primer. Bagaimanapun, kunci utama adalah kunci kandidat hingga dipilih menjadi kunci utama kami.

Jika ada yang salah dengan pemahaman saya sejauh ini, mohon koreksi saya dan terima kasih atas bantuan yang Anda berikan.

Arnab Datta
sumber
Itu adalah perasaan yang aneh sehingga hanya buku teks yang diterbitkan yang dapat memberikan deskripsi singkat dan akurat tentang suatu konsep. Jika Anda melihat jawaban untuk pertanyaan ini (sangat tua), Anda akan melihat bahwa tidak ada yang berperingkat tinggi tidak jelas atau tidak tepat. Memiliki definisi aljabar bukan masalah, memahami konsep melalui contoh dunia nyata adalah. Adapun kutipan dalam pertanyaan asli saya, google "tolong bantu saya Codd" untuk menemukan asal untuk kutipan. Tidak ada yang kabur tentang itu.
Arnab Datta
1
Dari mana saja Anda pikir sumber non-buku teks mendapatkan informasinya? Ada banyak buku pelajaran yang buruk juga, tetapi buku pelajaran ditinjau oleh banyak orang dengan magang akademik & jauh lebih mungkin untuk tidak omong kosong daripada interpretasi orang lain tentang buku teks. Peringkat tinggi oleh orang yang tidak mendapat informasi & informasi yang salah tidak membuat sesuatu yang benar. Saya memberikan komentar itu untuk orang-orang yang tiba pada pertanyaan Anda. Ungkapan "tidak lain kecuali kunci" itu kurang dari berguna. Memiliki definisi yang benar tentu merupakan masalah, karena "memahami konsep" tidak mungkin tanpa definisi.
philipxy

Jawaban:

162

Pizza Anda dapat memiliki tiga jenis topping:

  • satu jenis keju
  • satu jenis daging
  • satu jenis sayuran

Jadi kami memesan dua pizza dan memilih topping berikut:

Pizza    Topping     Topping Type
-------- ----------  -------------
1        mozzarella  cheese
1        pepperoni   meat
1        olives      vegetable
2        mozzarella  meat
2        sausage     cheese
2        peppers     vegetable

Tunggu sebentar, mozzarella tidak bisa berupa keju dan daging! Dan sosis bukan keju!

Kita perlu mencegah kesalahan semacam ini, untuk membuat mozzarella selalu menjadi keju. Kita harus menggunakan tabel terpisah untuk ini, jadi kita menuliskan fakta itu hanya di satu tempat.

Pizza    Topping
-------- ----------
1        mozzarella
1        pepperoni
1        olives
2        mozzarella 
2        sausage
2        peppers

Topping     Topping Type
----------  -------------
mozzarella  cheese
pepperoni   meat
olives      vegetable
sausage     meat
peppers     vegetable

Itulah penjelasan yang mungkin dimengerti oleh anak berusia 8 tahun. Ini adalah versi yang lebih teknis.

BCNF bertindak berbeda dari 3NF hanya ketika ada beberapa kunci kandidat yang tumpang tindih.

Alasannya adalah bahwa ketergantungan fungsional X -> Yini tentu saja benar jika Ymerupakan bagian dari X. Jadi di setiap tabel yang hanya memiliki satu kunci kandidat dan berada di 3NF, itu sudah ada di BCNF karena tidak ada kolom (baik kunci atau non-kunci) yang secara fungsional bergantung pada apa pun selain kunci itu.

Karena setiap pizza harus memiliki tepat satu dari setiap jenis topping, kita tahu bahwa (Pizza, Topping Type) adalah kunci kandidat. Kami juga tahu secara intuitif bahwa topping yang diberikan tidak dapat dimiliki oleh berbagai jenis secara bersamaan. Jadi (Pizza, Topping) harus unik dan karenanya juga merupakan kunci kandidat. Jadi kami memiliki dua kunci kandidat yang tumpang tindih.

Saya menunjukkan anomali di mana kami menandai mozarella sebagai jenis topping yang salah. Kami tahu ini salah, tetapi aturan yang membuatnya salah adalah ketergantungan Topping -> Topping Typeyang bukan ketergantungan yang sah untuk BCNF untuk tabel ini. Ini ketergantungan pada sesuatu selain kunci kandidat keseluruhan.

Jadi untuk mengatasi ini, kita ambil Topping Type dari tabel Pizzas dan menjadikannya atribut non-kunci dalam tabel Toppings.

Bill Karwin
sumber
3
"Itu ketergantungan pada sesuatu selain kunci kandidat keseluruhan." - Terima kasih
gnsb
12
"Jadi di setiap meja yang hanya memiliki satu kunci kandidat dan dalam 3NF" - Tidak cukup. Contoh yang Anda berikan memenuhi persyaratan ini. Namun, ini bukan contoh 3NF karena bukan 2NF. Kunci (1NF), seluruh kunci (2NF), dan tidak lain adalah kunci (3NF). Kuncinya adalah (Pizza, Topping), dan kolom ToppingType tergantung pada kunci dan tidak lain adalah kunci, tetapi itu tidak tergantung pada keseluruhan kunci. Oleh karena itu bukan 2NF, dan dengan demikian bukan 3NF atau BCNF. Itu adalah 1NF. Menjadikannya 2NF akan mem-bypass masalah yang Anda coba gambarkan.
Daniel Barbalace
4
@DanielBarbalace, Maksud dari tabel ini adalah ia memiliki kunci kandidat alternatif untuk tabel ini: (Pizza, ToppingType). Karena ToppingType adalah bagian dari kunci kandidat itu, ia memuaskan 2NF.
Bill Karwin
6
Maaf saya harus downvote. Contoh yang Anda tunjukkan tidak dalam 3NF. Untuk memahami tujuan BCNF, saya harus melihat contohnya di 3NF tetapi bukan BCNF. Saat ini, saya tidak melihat tujuan BCNF.
Spero
5
Mengapa ini TIDAK ditangani di 2NF? Dari sudut pandang saya, kunci utama tabel asli adalah Pizza + Topping, dan Topping Type tergantung pada Topping, jadi bukankah itu ketergantungan sebagian yang harus dijaga pada tahap 2NF?
GreenPenguin
91

Perbedaan yang halus adalah bahwa 3NF membuat perbedaan antara atribut kunci dan non-kunci (juga disebut atribut non-prima ) sedangkan BCNF tidak.

Ini paling baik dijelaskan menggunakan definisi Zaniolo tentang 3NF, yang setara dengan Codd:

Suatu relasi, R, dalam 3NF iff untuk setiap FD nontrivial (X-> A) dipenuhi oleh R setidaknya SATU dari kondisi berikut ini benar:

(a) X adalah superkey untuk R, atau

(B) A adalah atribut utama untuk R

BCNF membutuhkan (a) tetapi tidak memperlakukan (b) sebagai kasus khusus sendiri. Dengan kata lain BCNF mensyaratkan bahwa setiap penentu nontrivial adalah superkey bahkan atribut dependennya kebetulan menjadi bagian dari kunci.

Suatu relasi, R, ada dalam BCNF iff untuk setiap FD nontrivial (X-> A) yang dipenuhi oleh R kondisi berikut ini benar:

(a) X adalah superkey untuk R

Karena itu BCNF lebih ketat.

Perbedaannya sangat halus sehingga apa yang banyak orang gambarkan sebagai 3NF secara informal sebenarnya adalah BCNF. Sebagai contoh, Anda menyatakan di sini bahwa 3NF berarti "data tergantung pada kunci [s] ... dan tidak ada apa pun selain kunci [s]", tetapi itu benar-benar deskripsi informal BCNF dan bukan 3NF. 3NF dapat lebih akurat digambarkan sebagai " data non-kunci tergantung pada kunci ... dan tidak lain kecuali kunci".

Anda juga menyatakan:

kutipan 3NF secara eksplisit mengatakan "apa-apa selain kunci" yang berarti bahwa semua atribut hanya bergantung pada kunci primer.

Itu penyederhanaan yang berlebihan. 3NF dan BCNF dan semua Formulir Normal berkaitan dengan semua kunci kandidat dan / atau superkeys, bukan hanya satu kunci "primer".

nvogel
sumber
7
Wow. Zaniolo sebenarnya mengajar kelas saya (CS 143, UCLA), dan saya menemukan jawaban ini sambil mempersiapkan ujian akhir. Senang melihat nama prof saya, dan terima kasih atas jawaban terperinci!
DV.
dapatkah Anda memberikan contoh relasi yang ada di 3NF tetapi tidak di BCNF? sulit bagiku untuk membayangkan ...
Leo
10
R {A, B, C} di mana {A, B} adalah kunci. Mengingat ketergantungan C-> B, R memenuhi persyaratan 3NF tetapi tidak BCNF.
nvogel
2
Kunci berarti kunci kandidat. Atribut kunci berarti atribut yang merupakan bagian dari kunci kandidat, AKA atribut utama .
nvogel
3
Atribut adalah prima jika itu adalah bagian dari kunci kandidat; non-prima jika itu bukan bagian dari kunci kandidat.
nvogel
26

Perbedaan antara BCNF dan 3NF

Menggunakan definisi BCNF

Jika dan hanya jika untuk setiap dependensinya X → Y, setidaknya satu dari kondisi berikut berlaku :

  • X → Y adalah ketergantungan fungsional yang sepele (Y ⊆ X), atau
  • X adalah kunci super untuk skema R

dan definisi 3NF

Jika dan hanya jika, untuk masing-masing dependensi fungsionalnya X → A, setidaknya satu dari kondisi berikut ini berlaku:

  • X mengandung A (yaitu, X → A adalah dependensi fungsional yang sepele), atau
  • X adalah superkey, atau
  • Setiap elemen AX, perbedaan set antara A dan X, adalah atribut utama (yaitu, setiap atribut dalam AX terkandung dalam beberapa kunci kandidat)

Kami melihat perbedaan berikut, secara sederhana:

  • Di BCNF : Setiap kunci parsial (atribut utama) hanya dapat bergantung pada superkey,

sedangkan

  • Dalam 3NF : Kunci parsial (atribut prima) juga dapat bergantung pada atribut yang bukan superkey (yaitu atribut kunci parsial / primer lainnya atau bahkan atribut non-prima).

Dimana

  1. Sebuah atribut utama adalah atribut ditemukan di sebuah kunci kandidat, dan
  2. Sebuah kunci kandidat adalah superkey minimal untuk hubungan itu, dan
  3. Sebuah superkey adalah seperangkat atribut dari variabel hubungan yang memegang bahwa dalam semua hubungan ditugaskan untuk variabel itu, tidak ada dua tupel yang berbeda (baris) yang memiliki nilai yang sama untuk atribut dalam set.Equivalently superkey juga bisa didefinisikan sebagai seperangkat atribut dari skema hubungan di mana semua atribut skema tergantung secara fungsional. (Superkey selalu berisi kunci kandidat / kunci kandidat selalu merupakan subset dari superkey. Anda bisa menambahkan atribut apa pun dalam relasi untuk mendapatkan salah satu dari superkey tersebut.)

Artinya, tidak ada subset parsial (subset non trivial kecuali set lengkap) dari kunci kandidat yang secara fungsional tergantung pada apa pun selain superkey.

Tabel / relasi yang tidak ada dalam BCNF tunduk pada anomali seperti pembaruan anomali yang disebutkan dalam contoh pizza oleh pengguna lain. Sayangnya,

  • BNCF tidak selalu dapat diperoleh , sementara
  • 3NF selalu dapat diperoleh .

Contoh 3NF vs. BCNF

Contoh perbedaan saat ini dapat ditemukan di " tabel 3NF tidak memenuhi BCNF (bentuk normal Boyce-Codd) " di Wikipedia, di mana tabel berikut ini bertemu 3NF tetapi bukan BCNF karena "Lapangan Tenis" (atribut kunci / atribut parsial) tergantung pada "Jenis Jenis" (atribut kunci parsial / utama yang tidak superkey), yang merupakan ketergantungan yang dapat kita tentukan dengan bertanya kepada klien dari basis data, klub tenis:

Pemesanan Lapangan Tenis Hari Ini ( 3NF, bukan BCNF )

Court   Start Time  End Time    Rate Type
------- ----------  --------    ---------
1       09:30       10:30       SAVER
1       11:00       12:00       SAVER
1       14:00       15:30       STANDARD
2       10:00       11:30       PREMIUM-B
2       11:30       13:30       PREMIUM-B
2       15:00       16:30       PREMIUM-A

Superkeys tabel adalah:

S1 = {Court, Start Time}
S2 = {Court, End Time}
S3 = {Rate Type, Start Time}
S4 = {Rate Type, End Time}
S5 = {Court, Start Time, End Time}
S6 = {Rate Type, Start Time, End Time}
S7 = {Court, Rate Type, Start Time}
S8 = {Court, Rate Type, End Time}
ST = {Court, Rate Type, Start Time, End Time}, the trivial superkey

Masalah 3NF : Atribut kunci / utama atribut "Pengadilan" tergantung pada sesuatu selain dari superkey. Sebaliknya, itu tergantung pada kunci parsial / atribut utama "Tipe Harga". Ini berarti bahwa pengguna harus secara manual mengubah jenis tarif jika kami memutakhirkan pengadilan, atau mengubah pengadilan secara manual jika ingin menerapkan perubahan tarif.

  • Tetapi bagaimana jika pengguna meningkatkan pengadilan tetapi tidak ingat untuk meningkatkan tarif? Atau bagaimana jika jenis kurs yang salah diterapkan ke pengadilan?

(Dalam istilah teknis, kami tidak dapat menjamin bahwa ketergantungan fungsional "Tipe Tipe" -> "Pengadilan" tidak akan dilanggar.)

Solusi BCNF : Jika kita ingin menempatkan tabel di atas dalam BCNF kita dapat menguraikan relasi / tabel yang diberikan ke dalam dua relasi / tabel berikut (dengan asumsi kita tahu bahwa tipe kurs bergantung hanya pada status pengadilan dan keanggotaan, yang kita dapat temukan dengan bertanya kepada klien dari basis data kami, pemilik klub tenis):

Jenis Nilai ( BCNF dan 3NF yang lebih lemah, yang tersirat oleh BCNF)

Rate Type   Court   Member Flag
---------   -----   -----------
SAVER       1       Yes
STANDARD    1       No
PREMIUM-A   2       Yes
PREMIUM-B   2       No

Pemesanan Lapangan Tenis Hari Ini ( BCNF dan yang lebih lemah 3NF, yang tersirat oleh BCNF)

Member Flag     Court     Start Time   End Time
-----------     -----     ----------   --------
Yes             1         09:30        10:30
Yes             1         11:00        12:00
No              1         14:00        15:30
No              2         10:00        11:30
No              2         11:30        13:30
Yes             2         15:00        16:30

Masalah terpecahkan : Sekarang jika kami memutakhirkan pengadilan, kami dapat menjamin jenis tarif akan mencerminkan perubahan ini, dan kami tidak dapat membebankan harga yang salah untuk pengadilan.

(Dalam istilah teknis, kami dapat menjamin bahwa ketergantungan fungsional "Tipe Harga" -> "Pengadilan" tidak akan dilanggar.)

AGéoCoder
sumber
6

Semua jawaban bagus. Untuk memasukkannya ke dalam bahasa sederhana [BCNF] Tidak ada kunci parsial yang dapat bergantung pada kunci tersebut.

yaitu Tidak ada subset parsial (yaitu subset non trivial kecuali set lengkap) dari kunci kandidat dapat secara fungsional tergantung pada beberapa kunci kandidat.

smartnut007
sumber
2
Kenapa tidak? Katakanlah ada relasi R (A, B, C, D, E) dan (A, B) dan (C, D) adalah kunci kandidat. Kemudian AB-> D. Karena AB adalah superkey dari R, maka R harus di BCNF, kan? (Hanya sebuah pertanyaan, mencoba memahami hal ini.)
peteykun
3

Jawaban oleh ' smartnut007 ', ' Bill Karwin ', dan ' sqlvogel ' sangat baik. Namun izinkan saya menempatkan perspektif yang menarik untuk itu.

Yah, kami memiliki kunci prima dan non-prima.

Ketika kita fokus pada bagaimana non-primes bergantung pada primes, kita melihat dua kasus:

Non-prima dapat bergantung atau tidak .

  • Ketika tergantung: kita melihat mereka harus bergantung pada kunci kandidat penuh. Ini adalah 2NF .
  • Ketika tidak tergantung: mungkin tidak ada ketergantungan atau ketergantungan transitif

    • Ketergantungan bahkan tidak transitif: Tidak yakin apa teori normalisasi membahas ini.
    • Ketika tergantung secara transitif: Itu dianggap tidak diinginkan. Ini adalah 3NF .

Bagaimana dengan dependensi di antara bilangan prima?

Sekarang Anda tahu, kami tidak membahas hubungan ketergantungan antara bilangan prima dengan NF ke-2 atau ke-3. Lebih lanjut ketergantungan seperti itu, jika ada, tidak diinginkan dan oleh karena itu kami memiliki satu aturan untuk mengatasinya. Ini BCNF .

Mengacu pada contoh dari posting Bill Karwin di sini, Anda akan melihat bahwa ' Topping ', dan ' Topping Type ' adalah kunci utama dan memiliki ketergantungan. Jika mereka non-prima dengan ketergantungan, maka 3NF akan menendang.

catatan:

Definisi BCNF sangat generik dan tanpa membedakan atribut antara prima dan non-prima. Namun, cara berpikir di atas membantu untuk memahami bagaimana beberapa anomali diserap bahkan setelah NF ke-2 dan ke-3.

Topik Tingkat Lanjut: Memetakan BCNF umum ke 2NF & 3NF

Sekarang kita tahu BCNF memberikan definisi umum tanpa referensi ke atribusi utama / non-prima, mari kita lihat bagaimana BCNF dan 2/3 NF saling terkait.

Pertama, BCNF mensyaratkan (selain dari kasus sepele) bahwa untuk setiap ketergantungan fungsional X -> Y(FD), X harus super-kunci. Jika Anda hanya mempertimbangkan FD, maka kami memiliki tiga kasus - (1) Baik X dan Y non-prima, (2) Baik prima dan (3) X prima dan Y non-prima, membuang kasus (tidak masuk akal) X non -prime dan Y prime.

Untuk kasus (1), 3NF menangani.

Untuk kasus (3), 2NF menangani.

Untuk kasus (2), kami menemukan penggunaan BCNF

KGhatak
sumber
3

Ini adalah pertanyaan lama dengan jawaban yang berharga, tetapi saya masih agak bingung sampai saya menemukan contoh kehidupan nyata yang menunjukkan masalah dengan 3NF. Mungkin tidak cocok untuk anak berusia 8 tahun tetapi harap ini membantu.

Besok saya akan bertemu para guru putri sulung saya di salah satu pertemuan orang tua / guru triwulanan itu. Seperti apa buku harian saya (nama dan kamar telah diubah):

Teacher   | Date             | Room
----------|------------------|-----
Mr Smith  | 2018-12-18 18:15 | A12 
Mr Jones  | 2018-12-18 18:30 | B10 
Ms Doe    | 2018-12-18 18:45 | C21 
Ms Rogers | 2018-12-18 19:00 | A08 

Hanya ada satu guru per kamar dan mereka tidak pernah bergerak. Jika Anda melihat-lihat, Anda akan melihat bahwa: (1) untuk setiap atribut Teacher, Date, Room, kita hanya memiliki satu nilai per baris. (2) super-kunci adalah: (Teacher, Date, Room),(Teacher, Date) dan (Date, Room)dan kunci kandidat yang jelas (Teacher, Date)dan (Date, Room).

(Teacher, Room) bukan superkey karena saya akan menyelesaikan tabel kuartal berikutnya dan saya mungkin memiliki baris seperti ini (Mr Smith tidak bergerak!):

Teacher  | Date             | Room
---------|------------------| ----
Mr Smith | 2019-03-19 18:15 | A12

Apa yang bisa kita simpulkan? (1) adalah formulasi 1NF informal tetapi benar. Dari (2) kita melihat bahwa tidak ada "atribut non prime": 2NF dan 3NF diberikan secara gratis.

Buku harian saya adalah 3NF. Baik! Tidak. Tidak juga karena tidak ada pemodel data yang akan menerima ini dalam skema DB. The Roomatribut tergantung padaTeacher atribut (lagi: guru tidak bergerak!) Tapi skema tidak mencerminkan fakta ini. Apa yang akan dilakukan oleh pemodel data yang waras? Bagi tabel menjadi dua:

Teacher   | Date
----------|-----------------
Mr Smith  | 2018-12-18 18:15
Mr Jones  | 2018-12-18 18:30
Ms Doe    | 2018-12-18 18:45
Ms Rogers | 2018-12-18 19:00

Dan

Teacher   | Room
----------|-----
Mr Smith  | A12
Mr Jones  | B10
Ms Doe    | C21
Ms Rogers | A08

Tetapi 3NF tidak berurusan dengan dependensi atribut prima. Ini masalahnya: Kepatuhan 3NF tidak cukup untuk memastikan desain skema tabel suara dalam beberapa keadaan.

Dengan BCNF, Anda tidak peduli apakah atributnya adalah atribut utama atau tidak dalam aturan 2NF dan 3NF. Untuk setiap ketergantungan non-sepele (himpunan bagian jelas ditentukan oleh superset mereka), penentu adalah kunci super lengkap.Dengan kata lain, tidak ada yang ditentukan oleh sesuatu selain dari kunci super lengkap (tidak termasuk FD sepele). (Lihat jawaban lain untuk definisi formal).

Begitu Roomtergantung pada Teacher, Roomharus menjadi bagian dari Teacher(bukan itu masalahnya) atauTeacher harus menjadi kunci super (itu tidak terjadi dalam buku harian saya, tapi itulah yang terjadi ketika Anda membagi tabel).

Untuk meringkas: BNCF lebih ketat, tetapi menurut saya lebih mudah dipahami, daripada 3NF:

  • dalam kebanyakan kasus, BCNF identik dengan 3NF;
  • dalam kasus lain, BCNF adalah apa yang Anda pikirkan / harapkan 3NF.
jferard
sumber