Kötü tasarım, fonksiyonel bağımlılıklar ve closure

Normalizasyon (normalization) bölümünün ilk haftası. Vizeden sonraki sınavda en garantili puanlar buradan gelir, çünkü soruların çoğu mekanik: closure hesapla, anahtar bul, FD türet. Bu sayfadaki üç beceri bir sonraki iki haftanın (normal formlar, ayrıştırma) temeli:

1. Tek büyük tablonun neden sorun çıkardığını anomalilerle açıklamak.
2. Bir fonksiyonel bağımlılığın (functional dependency) ne demek olduğunu ve örnek veride sağlanıp sağlanmadığını kontrol etmek.
3. Attribute closure ile süper anahtar ve aday anahtar bulmak.

Kötü tasarım: her şey tek tabloda

Ders boyunca kullandığımız üniversite veritabanında takes, student, course ve department ayrı tablolar. Bunları tek bir “geniş” tabloda birleştirdiğini düşün:

CREATE TABLE wide AS
SELECT t.stu_id, s.name AS stu_name, t.course_id, c.title, c.credits,
       c.dept_name AS course_dept, d.building, t.grade
FROM takes t JOIN student s ON s.stu_id = t.stu_id
             JOIN course c ON c.course_id = t.course_id
             JOIN department d ON d.dept_name = c.dept_name;

Sonuç 14 satır (stu_name ve credits sütunlarını yer kazanmak için göstermiyorum):

Sorgu yazmak kolaylaştı ama tablo üç tür hataya açık:

Kök neden: tablo birbirinden bağımsız gerçekleri (bir dersin adı, bir bölümün binası, bir öğrencinin notu) aynı satıra sıkıştırıyor. Bu gerçekleri biçimsel olarak ifade etmenin yolu fonksiyonel bağımlılık.

Fonksiyonel bağımlılık (functional dependency)

$X$ ve $Y$, $R$ şemasının öznitelik kümeleri olsun. $X \to Y$ şu demek: $X$ değerleri aynı olan her iki satırın $Y$ değerleri de aynıdır. ”$X$, $Y$‘yi belirler” diye okunur.

Geniş tablo için gerçek dünya kuralları:

• $\text{stu\_id} \to \text{stu\_name}$
• $\text{course\_id} \to \text{title, credits, course\_dept}$
• $\text{course\_dept} \to \text{building}$
• $\text{stu\_id, course\_id} \to \text{grade}$

Bu FD’lerden {stu_id, course_id} tablonun tek aday anahtarı çıkıyor (aşağıda nasıl bulunacağını göreceksin).

Örnek veride kontrol etmek

Bir FD’nin ihlali için tek bir çift yeter: sol tarafı aynı, sağ tarafı farklı iki satır. SQL ile bunu gruplayarak bulursun:

-- building -> course_dept sağlanıyor mu?
SELECT building FROM wide
GROUP BY building
HAVING COUNT(DISTINCT course_dept) > 1;

Galata

Galata hem CS hem EE ile eşleşiyor: $\text{building} \to \text{course\_dept}$ ihlal. Aynı sorguyu course_id/title ya da course_dept/building için çalıştırınca sonuç boş, yani bu FD’ler bu örnekte sağlanıyor. credits -> course_dept için sorgu 3 ve 4 değerlerini döndürür (4 kredilik dersler hem CS hem MATH).

TUZAK · örnek veri kanıt değildir. Sorgu boş döndüyse FD bu satırlarda ihlal edilmiyor demektir, şemada geçerli demek değildir. Yarın gelecek bir satır onu bozabilir. FD bir tasarım kararıdır (gerçek dünya kuralı); veri onu sadece çürütebilir.

Aşikar bağımlılık (trivial dependency)

$Y \subseteq X$ ise $X \to Y$ her ilişkide doğrudur: $AB \to A$, $\{\text{stu\_id, grade}\} \to \text{stu\_id}$. Bilgi taşımazlar. Sınavda “list the non-trivial FDs” denirse bunları yazma.

Armstrong aksiyomları

Verilen FD kümesi $F$‘den başka FD’ler türetilebilir. Türetilebilen her şeyin kümesine $F$‘nin kapanışı (closure of F) denir ve $F^+$ diye yazılır. Üç temel kural yeter (sound ve complete):

Bunlardan türetilen pratik kurallar:

Çözümlü örnek. $F = \{A \to B,\ B \to C,\ CD \to E\}$ verildiğinde $AD \to E$‘yi türet.

