hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
|
mgr-szz:in-pos:3-pos [2019/06/08 18:41] lachmanfrantisek dotazy, transakce, zabezpečení |
mgr-szz:in-pos:3-pos [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 77: | Řádek 77: | ||
| - | === 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> | ||
| == Eliasovy kódy == | == Eliasovy kódy == | ||
| - | <box 90% blue|Eliasův kód> | + | <box 90% blue|Eliasův kód C1> |
| Kódování celých čísel u kterých není předem známá horní hranice. | Kódování celých čísel u kterých není předem známá horní hranice. | ||
| Řádek 104: | Řádek 87: | ||
| - Zapíšeme číslo dvojkově. | - 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. | - 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. | |
| - | </box> | + | |
| - | + | ||
| - | <box 90% blue|Eliasův kód C1> | + | |
| - | + | ||
| - | Prefix 0 určuje délku binární reprezentace. | + | |
| Př.: | Př.: | ||
| Řádek 126: | Řádek 104: | ||
| Př.: | Př.: | ||
| - | * <m>C_2(5)</m> = 0<color red>0</color>0<color red>1</color>1 | + | * <m>C_2(5)</m> = <color red>0</color>0<color red>0</color>1<color red>1</color> |
| </box> | </box> | ||
| Řádek 144: | Řádek 122: | ||
| * <m>C_3(50)</m> = <color red>01001</color>10010 | * <m>C_3(50)</m> = <color red>01001</color>10010 | ||
| </box> | </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 == | == Komprese == | ||
| Řádek 210: | Řádek 207: | ||
| * **Slovníkové metody**: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku. | * **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> | + | <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ěnlivé. | + | * 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: | * Výstupem je trojice: | ||
| * ukazatel počátku vzoru ve slovníku | * ukazatel počátku vzoru ve slovníku | ||
| Řádek 218: | Řádek 215: | ||
| </box> | </box> | ||
| - | <box 90% blue|LZ78> | + | <box 90% blue|LZ78 (Lempel-Ziv)> |
| * Používá se samostatný dynamicky vytvářený slovník. | * Používá se samostatný dynamicky vytvářený slovník. | ||
| * Výstupem je dvojice: | * Výstupem je dvojice: | ||
| Řádek 225: | Řádek 222: | ||
| </box> | </box> | ||
| - | <box 90% blue|LZW> | + | <box 90% blue|LZW (Lempel-Ziv-Welch)> |
| * Používá se samostatný dynamicky vytvářený slovník. | * Používá se samostatný dynamicky vytvářený slovník. | ||
| * Potenciální elementy slovníku jsou v kódové knize přednastaveny. | * Potenciální elementy slovníku jsou v kódové knize přednastaveny. | ||
| Řádek 285: | Řádek 282: | ||
| </box> | </box> | ||
| + | == Statické x dynamické soubory == | ||
| - | === 1. Statické organizace souborů ==== | + | * návrh **statických** (neměnných souborů) je snadno dosažitelný |
| - | * homogenní soubor -- hodnoty položek jsou primitivní typy, všechny záznamy jsou jednoho typu | + | * návrh **dynamický struktur** je obtížnější |
| - | *je deklarovatelný formou S(A1:D1,...,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot | + | * dochází k doplňování, modifikaci a odstraňování záznamů |
| - | * nehomogenní soubor -- hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu | + | * příklady: |
| + | * B-strom | ||
| + | * dynamický haš soubor | ||
| + | * založený na rozšiřitelném hašování nebo lineárním hašování | ||
| - | **Do statické organizace souborů patří:** | + | == Záznamy pevné x proměnné délky == |
| - | * **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í | + | |
| + | * 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) | ||
| - | === 2. Dynamické organizace souborů === | + | Položky: |
| - | Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální. | + | * fixní struktura |
| - | - B-strom | + | * bez oddělovačů |
| - | - dynamický haš soubor | + | * variabilní |
| - | * založený na rozšiřitelném hašování nebo lineárním hašování | + | * 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 | ||
| Řádek 344: | Řádek 340: | ||
| * logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky) | * logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky) | ||
| * **Fyzické schéma** | * **Fyzické schéma** | ||
| - | * Zobrazení logických stránek do fyzických stránek konkríétního použitého typu vnější paměti. | + | * 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** | * **Implementační schéma** | ||
| * Zajišťuje alokaci fyzických stránek v použitém zařízení. | * Zajišťuje alokaci fyzických stránek v použitém zařízení. | ||
| Řádek 351: | Řádek 347: | ||
| + | ==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ů== | |
| - | <box 90% round blue | Definice>**soubor 1** = pojmenovaná kolekce souvisejících záznamů | + | * hromada |
| - | **soubor 2** = logická paměťová jednotka zobrazovaná operačním systémem do fyzického paměťového zařízení | + | * sekvenční soubor |
| - | **záznam** = kolekce atributů charakterizujících jistý objekt | + | * indexovaný sekvenční soubor |
| - | **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> | + | * indexovaný soubor |
| - | + | * hašovaný soubor (soubor s přímým přístupem) | |
| - | == 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 | + | |
| + | ==Zamykání souborů== | ||
| + | * **povinné**: zamčený soubor je nepřístupný | ||
| + | * **poradní**: proces si může zjistit stav zámku a rozhodnout se | ||
| - | * Popis dat | + | ==Popis dat== |
| - | * implicitní: aplikace/uživatel data zná | + | * **implicitní**: aplikace/uživatel data zná |
| - | * metadata: uvedená v hlavičce souboru | + | * **metadata**: uvedená v hlavičce souboru |
| - | * častá standardizace pro třídu aplikací | + | * častá standardizace pro třídu aplikací |
| - | * **Klasifikace souborových organizací** | + | ==Adresář== |
| - | * sekvenční přístup (aplikovatelné na pásce, na disku) | + | 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...) |
| - | * přímý přístup (aplikovatelné na disku) | + | |
| - | * Určení místo pomocí **indexu**, nebo **hašování** | + | |
| - | * Zamykání souborů | + | * Sám je souborem. |
| - | * 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. | + | **Struktury:** |
| - | * Sám je souborem. | + | |
| - | * Struktury: | + | |
| <box 90% red|1-úrovňový adresář> | <box 90% red|1-úrovňový adresář> | ||
| Řádek 422: | Řádek 408: | ||
| - | * Řízení přístupu | + | == Ří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> | + | * volitelné řízení přístupu (vlastní určuje KDO a CO kdo může) |
| - | Řídící struktura obsahující klíčové informace potřebné pro oeprační systém při správě konkrétního souboru. | + | * UNIX rwx/ugo |
| - | </box> | + | * Access control lists |
| + | * Capability Tickets | ||
| + | * povinné řízení (práva k souborům prosazována bezpečnostní politikou) | ||
| - | === 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> | + | ==== Indexování a hašování ==== |
| - | <box 90% blue|Mapa disku, UNIX> | + | * 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ší |
| - | * Inode obsahuje (mimo jiné): | + | * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk |
| - | * přímé odkazy na bloky (12x4KB) | + | * č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í |
| - | * single indirect (až 48MB) | + | * forma indexu: <color blue>{ vyhledávací klíč ; ukazatel na záznam }</color> |
| - | * double indirect (až 4GB) | + | |
| - | * triple indirect (až 4TB) | + | |
| - | </box> | + | |
| - | <box 90% blue|NTFS> | + | __typy indexů:__ |
| - | * 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> | + | |
| + | * **řá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 | ||
| - | ==== Indexování a hašování ==== | + | {{:home:prog:husty.jpg?500|}} |
| - | * 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ší | + | * **řídký** |
| - | * díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk | + | * indexový záznam pouze pro některé hodnoty vyhledávacího klíče |
| - | * č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í | + | * použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádá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|}} | {{:home:prog:ridky.jpg?500|}} | ||
| Řádek 532: | Řádek 500: | ||
| === Hašování === | === 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í | + | |
| + | <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 | **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ě | + | * 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> | </box> | ||
| - | Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá. | + | |
| Požadované vlastnosti hašovací funkce: | Požadované vlastnosti hašovací funkce: | ||
| * je deterministická | * je deterministická | ||
| Řádek 543: | Řádek 522: | ||
| * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | * vypočítává se z hodnot všech nebo alespoň většiny bitů klíče | ||
| * pokrývá cílový prostor rovnoměrně | * 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í == | == Statické hašování == | ||
| * používá se u souborů, které procházejí jen minimem změ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 | + | * 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í == | == 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 | * 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ů | * 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í | * 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|}} | {{: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) | * 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//)** | * jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce **//h//(//k//)** | ||
| Řádek 562: | Řádek 546: | ||
| * 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 -- 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 | * globální hloubka = lokální hloubka -- musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes | ||
| - | </note> | + | </box> |
| - | * lineární hašování | + | |
| - | <note> | + | |
| + | <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** | * ř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 % | * 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ě**. | * 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> | + | </box> |
| Řádek 580: | Řádek 565: | ||
| Postup zpracování a optimalizace dotazu: | Postup zpracování a optimalizace dotazu: | ||
| - | - dotaz | + | - Převod dotazu na **syntaktický strom** pomocí parseru. |
| - | - syntaktický strom dotazu | + | - Převod na **logický plán** ve formě výrazů relační algebry. |
| - | - logický plán dotazu - v pojmech relační algebry | + | - Aplikací transformačních pravidel (viz níže) vznikne **vylepšený logický plán** |
| - | - vylepšený logický plán dotazu | + | - 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 | + | - **logický plán dotazu s velikostmi** - v PostgreSQL lze zobrazit příkazem EXPLAIN |
| - | - fyzický plán dotazu | + | - Transformace na **fyzický plán** určující pořadí operací. |
| - | - vyhodnocení | + | - Výběr nejlevnějšího **fyzické plánu** (velikost výsledků, počet V/V operací). |
| - | + | - Vyhodnocení vybraného **fyzického plánu**. | |
| - | 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 === | === Transformační pravidla === | ||
| - | * Přirozené spojení, kartézský součin, sjednocení, průnik | + | = 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é. | * Protože jsou všechny atributy zachovány, není pořadí důležité. | ||
| Řádek 651: | Řádek 638: | ||
| * Techniky přepsání dotazu | * Techniky přepsání dotazu | ||
| - | * Použití indexů | ||
| * Rušení nadbytečných DISTINCT | * Rušení nadbytečných DISTINCT | ||
| * (Korelované) poddotazy | * (Korelované) poddotazy | ||
| Řádek 657: | Řádek 643: | ||
| * Používání HAVING | * Používání HAVING | ||
| * Používání pohledů (VIEW) | * Používání pohledů (VIEW) | ||
| + | * Použití indexů | ||
| * Uložené pohledy (materializedviews) | * Uložené pohledy (materializedviews) | ||
| + | |||
| * Vytvoření indexu | * Vytvoření indexu | ||
| Řádek 696: | Řádek 684: | ||
| - | + | <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> | |
| - | + | ||
| - | + | ||
