Kihagyás

Relációs sémák tervezése

Cél: az anomáliák és redundancia megszüntetése

A tervezéshez a poorly designed Főnökök(név, cím, kedveltSörök, kedvencSör) fogjuk használni

Anomáliák

Törlési anomália

  • Az éppen nem aktív kapcsolatról minden adatot elveszíthetünk
  • Mi van akkor, ha jelen pillanatban már senki sem szereti a Bud-ot, ki tudjuk találni, ki gyártotta
    • segítek, nem, lmao

Módosítási anomália

  • Biztosan minden érintett sort módosítani fogunk?
  • Ha Janeway- ből Judy lesz, minden sorral meg fogjuk tenni?

Beszúrási anomália

  • A kapcsolatnak létrehozáskor léteznie kell
  • Mi van, ha a főnök nem iszik sört egyáltalán??

Relációk felbontása

\(R\) relációt, \(\{A_1,A_2, \ldots,A_n\}\) attribútumokkal helyettesítjük az \(S(B_1,B_2,\ldots,B_m)\) és \(K(C_1,C_2,\ldots,C_k)\) relációkkal úgy, hogy

\[ \{A_1,A_2, \ldots,A_n\}=\{B_1,B_2, \ldots,B_m\}\cup\{C_1,C_2, \ldots,C_k\} \]

Veszteségmentes felbontás

  • Ha \(r = \Pi_{R_1}(r)\Join\ldots\Join\Pi_{R_k}(r)\) teljesül, akkor az előbbi összekapcsolás veszteségmentes
  • \(\Pi_{R_i}(r)\) az \(r\) sorainak \(R_i\) attribútumaira projektálva
  • \(r\subseteq\Pi_{R_1}(r)\Join\ldots\Join\Pi_{R_k}(r)\) mindíg teljesülni fog
     R          R1     R2
 A | B | C    A | B   B | C
-----------  -------  ------
 a | b | c    a | b   b | c
 d | e | f    d | e   e | f
 c | b | c    c | b

Boyce-Codd normálforma - BCNF

Egy \(R\) reláció BCNF-ban van, ha minden \(X\to Y\) nemtriviális FF-re \(R\)-ben X szuperkulcs

  • Nemtriviális: \(Y\not\subseteq X\)
  • Szuperkulcs: tartalmaz kulcsot (ő maga is lehet kulcs)

A Főnökök(név, cím, kedveltSörök, kedvencSör) példa esetén

  • FF-ek: név → cím kedveltSör, kedveltSörök → gyártó
  • Egy kulcs van: {név, kedveltSörök}
  • A FF esetén sem szuperkulcs a bal oldal
    • Ketten kulcsot alkotnak, remember, akkor semelyik rész sem szuperkulcs magában
  • Konklúziónk az, hogy a Főnökök reláció nincs BCNF-ben

BCNF-re való felbontás

  • Adott \(R\) reláció, és \(F\) funkcionális függőségek
  • Van-e olyan \(X\to Y\) FF, ami cérti a BCNF-t?
    • Ha előáll egy olyan következmény \(F\) FF-ben, ami sérti a BCNF-t, akkor valamelyik \(F\)-beli FF is sérti
  • Kiszámoljuk \(X^+\)-t
    • Ha nem jelenik meg az összes attribútum, akkor \(X\) nem szuperkulcs!

R dekomponálása \(X\to Y\) felhasználásával

  • \(R\)-t két részre bontjuk
    • \(R_1=X^+\)
    • \(R_2 = R -(X^+ - X)\)
      • Vagy \(R_2 = (R \ X^+)\cup X\)
  • A meglévő FF-eket projektáljuk a két új relációsémára

Dekomponálás - Diagram

Felbontás eredménye

Dekomponálás - Példa

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

$F= $ név → cím, név → kedvencSör, kedveltSörök → gyártó

Vegyük a név → cím FF-t

\[ \large{\{\text{név}\}^+=\{\text{név, cím, kedvencSör}\}} \]

A dekomponálás eredménye:

  • Főnökök1(név, cím, kedvencSör)
  • Főnökök2(név, kedveltSörök, gyártó)

