Databázové systémy - základní pojmy, principy, architektury. Ukládání a reprezentace dat, zpracování dotazu. Korektní vykonávání transakcí, zpracování systémových chyb, souběžné zpracování, plány, zámky.

Databáze (DB) je uspořádaná množina dat, se kterými můžeme dále pracovat. Správa databáze je realizována prostřednictvím Systému pro správu databáze (Database Management System, DBMS). DB + DMBS tvoří dohromady databázový systém.

Databázové systémy byly vyvinuty kvůli zvládnutí následujících problémů při zpracování souborů v tradičních operačních systémech:

• redundance a inkonsistence dat
• problémy s přístupy k datům
• izolace dat – různé soubory a formáty
• problémy s integritou
• jedinečnost (atomicita) aktualizací
• současný přístup více uživatelů
• bezpečnostní problémy

Databázové systémy mají tedy následující vlastnosti:

1. Struktury datových souborů jsou odděleny od aplikačních (uživatelských) programů.
2. Přístup k datům je možný jen prostřednictvím programů databázového systému.
3. Data je možné vyhodnotit jakýmkoliv způsobem.
4. Je umožněn přístup více uživatelů současně a vyřešena ochrana dat před zneužitím.

Správa databáze zahrnuje prostředky pro popis dat a popis algoritmu.

• definuje sadu příkazů, které lze použít pro vytvoření, úpravu a odstranění objektů (tabulky, pohledy, procedury, funkce) v databázi
• CREATE (vytvoření), ALTER (úprava), DROP (odstranění)

• je syntax podobná programovaciemu jazyku používaná na kontrolu prístupu k dátam ktoré sú uložené v databázi
• GRANT - autorizuje jedného alebo viac užívateľov na vykonanie operácie alebo množinyy operácii na nejakom dátovom objekte
• REVOKE - odoberie prava k vykonaniu operacii

• množina příkazů, které se používají pro výběr, vkládání, úpravu a mazání dat v tabulkách
• SELECT, INSERT, UPDATE, DELETE

1. Externí úroveň – reprezentována daty z pohledu uživatele (např. formuláře pro vstup dat, výstupní tiskové sestavy), různí uživatele vidí různě vymezené části databáze, jde o externí schéma
2. Konceptuální úroveň – popisuje data uložená v databázi a vztahy mezi nimi, jde o logické schéma
3. Interní úroveň – popisuje fyzický způsob uložení dat na vnějších paměťových médiích a metody přístupu k datům, jde o fyzické schéma

• centrální architektura – DB i DBMS jsou umístěné v centrálním počítači, komunikaci zprostředkovávají terminály
• architektura file-server – DB je umístěna na zvláštním počítači pracujícím jako file-server, DBMS na jednotlivých klientských počítačích
• architektura klient-server – DB i DBMS jsou umístěné na datovém serveru, na jednotlivých klientských počítačích běží aplikace, které předávají dotazy na tento datový server
• architektura distribuovaných databází – databázová data jsou rozložena v několika počítačích, navenek se tváří jako jediná velká databáze

• Relační databáze - ukládají data formou tabulek, řádky tabulek reprezentují relace mezi množinami hodnot datových typů, např. PostgreSQL, MySQL, SQLite
• Cyklické databáze - ukládají údaje daného datového typu v časových intervalech, po čase se mohou začít přepisovat, např. RRDtool
• Databáze klíč-hodnota - zpravidla jednoduché aplikační databáze, např. BerkleyDB

Hierarchie ukládání dat je následujicí: Datový element » Záznam » Blok » Soubor » Paměť

Databáze je uložena v kolekci souborů. Každý soubor je tvořen posloupností záznamů. Záznam se skládá z jednotlivých atributů (datových elementů), které mají svůj typ buď pevné (většinou) nebo proměnlivé délky. V nejjednodušším případě je délka záznamu pevná, každý soubor má pouze záznamy jednoho typu a každá tabulka má právě jeden soubor. Záznamy (ať už pevné nebo proměnné délky) ukládáme do bloků pevné velikosti. Záznamy můžeme oddělovat mezi sebou a rozdělovat/nerozdělovat do více bloků.

