Funkcionális függések

Tervezés szempontjából rettenetes, de érdemes tudni a fogalmat

• Megtehetnénk, hogy az adatokat egyetlen relációba tennék
  • A felhasználó szempontjávól kényelmes
  • Sok felsesleges redundancia van benne
    • Nem hatékony tárolás szempontjából
    • A nem jól kezelt redundancia ellentmondásossá teheti az adatbázist
• Előzők miatt modellezésre lesz szükség

Redundancia

Adott egy \(R(A_1,\;\ldots,\;A_n)\) reláció.

Ha valamely \(A_i\) előállítható adott \(\{A_j\;|\;j\ne i\}\) attribútumok értékeiből, akkor az \(R\) reláció redundáns

Funkcionális függőségek

\(X\to Y\) egy \(R\) relációra vonatkozó megszorítás, miszerint ha két sor megegyezik \(X\) minden attribútumán, akkor az \(Y\) attribútumain is meg kell, hogy egyezzenek.

Jelölés

• \(X,Y,Z,\ldots\) attribútum halmazok; \(A,B,C,\ldots\) attribútumok
• \(\{A,B,C\}\) attribútum halmaz helyett \(ABC\)-t írunk

Funkcionális függőség - Példa

Főnökök(név, cím, kedceltSörök, gyártó, kedvencSör)

Várható FF-k:

• név\(\to\)cím
  • Alkesz(név, cím, telefon) miatt
• kedveltSörök\(\to\)Gyártó
  • Sörök(név, gyártó) miatt

Jobboldal szétvágása

A FF jobb oldali attribútumhalmaza mindíg felbontható.

Példa:

\[ A\to BC \iff A\to B,~~A\to C \]

• Balolbal szétvágására nincs általános szabály
• Jellemzően a funkcionális függés jobb oldalát egy attribútumik fogjuk egyszerűsíteni...

Relációk kulcsaik

• \(K\) szuperkulcs \(R\) relációra, ha \(K\) funkcionálisan meghatározza \(R\) attribútumait
  • Auto-inkrement azonosítók jellemzően szuperkulcsok
• \(K\) kulcs \(R\)-en, ha szuperkulcs, de egyetlen valódi részhalmaza sem szuperkulcs
  • A több attribútumból álló kulcsok esetén gyakran előfordulhat, hogy minden attribútum kell az azonosításhoz
  • pl.: Ismerős(becenév, barátiTársaság, utoljáraLáttam)
  • Lehet több baráti társaságod (sus), és hívhatsz több embert is Öcsi-nek, de egy társaságban a becenév egyedi
  • \(\{\text{becenév},\;\text{barátiTársaság}\}\) szuperkulcsot alkot, de magukban egyik sem az

Kulcsot hogyan kaphatunk?

• A specifikációból egyértelműen eldönthető, ha az FF-k \(K\to A\) alakúak
• Megadjuk az FF-ket, és ezekből következtetjük ki

Amstrong-axiómák

Következtetési szabályok

(A1) - Reflexivitás

• Triviális függőség

(A2) - Bővítés

(A3) - Tranzitivitás

Amstrong - Példa

Legyen \(R=ABCD\;F=\{A\to C,\;B\to D\}:\)

Így az \(A\to C\), \(B\to D\) FF-ből elő tudtuk állítani az \(AB\) szuperkulcsot 🤗

Nincs arról bizonyításunk, hogy \(A\) vagy \(B\) önmagában nem lehetne szuperkulcs, így technikailag lehet nem kulcs (csak szuperkulcs)...

További Feladatok

Mutassuk be, hogy ezek miért nem érvényes szabályok

• \(A\to B\implies B\to A\)
• \(AB \to C,\; A\to C\implies B\to C\)
• \(AB \to C \implies A\to C\;\lor\;B\to C\)

Lezárt

• Adott FF-eknek egy \(F\) halmaza
  • Attribútum(ok)ból attribútum(ok)ra szóló következtetések halmaza

Adott \(R\) reláció és FF-einek egy \(F\) halmaza, ekkor

• \(Y\subseteq R\) lezártja:
• Jelölés: \(Y^+\)
• \(Y^+:=\{A \subseteq R\;|\;F \implies Y\to A\}\)
  • Azon \(A\) attribútumhalmazok halmaza, amik \(F\) szerint funkcionálisan függnek \(Y\)-tól

Lezárt kiszámolása

• Kiindulás: \(Y^+ = Y\)
• Indukció: Olyan FF-eket keresünk, amiknek a bal oldala benne van \(Y^+\)-ban, ekkor azon FF jobb oldalát hozzáadjuk Y^+-hoz
  • Ilyen \(X\to A\) esetén \(A\)-t hozzáadjuk \(Y^+\)-hoz
• Ha \(Y^+\)-hoz már nem lehet további attribútumot adni, vége

Bizonyítás

\(R\) reláció és \(F\) FF esetén:

1. \(B\in Y^+\implies Y\to B\)
2. \(\nexists F\ni X = X_1\to X_2: Y^+ \to X_1 \land X\not\in Y^+\)
   • tehát nem hagytunk ki semmit

Bizonyítás első fele

• Indukció, yolo
• 1. lépés: \(B\subseteq Y\), triviális függőség
• TFH Akkor \(B\)-vel bővítünk, amikor \(X\to B\in F\)
  • Az indukciós feltevés miatt: R eleget tesz \(Y\to X\)-nek
  • Ezét ha két sor egyezik \(Y\)-on, akkor \(X\)-en is, így \(X\to B\) miatt \(B\)-n is megegyezik 🤯

Bizonyítás emásodik fele

• Indirekt bizonyítás
• Vegyük azt, hogy létezik olyan \(Y\to B\) FF, amelyet az algoritmus nem talált meg
• Akkor ha mutatunk legalább egy olyan előfordulást, amire \(F\) minden FF-je teljesül, akkor abból az is következik, hogy \(Y\to B\) is következnie kell belőle
• \(\square\)