Ellenőrizzük, hogy az új Főnökök1 és Főnökök2 BCNF-ben van-e

Az FF-ek projektálása könnyű

  • Főnökök1(név, cím, kedvencSör)
    • FF-ek: név → cím, név → kedvencSör
    • Egyetlen kulcs: \(\{\text{név}\}\), tehát BCNF-ben van
  • Főnökök2(név, kedveltSörök, gyártó)
    • Egyetlen FF: kedveltSörök → gyártó
    • Egyetlen kulcs: \(\{\text{név}, \text{kedveletSörök}\}\)
      • Sérül a BCNF 🤯

Bontsuk tovább a Főnökök2(név, cím, kedveltSörök, gyártó)-r

\[ \large{\{\text{kedveltSörök}\}^+=\{\text{kedveltSörök, gyártó}\}} \]

A dekomponálásból lesznek:

  • Főnökök3(kedveltSörök, gyártó)
  • Főnökök4(név, kedveltSörök)
Dekomponálás - Kimenet

Dekomponálás eredménye a példa táblán

Így már lehet antialkoholista vezetőnk, ott egyszerűen NULL-ra vesszük fel a kapcsolatot

Mért működik a BCNF?

  • Egy reláció bármely veszteségmentes felbontásán egyik elemét annal veszteségmentes felbontásával helyettesítjük, az továbbra is veszteségmentes marad
  • Minden két attribútumú séma BCNF-ben van
  • Láthatóan működik, sajnos a függőségek vetítése miatt exponenciális lépésszámú is lehet

Chase-test

  • Példának adott \(R(A,B,C,D),\;F=\{A\to B,\;B\to C,\;CD\to A\}\), illetve az \(R_1(A,D),\;R_2(A,C),\;R_3(B,C,D)\) felbontások
    • Veszteségmentes-e ez így?
  • Vegyük a \(\orange{t=(a,b,c,d)}\) sorát a \(R_1\Join R_2\Join R_3\) összekapcsolásnak
  • Bizonyítani kell, hogy \(t\) az \(R\) egy sora, a következő táblánk van:
A B C D
\(a\) \(b_1\) \(c_1\) \(d\)
\(a\) \(b_2\) \(c\) \(d_2\)
\(a_3\) \(b\) \(c\) \(d\)

Az alsóindexek azt mutatják, hogy valami \(t\) -től lehetségesen eltérő elemet látunk

  • Ez azt is jelenti, hogy egyáltalán nem biztos, hogy \(t\)-t megtaláltuk
  • Az FF-ek segíthetnek feloldani a bizonytalanságokat
    • Egy FF alkalmazásával minden ismert heélyettesítést végezzünk el
    • A két indexes szimbólum esetén a kissebbiket adjuk át
  • Az algotritmus véget ér, ha valamelyik sorban megjelenik \(t\), vagy már nincs több felhasználható szimbólum

Alkalmazzuk sorra az FF-eket, nézzük mit kapunk

\[ \large{R_1\Join R_2\Join R_3} \]
A B C D
\(a\) \(b_1\) \(c_1\) \(d\)
\(a\) \(b_2\) \(c\) \(d_2\)
\(a_3\) \(b\) \(c\) \(d\)
\[ \Large{A\to B:} \]
A B C D
\(a\) \(b_1\) \(c_1\) \(d\)
\(a\) \(b_{\green{1}}\) \(c\) \(d_2\)
\(a_3\) \(b\) \(c\) \(d\)
\[ \Large{B\to C:} \]
A B C D
\(a\) \(b_1\) \(\green{c}\) \(d\)
\(a\) \(b_1\) \(c\) \(d_2\)
\(a_3\) \(b\) \(c\) \(d\)
\[ \Large{CD\to A:} \]
A B C D
\(a\) \(b_1\) \(c\) \(d\)
\(a\) \(b_1\) \(c\) \(d_2\)
\(\orange{a}\) \(\orange{b}\) \(\orange{c}\) \(\orange{d}\)

Lényegében a Függőség megkötési segítenek