B0B36DBS Webové stránky předmětu

• Konceptuální modelování – ER (entitní typy, atributy, identifikátory, vztahové typy, n-ární, rekurzivní, slabé entitní typy, ISA hierarchie). Logické modely (tabulkový, objektový, stromový, grafový). Relační model (definice, klíč, nadklíč, cizí klíč), transformace ER schématu do relačního schématu.
• Relační databáze – datový model, NULL hodnoty, tříhodnotová logika, integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a referenční akce), umělé identifikátory.
• Jazyk SQL – definice schématu. Manipulace s daty (SELECT, INSERT, UPDATE, DELETE). Spojování tabulek, predikáty, řazení, seskupování a agregace, množinové operace, vnořené dotazy. Pohledy (aktualizovatelnost, CHECK OPTION). Procedurální rozšíření (funkce, kurzory, triggery).
• Fyzická vrstva – bloky, sloty, buffer management. Organizace záznamů (halda, seřazený soubor, hašovaný soubor, složitost operací), indexové struktury (B+-stromy, hašované indexy, bitmapové indexy).
• Funkční závislosti – definice, Armstrongovy axiomy, úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, redukovaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).
• Transakce – základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh / historie, uspořádatelnost / serializovatelnost. Konfliktová uspořádatelnost (konflikty WR, RW, WW, precedenční graf), zamykací protokoly (dvoufázové a striktní dvoufázové zamykání), uváznutí (deadlock, graf čekání, Coffmanovy podmínky, strategie wait-die a wound-wait), fantom.

ER (entitní typy, atributy, identifikátory, vztahové typy, n-ární, rekurzivní, slabé entitní typy, ISA hierarchie). Logické modely (tabulkový, objektový, stromový, grafový). Relační model (definice, klíč, nadklíč, cizí klíč), transformace ER schématu do relačního schématu.

• ER diagramy - diagramy zobrazující realnou strukturu systému, pomáhají uvědomit si co je potřeba zavést do databáze.
• ER - Entity-relationship model
• Nemá standardy - takže si každý z prdele tahá notaci a je to uplně k hovnu
• Méně využíván než UML (for good fucking reason too)

Entita je obecně osoba, projekt, nějaký objekt = třída v UML.

• Silní entitní typ - má alespoň jeden plný identifikátor (např. název u projektu)
• Slabý entitní typ - nemá plný identifikátor, má jeden nebo více částečných id → jeho identifikace závisí na jiné entitě

• Vlastnost entity

• Mají název a kardinalitu (množství)
• Složené atributy - basically více atributů složené do jednoho (např. adresa)
• mají datový typ

• Atribut nebo skuipina atributů, která jednoznačně určuje entitu
• Rozdělení
  • Plné - atribut nebo skupina atributů jedné entity

• Částečné - pomocí vazby na jinou entitu, dovoluje pouze kardinalitu (1,1)

• Mají název, entity a kardinalitu
• Binární - 2 entity
• N-ární - více než 2 entity, mohou být nahrazeny třídou, která má binární vztahy se všemi entitami ve vztahu
• Rekurzivní - typ vztahu mezi entitami stejného typu

specifický vztah bez názvu a kardinalit

• Vytváří hierarchii parent-child
• typ entity, která je speicalizací jiné enity
• child může mít max jednoho parent

• Proces logického modelování
  • Výběr modelu podle charakteristik dat, možností dotazování, použití, požadavky
  • Tvorba logického schématu - transformace z konceptuálního schématu do logického

• Struktura - řádky pro entitry a sloupce pro atributy
• Operace - selection, projection, join
• např.: sql

• Struktura - objekty s atributy, používá ukazatele mezi objekty
• Operace - navigation

• Struktura - vrchol s atributy, hrany mezi vrcholy
• Hieararchie, kategorizace, semi-strukturovaná data
• např.: xml dokumenty, json

• Struktura vrcholy, hrany, atributy
• Opearce - Obhcázení, porovnávání vzorů, grafové algoritmy
• Např.: síťovy model, REsource Description Framework, FlockDB

