Implementace databázových systémů

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
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.[editovat | editovat zdroj]

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

Asi malo: http://statnice.matfyz.info/generated/IOI-html/node78.html http://www.databaze.chytrak.cz/architektura.htm

Transakce[editovat | editovat zdroj]

Modely a vlastnosti transakcí[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

  • 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)[editovat | editovat zdroj]

  • 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)[editovat | editovat zdroj]

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 (🎓)[editovat | editovat zdroj]

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é[editovat | editovat zdroj]

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)[editovat | editovat zdroj]
  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. (🎓🎓)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

  • 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í)[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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 (🎓🎓)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í.

okruhy 14/15: 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.

Interní hašování[editovat | editovat zdroj]

viz společná část "Hašování" dá se to přežít jenom s interním hashováním

Externí hašování[editovat | editovat zdroj]

hashovací struktura se nevejde do hlavní paměti (RAM), efektivnost se počítá podle počtu přístupů k blokům v externí paměti (HDD)

Statické hashovací metody[editovat | editovat zdroj]

  • hashovací fce mapuje klíče do fixního počtu adres/stránek
  • umožňují přidávat klíče ale neumožňují rozšiřovat adresní prostor bez přehashování celého indexu
  • vhodné pro statické databáze

Cormack (perfektní hashování)[editovat | editovat zdroj]

Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ (k, j.r)

V vyzdvyhnutiu lubovolneho zaznamu su potrebne najviac dva pristupy na disk. Ak je adresar ulozeny v pamati tak potom jeden.

Potrebujeme:

  • Hlavnu hashovaciu funkciu h(k) ktora vracia [0...n] Pre pristup k riadku adresara
  • Pomocnu hashovaciu funkcia hᵢ(k, r) vracia hodnotu s ⟨0, r - 1⟩ napr hᵢ(k, r) = (k mod (2i + 100r + 1)) mod r
  • Adresar ( Velkost O(n) kde n je velkost suboru ) ktory obsahuje parametre druhej hashovacej funkcie ( p : index do primarneho adresara, i index hashovacej funcie , r pocet miest na kolko hashovacia funcia hᵢ prvky hashuje)
  • Primarny subor obsahuje data a je ulozeny na disku.

FIND: Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ ( k, j.r )

INSERT: Vsetky hodnoty adresara su na zaciatku 0.

  • Zistime riadok adresara
    • Ak je prvy najdeme pre neho volne miesto , ulozime ho a zauktualizujeme adresar
    • Ak nieje prvy zobereme kolidujuce zaznamy a pozrieme ci nemame koliziu. Ak nie najdeme novu funciu ktora bude mat obor hodnot tak aby sme zaheshovali n + 1 prvkov , najdeme volne miesto a zaktualizujeme adresar.
Příklad  
Vysvetlivky:
  p ... pointer do primarniho souboru
  i ... index pouzite hashovaci funkce
  r ... pocet kolidujicich prvku/rozsah pro hi (velikost bloku v prim.
        souboru, jehoz zacatek dostanu pomoci has. fce h)

Hashovaci funkce:
  h(k) = k mod 7
  hi(k,r) = (k >> i) % r

Vkladane prvky:
  8, 9, 23, 5, 12, 22, 2

i(8):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │    └────┘
2 │    │   │   │      \
3 │    │   │   │       primarni soubor
4 │    │   │   │
5 │    │   │   │
6 │    │   │   │ - adresar
  └────┴───┴───┘
--------------------------------------------------------------------------
i(9):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │  9 │
2 │  1 │ 0 │ 1 │    └────┘
3 │    │   │   │
4 │    │   │   │
5 │    │   │   │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(23):
23 % 7 = 2, dochazi ke kolizi. Najdeme nove misto v prim. souboru,
kam se vejdou oba kolidujici prvky (souvisly blok velikosti 2).
Prvni takovy existuje na pozici 2.
Zkusime pouzit fci h0:
  23 % 2 = 1, ale take 9 % 2 = 1.
Musime tedy zvolit jinou hasovaci funkci.
Pouzijeme h1, vypocitame nove pozice prvku 9 a 23 v ramci bloku
velikosti 2.
  (23 >> 1) % 2 = 11 % 2 = 1
  (9 >> 1) % 2 = 4 % 2 = 0
Vysly ruzne hodnoty, tedy lze h1 pouzit.
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │    └────┘
5 │    │   │   │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(5):
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │  5 │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │    └────┘
5 │  1 │ 0 │ 1 │
6 │    │   │   │
  └────┴───┴───┘
--------------------------------------------------------------------------
i(12):
 Kolize s cislem 5. Zkusime pouzit hasovaci fci h0.
  5 % 2 = 1
  12 % 2 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  8 │
1 │  0 │ 0 │ 1 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │    └────┘
  └────┴───┴───┘
--------------------------------------------------------------------------
i(22):
 Kolize s 8. Fci h0 nelze pouzit k rozliseni, zkusime h1.
  (8 >> 1) % 2 = 0
  (22 >> 1) % 2 = 1
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │    │
1 │  6 │ 1 │ 2 │  1 │    │
2 │  2 │ 1 │ 2 │  2 │  9 │
3 │    │   │   │  3 │ 23 │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
                    └────┘
--------------------------------------------------------------------------
i(2):
 Kolize s 9 a 23.
 Fce h0 selze, protoze 23 % 3 = 2 % 3 = 2.
 
 9 dec = 1001 bin
 23 dec = 10111 bin
 12 dec = 1100 bin

Zkusime h1:
  (9 >> 1) % 3 = 4 % 3 =1
  (23 >> 1) % 3 = 11 % 3 = 2
  (2 >> 1) % 3 = 1
Zkusime h2:
  (9 >> 2) % 3 = 2
  (23 >> 2) % 3 = 2
  (2 >> 2) % 3 = 0
Zkusime h3:
  (9 >> 3) % 3 = 1
  (23 >> 3) % 3 = 2
  (2 >> 3) % 3 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │    │   8 │  2 │
1 │  6 │ 1 │ 2 │  1 │    │   9 │  9 │
2 │  8 │ 3 │ 3 │  2 │    │  10 │ 23 │
3 │    │   │   │  3 │    │     └────┘
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
--------------------------------------------------------------------------
d(23):
Postupujeme podobne jako u vkladani. Potrebujeme najit souvisly blok
velikosti 2. Takovy je na zacatku, nemusime zvetsovat velikost
prim. souboru. Zmenime tedy p na 0. Snizime r a prozkousime has. fce.
Zkusime h0:
  23 % 2 = 1
  2 % 2 = 0
   p    i   r
  ┌────┬───┬───┐    ┌────┐
0 │    │   │   │  0 │  2 │
1 │  6 │ 1 │ 2 │  1 │  9 │
2 │  0 │ 0 │ 2 │  2 │    │
3 │    │   │   │  3 │    │
4 │    │   │   │  4 │ 12 │
5 │  4 │ 0 │ 2 │  5 │  5 │
6 │    │   │   │  6 │  8 │
  └────┴───┴───┘  7 │ 22 │
                    └────┘
Faginovo hashovanie pre hlbku adresara 2

Dynamické hashovací metody[editovat | editovat zdroj]

  • umožňuje dynamický nárůst adresního prostoru pomocí dynamické hashovací fce
  • vhodné pro db s měnící se velikostí

Fagin (rozšiřitelné adresářové hashování, Koubkovo "externí hashování")[editovat | editovat zdroj]

Potrebujeme

  • Adresar ( Obsahuje ukazovatele / nie nutne unikatne / na stranky dat v na disku ; hlavicku v ktorej je ulozena hlbka adresara 0 < d < r) / aky pocet bitov sa bere s pseudokluca)
  • Hashovaciu funkciu pre pseodukluc h(k). Pseodukluce maju vsetky rovnaku dlzku r
  • Stranky na disku , stranka obsahuje lokalnu hlbku d`. Ak d` < d tak na jednu stranku vedie viac ukazovatelov

