Ayrıştırma: kayıpsız birleştirme, bağımlılık koruma, BCNF ve 3NF algoritmaları

Geçen hafta bir şemanın hangi normal formda olduğunu bulmayı öğrendin. Normal form düşükse çözüm şemayı parçalara ayırmak (decomposition). Ama her bölme iyi değil. Bir ayrıştırmadan iki şey istersin:

1. Kayıpsız birleştirme (lossless join): Parçaları NATURAL JOIN ile geri birleştirince tam olarak orijinal tablo çıkmalı.
2. Bağımlılık koruma (dependency preservation): Her FD, join yapmadan tek tek parçalarda denetlenebilmeli.

Sınavda tipik sorular: “Is this decomposition lossless?”, “Is it dependency preserving?”, “Decompose R into BCNF”, “Apply the 3NF synthesis algorithm”.

Kayıplı ayrıştırma: veride görelim

Örnek veritabanından öğrencinin bölümünü ve aldığı dersi tutan bir tablo türet (bölümü NULL olan S7 dışarıda): enr(stu_id, dept_name, course_id), 13 satır. Tek FD: $\text{stu\_id} \to \text{dept\_name}$.

Şimdi bunu yanlış yerden bölelim:

CREATE TABLE r1 AS SELECT DISTINCT stu_id, dept_name FROM enr;    -- 5 satır
CREATE TABLE r2 AS SELECT DISTINCT dept_name, course_id FROM enr; -- 10 satır
SELECT COUNT(*) FROM r1 NATURAL JOIN r2;

18

13 satırlık tablo 18 satır olarak geri geldi. Fazlalığı EXCEPT ile görebilirsin:

SELECT stu_id, dept_name, course_id FROM r1 NATURAL JOIN r2
EXCEPT SELECT * FROM enr;

Bu satırlara sahte satır (spurious tuple) denir. Neden sadece CS? Join dept_name üzerinden yapılıyor ve CS’de üç öğrenci var (S1, S2, S5). r2, “bir CS öğrencisi bu dersi aldı” bilgisini tutuyor ama hangi öğrenci olduğunu kaybetmiş. EE’de ve MATH’te tek öğrenci olduğu için orada karışıklık çıkmıyor.

TUZAK · “kayıplı” satır kaybetmek demek değil. Kayıplı ayrıştırmada join daha fazla satır üretir. Kaybedilen şey bilgi: hangi satırın gerçek olduğunu artık bilemezsin.

Doğru bölme: r1(stu_id, dept_name) ve r3(stu_id, course_id). Kesişim stu_id, ve $\text{stu\_id} \to \text{dept\_name}$ olduğu için stu_id r1’in anahtarı. r1 NATURAL JOIN r3 tam 13 satır verir, EXCEPT sonucu boş.

İkili test (binary decomposition)

$R$‘yi $R_1$ ve $R_2$‘ye bölüyorsan, ayrıştırma ancak ve ancak şu FD’lerden biri $F^+$‘da ise kayıpsızdır:

$R_1 \cap R_2 \to R_1 \qquad \text{ya da} \qquad R_1 \cap R_2 \to R_2$

Yani kesişim, parçalardan birinin süper anahtarı olmalı. Hesap: kesişimin closure’ını al.

$R(A,B,C,D)$, $F = \{A \to B,\ C \to D\}$:

Üç ve daha fazla parça: chase testi

İkili test sadece iki parça için. Daha fazlası için tablo (tableau) yöntemi:

1. Sütunlar R’nin öznitelikleri, her parça bir satır.
2. Satırda parçanın içerdiği sütunlara a, diğerlerine b (satıra özel) yaz.
3. Her $X \to Y$ için: X sütunlarında aynı olan iki satırın Y değerlerini eşitle (biri a ise ikisi de a olur).
4. Değişiklik bitene kadar tekrarla. Tamamen a’dan oluşan bir satır çıkarsa kayıpsız.

Çözümlü örnek. $R(A,B,C,D,E)$, $F = \{A \to B,\ C \to D,\ BD \to E\}$, parçalar (A,B), (C,D), (A,C,E).

         A    B    C    D    E
R1(AB)   a    a    b    b    b
R2(CD)   b    b    a    a    b
R3(ACE)  a    b    a    b    a

A -> B : R1 ve R3 A'da eşit  → R3.B = a
C -> D : R2 ve R3 C'de eşit  → R3.D = a
R3     : a    a    a    a    a      → KAYIPSIZ

Aynı F ile (A,B), (C,D), (B,D,E) denersen hiçbir FD uygulanamaz (A’da ya da C’de eşit iki satır yok, BD’de eşit iki satır yok) ve tamamen a satırı oluşmaz: kayıplı. Bir sezgi (kural değil): ilk örnekte kazanan satır, aday anahtar AC’yi içeren R3 oldu. İkinci örnekte A ile C’yi birlikte tutan parça yok.

Bağımlılık koruma (dependency preservation)