• Databáze - Logicky uspořádaný soubor souvisejících dat, obsahuje data, metadata, schéma, omezení integrity atd.
• Database management system (DBMS) - Softwarový systém umožňující přístup do databáze, poskytuje mechanismy pro zajištění bezpečnosti a
• spolehlivosti, souběžnost, integritu uložených dat, …
• Databázový systém - informační systém obsahující databázi, DBMS, hardware, procesy, osoby…
• Relační databáze - množina relací

• Vyjadřuje vhybející informaci
• Operace s null
• 3 + null = null
• 3 < null = uknown

==== Integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a referenční akce) *

• Entitní – každý záznam v tabulce má platný a jedinečný primární klíč.
• Doménová – zajišťují dodržování datových typů/domén definovaných u sloupců databázové tabulky
• Referenční – zabývají se vztahy dvou tabulek, kde jejich relace je určena vazbou primárního a cizího klíč
  • NOT NULL - hodnoty nesmí být null
  • UNIQUE - hodnoty musí být unikátní
  • PRIMARY KEY = NOT NULL + UNIQUE
  • FOREIGN KEY - hodnoty klíče v odkazující tabulce musí být v odkazované tabulce
  • CHECK - definuje se podmínka, která musí být splněna

Pokud nejsou nastavené referenční akce a zároveň by operace v odkazované tabulce způsobila porušení cizího klíče v odkazující tabulce, tak by operace byla blokována a generoval by se error message

• Trigger - různé případy změn v tabulce
  • ON UPDATE
  • ON DELETE
• Akce - co se provede po změne v tabulce
  • CASCADE - hodnota je také změněna / odstraněna
  • SET NULL - hodnota nastavena na NULL
  • SET DEFAULT - hodnota nastavena na výchozí
  • NO ACTION - zabraňuje provedení operace
  • RESTRICT - podobný no action

• Zcela automatizované
• Obvykle se jedná o celočíselné řady a každý novější záznam dostává číslo vždy o jednotku vyšší než je číslo u posledního vloženého záznamu
• (číselné označení záznamů s časem stoupá).

Structured Query Language (SQL) je jazyk pro kladení dotazů do databáze. Obsahuje jak příkazy DML (Data manipulation Language), tak i DDL příkazy (Data Definition Language). SQL je case insensitive (nerozlišuje mezi velkými a malými písmeny).

• Transaction management
• Administrace Databáze

CREATE TABLE *

• Název tabulky
• Definování sloupců (atributů) - názvy, datové typy, výchozí hodnota
• Definování integritních omezení v rozsahu tabulky

• ALTER TABLE – změny existujících objektů.
  • RENAME TO
  • ADD COLUMN
  • ALTER COLUMN
  • DROP COLUMN
  • ADD (constraint definition)
  • DROP CONSTRAINT
• DROP TABLE

• Příkazy pro získání dat z databáze a pro jejich úpravy
• DML – Data Manipulation Language
• INSERT INTO – vkládá do databáze nové řádky (záznamy)
• UPDATE – mění data v databázi (editace záznamu)
• MERGE – kombinace INSERT a UPDATE – data buď vloží (pokud neexistuje odpovídající klíč), pokud existuje, pak je upraví ve stylu UPDATE.
• DELETE FROM – odstraňuje data (záznamy) z databáze
• EXPLAIN – speciální příkaz, který zobrazuje postup zpracování SQL příkazu. Pomáhá uživateli optimalizovat příkazy tak, aby byly rychlejší.
• SHOW - méně častý příkaz, umožňující zobrazit databáze, tabulky nebo jejich definice
• SELECT - Vybírá data z databáze, umožňuje výběr podmnožiny a řazení dat
  • SELECT + názvy sloupců, nebo * , nebo definování nových a agregovaných sloupců
    • nové pojmenování sloupců pomocí AS
    • ALL - vše
    • DISTINCT - odstranění duplicit
    • FROM - z které tabulky, poddotazu nebo pohledu
    • WHERE - podmínka
      • AND, OR, NOT
      • predikáty
    • GROUP BY - volba atributů pro agregaci
    • HAVING - podmínka pro agregovaná data
    • ORDER BY - řazení

