====== IN-POS 3. Databáze ======

===== Zadání =====

  * Kódování dat, kompresní kódování dat, organizace souborů dat.
  * Indexování a hašování, bitmapové indexy, dynamické hašování.
  * Vyhodnocení dotazů, transformační pravidla, statistiky a odhady.
  * Optimalizace dotazů a schématu.
  * Zabezpečení báze dat, přístupová práva.
  * Transakce, řízení souběžných transakcí, systémy obnovy transakcí po výpadku.


  * PV062, PA152, PA150

===== Vypracování =====

FIXME: doladit, doplnit, zpřehlednit

==== Kódování dat ====

**Kódování** = Proces nahrazování symbolů (resp. jejich posloupností) zprávy symboly (resp. jejich posloupností) nabývajících znaků cílové (kódovací) abecedy.

<box 90% red|Množství informace>
Množství získané informace odpovídá velikosti odstraněné neurčitosti získáním informace.

<m>i(A) = - log P(A)</m>

Pro <m>log_2</m> je jednotkou **bit**.

</box>

<box 90% red|Entropie>

Neurčitost zdroje zprávy je rovna množství informace v ní obsažení. (Neurčitost je přijetím zprávy odstraněna.)

<m>H(X) = sum{i=1}{s}{p_i log_2 p_i}</m>


  * Každý stav s pravděpodobností svého výskytu přispívá do neurčitosti svojí neurčitostí.
  * Vztah nabývá maxima pro <m>p_1 = ... = p_s</m>, kde <m>p_i = 1/s</m>.

</box>

  * **Abeceda** = konečná množina znaků (prvků abecedy, písmen,...)
  * **Kódové slovo** = slovo (posloupnost znaků) v kódové abecedě
  * **Kódování** = funkce <m>K : A -> A^{+}_C</m>
  * **Kód** = kódem daného kódování se rozumí obor hodnot zobrazení K


=== Klasifikace kódů ===

  * Kód s kódovými slovy **pevné** délky.
  * Kód s kódovými slovy **proměnlivé** délky.
    * prefixový, sufixový kód
  * **stupeň** (rate) kódu = průměrný počet bitů použitých pro kódování zdrojových znaků v tomto kódu.
  * **optimální kód** má stupeň minimálně převyšující množství informace obsažené v symbole zdrojových zpráv.
  * **Nesingulární kód** = jeho kódovací funkce je prostá
  * **Jednoznačně dekódovatelný kód** = Všechny možné řetězce jsou jednoznačně dekódovatelné
    * prefixové, sufixové a blokové kódy jsou jednoznačně dekódovatelné
  * **Prefixový  kód** = Bezprostředně jednoznačně dekódovatelný kód.

<box 90% blue|Minimální kódování>

  * Fanovo kódování
  * kódová slova znaků mají délky úměrné množství informace, které znaky nesou.

Př.:

  * A = 1 , C = 01 , G = 000 a T =001
  * např. řetětzec 8 symbolů  ACATGAAC je kódovaný  14 bity:

    10110010001101

  * tj. v průměru <m>14/8 = 1.75</m> b/symbol

</box>



== Eliasovy kódy ==


<box 90% blue|Eliasův kód C1>

Kódování celých čísel u kterých není předem známá horní hranice.

  - Zapíšeme číslo dvojkově.
  - Odečteme 1 od počtu bitů zapsaných v kroku 1 a na začátek připojíme takový počet nul.
    - Prefix 0 při dekódování určuje délku binární reprezentace.

Př.:

  * n=38, <m>hat{B}(38)= 00110_2</m> <m>|B(38)|=6</m>
    * => <m>C_1(38)</m> = <color red>000001</color>00110

</box>

<box 90% blue|Eliasův kód C2>

Přeuspořádání C1.

  * Bity nul se rozptýlý do kódového slova a na konec se přidá 1.

Př.:

  * <m>C_2(5)</m> = <color red>0</color>0<color red>0</color>1<color red>1</color>

</box>

<box 90% blue|Eliasův kód C3>

Vyjádření délky kódového slova pomocí C2.

  * Bity nul se rozptýlý do kódového slova a na konec se přidá 1.

