// Kradeno z https://github.com/Krejdom/school_notes/blob/master/PB154.md
- určitá omezení, která platí pro určitou relaci
- obecně α → β je triviální závislost, pokud β ⊆ α (Hodnoty atributů nalevo, mi jednoznačně určují hodnoty atributů napravo)
- syntax = zápis
- sémantika = význam
- platí = v celém světě to tak je a funguje
- splňuje = v této konkrétní tabulce to funguje
- pokud β ⊆ α, pak α → β (reflexivita)
- pokud α → β, pak γ, α → γ, β (rozšíření)
- pokud α → β a β → γ, pak α → γ (tranzitivita)
- K je superklíčem pro relační schéma R, právě když K → R
- K je kandidátním klíčem R, právě když platí
- K → R, a zároveň
- pro žádné α ⊂ K neplatí α → R
- Pro množinu atributů α definujeme uzávěr množiny atributů α⁺ jako množinu atributů, které jsou funkčně závislé na α podle množiny funkčních závislostí F.
result := α;
previousResult := null;
while (result != previousResult ) do {
previousResult := result;
for each β → γ in F do {
if β ⊆ result then result := result ∪ γ;
- z dané množiny funkčních závislostí vyvozujeme nové a tím postupně rozšiřujeme množinu, proces opakujeme, dokud dvě po sobě jdoucí iterace nevrátí stejný výsledek; využití: test superklíče, funkčních závislostí uzávěru F
F⁺ := ∅;
for each γ ⊆ R do {
for each S ⊆ γ⁺ do {
F⁺ := F⁺ ∪ γ → S;
}
}
- Dekompozice je bezeztrátová, pokud nahrazením původní tabulky novými nedojde ke ztrátě informací.
- Nechť R₁, R₂ je rozklad tabulky R. Rozklad je bezeztrátový, pokud pro všechny možné relace s danými schématy platí r = Π R₁(r) ⨝ Π R₂(r)
- Ověření bezeztrátovosti: Dekompozice R na R₁, R₂ je bezeztrátová, pokud alespoň jedna z následujících funkčních závislostí je v F⁺:
- R₁ ∩ R₂ → R₁
- R₁ ∩ R₂ → R₂
- atributy musí být atomické (nedělitelné)
- př.
adresa → adresa_mesto, adresa_ulice, adresa_cislo
- splňuje požadavky 1. NF
- každý atribut je součástí kandidátního klíče
- nebo není částečně závislý na žádném kandidátním klíči
- splňuje požadavky 1. a 2. NF
- atribut je součástí některého kandidátního klíče
- nebo není tranzitivně závislý na žádném superklíči (je přímo závislý na celém kandidátním klíči, nikoliv podčásti nebo tranzitivně)
- dekompozice je vždy bezztrátová vůči joinu a zachovává funkční závislosti
- výskyt redundance a null hodnot
- Definice BCNF: Relační schéma R je v BCNF vzhledem k F, pokud je v 1NF a pro každou závislost α → β v F+ platí:
- α → β je triviální závislost, nebo
- α je superklíč v R.
- ! nemusí zachovat funkční závislosti !
- nemusíme kontrolovat ztrátovost
- Každé relační schéma, které je v BCNF, je také v 3.NF.
- Algoritmus: mějme relaci R, která není v BCNF. Pak existuje alespoň jedna netriviální funkční závislost α → β taková, že α není superklíčem R. Relaci R nahradíme relacemi
- R₁ = α ∪ β
- R₂ = (R-(β-α))
- Vytvořit relace se schématy takovými, které splňují všechny následující podmínky:
- relace jsou v BCNF
- bezeztrátová dekompozice
- zachovány všechny funkční závislosti
- Pokud nelze splnit všechny tři, postačí:
- relace jsou v 3NF
- bezeztrátová dekompozice
- zachovány všechny funkční závislosti