Kanonik örtü ve normal formlar: 1NF, 2NF, 3NF, BCNF

Geçen hafta closure ve anahtar bulmayı gördün. Bu hafta onları kullanarak iki şey yapacaksın: FD kümesini en sade hâline indirmek (kanonik örtü) ve bir şemanın en yüksek normal formunu bulmak. Sınavda “What is the highest normal form of R?” sorusu neredeyse garantidir. Reçete hep aynı:

1. Tüm aday anahtarları bul.
2. Asal (prime) öznitelikleri yaz: en az bir aday anahtarda geçenler.
3. Her aşikar olmayan FD’yi sırayla BCNF, 3NF, 2NF testinden geçir.

Kanonik örtü (canonical cover)

Aynı bilgiyi taşıyan çok sayıda FD kümesi olabilir. Kanonik örtü $F_c$, $F$ ile eşdeğer (aynı $F^+$) ama gereksiz hiçbir şey içermeyen kümedir:

• Hiçbir FD’de gereksiz öznitelik (extraneous attribute) yok.
• Her sol taraf tektir ($A \to B$ ve $A \to C$ yerine $A \to BC$).

Gereksiz öznitelik testi

TUZAK · hangi F altında? Sol taraf testinde closure değiştirilmemiş F ile alınır. Sağ taraf testinde ise FD’yi kısaltılmış hâliyle küme içine koyup closure alırsın. İkisini karıştırmak yanlış “gereksiz” kararları doğurur.

Çözümlü örnek

$F = \{A \to BD,\ AB \to C,\ C \to D,\ B \to D\}$

1) Sağları böl:      A -> B, A -> D, AB -> C, C -> D, B -> D

2) Sol taraflar:     AB -> C içinde B gereksiz mi?
                     {A}+ (F altında): A -> B, A -> D, AB -> C  →  ABCD   C var → B gereksiz
                     A gereksiz mi? {B}+ = BD, C yok → değil
                     FD:  A -> C

3) Gereksiz FD'ler:  A -> D atılırsa: {A}+ = A -> B, A -> C, C -> D → ABCD   D var → at
                     B -> D atılırsa: {B}+ = B, D yok → gerekli
                     C -> D atılırsa: {C}+ = C, D yok → gerekli
                     A -> B atılırsa: {A}+ = ACD, B yok → gerekli
                     A -> C atılırsa: {A}+ = ABD, C yok → gerekli

4) Birleştir:        Fc = { A -> BC,  B -> D,  C -> D }

Son kontrol: $F_c$ ile $F$ eşdeğer mi? $F$‘deki her FD $F_c$‘den türetiliyor ve tersi de doğru. Eşdeğer.

İPUCU · kanonik örtü tek değildir. Gereksiz testi farklı sırada yaparsan farklı ama eşdeğer bir $F_c$ bulabilirsin. Sınavda adımlarını yazarsan iki cevap da kabul görür. Bu sayfadaki örnekler soldan sağa sırayla çözüldü.

Birinci normal form (1NF)

Bir şema, her özniteliğin değer alanı atomik (atomic domain) ise 1NF’dedir: hücrede liste, küme ya da tekrar eden grup yok.

Bu tablo 1NF değil. Düzeltme: student_phone(stu_id, phone) ayrı tablosu, her telefon ayrı satır. İlişkisel modelde her tablo varsayılan olarak 1NF kabul edilir; bundan sonraki formlar FD’lere bakar.

İkinci normal form (2NF)

1NF + hiçbir asal olmayan öznitelik, bir aday anahtarın öz alt kümesine bağlı değil. Bu yasak duruma kısmi bağımlılık (partial dependency) denir.

Üniversite örneği: takes_wide(stu_id, course_id, grade, stu_name, title), FD’ler $\{\text{stu\_id, course\_id}\} \to \text{grade}$, $\text{stu\_id} \to \text{stu\_name}$, $\text{course\_id} \to \text{title}$.

Tek anahtar {stu_id, course_id}. stu_name sadece stu_id’ye bağlı, title sadece course_id’ye. İkisi de kısmi bağımlılık: en yüksek 1NF. Geçen haftaki geniş tablonun güncelleme anomalisi tam olarak buradan geliyordu.