Př.:

  * <m>C_3(50)</m> (<m>50_{10} = 110010_2</m>)
  * <m>|B(50)|</m> = 6 bitů
  * <m>C_1(6)</m> = <color red>001</color>10
  * <m>C_2(6)</m> = <color red>0</color>1<color red>0</color>0<color red>1</color>
  * <m>C_3(50)</m> = <color red>01001</color>10010
</box>

=== Kompresní kódování dat ===

Cílem:

  * minimalizace stupně kódu
  * při schopnosti on-line dekódování slov bez vkládání separátorů

<box 90% red|Kraftova nerovnost>
Prefixový q-ární kód s délkami kódových slov d1,d2,...,dm existuje právě tehdy, když je splněna Kraftova nerovnost:

<m>sum{i=1}{m}{q^{{-d}_{i}}} <= 1</m>

</box>

<box 90% red|McMillanova veta>
Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování.
</box>


== Komprese ==


  * **Neztrátová komprese (Lossless Compression)**
    * dekompresí se získají originální data
    * Cílem je zobrazení informace do bitového prostoru co nejméně převyšujícího množství informace obsažené v originálních datech.
    * Typicky komprese textů.


  * **Ztrátová komprese (Lossy Compression)**
    * Zefektivnění procesu a výsledku komprese za cenu snížení požadavků na přesnost rekonstrukce.
    * Informace nevýznamná pro následující zpracování se odstraňuje definitivně.
    * Typicky komprese obrázků, zvuku,...


  * Kompresní a dekompresní (rekonstrukční) algoritmus.

  * **Komprese** = Kódování zprávy délky P(X) [b] na zprávu délky L(X) [b]
    * cílem je dosažení L(X) << O(X)
    * ideálně L(X) -> H(X) (neurčitost zprávy; méně bity nelze zakódovat beztrátově)
  * **Kompresní poměr** = L(X)/O(X)
  * **Kompresní faktor** = O(X)/L(X)
  * **Kompresní zisk** = (O(X)-L(X))/O(X)
  * **Redundance zprávy** = R(X) = O(X) - H(X)
  * **Redundance komprimované zprávy** = R'(X) = L(X) - H(X)

  * **Statická komprese**
    * Neměnná procedura, model.
  * **Adaptivní komprese**
    * Procedura komprese se dynamicky mění.

  * **Fyzická komprese**
    * Ignoruje se význam komprimovaných dat.
  * **Logická komprese**
    * Pro dosažení lepších výsledků se zohledňuje/využívá význam komprimovaných dat.
    * Převážně ztrátová komprese.

== Kompresní metody ==

  * **Základní metody**
    * Brailovo písmo
    * Baudotův kód: 5bit kód, číslicová/písmenová změna
    * RLE (Run Length Encoding): náhrada opakujících se sousedních symbolů čítačem opakování a specifikací opakovaného symbolu
    * Kódování podle Bentleyho (Move-to-Front Coding): Dynamicky se tvořící abeceda
      * lokální adaptivita

  * **Statistické metody**

<box 90% blue|Shannon-Fanovo kódování>
  * Metoda na vytvoření prefixového kódu proměnné délky pro známou množinu znaků a četností.
  * Reprezentace binárním stromem na základě dělení posloupnosti na poloviny dle četností.
</box>

<box 90% blue|Huffmanovo kódování>
  * Metoda na vytvoření kódu s minimální redundancí.
  * Tvorba stromu opačným směrem než Shannon-Fannova metoda. (Od spoda nahoru.)
</box>

<box 90% blue|Aritmetické kódování>
Nekóduje jednotlivé symboly zprávy, ale používá jedno kódové slovo pro zakódování celé zprávy.
  * Kódem celé zprávy je číslo z intervalu <0,1)
</box>

  * **Slovníkové metody**: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku.

<box 90% blue|LZ77 (Lempel-Ziv)>
  * Jako slovník se používá jistá zpracovaná část zdrojového textu, vybíraná klouzajícím oknem, kódují se v něm obsažené řetězce proměnné délky.
  * Výstupem je trojice:
    * ukazatel počátku vzoru ve slovníku
    * délka vzoru
    * kódové slovo příštího symbolu za kódovým textem
</box>

<box 90% blue|LZ78 (Lempel-Ziv)>
  * Používá se samostatný dynamicky vytvářený slovník.
  * Výstupem je dvojice:
    * index vzoru ve slovníku
    * kódové slovo příštího symbolu za kódovým textem
