hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
mgr-szz:in-pos:3-pos [2019/06/13 16:39] lachmanfrantisek |
mgr-szz:in-pos:3-pos [2020/04/12 16:56] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== 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> | ||
| - | |||
| - | |||
| - | === 1. Statické organizace souborů ==== | ||
| - | * 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 | ||
| - | |||
| - | **Do statické organizace souborů patří:** | ||
| - | * **hromada (neuspořádaný sekvenční soubor)** | ||
| - | * Hromada (heap) je nejjednodušší schéma organizace souboru, kdy jsou záznamy v souboru jen náhodně naházeny za sebou. Časová složitost vyhledávání je O(n) (lineární), pokud n je počet záznamů. Jde o nehomogenní soubor, kde záznamy obvykle nemají pevnou délku. | ||
| - | * **neuspořádaný sekvenční soubor** | ||
| - | * homogenní soubor | ||
| - | * sekvenční přístup | ||
| - | * homogenní obdoba hromady | ||
| - | {{:home:prog:neusek.jpg?500|}} | ||
| - | * **uspořádaný sekvenční soubor** | ||
| - | * V uspořádaném sekvenčním souboru jsou záznamy řazeny podle vyhledávacího klíče. Aktualizované záznamy se umístí do zvláštního souboru a až při další operaci //reorganization// jsou přidány do primárního souboru. Složitost nalezení záznamu je také O(n) (lineární), ale pokud se hledá podle klíče, podle kterého jsou záznamy seřazeny, a navíc je soubor na médiu s přímým přístupem, sníží se na O(log n) (logaritmická). | ||
| - | * **Primární soubor** + **soubor aktualizací** (dodatečných změn) | ||
| - | * **Soubor aktualizací** nebývá seřazený (dopisuje se na konec) | ||
| - | * **Reorganizace**: seřadíme soubor aktualizací + zatřídíme s primárním souborem do nového primárního souboru | ||
| - | * nevýhody primárního souboru -- při vkládání je nutná náročná reorganizace | ||
| - | * **keysort** -- snižuje náklady na reorganizaci -- udržuje se soubor (nemusí být seřazený) + index (je vždy seřazený) | ||
| - | * **řetězené struktury** -- řetězení usnadní následná vkládání a rušení záznamů | ||
| - | Ukázka uspořádaného sekvenčního souboru -- keysort: | ||
| - | {{:home:prog:usp_sekv_soubor_1_obr.png?500| Uspořádaný sekvenční soubor -- keysort}} | ||
| - | Ukázka uspořádaného sekvenčního souboru -- řetězené struktury: | ||
| - | {{:home:prog:usp_sekv_soubor_2_obr.png?500| Uspořádaný sekvenční soubor -- řetězené struktury}} | ||
| - | * **index-sekvenční soubor** | ||
| - | * části: primární soubor, index a oblast přetečení | ||
| - | * primární soubor je seřazený podle primárního klíče, ke kterému je vytvořena struktura indexů | ||
| - | * 2 možné přístupy -- indexový i sekvenční | ||
| - | * Indexem se vymezuje oblast stránek v primárním souboru, kde záznam může ležet, tato oblast se prohlíží sekvenčně | ||
| - | * buckety pro přesahy, nutná občasná reorganizace | ||
| - | {{:home:prog:index-sekvencni.png?500|}} | ||
| - | * **indexovaný soubor** | ||
| - | * seřadí se index, primární soubor se záznamy je neseřazený | ||
| - | * Indexovaný soubor znamená primární soubor plus indexy pro různé vyhledávací klíče. Neindexují se už stránky, ale přímo záznamy, a proto primární soubor nemusí být nutně seřazený. Index může být podobný jako u index-sekvenčního souboru, pro záznamy se stejným klíčem je ale vhodné, aby byly na všech úrovních indexu kromě poslední sloučené. Při aktualizaci se nepoužívá oblast přetečení, mění se pouze index. | ||
| - | {{:home:prog:index.png?500|}} | ||
| - | * **soubor s přímým přístupem** (tak kdyz je tam hash tak to asi patri do dynamickych struktur) | ||
| - | * algoritmická transformace vyhledávacího klíče na adresu záznamu | ||
| - | * hašování | ||
| - | |||
| - | |||
| - | === 2. Dynamické organizace souborů === | ||
| - | Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální. | ||
| - | - B-strom | ||
| - | - dynamický haš soubor | ||
| - | * založený na rozšiřitelném hašování nebo lineárním hašování | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | === 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|}} | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | <box 90% round blue | Definice>**soubor 1** = pojmenovaná kolekce souvisejících záznamů | ||
| - | **soubor 2** = logická paměťová jednotka zobrazovaná operačním systémem do fyzického paměťového zařízení | ||
| - | **záznam** = kolekce atributů charakterizujících jistý objekt | ||
| - | **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...)</box> | ||
| - | |||
| - | == Možná formátování == | ||
| - | - volné formátování -- sekvenčně řazené záznamy pevné i proměnlivé délky | ||
| - | - komplexní formátování -- soubor obsahuje vhodné řídící struktury nebo se k záznamům přistupuje přes přístupové funkce (B-stromy, haše...) | ||
| - | |||
| - | == Uložení souborů na disku == | ||
| - | - souvislá alokace datových bloků | ||
| - | * soubor je na disku uložen v souvislé posloupnosti datových bloků | ||
| - | - alokace datových bloků pomocí zřetězeného seznamu | ||
| - | * každý datový blok obsahuje data a ukazatel na následující datový blok | ||
| - | - alokace datových bloků pomocí tabulky | ||
| - | * alokace datových bloků je založená na zřetězeném seznamu, ale ukazatele na následující datový blok jsou uloženy v tabulce FAT | ||
| - | - i-nodes | ||
| - | * i-node je struktura, která obsahuje jak atributy souboru, tak adresy datových bloků, ve kterých je uložen obsah souboru | ||
| - | |||
| - | |||
| - | |||
| - | * Popis dat | ||
| - | * implicitní: aplikace/uživatel data zná | ||
| - | * metadata: uvedená v hlavičce souboru | ||
| - | * častá standardizace pro třídu aplikací | ||
| - | |||
| - | |||
| - | * **Klasifikace souborových organizací** | ||
| - | * sekvenční přístup (aplikovatelné na pásce, na disku) | ||
| - | * přímý přístup (aplikovatelné na disku) | ||
| - | * Určení místo pomocí **indexu**, nebo **hašování** | ||
| - | |||
| - | * Zamykání souborů | ||
| - | * povinné: zamčený soubor je nepřístupný | ||
| - | * poradní: proces si může zjistit stav zámku a rozhodnout se | ||
| - | |||
| - | * Adresář = kolekce dat obsahující informace o souborech uschovaných na disku. | ||
| - | * 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) | ||
| - | |||
| - | <box 90% blue|Inode> | ||
| - | Řídící struktura obsahující klíčové informace potřebné pro oeprační systém při správě konkrétního souboru. | ||
| - | </box> | ||
| - | |||
| - | === Implementace systému souborů === | ||
| - | |||
| - | <box 90% blue|File Allocation Table (FAT)> | ||
| - | = vázané přidělování diskového prostoru | ||
| - | |||
| - | * využití v MS-DOS, Windows | ||
| - | * jednoduchá metoda | ||
| - | * vázaný seznam nesousedních bloků disku | ||
| - | * ➖ pevný počet položek | ||
| - | |||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Mapa disku, UNIX> | ||
| - | * Inode obsahuje (mimo jiné): | ||
| - | * přímé odkazy na bloky (12x4KB) | ||
| - | * single indirect (až 48MB) | ||
| - | * double indirect (až 4GB) | ||
| - | * triple indirect (až 4TB) | ||
| - | </box> | ||
| - | |||
| - | |||
| - | <box 90% blue|NTFS> | ||
| - | * základem je NTFS svažek (volume) uložýí na diskové oblasti | ||
| - | * všechna metadata ukládána do svazku jako soubory | ||
| - | * struktura | ||
| - | * ID sektor (boot) | ||
| - | * tabulka Master File Table (MFT) -- obsahuje záznamy o souborech (i metadata) | ||
| - | * ostatní systémové soubory | ||
| - | * zrcadlová kopie MFT | ||
| - | * soubor s protokolem pro obnovu | ||
| - | * metadata souborového systému | ||
| - | * soubor s bitovou mapou volných a přidělených alokačních bloků | ||
| - | * soubor s definicí vadných sektorů | ||
| - | * uživatelské adresáře a data | ||
| - | </box> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ==== 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ů | ||
| - | * 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é. | ||
| - | **Dělení 1** | ||
| - | - 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ý | ||
| - | **Dělení 2** | ||
| - | //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ě)** = převedení libovolně dlouhého vstupu na výstup pevné délky | ||
| - | **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 | ||
| - | * obvykle se řeší pomocí bucketů -- každé paměťové místo má předepsanou kapacitu záznamů, ve které se následně vyhledává lineárně | ||
| - | </box> | ||
| - | Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá. | ||
| - | 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ě | ||
| - | |||
| - | == 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í == | ||
| - | * 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í | ||
| - | * Druhy: | ||
| - | * rozšiřitelné hašování | ||
| - | {{:home:prog:rozhas.jpg|}} | ||
| - | <note> | ||
| - | * 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 | ||
| - | </note> | ||
| - | * lineární hašování | ||
| - | <note> | ||
| - | * ř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ě**. | ||
| - | </note> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ==== Dotazy ==== | ||
| - | |||
| - | === Vyhodnocení dotazu === | ||
| - | |||
| - | Postup zpracování a optimalizace dotazu: | ||
| - | |||
| - | - dotaz | ||
| - | - syntaktický strom dotazu | ||
| - | - logický plán dotazu - v pojmech relační algebry | ||
| - | - vylepšený logický plán dotazu | ||
| - | - logický plán dotazu s velikostmi - v PostgreSQL lze zobrazit příkazem EXPLAIN | ||
| - | - fyzický plán dotazu | ||
| - | - vyhodnocení | ||
| - | |||
| - | Dotaz se nejprve pomocí parseru převede na syntaktický strom reprezentující strukturu dotazu. Ten se po té zpracuje do výrazů relační algebry (logický plán dotazu). Pomocí transformačních pravidel (kombinace přirozeného spojení, kartézského součinu, sjednocení, selekce a projekce) dále vznikne vylepšený logický plán. Nyní se za pomocí různých statistik (počet záznamů, velikost záznamů v bajtech, počet obsazených bloků, počet unikátních hodnot daného atributu) odhadnou velikosti výsledků, které ovlivňují odhad ceny provedení. Následně se logický plán transformuje na fyzický plán, který určí pořadí operací nutných k vykonání. Porovnají se různé fyzické plány, odhadnou se náklady (velikost výsledků, počet V/V operací) a zvolí se nejlevnější. Nakonec se daný plán provede a tím se získá výsledek. | ||
| - | |||
| - | === Transformační pravidla === | ||
| - | |||
| - | * Přirozené spojení, kartézský součin, 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 | ||
| - | * Použití indexů | ||
| - | * Rušení nadbytečných DISTINCT | ||
| - | * (Korelované) poddotazy | ||
| - | * Dočasné tabulky | ||
| - | * Používání HAVING | ||
| - | * Používání pohledů (VIEW) | ||
| - | * 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> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ==== 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 | ||