FIND:

  • Spocitame pseodukluc k` = h(k)
  • Vezmeme hlbku adresata (d) a precitame prvych d bitov s pseodokluca ( nazveme to p)
  • Zobereme ukazovatel, ktory je umieneny v p.v ( v je velkost kazdeho pointra v bytoch ) ⇒ vedie na hladanu stranku

INSERT: Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář.

Příklad  
 Predpokladejme, ze do stranky se vejdou 2 zaznamy

 h(k) = k mod 32 - hasovaci fce
  -Vzdy na klic pouzijeme h(k) a potom vezmeme horni bity z takto
   ziskaneho cisla.
  -Pocet bitu, ktere budeme brat mame v "ousku" adresare. Pritom vzdy uvazujeme
   vsech pet bitu z cisla, tj napr. 2 dec = 10 bin budeme uvazovat jako 00010

 Vkladane hodnoty:
   5, 20, 33, 28, 30, 8, 25

 i(5): // 5 dec = 00101
       "ousko" adresare - rika, kolik bitu ma adresar
   ┌─┐/          "ousko" u stranky - rika, kolik (hornich) bitu rozlisuje
   │1└─┐     ┌─┐/ hodnoty
 0 │   │─────│1└─┐
 1 │   │─┐   │ 5 │
   └───┘ │   │   │
         │   └───┘
         └┌─┐
          │1└─┐
          │   │
          │   │
          └───┘
 i(20): // 20 dec = 10100
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │   │
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │   │
          └───┘
 i(33): // 33 mod 32 = 1 = 00001
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │ 33│
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │   │
          └───┘
 i(28): // 28 = 11100
   ┌─┐
   │1└─┐     ┌─┐
 0 │   │─────│1└─┐
 1 │   │─┐   │  5│
   └───┘ │   │ 33│
         │   └───┘
         └┌─┐
          │1└─┐
          │ 20│
          │ 28│
          └───┘
 i(30): // 30 = 11110
   Chceme umistit hodnotu do stranky, ktera je plna. Zvetsime adresar, po zmene
   bude dvoubitovy. Strankam, ktere nepotrebujeme stepit jen zvetsime "rozsah",
   prvky ze stepenych stranek rozhazime podle hornich bitu do spravnych stranek.
   Take si do "ouska" stranek poznamename, ze rozlisujeme hodnoty podle dvou
   bitu.
    ┌─┐       ┌─┐
    │2└─┐     │1└─┐
 00 │   │─┬───│  5│
 01 │   │─┘   │ 33│
 10 │   │───┐ └───┘
 11 │   │─┐ └─────┌─┐
    └───┘ └┌─┐    │2└─┐
           │2└─┐  │ 20│
           │ 28│  │   │
           │ 30│  └───┘
           └───┘
 i(8): // 8 = 01000
   Vkladame do plne stranky, ta se ale da rozstepit, protoze rozlisuje
   hodnoty jen podle jednoho bitu.
         ┌──────────┌─┐
    ┌─┐  │    ┌─┐   │2└─┐
    │2└─┐│    │2└─┐ │  5│
 00 │   │┘┌───│  8│ │ 33│
 01 │   │─┘   │   │ └───┘
 10 │   │───┐ └───┘
 11 │   │─┐ └─────┌─┐
    └───┘ └┌─┐    │2└─┐
           │2└─┐  │ 20│
           │ 28│  │   │
           │ 30│  └───┘
           └───┘
 i(25): // 25 = 11001
   Vkladame do plne stranky, jeji "rozsah" nelze rozdelit (rozlisuje hodnoty
   podle dvou bitu) - musime zvetsit adresar a rozdelit prislusnou stranku a
   zmenit "rozsahy" jednotlivych stranek.
           ┌─────────┌─┐
     ┌─┐   │   ┌─┐   │2└─┐
     │3└─┐ │   │2└─┐ │  8│
 000 │   │─┤┌──│  5│ │   │
 001 │   │─┘│  │ 33│ └───┘
 010 │   │─┬┘  └───┘
 011 │   │─┘            ┌─┐
 100 │   │─┬────────────│2└─┐
 101 │   │─┘       ┌─┐  │ 20│
 110 │   │─────────│3└─┐│   │
 111 │   │──┌─┐    │ 25│└───┘
     └───┘  │3└─┐  │   │
            │ 28│  └───┘
            │ 30│
            └───┘
Schéma štěpení při lineárním hašování

Litwin (lineární bezadresářové hashování)[editovat | editovat zdroj]

Nevyužívá adresář, ale potřebuje oblast přetečení a tedy není zaručeno, že se ke všem datům dostaneme v 1 přístupu na disk. Data uložena ve stránkách.

Stránky jsou štěpeny nezávisle na tom, kde došlo ke kolizi, kruhovým schématem (viz obrázek). Po každých L (L je parametr metody) vloženích je rozštěpena 1 stránka. Když dochází ke štěpení stránky, přidáme 1 stránku na konec úložiště stránek . Záznamy ze štěpené stránky (a případné z oblasti přetečení, které by patřily do štěpené stránky) jsou potom rozděleny mezi novou a štěpenou stránku.

FIND: h(k) = k` (pseudoklíč má na rozdíl Fagina podle posledních bitů a jeho délku spočítá podle počtu všech stránek, pokud tam není hledáme v obl.přetečení)