• celé číslo (zpravidla 2 nebo 4 bajty, přímý nebo inverzní kód)
• reálné číslo (plovoucí (mantisa+exponent) nebo pevná desetinná čárka)
• znak (ASCII, UTF-8, UTF16…)
• pravdivostní hodnota (1 byte » true=11111111 false=00000000)
• bitové pole
• datum (řetězec, UNIX timestamp)
• čas
• výčtový typ
• řetězec (pevná vs. proměnlivá délka. Problémy s pevnou délkou v případě UTF-8)

• Zhruba odpovídají řádkům tabulky
• Formát
  • Pevný - tabulka má danou strukturu, ta je většinou uložena mimo záznamy
  • Proměnlivý - každý záznam obashuje svoje schéma, vhodné pro DB ve vývoji nebo pro velmi řídké tabulky
• Pevná vs. proměnlivá délka záznamu =⇒ jednoduchost,rychlost vs. více možností, úspora paměti
  • S pevnou délkou se lépe pracuje v paměti
  • Proměnlivá délka mívá alespoň na začátku svoji délku
• Hlavička záznamu obsahuje
  • délku záznamu
  • počet atributů, ukazatel na schéma
  • ID záznamu
  • Pole pro NULL hodnoty (1bit pro každý atribut)

Na disku jsou záznamy uloženy v blocích (soubor má vždy velikost násobku bloků).

• halda – záznam je uložen kdekoli na volné místo v souboru
• sekvenční – záznamy jsou v souboru uspořádány podle vyhledávacího atributu
• hašování – pro výpočet čísla bloku, kde má být záznam uložen, se používá hašovací funkce (toto číslo je vypočítáno na základě hodnot vybraných atributů)
• shlukování – záznamy různých tabulek mohou být uloženy v jednom bloku (některá data jsou vyžadována současně)

Každý blok má hlavičku, která obsahuje

• ID bloku
• Adresář záznamů
• Ukazatel na volné místo
• Typ bloku (záznamy, přetoková oblast, TOAST)
• Ukazatel na další blok
• Čas modifikace

Postup zpracování a optimalizace dotazu:

1. dotaz
2. syntaktický strom dotazu
3. logický plán dotazu - v pojmech relační algebry
4. vylepšený logický plán dotazu
5. logický plán dotazu s velikostmi - v PostgreSQL lze zobrazit příkazem EXPLAIN
6. fyzický plán dotazu
7. vyhodnocení

Dotaz se nejprve pomocí parseru převede na syntaktický strom reprezentující strukturu dotazu. Ten se po té zpracuje do výrazů relační algebry (logický plán dotazu). Pomocí transformačních pravidel (kombinace přirozeného spojení, kartézského součinu, sjednocení, selekce a projekce) dále vznikne vylepšený logický plán. Nyní se za pomocí různých statistik (počet záznamů, velikost záznamů v bajtech, počet obsazených bloků, počet unikátních hodnot daného atributu) odhadnou velikosti výsledků, které ovlivňují odhad ceny provedení. Následně se logický plán transformuje na fyzický plán, který určí pořadí operací nutných k vykonání. Porovnají se různé fyzické plány, odhadnou se náklady (velikost výsledků, počet V/V operací) a zvolí se nejlevnější. Nakonec se daný plán provede a tím se získá výsledek.

Transakce je posloupnost operací (DML příkazů), které převedou datové schéma z jednoho konzistentního stavu do druhého (zpřístupňuje a aktualizuje data). Platí o ní, že je ACID:

• Atomic (atomičnost) – transakce se celá provede nebo se celá zruší
• Consistency (konzistence) – po dokončení transakce je databáze konzistentní
• Isolation (izolovanost) – různé transakce o sobě vzájemně nevědí
• Durability (trvanlivost) – po ukončení transakce jsou data trvale uložena

Více transakcí může být spouštěno současně, může však dojít k uváznutí (deadlocku). Chronologické pořadí provádění instrukcí souběžných transakcí je předem určeno pomocí plánu.