• JOIN
  • CROSS JOIN - kartézský součin všech řádků z obou tabulek (všechny kombinace)
  • NATURAL JOIN - výsledkem pouze řádky, které mají stejné hodnoty atributů
  • INNER JOIN - defaultní JOIN
    • podmínka ON
    • USING atribut - odpovídá natural join
    • pokud bez ON nebo USING - odpovídá cross join
  • OUTER JOIN - řádky z inner joinu a řádky, které nemohou být spojeny (hodnoty doplněny NULL)
  • LEFT / RIGHT - řádky z levé / pravé tabulky
  • FULL - z obou
  • UNION JOIN - řádky jsou integrovány do jedné tabulky, žádné řádky nejsou spojeny

Fyzická vrstva (bloky, sloty, buffer management). Organizace záznamů (halda, seřazený soubor, hašovaný soubor, složitost operací), indexové struktury (B$^+$-stromy, hašované indexy, bitmapové indexy).

• Specifikuje jak jsou databázové struktury implementovány ve specifickém prostředí
• Zahrnuje soubory, indexovací struktury a tak dále

• Záznamy jsou uloženy na disku v blocích (angl. page) fixní velikosti
• Hardware přistupuje pouze k celým stránkám uloženým na disku (čtení i zápis)
• Čas, který trvá jedna I/O operace se na rotačním pevném disku spočítá jako součet doby hledání, rotačního zpoždění a přenosu dat
• stránky bývají rozděleny na sloty ve kterých jsou uložené záznamy, které jsou identifikované číslem stránky + číslem záznamu
• Záznamy mohou mít fixní nebo variabilní velikost
• Každá stránka má ještě hlavičku, která obsahuje informace o využití slotů, případně jejich velikosti pokud stránka obsahuje záznamy variabilní velikosti

• Buffer je část hlavní paměti, kde jsou dočasně uloženy celé stránky z disku, stránky jsou mapovány na paměťové rámce
• Každý rámec si drží počet referencí na stránku v rámci a dirty flag, který označuje změněný záznam, který nebyl zapsán na disk

• Halda je druh souboru, kde záznamy nejsou v blocích řazené a záznamy tedy mohou být vyhledávány pouze sekvenčně, vkládat nové záznamy je snadné, ale při mazání může vznikat nevyužité místo

  • Prázdné stránky jsou udržovány pomocí spojového seznamu nebo tabulky stránek
  • Všechny operace mají lineární složitost, až na vkládání, které je konstantní
• Řazený soubor je druh souboru, kde jsou záznamy řazeny na základě nějakého klíče

  • Rychlé vyhledávání (logaritmická složitost)
  • Pro vkládání má každá stránka prázdný overhead, pokud je zaplněn jsou použity nové stránky
  • Ve všem kromě vyhledávání je pomalejší než halda

• Soubor je organizovaný do tzv. kapes (anglicky buckets)
• To v jaké kapse je záznam uložený je rozhodnuto na základě hashovací funkce $f$
• Pokud je kapsa plná, je alokována nová stránka a propojena s kapsou formou spojového seznamu
• Výhodou je rychlé vyhledávání, nevýhodou je ale paměťová náročnost (řešeno dynamickým hashováním)
• Většina operací má přibližně složitost $N/K$, kde $K$ je počet kapes

• Index je pomocná struktura, která poskytuje rychlé vyhledávání na základě hledaných klíčů
• Obsahuje typicky jenom klíče a odkazy k záznamům, vyžaduje proto výrazně méně místa než datové soubory
• Index může obsahovat celý záznam, pár klíče a odkazu na záznam, nebo pár klíče a seznamu odkazů na záznam
• Řazení indexovaných předmětů může být zachováno (clustered indexing) nebo nemusí (unclustered indexing)

• Rozšířený B-strom
• Logaritmická složitost pro vkládání, vyhledávání podle rovnosti a mazání podle rovnosti
• Garantuje využití alespoň 50% stránek

  • Oproti B-stromu jsou všechny data (klíču jsou stále v B strom struktuře) v listech a stránky příslušné listům jsou provázány pro vykonávání dotazů založených na intervalech