</box>

<box 90% blue|LZW (Lempel-Ziv-Welch)>
  * Používá se samostatný dynamicky vytvářený slovník.
  * Potenciální elementy slovníku jsou v kódové knize přednastaveny.
  * Výstupem je jediný údaj -- index vzoru ve slovníku.
</box>

















==== Organizace souborů dat ====

=== Databáze ===

  * **databáze** = kolekce vzájemně explicitně souvisejících dat
    * spravovaná **systémem řízení báze dat**
  * **pole/položka/atribut** základní prvek dat
    * s každým atributem souvisí **datový typ** určující obor možných **hodnot** a **operací** nad nimi.
  * **záznam** = strukturovaná kolekce polí
  * **soubor** = pojmenovaná kolekce příbuzných záznamů



=== Systém souborů ===

  * **soubor** = pojmenovaná kolekce záznamů
    * přístup k souboru jako celku řeší **adresářová služba** systému souborů
    * přístup k datům souboru řeší **organizace souborů**
    * fyzický soubor
        * existuje ve vnější paměti
        * manipuluje s ním OS
        * zaznamenán v adresáři souborů
        * pojmenování vnějším jménem
    * logický soubor
      * souborová struktura z pohledu procesu
      * pojmenování jedinečným vnitřním jménem souboru
      * svázán s fyzickým souborem službou OS


  * **Systém souborů (File System)** = Sestava služeb pro manipulaci se soubory.

<box 90% red|Požadavky na systém souborů>
  * umožnit uživatelům/procesům manipulaci s daty na vnějších pamětech
  * zajišťovat validnost dat, eliminovat ztrátu dat
  * souběžná činnost více uživatelů/aplikací
  * podpora různých zařízení pomocí definovaného API
</box>

== Statické x dynamické soubory ==

  * návrh **statických** (neměnných souborů) je snadno dosažitelný
  * návrh **dynamický struktur** je obtížnější
    * dochází k doplňování, modifikaci a odstraňování záznamů
    * příklady:
      * B-strom
      * dynamický haš soubor
    * založený na rozšiřitelném hašování nebo lineárním hašování

== Záznamy pevné x proměnné délky ==

  * implicitní (fixní) délka záznamu
    * neuvádějí se oddělovače záznamů
  * variabilní délka záznamu se vyjadřuje:
    * explicitně (např. na začátku záznamu)
    * oddělovačem na konci záznamu
    * ukazatelem na záznam uloženým v jiném souboru (indexu)

Položky:
  * fixní struktura
    * bez oddělovačů
  * variabilní
    * explicitně
    * oddělovačem

Důvod volitelných délek:
  * obsah proměnné délky
  * seznam hodnot
  * volitelné položky

<box 90% red|Blok>
Samostatně manipulovatelná/adresovatelná datová jednotka na vnější paměti.

  * neblokovaný záznam
    * blok obsahuje právě jeden logický záznam
  * blokovaný záznam
    * blok obsahuje celistvý počet logických záznamů
  * přerostlé záznamy
    * záznamy jsou zapisované do bloků nezávisle na hranice
</box>


  * **homogenní soubor**
    * hodnoty položek jsou primitivní typy
    * všechny záznamy jsou jednoho typu
    * je deklarovatelný formou S(A1:D1,...,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot
  * **nehomogenní soubor**
    * hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu


=== Schéma organizace souborů ===


  * **Logické schéma**
    * logická paměť se člení na logické stránky (sekvenční/hierarchické uspořádání)
    * logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky)
  * **Fyzické schéma**
    * Zobrazení logických stránek do fyzických stránek konkrétního použitého typu vnější paměti.
  * **Implementační schéma**
    * Zajišťuje alokaci fyzických stránek v použitém zařízení.

{{:mgr-szz:in-pos:schema-souboru.png?300|}}


==Přístup k souborům==
  * sekvenční
    * aplikovatelné na pásce disku
  * přímý přístup
    * aplikovatelné na disku
    * určení místa pomocí indexu, nebo hašování

==Formy organizace souborů==
  * hromada
  * sekvenční soubor
  * indexovaný sekvenční soubor
  * indexovaný soubor
  * hašovaný soubor (soubor s přímým přístupem)


