{{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ří?}}
Asi malo:
http://statnice.matfyz.info/generated/IOI-html/node78.html
http://www.databaze.chytrak.cz/architektura.htm
==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.)
}}
{{TODO| mega zjednodusit - sloucit z datovkama a pridat jenom vychytavky z DB (proc se pouzivaji atd)}}
=== GRACE ===
v DJ1-4-vyhodnoceni.pdf
=== 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..
}}
{| class="wikitable" style="float:right; clear:right;"
! scope="row" colspan="2"| štěpení uzlu R-Stromu m=3, M=8
|-
| scope="row" colspan="2"| [[Soubor:Rtreetable.png]]
|- style="vertical-align:top;"
|
dle '''Guttmana''':
'''Pick Seeds''' - největší nevyužitá plocha B,H=44
;'''∀Pick Next'''
[[File:Guttman.png]]
: ⇒ BDIE, FGHCA
|
dle '''Greene''':
;Pick Axis
*PickSeeds(z Guttmana): největší nevyužitá plocha B,H=44
*spočteme normované vnitřní vzdálenosti:
**y: 5/8
**x: 3/8
*vybereme tu s větší normovanou vzdáleností, tedy y
'''Half''' - setřídíme objekty podle y souřadnice a rozdělíme
[[File:Green.png]]
: ⇒ ABCDE, FGIH
|}
{{zdroje|
* zapsáno podle: http://siret.ms.mff.cuni.cz/members/hoksza/lectures/ndbi003}}
Typické dotazy na prostorová data jsou:
*vyhledej bod v prostoru
*vyhledej oblast v prostoru
*vyhledej okolí oblasti (bodu)
===R-stromy===
💡 obdoba B-stromů pro prostorové objekty (ale hledání může jít současně více cestami)
*∀uzel '''E''' má '''m až M synů''' (až na kořen - má aspoň 2 syny) a platí: '''m ≤ M/2'''
** E.p - '''identifikátor prostorového objektu''' (listy) nebo '''pointer na syna'''
** E.I - '''MBR (minimum bounding rectangle)''' - minimální ohraničující obdélník - MOO (💡 n-dimensionální)
**: 💡 jednotlivé oblasti se mohou překrývat
*všechny cesty v R-stromu jsou stejně dlouhé (listy na stejné úrovni) ≤ logₘ ''n''
'''INSERT''' - štěpení uzlu při jeho ''M''+1 přeplnění (hledám co nejmenší využití prostoru)
;'''Guttman'''
* '''PickSeeds''' - 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)
'''Greenová''' (snažíme se odstranit překrytí listů - při štěpení vyberem jednu z os)
* '''PickSeeds''' - z Guttmana
* '''ChooseAxis''' - ∀ osu a MBR(2 prvků) spočti maximální normalizovanou vzdálenost (💡 vnitřní vzdálenost vydělím hranou MBR 2 prvků v dané ose)
*: → vyberu osu s největší normalizovanou vzdáleností
*'''Distribute''' - větší půlka ⌈(M+1)/2⌉ se 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í (je tedy duplikován)
* vnitřní (nelistové) MOO uzly se 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žují také okraj a překrytí
*rozdíl od R-Stromů: algoritmem na rozdělení přetečené stránky, bere v úvahu více trideni podle os, při přetečení provádí reinsertování, taky algoritmem na hledání listu pro insert (overlap místo nejmenšího rozšíření)
*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
{{collapse|1=další stromy|2=
další:
;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
;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]]''
}}
== [[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}}