• Stejné jako hašovaný soubor, ale obsahuje pouze odkazy na záznamy

• Vhodné pro atributy, které mohou nabývat malého množství hodnot
• Každý atribut je realizován jako vektor bitů, kde $i$-tý bit popisuje jestli atribut nabývá $i$-té hodnoty nebo ne
• Dotazy lze pak provádět pomocí bitových masek a bitwise operací
• Výhody - efektivní, kompaktní, rychlé, snadno paralelizovatelné
• Nevýhody - Pouze pro atributy s doménou malé kardinality, pomalé dotazy na základě rozsahu (lineární v šířce rozsahu)

Funkční závislosti (definice, Armstrongovy axiomy), úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, reduko- vaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).

• Funkční závislost $X\rightarrow Y$ nad schématem $R(A)$ je mapování $f_i:X_i\rightarrow Y_i$, kde $X_i,Y_i \subseteq A$
• U $X\rightarrow Y$ říkáme, že hodnoty v $X$ určují hodnoty v $Y$
• Pokud platí $X\leftarrow Y$ a $Y\leftarrow X$, pak řekneme, že $X\leftrightarrow Y$ jsou funkčně ekvivalentní
• Pokud je na pravé straně funkční závislosti jediný atribut $a$, mluvíme o elementární funkční závislosti

1. Triviální funkční závislost: $Y\subseteq X\Rightarrow X\rightarrow Y$
2. Tranzitivita: $(X\rightarrow Y\land Y\rightarrow Z)\Rightarrow X\rightarrow Z$
3. Kompozice: $(X\rightarrow Y\land X\rightarrow Z)\Rightarrow X\rightarrow YZ$
4. Dekompozice: $X\rightarrow YZ\Rightarrow(X\rightarrow Y\land X\rightarrow Z)$

• Uzávěr množiny funkčních závislosti $F$ je množina všech funkčních závislostí, které lze odvodit z funkčních závislostí v $F$ pomocí Armstrongových axiomů
• Značí se $F^+$

• Pokrytí množiny funkčních závislostí $F$ je nějaká množina funkčních závislostí $G$ taková, že platí $F^+=G^+$
• Kanonické pokrytí je takové pokrytí, které obsahuje pouze elementární funkční závislosti

• Funkční závislost $f$ je redundantní v množině $F$, pokud platí $(F-{f}^+=F^+)$
• To znamená, že $f$ je odvoditelné ze zbytku množiny $F$
• Neredundantní pokrytí množiny $F$ je pak takové pokrytí, které vznikne po odstranění všech redundantních funkčních závislostí z $F$

• Uzávěr atributů $X^+$ je podmnožina všech atributů z $A$, které lze odvodit z množiny atributů $X$ pomocí funkčních závislostí
• Pokud $X^+=A$, pak říkáme, že $X$ je super-klíč (nadklíč)
• Ve funkční závislosti $X\rightarrow Y$ je atribut $a$ redundantní když $Y\subseteq(X-a)^+$
• Redukovaná fukční závislost neobsahuje žádné redundantní atributy
• Pro $R(A)$ je klíč je takový super-klíč, kde je funkční závislost $K\rightarrow A$ redukovaná
• Klíčový atribut je atribut, který se nachází v jakémkoliv klíči (klíčů může být víc)

• Minimální pokrytí je neredundantní kanonické pokrytí, které obsahuje pouze redukované funkční závislosti

• Z triviální funkčí závislosti $A\rightarrow A$ postupně odstraňujeme redundantní atributy na levé straně, dokud tam žádné nezůstanou
• Na levé straně funkčí závislosti pak dostaneme jeden z klíčů $A$

