{{TOC float}}
{{Sources|
''Tento výcuc ke [[Státnice|magisterským státnicovým]] otázkám z [[Státnice - Informatika - Datové struktury|datových struktur]] pochází z poznámek k [[OZD I|Organizace a zpracování dat I]] -- [[User:Tuetschek|Tuetschek]] 01:08, 18 Aug 2010 (CEST)''<br/>
''Diakritika přidána automaticky programem michalisekSpell -- [[User:Michalisek|Michalisek]] 16:00, 28 Aug 2010''
}}
== Základní pojmy ==
* Logickou jednotkou dat je ''záznam'', který má ''atributy'' se jmény a doménami (max. 1 hodnota <math> \forall\,\!</math> atribut.
* ''(Homogenní) soubor'' je kolekce (multimnožina) záznamů. Na souboru jsou definovány operace '''INSERT''', '''DELETE''', '''UPDATE''' a '''FETCH'''.
* Pro soubory s neopakujícími se záznamy je ''klíč'' množina atributů, které záznam jednoznačně identifikují v souboru. Jeden nich z klíčů se označuje jako ''primární''.
* ''Vyhledávací klíč '' je něco jiného -- k jeho jedné hodnotě se dá najít množina odpovídajících záznamů. Jsou tři druhy vyhledávacích klíčů: ''hodnotový'', ''hashovaný'' a ''relativní'' (přímo pozice v souboru).
* Logickému záznamu odpovídá '' fyzický záznam '' délky <math>R\,\!</math>, BÚNO na magnetickém disku; ten může obsahovat další data - oddělovače, ukazatele, hlavičky. Záznamy mají buď pevnou, nebo proměnnou délku.
* Fyzické záznamy jsou organizovány do ''bloků'' délky <math>B\,\!</math> -- hlavní jednotky přenosu mezi RAM a HDD.
* <math>\frac{B}{R}\,\!</math> se nazývá ''blokovací faktor'' (<math> \lfloor b\rfloor\,\!</math>).
* ''Schéma organizace souborů'' (SOS) je popis logické paměťové struktury, ve které se soubor nachází. Může obsahovat více logických souborů, ten který nese uživatelská data je ''primární'', jeho délka v počtu záznamů se značí <math> N\,\!</math>. Další operace nad SOS jsou '''BUILD, REORGANIZATION, OPEN, CLOSE'''.
* Dotaz je každá funkce, která pro zadaný argument vrátí "odpověď" -- množinu záznamů. Dotazy mohou být buď na ''úplnou'', nebo jen ''částečnou shodu'', popř. ''intervalovou shodu''.
* ''Vyváženost struktury'' je zajištění omezení délky cesty při vyhledávání nějakým výrazem ( <math> O(\log N)\,\!</math> atp.), popř. rovnoměrnosti naplnění bloků (popisuje ji ''faktor naplnění stránek''). Splnění se dosahuje štěpením a sléváním bloku.
* SOS, které splňuje vyváženost, se nazývá ''dynamické'', jinak ''statické''.
====Fyzická média====
Soubory se fyzicky ukládají hlavně na magnetické pásky nebo HDD.
* ''Pásky'' umožňují jen sekvenční přístup, bloky jsou při vyhledávání čteny a kontrolovány sekvenčně (vhodné setřídění dát podle klíče). Pro kapacitu pásky je důležitá hustota, jsou nutné meziblokové mezery.
* ''HDD'' umožňuje přímý přístup k datům. Uvažují se ''hlavy'', ''válce (cylindry)'' a ''stopy''. Vždy jen jedna hlava může číst. Většinou se HDD dělí na sektory. Pro rychlost přístupu jsou důležité náledující proměnné:
** ''seek'' (přesun na jiný válec) - <math>s</math>
** ''rotate'' (doba 1 půlotáčky) - <math>r</math>
** ''block transfer time'' - propustnost sběrnice - <math>btt</math>
Nové disky mají různý počet sektorů na 1 stopu a tím pádem složitý výpočet cylindru a hlavy z čísla bloku, který dělá řídící elektronika. Udávaná adresa cylindr-hlava-sektor tak nemusí mít nic společného se skutečností.
:Př. nechť 1 stopa = 512 K. Načtení 1 MB pak trvá minimálně <math> s + r\,\!</math> pro nalezení prnvího sektoru <math> + 2\times 2r\,\!</math> za načtení stop. Při čtení z náhodně rozmístěných 4 K bloků ale vyjde <math> 256\times(s+r+btt)\,\!</math> - tj. až 100x pomalejší.
== Statické metody org. souboru ==
Časový odhad doby přístupu k záznamu <math> T_F\,\!</math> - složitější: <math> s+r+btt\,\!</math> obecně, <math> r+btt\,\!</math> pro další ve stejném cylindru, <math> T_{RW} = 2r\,\!</math> REWRITE - přepis (během 1 otáčky disků). Sekvenční čtení - <math> t' = R\cdot t/(R+W)\,\!</math>, kde <math> W\,\!</math> jsou meziblok. mezery, <math> t\,\!</math> je transfer rate. Další časy: <math> T_I\,\!</math>, <math> T_D\,\!</math> <math> T_U\,\!</math>, <math> T_Y\,\!</math> (reorg.), <math> T_X\,\!</math> (read entire file)
''Hromada''- jenom fyzicky za sebe naplácané záznamy. Složitost nalezení <math> O(N)\,\!</math>.
=== Sekvenční soubor ===
==== neuspořádaný ====
to samé co hromada, '' uspořádaný '' - záznamy řazeny podle klíče. aktualizované záznamy se umisťují do zvl. neusp. souboru, REORGANIZATION znova setřídí. Nalezení opět <math> O(N)\,\!</math> nebo <math> O(N/\lfloor b\rfloor)\,\!</math>. U médií s přímým přístupem ale <math> O(\log_2 N)\,\!</math>.
=== Index-sekvenční soubor ===
Prim. soubor - sekvenční soubor setříděný podle prim. klíče \& nad ním (i víceúrovňový) index: číslo bloku \& min. hodnota klíče v něm; pro vyšší úroveň to samé ale na blocích indexu nižší úrovně. Nejvyšší úroveň - obvykle 1 blok (''master''). Počet úrovní se dá spočítat : <math> x=\lceil\log_p N/\lfloor b\rfloor \rceil\,\!</math>, kde <math> p = \lfloor B/(V+P)\rfloor\,\!</math> a <math> V\,\!</math> je velikost klíče a <math> P\,\!</math> velikost pointeru na blok/záznam. Zařazení nového záznamu - problémy: přidávání do oblasti přetečení \& v ní řetězení záznamu za sebe (<math> \forall\,\!</math> má pointer na další záznam, nejenom blok, v obl. přetečení). Pro oddálení nutnosti vkládat do oblasti přetečení lze bloky plnit na míň než 100
=== Indexovaný soubor ===
Prim. soubor + indexy pro různé vyhledávací klíče. Indexují se přímo záznamy, ne jen bloky. Prim. soubor už nemusí být setříděný. Index může být podobný jako u indexsekvencniho souboru; ale lepší je, když pro záznamy se stejným klíčem je ve všech úrovních až na první (nejnižší) ten klíč jen 1x a pak odkazuje na seznam záznamu. Pro aktualizace se nepředpokládá oblast přetečení, ale změny v indexu. <math> T_F = (1+x)(s+r+btt)\,\!</math>. Dotazy na kombinovanou částečnou shodu - lze použít, ale náročné; Alternativa: ''kombinovaný index'' pro více atributů; to ale vyžaduje analýzu na co jsou dotazy nejčastější. ''clusterovany index'' - záznamy se společnou hodnotou 1 atributů jsou blízko sebe (jde jen pro 1 atribut).
==== bitové mapy ====
efektivní způsob indexace pro atributy s malou doménou (max. 100vky) - pro každou hodnotu této domény vyrobit vektor bitů délky <math> N\,\!</math>, kde 1 na i-té pozici indikuje, že i-ty záznam má právě tuto hodnotu atributů. Boolske dotazy potom jako bitové operace nad těmito vektory, and, oř, not - normální bitové operace ČPU. Vektory bitů lze navíc komprimovat - nejsou tak velké, vhodné pro databáze s hodně záznamy.
==== indexy v DIS (document information systém)====
tzv. ''invertované soubory'' pro fulltextové hledání - uložené pro každé slovo počet souboru kde se vyskytuje a pointer na soubor souřadnic = dvojic dokument, pozice. Dotazy na shodu pro více slov - množinové průniky (zač. od slova s nejmenším počtem výskytu v databázi). Získání invertovaného souboru: rozparsovani na slova, setřídění, odstranění duplicit, výpočet frekvencí slov. ''Zipfův zákon'' distribuce slov <math> f=k/r\,\!</math>, kde <math> k\,\!</math> je konstanta, <math> r\,\!</math> je pořadí četnosti, <math> f\,\!</math> je četnost. Taky využití komprese; zmenšení - vyhození nevýznamných slov.
=== Soubor s přímým přístupem ===
záznamy v primárním souboru (adresový prostor) rozptýleny pomocí hash-fce. Často používané <math> h=k \mod M'\,\!</math> kde <math> M'\,\!</math> je nejbližší prvočíslo menší než velikost adr. prostoru. Hash-fce není prostá, proto vznikají kolize, řešení: otevřené adresování (pozice + 1), rehashování, oblast přetečení. <math> h\,\!</math> prostá = perfekni hashování (řídký výskyt), jinak se perfektní hashování označuje taky stav, kdy je potřeba <math> O(1)\,\!</math> přístupu na disk pro nalezení záznamu. Implementace - buď hash = číslo stránky; nebo hash = číslo stránky i relativní pozice v ní. Kolize - snaha umístit záznam pokud možno do stejné stránky. Očekávaná délka řetězce kolizí: <math> \lambda = M/N\,\!</math> - pravděpodobnost že místo je plné, délka <math> E=(1-\lambda)+2(1-\lambda)\lambda+k(1-\lambda)\lambda^{k-1}...=(1-\lambda)\sum_{i=0}^{\infty} \lambda^{i}=(1-\lambda)\cdot 1/(1-\lambda)^2=1/(1-\lambda)\,\!</math>.
== Statické hashovaci metody ==
=== Cormackovo perfektní hashování ===
Soubor + adresář. Krom prim. hashovaci funkce <math> h\,\!</math> jsou potřeba další hash-fce <math> h_i(k,r)=(k\mod(2i + 100r +1))\mod r\,\!</math>, kde <math> r\,\!</math> je velikost oboru hodnot (počet kolizí), <math> i\,\!</math> je nějaký vhodnyparametr - číslo hash fce (hledá se postupným zkoušením dokud není výsledek bez kolizí). V adresáři: <math> \forall\,\!</math> záznam uložený odkaz do prim. souboru, <math> r\,\!</math> a <math> i\,\!</math>. V prim. souboru klíč a data. Při hledání zahashuju klíč <math> h\,\!</math>, dostanu se do adresáře, pokud je tam <math> r=0\,\!</math>, nenašel jsem. Pokud <math> r\geq 1\,\!</math>, spočítám podle uloženého <math> i\,\!</math> hash-fci <math> h_i\,\!</math>, vezmu odkaz do prim. souboru, přičtu výsledek <math> h_i\,\!</math> a v prim. souboru zkontroluju jestli jsem našel co jsem hledal. Přidávání - spočítám <math> h\,\!</math>, pokud tam nic není, najdu volné místo v prim. souboru délky 1 a vložím, pokud tam už něco je, najdu volné místo délky <math> r+1\,\!</math>, zvětším <math> r\,\!</math> a najdu <math> i\,\!</math>, aby kolizní od sebe rozházela a přeházím je na nové místo. <math> r\,\!</math> nemusím zvětšovat o 1, ale rychleji, takže najdu požadované <math> i\,\!</math> lépe (pokud mám blbý <math> h_i\,\!</math>, někdy <math> r\,\!</math> prostě musím zvětšit). Dá se použít i pro dynamický paměťový prostor.
=== Perf. hashování Larson-Kalja ===
Menší pomocná tabulka: jen ''separátor'' (speč. číslo) pro každou stránku. Mam <math> M\,\!</math> hash-fci, které vytvářejí pro záznam posloupnost stránek do kterých ho zkouším vkládat, navíc 2. sadu jim jednozn. odpovídajících fci, které počítají ''signaturu''. <math> \forall\,\!</math> stránka má separátor, pokud je separátor <math> >\,\!</math> signatura záznamů, OK, jinak tam záznam nemůžu vložit. Po přeplnění vyhodím záznamy s největší signaturou a zmenším separátor. Prvek se nemusí podařit vložit (když mi dojdou obě sady funkcí). Pokud vkládám do plné stránky, nemůžu vložit i když mám menší signaturu než je separátor - separátor pak musím zmenšit a ze stránky vyhodit i něco dalšího - kaskadovani insertu. Vhodné pro málo vkládání a hodně čtení - jen 1 přístup na disk (malý adresář se do paměti vejde).
=== Dotazy na částečnou shodu ===
Predp. že záznam má <math> n\,\!</math> atributů, vezmu <math> n\,\!</math> hash-fci, každá generuje <math> d_i\,\!</math>-bitový výsledek (signaturu atributů). Pro adresový prostor <math> M=2^d\,\!</math> stránek <math> \sum d_i = d\,\!</math> (-zřetězení: signatura záznamu). Částečná shoda - dotaz kde bity některých atributů jsou nahrazeny "?" - "<math> s\,\!</math>-bitová signatura" pro <math> s\,\!</math> bitů zadaných - takový dotaz je <math> 2^{d-s}\times\,\!</math> dražší. Průměrná cena dotazů je pro pravděpodobnost <math> P_i\,\!</math> dotazů na atribut <math> i\,\!</math> :
:<math>\sum_{q\in\mathcal{P}(\{1,..n\})}(P_q\cdot\Pi_{i\not\in q}2^{d_i})\,\!</math>
. Ideální rozvržení <math> d_i\,\!</math>: <math> d_i = (d - \sum_{j=1}^{n} \log_2 P_j)/n + \log_2 P_i\,\!</math>. Extrémy upravit na <math> 0\,\!</math>, <math> d\,\!</math>; Pokuď je <math> 2^{d_i}\,\!</math> větší než doména <math> A_i\,\!</math>, upravit na <math> A_i = \lceil\log_2|A_i|\rceil\,\!</math> a přepočítat ostatní.
Urychlení dotazů - ''deskriptory stránek''- deskriptor záznamů: <math> w = w_1 + .. + w_n\,\!</math> -bitový řetězec: pro každý atribut <math> A_1,.. A_n\,\!</math> ex. fce <math> T_i\,\!</math>, která každé jeho hodnotě přiřadí <math> w_i\,\!</math>-bitový řetězec s právě 1 jedničkou (může být zadáno jinak, ex. vzorce pro ideální <math> w_i\,\!</math> i počet jedniček k nim). Deskriptor stránek je "||" deskriptorů všech záznamů ve stránce. Při hledání vyrobím deskriptor dotazů, kde jsou "?", tam dám samé nuly, pokud má dotaz někde v deskriptoru "<math> 1\,\!</math>" a stránka "<math> 0\,\!</math>", nemusím tam hledat. Lze udělat i 2urovnove - deskriptory segmentu.
Další možnost - ''Grayovy kódy'' - snaží se řešit nesouvislost oblasti stránek se záznamy vyhovujícími dotazů (pr. <math> 10???1010\,\!</math>). Jde o jiný způsob kódování binárních čísel - 2 po sobě jdoucí čísla se liší vždy jen v 1 bitů. Max. zisk - o 50\binární. Konverze na Graye: <math> G[n]=B[n]\,\!</math>, <math> G[í]=B[i+1] \mathrm{xor} B[í]\,\!</math>.
== Dynamické hashování ==
=== Rozšiřitelné hashování - Fagin ===
Pomocná struktura - adresář s pointery na stránky (některé mohou být v adresáři víckrát), hash. fce s rovnoměrným rozdělením. Vždy použiju jen prvních <math> d\,\!</math> bitů hash-fce, minimum kolik potřebuju. Podle nich určím záznam v adresáři, z něj najdu stránku. Pro stránku se může používat míň bitů, proto na ní může ukazovat víc záznamů v adresáři. Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-fce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář (a zdvojnásobit jeho velikost), s ostatními stránkami nic nedělám. Při vypouštění záznamu lze stránky slévat, pokud si pamatuju jejich využití (můžu slévat jen stránky které se liší jen v posledním bitu).
=== Lineární hashování - Litwin ===
Nemá adresář, má oblast přetečení. Data vkládána do prim. stránek, po každých <math> L\,\!</math> vložení se vynucené stepi určená stránka (v pořadí podle čísel stránek <math> 0, 1, 00, 01, 10, 11, 000\,\!</math>). Přetečení přístupné pointry z prim. stránek. Podle hashe (jeho konec musí odpovídá číslu stránky) se rozdělují při štěpení prvky. Hledání: když mám aktuálně <math> n\,\!</math> stránek, vezmu posledních <math> \lfloor\log_2 n\rfloor + 1\,\!</math> bitů, pokud je to <math> >n\,\!</math>, zanedbám horní bit, mám číslo stránky. Když tam není a stránka je přetečená, podívám se ještě do obl. přetečení. Při štěpení je nutné vrátit do rozštěpených stránek i záznamy z obl. přetečení. Problém: více zaplněné stránky na konci, tedy ještě nerozštěpené. Řešení: buď nerovnoměrné rozdělení hash-fce, nebo skupinové štěpení stránek.
=== Skupinové štěpení stránek ===
Rozšíření Litwina pro lepší využití stránek; stránky vždy v <math> s\,\!</math> skupinách po <math> g\,\!</math>, mám inicializační hash-fci <math> hash\,\!</math> do <math> 0..(g\cdot s_0)-1\,\!</math>. <math> s_0\,\!</math> se časem zvětšuje, <math> g\,\!</math> je konstanta. Štěpím také po <math> L\,\!</math> vložení, vždy <math> g\,\!</math> stránek do <math> g+1\,\!</math>, na to mám nezávislé hash-fce <math> h_0,...h_1\,\!</math> do <math> 0..g\,\!</math>. Až dostanu <math> s\,\!</math> skupin po <math> g+1\,\!</math> stránkách, přeorganizuju stránky zpátky do skupin po <math> g\,\!</math> (můžu přidat nějaké prázdné aby to vycházelo). Při hledání - počítají se všechna prehashování úplně od začátku - docela HW náročné, ale proti rychlosti disků se vyplatí.
=== Spirálová paměť ===
Podobně lin. hashování, ale pro exponenciální rozdělení klíčů; místo rozdělení 1 stránky na starou a novou tu starou zahodí a přidá 2 nové. Klíče nejprve rovnoměrně rozděleny hash-fci <math> G(c,k): <c, c+1>\,\!</math> (<math> c\in\mathbb{R}^+_0\,\!</math>) , pak přepočtený do <math> <b^c, b^{c+1}>\,\!</math> a zaokrouhleny na konkrétní čísla stránek (<math> \lfloor b^G \rfloor\,\!</math>). Při změně <math> c\,\!</math> se mění velikost prostoru. Při expanzi se nově <math> c\,\!</math> volí tak, aby zničilo stránku která se štěpí (nejnižší číslo) - <math> c_{n+1} := log_b( f + 1 )\,\!</math> (kde <math> f\,\!</math> je číslo 1. stránky). Aby se mi neposouvaly všechny stránky pořád dál od 0, první zahozené stránce dám nové číslo a znova ji použiju -- přepočítávání log. stránek na fyzické se pak dělá rekurzivně ( if <math> \lfloor\,\!</math>log. stránka<math> / b\rfloor < \lfloor( 1+\,\!</math>log. stránka<math> )/b\rfloor\,\!</math> vezmi rekurzivně fyz. stránka <math> :=\,\!</math> fyz. stránka(<math> \lfloor\,\!</math>log.stránka<math> / b\rfloor\,\!</math>), else vrat fyz. stránka <math> =\lfloor\,\!</math>log. stránka<math> / b\rfloor\,\!</math>. )
=== Hash. fce zachovávající uspořádání ===
Kvůli urychlení intervalových dotazů - hashovaci metody, zachovávající uspořádání klíčů. '' lín. hashování pro intervalové dotazy '' Vychází z Litwina, využívá nejvyznamejsi bity k určení stránky.
==== částečně lineární hashování zachovávající uspořádání ====
vychází ze znalosti rozdělení klíčů, dělí doménu klíčů na nestejně dlouhé intervaly aby vyvažovalo nerovnoměrnost rozdělení. Nelze ale pořád reorganizovat, takže se upravují jenom přilehlé intervaly při vkládání a odebírání. Nehodí se pro dynamicky rostoucí doménu klíčů. Může být provedeno víceúrovňové.
===Externí hashování===
{{TODO|Tohle je z Datových struktur, není to totéž co něco z OZD?}}
Jiný cíl -- minimalizace počtu operací s externí pamětí, ve které jsou uložená všechna data. Vezmeme prostou funkci <math> U\to \{0,1\}^k\,\!</math>. Pro mn. <math> S\,\!</math>. Slovu <math> \alpha\in\{0,1\}^{*}\,\!</math> kratšímu než <math> k\,\!</math> přiřadíme <math> h_S^{-1}(\alpha)=\{s\in S;\alpha \mbox{ je prefix }h(S)\}\,\!</math>. Potom <math> \alpha\,\!</math> je ''kritické slovo'', když <math> h_S^{-1}(\alpha)\,\!</math> se vejde do 1 stránky ext. paměti, ale všechny prefixy <math> \alpha\,\!</math> toto neumí. Pro každé <math> s\in S\,\!</math> existuje právě 1 krit. slovo; def. <math> d(S)=\max\{\mbox{délka}(\alpha);\alpha\mbox{ krit. slovo}\}\,\!</math>. Pak na stránce příslušející <math> \alpha\,\!</math> uložíme <math> h_S^{-1}(\alpha)\,\!</math>. Přiřazení stránky kritickému slovu <math> \alpha\,\!</math> řeší funkce -- adresář. Adresář může být lexikograficky podle prefixů uspořádaná tabulka adres stránek. Ukládáme ho pak taky na jedné stránce ext. paměti. Potom MEMBER jsou max. 3 operace a INSERT/DELETE max. 6 operací s ext. pamětí. Očekávaný počet použitých stránek je <math> \frac{n}{b\ln 2}\,\!</math> a velikost adresáře <math> \frac{e}{b\ln 2}n^{1+\frac{1}{b}}\,\!</math> -- to je víc než lineární růst, tj. nelze používat donekonečna (bez důkazů).
{{Statnice I3}}
