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 organizace souborů dat, indexování, hašování
+++ mgr-szz:in-pos:3-pos [2020/04/12 16:56] (aktuální)
@@ Řádek 15: / Řádek 15: @@
 ===== Vypracování =====
+FIXME: doladit, doplnit, zpřehlednit
 ==== Kódování dat ====
@@ Řádek 76: / Řá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 ==
-<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.
@@ Řádek 103: / Řádek 87: @@
   - 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.
-</box>
-<box 90% blue|Eliasův kód C1>
-Prefix 0 určuje délku binární reprezentace.
 Př.:
@@ Řádek 125: / Řádek 104: @@
 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>
@@ Řádek 143: / Řádek 122: @@
   * <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 ==
@@ Řádek 209: / Řádek 207: @@
   * **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:
     * ukazatel počátku vzoru ve slovníku
@@ Řádek 217: / Řádek 215: @@
 </box>
-<box 90% blue|LZ78>
+<box 90% blue|LZ78 (Lempel-Ziv)>
   * Používá se samostatný dynamicky vytvářený slovník.
   * Výstupem je dvojice:
@@ Řádek 224: / Řádek 222: @@
 </box>
-<box 90% blue|LZW>
+<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.
@@ Řádek 284: / Řádek 282: @@
 </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 343: / Řádek 340: @@
     * 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.
+    * 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í.
@@ Řádek 350: / Řá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ář>
@@ Řádek 421: / Řá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|}}
@@ Řádek 531: / Řádek 500: @@
 === 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
-  * 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>
-Perfektní hašovací funkce -- hašovací funkce //h//, která je prostá.
 Požadované vlastnosti hašovací funkce:
   * je deterministická
@@ Řádek 542: / Řádek 522: @@
   * 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
+  * 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í
-  * 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//)**
@@ Řádek 561: / Řá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 -- 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**
   * 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>
+</box>
@@ Řádek 575: / Řádek 561: @@
 ==== Dotazy ====
-=== Vyhodnocení dotazů ===
+=== 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>
@@ Řádek 597: / Řádek 697: @@
 === 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"
@@ Řádek 604: / Řádek 735: @@
 ==== 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
@@ Řádek 616: / Řádek 814: @@
   * 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

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

Nahoru