• Algoritmus k nalezení všech klíčů

  1. Najdeme jakýkoliv klíč $K$
  2. Vybereme funkční závislost $X\rightarrow y$ z $F$ takovou, že $y\in K$, nebo ukončíme algoritmus pokud neexistuje
  3. Protože, platí $X{K-y}\rightarrow A$, $X{K-y}$ je super-klíč
  4. Redukujeme $X{K-y}\rightarrow A$ a na levé straně dostaneme nový klíč $K'$, který je jiný než $K$
  5. Pokud $K'$ ještě není v množině nalezených klíčů, uložíme jej, položíme $K:=K'$ a pokračujeme na krok 2. Jinak algoritmus končí

• Relace je v 1NF právě tehdy, když platí současně:

  • atributy jsou atomické (dále nedělitelné)
  • k řádkům relace lze přistupovat podle obsahu (klíčových) atributů
  • řádky tabulky jsou jedinečné
• Relace nesplňující 1NF:

• Relace v 1NF:

• Relace je v 2NF právě tehdy, když platí zároveň:

  • relace je v 1NF
  • každý neklíčový atribut je plně závislý na každém kandidátním klíči
• Příklad:

  • Mějme relaci {IdStudenta, IdPredmetu, JmenoStudenta, SemestrLZ}, kde IdStudenta a IdPredmetu tvoří primární klíč.
  • Tato relace není v 2NF, protože JmenoStudenta je závislé pouze na IdStudenta a SemestrLZ je závislé pouze na IdPredmetu.
• Řešení:

  • Rozdělení relace do tří tabulek

    • {IdStudenta, _IdPredmetu__}_
    • _{__IdStudenta,_ JmenoStudenta}
    • {IdPredmetu, Semestr}

• Relace je v 3NF právě tehdy, když platí:

  • relace je v 2NF
  • všechny neklíčové atributy musí být vzájemně nezávislé

• Příklad:

  • Mějme relaci {IdStudenta, JmenoStudenta, Fakulta, Dekan} ta není ve 3NF. Sice je ve 2NF, ale atribut Dekan je funkčně závislý na Fakulta a Fakulta je funkčně závislá na IdStudenta (předpokládáme, že student nemůže být současně studentem více fakult téže university)
  • IdStudenta není funkčně závislá na Fakulta. Atribut _Deka_n je tedy transitivně závislý na klíči.
• Řešení:

  • Rozdělíme relaci do tabulek:

    • _{__IdStudenta,_ JmenoStudenta, Fakulta}
    • {Fakulta, Dekan}

Transakce (základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh, historie, uspořádatelnost, serializovatelnost), konfliktová, uspořádatelnost (konflikty WR, RW, WW, precedenční graf), zamykací protokoly (dvoufázové a striktní dvoufázové zamykání), uváznutí (deadlock, graf čekání, Coffmanovy podmínky, strategie wait-die a wound-wait), fantom.

• transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data.
• Transakce pracuje s konzistentní databází.
• Během spouštění transakce může být databáze v nekonzistentním stavu.
• Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní.
• Dva hlavní problémy:

  • Různé výpadky, např. chyba hardware nebo pád systému
  • Souběžné spouštění více transakci

• K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit:

  • Atomicity : transakce atomická - buď se podaří a provede se celá nebo nic. Nelze vykonat jen část transakce.
  • Consistency : transakce - konkrétní transformace stavu, zachování invariant - integritní omezení.
  • Isolation : (isolace = serializovatelnost). I když jsou transakce vykonány zároveň, tak výsledek je stejný. jako by byly vykonány jedna po druhé.
  • Durability : po úspěšném vykonání transakce (commit) jsou změny stavu databáze trvalé a to i v případě poruchy systému - zotavení chyb.

• akce na objektech : READ, WRITE, XLOCK, SLOCK, UNLOCK
• akce globální : BEGIN, COMMIT, ROLLBACK

• Posloupnost akcí několika transakcí, jež zachovává pořadí akcí, v němž byly prováděny
• Historie (rozvrh) se nazývá sériová, pokud jsou všechny kroky jedné transakce provedeny před všemi kroky druhé transakce.