$F_i$, $F^+$‘nın $R_i$‘ye izdüşümü (projection) olsun: $F^+$‘daki, tüm öznitelikleri $R_i$ içinde olan FD’ler. Ayrıştırma koruyucudur eğer $(F_1 \cup F_2 \cup \dots)^+ = F^+$. Pratik test: F’deki her $X \to Y$ için $X$‘in closure’ını sadece izdüşüm FD’leriyle al; Y çıkıyorsa korunuyor.

Örnek 1. $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ C \to D\}$, parçalar (A,B), (A,C), (C,D).

İzdüşümler: $A \to B$, $A \to C$, $C \to D$. Bu kümeyle $\{B\}^+ = \{B\}$: $B \to C$ kaybolur. Ayrıştırma kayıpsız ama koruyucu değil. Parçaları (A,B), (B,C), (C,D) seçseydin üç FD de bir parçada olurdu.

Örnek 2. $R(A,B,C)$, $F = \{A \to B,\ B \to C,\ C \to A\}$, parçalar (A,B), (B,C). $C \to A$‘yı içeren parça yok. Ama $\{B\}^+ = ABC$ olduğu için AB’ye izdüşümde $B \to A$, BC’ye izdüşümde $C \to B$ var. $C \to B \to A$: $C \to A$ korunuyor.

TUZAK · izdüşüm sadece F’den alınmaz. Bir parçaya düşen FD’leri bulurken F’deki listeye bakıp “bu FD’nin öznitelikleri parçada mı?” demek yetmez. $F^+$‘dan gelen FD’leri de düşünmen gerekir; bunun yolu parçadaki her alt kümenin closure’ını almak.

BCNF ayrıştırma algoritması

sonuç := {R}
sonuçta BCNF olmayan bir Ri oldukça:
    Ri'de geçerli, X süper anahtar olmayan bir X -> Y bul
    Ri yerine  (X+ ∩ Ri)  ve  Ri − (X+ − X)  koy

Her bölmede kesişim X ve X ilk parçanın anahtarı, o yüzden sonuç her zaman kayıpsız. Koruma ise garanti değil.

Çözümlü örnek. $R(A,B,C,D,E)$, $F = \{A \to B,\ BC \to D,\ D \to E\}$. A ve C sağda yok, $\{A,C\}^+$ = ABCDE: tek anahtar AC. Her adımda en kısa ihlal eden sol tarafı seçiyoruz.

ABCDE : A -> B ihlal.  A+ ∩ Ri = AB         →  AB  ve  ACDE
AB    : BCNF
ACDE  : D -> E ihlal.  D+ ∩ Ri = DE         →  DE  ve  ACD
DE    : BCNF
ACD   : izdüşüm AC -> D, AC anahtar         →  BCNF
Sonuç : AB, DE, ACD

Koruma kontrolü: $BC \to D$. B ve C aynı parçada değil, izdüşümlerle $\{B,C\}^+ = \{B,C\}$. Kayboldu. İlk adımda $D \to E$ ile başlasaydın farklı bir sonuç bulabilirdin; ayrıştırma tek değildir, sınavda seçtiğin sırayı yaz.

Üniversite örneği: wide(S, N, C, T, G) = (stu_id, stu_name, course_id, title, grade), $F = \{S \to N,\ C \to T,\ SC \to G\}$. Algoritma CT, NS ve CGS’yi verir: course(course_id, title), student(stu_id, stu_name), takes(stu_id, course_id, grade). Bu sefer üç FD de korunuyor; ders boyunca kullandığımız tabloların neden böyle ayrıldığının cevabı bu.

3NF sentez algoritması (synthesis)

1. F'nin kanonik örtüsünü Fc bul
2. Fc'deki her X -> Y için şema (X ∪ Y) oluştur
3. Hiçbir şema R'nin bir aday anahtarını içermiyorsa, bir aday anahtarı ayrı şema olarak ekle
4. Başka bir şemanın alt kümesi olan şemaları sil

Sonuç hem kayıpsız hem bağımlılık koruyan bir 3NF ayrıştırmasıdır.

Aynı örnek: $F_c = \{A \to B,\ BC \to D,\ D \to E\}$ (gereksiz bir şey yok). Şemalar AB, BCD, DE. Hiçbiri AC’yi içermiyor, AC ekle. Sonuç AB, BCD, DE, AC. Chase testi kayıpsız diyor, üç FD de birer parçanın içinde. Bu örnekte parçaların hepsi BCNF bile çıktı; her zaman böyle olmaz.

BCNF mi 3NF mi?

Klasik ikilem: tutoring(stu_id, subject, tutor_id), $\text{tutor\_id} \to \text{subject}$, $\{\text{stu\_id, subject}\} \to \text{tutor\_id}$. BCNF ayrıştırma (tutor_id, subject) ve (stu_id, tutor_id) verir. Kayıpsız ama “bir öğrenci bir konuda tek öğretici” kuralı artık tek tabloda denetlenemiyor. Tasarımcı çoğu zaman 3NF’de kalıp bu kuralı korumayı seçer.

Sık yapılan hatalar