==Zamykání souborů==
  * **povinné**: zamčený soubor je nepřístupný
  * **poradní**: proces si může zjistit stav zámku a rozhodnout se

==Popis dat==
  * **implicitní**: aplikace/uživatel data zná
  * **metadata**: uvedená v hlavičce souboru
    * častá standardizace pro třídu aplikací


==Adresář==
Kolekce dat obsahující informace o souborech uchovávaných na disku (jméno, typ, adresa, délka, maximální délka, čas posledního přístupu...)

  * Sám je souborem.

**Struktury:**

<box 90% red|1-úrovňový adresář>
Jediný adresář v celém systému.

  * ➖ neřeší problém unikátnosti pojmenování souboru.
  * ➖ neřeší se problém seskupování souborů
</box>


<box 90% red|2-úrovňový adresář>
  * ➕ Separace adresářů a uživatelů. (cesta user/soubor)
  * ➕ Uživatelé mohou stejně pojmenovat různé soubory.
  * ➕ efektivní hledání
  * ➖ neřeší se problém seskupování souborů
  * ➖ nelze sdílet  
</box>

<box 90% red|stromová struktura>
  * ➕ efektivní hledání hodnoty v uzlu
  * ➕ řeší nezávislé pojmenování i seskupování

  * **pracovní adresář** = dynamicky určovaný výchozí bod v adresáři
    * **absolutní** x **relativní** cesta

  * **aliasing** = jeden objekt má více různých jmen

  * **File System Mounting** = Připojení nového souborového systému do stávající adresářové struktury (bod přidání = **mount point**).
</box>


== Řízení přístupu ==

  * volitelné řízení přístupu (vlastní určuje KDO a CO kdo může)
    * UNIX rwx/ugo
    * Access control lists
    * Capability Tickets
  * povinné řízení (práva k souborům prosazována bezpečnostní politikou)


 


==== Indexování a hašování ====

  * procházení přímo záznamů je při operacích velice pomalé -- indexy mají řádově menší velikost než samotné záznamy a jejich prohledávání je výrazně rychlejší
  * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk
  * často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů -- na základě indexů je možné efektivně provádět filtrování
  * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color>


__typy indexů:__

  * **řádné, lineární indexy**:
    * v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče
  * **hašované indexy**
    * využití hašovací funkce vyhledávacího klíče
  * **stromové indexy**
    * využití grafové struktury strom
  * **indexové bitové mapy**
    * pozice bitů v bitovém vektoru určují lokality záznamů
    * vhodné pro atributy s malým množstvím různých hodnot (uchováváme bitovou mapu pro každou hodnotu)

Indexy mohou být víceúrovňové -- "index do indexu" -- nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy

=== Řádné indexy ===

Obvykle pokud se mluví o indexech, jsou myšleny řádné.

**Primární x sekundární**
  * **primární index**
    * podle jeho klíče je uspořádán primární soubor se záznamy
    * může být hustý nebo řídký
  * sekundární index
    * určený pro dotazy založené na jiném vyhledávacím klíči než na primárním
    * musí být hustý

**Hustý x řídký**

  * **hustý**
    * indexový záznam pro každou hodnotu vyhledávacího klíče.
    * Typicky bývá uspořádán podle hodnoty klíče

{{:home:prog:husty.jpg?500|}}

  * **řídký**
    * indexový záznam pouze pro některé hodnoty vyhledávacího klíče
    * použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán

{{:home:prog:ridky.jpg?500|}}

<box 90% orange | Příklad>
**Uložený soubor se záznamy:**

^ ID (2B) ^ Jméno (20B)      ^ Rok narození (2B)       ^ Místo narození (16B)          ^ Telefon (4B) ^ Bydliště (16B) ^
| 1 | Bílá Alena | 1972 | Ostrava | xxxxxxxx | Brno |
| 2 | Novák Jan | 1952 | Praha | 123456789| Kladno |
| 3 | Novotný Tomáš | 1987 | Brno | 565656565| Vyškov |
| 4 | Procházka Petr | 1964 | Brno | 100001011| Řestoky |

