IN-POS 3. Databáze

• 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

: doladit, doplnit, zpřehlednit

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.

• Abeceda = konečná množina znaků (prvků abecedy, písmen,…)
• Kódové slovo = slovo (posloupnost znaků) v kódové abecedě
• Kódování = funkce
• Kód = kódem daného kódování se rozumí obor hodnot zobrazení K

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

  10110010001101 

Cílem:

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

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

• 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

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

• 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ů

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

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

• 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

• 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

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

• sekvenční
  • aplikovatelné na pásce disku
• přímý přístup
  • aplikovatelné na disku
  • určení místa pomocí indexu, nebo hašování

• hromada
• sekvenční soubor
• indexovaný sekvenční soubor
• indexovaný soubor
• hašovaný soubor (soubor s přímým přístupem)

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

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

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:

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

• 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: { vyhledávací klíč ; ukazatel na záznam }

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

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

• ří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

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í

• 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

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

• 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

• 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

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

• 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 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:

• Atomic (atomičnost) – transakce se celá provede nebo se celá zruší
• Consistency (konzistence) – po dokončení transakce je databáze konzistentní
• Isolation (izolovanost) – různé transakce o sobě vzájemně nevědí
• Durability (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.

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.

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

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

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

• 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

• 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