Každá transakce může nabývat těchto stavů: aktivní, částečně potvrzená, chybující, zrušená a potvrzená. Pokud byla transakce zrušena, je možné ji znovu spustit (nedošlo-li k logické chybě) nebo zamítnout.

• Klasifikace výpadků
  • výpadek transakce
    • logická chyba (např. data nenalezena)
    • systémová chyba (např. deadlock)
  • zhroucení systému
  • porucha disku

Pro obnovu výpadku požadujeme, aby tranakce byly atomické, databáze konzistentní.

Žurnálování (log, deník)

• O prováděných tranakcích (a jejích operacích) si vedu záznam v žurnálu.
• Při výpadku můžu použít žurnál k REDO, UNDO…
• Místo žurnálování můžu použít redundanci (RAID)

• V případě výpadku se některé operace zruší (z nedokončených transakcí)
• Pro každou akci vytvoř v žurnálu záznam obsahující starou hodnotu
• Před změnou x na disku musí být na disku záznamy žurnálu týkající se x - Tzv. write ahead logging (WAL)
• Před vytvořením záznamu <commit> v žurnálu musí být všechny zápisy transakce uloženy na disku.

• V případě výpadku se některé operace dokončí
• Změny později provedené transakcí jsou ukládány Tj. při potvrzení (commit) – Ušetření zápisů na disk
• Při obnově jsou ignorovány nedokončené transakce
• Vyžaduje uložení žurnálu před uložením změn v DB.

• pravidelné ukládání kontrolních stavů databáze pro případné pozdější obnovení
• něco jako otisky DB , aby se při obnově nemusely dělat od začátku
• také dálají redo, undo

Plánovače

• sériový plán: transakce jdou po sobě
• serializovatelný plán: ekvivalentní sériovému
• Plánovače: optimistické (předpokládají málo konfliktů a nechávají věci plynout, při selhání transakce vracejí, ruší) X pesimistické (předpokládají hodně konfliktů, předchází jim silnou serializací)

Souběžné zpracování (zajišťuje izolovanost)

• zámky:
  • exkluzivní – jen jedna transakce čte a píše,
  • sdílený (shared) – více čtení, žádný write
  • (v ideálním případě se rovná idální serializaci)
  • zámky zpravuje správce zámků a transakce s mím mluví protokolem
    • Dvoufázový transakční protokol na bázi zamykání (růstová fáze - zamykání, couvací fáze - uvolňování po provedení transakce)
    • Grafový (stromový) protokol řízení souběhu transakcí (jednofázový, zná pořadí přístupu transakcí k datům)
    • oba pesimistické plánovače
  • správa zámků představuje netriviální režii.
• Časová razítka – jiné řešení transakce mají čas, kdy vznikly. Nejstarší jde nejdřív. Pesimistické plánování
• Protokol řízení souběhu transakcí na bázi validace (optimistický plánovač). Na konci transakce se zvaliduje, zda došlo ke konfliktu, pokud ano, jedna transakce se abortuje.
• další příklad optimistických je Dropbox.

TODO: příklady plánovačů (2 fázové zamykání, …), viz PA150

• PA152 Efektivní využívání databázových systémů: https://is.muni.cz/auth/el/1433/jaro2011/PA152/um/
• Prednáška k spracovaniu dotazu: https://is.muni.cz/auth/el/1433/jaro2011/PA152/um/slides06-zpracovani-dotazu.pdf
• Prednáška k transakciám: https://is.muni.cz/auth/el/1433/jaro2011/PA152/um/slides11-recovery.pdf
• PA150 Principy operačních systémů: http://www.fi.muni.cz/usr/staudek/vyuka/opsysprincipy/PA150.xhtml
• www.fit.vutbr.cz/study/courses/DSI/public/pdf/nove/9_2.pdf

• Věci převzaté z 4. otázky oboru INS: Honza Havelka, 207401, honza.havelka@seznam.cz
• Zbytek: Michal Trunečka