hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Následující verze | Předchozí verze | ||
|
mgr-szz:in-pos:3-pos [2019/05/22 12:11] lachmanfrantisek zadání |
mgr-szz:in-pos:3-pos [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 14: | Řádek 14: | ||
| ===== Vypracová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. | ||
| + | |||
| + | <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 | ||
