Databáze II

Note	Funkční závislosti, normální formy (1NF, 2NF, 3NF, Boyce-Coddova NF), vztahy mezi normálními formami. Dekompozice relačních schémat, normalizace schématu. PB154

Funkční závislosti

V relačním schématu $R$ řekneme, že $α \to β$ , kde $α \subseteq R, β \subseteq R$ , je funkční závislost, pokud

t_{1} [α] = t_{2} [α] ⟹ t_{1} [β] = t_{2} [β] .

Note	$t_{1} [α]$ jsou ty hodnoty atributů z řádku $t_{1}$ , které jsou v množině $α$ .

Jinak řečeno hodnota množiny atributů $α$ jednoznačně určuje hodnotu množiny atributů $β$ . Atributy v $β$ tak nějak závisí na atributech z $α$ .

Funkční závislosti využíváme k testování relace nebo specifikace omezení.

Triviální funkční závislost: Pokud $β \subseteq α$ , pak $α \to β$ je triviální závislost.
Superklíč relace $R$: Superklíč relace $R$ je množina atributů $K \subseteq R$ taková, že $K \to R$ .
Kandidátní klíč relace $R$: Kandidátní klíč relace $R$ je množina atributů $K \subseteq R$ taková, že $K$ je superklíč a pro každé $α \subset K$ platí $α ↛ R$ (je neredundantní).

Armstrongovy axiomy

Note	Notace $α β$ znamená $α \cup β$ .

Reflexivita: Pokud $β \subseteq α$ , pak $α \to β$ .
Rozšíření: Pokud $α \to β$ , pak $γ α \to γ β$ .
Tranzitivita: Pokud $α \to β$ a $β \to γ$ , pak $α \to γ$ .

Důsledky Armstrongových axiomů

Sjednocení: Pokud $α \to β$ a $α \to γ$ , pak $α \to β γ$ .
Rozklad: Pokud $α \to β γ$ , pak $α \to β$ a $α \to γ$ .
Pseudotranzitivita: Pokud $α \to β$ a $γ β \to δ$ , pak $γ α \to δ$ .

Normalizace

Proces dekompozice a reorganizace relačního schématu tak, aby se s ním lépe pracovalo. Vede k omezení redundance a zlepšení konzistence databáze, ale vede jen k zanadbatelnému navýšení jejího výkonu.

1NF — atributy jsou atomické.
2NF — 1NF + neklíčové atributy jsou plně závislé na každém kandidátním klíči.
3NF — 2NF + neklíčové atributy jsou vzájemně nezávislé.
BCNF — 3NF + atributy primárního klíče jsou vzájemně nezávislé.

1. normální forma (1NF)

Schéma $R$ je v 1NF, pokud všechny atributy v $R$ jsou atomické — nemají podčásti.

Není v 1NF

Adresa
Ulice 1, Město, 666 00

Adresa

Ulice 1, Město, 666 00

Je v 1NF

Ulice	Č.P.	Město	PSČ
Ulice	1	Město	666 00

Ulice

Č.P.

Město

PSČ

Ulice

Město

666 00

2. normální forma (2NF)

Schéma $R$ je v 2NF, pokud je v 1NF a každý atribut v $R$ , který není součástí kandidátního klíče, tranzitivně závisí na každém kandidátním klíči plně (nikoliv na žádné jeho ostré podmnožině).

Není v 2NF

Autor

Obraz

Místnost

Barvy

Není v 2NF, pokud Místnost závisí na kandidátním klíči plně $Autor, Obraz \to M \overset{ı}{ˊ} stnost$ , ale Barvy pouze částečně $Obraz \to Barvy$ .

3. normální forma (3NF)

Schéma $R$ je v 3NF, pokud je v 2NF a každý atribut v $R$ , který není součástí kandidátního klíče, je netranzitivně závislý právě na všech kandidátních klíčích.

Alternativně, schéma $R$ je v 3NF, právě když pro každou funkční závislost $α \to β$ platí

$α \to β$ je triviální, tedy $β \subseteq α$ , nebo
$α$ je kandidátní klíč, nebo
každý atribut v $β ∖ α$ je součástí nějakého kandidátního klíče.

Every non-key attribute must provide a fact about the key, the whole key, and nothing but the key, so help me Codd.

Není v 3NF

Student

Jméno

Není v 3NF, pokud Jméno závisí na ID tranzitivně: $ID \to Student$ , $Student \to Jm \overset{e}{ˊ} no$ .

Boyce-Coddova normální forma (BCNF)

Schéma $R$ je v BCNF, pokud je v 3NF a každá závislost $α \to β$ , kde $α \subset R, β \subset R$ splňuje

$α \to β$ je triviální, nebo
$α$ je superklíč.

BCNF nemusí na rozdíl od ostatních NF zachovávat funkční závislosti.

Není v BCNF

Učo

Ročník

Jméno

Věk

$U \overset{c}{ˇ} o, Ro \overset{c}{ˇ} n \overset{ı}{ˊ} k \to Jm \overset{e}{ˊ} no, V \overset{e}{ˇ} k$

$V \overset{e}{ˇ} k \to Ro \overset{c}{ˇ} n \overset{ı}{ˊ} k$

Není v BCNF, neboť v závislosti $V \overset{e}{ˇ} k \to Ro \overset{c}{ˇ} n \overset{ı}{ˊ} k$ Věk není superklíčem.

Vztahy mezi normálními formami

BCNF \subset 3NF \subset 2NF \subset 1NF

Příklad: Všechno, co je v BCNF je zároveň v 3NF, 2NF i 1NF. Existují však relace, které nejsou v BCNF, ale jsou v 3NF. Atd.

Vždy existuje převod do 3NF takový, že je bezztrátový a zachová funkční závislosti (který využívá dekompozici).

Dekompozice relačních schémat

Rozklad na více relačních schémat.

Bezztrátová dekompozice

Všechny atributy původního schématu $r$ se objeví i v rozkladu na schémata $r_{1}$ a $r_{2}$ .

r = r_{1} \cup r_{2} r = π_{A, B} (r) ⋈ π_{B, C} (r)

Dekompozice zachovávající funkční závislosti

Sjednocení všech funkčních závislostí z dekomponovaných schémat dá původní funkční závislosti originálního schématu. Pokud ne, musíme relace při každé modifikaci spojit $⋈$ a ověrit platnost závislostí.