Toto je starší verze dokumentu! —-

Obsah

IN-POS 3. Databáze
- Zadání
- Vypracování

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.

i(A) = - log P(A)

Pro log_2 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.)

$H(X) = sum{i=1}{s}{p_i log_2 p_i}$

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 : A -> A^{+}_C$
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:

$sum{i=1}{m}{q^{{-d}_{i}}} <= 1$

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, $hat{B}(38)= 00110_2$
- ⇒ = 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ř.:

( $50_{10} = 110010_2$ )
= 6 bitů
= 00110
= 01001
= 0100110010

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

Databáze

databáze = kolekce vzájemně explicitně souvisejících dat
- spravovaná systémem řízení báze dat
pole/položka/atribut základní prvek dat
- s každým atributem souvisí datový typ určující obor možných hodnot a operací nad nimi.
záznam = strukturovaná kolekce polí
soubor = pojmenovaná kolekce příbuzných záznamů

Systém souborů

soubor = pojmenovaná kolekce záznamů
- přístup k souboru jako celku řeší adresářová služba systému souborů
- přístup k datům souboru řeší organizace souborů
- fyzický soubor
  - existuje ve vnější paměti
  - manipuluje s ním OS
  - zaznamenán v adresáři souborů
  - pojmenování vnějším jménem
- logický soubor
  - souborová struktura z pohledu procesu
  - pojmenování jedinečným vnitřním jménem souboru
  - svázán s fyzickým souborem službou OS

Systém souborů (File System) = Sestava služeb pro manipulaci se soubory.

Požadavky na systém souborů

umožnit uživatelům/procesům manipulaci s daty na vnějších pamětech
zajišťovat validnost dat, eliminovat ztrátu dat
souběžná činnost více uživatelů/aplikací
podpora různých zařízení pomocí definovaného API

1. Statické organizace souborů

homogenní soubor – hodnoty položek jsou primitivní typy, všechny záznamy jsou jednoho typu
- je deklarovatelný formou S(A1:D1,…,An:Dn), kde Ax je jméno atributu a Dx je doména hodnot
nehomogenní soubor – hodnoty položek jeho záznamů nejsou primitivní typy nebo záznamy nejsou jednoho typu

Do statické organizace souborů patří:

hromada (neuspořádaný sekvenční soubor)
- Hromada (heap) je nejjednodušší schéma organizace souboru, kdy jsou záznamy v souboru jen náhodně naházeny za sebou. Časová složitost vyhledávání je O(n) (lineární), pokud n je počet záznamů. Jde o nehomogenní soubor, kde záznamy obvykle nemají pevnou délku.
neuspořádaný sekvenční soubor
- homogenní soubor
- sekvenční přístup
- homogenní obdoba hromady

uspořádaný sekvenční soubor
- V uspořádaném sekvenčním souboru jsou záznamy řazeny podle vyhledávacího klíče. Aktualizované záznamy se umístí do zvláštního souboru a až při další operaci reorganization jsou přidány do primárního souboru. Složitost nalezení záznamu je také O(n) (lineární), ale pokud se hledá podle klíče, podle kterého jsou záznamy seřazeny, a navíc je soubor na médiu s přímým přístupem, sníží se na O(log n) (logaritmická).
- Primární soubor + soubor aktualizací (dodatečných změn)
- Soubor aktualizací nebývá seřazený (dopisuje se na konec)
- Reorganizace: seřadíme soubor aktualizací + zatřídíme s primárním souborem do nového primárního souboru
- nevýhody primárního souboru – při vkládání je nutná náročná reorganizace
- keysort – snižuje náklady na reorganizaci – udržuje se soubor (nemusí být seřazený) + index (je vždy seřazený)
- řetězené struktury – řetězení usnadní následná vkládání a rušení záznamů

Ukázka uspořádaného sekvenčního souboru – keysort:
Ukázka uspořádaného sekvenčního souboru – řetězené struktury:

