Kihagyás

3. Normálforma - 3NF

Gyors Kotlin explainer az első kettőről

Don't ask what happened with the first two, haven't seen mentioned as normal forms in the EA

UNF

Valami baj van, fiam.

  • Bármi hiányzik az 1NF-ból ezt eredményezi
  • Viszont a sorok egyediek

1NF

praktikusan a reláció fogalma

  • A tábla két dimenziós, sorokkal és oszlopokkal
  • Minden sor adatokat tartalmaz, amik valamit, vagy valaminek egy részét tárolják
  • Minden oszlop egy attribútumot jelöl
  • Minden cella egy darab értéket tárol magában
  • Minden adat egy oszlopban ugyanazon típusú / ugyanarról szól
  • Minden oszlopnak egyedi neve van
  • Minden sor egyedi
  • A sorok és oszlopok sorrendje nem releváns információ

Az egyediségből következik, hogy 1NF-ban létezik kulcs, azonban nincs rá extra megkötés, tehát legrosszabb esetben minden attribútum alkot összetett kulcsot

2NF

Lényegében legyen kulcsa, egy értelmes kulcsa

  • 1NF
  • Minden nem kulcs attribútumnak függenie kell a kulcstól

Ahol a kulcstól nem függő attribútum megjelenik, ott érdemes felbontani, és az \(n\) lépés után kapott táblák 2NF-ban lesznek

2NF ki van téve a tranzitív függőségeknek, törlés az egyik ponton törlési anomáliát jelenthet a függőség-lánc végén

3NF

3nf - Motiváció példával

Tranzitív függőségek elkerülése

  • Bizonyos FF halmazok esetén a felbontással függőségeket veszíthetünk
  • \(AB\to C,\;C\to B\)
    • Példa: \(A=\text{f\_cím},\;B=\text{város},\;C=\text{mozi}\)
  • Két kulcs van: \(\{A,\;B\},\;\{A,\;C\}\)
    • \(\{\text{f\_cím},\;\text{város}\},\;\{\text{f\_cím},\;\text{mozi}\}\)
    • \(C\to B\) megsérti a BCNF-t, tehát \(AC,\;BC\)-re dekomponálunk
      • mozi → város nem szuperkulcs \(C\)

FF-ek kikényszerítése

  • A példán látható \(AC,\;BC\) sémákkal nem tudjuk kikényszeríteni az \(AB\to C\) függőséget
Kikényszeríthetetlen FF

Mozi mentén kapcsolás

3NF - Szabályok

  • Annyiban más a BCNF feltételtől, hogy az előbbi esetben (tranzitív függőségek esetén) nem kell dekomponálnunk
  • Egy attribútum prím(elsődleges attribútum), ha legalább egy kulcsnak eleme
  • Egy adott \(X\to A\) nem-triviális FF. akkor és csak akkor sérti meg 3NF-t, ha \(X\) nem szuperkulcs, és \(A\) nem prím
  • Minden nem triviális FF-re igaz, hogy vagy a bal oldal szuperkulcs, vagy a jobb oldal (kizárólag) elsődleges attribútumokat tartalmaz

Szabályok ellenőrzése a példán

  • A problematikus esetben az \(AB\to C,\;C\to B\) FF-ek esetén a kulcsok \(AB\) és \(AC\)
  • Ezért \(A,\;B,\;\text{és} C\) mindegyike prím
  • Habár \(C\to B\) sér(tege)ti BCNF-t, 3NF-nak eleget tesz

3NF és BCNF célja

A dekompozíció fő tulajdonságai

  1. Veszteségmentes összekapcsolás
  2. Függőségek megőrzése

  3. Anomáliák kiküszöbölése

    1. igaz lesz 3NF-ra és a BCNF-ra is
  5. 3NF teljesíti 2.t, de maradhat benne anomália (általában ez nem akkora baj, according to EA)
  6. BCNF esetén 2. sérülhet, de anomália nem lehet

Minimális bázis létrehozása

Minimális bázis - Öttlet

  1. Jobboldalak szétvágása
  2. Próbáljuk törölni az FF-eket egymás után
  3. Ellenőrizzük, hogy az eredetivel ekvivalens-e az új halmaz
  4. Amíg az eredetivel ekvivalens FF-halmazt kapunk, töröljük az FF-eket

Minimális bázis - Algoritmus

Jelölje \(F^+\) az \(F\) függőségi halmazból következő függőségek halmazát

  1. \(G:=\emptyset\)
  2. Minden \(X\to Y\in F\) helyett vegyük azokat az \(X\to A\) függőségeket, ahol \(A\in Y-X\)
  3. Minden \(X\to A\setminus G\)-re, ha \(X\to A\in(G-\{X\to A\})^+\), akkor eldobjuk
    • \((G:=G-\{X\to A\})\)
  4. Minden \(X\to A\setminus G\)-re, amíg van olyan \(B\in X\)-re, hogy \(A\in(X-B)^+\) a \(G\) szerint
    • Tehát ha \((X-B)\to A\) teljesül, akkor \(X:=X-B\)
    • A 2. lépés után ugye minden G-beli függőség \(X\to A\) alakú
    • A 3. lépés addig tart, amíg nem marad elhagyható függőség
    • A 4. lépést követően mindne balolbal minimális lesz

3NF előállítása

  • A minimális bázis minden FF-re megad egy sémát a felbontásban
    • A séma a jobb- és balolbalak uniója lesz (Az FF: \(X\to A\),A séma: \(XA\))
  • A minimális bázis FF-jei által meghatározott sémák között ha nincs szuperkulcs, akkor a felbontáshoz hozzáadunk egy olyan sémát, amely maga egy kulcs az \(R\) relációra

Mért működik?

  • Megőrzi a függőségeket, hiszen a minimális bázisból átveszünk minden FF-et
  • Veszteségmentes összekapcsolás
    • CHASE algoritmussal ellenőrizhető
  • Az eredmény 3NF-ban van, ez a minimális bázis tulajdonságaiból következik