Harfli örnek: $R(A,B,C,D)$, $F = \{AB \to C,\ B \to D\}$. Anahtar AB, $B \to D$ kısmi: 1NF.

TUZAK · tek öznitelikli anahtar. Bütün aday anahtarlar tek öznitelikliyse kısmi bağımlılık imkânsız; şema 1NF ise otomatik olarak 2NF’dir. Bu durumda 2NF testini atlayıp doğrudan 3NF’ye bak.

Üçüncü normal form (3NF)

Her aşikar olmayan $X \to A$ için şunlardan en az biri doğru olmalı:

1. $X$ bir süper anahtar, ya da
2. $A$ asal (prime) bir öznitelik.

Bozan tipik durum geçişli bağımlılık (transitive dependency): anahtar → anahtar olmayan → anahtar olmayan.

Üniversite örneği: student_dept(stu_id, name, dept_name, building), FD’ler $\text{stu\_id} \to \text{name, dept\_name}$, $\text{dept\_name} \to \text{building}$. Anahtar stu_id (tek öznitelik, 2NF otomatik). $\text{dept\_name} \to \text{building}$: dept_name süper anahtar değil, building asal değil. 3NF bozuluyor: en yüksek 2NF.

Harfli örnek: $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ A \to D\}$: anahtar A, $B \to C$ geçişli, 2NF.

Boyce-Codd normal form (BCNF)

Her aşikar olmayan $X \to Y$ için $X$ süper anahtar olmalı. 3NF’deki “ya da A asal” kaçış yolu yok. Her BCNF şema 3NF’dir; tersi her zaman doğru değil.

3NF olup BCNF olmayan klasik durum: anahtar olmayan bir öznitelik, bir anahtarın parçasını belirliyor. Üniversite örneği: tutoring(stu_id, subject, tutor_id). Kurallar: her öğretici (tutor) tek konuya bakar, her öğrenci her konu için tek öğreticiyle çalışır.

$\text{tutor\_id} \to \text{subject} \qquad \{\text{stu\_id, subject}\} \to \text{tutor\_id}$

Anahtarlar: {stu_id, subject} ve {stu_id, tutor_id}. Üç öznitelik de asal. $\text{tutor\_id} \to \text{subject}$: tutor_id süper anahtar değil, BCNF ihlali. Ama subject asal, 3NF sağlanıyor. En yüksek 3NF.

Harfli karşılığı: $R(A,B,C)$, $F = \{AB \to C,\ C \to B\}$, anahtarlar AB ve AC, sonuç 3NF.

Hepsi bir arada: çözümlü tespit

$R(A,B,C,D,E)$, $F = \{AB \to CDE,\ C \to D,\ D \to B\}$.

Anahtarlar:  A sağda yok → her anahtarda
             {A}+ = A
             {A,B}+ = ABCDE   anahtar
             {A,C}+: C -> D, D -> B, AB -> CDE  = ABCDE  anahtar
             {A,D}+: D -> B, AB -> CDE          = ABCDE  anahtar
             {A,E}+ = AE      değil
Asal:        A, B, C, D        (E asal değil)

AB -> CDE    AB süper anahtar          BCNF uygun
C  -> D      C süper anahtar değil     BCNF ihlali; D asal → 3NF uygun
D  -> B      D süper anahtar değil     BCNF ihlali; B asal → 3NF uygun

Sonuç: 3NF (BCNF değil)

Bir de BCNF örneği: $R(A,B,C,D)$, $F = \{A \to BCD,\ BC \to A\}$. $\{A\}^+$ ve $\{B,C\}^+$ ikisi de ABCD: her sol taraf süper anahtar, BCNF. Üniversitenin course(course_id, title, dept_name, credits) ve department(dept_name, building, budget) tabloları da aynı nedenle BCNF: tek FD’leri anahtardan çıkıyor.

TUZAK · parçalarda sadece F’ye bakmak. Tüm şemayı test ederken F’deki FD’lere bakmak yeter. Ama ayrıştırılmış bir parçayı test ederken $F^+$‘nın o parçaya izdüşümünü (projection) düşünmen gerekir: parçada görünmeyen bir ara öznitelik üzerinden gelen FD’ler de sayılır. Gelecek hafta bunu kullanacağız.

Normal formlar özet tablosu

Sık yapılan hatalar