index-sekvenční soubor
- části: primární soubor, index a oblast přetečení
- primární soubor je seřazený podle primárního klíče, ke kterému je vytvořena struktura indexů
- 2 možné přístupy – indexový i sekvenční
- Indexem se vymezuje oblast stránek v primárním souboru, kde záznam může ležet, tato oblast se prohlíží sekvenčně
- buckety pro přesahy, nutná občasná reorganizace

indexovaný soubor
- seřadí se index, primární soubor se záznamy je neseřazený
- Indexovaný soubor znamená primární soubor plus indexy pro různé vyhledávací klíče. Neindexují se už stránky, ale přímo záznamy, a proto primární soubor nemusí být nutně seřazený. Index může být podobný jako u index-sekvenčního souboru, pro záznamy se stejným klíčem je ale vhodné, aby byly na všech úrovních indexu kromě poslední sloučené. Při aktualizaci se nepoužívá oblast přetečení, mění se pouze index.

soubor s přímým přístupem (tak kdyz je tam hash tak to asi patri do dynamickych struktur)
- algoritmická transformace vyhledávacího klíče na adresu záznamu
- hašování

2. Dynamické organizace souborů

Motivace: změny dat neznamenají velké (globální) reorganizace, které jsou drahé, ale spíše reorganizace lokální.

B-strom
dynamický haš soubor
- založený na rozšiřitelném hašování nebo lineárním hašování

Schéma organizace souborů

Logické schéma
- logická paměť se člení na logické stránky (sekvenční/hierarchické uspořádání)
- logická paměť obsahuje primární soubory i sekundární (pomocné) soubory (indexy, rejstříky)
Fyzické schéma
- Zobrazení logických stránek do fyzických stránek konkríétního použitého typu vnější paměti.
Implementační schéma
- Zajišťuje alokaci fyzických stránek v použitém zařízení.

Definice

soubor 1 = pojmenovaná kolekce souvisejících záznamů
soubor 2 = logická paměťová jednotka zobrazovaná operačním systémem do fyzického paměťového zařízení
záznam = kolekce atributů charakterizujících jistý objekt
adresář = kolekce dat obsahující informace o souborech uchovávaných na disku (jméno, typ, adresa, délka, maximální délka, čas posledního přístupu…)

Možná formátování

volné formátování – sekvenčně řazené záznamy pevné i proměnlivé délky
komplexní formátování – soubor obsahuje vhodné řídící struktury nebo se k záznamům přistupuje přes přístupové funkce (B-stromy, haše…)

Uložení souborů na disku

souvislá alokace datových bloků
- soubor je na disku uložen v souvislé posloupnosti datových bloků
alokace datových bloků pomocí zřetězeného seznamu
- každý datový blok obsahuje data a ukazatel na následující datový blok
alokace datových bloků pomocí tabulky
- alokace datových bloků je založená na zřetězeném seznamu, ale ukazatele na následující datový blok jsou uloženy v tabulce FAT
i-nodes
- i-node je struktura, která obsahuje jak atributy souboru, tak adresy datových bloků, ve kterých je uložen obsah souboru

Popis dat
- implicitní: aplikace/uživatel data zná
- metadata: uvedená v hlavičce souboru
  - častá standardizace pro třídu aplikací

Klasifikace souborových organizací
- sekvenční přístup (aplikovatelné na pásce, na disku)
- přímý přístup (aplikovatelné na disku)
  - Určení místo pomocí indexu, nebo hašování

Zamykání souborů
- povinné: zamčený soubor je nepřístupný
- poradní: proces si může zjistit stav zámku a rozhodnout se

Adresář = kolekce dat obsahující informace o souborech uschovaných na disku.
- Sám je souborem.
- Struktury:

1-úrovňový adresář

Jediný adresář v celém systému.

➖ neřeší problém unikátnosti pojmenování souboru.
➖ neřeší se problém seskupování souborů