INSERT: najdi místo pomocí FIND a pak vložíme, pokud se nevejde tak nacpeme do oblasti přetečení, po L INSERTech štěpíme a podle posledních bitů rozdělíme záznamy

Růst primárního souboru je lineární ⇒ lineární hashování

Příklad  
Hasovaci fce - v nasem pripade pouze prevod z desitkove do dvojkove soustavy
Vysvetlivky:
b = 3 ...velikost bloku
l = 2 ...po kolika insertech se ma stepit stranka
Vkladane hodnoty:
12, 5, 4, 1, 3, 2, 7, 14

i(12):
┌────┐ Kdyz mame jedinou stranku (do 1. stepeni), vkladame do ni
│ 12 │ vsechny hodnoty (nezalezi na poslednim bitu).
│    │
│    │
└────┘
i(5):
┌────┐
│ 12 │
│  5 │
│    │
└────┘      "oznaceni stranky" - posledni bit(y) cisel ve strance maji
 ├──────┐ /                      tuto hodnotu
 │ 0    │ 1
┌────┐ ┌────┐  Protoze l=2 a vlozili jsme druhy prvek, dojde ke stepeni.
│ 12 │ │ 5  │  Podle posledniho bitu cisel se rozhodne, do
│    │ │    │  ktere pujdou stranky.
│    │ │    │
└────┘ └────┘
i(4):
    0      1
┌────┐ ┌────┐
│ 12 │ │  5 │
│  4 │ │    │
│    │ │    │
└────┘ └────┘
i(1): 
    0      1
┌────┐ ┌────┐
│ 12 │ │  5 │
│  4 │ │  1 │
│    │ │    │
└────┘ └────┘
 ├──────────────┐
 │ 00      1    │10
┌────┐ ┌────┐ ┌────┐ Vlozili jsme 4. prvek - dochazi ke stepeni.
│ 12 │ │  5 │ │    │ Hodnoty rozdelujeme podle poslednich dvou
│  4 │ │  1 │ │    │ bitu.
│    │ │    │ │    │
└────┘ └────┘ └────┘
i(3): 
   00      1     10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │    │
│  4 │ │  1 │ │    │
│    │ │  3 │ │    │
└────┘ └────┘ └────┘
i(2): 
   00      1     10
┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │
│  4 │ │  1 │ │    │
│    │ │  3 │ │    │
└────┘ └────┘ └────┘
        ├──────────────┐
   00   │ 01     10    │11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │    │ │    │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
i(7): 
   00     01     10     11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │    │ │  7 │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
i(14): 
   00     01     10     11
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ 12 │ │  5 │ │  2 │ │  3 │
│  4 │ │  1 │ │ 14 │ │  7 │
│    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘
 ├───────────────────────────┐
 │000     01     10     11   │100
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│    │ │  5 │ │  2 │ │  3 │ │ 12 │
│    │ │  1 │ │ 14 │ │  7 │ │  4 │
│    │ │    │ │    │ │    │ │    │
└────┘ └────┘ └────┘ └────┘ └────┘
další zdroje  

https://is.cuni.cz/webapps/zzp/detail/46740/


GRACE algoritmus[editovat | editovat zdroj]

viz Algoritmy implementace relacních operací.

B-stromy (🎓🎓🎓🎓)[editovat | editovat zdroj]

praktické použití B-stromů:
  • NTFS adresáře (B+)
  • Oracle 11g (B+)
  • MS SQL Server 2012 (B+)
  • PostgreSQL 9.2 (B+)
  • MySQL 5.5 (B+)

Více I2 praktický pohled z OZD - důležitá otázka pro databázisty
okruhy 14/15: B-stromy a jejich varianty

