İşlevsel Bağımlılık

İlişkisel Model konusu şemayı kurdu ama tek bir soruyu yanıtsız bıraktı: hangi sütun hangi bağıntıya konmalı? Kursun ilk dersindeki odunc.csv dosyasında üye adı üç satırda tekrar ediyor, e-posta değişikliği üç yerde düzeltme gerektiriyordu. Bu dersin sorusu şudur: o tekrarın kaynağı nedir ve nasıl biçimsel olarak adlandırılır?

Yanıt tek bir kavramdadır. Bir sütun kümesinin değeri, başka bir sütun kümesinin değerini belirliyorsa aralarında bir bağımlılık vardır; tekrar, bu bağımlılığın yanlış yere yerleştirilmesinden doğar.

Tanım ve Gösterim

$R$ bağıntısının öznitelik kümesi $H$, ve $X, Y \subseteq H$ olsun. $R$’nin her geçerli değerinde, $X$ üzerinde aynı değerleri taşıyan iki satır $Y$ üzerinde de aynı değerleri taşıyorsa, $Y$ özniteliklerinin $X$’e işlevsel bağımlı (functionally dependent) olduğu söylenir ve şöyle yazılır:

$$X \to Y$$

Okunuşu “$X$, $Y$’yi belirler”dir. Kütüphane alanında birkaç örnek:

• $\text{üye no} \to \text{üye adı}, \text{üye e-postası}$ — üye numarası bilinince üyenin adı ve adresi bellidir.
• $\text{ISBN} \to \text{kitap başlığı}, \text{kitap yazarı}$
• $\text{şube kodu} \to \text{şube adı}$
• $\text{ödünç no} \to$ diğer bütün öznitelikler.

Son satır, bir önceki konudaki süperanahtar tanımının bağımlılık diliyle yazılışıdır: $K$ bir süperanahtardır ancak ve ancak $K \to H$ ise. Aday anahtar ise bu özelliği taşıyan en küçük kümedir. Anahtar kavramı, bağımlılık kavramının özel bir durumudur.

Bağımlılık Anlamdan Gelir

Kritik nokta şudur: işlevsel bağımlılık, bugünkü veriden okunmaz. Bugünkü veri bir bağımlılığı yalnızca çürütebilir; doğrulayamaz. Bağımlılık, alanın kuralından gelir.

Aradaki farkı bir örnek üzerinde saymak, bağımlılık adaylarını elemenin en hızlı yoludur:

const basliklar = "odunc_no uye_no uye_ad isbn kitap_baslik sube_kodu sube_ad".split(" ");
const veri = [
  "1001 41 Ayse_Demir 975-01 Kayip_Zaman MRK Merkez",
  "1002 52 Mert_Kaya 975-01 Kayip_Zaman MRK Merkez",
  "1003 41 Ayse_Demir 975-02 Deniz_Fenerleri BHC Bahcelievler",
  "1004 41 Ayse_Demir 975-01 Kayip_Zaman MRK Merkez",
  "1005 63 Ayse_Demir 975-02 Deniz_Fenerleri MRK Merkez",
  "1006 52 Mert_Kaya 975-03 Sessiz_Bahce BHC Bahcelievler",
].map((s) => Object.fromEntries(s.split(" ").map((v, i) => [basliklar[i], v])));

function ihlalSay(sol, sag) {
  const grup = new Map();
  for (const satir of veri) {
    const anahtar = sol.map((a) => satir[a]).join("|");
    const deger = sag.map((a) => satir[a]).join("|");
    if (grup.has(anahtar)) grup.get(anahtar).add(deger);
    else grup.set(anahtar, new Set([deger]));
  }
  return [...grup.values()].filter((d) => d.size > 1).length;
}

const adaylar = [
  [["odunc_no"], ["uye_no"]],
  [["uye_no"], ["uye_ad"]],
  [["uye_ad"], ["uye_no"]],
  [["isbn"], ["kitap_baslik"]],
  [["kitap_baslik"], ["isbn"]],
  [["sube_kodu"], ["sube_ad"]],
  [["uye_no"], ["isbn"]],
];

for (const [sol, sag] of adaylar) {
  const ihlal = ihlalSay(sol, sag);
  const durum = ihlal === 0 ? "veriyle uyumlu" : `${ihlal} grupta ihlal`;
  console.log(`${sol.join(",")} -> ${sag.join(",")}`.padEnd(30), durum);
}

