4. Normálforma - 4NF

Motiváció

Oktató	Város	Közterület	Tárgy	Szemeszter
Kovács István	Budapest	Rákóczi út 1.	Adatbázisok	2020/21/1
Kovács István	Debrecen	Kossuth tér 1.	Adatbázisok	2020/21/1
Kovács István	Budapest	Rákóczi út 1.	Hálózatok	2020/20/2
Kovács István	Debrecen	Kossuth tér 1.	Hálózatok	2020/20/2
Kovács István	Budapest	Rákóczi út 1.	Programozás	2020/19/1
Kovács István	Debrecen	Kossuth tér 1.	Programozás	2020/19/1

Did you notice a pattern?

Többértékű függőség - TÉF

Adott \(R\) reláció fölött \(X\twoheadrightarrow Y\) teljesül, ha
- bármely két sorra, melyek megegyeznek az \(X\) minden attribútumán, az \(Y\) attribútumaihoz tartozó értékek felcserélhetőek, azaz a keletkező két új sor \(R\)-beli lesz
Lényegében \(X\) minden értéke esetén \(Y\)-hoz tartozó értékek függetlenek az \(R-X-Y\) értékeitől
Előző példában: oktató ↠ Város Közterület

Ez azt a mintát akarja leírni, hogy a tábla úgy néz ki, mintha önmagában kapcsolás lenne

A példában minden Budapesti sorhoz rendelve van DB, Hálózatok, meg Prog, ugyanez Debrecennel. Ezért van az, hogy a sorokat ha csak ezen attribútumokban cserélnénk, olyan, mintha nem változtattunk volna a reláción

TÉF - Példa

Alkesz(név, cím, tel, kedveltSörök)

Az alkeszek telefonszámai függetlenek az általuk kedvelt söröktől
- név ↠ tel
- név ↠ kedveltSörök
Így egy-egy alkesz minden telefonszáma minden általa kedvelt sörrel kombinációban áll
Ez a jelenség teljesen független a funkcionális függéstől
- A példában név → cím az egyettlen FF
Jellemzően a TÉF-ek ki vannak téve a módosítási anomáliának

TÉF szabályok

Minden FF TÉF
- Ha \(X\to Y\) és két sor megyegyezik \(X\)-en, akkor \(Y\)-on is
  - Ott a felcserélés ugyanazt az eredményt generálja
- \(X\to Y \implies X\twoheadrightarrow Y\)
Ha \(X\twoheadrightarrow Y\), és \(Z\) az összes többi attribútum halmaza, akkor \(X\twoheadrightarrow Z\)
A jobb oldal az FF-ekhez hasonlóan nem bontható fel
Azonban TÉF-eknél a jobb oldal sem bontható fel

FF és TÉF axiómák

\(R\) reláció felett, ahol \(X,Y,Z,W,S \in R\) attribútumok

FF axiómák

(A1) - Reflexitás

\[ Y\subseteq X \implies X\to Y \]

(A2) - Bővíthetőség

\[ X\to Y \implies \forall\,Z: XZ\to YZ \]

(A3) - Tranzitivitás

\[ X\to Y,\;Y\to Z\implies X\to Z \]

TÉF axiómák

(A4) - Komplementer

\[ X\twoheadrightarrow Y,\; Z= R-XY \implies X\twoheadrightarrow Z \]

(A5) - Bővíthetőség

\[ X \twoheadrightarrow Y,\;\forall\,V\subseteq W:\;XW\twoheadrightarrow YV \]

(A6) - Tranzitivitás

\[ X \twoheadrightarrow Y,\;Y\twoheadrightarrow Z \implies X \twoheadrightarrow Z \]

Vegyes axiómák

(A7): FF \(\to\) TÉF

\[ X\to Y \implies X \twoheadrightarrow Y \]

(A8): TÉF \(\to\) FF \(\to\) FF

\[ X \twoheadrightarrow Y,\; W\to S,\; S\subseteq Y,\;W\cap Y =\emptyset\implies X \to S \]

4NF

A TÉF-ek okozta redundanciát BCNF nem szünteti meg
Negyedik normálformánál a dekomponálás esetén a TÉF-eket FF-ekhez hasonlóan kezeljük, azonban a kulcsok megtalálásánál nem számítanak

Triviális TÉF-ek

\(X,Y\subseteq R\)

\(Y\subseteq X \implies X\twoheadrightarrow Y\)
\(X\cup Y = R \implies X \twoheadrightarrow Y\)

4NF definíció

Egy \(R\) reláció 4NF-ben van, ha minden \(X \twoheadrightarrow Y\) nemtriviális TÉF esetén \(X\) szuperkulcs
- Tehát \(Y\not\subseteq X,\;X\cup Y\ne R\)
- A szuperkulcs definíciója változatlan, csak az FF-ektől függ

BCNF \(\subset\) 4NF

Minden \(X\to Y\) FF egyúttal \(X\twoheadrightarrow Y\) TÉF is
Minden olyan feltétel, ami BCNF-t sérti, sérti a negyedik normálformát is
Viszont \(R\) ki tudja elégíteni BCNF minden feltételét a TÉF-ek megszorítása nélkül

4NF dekompozíció - Példa

Alkeszek(név, cím, tel,kedveltSörök)

FF

\(\text{név}\to\text{cím}\)

TÉF

\(\text{név}\twoheadrightarrow\text{tel}\)
\(\text{név}\twoheadrightarrow\text{kedveltSörök}\)

