Obsah

IN-POS 3. Databáze

Zadání

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.

Množství informace

Množství získané informace odpovídá velikosti odstraněné neurčitosti získáním informace.

i(A) = - log P(A)

Pro log_2 je jednotkou bit.

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.)

H(X) = sum{i=1}{s}{p_i log_2 p_i}

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

Klasifikace kódů

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 14/8 = 1.75 b/symbol
Eliasovy kódy

Eliasův kód C1

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

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

Př.:

  • n=38, hat{B}(38)= 00110_2 |B(38)|=6
    • ⇒ C_1(38) = 00000100110

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ř.:

  • C_2(5) = 00011

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ř.:

  • C_3(50) (50_{10} = 110010_2)
  • |B(50)| = 6 bitů
  • C_1(6) = 00110
  • C_2(6) = 01001
  • C_3(50) = 0100110010

Kompresní kódování dat

Cílem:

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:

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

McMillanova veta

Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování.
Komprese
Kompresní metody

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í.

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.)

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)

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

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

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.

Organizace souborů dat

Databáze

Systém souborů

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
Statické x dynamické soubory
Záznamy pevné x proměnné délky

Položky:

Důvod volitelných délek:

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

Schéma organizace souborů

Přístup k souborům
Formy organizace souborů
Zamykání souborů
Popis dat
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…)

Struktury:

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ů

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

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).
Řízení přístupu

Indexování a hašování

typy indexů:

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í

Hustý x řídký

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á Alena1
Novák Jan2
Novotný Tomáš3
Procházka Petr4

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á Alena1
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
Brno3,4
Ostrava1
Praha2

Hašování

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

Požadované vlastnosti hašovací funkce:

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

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í

  • 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

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ě.

Dotazy

Vyhodnocení dotazu

Postup zpracování a optimalizace dotazu:

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

Statistiky a odhady

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)

Optimalizace dotazů a schématu

Ladění dotazu
Optimalizace schématu

1NF

Všechny atributy jsou atomické.

2NF

Všechny atributy závisí na celém klíči.

3NF

Všechny atributy závisí přímo na klíči.
  • Není tranzitivní závislost.

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

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íč

Zabezpečení báze dat

Přístupová práva

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:

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

Souběžné zpracování (zajišťuje izolovanost)

Systémy obnovy transakcí po výpadku

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

Žurnálování (log, deník)

Undo logging
Redo logging
Check points

Zdroje