Adatbázis tervezés II

Adatbázis tervezés II

Cél: az anomáliák és a redundancia megszüntetése
- Módosítási anomália
- Törlési anomália
- Beszúrási anomália

Relációk felbontása

$R$ relációt, ${A_{1}, A_{2}, \dots, A_{n}}$ attribútumokkal helyettesítsük $S (B_{1}, B_{2}, \dots, B_{m})$ és $T (C_{1}, C_{2}, \dots, C_{k})$ relácciókkal úgy, hogy

${A_{1}, A_{2}, \dots, A_{n}} = {B_{1}, B_{2}, \dots, B_{m}} \cup {C_{1}, C_{2}, \dots, C_{k}}$
$S = Π_{B_{1}, B_{2}, \dots, B_{m}} (R)$
$T = Π_{C_{1}, C_{2}, \dots, C_{k}} (R)$

Veszteségmentes felbontás

Ha $r = Π_{R_{1}} (r) ∣ X ∣ \dots ∣ X ∣ Π_{R_{k}} (r)$ teljesül, akkor az előbbi összekapcsolásra azt mondjuk, hogy veszteségmentes. Itt $r$ egy $R$ sémájú relációt jelöl és $R$ attribútumainak részhalmazai az $R_{1}, \dots R_{2}$
$Π_{R_{i}} (r)$ jelentése: $r$ sorai az $R_{i}$ attribútumaira projektálva.
Látható, hogy $r \subseteq Π_{R_{1}} (r) ∣ X ∣ \dots ∣ X ∣ Π_{R_{k}} (r)$ mindig teljesül.

Boyce Codd normálforma

$R$ reláció BCNF normálformában van, ha minden $X \to Y$ nemtriviális funkciónális függőségre $R$ -ben $X$ szuperkulcs.

Nemtriviális: $Y$ nem része $X$ -nek
Szuperkulcs: tartalmaz kulcsot (ő maga is lehet kulcs)

BCNF-re bontás:

Adott $R$ reláció ls $F$ funkcionális függőségek.
Van-e olyan $X \to Y$ ami sérti a BCNF-t?
- Ha van olyan következmény $F$ -ben, ami sérti a BCNF-t, akkor $F$ -beli funkcionális függőség is sérti
Kiszámoljuk $X^{+}$ -t:
- Ha itt nem szerepel az összes attribútum, $X$ nem szuperkulcs
$R$ dekomponálása $X \to Y$ felhasználásával:
- $R$ -t helyettesítsük az alábbiakkal:
  1. $R_{1} = X^{+}$
  2. $R_{2} = R - (x^{+} - X)$
- Projektáljuk a megfelelő $F$ -beli FF-eket a két új relációsémára

Miért működik a BCNF?

$(R, F)$ esetén ha $R_{1}, \dots, R_{k}$ egy veszteségmentes felbontás, $S_{1}, S_{2}$ pedig $R_{1}$ veszteségmentes felbontása, akkor $S_{1}, S_{2}, R_{2}, \dots R_{k}$ is veszteségmentes felbontás.
Könnyen ellenőrizhrtő, hogy BCNF felbontás dián az $R_{1}, R_{2}$ veszteségmentes.
Minden két attribútum séma BCNF normálformában van
A fentiekkel igazolható:
- Az algoritmus valóban veszteségmentes felbontást ad, ám sajnos exponenciális lépésszámú is lehet a függődégek vetítése miatt.

Chase teszt veszteségmentességhez

Az $F$ -beli függőségeket használva egyenlővé tesszük azokat a szimbólumokat, amelyeknek ugyanazoknak kell lennie, hogy valamelyik függőség ne sérüljön.

Ha a két egyenlővé teendő szimbólum közül az egyik index nélküli, akkor a másik is ezt az értéket kapja.
Két indexes szimbólum esetén a kisebbik indexű értéket kapja meg a másik.
A szimbólumok minden előfordulását helyettesíteni kell az új értékkel. Az algoritmus véget ér, ha valamelyik sor $t$ -vel lesz egyenlő, vagy több szimbólumot már nem tudunk egyenlővé tenni.

Ha $t$ szerepel a tablóban, akkor valóban $R$ -nek egy sora, és mivel $t$ -t tetszőlegesen választottuk, ezért a felbontás veszteségmentes.

Ha nem kapjuk meg $t$ -t, akkor viszont a felbontás nem veszteségmentes.

A harmadik normálforma

Motiváció

Bizonyos FF halmazok esetén a felbontáskor elveszíthetünk függőségeket.
$A B \to C$ és $C \to B$
- pl.: $A = f_{c} \overset{ı}{ˊ} m, B = v \overset{a}{ˊ} ros, C = mozi$
Két kulcs van: ${A, B}$ és ${A, C}$
$C \to B$ megsérti a BCNF-t, tehát $A C, BC$ -re dekomponálunk

A probléma az, hogy $A C$ és $BC$ sémákkal nem tudjuk kikényszeríteni $A B \to C$ függőséget

3NF

3.normálformában (3NF) úgy módosul a BCNF feltétel, hogy az előbbi esetben nem kell dekomponálnunk.
Egy attribútum prím (elsődleges attribútum), ha legalább egy kulcsnak eleme.
$X \to A$ nem-triviális FF, megsérti 3NF-t akkor és csak akkor, ha $X$ nem szuperkulcs és $A$ nem prím.
minden nem triviális függőségre igaz, hogy bal oldala szuperkulcs, vagy jobb oldala csak elsődleges attribútumokat tartalmaz
3NF feltétel és a BCNF feltétel közötti különbség a "vagy jobb oldala csak elsődleges attribútumokat tartalmaz"

3NF-re bontás

Minimális bázis létrehozása

Jobb oldalak szétvágása.
Próbáljuk törölni az FF-eket egymás után. Ha a megmaradó FF-halmaz nem ekvivalens az eredetivel, akkor nem törölhető az épp aktuális FF.
Egymás után próbáljuk csökkenteni a baloldalakat, és megnézzük, hogy az eredetivel ekvivalens FF-halmazt kapunk-e.

A minimális bázis minden FF-re megad egy sémát a felbontásban.

A séma a jobb- és baloldalak uniója lesz ( $X \to A$ FF, $X A$ séma) .
Ha a minimális bázis FF-jei által meghatározott sémák ( $X \to A$ FF, $X A$ séma) között nincs szuperkulcs, akkor hozzáadunk a felbontáshoz egy olyan sémát, amely maga egy kulcs az $R$ relációra.

3NF vs BCNF

A dekompozícióknak három fontos tulajdonsága lehet:

Veszteségmentes összekapcsolás (információ visszaállíthatóság)
Függőségek megőrzése
Anomáliák kiküszöbölése

Az (1) tulajdonság teljesül a BCNF esetében.

A 3NF (1) és (2)-t is teljesíti, de maradhat benne anomália (általában ez nem akkora baj)
A BCNF esetén (2) sérülhet, viszont (FF-ek okozta) anomália nem lehet benne

4. félévi jegyzetek