1. A -> B, B -> C           geçişlilik     A -> C
2. A -> C, D ekle           genişletme     AD -> CD
3. AD -> CD, CD -> E        geçişlilik     AD -> E

TUZAK · sol tarafı bölemezsin. Ayrışım kuralı sadece sağ taraf için geçerli. $AB \to C$‘den $A \to C$ çıkmaz. “Decomposition” görünce sağ tarafı böldüğünü hatırla.

$F^+$ genelde çok büyük olduğu için elle listelenmez. Pratikte asıl araç öznitelik kümesinin closure’ı.

Öznitelik closure’ı (attribute closure)

$X^+$: $F$ altında $X$‘in belirlediği tüm özniteliklerin kümesi. Algoritma:

sonuç := X
tekrarla:
    F'deki her  L -> M  için:
        L ⊆ sonuç ise  sonuç := sonuç ∪ M
değişiklik olmayana kadar

Çözümlü örnek. $R(A,B,C,D,E,G)$, $F = \{A \to B,\ AC \to D,\ B \to E,\ DE \to G\}$.

{A}+    : A
          A -> B     AB
          B -> E     ABE
          (AC -> D için C yok, DE -> G için D yok)  →  {A,B,E}

{A,C}+  : AC
          A -> B     ABC
          AC -> D    ABCD
          B -> E     ABCDE
          DE -> G    ABCDEG   →  tüm şema

Closure üç soruyu birden cevaplar:

1. $X \to Y$ türetilebilir mi? $Y \subseteq X^+$ ise evet. $\{A\}^+ = \{A,B,E\}$, o yüzden $A \to D$ türetilemez ama $A \to E$ türetilebilir.
2. $X$ süper anahtar (superkey) mı? $X^+ = R$ ise evet. AC süper anahtar.
3. $X$ aday anahtar (candidate key) mı? Süper anahtar ve hiçbir öz alt kümesi süper anahtar değilse evet. $\{A\}^+$ ve $\{C\}^+ = \{C\}$ şemayı vermiyor, AC aday anahtar.

Bütün aday anahtarları bulmak

Kaba kuvvet $2^n$ alt küme demek. Sınavda hızlı yol şu gözlem:

• Hiçbir FD’nin sağında görünmeyen öznitelik başka hiçbir şeyden türetilemez, o yüzden her anahtarda olmak zorunda.
• Sadece sağda görünen (hiç solda olmayan) öznitelik hiçbir minimal anahtarda olmaz.
• Önce “zorunlu” kümenin closure’ını al. Yetmiyorsa ona sırayla birer öznitelik ekle, sonra ikişer. Bulduğun anahtarın üst kümelerini atla.

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

Sağda hiç olmayan: B          → her anahtarda B var
{B}+ = {B}                     → yetmez
{A,B}+: AB -> C, C -> D, D -> E          = ABCDE   anahtar
{B,C}+: C -> D, D -> E, E -> A, AB -> C  = ABCDE   anahtar
{B,D}+: D -> E, E -> A, AB -> C          = ABCDE   anahtar
{B,E}+: E -> A, AB -> C, C -> D          = ABCDE   anahtar

Dört aday anahtar: AB, BC, BD, BE. Üçlü kümeleri denemene gerek yok, hepsi bunlardan birini içerir.

Döngü içeren bir örnek: $R(A,B,C,D)$, $F = \{A \to B,\ B \to C,\ C \to A\}$. D hiçbir sağda yok, $\{D\}^+ = \{D\}$. A, B ya da C’den herhangi biri döngüyü tamamlar: anahtarlar AD, BD, CD.

İPUCU · süper anahtar sayısı. Aday anahtar tekse ve $k$ öznitelikliyse, $n$ öznitelikli şemada süper anahtar sayısı $2^{n-k}$ olur (anahtar artı kalanların herhangi bir alt kümesi). $R(A,B,C,D)$, anahtar A: $2^3 = 8$ süper anahtar. Birden çok anahtar varsa kesişimleri çift saymamaya dikkat et.

Geniş tabloya dönersek, harflerle yaz: S = stu_id, N = stu_name, C = course_id, T = title, K = credits, D = course_dept, B = building, G = grade. $F = \{S \to N,\ C \to TKD,\ D \to B,\ SC \to G\}$. S ve C sağda yok, $\{S,C\}^+$ her şeyi veriyor: tek aday anahtar {stu_id, course_id}. $\{C\}^+ = \{C,T,K,D,B\}$: anahtarın sadece bir parçası bu kadar özniteliği belirliyor. Gelecek hafta bunun adını koyacağız: kısmi bağımlılık (partial dependency).

Sık yapılan hatalar