Implementace databázových systémů: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(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. (🎓))
Řádka 1: Řádka 1:
 +
{{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.''
 
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.''
  

Verze z 3. 5. 2015, 16:10

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

Obsah

Architektury databázových systému.

Tato část je neúplná a potřebuje rozšířit. co sem patří?

Transakce

Modely a vlastnosti transakcí

Transakce notace podle Graye
Transakce notace podle Graye
Flat model(př.3 stavy): transakce T je aktivní (a bude ABORTovat), T je ABORTovaná, T je COMMITovaná
Flat model(př.3 stavy): transakce T je aktivní (a bude ABORTovat), T je ABORTovaná, T je COMMITovaná

Transakce je posloupnost akci (r, w, vypocet,..) nad persistentními daty se kterou se zachazi jako s celkem.

Zacatek transakce se oznacuje obvykle BEGIN, konec COMMIT/ABORT,ROLLBACK. V pripade neuspesneho zakonceni transakce se system vrati do stavu pred zapocetim te transakce.

Databázové transakce musí splňovat tzv. vlastnosti ACID (viz wen:ACID)
Atomicity - Transakce proběhne celá, nebo vůbec.
Consistency - Při provádění transakcí se DB převádí z jednoho konzistentního stavu do jiného.
Isolation - Transakce o sobe navzájem nevědí, jako by běžela jen jedna.
Durability - Změny commitnuté transakce jsou trvalé.

Flat Model (FM)

Omezení transakčního modelu flat transactions, která mohou bránit jeho praktickému využití v některých transakčních systémech:

  • Mají příliš velký rozsah. Abortu po stotisící operaci se nedá nijak zabránit. To se dá přičíst tomu, že nemají žádnou vnitřní strukturu.
  • Žádný dílčí neúspěch není tolerován. Pokud je špatně jediné číslo konta u deseti tisíc zaměstnanců nějakého podniku, pak transakce odeslání mezd všem zaměstnancům kvůli této chybě abortuje.
  • Flat transakce nemohou spolupracovat s jinými transakcemi. Nemohou s nimi sdílet data (pro sdílení dat neexistují žádná primitiva nebo pravidla), nemohou být vzájemně propojeny přes signifikantní události.
  • Neřeší přirozený problém vnoření do sebe. Běžné programovací jazyky umožňují vnořovat volání procedur, take se může stát, že zavoláme v transakci proceduru, která zahájí novou vnořenou transakci.
SavePointy
SavePointy
Zřetězené transakce
Zřetězené transakce

Savepointy (SP)

  • podporuje MS SQL Server 2008 a Oracle také commitovány.
  • rollbacky se neprovadi az na zacatek, ale k jiz ulozenym savepointum (první SP většinou po startu transakce).
  • dopředný rollback
    • rollback k rollbacknutým stavům
    • rollbacky se pak stávají součástí historie
  • neřeší tvrdé výpadky systemu ⇒ po opetovnem nabehnuti systemu se musi transakce provest znovu, ne od posledniho savepointu, persistetní savepointy zase nemusí odpovídat stavu kódu transakce
Dopředný rollback detailně  

Dopředný rollback u SP si představuju jako akci zpět a dopředu u prohlížečů.

Akce zpět způsobí klasický rollback k danému SP (tj. v prohlížeči se vrátit o X stránek zpět).

Akce dopředu způsobí, že se zruší rollback a vrátíš se k původně smazanému SP (tj. v prohlížeči jít o X stránek dopředu).

V praxi si myslím, že to funguje následovně (předpoklad: těsně před zavolání rollbacku se vytvoří SP):

SP1 ... SP2 ... SP3 ... SP4 ... SP5 + Rollback(SP2)
                    ... SP6 ... Rollback(SP5)

Vyzvětlivky: - Rollback(SP2) způsobí vytvoření SP5 a zrušení efektu akcí mezi SP2 a SP5; - Rollback(SP5) funguje jako dopředný rollback - tj. smaže se efekt akcí mezi SP2 a SP6 a znovu se projeví efekt akcí mezi SP2 a SP5.

Ale tadyto jsem nikde nevyčetl, je to spíš moje představa o tom, jak by to mohlo fungovat.

Zřetězené transakce (Chained Transactions - CT)

  • Programátor se po části výpočtu vzdá možnosti rollbacku nad touto částí, tj. komituje
  • Nechce ale ztratit kontext, kurzory, atp.
  • Tj. je potřeba zavést atomickou operaci Chain work = Commit + Begin
Nested Transactions

Hnízděné transakce (Nested Transactions - NT)

výpočet jako hierarchie transakcí, zobecnění SP

Pravidla pro podtransakce:

  • COMMIT pravidlo - po potvrzení podtransakce jsou výsledky dostupné jen v rodičovské transakci, podtran. skutečně potvrdí až s potvrzením kořenové transakce
  • ROLLBACK pravidlo - pokud je podtransakce zrušena, bere sebou všechny své potomky (i když už lokálně potvrdili), když je zrušena kořenová transakce
  • pravidlo viditelnosti změn - zmeny v podtransakci jsou po lokálním COMMITu vidět jen v rodiči, objekty držené rodičem jsou přístupné potomkům, potomci jsou izolovaní v případě souběžného spuštění
  • rodič rozhoduje o řešení zrušení potomka (restartovat, zvolit alternativní výpočet, abortovat)

ACID vlastnosti podtransakci jsou splnene jen částečně: A - podtr. jsou A jen z rodiče, C - podtr. jsou C vzhledem lok.fci., I - silná, D - neplatí kvuli commit pravidlu


Distribuované transakce

Distribuované Transakce - DT (🎓)

příklad DT - převod peněz
  • BEGIN TRANSACTION
  • UPDATE amount = amount - 100 IN bankAccounts WHERE accountNr = 1
  • UPDATE amount = amount + 100 IN someRemoteDatabaseAtSomeOtherBank.bankAccounts WHERE accountNr = 2
  • COMMIT

Zážitky ze zkoušek  
  • Distribuované transakce (2010, Richta) - Stačilo jen základy. Centralizovaný/decentralizovaný přístup. Dvoufázový potvrzovací protokol.


  • jsou to transakce, které pracují s více uzly najednou / s více databázemi v síti apod. (říká se jim také globální transakce)
  • musejí splňovat ACID (jako jakékoliv jiné transakce) nezávisle na fragmentaci a replikaci dat
  • celkem jednoduchý algoritmus, který problém řeší je "Dvoufázový commit"
Zamykaní v DT - centralizované/decentralizované

V distribuovanych systemech muze byt sprava zamku bud centralni nebo v kazdem uzlu pro lokalni data.

  • centralni - uviznuti je mozne detekovat pomoci konstrukce grafu vzajemnych zavislosti, nevyhodou jsou vysoke komunikacni naklady a zranitelnost systemu vypadkem uzlu spravujiciho zamky.
  • lokalni (decentralizované) - obvykle vsak lze graf vzajemnych zavislosti konstruovat bez prilisnych pridavnych nakladu alespon pro lokalni podtransakce (lokální waits-for graf na každém uzlu ale nezachycuje globální závislosti). Pro globalni transakce se casto urcuje casovy limit, jehoz vyprseni se povazuje za uviznuti.
2PC
1. commit-request phase:
        QUERY TO COMMIT
 ------------------------->
        VOTE Y/N            
 <-------------------------
2. commit phase:
        COMMIT (a = b = Y)
        ABORT (a = N ∨ b = N)
 ------------------------->
        ACKNOWLEDGMENT      
 <------------------------- 

příklad 2PC na svatbě [1]

Wedding.png
Dvoufázový Commit 2PC (two-phase commit)
  1. commit-request phase
    • kordinátor (transakční manažer) pošle všem uzlům dotaz → oni ho vykonají až do stavu před COMMIT/ABORT
    • každý uzel pošle svůj výsledek koordinátorovi (YES - COMMIT/NO - ABORT)
  2. commit phase
    • pokud koordinátor dostal od všech uzlů odpověď YES (COMMIT)
      • koordinátor pošle COMMIT zprávu všem uzlům
      • všechny uzly uvolní své zdroje a zámky
      • všechny uzly pošlou koordinátorovi výsledek dotazu
      • koordinátor vše skompletuje
    • pokud koordinátor dostal alespoň jedno NO (ABORT)
      • koordinátor všem uzlům pošle ABORT zprávu
      • každý z uzlů udělá vlastní abort a uvolní zámky a zdroje
      • všechny uzly pošlou koordinátorovi výsledek dotazu
      • poté co koordinátor obdrží výsledky abortuje celou transakci

💡 read-only DT nemusi ucastnik cekat na vysledek hlasovani (staci jen 1. faze) a po 1. fazi uz uvolni zamky. Koordinator nemusi ucastnikovi zasilat vysledek hlasovani

Problémem 2PC protokolu je, že každý z uzlů čeká, až dodělá práci poslední z uzlů, čímž dost dlouho blokuje.

další zdroje  


Izolace transakcí, alokace prostředků. Uzamykací protokoly, časová razítka. (🎓🎓)

Zážitky ze zkoušek  
  • Izolacie transakcii (Skopal) - Ak uz je spominane nizsie, p.Skopal skusa velmi zahadnym sposobom ked polozi otazku a vy netusite co chce pocut. Po 15 minutach ked uz ste spotili aj kravatu zisite ze sa pyta na uplnu trivialitu, ktoru ovladate ale bohuzial za tych 15 minut ste nezistili ze sa pyta prave na to. Toto bolo najtazsia cast mozno aj preto ze pri uceni som to preskakoval s tym ze je to lahke a potom som sa tazko z hlavy vymyslal definicie.
  • Uzamykaci protokoly, casova razitka (Riha) - Serializovatelnost rozvrhu, legalni rozvrh, dobre formovane transakce. Nevedel jsem si rady s pohledovou x konfliktovou ekvivalenci (nejak tak?). Dale casova razitka, jako priklad stromoveho protokolu jsem dal B-stromy se zamykanim a na zaver byla otazka na optimisticke algoritmy.


Tato část je neúplná a potřebuje rozšířit. projit jeste podle wordu

Rozvrhy (VSR ⊃ CSR a RC ⊃ ACA ⊃ ST)

VSR ⊃ CSR
RC ⊃ ACA ⊃ ST

Rozvrh (historie) - stanovene poradi provadeni akci vice transakci

Rozvrh muze byt (formalne viz Soubor:Transakce-typy historii.pdf):

  • Zotavitelny (RC) - když T₂ čte hodnoty z T₁ , pak COMMIT₁ < COMMIT₂ (💡 ABORT neovlivní data potvrzených transakcí)
    • Proti kaskadovemu abortu (ACA) - pokud transakce čte data, museji byt potvrzena (po COMMITu)
      • Striktni (ST) - pokud T₁ zapíše data, T₂ může později číst/přepsat tyto data pouze pokud T₁ skoncila (COMMIT/ABORT)
  • Pohledove uspořadatelný (VSR), pokud je pohledove ekvivalentni se seriovym rozvrhem na stejnych transakcich
    (💡 čtou se stejná data jako v nějakém sériovém r.)
    Rozvrhy S₁, S₂ jsou pohledove ekvivalentni (NP-úplný problém), pokud splnuji nasledujici:
    1. Pokud transakce Tᵢ čte počátecni hodnotu v S₁, čte ji i v S₂
    2. Pokud transakce Tᵢ čte hodnotu zapsanou Tⱼ v S₁, čte ji i v S₂
    3. Pokud transakce Tᵢ provede poslední zápis hodnoty v S₁, provede jej i v S₂
    • Konfliktove uspořadatelný (CSR) - když precedencni graf neobsahuje cykly.
      • Precedenční graf historie H nad množinou transakcí {T₁, .., Tₙ} je orientovaný graf
        • Kde uzly jsou transakce z COMMITované projekce historie H
        • Hrana mezi uzlem Tᵢ a Tⱼ existuje prave tehdy, kdyz operace z Tᵢ předchází a je v konfliktu s nějakou operací z Tⱼ (v konfliktu jsou operace RW (read-write), WR (write-read) a WW (write-write))
      • Uspořadatelný (či Serializovatelný) pokud jeho vykonani vede ke konzistentnimu stavu databaze
        (💡 výsledný stav odpovídá nějakému sériovému r.)
        • Pozor, nyní uvažujeme pouze potvrzené (committed) transakce a statickou databázi (neexistuje vkládání a mazání objektů, pouze čtení a aktualizace)
        • Zcela obecně (včetně akce abort a dynamické povahy DB) se pak definuje konzistence zachovávající uspořádatelnost jako pohledová uspořádatelnost

Testování uspořádatelnosti pro pohledovou ekvivalenci je NP-úplný problém, takže se v praxi nepoužívá - lze nahradit CSR a RC rozvrhy

Izolace transakcí

Chceme aby současný běh více transakcí změnil DB stejně jako seriový běh transakcí (tedy aby mu byl ekvivalentní).

Úrovně isolace transakcí, obecne jsou 4 druhy (definovane standardem SQL92). Jsou to:

Stupeň izolace / fenomén Řešení pomocí zámků DIRTY READ (WR) NON-REPEATABLE READ (RW) PHANTOM
READ UNCOMMITTED zabranuje přepsání nepotvrzených dat nejsou nutné žádné zámky na čtení, S2PL na zápis může nastat může nastat může nastat
READ COMMITTED zabraňuje navíc čtení nepotvrzených dat zámky na čtení (shared), S2PL na zápis nemůže nastat může nastat může nastat
REPEATABLE READ nestane se že 2 stejna cteni vrati ruzne hodnoty S2PL nemůže nastat nemůže nastat může nastat
SERIALIZABLE zabraňuje navíc fantomům S2PL + prevence fantoma (predikátové/intervalové/granulované zámky) nemůže nastat nemůže nastat nemůže nastat
Fenomény zdroj  
  • DIRTY READ (WR): Klient A provede změnu dat a prozatím neukončí transakci. Klient B přečte tato změněná data. Poté klient A odvolá svou transakci. Klient B tedy přečetl data, která nikdy nebyla potvrzena.
  • NON-REPEATABLE READ (RW): Klient A přečte data a prozatím neukončí transakci. Klient B změní nebo zruší tato data a ukončí svou transakci. Klient A ve své transakci znovu čte stejná data a nenajde je.
  • PHANTOM: Klient A položí dotaz, přečte odpověď na něj a prozatím neukončí transakci. Klient B vloží do databáze další řádky vyhovující podmínkám v dotazu klienta A a ukončí svou transakci. Klient A ve své transakci znovu položí stejný dotaz a obdrží jinou odpověď.
Výskyt v dynamických DB (dynamicke DB podporuji vkládání a mazání záznamů)
Triviálně lze řešit zamknutím celé DB -> SR rozvrh
V praxi se spíš řeší jemnějším zamykáním (melo by stacit vedet jen, ze existuji)
Predikátové zámky - napr. se zamknou vsechny zaznamy lidi, kteri jsou starsi nez urcity vek
Rozsahové zámky - vhodné pro struktury využívající uspořádání záznamů
Granulované zámky - používají se pro data organizovaná do logických hierarchií, kde zámek na určitém uzlu hierarchie implikuje zámky na všech potomcích. Zamykani velkych objektu zjednodusuje praci, ale vyrazne snizuje mozny paralelismus a tim vykon.

Ne vždy je potřeba uroven SERIALIZABLE, např. pro statistické dotazy (pro vypocet průměrneho platu z 1000 zaměstannců mi nevadí neopakovatelné čtení), pro účetnictví už by to byl problém

Existuje více strategií, jak zajistit izolaci transakcí

další zdroje  
viz wen:Isolation (database systems), wen:Lock (database), wen:Two phase locking, wen:Deadlock

Zámky

Transakce, která chce přistoupit k datům musí nejdříve tyto data zamknout

zámek - atomická a levná operace

  • shared - čtení dat (rl/ru)
  • exclusive - zápis dat (wl/wu)
Konkrétní implementace DB obsahují mnoho dalších typů zámku, MSSQL např. implementuje tzv. range lock, intent lock, schema lock, …
💡 Platí, že exkluzivní zámek je vzdy konfliktní s jinym (sdilenym/exkluzivnim). Jen dva sdilene zamky jsou v poradku
  • intention - pro hierarchické struktury
    • irl – v podstromu bude požadován rl
    • iwl – v podstromu bude požadován wl
    • riwl – uzel uzamčen pro čtení, v podstromu bude požadován wl

Legální rozvrh - Transakce dostane zámek objektu jen když je k dispozici (podle tabulky konfliktů)

  • Příklad: wl2 [x] w2 [x] wu2 [x] rl1 [x] r1 [x] ru1 [x]
💡 samotná legálnost rozvrhu nezaručuje uspořádatelnost

Dobře formovaná transakce - Před r[x] je vždy (právě jeden) rl[x] a před w[x] je vždy (právě jeden) wl[x]

  • Příklad: rl[x] r[x] wl[y] w[y] ru[x] wu[y] c

Dvoufázová transakce - Dvě fáze – 1. pouze zamykání a 2. pouze odemykání

  • Příklad: rl[x] r[x] wl[y] ru[x] w[y] wu[y] c

Uzamykací protokoly

2PL protokol (dvoufázové zamykání)

2PL - ABORT transakce $ T_1 $ může zkončit ABORTem $ T_2 $ protože měla přístup ke společným objektům po tom co $ T_1 $ už začala uvolňovat zámky
popis konfliktová uspořadatelnost (CSR) zotavitelnost rozvrhu (RC) proti kask. abortům (ACA) zabraňuje deadlocku
2PL nejdrive T jenom zamyká, pak jenom odemyká ANO NE NE NE
S2PL uvolňuje zámky až po konci T (COMMIT / ABORT) ANO ANO ANO NE
K2PL (SSPL) uzamykání pouze na začátku T, odem. na konci ANO ANO ANO ANO
'Klasicky' 2PL protokol
  • pokud už transakce o nějaký zámek požádala a uvolnila ho, nesmí o žádný požádat znovu (💡 stav kdy nepotřebuje žádné dálší zámky = lock point)
  • ⇒ 2 fáze: zamykání a odemykání (tyto 2 faze se tykaji vzdy kazde transakce zvlast, ne celeho rozvrhu)
  • takovýto rozvrh je konfliktově uspořádatelný (CSR), ale negarantuje zotavitelnost rozvrhu (RC) a tim padem ani ACA a ST (=> striktní 2PL)
S2PL
S2PL
KPL
KPL
Striktní 2PL protokol (S2PL)
  • všechny zámky jsou uvolněny až při ukončení transakce
  • generuje striktni rozvrh (ST - tim padem predchazi kaskádovému rušení transakcí ACA a je i zotavitelny RC)
  • rozvrh je konfliktově uspořádatelný (CSR - jako klasicky 2PL)
  • je implementován v každém větším db systému
Konzervativní 2PL protokol
  • implementace S2PL s prevencí deadlocku: všechny zámky které bude potřebovat si vyžádá hned na začátku
  • není používán protože: neví se co za zámky se bude potřebovat, vysoká režie uzamykání a limituje (potencionální) současný běh dlouhých transakcí

💡 Vztahy:

  • Gen(K2PL)⊂Gen(S2PL)⊂Gen(2PL)
  • Gen(S2PL) ⊆ CSR∩ST
další zdroje  
Deadlock (uváznutí)

transakce na sebe čekají v kruhu (čekají navzájem na nějaký zdroj a nechtějí si dát ten svuj)

podmínky pro vznik Deadlock (musí být splněny všechny)

  • vzájemné vyloučení - prostředek může být přidělen pouze jednomu procesu
  • držení prostředků
  • neodnímatelnost
  • čekání v kruhu

Detekce, řešení

  • detekce: cyklus v grafu waits-for
  • abort + restart transakce z cyklu podle nějakého kriteria (např. nejnovější)

snížení frekvence uváznutí (ne její řešení)

  • lock downgrade - pokud už nepotřebuji výhradní zámek, snížím na sdílený
  • lock upgrade - pokud potřebuju výhradní a mám sdílený, mám větší právo, než ten co nemá nic a chce výhradní

prevence deadlocku

  • konzervativní 2PL
  • časové razítko (klasicke nebo striktni, asi ne konzervativni)
  • prioritizování/timestamp (pro 2PL)
    • každá transakce dostane nějakou prioritu (např. časové razítko - čím starší, tím vyšší priorita)
    • dvě možnosti řešení za použití priorit
      • wait-die: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, čeká, jinak zemře
      • wounds-wait: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, T2 zemře, jinak T1 čeká
    • rušeným transakcím je třeba zvyšovat prioritu aby nebyly pořád utiskované

Časová razítka - Time Ordering (TO)

konfliktní operace jsou seřazeny dle odpovídajících časových razítek (TO pravidlo), a tedy nepoužívá zámky (zatím se v komerčních systémech moc neujalo)

  • Každá transakce má přiřazeno unikátní časové razítko ts(Ti)
  • Pro každé dvě různé transakce platí $ ts(T_i) < ts(T_j) $ nebo $ ts(T_j) < ts(T_i) $
  • Každá operace $ p_i[x] $ je označena pomocí $ ts(T_i) $

💡 Pokud je H historie reprezentující výpočet plánovaná pomocí TO pravidla, pak je H uspořádatelná. H je dokonce CSR (viz odkaz), z cehoz plyne usporadatelnost

Zakladni TO pravidlo - jednoduchá agresivní impl. TO pravidla

  • plánovač posílá op. všech transakcí do db (FIFO)
  • pokud nejaka op. prijde pozdě (s nižším $ ts $ než předchozí) dojde k ABORTu její transakce a musí dostat novou $ ts $

💡 Nezajistuje zotavitelnost. Pro dosažení zotavení je potřeba implementovat bufferování všech zápisů dokud transakce nepotvrdí.

Striktní TO pravidlo
  • Kazda transakce pred zapisem danou polozku zamkne (pro zapis i cteni), aby se soucasne nesahalo do DB, a odemkne az skonci (COMMITem/ABORTem)

💡 Zajistuje zotavitelnost (vysledny rozvrh je striktni z cehoz vyplyva, ze je zotavitelny)

💡 Nemuze nastat deadlock (cekaji vzdy transakce s vyssim razitkem). Pri zakladnim TO pravidle deadlock take nenastava - neblokuje se nic (jen objekt pro rychle precteni z DB)

Konzervativní TO pravidlo
  • Pozdržet některé operace (čekat na operace starších transakcí), aby nedochazelo k restartovani transakci.
  • 💡 Pry muze nastat deadlock (viz zde) kvuli temto zdrzenim - zvlastni, kdyz cekaji novejsi transakce na ty starsi (starsi by nemela cekat na novejsi)
další zdroje  


Pomocí precedenčního grafu (PG)

  • nepoužívá zámky, zatím se v komerčních systémech moc neujalo
  • je postaveno na udržování lehce modifikovaného precedenčního grafu, ve kterém se hlídá acykličnost
  • modifikovaný precedenční graf (MPG)
    • neobsahuje všechny komitované transakce (jsou odebrány takové, které byly dávno ukončené)
    • obsahuje uzly všech aktivních transakcí (až na ABORTbortované a COMMITované)
  • existuje základní a konzervativní plánování pomocí PG. Vytváří uspořádatelné historie, které ale nejsou RC (tedy ani nejsou ACA a ST)

Certifikace (optimistické řešení)

  • korektnost se testuje až při pokusu o COMMIT - použitelná pokud dochází velmi zřídka k jakýmkoliv konfliktům (snižuje režii) jinak totiž zbytečně moc často ABORTuje
    • 💡příklad: ukládání článků zde na wiki, wikipedii,...
  • může být založena na různých algoritmech – 2PL, TO, PG certifikátory
  • skládá se ze tří fází
    • Modify - transakce čte z databáze, provádí různé operace, ale vše zapisuje do svého prostoru (databázi nemění)
    • Validate - transakce předloží co vytvořila a SŘBD zkontroluje, zda to není v konfliktu s jinou transakcí (pomocí 2PL,TO,MPG)
    • COMMIT/ROLLBACK - pokud je vše ok COMMIT jinak ABORT
Transactions and Read Consistency: As a query enters the execution stage, the current system change number (SCN) is determined. In Figure, this system change number is 10023. As data blocks are read on behalf of the query, only blocks written with the observed SCN are used. Blocks with changed data (more recent SCNs) are reconstructed from data in the rollback segments, and the reconstructed data is returned for the query. Therefore, each query returns all committed data with respect to the SCN recorded at the time that query execution began. Changes of other transactions that occur during a query's execution are not observed, guaranteeing that consistent data is returned for each query.

Multiversion data

  • existuje vice verzi hodnot nejakeho objektu, takze prepsanim nejake hodnoty se neztrati ta minula, ale jsou znamy obe verze. Přestávají být konfliktní w/w dvojice – nejsou nad stejnou proměnnou
  • s tím jsou ale spojené nové problémy - plánovač musí doplnit operaci čtení o informaci, jakou verzi číst (od toho by měl být uživatel odstíněn)
  • může být založena na různých algoritmech – 2PL, TO, PG
  • std používá Oracle v SQL Serveru se může zapnout
další metody izolace  
Integrované plánovače
  • asi jakesi vylepseni stavajicich planovacu. Je to ukazano na prikladu TO a Thomas Write pravidla:
    • to rika, ze kdyz prepisuju neco, co se vubec neprecetlo (jinak by nastal rollback kvuli tomu cteni) a pritom je to v poradi tech razitek, tak ten drivejsi zapis lze ignorovat. Rozdil je nicmene v tom, ze ten naivni pristup zajisti konfliktovou usporadatelnost, kdezto ten Thomas Write Rule nutne nemusi, nicmene zajisti pohledovou usporadatelnost, coz staci.

Zotavení z chyb, žurnály (🎓🎓)

Zážitky ze zkoušek  
  • Zotavení a žurnály (?) - popsal jsem dva typy způsobů jak to provádět (visí to někde, snad na wiki), proč se to stane a co se musí zajistit. K tomu po mě chtěl zkoušející popsat v základu co je to transakce.
  • Zotavení po chybě systému (Říha) - Zmínil jsem ukládání operací v transakcích do logu (žurnál), dále jak a kdy se ukládá log na disk, jak probíhá samotné zotavení (UNDO, REDO - kdy co) a ještě jsem popsal politiky zápisu nových dat do DB (okamžitý/odkládaný zápis). Zkoušel mě pan Říha, který byl velice příjemný, ale chtěl vědět ještě více informací (jak se udržuje identifikace transakcí v logu, kdy se ukládají savepointy, ...) a já jsem se do toho trochu zamotal a některé věci popletl, ale nakonec taky v pohodě.


Zotavení po havárii systému provádí recovery manager, zajišťuje:

  • atomicitu (odvolání akcí, pokud byla transakce zrušena - undo)
  • trvanlivost (zapsání potvrzených akcí i když systém havaroval)

💡 Datové položky se nezapisují přímo na disk a záznamy logu se nezapisují okamžitě do stabilní paměti - jak DB tak log mají buffer.

ARIES (Algorithms for Recovery and Isolation Exploiting Semantics)

zotavení pomocí ARIES

spustí se po restartu havarovaného systému - implementovan napr. IBM DB2, MS SQL, Informix, Sybase, Oracle

Zotavení probíhá ve třech fázích
  • Analysis - identifikují se dirty pages (stránky modifikované, ale nezapsané v okamžiku havárie) v bufferu a transakce, které byly aktivní v okamžiku havárie
  • Redo - zopakují se všechny akce od posledního uložení na disk (checkpoint) tak aby se databáze dostala do stavu před havárií
  • Undo - odvolají se všechny akce těch transakcí, které nebyly potvrzeny (commitnuty), tedy databáze obsahuje pouze potvrzené transakce

Hlavní principy ARIES

  • Write Ahead Logging – do logu by se mělo zapsat vždy dříve, než se provede a uloží samotná změna objektu do perzistentní paměti
  • Opakování historie během REDO - při restartu po pádu ARIES znovu projede akce před pádem a vrátí systém do stavu před pádem, pak udělá UNDO na transakce aktivní během pádu (nestihly se potvrdit)
  • Logování změn během UNDO (neopakování undo operací během opakovaného pádu systému) - zmeny v databázi během undování transakcí se logují aby se neopakovaly při případných opakovaných restartech

Log ARIES = žurnál (journal), každá změna databáze je nejdříve uložena zde (právě kvůli možné havárii).

Po restartu algoritmus vystopuje všechny akce před havárií a znovu je provede tak, aby se db dostalo do stavu před havárií.
Nepotvrzené akce jsou zrušeny. Při rušení je opět vše logováno pro případ opětovné havárie při provádění ABORT.
záznam v logu je identifikován(log sequence number - LSN)
Take se zalohuji zurnaly. Predpokladame zalohovani v dobe nerozjetych transakci a tudiz kdyz se DB zotavuje ze zalohy zurnalu (neco se s puvodnim zurnalem stalo), nedela se faze Undo.
další zdroje  

Transakce - uzamykací protokoly, zotavení (Databázové systémy)

Indexace relacních dat: B-stromy, hašování, GRACE algoritmus (🎓🎓🎓)

Zážitky ze zkoušek  
  • Indexace relacnich dat - B-stromy a hasovani
  • 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 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:

Fyzická implementace relačních databází (Databázové systémy)
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

Slajdy Pokorný

Vícerozměrné stromy

Vícerozměrné B-stromy

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 (🎓🎓🎓)

Zážitky ze zkoušek  
  • 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)


další zdroje  
viz wen:R-Tree


Tato část je neúplná a potřebuje rozšířit. R-stromy komplet

Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace (🎓)

Zážitky ze zkoušek  
  • IDS - Vektorovy a boolovsky model (Kopecky) - princip, tvar dotazu a odpovede, implementacia


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. (🎓)

Komprese dat: modely textu, kódování

komprese textu

obecné typy redukce dat:

  • ztrátová (nazývá se kompakce) - např. obraz, zvuk, video
  • bezeztrátová (nazývá se komprese a je reverzibilní přes dekopresi)

Proces komprese má 2 fáze:

  • modelování (modely textu) - přiřazení pravděpodobností jednotkám textu (znaky nebo m-tice znaků pevné délky)
  • kódování - transformace do nového kódu pomocí modelu

prefixový kód - jednotliva kodova slova nejsou prefixem zadneho jineho slova

dělení modelů:

  • statická - model je statický pro všechny dokumenty (uložen jednou)
  • semiadaptivní (polostatické) - každý dokument má vlastní model (pošle se s dokumentem)
  • dynamická (adaptivní) - oba algoritmy si model tvoří na základě již zpracovaných dat (musí se dekodovat od zacatku)

Huffmanovo kódování (statické, dynamické) (🎓🎓🎓)

Huffmanovo k. se pouziva v poslední fázi u
  • JPEG
  • MP3,...
Zážitky ze zkoušek  
  • Huffmanovo kódování (?) - stručně jsem popsal a nakreslil příklad k statické verzi, popsal jsem jak funguje dynamická, jak se mění strom atd.
  • Huffmanovo kódovanie (Galamboš) - toto som vedel, takže sa v tom moc nevŕtal
  • Huffmanovo kódování - statické, dynamické (Holubová) - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.


Staticke Huffmanovo kodovaní

statické kodovani
  1. Spočítáme frekvence výskytů symbolů (včetně mezer).
  2. Seřadíme znaky od nejmenší frekvence.
  3. Spojováním dvojic zleva vytváříme strom. Nové vrcholy zařazujeme do řady (co nejvíce doprava).
  4. Levé hrany jsou 0, pravé 1.
Vstup: seznam $ n $ zdrojovych jednotek ke kodovaní, $ p $ - usporadana posloupnost $ n $ vah (pravdepodobností) $ p[i] $ ($ 1 ≤ i ≤ n $) jejich vyskytu ve zprave
Vystup: kodova slova dana zretezením ohodnocení hran na cestach od korene k jednotlivym listum binarního stromu
  • výsledný strom se nazývá Huffmanův, výsledný kód je prefixový
  • místo pravděpodobností můžeme použít i četnosti znaku, ohodnocení hran stromu pomocí 0 a 1 je konvencí (je tudíž možno použít i ohodnocení opačné)
  • Huffmanuv i Shannon-Fanův kód je možné generovat v čase $ O(n) $
BEGIN
 ∀ jednotku i vytvoř list o(p[i])
 (uzel ohodnocený pravděpodobností p[i]);
 k := n;
 WHILE k ≥ 2 DO
  BEGIN
   vyber z p dvě nejmenší nenulové p[r] a p[s], kde r ≠ s;
   q := p[r]+p[s];
   vytvoř uzel ohodnocený q;
   hranám < o(q); o(p[r]) > a < o(q); o(p[s]) >
    přiřaď ohodnocení 0 a 1;
   p[r] := q; p[s] := 0; k := k-1
  END
END

Dynamické (Adaptivní) Huffmanovo kódování

Sourozenecká vlastnost stromu: ∀ uzel má sourozence a četnosti v uspořádání podle č.šipky neklesají
  • strom reorganizován podle toho, jak se mění pravděpodobnosti v průběhu kódování (tj. poruší se sourozenecké pravidlo)
  • nepředpokládají se žádné informace o pravděpodobnostech zdrojových jednotek (strom ale můžeme inicializovat vstupní abecedou)
FGK (Faller, Galagher, Knuth)
Vstup: daný Huffmanův strom $ T_1 $, uzel $ o $
Výstup: modif. Huff. strom $ T_2 $
BEGIN
 current:=o;
 WHILE current ≠ root DO
  BEGIN
  vyměň uzel a jeho příp.podstrom v current s uzlem o', který má nejvyšší pořadí mezi uzly se stejnou frekvencí;
  četnost[current]++
  current:=predcessor(current)
 END
END
  • $ AL_{HD} ≤ 2 . AL_{HS} $, kde $ AL_{HD} $ je průměrná délka kódových slov dynamického Huffmanova kódování a $ AL_{HS} $ statického

💡 Λ (Vitter) - složitější úprava FGK s těmito vlastnostmi:

  • počet výměn podstromů je nejvýše $ 1 $, přidá se escape sekvenci pro první výskyt nového znaku
  • minimalizuje nejen $ \sum^n_{i=1} d[i] . p[i] $ ale i $ \sum^n _{i=1} d[i] $ a $ max_i d[i] $
  • $ AL_{HD} ≤ AL_{HS} + 1 $ (nejlepší hodnota mezi dynamickými Huffmanovými metodami)


další zdroje  


aritmetické kódování,

viz wen:Arithmetic coding
Slajdy k OZD II (od slajdu 47)
Dokumenty k DIS (myslím, že v posledním kroku příkladu je chyba)

LZ algoritmy,

Slajdy k OZD II (od slajdu 56) (LZ77, LZSS, LZ78, LZW a další)

komprese bitových map,

Slajdy k OZD II (od slajdu 92)
  • pomocí Huffmanova kódování
    • kódováním posloupností pevné délky
    • kódování běhů (posloupnost nul ukončených jedničkou apod.)

rídkých matic,

OZD II

Burrows-Wheelerova transformace.

Reprezentace celých čísel (zrušeno 2010)

Zážitky ze zkoušek  
  • komprese, obecně + komprese čísel (2008 Kopecký) - opět jsem neměl moc jasnou představu, kde je to využíváno - nicméně po lehkým naťuknutí jsem rovnou použil předchozí pohovor o indexaci dokumentů a správně řekl, že se to používá v tom invertovaném souboru pro kódování seznam těch dokumentů, kde se term vyskytuje. Pak jsem byl ještě poučen, že jak je ten seznam setřízen, tak se nekódují konkrétní čísla, ale přírustek od předchozího indexu.


Slajdy k OZD II (od slajdu 21) (Fibonacciho, Eliasovy kódy, fázování)

Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic

  1. Gray: Transaction Processing: Concepts and Techniques, p.574