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/08 17:03]
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í =====
-==== 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>
-=== 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 ==
-<box 90% blue|Eliasův kód>
-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.
-</box>
-<box 90% blue|Eliasův kód C1>
-Prefix 0 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> = 0<color red>0</color>0<color red>1</color>1
-</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>
-== 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>
-  * 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é.
-  * 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>
-  * 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>
-  * 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í 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 ===
-==== Zdroje ====
-  * slidy PV062 (verze jaro 2015)
-  * slidy PA150 (podzim 2016)
-  * http://statnice.dqd.cz/home:prog:ap12

mgr-szz/in-pos/3-pos.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru