Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Algoritmy návrhu schémat relací

Schémata relací by měla být navrhována tak, aby odpovídala předem připravenému konceptuálnímu modelu (např. pomocí ER diagramů) a zároveň pokud možno splňovala co nejpřísnější požadavky na normální formy. Pro modelování relační databáze existují dva přístupy:

1. Získání množiny relačních schémat (ručně nebo převodem z např. ER diagramu) a provádění normalizace pro každou tabulku zvlášť
2. Návrh tzv. univerzálního schématu databáze - jedna velká tabulka pro celou databázi (vč. platných funkčních závislostí) a normalizace prováděná globálně

První možnost je relativně intuitivní (s ER diagramy) a jednoduchá, ale hrozí riziko přílišného rozdrobení databáze na velký počet malých tabulek (a nadbytečný i vzhledem k požadované normální formě). V druhém způsobu jsou entity jednotlivých relací vypozorovány jako efekt funkčních závislostí, což není příliš průhledné a jednoduše proveditelné, ale minimalizuje to šanci na rozdrobení databáze. Oba přístupy lze také zkombinovat - převést ER model databáze do schémat a některá (nebo až všechna) potom před normalizací sloučit.

Normalizace

Jediným způsobem, jak u nějakého obecného relačního schématu dosáhnout normální formy (obecně se požaduje většinou 3NF nebo BCNF), je rozdělení na několik podschémat. Dá se to provést ručně nebo algoritmicky a existuje více přístupů podle požadavku na normální formu, bezztrátovost (dekompozice relace do a je bezeztrátová, když nebo , tedy opětovným spojením do původní relace nevzniknou další řádky) nebo pokrytí závislostí (dekompozice do zachovává pokrytí závislostí, když - nesmí se ztratit závislost ani v rámci dílčího schématu, ani jdoucí napříč schématy).

Algoritmus (Dekompozice)

Dekompozice je algoritmus, který relační schéma převede do Boyce-Coddovy normální formy. Zaručuje zachování bezeztrátovosti, ale už ne pokrytí závislostí (bez ohledu na algoritmus toto u BCNF někdy není možné). Jeho běh vypadá následovně:

1. Vyber nějaké schéma, které není v BCNF.
2. Vezmi pro něj neklíčovou závislost (tak že není klíč) a dekomponuj podle ní - vyhoď ze schématu a dej do zvláštní tabulky.
3. Opakuj od kroku 1, dokud existuje schéma, které není v BCNF.

Algoritmus (Syntéza)

Algoritmus syntézy obecně dosahuje třetí normální formy a zachovává pokrytí závislostí (ale ne bezeztrátovost). Pro relační schéma s množinou funkčních závislostí vypadá následovně:

1. Udělej minimální pokrytí (vzhledem k tranzitivitě), nazvi ho .
2. Sluč funkční závislosti z se stejnou levou stranou a z každé vytvoř jedno schéma.
3. Zahoď schémata, která jsou podmnožiny jiných.

Nakonec je možné sloučit schémata s funkčně ekviv. klíči ( ), ale může to porušit normální formu, které bylo dosaženo! Pro zachování bezeztrátovosti lze do přidat nějaké schéma, obsahující univerzální klíč celého původního (neděleného) schématu.

Poznámka

Pro nalezení minimálního pokrytí atributů se používá pomocný algoritmus, který se chová takto:

1. Dekomponuj všechny funkční závislosti na elementární (na pravé straně je jen jeden sloupec)
2. Odstraň z nich redundantní atributy (takové z levé strany, které funkčně závisí na jiných z levé strany)
3. Odstraň redundantní funkční závislosti (tj. takové, které jsou tranzitivním důsledkem jiných - pravá strana funkčně závisí na levé, i když z množiny funkčních závislostí onu redundantní odstraním)

Pro druhý i třetí krok je potřeba získat atributový uzávěr (množina všech atributů i tranzitivně závislých na levé straně) - to se opakovaně zkouší, jestli díky funkčním závislostem nedostanu z atributů původní množiny nějaké další atributy (dokud nacházím další, přidávám je do množiny a opakuji).