odunc_no -> uye_no             veriyle uyumlu
uye_no -> uye_ad               veriyle uyumlu
uye_ad -> uye_no               1 grupta ihlal
isbn -> kitap_baslik           veriyle uyumlu
kitap_baslik -> isbn           veriyle uyumlu
sube_kodu -> sube_ad           veriyle uyumlu
uye_no -> isbn                 2 grupta ihlal

Çözümleyici, sol taraf değerlerine göre gruplar ve bir grupta birden çok sağ taraf değeri görürse ihlal sayar. uye_ad -> uye_no bir grupta ihlal verir: iki farklı üye aynı adı taşımaktadır. uye_no -> isbn iki grupta ihlal verir: aynı üye birden çok kitap almıştır.

Buradaki asıl ders, “veriyle uyumlu” çıkan satırlardadır. kitap_baslik -> isbn bağımlılığı bu altı satırda çürütülmemiştir, ama geçerli değildir — iki farklı kitabın aynı başlığı taşıması mümkündür ve o kayıt girildiği gün şema bozulur. Çözümleyici bir eleme aracıdır: ihlal bulursa bağımlılık kesin yoktur, bulmazsa yalnızca henüz çürütülmemiştir. Kararı alanın kuralı verir.

Bağımlılık Türleri

Dört ayrım normal formların tanımında kullanılacaktır.

Önemsiz bağımlılık (trivial dependency): $Y \subseteq X$ olduğunda $X \to Y$ her zaman doğrudur. $\text{üye no}, \text{üye adı} \to \text{üye adı}$ bilgi taşımaz.

Tam bağımlılık (full dependency): $X \to Y$ geçerli ve $X$’in hiçbir öz alt kümesi $Y$’yi belirlemiyorsa, bağımlılık tamdır.

Kısmi bağımlılık (partial dependency): $X$ bileşik bir anahtarken $Y$, $X$’in bir öz alt kümesine bağımlıysa bağımlılık kısmidir. Ödünç kaydının anahtarı $(\text{üye no}, \text{ISBN})$ olsaydı, $\text{üye no} \to \text{üye adı}$ kısmi bir bağımlılık olurdu: üye adı anahtarın tamamına değil yarısına bağlıdır.

Geçişli bağımlılık (transitive dependency): $X \to Y$ ve $Y \to Z$ geçerliyken $Z$, $X$’e $Y$ üzerinden bağlıdır. Ödünç kaydında $\text{ödünç no} \to \text{şube kodu} \to \text{şube adı}$ zinciri budur; şube adı ödünç işlemine doğrudan değil, şube kodu üzerinden bağlıdır.

Kısmi ve geçişli bağımlılıklar, aynı olgunun birden çok satırda tekrar etmesine yol açar — şube adı, o şubeden yapılan her ödünç işleminde yeniden yazılır. Sıradaki dersin konusu bu iki bağımlılığın giderilmesidir.

Armstrong Aksiyomları

Bağımlılıklar birbirinden türetilebilir. Üç aksiyom, bilinen bir bağımlılık kümesinden çıkarılabilecek her bağımlılığı üretmeye yeter.

• Yansıma (reflexivity): $Y \subseteq X$ ise $X \to Y$.
• Genişletme (augmentation): $X \to Y$ ise, her $Z$ için $X \cup Z \to Y \cup Z$.
• Geçişlilik (transitivity): $X \to Y$ ve $Y \to Z$ ise $X \to Z$.

Bunlardan üç kullanışlı kural türer: birleşim ($X \to Y$ ve $X \to Z$ ise $X \to Y \cup Z$), ayrışma ($X \to Y \cup Z$ ise $X \to Y$ ve $X \to Z$) ve sözde geçişlilik. Ayrışma kuralı, sağ tarafında birden çok öznitelik bulunan bağımlılıkları tek öznitelikli parçalara bölmeyi meşru kılar; çözümleme genellikle bu biçimde yapılır.

Aksiyom takımının iki özelliği vardır: sağlamdır (türetilen her bağımlılık gerçekten geçerlidir) ve tamdır (geçerli her bağımlılık türetilebilir). Bu yüzden normal form denetimleri elle sezgiyle değil, mekanik olarak yapılabilir.

Öznitelik Kapanışı

Türetmeyi elle yapmak yerine bir küme hesaplanır. $X$ kümesinin öznitelik kapanışı (attribute closure) $X^+$, verilen bağımlılıklardan yararlanarak $X$’ten belirlenebilen bütün özniteliklerin kümesidir. Hesap yinelemelidir: sol tarafı $X^+$ içinde kalan her bağımlılığın sağ tarafı kümeye eklenir, küme büyümeyi durdurana dek sürer.