Kulcs

\(\{\text{név},\text{tel},\text{kedveltSörök}\}\)

Minden függőség megsérti a 4NF-t

Dekompozíció \(\text{név}\to\text{cím}\) szerint

Alkesz1(név,cím)
- Ez 4NF-beli, egy függőséggel (név→cím)
Alkesz2(név,tel,kedveltSörök)
- Nincs 4NF-ben
- A név↠tel és név↠kedveltSörök függőségek teljesülnek
  - A három attribútum együtt kulcs (mert nincs nemtriviális FF)

Dekompozíció \(\text{név}\twoheadrightarrow\text{tel}\) vagy \(\text{név}\twoheadrightarrow\text{kedveltSörök}\) szerint

Mindkét esetben ugyanazt kapjuk

Alkesz3(név,tel)
Alkesz4(név,kedveltSörök)

CHASE Kiterjesztése TÉF-ekre

FF-ek esetén ugyanúgy járjunk el, mint eddig
Egy TÉF eseté írjuk be azokat a sorokat, melyek szükségesek ahhoz, hogy az előfordulás ne sértse meg a TÉF-et
- \(X\twoheadrightarrow Y\): ha van két sor a tablóban, melyek \(X\)-en egyeznek
  - Készíthetünk két újjabb sort, megcserélve \(Y\)-on elhelyezkedő komponenseiket
- A két új sornak szerepelnie kell az új tablóban is
Ha FF-ekből és TÉF-ekből szeretnénk levezetni egy \(X\twoheadrightarrow Y\)-t, akkor 2 soros tablóval kezdünk, melyek \(X\)-en megegyeznek, a többinél különböznek
Ha észrevesszük, hogy az eredeti sorok egyikében az \(Y\) attribútumokat kicseréljük egy másik eredeti sorból ugyanazokkal, ezzel be tudtuk látni a függőséget

CHASE Setup

Kiindulásként legyen az első sor olyan, hogy nem indexelt betűket tartalmaz \(X\)-en és \(Y\)-on, a második pedig ugyanilyeneket \(X\)-en, de az előző \(Y\) tól különböző
A két sorban fennmaradó helyeken új, egyszer szereplő szimbólumok legyenek
Cél: előállítani egy olyan sort, ahol minden elem indexeletlen

Tabló \(A\to C\) bizonyítása

\(A\twoheadrightarrow BC,\;D\to C\), akkor \(A\to C\) teljesül minden esetben

Cél elérni, hogy \(c_1=c_2\)

A	B	C	D
\(a\)	\(b_1\)	\(c_1\)	\(d_1\)
\(a\)	\(b_2\)	\(c_2\)	\(d_2\)

\[ \large{A\twoheadrightarrow BC} \]

A	B	C	D
\(a\)	\(b_1\)	\(c_1\)	\(d_1\)
\(a\)	\(b_2\)	\(c_2\)	\(d_2\)
\(a\)	\(\green{b_2}\)	\(\green{c_2}\)	\(d_1\)
\(a\)	\(\green{b_1}\)	\(\green{c_1}\)	\(d_2\)

\[ \large{D \to C} \]

A	B	C	D
\(a\)	\(b_1\)	\(c_1\)	\(d_1\)
\(a\)	\(b_2\)	\(c_{\green{1}}\)	\(d_2\)
\(a\)	\(b_2\)	\(c_{\green{1}}\)	\(d_1\)
\(a\)	\(b_1\)	\(c_1\)	\(d_2\)

Tabló \(A\twoheadrightarrow C\) bizonyítása

\(A\twoheadrightarrow B,\;B\twoheadrightarrow C\) esetén fennáll \(A\twoheadrightarrow C\)

Ha a séma \(ABC\), akkor a komplementálási szabályból azonnal következik

TFH \(ABCD\) általánosabb séma esetén is teljesül-e

Cél: előállítani az \((a,b,c,d)\) sort

A	B	C	D
\(a\)	\(b_1\)	\(c\)	\(d_1\)
\(a\)	\(b\)	\(c_1\)	\(d\)

\[ A\twoheadrightarrow B \]

A	B	C	D
\(a\)	\(b_1\)	\(c\)	\(d_1\)
\(a\)	\(b\)	\(c_1\)	\(d\)
\(a\)	\(\green{b}\)	\(\green{c_1}\)	\(d_1\)
\(a\)	\(\green{b_1}\)	\(\green{c}\)	\(d\)

\[ B\twoheadrightarrow C \]

A	B	C	D
\(a\)	\(b_1\)	\(c\)	\(d_1\)
\(a\)	\(b\)	\(c_1\)	\(d\)
\(a\)	\(b\)	\(c\)	\(d_1\)
\(a\)	\(b_1\)	\(c_1\)	\(d\)
\(a\)	\(\green{b}\)	\(\green{c_1}\)	\(d_1\)
\(\orange{a}\)	\(\orange{b}\)	\(\orange{c}\)	\(\orange{d}\)
\(a\)	\(\green{b_1}\)	\(\green{c_1}\)	\(d_1\)
\(a\)	\(\green{b_1}\)	\(\green{c}\)	\(d\)

CHASE célok

\(U\to V\)-nél akkor nyertünk, ha a megfelelő változók \(V\)-hez tartozó minden oszlopban egyenlőek
\(U\twoheadrightarrow V\)-nél akor nyőztünk, ha sikerül olyan sort előállítani, ami az eredeti két sorból keletkezik \(V\) értékeinek felcserélésével