Zážitky ze zkoušek  
  • Indexace relacnich dat (2014, 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 jejich varianty (2014, Kopecký) - 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.)
  • DS - B-stromy a jejich varianty (2012) - tady jsem neznal úplně všechny varianty (stacily B/B+/B* jine TEORIE.PDF je neobsahuje), ale nebylo to nijak zásadní, vše hlavní a podstatné jsem věděl, takže OK.
  • B-stromy (2012, Dvořák) Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko :D ) Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost ) Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka )
  • DS - B-stromy + jejich varianty (2010, nějaký teoretik) - Def., operace, složitosti bez žádných větších důkazů.
  • DS - B-stromy a ich varianty (2009, 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.
  • I1/I4 DS - B-stromy (2011, Koubek/Majerech) - Zhruba 2 A4, popis (a,b)-stromu, B-strom jako spec. pripad. Odvozeni log. vysky, neformalne zakl. algoritmy, jejich slozitost, varianty B+, B*, preventivni stepeni a slevani, vyuziti: v databazich, index-sekvencni soubory, A-sort. Ptali se me na to definici (dulezity, ze u korene neplati ta podminka na pocet synu) a pak to zacalo: nejdriv rozdil mezi redudantni a neredudantni verzi a jak se tam lisi delete. :( Nejak jsem nedokazal odvodit, kde je to horsi, pak zacal diskutovat Koubek s Majerechem, ze se to takhle neda poradne rict, ze ta slozitost muze byt v nejhorsim pripade stejna (log n, coz jsem rikal), chvilku se "hadali", pak po me chteli amortizovanou slozitost posloupnosti insertu a deletu - odpoved je, ze to vyjde amortizovane O(1) na operaci, ale dokazat jsem to neumel (pry nejak pres potencial, obdobne jako u Fibonaciho haldy). No a jeste se mne docela pacili, proc jsou ty B-stromy pro databaze lepsi, nez streba BVS - no protoze ja to b muzu zvolit tak, ze pak list ~ stranka na disku. Ale pak me nechali uz zit. Asi jsem uplne neoslnil, ale aby me vyhodili, na to to zas nebylo.


Tato část je neúplná a potřebuje rozšířit. najít další zkazky a doplnit podle nich
  • umožňují při daném klíči najít záznam pomocí několika málo operací, na rozdíl od hashování ale i klíče z nějakého intervalu
  • nejčastější pro indexy na externí paměti, pomocí "klastrování" odfiltrujeme nerelevantní záznamy

B-strom (redundantni, neredundantni)[editovat | editovat zdroj]

setříděný vyvážený m-nární strom s definovanými omezeními větvení (díky nim je rozumně široký)

💡 inserty a delety způsobují pouze lokální změny

pravidla pro neredundatní verzi:

  1. kořen≥2 syny (pokud není list)
  2. vnitřní uzel (mimo kořene) má od ⌈m/2⌉ do m synů
  3. ∀uzel má od ⌈m/2⌉-1 do m-1 (poiterů na) datových záznamů
  4. větevstejnou délku
  5. uzly vypadají takhle: p₀,(k₁,p₁,d₁),(k₂,p₂,d₂), ... ,(kₙ,pₙ,dₙ),u (p - pointery, k - klíče - řadí se podle nich, d - data/pointery na data)
  6. podstromy mají hodnoty klíče mezi klíči z otce
INSERT

💡 v neredundatních se teoreticky dostaneme rychleji k záznamům (ve vnitřních uzlech)

redundatní - mají datové záznamy pouze v listech, takže klíče jsou redundantní ve vnitřních uzlech

Implementace

💡 většinou 1 stránka/blok(8kb) = 1 uzel , tedy arita B-Stromu je okolo 500 a výška se drží okolo 3

INSERT
  • najdeme list kam vložit a pokud je plný uděláme split takže každý nový list je z půlky plný
  • split můžeme zvýšit počet podstromů otce ⇒ split kaskáda (💡 možná optimalizace: přetékáme do sousedů = vyvažování stránek ⇒ nenastane kaskáda)
DELETE
DELETE
  • pokud je po delete uzel méně než z pulky plný mergujeme se sousedem
  • merge můžeme snížit počet podstromů otce ⇒ merge kaskáda

Oba algoritmy pracují v O(log N) v nejhorším případě.

B+-stromy (redundantni)[editovat | editovat zdroj]

tedy data (pointry na ně) jsou pouze v listech, a listy jsou propojeny pointery (💡 nelistové vyšší úrovně mouhou být také propojeny - např. MSSQL pro intervalové zámky)

  • menší vnitřní uzly ⇒ nižší výška (pže uzly mohou být větší) a tj.rychlejší hledání
  • INSERT/DELETE jednodušší ⇒ jednodušší implementace (hlavně range queries)

B*-strom (redundantni, neredundantni)[editovat | editovat zdroj]

generalizace vyvažování:

  • kořen≥2 syny (pokud není list)
  • větevstejnou délku
  • ∀uzel má alespoň ⌈(2m-1)/3⌉ synů
INSERT/DELETE
  • Štěpení se odkládá, dokud nejsou sourozenci plní, potom se štěpí buď 2 do 3. Při odebírání se slévají 3 uzly do 2.

💡 detailněji zde: B-Stromy

staré  
 ;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.
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.
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

Přístupové metody k prostorovým objektům: R-stromy a jejich varianty (🎓🎓🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • R-stromy (2012, Mlýnková) - 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 (2010, 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 (2009, 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..


štěpení uzlu R-Stromu m=3, M=8
Rtreetable.png

dle Guttmana:

PickSeeds: největší nevyužitá plocha B,H=44

∀PickNext

Guttman.png

⇒ BDIE, FGHCA

dle Greene:

Pick Axis
  • PickSeeds: 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

Distribute: setřídíme objekty podle y souřadnice a rozdělíme

Green.png

⇒ ABCDE, FGIH

Typické dotazy na prostorová data jsou:

  • vyhledej bod v prostoru
  • vyhledej oblast v prostoru
  • vyhledej okolí oblasti (bodu)

R-stromy[editovat | editovat zdroj]

💡 obdoba B-stromů pro prostorové objekty (ale hledání může jít současně více cestami)

  • ∀uzel Em 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í: MBB (minimum bounding box) - minimální ohraničující kostka (MOK)
      💡 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 (kvadratická verze, lin.dává horší výsledky)

  • PickSeeds - vybrat dvojici prvků s největší nevyužitou plochou
💡 napáchaly by největší škodu, pokud bychom je dali do stejné skupiny
  • ∀(zbývající uzel) PickNext - postupně k nim přiřazujeme zbylé prvky aby přírustek nev.plochy byl co nejmenší
    • |přírustek k původnímu MBR 1.skupiny pomocí dalšího uzlu - přírustek pův. MBR 2.skupiny pomocí stejného uzlu|
    • vybereme maximální rozdíl (💡 tj.přidání do op. skupiny by napáchalo největší škodu)

Greenová (snažíme se odstranit překrytí listů - při štěpení vyberem jednu z os)

ChooseAxis (=modifikace Guttmana)

  • PickSeeds - z Guttmana
  • ∀ 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[editovat | editovat zdroj]

  • vnitřní (nelistové) MBR uzly se nepřekrývají ⇒ měně větvení dotazu ALE více dělení a větší výška než R-Stromy
  • přiřazuje prostorové objekty do všech listů, do kterých zasahují (tj. odkaz na objekt duplikován)
  • u uzlů není zaručena minimální zaplněnost


štěpení uzlu R*-Stromu m=3, M=8 (jako nahoře)
Rtreetable.png

ChooseSplitAxis

  • seradime podle osy y a počítáme h-okraje

Rstar1.png

  • Celkem: 184
  • seradime podle osy x a počítáme h-okraje

Rstar2.png

  • Celkem: 182
  • vybereme tu s menší hodnotou, tedy x

ChooseSplitIndex - počítáme h-překryv když jsou 2 nejmenší stejné tak i h-objem

Rstar3.png

  • zase vybereme nejmenší a podle nich rozdělíme
⇒ FAHCG, EIBD

R*-stromy[editovat | editovat zdroj]

  • více optimalizačních kritérií oproti R-stromům – minimalizují pokrytí a překrytí pomocí okraje
  • 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ů)
  • Split_RS - štěpení
    • prvky se setřídí do 2 skupin podle osy x1 a x2
      • ∀setřídění jsou vytvořeny všechny kombinace rozdělení prvků tak, aby v 1. skupině bylo aspoň (m-1)+k prvků
    • ChooseSplitAxis - ∀osu se dle ní setřídí prvky a spočítá suma margin-value všech distribucí v dané ose a vybere se osa s nejmenší (margin-value sumou)
    • ChooseSplitIndex - v této ose se vybere distribuce s nejmenší overlap-value, pokud se rovnají menší area-value
      • area-value (h-objem) - součet obou MBR distribucí
      • margin-value (h-okraj) - součet okrajů – ve 2D obvod MBR, ve 3D ohraničující plocha MBB distribucí
      • overlap-value (h-překrytí) - překrytí obou MBR distribucí
    • rozdělíme prvky do 2 distribucí
  • Forced Reinsert
    • ∀prvky nodu N sestupně setřid podle vzd. od středu MBR
    • prvních p prvků odstraň z N a pak je znova insertuj


další stromy  
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)
další zdroje  


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

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


Komprese dat[editovat | editovat zdroj]

okruhy 09/10: Komprese dat: predikce a modelování, reprezentace celých císel, obecné metody komprese, komprese textu. Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, rídkých matic.

okruhy 14/15: 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.

Modely textu[editovat | editovat zdroj]

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

dělení modelů (💡 jako by slovníky):

  • statické - model je statický pro všechny dokumenty (uložen jednou)
  • semiadaptivní (polostatické) - ∀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)
f: A → C⁺ je prosté kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C

kódování[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • komprese (2015, konzultace Kopecký) - pod kódováním bych já asi viděl obecnou problematiku kódování (tj. věci jako reprezentace nějaké posloupnosti znaků slovy nějaké abecedy, prefixovost, jednoznačnou dekódovatelnost, vztah mezi prefixovostí a jednoznačnou dekódovatelností, entropii, a podobně. To další jsou pak speciální případy s nějakými konkrétními vlastnostmi. Když budete umět Fibbonaciho/Eliasovy kódy jako speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků, určitě to nebude na škodu.
  • 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.


Kód K = (A,C,f), kde

  • A = {a₁, ..., aₙ} je zdrojová abeceda, |A| = n
  • C = {c₁, ..., cₘ} je cílová abeceda, |C| = m, obvykle C = {0,1}
  • f: A → C⁺ je prosté kódové zobrazení znaků z abecedy A do prostoru slov v abecedě C.
  • vlastnosti:
    • jednoznačně dekódovatelný - ∀zakódovaný (cílový) řetěz Y ∃ max. 1 zdrojový řetěz X že f(X) = Y.
    • prefixový - jednotliva kodova slova nejsou prefixem zadneho jineho slova
      • 💡 prefixový ⇒ jednoznačně dekódovatelný (opačně neplatí)

Entropie (míra informace) znaku ai v textu je rovna hodnotě E(aᵢ) = -log( "pst výskytu znaku aᵢ v textu" ) bitů.

  • 💡 tj. "obrácená hodnota" - čím je znak častější tím menší má entropii = tím méně informace nese (tím menší počet bitů je potřeba na její reprezentaci)
  • 💡 použítí viz: IDF/ITF
  • prům. entropie 1 znaku: AE(A) = -Σ ("pst výskytu znaku ai v textu") log( "pst výskytu znaku aᵢ v textu" )
    • očekávaná délka 1 znaku přes ∀znaky a jejich psti
  • entropie zprávy: E(A) = E(a₁...aₖ) = -Σ log( "pst výskytu znaku aᵢ v textu" )
    • 💡 tj. součet entropií znaků ve zprávě
    • platí že délka zakódované zprávy je |f(A)| > E(A)
    • redundance: R = |f(A)| - E(A)
speciální případy pro nekonečné množiny s nerovnoměrnou pravděpodobností výskytu znaků  
 
Fibonacciho kody
  • Zalozeno na fibonacciho cislech radu >=2 (např. při řádu 4, se Fib. číslo Fₙ = Fₙ₋₁ + Fₙ₋₂ + Fₙ₋₃ + Fₙ₋₄). Cislo se rozdeli hladovou metodou na scitance v podobe fibonacciho cisel. Ty se seradi od nejmensiho po nejvetsi, zapisi formou '1' je, '0' neni scitanec a zakonci se jednickou navic.
  • pr. (fib cisla 1,2,3,5,8,13,21)
  • 1 -> 11, 2 -> 011, 3 ->0011, 4 -> 1011, 12-> 101011, 32 ->00101011
  • prosty binarni zapis by byl sice kratsi, ale neodlisitelny. Tady mi dve jednicky delaji jasny konec znaku. (pokud se vyskytují dvě jedničky za sebou někde jinde, je možné je nahradit vyšším Fibonacciho číslem, pokud postupuju při určování jedniček od nejvyššího čísla, tak se mi to nestane)
Eliášovy kódy
  • řada kódování, které mají různé vlstanosti
  • alfa kód (unární) – n-1 nul a na konci jednička, dekódovatelné, ale velmi dlouhé kódy
  • beta kód (binární) – klasické binární kódování, krátké kódy, ale nedekódovatelné
  • modifikovaný beta kód – stejně jako beta kód, ale bez úvodní jedničky
  • theta kód – speciální znak pro rozlišení konce kódu
  • gama kód – modifikovaný beta kód je obalený alfa kódem délky tohoto kódu – např. 37, v binárním kódu 100101, v modifikovaném beta kódu 00101, v gama kódu 00000100011
    • jednička na liché pozici určuje konec znaku v textu (krátké kódy + dekódovatelný)
  • modifikovaný gama kód – na začátku má alfa kód délky modifikovaného beta kódu a za ním modifikovaný betakód 00000100101
    • není regulární (asi, že je potřeba dekódovat zprávu vždy odzačátku)
  • delta kód – obdoba modifikovaného gama kódu, ale místo alfa kódu délky využívá gama kódu délky 0100100101, kde 01001 je gama kód pro 6 (délka beta(37))
  • omega kód – pro velmi velká čísla – posloupnost beta kódů zakončená nulou B₀,B₁,...,Bₖ,0
    • Bₖ je binární zápis slova, Bᵢ₋₁ je binárním vyjádřením délky slova Bᵢ znižené o 1, velikost B₀ je 2
    • př: 37: 101011001010
    • 0010 (1), 01100 (2), 01110 (3) nula na konci kódu je příznak toho, že při dekódování, pokud načtu první znak nulu, znamená to, že poslední přečtená část byla Bₖ a ne nějaké Bᵢ, i<k)
  • kódování čísel se používá například při indexaci dokumentů, kdy mám invertovaný soubor, kde je index termů a každý term má seznam ID dokumentů, ve kterých se vyskytuje (pro urychlení vyhodnocování dotazů je tento seznam setřízen – tyhle čísla se pak kódují nějakým prefixovým kódem. Optimalizace, využívá toho, že menší čísla mají kratší kódy – místo jednotlivých ID se kódují pouze přírustky ID (tzn. mám-li seznam 2,8,13,15 – tak se kódují čísla 2, 6, 5, 2)


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

Znakové[editovat | editovat zdroj]

Huffmanovo kódování (statické, dynamické) (🎓🎓🎓)[editovat | editovat zdroj]

Huffmanovo k. se pouziva v poslední fázi u
  • JPEG
  • MP3,...
StatickyHuffman(EMA MELE MASO)
seřadíme podle vyskytu, spojováním uzlů podle nejmenší četnosti zleva vytváříme binární strom
Zážitky ze zkoušek  
  • Huffmanovo kódování - statické, dynamické (2015, Holubová) - Hned na zacatku mi bylo receno, ze se mam zamerit na dynamicke H. kodovani. Mel jsem cokoliv zakodovat a dekodovat.
  • Huffmanovo kódování (2009) - 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 (2008, Galamboš) - toto som vedel, takže sa v tom moc nevŕtal


Staticke Huffmanovo kodovaní[editovat | editovat zdroj]

Kodování
  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.
  • 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) $

Dynamické (Adaptivní) Huffmanovo kódování[editovat | editovat zdroj]

Sourozenecké pravidlo stromu: ∀ uzel má sourozence a četnosti v uspořádání podle červené š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
FGK (Faller, Galagher, Knuth)[editovat | editovat zdroj]
Dynamické kodovani dekódování
  1. Init: Začínáme se stromem s 1 vrcholem (speciální).
  2. Read: Načteme a najdeme znak ve stromu.
  3. Code: Na výstup vypisujeme čísla na hranách (0 vlevo, 1 vpravo). Není ve stromu⇒jdeme do speciálního vrcholu a pak vypíšeme znak na výstup.
  4. FixTree: Pokud znak ve stromu není, přidáme ho a aktualizujeme frekvence postupně až do kořene:
    • Kontrolujeme zda ve stromu ve směru doprava nahoru není vrchol s menší frekvencí než je nová hodnota aktualizovaného. Pokud ano, vezmeme poslední takový a přehodíme ho s aktualizovaným (celé podstromy).
  1. Init: Začínáme se stromem s 1 vrcholem (speciální - ? nebo NYT).
  2. Read: Čteme bity a podle nich hledáme ve stromě.
  3. DeCode: Pokud dojdeme do listu s písmenem, vypíšeme ho.
  4. FixTree: Dojdeme-li do speciálního vrcholu, načteme znak ze vstupu.
    • Znak vypíšeme.
    • Znak přidáme do stromu stejně jako při kódování.
  • speciální vrchol se značí ? nebo NYT
  • první definice symbolů abecedy se kódují nějakým základním prefixovým kódem
  • dosahuje mensi (lepsi) delky kodoveho slova oproti staticke verzi
příklad kódování "aa bb" (dekódování prakticky stejné):
  
kódujeme zprávu "aa bb"

0. začneme stromem s jedním speciálním vrcholem

?(0)

1. kódujeme první znak zprávy a, vypíšeme kód spec.uzlu ? (prázdný řetězec) následovaný definicí znaku a, vložíme do stromu a aktualizujeme frekvence ve stromu

  • Input: aa bb
  • Output: a
  • OutBin: 000
  (1)
 0/ \1
?(0) a(1)

2. kódujeme další a, pouze vypíšeme jeho kód a aktualizujeme frekvence ve stromu

  • Input: aa bb
  • Output: a1
  • OutBin: 0001
  (2)
 0/ \1
?(0) a(2)

3. kódujeme "mezeru", vypíšeme kód spec.uzlu ? (0) a definici znaku "mezera", vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)

  • Input: aa_bb
  • Output: a10_
  • OutBin: 00010001
    (3)
   0/ \1
  (1) a(2)
 0/ \1
?(0) _(1)

4. kódujeme b, vypíšeme kód ? (00) a definici b, vložíme do stromu a aktualizujeme frekvence ve stromu (žádné výměny nejsou potřeba)

  • Input: aa bb
  • Output: a10 00b
  • OutBin: 0001000100010
      (4)
     0/ \1
    (2) a(2)
   0/ \1
  (1) _(1)
 0/ \1
?(0) b(1)

5. kódujeme další b, vypíšeme kód b a aktualizujeme frekvence ve stromu -> porušíme sourozeneckou vlastnost, musíme prohodit uzly na úrovni před kořenem a dokončíme aktualizaci frekvencí

  • Input: aa bb
  • Output: a10 00b001
  • OutBin: 0001000100010001
      (4)
     0/ \1
    (2) a(2)
   0/ \1
  (1) _(1)
 0/ \1
?(0) b(2)

      (4)
     0/ \1
    (3) a(2)
   0/ \1
  (1) b(2)
 0/ \1
?(0) _(1)

      (5)
     0/ \1
   a(2) (3)
       0/ \1
     (1) b(2)
    0/ \1
  ?(0) _(1)
💡 Λ (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  


💡 je optimální pro pravděpodobnosti výskytů znaků, které jsou mocninami 1/2.

aritmeticky zakodovat "JUJ!":

abeceda = {J,U,!}

Pᵢ ={1/2, 1/4 , 1/4}
  0|---J---|1/2----------U----|(1/2+1/4) -------------!---|1
  0|---J---|1/4----------U----|(1/4+1/8) -------------!---|1/2 
1/4|---J---|(1/4+1/16)---U----|(1/4+1/16+1/8+1/32) ---!---|(1/4+1/8)

<1/4+1/8+1/16+1/32; 1/4+1/8> =bin <1/4+1/8+1/16+1/32; 1/4+1/8>

Aritmetické kódování[editovat | editovat zdroj]

Diagram ukazující dekódování čísla 0.538 (kruhová tečka) pro ukázkový model. Oblast je rozdělená do podoblastí úměrně k četnostem symbolů, potom je podoblast obsahující tečku postupně rozdělen stejným způsobem.

vyjadruje kod jako interval z ⟨0;1).

Komprese: rozdelim interval ⟨0;1) na useky odpovidajici relativnim cetnostem jednotlivych znaku. Pri kodovani znaku se z intervalu ⟨0;1) "stane" interval ⟨x;y) odpovidajici kodovanemu znaku. Tento interval se pote vezme jako jednotkovy do dalsi iterace.

