hledat
Toto je starší verze dokumentu!
—-
Obsah
IN-POS 3. Databáze
Zadání
- Kódování dat, kompresní kódování dat, organizace souborů dat.
- Indexování a hašování, bitmapové indexy, dynamické hašování.
- Vyhodnocení dotazů, transformační pravidla, statistiky a odhady.
- Optimalizace dotazů a schématu.
- Zabezpečení báze dat, přístupová práva.
- Transakce, řízení souběžných transakcí, systémy obnovy transakcí po výpadku.
- PV062, PA152, PA150
Vypracování
Kódování dat
Kódování = Proces nahrazování symbolů (resp. jejich posloupností) zprávy symboly (resp. jejich posloupností) nabývajících znaků cílové (kódovací) abecedy.
Množství informace
Množství získané informace odpovídá velikosti odstraněné neurčitosti získáním informace.
Pro je jednotkou bit.
Entropie
Neurčitost zdroje zprávy je rovna množství informace v ní obsažení. (Neurčitost je přijetím zprávy odstraněna.)
- Každý stav s pravděpodobností svého výskytu přispívá do neurčitosti svojí neurčitostí.
- Vztah nabývá maxima pro
, kde
.
- Abeceda = konečná množina znaků (prvků abecedy, písmen,…)
- Kódové slovo = slovo (posloupnost znaků) v kódové abecedě
- Kódování = funkce
- Kód = kódem daného kódování se rozumí obor hodnot zobrazení K
Klasifikace kódů
- Kód s kódovými slovy pevné délky.
- Kód s kódovými slovy proměnlivé délky.
- prefixový, sufixový kód
- stupeň (rate) kódu = průměrný počet bitů použitých pro kódování zdrojových znaků v tomto kódu.
- optimální kód má stupeň minimálně převyšující množství informace obsažené v symbole zdrojových zpráv.
- Nesingulární kód = jeho kódovací funkce je prostá
- Jednoznačně dekódovatelný kód = Všechny možné řetězce jsou jednoznačně dekódovatelné
- prefixové, sufixové a blokové kódy jsou jednoznačně dekódovatelné
- Prefixový kód = Bezprostředně jednoznačně dekódovatelný kód.
Minimální kódování
- Fanovo kódování
- kódová slova znaků mají délky úměrné množství informace, které znaky nesou.
Př.:
- A = 1 , C = 01 , G = 000 a T =001
- např. řetětzec 8 symbolů ACATGAAC je kódovaný 14 bity:
10110010001101
- tj. v průměru
b/symbol
Kompresní kódování dat
Cílem:
- minimalizace stupně kódu
- při schopnosti on-line dekódování slov bez vkládání separátorů
Kraftova nerovnost
Prefixový q-ární kód s délkami kódových slov d1,d2,…,dm existuje právě tehdy, když je splněna Kraftova nerovnost:
McMillanova veta
Kraftova nerovnost platí pro libovolné jednoznačně dekódovatelné kódování.
Eliasovy kódy
Eliasův kód
Kódování celých čísel u kterých není předem známá horní hranice.
- Zapíšeme číslo dvojkově.
- Odečteme 1 od počtu bitů zapsaných v kroku 1 a na začátek připojíme takový počet nul.
Eliasův kód C1
Prefix 0 určuje délku binární reprezentace.
Př.:
- n=38,
- ⇒
= 00000100110
Eliasův kód C2
Přeuspořádání C1.
- Bity nul se rozptýlý do kódového slova a na konec se přidá 1.
Př.:
= 00011
Eliasův kód C3
Vyjádření délky kódového slova pomocí C2.
- Bity nul se rozptýlý do kódového slova a na konec se přidá 1.
Př.:
(
)
= 6 bitů
= 00110
= 01001
Komprese
- Neztrátová komprese (Lossless Compression)
- dekompresí se získají originální data
- Cílem je zobrazení informace do bitového prostoru co nejméně převyšujícího množství informace obsažené v originálních datech.
- Typicky komprese textů.
- Ztrátová komprese (Lossy Compression)
- Zefektivnění procesu a výsledku komprese za cenu snížení požadavků na přesnost rekonstrukce.
- Informace nevýznamná pro následující zpracování se odstraňuje definitivně.
- Typicky komprese obrázků, zvuku,…
- Kompresní a dekompresní (rekonstrukční) algoritmus.
- Komprese = Kódování zprávy délky P(X) [b] na zprávu délky L(X) [b]
- cílem je dosažení L(X) « O(X)
- ideálně L(X) → H(X) (neurčitost zprávy; méně bity nelze zakódovat beztrátově)
- Kompresní poměr = L(X)/O(X)
- Kompresní faktor = O(X)/L(X)
- Kompresní zisk = (O(X)-L(X))/O(X)
- Redundance zprávy = R(X) = O(X) - H(X)
- Redundance komprimované zprávy = R'(X) = L(X) - H(X)
- Statická komprese
- Neměnná procedura, model.
- Adaptivní komprese
- Procedura komprese se dynamicky mění.
- Fyzická komprese
- Ignoruje se význam komprimovaných dat.
- Logická komprese
- Pro dosažení lepších výsledků se zohledňuje/využívá význam komprimovaných dat.
- Převážně ztrátová komprese.
Kompresní metody
- Základní metody
- Brailovo písmo
- Baudotův kód: 5bit kód, číslicová/písmenová změna
- RLE (Run Length Encoding): náhrada opakujících se sousedních symbolů čítačem opakování a specifikací opakovaného symbolu
- Kódování podle Bentleyho (Move-to-Front Coding): Dynamicky se tvořící abeceda
- lokální adaptivita
- Statistické metody
Shannon-Fanovo kódování
- Metoda na vytvoření prefixového kódu proměnné délky pro známou množinu znaků a četností.
- Reprezentace binárním stromem na základě dělení posloupnosti na poloviny dle četností.
Huffmanovo kódování
- Metoda na vytvoření kódu s minimální redundancí.
- Tvorba stromu opačným směrem než Shannon-Fannova metoda. (Od spoda nahoru.)
Aritmetické kódování
Nekóduje jednotlivé symboly zprávy, ale používá jedno kódové slovo pro zakódování celé zprávy.
- Kódem celé zprávy je číslo z intervalu <0,1)
- Slovníkové metody: Vytváří se slovník dříve přečtených řetězců výstupem jsou indexy do slovníku.
LZ77
- Jako slovník se používá jistá zpracovaná část zdrojového textu, vybíraná klouzajícím oknem, kódují se v něm obsažené řetězce proměnlivé.
- Výstupem je trojice:
- ukazatel počátku vzoru ve slovníku
- délka vzoru
- kódové slovo příštího symbolu za kódovým textem
LZ78
- Používá se samostatný dynamicky vytvářený slovník.
- Výstupem je dvojice:
- index vzoru ve slovníku
- kódové slovo příštího symbolu za kódovým textem
LZW
- Používá se samostatný dynamicky vytvářený slovník.
- Potenciální elementy slovníku jsou v kódové knize přednastaveny.
- Výstupem je jediný údaj – index vzoru ve slovníku.
Organizace souborů dat
Indexování a hašování
Bitmapové indexy
Dynamické hašování
Dotazy
Vyhodnocení dotazů
Transformační pravidla
Statistiky a odhady
Optimalizace dotazů a schématu
Zabezpečení báze dat
Přístupová práva
Transakce
Řízení souběžných transakcí
Systémy obnovy transakcí po výpadku
Zdroje
- slidy PV062 (verze jaro 2015)
- slidy PA150 (podzim 2016)