**Hustý index pro atribut jméno:**
^ Jméno ^ ID ^
|Bílá Alena|1|
|Novák Jan|2|
|Novotný Tomáš|3|
|Procházka Petr|4|
Pokud chceme vyhledat místo narození Tomáše Novotného, pak je při sekvenčním prohledávání nutné načíst 2 · (2 B + 20 B + 2 B + 16 B + 4 B + 16 B) + 2 B + 20 B + 2 B + 16 B = 160 B. Při použití hustého indexu stačí načíst 3 · (20 B + 2 B) + 2 B + 20 B + 2 B + 16 B = 106 B. Pokud je index uložen v operační paměti, pak v obou případech stačí pouze jeden přístup na disk, avšak v prvním případě bude třeba číst výrazně více dat.

**Řídký index pro atribut jméno:**
^ Jméno ^ ID ^
|Bílá Alena|1|
|Novotný Tomáš|3|
Pokud je požadavek na vyhledání například Jana Nováka, nalezne se poslední záznam v uspořádání před ním (Alena Bílá) a dál se postupuje sekvenčně.

**Sekundární index pro atribut místo narození:**
^ Místo narození ^ ID ^
|Brno|3,4|
|Ostrava|1|
|Praha|2|
</box>


=== Hašování ===


<box 90% round blue | Definice>

**hašovací funkce (obecně)** = Funkce, která mapuje libovolně velký vstup na výstup fixní délky a není prostá.
**hašovací funkce (ve smyslu organizace souborů)** = Funkce řešící přístup k záznamům souboru s konstantní složitostí.
**kolize** = situace, kdy je pro více záznamů spočítána stejná adresa
  * při nalezení kolize umisťujeme nový prvek:
    * ve stejné paměti (**otevřené adresování**)
      * lineární, kvadratické adresování
      * řetězení kolizí
      * násobné hašování
    * v jiné paměťové oblasti (**closed addressing**)
      * umístění do **kapes** 
</box>


Požadované vlastnosti hašovací funkce:
  * je deterministická
  * je rychlá  
  * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče
  * pokrývá cílový prostor rovnoměrně
  * drobná změna ve vstupu vede k výrazné změně ve výstupu
  * prostá = //perfektní hašování//

== Statické hašování ==
  * používá se u souborů, které procházejí jen minimem změn
  * případné změny mohou negativně ovlivnit efektivitu hašování
    * pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost

== Dynamické hašování ==

<box 90% blue|Rozšiřitelné hašování>

  * k výpočtu adresy se používá pouze prvních //i// bitů z výstupu hašovací funkce; toto //i// se dynamicky mění -- pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se //i// zmenšuje
  * používá se u souborů s proměnným počtem záznamů
  * buckety jsou naplněné rovnoměrně -- pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují

{{:home:prog:rozhas.jpg|}}

  * hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce)
  * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)**
  * délku indexu vymezuje globální hloubka adresy kapsy
  * štěpení
    * globální hloubka > lokální hloubka -- na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva
    * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes
</box>


<box 90% blue|Lineární hašování>
  * řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s **přetokovými kapsami**
  * počet kapes udržuje tak, aby byly naplněny z např. 80 %
  * rozdíl oproti rozšiřitelnému hašování: **nemusí se vytvářet ani udržovat adresář kapes**, přesto počet kapes roste **lineárně**.
</box>





==== Dotazy ====

=== Vyhodnocení dotazu ===

Postup zpracování a optimalizace dotazu:

  - Převod dotazu na **syntaktický strom** pomocí parseru.
  - Převod na **logický plán** ve formě výrazů relační algebry.
  - Aplikací transformačních pravidel (viz níže) vznikne **vylepšený logický plán**
  - Odhad ceny provedení na základě různých statistik (počet záznamů, velikost záznamů, počet unikátních hodnot, ...).
  - **logický plán dotazu s velikostmi** - v PostgreSQL lze zobrazit příkazem EXPLAIN
  - Transformace na **fyzický plán** určující pořadí operací.
  - Výběr nejlevnějšího **fyzické plánu** (velikost výsledků, počet V/V operací).
  - Vyhodnocení vybraného **fyzického plánu**.

=== Transformační pravidla ===