Reprezentujeme-li interval dvojici(L,S), kde L je dolni mez intervalu a S jeho delka, postupny vyvoj techto velicin muzeme vyjadrit takto:

L := L + S. cpᵢ
S := S . pᵢ

kde pᵢ je pravdepodobnost vyskytu kodovaneho znaku a cpᵢ = Σⁱⱼ₌₁ pⱼ neboli kumulovana pst. Pocatecni nastaveni je L=0 a S=1

Dekomprese: rozdelim interval ⟨0;1) na useky odpovidajici relativnim cetnostem jednotlivych znaku. Znak intervalu, ktery obsahuje kodovy interval dam na vystup a v tomto intervalu dale hledam.

Nevyhody: je treba aritmetiky velke presnosti, behem kodovani neni vystup – oboje lze ošetřit tím, že jakmile jsou známé první bity, tak se odešlou na výstup a dál se pokračuje se zbylým intervalem, který se jakoby posune o řád níž (např. pokud vím, že je interval [0; 0,001) v bitovém kódování, tak výsledný kód bude určitě vypadat ⟨0,00???; 0,00???))

Priklad: Mame abecedu {a,b,c,d} s pravdepodobnostmi 1/2, 1/4, 1/8 a 1/8 a kodujeme "abc".

λ -> ⟨0;1)  
'a' - ⟨0;1) -> ⟨0;1/2)
'b' - ⟨0;1/2) -> ⟨1/4;3/8)
'c' - ⟨1/4;3/8)-> ⟨25/64; 26/64)