• Teorie: Nechť se transakce $T$ i skládá z následujících elementárních akcí:

  • $\mathrm{READ}_i(A)$ - čtení objektu $A$ v rámci transakce $T_i$
  • $\mathrm{WRITE}_i(A)$ - zápis (přepis) objektu $A$ v rámci transakce $T_i$
  • $\mathrm{ROLLBACK}_i(A)$ - přerušení transakce $T_i$
  • $\mathrm{COMMIT}_i(A)$ - potvrzení transakce $T_i$
• Jsou možné 4 případy:

• WR konflikt - jedna transakce data zapíše, druhá je čte předtím než byla commited, tzv. dirty read
• RW konflikt - transakce čte data a druhá je zapíše předtím než byla ta první ukončena, tzv. unrepeatable read
• WW konflikt - přepis dat, která ještě nebyla commited, tzv. blind write
• Dvě historie jsou konfliktově ekvivalentní, pokud sdílí stejné konfliktní páry
• Historie je konfliktově uspořádatelná, pokud je konfliktově ekvivalentní s nějakou sériovou historií
• Precedenční graf je směrový graf, kde vrcholy jsou transakce a hrany jsou konfliktní páry mezi transakcemi

  • Pokud je acyklický, je historie sériově uspořádatelná

• Způsob tzv. pesimistické kontroly v plánovači transakcí
• Zamykací protokol je protokol, který zamyká entity tak, aby byla zabezpečena konfliktní serializovatelnost
• Dva druhy zámků

  • Exkluzivní zámek $X(A)$ je zámek, který může držet pouze jedna transakce, pouze transakce, která drží zámek $X(A)$, pak může přistupovat k entitě $A$
  • Sdílený zámek $S(A)$ je zámek, který může být držen více transakcemi, ale umožňuje pouze zápis, nikoliv čtení
• Navíc je definována operace odemykání $U(A)$

• Pokud transakce chce číst (zapisovat) entitu $A$, musí nejprve získat sdílený (exkluzivní) zámek na tuto entitu
• Transakce nesmí zažádat o zámek na entitu $A$ pokud jej předtím už uvolnila
• Zajišťuje acykličnost precedenčního grafu
• Nezajišťuje zotavitelnost (může se stále stát, že transakce uvolní všechny zámky, jiná po ní pokračuje a je ukončena a potom je první transakce přerušena)

• Zajišťuje zotavitelnost a kaskádovité přerušování
• Všechny zámky může transakce pustit až poté co je ukončena

• Situace, která nastane, když všechny transakce čekají až jiná transakce uvolní zámek
• Lze identifikovat pomocí tzv. grafu čekání

  • Vrcholy jsou jednotlivé transakce
  • Hrana z $T_1$ do $T_2$ říká, že transakce $T_1$ čeká až $T_2$ uvolní zámek
  • Pokud je v grafu cyklus, došlo k uváznutí

• Přerušení transakce a restart
• Detekce uváznutí pomocí grafu čekání a přerušení transakce na základě nějakého kritéria (například transakce, která vykonala nejméně práce)
• Dvě strategie na předcházení uváznutí, využívá priority transakcí:

  • wait-die - pokud má čekající transakce vyšší prioritu tak čeká dále, pokud ne, tak je ukončena
  • wound-wait - pokud má čekající transakce vyšší prioritu tak ukončí transakci, která drží zámek, který potřebuje, jinak čeká dále

• K uváznutí může nastat pokud platí všechny z následujících podmínek

  1. Vzájemné vyloučení - zdroje nejsou plně sdíleny a jsou drženy exkluzivně
  2. Držení zdrojů - další zdroje mohou být vyžadovány i když už jsou jiné drženy
  3. Žádná preempce - zdroje mohou být vypuštěny pouze dobrovolně
  4. Kruhové čekání - transakce čekají a vyžadují zdroje v kruhu
• Nenaplnění jakékoliv z těchto podmínek stačí na prevenci uváznutí

• Může nastat v databázi, kde jsou vkládány a mazány nové položky
• Jedna transakce pracuje s nějakou množinou entit, zatímco druhá transakce tuto množinu změní
• Může vést k nekonzistentní databázi
• Může nastat i při striktním dvoufázovém zamykání