= Transformační vztahy relační algebry zachovávající výsledek. Mohou ale zefektivnit samotné vyhodnocování. 


  * Přirozené spojení + kartézský součin a sjednocení + průnik
    * Protože jsou všechny atributy zachovány, není pořadí důležité.

  * Selekce
    * Konjunkci podmínek lze nahradit dvěma následnými selekcemi, nebo průnikem dvou selekcí.
    * Disjunkci podmínek lze nahradit sjednocením dvou selekcí.
    * Relace jsou multimnožiny!

  * Kombinace selekce a přirozeného spojení
    * Pokud selekce závisí jen na atributech jednoho z členů, pořadí operací neovlivní výsledek.

  * Vhodné transformace
    * selekce co nejdříve; nejblíže relacím
    * projekce co nejdříve; nejblíže relacím
    * eliminace společných podvýrazů
    * eliminace duplicit

=== Statistiky a odhady ===

  * odhad velikosti výsledku operace
    * počet záznamů
    * velikost záznamů
    * počet unikátních hodnot
    * Pro dobrý odhad jsou nutné aktuální hodnoty. => Aktualizace statistik ve vhodných intervalech (aktuálnost x zátěž).
  * odhad počtu V/V operací
    * cena všech operací (odhad ceny operace = počet čtení a zápisů z disku)
    * vstup se čte ze vstupu
    * výstup zůstává v operační paměti
    * operace CPU
    * komunikace po síti


<box 90% blue|Koncept Iterátoru>
  * Open: inicializace operace
    * příprava před vracením řádků výsledku
  * GetNext: vrácení dalšího řádku výsledku
  * Close: ukončení operace
    * uvolnění dočasné paměti

  * ➕ výsledek nemusí být vygenerován „naráz“
  * ➕ výsledek nezabírá paměť
  * ➕ výsledek nemusí být ukládán
  * ➕ operace lze řetězit (pipelining)
</box>

=== Optimalizace dotazů a schématu ===

== Ladění dotazu ==

  * Lokální změna = přepsání dotazu
    * První přístup ke zrychlení dotazu
    * Ovlivní pouze daný dotaz
  * Globální změna
    * Vytvoření indexu
    * Změna schématu
    * Rozdělení transakcí


  * Techniky přepsání dotazu
    * Rušení nadbytečných DISTINCT
    * (Korelované) poddotazy
    * Dočasné tabulky
    * Používání HAVING
    * Používání pohledů (VIEW)
    * Použití indexů
    * Uložené pohledy (materializedviews)


  * Vytvoření indexu
    * ➕ Zrychlí SELECT
    * ➖ Zpomalí INSERT, UPDATE, DELETE
      * Index se musí aktualizovat


== Optimalizace schématu ==


  * Funkční závislost (A -> B)
    * = Hodnoty atributu B zjistíme, pokud známe hodnoty atributů A


  * Normální formy
    * Normalizace = převod do BCNF (3NF)


<box 90% red|1NF>
Všechny atributy jsou atomické.
</box>

<box 90% red|2NF>
Všechny atributy závisí na celém klíči.
</box>

<box 90% red|3NF>
Všechny atributy závisí přímo na klíči.
  * Není tranzitivní závislost.
</box>

<box 90% red|Boyce-Codd NF>
Pro všechny funkční závislosti A->B platí jedno z následujících:
  * A->B je triviální funkční závislost (B je podmnožinou A)
  * A je superklíčem schématu
</box>


<box 90% blue|klíče>
**super klíč** = množina atributů jednoznačně určující každý záznam
**kandidátský klíč** = super klíč bez nadbytečných atributů
**primární klíč** = právě jeden vybraný kandidátský klíč
</box>





==== Zabezpečení báze dat ====

=== Přístupová práva ===

  * Analogie se souborovým systémem, ale jemnější.
  * Specifická práva pro:
    * tabulky
    * pohledy
    * sekvence
    * schéma
    * databáze
    * procedury
  * Pohledy (views)
    * základní nástroj pro řízení přístupu
  * Subjektem jsou obvykle uživatelé a skupiny
    * Často nazýváno jako authorization id nebo role
    * Subjekt „ostatní“ je označován jako PUBLIC
    * Povolení přístupu pro PUBLIC znamená povolení přístupu komukoli.

  * Uložené procedury
    * kontext provádění:
      * vlastník
      * volající
      * "určený uživatel"
















==== Transakce ====