Kapanış iki soruyu tek adımda yanıtlar. $X \to Y$ geçerli midir? $Y \subseteq X^+$ ise evet. $X$ süperanahtar mıdır? $X^+$ bütün öznitelikleri kapsıyorsa evet.

const oznitelikler = "odunc_no uye_no uye_ad isbn kitap_baslik sube_kodu sube_ad".split(" ");
const bagimliliklar = [
  [["odunc_no"], ["uye_no", "isbn", "sube_kodu"]],
  [["uye_no"], ["uye_ad"]],
  [["isbn"], ["kitap_baslik"]],
  [["sube_kodu"], ["sube_ad"]],
];

function kapanis(baslangic) {
  const sonuc = new Set(baslangic);
  let buyudu = true;
  while (buyudu) {
    buyudu = false;
    for (const [sol, sag] of bagimliliklar) {
      if (sol.every((a) => sonuc.has(a))) {
        for (const a of sag) if (sonuc.has(a) === false) { sonuc.add(a); buyudu = true; }
      }
    }
  }
  return [...sonuc];
}

for (const kume of [["odunc_no"], ["uye_no"], ["uye_no", "isbn"]]) {
  const k = kapanis(kume);
  console.log(`{${kume.join(",")}}+ = {${k.join(",")}}`);
  console.log(`  -> ${k.length === oznitelikler.length ? "superanahtar" : "superanahtar degil"}`);
}

{odunc_no}+ = {odunc_no,uye_no,isbn,sube_kodu,uye_ad,kitap_baslik,sube_ad}
  -> superanahtar
{uye_no}+ = {uye_no,uye_ad}
  -> superanahtar degil
{uye_no,isbn}+ = {uye_no,isbn,uye_ad,kitap_baslik}
  -> superanahtar degil

Ödünç numarası tek başına bütün özniteliklere ulaşır, yani süperanahtardır; hiçbir öz alt kümesi bulunmadığından aynı zamanda aday anahtardır. Üye numarası ile ISBN birlikte bile şube bilgisine ulaşamaz — çünkü şube, ödünç işlemine bağlıdır, üye ile kitabın çiftine değil.

Kapanış hesabı, Veri Yapıları kursundaki geçişli kapanış fikrinin bağımlılıklar üzerine uygulanmış hâlidir: bir düğümden ulaşılabilen düğümler kümesi yerine, bir öznitelik kümesinden belirlenebilen öznitelikler kümesi bulunur.

Bağımlılığın Şemadaki Karşılığı

Bir bağımlılık şemada iki biçimde görünür. Sol tarafı bir aday anahtar ise bağımlılık zaten anahtar kısıtıyla uygulanır — anahtar tekil olduğu için her değer bir kez geçer ve sağ taraf o satırda bir kez yazılır. Sol tarafı anahtar değilse bağımlılık şemaya yazılamaz; motorun onu bilmesinin bir yolu yoktur ve ihlal edilmesini engelleyecek hiçbir kısıt kurulamaz.

Buradan normalizasyonun tek cümlelik gerekçesi çıkar: her işlevsel bağımlılığın sol tarafı bir anahtar olacak biçimde bağıntıları bölmek, bağımlılıkların şema tarafından uygulanmasını sağlar. Sıradaki ders bu bölme işlemini adım adım tanımlar.

Özet

• $X \to Y$, $X$ üzerinde eşleşen iki satırın $Y$ üzerinde de eşleşmesi kuralıdır; süperanahtar, sağ tarafı bütün öznitelikler olan bağımlılığın sol tarafıdır.
• Bağımlılık alanın kuralından gelir; veri örneği onu yalnızca çürütebilir, doğrulayamaz.
• Kısmi bağımlılık bileşik anahtarın parçasına, geçişli bağımlılık bir ara öznitelik üzerinden kurulur; ikisi de satır tekrarına yol açar.
• Armstrong aksiyomları sağlam ve tamdır, bu yüzden bağımlılık çıkarımı mekanik olarak yapılabilir.
• Öznitelik kapanışı, bir bağımlılığın geçerliliğini ve bir kümenin süperanahtar olup olmadığını tek hesapla yanıtlar.

Sonraki Adım

Bu ders, tekrarın kaynağını adlandırdı: sol tarafı anahtar olmayan bağımlılıklar. Sıradaki ders bunları gidermenin basamaklarını tanımlar. Birinci normal form değerlerin bölünmezliğini, ikinci normal form kısmi bağımlılığın kaldırılmasını, üçüncü normal form geçişli bağımlılığın kaldırılmasını ister. Her basamakta aynı soru sorulacak: bu bölme, hangi güncelleme anomalisini ortadan kaldırıyor?