kód není prefixový ⇒ je třeba nějaký speciální znak pro odlišení konce kódu

oproti Huffmanovu kódování výhodné zejména pokud jeden znak je mnohem pravděpodobnější než ostatní

další zdroje  
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)

Slovníkové metody[editovat | editovat zdroj]

Kompresni algoritmy vytvareji pri sve praci slovnik, ktery pouzivaji ke kodovani vstupu. Vsechny metody jsou adaptivni, pri cteni kodu vytvari slovnik a zaroven taky generuji vysledny kod. Jsou kodovany "fraze" (shluky znaku nebo slova), cislovany ve slovniku od nuly.

Existuji dve zakladni kategorie:

  1. organizujici slova prirozeneho jazyka (BSTW)
  2. organizujici retezce (LZ*)

LZ algoritmy[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Komprese PNG a GIF (2012, Grafika, Zara) - Nejhorsi otazku sem si nechal na konec...tuhle sem absolutne nemel pripravenou, navic ji zkousel Zara Snazil sem se co nejdyl mluvit o obecnych metodach komprese obrazu ( RLE, Huffman, LZ77, LZW, Aritmeticke kodovani, Transformace obrazu ) ...to me ale Zara brzo zarazil ze to moc nesouvisi s tim na co se me ptaji at zacnu byt konretnejsi Tak sem otocil papir a tam sem mel par strohych poznamek o PNG a GIF formatech Kdyz sem to zacal komentovat tak me Zara prerusil at je spis vzajemne porovnam kdyz o nich mluvim. Co konkretne ho zajimalo: oba bezeztratove, LZ77 vs LZW, ze oba pouzivaji progresivni metodu zobrazeni, Proc muze mit PNG lepsi kompresni pomer nez GIF kdyz GIF pouziva modernejsi LZW oproti LZ77 ( odpoved ze LZ77 muze byt lepsi nez LZW na nekterych vstupech protoze je to uplne neco jinyho se mu moc nelibila...spravna odpoved je podle Zary ze tam je lepsi prediktor) No casto sem tady tipoval, hodne sem toho nevedel, parkrat me Zara poucil jak ze to vlastne je...celkem bida, ale mel sem pocit ze k vyhazovu sem mel jeste furt nejakou rezervu


LZW - Posíláme jen odkaz do slovníku (na začátku je v něm abeceda)[editovat | editovat zdroj]

Komprese: pocatecnimi frazemi jsou jednotlive znaky. V kazdem kroku se najde nejdelsi fraze ve slovniku shodna se vstupem a jeji kod se zapise. Nova fraze vznika pridanim dalsiho znaku na konec akt. pouzite fraze.

pr. vstup ababababa

  • poc. tabulka:
	fraze   a   b
	cislo   0   1
  • chod alg.
kod   | slovník:
      | 0 a
      | 1 b
a   0 | 2 ab
b   1 | 3 ba
ab  2 | 4 aba
aba 4 | 5 abab
ba  3
Dekomprese: zacina se tak jako u komprese se slovnikem, ve kterem jsou pouze znaky. Nova fraze se tvori z predchozi plus prvniho pismena aktualni (je mozne, aby "nova" fraze sla hned na vystup - jeji zacatek znam - je z predchozi a posledni pismeno bude shodne s prvnim.
  • Komprese i dekomprese vytvori stejny slovnik, používá se v GIF

LZ77 - Okénka (posíláme 3 údaje)[editovat | editovat zdroj]

  • na jeho zakladu jsou postaveny komprimacni programy soucasnosti(zip, arj,...)
  • metoda typu sliding window - posunuju vstupem okenko, pomoci ktereho i koduju. Delim ho na dve casti hledaci (az 7 znaku a vyhledove az 7 znaku). Zprava je kodovana trojicemi <a, l, c> a je posun od aktualni pozice zpet, l je delka jiz kodovane casti ktera se znovu pouzije a c je novy znak. Kazda trojice tak zakoduje nejmene jeden a nejvice 7 znaku.
  • proč zrovna 7 – vejde se to tak akorát do 3 bitů a je to rychlé
  • pr. EMA MELE MASO se zakoduje <0,0,E>, <0,0,M>, <0,0,A>, <0,0,MEZERA>, <3,1,E>, <0,0,L>, <2,1,MEZERA>, <5,1,A>, <0,0,S>, <0,0,O>,
  • pužívá se v PNG

Dalsi algoritmy - existuje spousta variant LZ algoritmu (LZ78 – starší obdoba LZW, LZJ – variace na LZW, kde je omezena délka kódovaných řetězců,...)

další zdroje  

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


Komprese bitových map[editovat | editovat zdroj]

Identifier HasInternet Bitmaps
Y N
1 Yes 1 0
2 No 0 1
3 No 0 1
4 Unspecified 0 0
5 Yes 1 0

Bitmapy se používají jako indexy pro atributy s malými doménami (napr.: muž/žena, low/medium/high,...)

  • velikost bitmapy se rovná počtu záznamů * velikost domény ⇒ rostou lineárně s databází
  • dotazování se dělá pomocí bitových logických boolovských operací
Tato část je neúplná a potřebuje rozšířit. projít podle OZD1H
Komprese

Uvažujeme bitovou mapu, resp. její j-tý sloupec (i-tá pozice říká, že záznam i odpovídá určité j-té hodnotě, nebo např. že dokument i obsahuje term j)

Uvažujeme předpoklad, že existence bitu 1 nebo 0 je nezávislá (pravděpodobnost p, že je tam 0, (1-p), že je tam 1). Z bitového řetězce lze spočítat pravděpodobnost p.

Rozdělíme bitový řetězec na bloky délky k a pro všechny možné bloky vzhledem k umístění jedniček (2^k) vypočítáme jejich pravděpodobnost. Potom pomocí Huffmanova kódování přiřadíme jednotlivým blokům kódy, kterými zakódujeme bitový řetězec. Čím větší p a k, tím větší zisk komprese, ale při velkém k (> 10) exponenicálně narůstá slovník, což nemusí být v praxi použitelné.

Druhou možností je nekódovat bloky pevné délky, ale běhy nul, zakončené jedničkou – tj. 1, 01, 001, 0001, atd. až do pevně stanovené velikosti m (tj poslední blok bude m nul). Spočítáme pravděpodobnosti pro běhy s jedničkou: (p^j)(1-p) – j je počet nul, zbylá pravděpodobnost do 1 (100%) bude odpovídat běhu ze samých nul. A opět Huffmanovým kódováním přiřadím kódy. V tomto případě slovník roste s k pouze lineárně, ale je zase hodně závislý na pravděpodobnosti, že se na vyskytuje 0 (když se blíží k 1, pak je to velice výhodné, jinak zisk komprese klesá)

  • 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.)

Slajdy k OZD II (od slajdu 92)

Řídké matice[editovat | editovat zdroj]

řídká matice obsahuje z velké většiny nuly (např. vektorový index - cca 90% nul), lze reprezentovat:

  • naivně ve tvaru matice (příliš veliké a neefektivní) ( $ \vec{d} $ = [w1, w2, ... , wk] )
  • seznamem indexů, kde se nachází nenulová hodnota ( $ \vec{d} $ = [j1:wj1, j2: wj2, ... , jk: wjk] )
    • kontrukce posuny - matici rozdělit na řádky, vhodně posuneme řádky (zaznamenáme), složíme řádky (sečteme), zaznamenáme do kterého řádku políčko patří
    • viz: OZD II
Burrowsova-Wheelerova transformace
Vstup Všechny
rotace
Seřazení
rotací
Výstup
^BANANA@
^BANANA@
@^BANANA
A@^BANAN
NA@^BANA
ANA@^BAN
NANA@^BA
ANANA@^B
BANANA@^
ANANA@^B
ANA@^BAN
A@^BANAN
BANANA@^
NANA@^BA
NA@^BANA
^BANANA@
@^BANANA
BNN^AA@A

Burrows-Wheelerova transformace (BWT) - Matice, permutace[editovat | editovat zdroj]

Pomocný algoritmus pro změnu pořadí symbolů (permutaci), tak aby se dobře komprimoval (často vyskytující se symboly dá k sobě).

  • používá se v bzip2
tranformace
  • Ze vstupního řetězce (zakončeného symbolem EOF) vytvoří všechny jeho možné rotace.
  • Tyto se dále klasicky seřadí.
  • Ze seřazeného pole rotací původního řetězce se do výstupního zapíše postupně od počátku poslední symbol z každé rotace.

komprese - move-front jako BSTW akorát že inicializujeme slovník abecedou

BSTW[editovat | editovat zdroj]

  • metoda nenavazujici na LZ
  • na zacatku prazdny slovnik, ukladaji se do nej cela slova, vzdy na zacatek. Za kazde slovo je poslan jeho index ve slovniku nebo cislo o jedna vyssi nez je pocet slov ve slovniku spolu s novym slovem. Po kazdem "pouziti" slova ze slovniku se to slovo presune na zacatek slovniku.
  • Pr. kazdy sofsemista musi kazdy den bdit cely den
    • zakoduje se na : 1 kazdy 2 sofsemista 3 musi 3 (<--- ted uz znamena kazdy) 4 den 5 bdit 6 cely 3 (=den)
další zdroje  

http://cs.wikipedia.org/wiki/Burrowsova-Wheelerova_transformace


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