Transakce je posloupnost operací (DML příkazů), které převedou datové schéma z jednoho konzistentního stavu do druhého (zpřístupňuje a aktualizuje data). Platí o ní, že je ACID:

  *  //**A**tomic (atomičnost)// – transakce se celá provede nebo se celá zruší
  *  //**C**onsistency (konzistence)// – po dokončení transakce je databáze konzistentní
  *  //**I**solation (izolovanost)// – různé transakce o sobě vzájemně nevědí
  *  //**D**urability (trvanlivost)// – po ukončení transakce jsou data trvale uložena

Více transakcí může být spouštěno současně, může však dojít k uváznutí (deadlocku). Chronologické pořadí provádění instrukcí souběžných transakcí je předem určeno pomocí plánu.

Každá transakce může nabývat těchto stavů: aktivní, částečně potvrzená, chybující, zrušená a potvrzená. Pokud byla transakce zrušena, je možné ji znovu spustit (nedošlo-li k logické chybě) nebo zamítnout.



=== Řízení souběžných transakcí ===

Plánovače
  * sériový plán: transakce jdou po sobě
  * serializovatelný plán: ekvivalentní sériovému
  * Plánovače:
    * **optimistické** (předpokládají málo konfliktů a nechávají věci plynout, při selhání transakce vracejí, ruší)
    * **pesimistické** (předpokládají hodně konfliktů, předchází jim silnou serializací)

Souběžné zpracování (zajišťuje izolovanost)
  * zámky: 
     * exkluzivní -- jen jedna transakce čte a píše, 
     * sdílený (shared) -- více čtení, žádný write
     * (v ideálním případě se rovná idální serializaci)
     * zámky zpravuje správce zámků a transakce s mím mluví protokolem
        * Dvoufázový transakční protokol na bázi zamykání (růstová fáze - zamykání, couvací fáze - uvolňování po provedení transakce)
        * Grafový (stromový) protokol řízení souběhu transakcí (jednofázový, zná pořadí přístupu transakcí k datům)
        * oba pesimistické plánovače
     * správa zámků představuje netriviální režii.
  * Časová razítka -- jiné řešení transakce mají čas, kdy vznikly. Nejstarší jde nejdřív. Pesimistické plánování
  * Protokol řízení souběhu transakcí na bázi validace (optimistický plánovač). Na konci transakce se zvaliduje, zda došlo ke konfliktu, pokud ano, jedna transakce se abortuje.




=== Systémy obnovy transakcí po výpadku ===

  * Klasifikace výpadků
     * výpadek transakce
       * logická chyba (např. data nenalezena)
       * systémová chyba (např. deadlock)
     * zhroucení systému
     * porucha disku

Pro obnovu výpadku požadujeme, aby tranakce byly atomické, databáze konzistentní.

Žurnálování (log, deník)
  * O prováděných tranakcích (a jejích operacích) si vedu záznam v žurnálu.
  * Při výpadku můžu použít žurnál k REDO, UNDO...
  * Místo žurnálování můžu použít redundanci (RAID)

== Undo logging ==
  * V případě výpadku se některé operace zruší (z nedokončených transakcí)
  * Pro každou akci vytvoř v žurnálu záznam obsahující starou hodnotu 
  * Před změnou x na disku musí být na disku záznamy žurnálu týkající se x - Tzv. write ahead logging (WAL)
  * Před vytvořením záznamu <commit> v žurnálu musí být všechny zápisy transakce uloženy na disku.

== Redo logging ==
  * V případě výpadku se některé operace dokončí
  * Změny později provedené transakcí jsou ukládány Tj. při potvrzení (commit) -- Ušetření zápisů na disk
  * Při obnově jsou ignorovány nedokončené transakce
  * Vyžaduje uložení žurnálu před uložením změn v DB.

== Check points ==

  * pravidelné ukládání kontrolních stavů databáze pro případné pozdější obnovení
  * něco jako otisky DB , aby se při obnově nemusely dělat od začátku
  * také dálají redo, undo


==== Zdroje ====

  * slidy PV062 (verze jaro 2015)
  * slidy PA150 (podzim 2016)
  * slidy pa152 (jaro 2019)
  * http://statnice.dqd.cz/home:prog:ap12
  * http://statnice.dqd.cz/mgr-szz:in-bit:14-bit