{{collapse|okruhy 09/10 (pro srovnání)|''Metody indexace relací, datové struktury na externí pameti: hašování, B-stromy. Vícerozmerné dotazy pomocí hašovacích metod, vícerozmerných mrížek, vícerozmerných stromu. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: indexy, signatury, metody implementace signatur (vrstvené kódování), usporádání odpovedí. Komprese dat: predikce a modelování, reprezentace celých císel, obecné metody komprese, komprese bitových map, rídkých matic, komprese textu. Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy. Modely a vlastnosti transakcí: uzamykací protokoly, casová razítka. Izolace transakcí, alokace prostredku. Distribuované transakce. Zotavení z chyb, žurnály.''}}
okruhy 14/15: ''Architektury databázových systému. Modely a vlastnosti transakcí: uzamykací protokoly, casová razítka. Izolace transakcí, alokace prostredku. Distribuované transakce. Zotavení z chyb, žurnály. Indexace relacních dat: B-stromy, hašování, GRACE algoritmus. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace. Komprese dat: modely textu, kódování, Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic, Burrows-Wheelerova transformace.''
'''Vsechnu latku pokryva text "Zaklady implementace souboru a databazi" od Pokorneho a Zemlicky a slajdy "Dokumentografickych informacnich systemu" od Kopeckeho'''
== Architektury databázových systému. ==
{{TODO|co sem patří?}}
==Transakce==
{{:Implementace_databázových_systémů/Transakce}}
== Indexace relacních dat: B-stromy, hašování, GRACE algoritmus (🎓🎓🎓) ==
{{Zkazky|
* '''Indexace relacnich dat (Hoksza)''' - B-stromy a hasovani - -B B+ B* (proc se pouzivaji - velikost vnitrniho uzlu), hashování 7 druhu, viz Hoksza slajdy
* '''DS - B-stromy a ich varianty (Kopecky)''' - Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.) Prijemne aj ked pomerne podrobne sa snazil preverit znalosti.
* '''DS - B-stromy a jejich varianty (?)''' - Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.)
}}
=== Metody indexace relací ===
* relacie mozu byt chapane ako subory, zaznamy suboru ako n-tice relacie, samozrejme su tam rozdiely, napr.:
** schemy vsetkych relacii sa natiahnu naraz s celou DB, subory musime otvarat/zatvarat jednotlivo
*indexsekvenční soubor (indexováno jen podle primárního klíče)
*invertovaný soubor - lze indexovat podle čehokoliv - indexují se přímo záznamy
*bitová mapa
**pro atributy malých domén (pohlaví, typ karoserie vozu...) se pro každou doménu vytvoří bitový vektor a jednička tam kde hodnota pro daný řádek platí, tedy vždy jen jedna jednička na řádku => hodně nul, lze dobře komprimovat
**vyhledávání je rychlé používají se operace AND, OR atd.
**insertem se všechny vektroy prodlouží, přidáním další možnosti (rozšíření domény) se přidá další bitový vektor
**lze využívat i pro GROUP BY, COUNT atd.
=== Hashování ===
* perfektni hasovani Cormacka
* perfektni hasovani Larsona a Kalji
* Deskriptory stranek, Grayovy kody (viz Vícerozměrné dotazy implementované pomocí hashovacích metod)
* hasovani Fagina
* dynamicke hashovani Litwina
* skupinove stepeni stranek
=== B-stromy ===
''viz [[Státnice_-_Stromové_vyhledávací_struktury#B-Stromy|společná část "B-Stromy a jejich varianty"]]''
* redundantni, neredundantni B-strom
* redundantni, neredundantni B*-strom
* redundantni B+-stromy
* prefixove stromy
* (a, b)-stromy
* stromy s promenlivou delkou zaznamu
* vicerozmerne B-stromy
=== Datové struktury na externí paměti ===
*hromada - nehomogenni záznamy (ruzne delky) jsou ukládány za sebou (bez dalších podmínek) - vyhledání čehokoliv = projití celé hromady (v nejhorším případě)
*sekvenční soubor - podobný jako hromada, jen záznamy jsou pevné délky (homogenni)
** uspořádaný sekvenční soubor - záznamy uspořádány podle klíče, nově přidávané se ukládají do "souboru aktualizací" a občas je provedena reorganizace, kdy je "soubor aktualizací" vyprázdněn a data z něj zatříděna do uspořádaného sekvenčního souboru. Nalézt záznam lze pak půlením intervalů v case O(log_2(n)).
** indexsekvenční soubor - obdobně jako předchozí jsou záznamy setříděny podle klíče, navíc existují indexy do jednotlivých bloků (stránek). Indexy jsou tvořeny klíči některých záznamů. Celý index je pak jakýsi B-strom. Při přidávání není index reorganizován, ale je použita oblast přetečení, kam je nový záznam vložen. K záznamu, za který měl být nový záznam vložen se pak uloží číslo bloku i číslo záznamu, kde nový záznam leží. V oblasti přetečení jsou tak vytvářeny lineární seznamy.
**invertovaný (indexovaný) soubor - indexují se přímo záznamy, ne bloky (jak tomu je v indexsekvenčním souboru), data nejsou v souboru nijak uspořádána, jednotlivé bloky nemusí být na disku za sebou. Indexů může být více různých. Při přidávání není použita další struktura, přímo se upravují indexy. Používá se v DIS (invertovany soubor).
*ukládání pomocí hashování
*b-stromy
Jiny (urcite lepsi :) popis:
:[http://siret.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_11.pdf Fyzická implementace relačních databází] (Databázové systémy)
:[http://siret.ms.mff.cuni.cz/sites/default/files/doc/david.hoksza/lectures/ndbi007/2014W/lecture2.pdf File Organizations] (OZD 1)
Definice: '''Klíč''' schématu relace R je nejmensi mnozina atributů ze schématu R, na níz celá R funkčně závisí. Jakmile tedy máme hodnoty pro klíčové atributy, máme jednoznačné určen libovolný řádek tabulky.
;Organizace databázových souborů (podle OZD 1)
:'''Halda''' (hromada / heap file)
::zaznamy maji ruznou delku
::zaznamy jsou vkladany na konec souboru
:'''Sekvenční soubor''' (sequential file)
::''nesetrideny'' - halda s pevnou delkou zaznamu
::''setrideny'' - zaznamy setridene podle klice (narocny INSERT a DELETE)
:'''Index-sekvenční soubor''' (indexed sequential file)
::index nad jednim klicem je vytvoren
::je to vlastne primarni soubor se setridenymi daty podle klice + indexovy soubor, ktery muze mit vice urovni indexu
:'''Indexový soubor''' (index file)
::indexy nad vice klici jsou vytvoreny
::muze obsahovat primarni index (coz je index nad klicem, podle ktereho je setrideny primarni soubor - asi klastrovany index) a obsahuje sekundarni indexy (asi neklastrovane indexy)
:'''Hashovaný / hešovaný soubor''' (hashed file)
::pro jeden atribut (asi i klic) existuje hesovaci funkce
=== Vícerozměrné dotazy implementované pomocí hashovacích metod ===
* viacrozmerne dotazy - obsahuju viac atributov (n>1)
** na uplnu zhodu - hodnoty vsetkych n atributov su pevne dane (n=2: MENO='Jiri' AND MESTO='Praha')
** na ciastocnu zhodu - hodnoty niektorych atributov (<n) su pevne dane
** na uplnu intervalovu zhodu - pre vsetkych n atributov su dane intervaly hodnot (napr. VEK>22)
** na ciastocnu intervalovu zhodu - intervaly hodnot su dane len pre niektore atributy
* implementacia
**'''signatury''' - d bitove binarne retazce
*** signatura zaznamu (dlzky d) je zretazenim signatur jednotlivych atributov, pre kazdy atribut A_i je samostatna hasovacia funkcia h_i, ktora vytvori signaturu dlzky d_i. Plati, ze d_0+d_1+...+d_n=d; n-pocet atributov. Signatura dotazu sa tvori podobne, nezadane atributy su reprezentovane retazcom nul.
*** signatura dotazu Q sa porovnava so signaturami zaznamov S - na pozicii, kde je v Q jednicka, musi byt jednicka aj v S, inak zaznam do odpovede nepatri
**'''deskriptory stranok'''
*** vrstvia sa deskriptory zaznamov v danej stranke pomocou logickeho OR. Deskriptor zaznamu je opat zretazenie deskriptorov atributov A_i, pre kazdy atribut je dana hasovacia funkcia h_i, ktora priradi kazdej hodnote atributu binarny retazec obsahujuci prave 1 jednicku.
*** subor deskriptorov stranok je pripojeny k primarnemu suboru, ak je velky, moze byt dvojurovnovy (prim. subor sa rozdeli do segmentov, kazdy ma svoj subor deskriptorov, tie tvoria 1. uroven; 2. uroven ma deskriptory ukazujuce do 1.)
*** rychlejsie ako signatury, lebo sa musi porovnat menej deskriptorov (ale na ukor pamate); lepsie ako indexovany subor, lebo nerastie cas vyhodnocovania s rastucim poctom atributov v dotaze, pamatove naroky su podobne
**'''grayove kody''' - binarne retazce, hodnoty nasledujuce za sebou sa lisia vzdy len v jednom bite
*** adresa stranky dana signaturou je interpretovana ako grayov kod
*** zaznamy vyhovujuce signature dotazu tvoria zhluky, kde zaznamy su fyzicky za sebou v jednej stranke (alebo viacerych po sebe iducich strankach), nikdy nie je viac pristupov na disku ako u binarneho kodovania
*** dobre pre dotazy na ciastocnu zhodu pri malom pocte zadanych atributov a pre dotazy na intervalovu zhodu
=== Vícerozměrná mřížka ===
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm Slajdy Pokorný]
=== Vícerozměrné stromy ===
==== Vícerozměrné B-stromy ====
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm slajdy Pokorný]
*lze pomocí nich indexovat soubor podle několika atributů současně.
*celý strom má tolik hladin, kolik je atributů (hlavní strom není B-Strom!)
*pro každý atribut jsou vytvořeny stromy - pro první jeden, pro druhý tolik, kolik má první atribut různých hodnot atd. U každé hodnoty atributu (uzlu stromu) existuje index na strom s dalším atributem.
*jednotlivé vrstvy celého stromu jsou indexovány polem Level (vrstva = jeden atribut) - slouží pro přeskočení prvních i atributů, které nebyly v dotazu zadány
*stromy v jedné vrstvě jsou propojeny do spojáku pomocí NEXT v kořeni, poddoména jednoho stromu je určena pomocí LEFT a RIGHT (uloženy v kořeni), které ukazují do další hladiny na první a poslední strom, který se týká daného stromu. Tedy každý prvek z vrstvy i-1 má ve vrstvě i určeny všechny prvky ve vrstvě i+1, LEFT a RIGHT dává vše.
*podobná struktura by pravděpodobně šla definovat i pro obecný, nebo jakýkoliv jiný vyhledávací strom.
== Přístupové metody k prostorovým objektům: R-stromy a jejich varianty (🎓🎓🎓) ==
{{Zkazky|
* '''R-stromy''' - ''Napsal jsem, k čemu jsou dobré, definici a štěpení uzlů dle Guttmana a Greeneové. Dále jsem se zmínil o některých variantách R stromů. Zkoušející se pak jen zeptali na pár otázek.''
* '''R-Stromy (Pokorný)''' - ''Zadefinovať, k čomu slúžia, nákres, štiepenie Gutmann, Green. Rozhovor pokračoval k MOO, MOK - aproximáciám, aké sú výhody jednotlivých prístupov - náročnosť uloženia vs. schopnosť aproximácie. Žiadne detaily, stačilo rozumieť. R+ stromy som len popísal kritériá výberu osi a distribúcie, vravel som, že to kludne na papier dopíšem, ale Pokorný to zjavne nevyžadoval.''
* '''R-stromy (Skopal)''' - tuhle otazku jsem tak nejak cekal :-) Bohuzel pan Skopal zkousi pro me dost neprijemnym stylem .. po prvni vete vas dokaze zaskocit nejakou treba i jednoduchou a ne spatne minenou otazkou, na kterou rychle nevite, co odpovedet a pak se do toho tak zamotate, ze zacnete placat nesmysly..on se vas snazi k necemu dokopat, ale kdyz nevite kam presne miri, da se to jen tezko odhadnout..navic z jeho vyrazu nejde vycist, jestli je to jeste v pohode nebo jste na pokraji vyhozeni :-) Nastesti jsem u pana Skopala delal predtim jednu zkousku, tak uz jsem vedel, ze takhle zkousi, ale zas tak zly to neni, jak to v prubehu zkousky vypada...navic me potesilo, ze me nerozebral hned na zacatek uplne a vcas toho nechal..
}}
Prostorové objekty lze jen velmi obtížně uchovávat v relačních databázích (ztrácí se při tom část informací, které v sobě uchovávají – resp. je nutné je složitě dopočítávat). Typické dotazy na prostorová data jsou:
* vyhledej bod v prostoru
* vyhledej oblast v prostoru
* vyhledej okolí oblasti (bodu)
Bylo hledáno nové řešení, které by takovéto dotazy dokázalo dostatečně rychle vyřešit. Byla tak navržena nová schémata organizace souboru.
Uplatnění: GIS, CAD, ale i další (zdravotnictví, 3D grafika ve hrách, ....)
* radix (r^d) stromy
**uvažujme r=2, d=2 rozděluje plochu na 4 čtverce a každý čtverec je reprezentován uzlem stromu, a rekurzivně je dále členěn. Objekt může být uložen v mnoha listech. Strom může být nevyvážený.
** vhodné pouze pokud se celé vejdou do vnitřní paměti
**organizace prostoru – číslování do šířky, adresování cestou, z-uspořádání (peanova křivka), naivní uspořádání, spirálové uspořádání, hilbertova křivka (všechny po sobě jdoucí buňky jsou sousední v prostoru) – volbu organizace je vhodné přizpůsobit datům, pro čtvercové oblasti je vhodné spirálové uspořádání, pro obdélníky je vhodné naivní uspořádání ve směru delší strany
*K-D-stromy
**binární strom – ve vnitřím uzlu je osa podle níž se prostor půlí, v listech jsou B-kostky
*R-stromy
**založeny na myšlence MOO (minimálních ohraničujících obdélníků, resp. kostek)
**obdoba B-stromů pro prostorové objekty (každý uzel kromě kořene má m1 až m synů, kořen má aspoň 2 syny, nebo je listem, všechny cesty v R-stromu jsou stejně dlouhé)
**jednotlivé oblasti, které jsou reprezentovány v uzlech se mohou překrývat
**jak štěpit uzel při jeho přeplnění?
***všechny možnosti rozdělení a vybrání té s nejmenším použitým prostorem
***Guttman – vybrat dva prvky s největším mrtvým prostorem a postupně k nim přiřazovat zbylé prvky tak, aby přírustek plochy byl co nejmenší (je potřeba, aby každá skupina měla asoň m1 prvků, takže se případně zbylé prvky doplní do menší skupiny). Pokud má více prvků stejnou hodnotu přírustku je možné použít heuristiku (do skupiny s menším počtem prvků, nebo do skupiny s celkovým menším objemem)
***Green – při štěpení vybere jednu z os (pro každou osu spočti maximální normalizovanou vzdálenost dvou prvků – pro každou osu a každý prvek spočítám jejich vzdálenost a vydělím velikostí hrany nadkostky v dané ose, maximální hodnota osy je maxium z těchto hodnot, vybrána bude taková osa, která má maximální normalizovanou vzdálenost největší, pak se půlka (ev. +1) hodí do jednoho uzlu a zbytek do druhého uzlu.
*ne vždy je nalezena vhodná osa – může vést ke špatným výsledkům
*R+-stromy
**přiřazuje prostorové objekty do všech listů, do kterých zasahují, díky tomu se nelistové uzly nepřekrývají, u uzlů není zaručena minimální zaplněnost
**větší (objekt může být ve více uzlech) a náročnější na údržbu než R-stromy
*R*-stromy
**více optimalizačních ktitérií oproti R-stromům – uvažujjí také okraj a překrytí
**při INSERTu se v předposlední úrovni vybírá takový list, kde když bude, tak celá ta množina bude mít nejmenší překrytí s ostatními množinami (dalšími listy), ve vyšších úrovních se vybírá uzel, který způsobí nejmenší zvětšení prostoru (jako u R-stromů)
**štěpení
***pro každou osu se prvky setřídí podle souřadnice x1 a x2
***pro každé setřídění jsou vytvořeny všechny kombinace rozdělení prvků tak, aby v každé skupině bylo aspoň m prvků (tzn. m prvků bude v první a druhé skupině vždy stejných, zbylé se rozdělí dle uspořádání)
***pro každou takovou distribuci se spočítají
****h-objem (součet objemů jednotlivých skupin)
**** h-okraj (součet okrajů – ve 2D obvod, ve 3D ohraničující –plocha – skupin)
****h-překrytí (překrytí první a druhé skupiny)
*** pro každou osu se spočítá S (suma h-okrajů všech distribucí v dané ose) a vybere se osa s nejmenším S
*** v této ose se vybere distribuce, která má nejmenší h-překrytí, v případě rovnosti rozhoduje menší h-objem
*Buddy-stromy
**nepokrývají (nutně) celý prostor
**vhodné pro ukládání bodů (pokud chci složitější struktury je potřeba zdvojnásobit dimenzi a ukládat zvlášť dolní a zvlášť horní mez)
**při slévání se slévají dvě stránky, ale výsledné dělení musí být opět B-dělením (lze k němu dojít pomocí půlení prostoru) – slévat lze kostky, které jsou v poloze „buddy“ – tj. ohraničující kostka sjednocení těchto kostek má s ohraničujícími kostkami ostatních kostek v uzlu prázdný průnik
*prostorové spojení
**motivace: najdi všechny lesy v daném městě – uvažujme jakoby databázi s tabulkou lesů (id_lesu, název_lesu, území) a tabulkou města (id_města, název, území), snahou je vytvořit predikát, který bude fungovat jako spojení v relačních DB – nejčastěji by měl vracet dvojice, které mají neprázdný průnik (ale lze uvažovat i jiné predikáty)
**výsledkem spojení může být buď konkrétní průnik, nebo pouze ukazatele na překrývající se objekty (tzv. Id-spojení)
**prostorové spojení pomocí hnízděných cyklů
***obdoba spojení pomocí setřízení a porovnávání jako u relačních DB není možná prostorové objekty nelze jednoznačně uspořádat do 1 dimenze, jedinou variantou jsou tak hnízděné cykly (porovnají se všechny prvky z tabulky A se všemi z tabulky B) – to je náročné a tak se pokusíme optimalizovat:
****spočítá se spojení MOO těch objektů (kandidáti na správné hity)
****pomocí kvalitnějších aproximací se provede filtrace na jisté hity, jisté chybné hity a nerozhodnuté dvojice
****nerozhodnuté dvojice se rozhodnou pomocí přesné geometrie
***prostorové spojení pomocí z-uspořádání
****vytvoří se mřížka, políčka se očíslují pomocí z-uspořádání (Peanova křivka), objekt je potom aproximován množinou z-hodnot, při porovnávání objektů lze hledat z-hodnotu jednoho objektu mezi z-hodnotami druhého objetku
***prostorové spojení pomocí R-stromů
****nechť jsou prostorové relace uloženy v R-stromech, postupným procházením stromů je možné eliminovat řadu uzlů, protože mají prázdný průnik
***zametací algoritmus
****dvě prostorové relace (uvažujme 2D, obdélník, ev. MOO), každý obdélník je definován svým levým dolním a pravým horním rohem, provedu projekci do jedné osy, najdu obdélník s nejmenší x1 (z obou relací), nechť je to obdélník S1, nyní hledám všechny obdélníky z druhé relace (R), které mají ri.x1 menší než s1.x2. Pokračuji výběrem dalšího obdélníku, ale S1 již neuvažuji (nebude mít průnik s žádným dalším obdélníkem)
{{zdroje|
:''viz [[wen:R-Tree]]''
}}
{{TODO|R-stromy komplet}}
== [[Databázové_modely_a_jazyky#Datab.C3.A1ze_text.C5.AF:_modely_.28boolsk.C3.BD.2C_vektorov.C3.BD.29_.28.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.29 |Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace (🎓)]] ==
{{Zkazky|
* '''IDS - Vektorovy a boolovsky model (Kopecky)''' - princip, tvar dotazu a odpovede, implementacia
}}
== Komprese dat ==
{{TODO|zkonfrontovat obsah s nejakym zkousejicim}}
{{:Implementace_databázových_systémů/Komprese}}
{{Statnice_I2}}