2-úrovňový adresář

➕ Separace adresářů a uživatelů. (cesta user/soubor)
➕ Uživatelé mohou stejně pojmenovat různé soubory.
➕ efektivní hledání
➖ neřeší se problém seskupování souborů
➖ nelze sdílet

stromová struktura

➕ efektivní hledání hodnoty v uzlu
➕ řeší nezávislé pojmenování i seskupování

pracovní adresář = dynamicky určovaný výchozí bod v adresáři
- absolutní x relativní cesta

aliasing = jeden objekt má více různých jmen

File System Mounting = Připojení nového souborového systému do stávající adresářové struktury (bod přidání = mount point).

Řízení přístupu
- volitelné řízení přístupu (vlastní určuje KDO a CO kdo může)
  - UNIX rwx/ugo
  - Access control lists
  - Capability Tickets
- povinné řízení (práva k souborům prosazována bezpečnostní politikou)

Inode

Řídící struktura obsahující klíčové informace potřebné pro oeprační systém při správě konkrétního souboru.

Implementace systému souborů

File Allocation Table (FAT)

= vázané přidělování diskového prostoru

využití v MS-DOS, Windows
jednoduchá metoda
vázaný seznam nesousedních bloků disku
➖ pevný počet položek

Mapa disku, UNIX

Inode obsahuje (mimo jiné):
- přímé odkazy na bloky (12x4KB)
- single indirect (až 48MB)
- double indirect (až 4GB)
- triple indirect (až 4TB)

NTFS

základem je NTFS svažek (volume) uložýí na diskové oblasti
všechna metadata ukládána do svazku jako soubory
struktura
- ID sektor (boot)
- tabulka Master File Table (MFT) – obsahuje záznamy o souborech (i metadata)
- ostatní systémové soubory
  - zrcadlová kopie MFT
  - soubor s protokolem pro obnovu
  - metadata souborového systému
  - soubor s bitovou mapou volných a přidělených alokačních bloků
  - soubor s definicí vadných sektorů
- uživatelské adresáře a data

Indexování a hašování

procházení přímo záznamů je při operacích velice pomalé – indexy mají řádově menší velikost než samotné záznamy a jejich prohledávání je výrazně rychlejší
díky menší velikosti je možné indexy držet v operační paměti bez nutnosti přístupu na disk
často stačí pro vyřešení některých dotazů zpřístupnit pouze malou část záznamů – na základě indexů je možné efektivně provádět filtrování
forma indexu: { vyhledávací klíč ; ukazatel na záznam }
typy indexů:
- řádné, lineární indexy – v tabulce uspořádané dvojice { vyhledávací klíč ; ukazatel na záznam } podle hodnoty vyhl. klíče
- hašované indexy – využití hašovací funkce vyhledávacího klíče
- stromové indexy – využití grafové struktury strom
- indexové bitové mapy – pozice bitů v bitovém vektoru určují lokality záznamů
indexy mohou být víceúrovňové – „index do indexu“ – nejnižší úroveň může být přímo primární soubor, výše jsou řídké indexy

Řádné indexy

Obvykle pokud se mluví o indexech, jsou myšleny řádné.
Dělení 1

primární index – podle jeho klíče je uspořádán primární soubor se záznamy; může být hustý nebo řídký
sekundární index – určený pro dotazy založené na jiném vyhledávacím klíči než na primárním; musí být hustý

Dělení 2 hustý – indexový záznam pro každou hodnotu vyhledávacího klíče. Typicky bývá uspořádán podle hodnoty klíče
řídký – indexový záznam pouze pro některé hodnoty vyhledávacího klíče; použitelné pouze v případě, kdy je soubor podle tohoto klíče uspořádán

Příklad

Uložený soubor se záznamy:

ID (2B)	Jméno (20B)	Rok narození (2B)	Místo narození (16B)	Telefon (4B)	Bydliště (16B)
1	Bílá Alena	1972	Ostrava	xxxxxxxx	Brno
2	Novák Jan	1952	Praha	123456789	Kladno
3	Novotný Tomáš	1987	Brno	565656565	Vyškov
4	Procházka Petr	1964	Brno	100001011	Řestoky

Hustý index pro atribut jméno:

Jméno	ID
Bílá Alena	1
Novák Jan	2
Novotný Tomáš	3
Procházka Petr	4

Pokud chceme vyhledat místo narození Tomáše Novotného, pak je při sekvenčním prohledávání nutné načíst 2 · (2 B + 20 B + 2 B + 16 B + 4 B + 16 B) + 2 B + 20 B + 2 B + 16 B = 160 B. Při použití hustého indexu stačí načíst 3 · (20 B + 2 B) + 2 B + 20 B + 2 B + 16 B = 106 B. Pokud je index uložen v operační paměti, pak v obou případech stačí pouze jeden přístup na disk, avšak v prvním případě bude třeba číst výrazně více dat.

Řídký index pro atribut jméno:

Jméno	ID
Bílá Alena	1
Novotný Tomáš	3

Pokud je požadavek na vyhledání například Jana Nováka, nalezne se poslední záznam v uspořádání před ním (Alena Bílá) a dál se postupuje sekvenčně.

Sekundární index pro atribut místo narození:

Místo narození	ID
Brno	3,4
Ostrava	1
Praha	2

Hašování

Definice

hašovací funkce (obecně) = převedení libovolně dlouhého vstupu na výstup pevné délky
hašovací funkce (ve smyslu organizace souborů) = funkce řešící přístup k záznamům souboru s konstantní složitostí
kolize = situace, kdy je pro více záznamů spočítána stejná adresa

obvykle se řeší pomocí bucketů – každé paměťové místo má předepsanou kapacitu záznamů, ve které se následně vyhledává lineárně

Perfektní hašovací funkce – hašovací funkce h, která je prostá.
Požadované vlastnosti hašovací funkce:

je deterministická
je rychlá
vypočítává se z hodnot všech nebo alespoň většiny bitů klíče
pokrývá cílový prostor rovnoměrně

Statické hašování

používá se u souborů, které procházejí jen minimem změn
případné změny mohou negativně ovlivnit efektivitu hašování – pokud se sejde na stejné adrese více záznamů než je kapacita bucketu, vyhledávání v rámci těchto záznamů má lineární složitost

Dynamické hašování

k výpočtu adresy se používá pouze prvních i bitů z výstupu hašovací funkce; toto i se dynamicky mění – pokud je potřeba více adres, tak se zvyšuje, naopak při malém počtu se i zmenšuje
používá se u souborů s proměnným počtem záznamů
buckety jsou naplněné rovnoměrně – pokud jsou plné, tak se štěpí, pokud jsou prázdné, tak se spojují
Druhy:
- rozšiřitelné hašování

hašovací funkce rozmisťuje záznamy do kapes (kapsa = záznamy s jistou podmnožinou klíčů, vymezuje je hašovací funkce)
jako index v adresáři kapes se používá dynamicky určovaný prefix výsledku hašovací funkce h(k)
délku indexu vymezuje globální hloubka adresy kapsy
štěpení
- globální hloubka > lokální hloubka – na blok ukazuje více ukazatelů, jednoduše se rozdělí na dva
- globální hloubka = lokální hloubka – musí vzniknout nová kapsa a také se zdvojnásobí rozměr adresáře kapes

lineární hašování

řeší nedostatky rozšiřitelného hašování za cenu vyšší režie dané manipulací s přetokovými kapsami
počet kapes udržuje tak, aby byly naplněny z např. 80 %
rozdíl oproti rozšiřitelnému hašování: nemusí se vytvářet ani udržovat adresář kapes, přesto počet kapes roste lineárně.

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)

mgr-szz/in-pos/3-pos.1560006200.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru