# Zkouška

u zkoušky se rovněž může objevit učivo ze zápočtového testu (SQL, UML, ER)

## Relační algebra

- operace
	- množinové $R\cup S,\;R\cap S,\;R\setminus S,\; R\times S$
	- selekce $R(\text{cond})$
	- projekce $R[\text{attr1},\text{attr2}]$
	- spojení $R[\text{cond}]S$
	- přirozené spojení $R*S$
	- přejmenování $R\braket{\text{attr1}\to\text{x1},\text{attr2}\to\text{x2}}$
	- dělení $R\div S$
- přirozené spojení
	- spojení na základě atributů se stejným názvem v obou tabulkách
	- pokud ho chceme použít na dvě stejné tabulky, je potřeba rozumně použít projekci
- dělení
	- vrací největší možný výsledek takový, aby jeho kartézský součin s dělitelem byl „podmnožinou“ dělence
	- příklad
		- $A$ … tabulka s dvojicemi (film, herec)
		- $B$ … tabulka se jmény herců
		- $A \div B$ … tabulka s názvy takových filmů, v nichž hrají všichni herci s tabulky B

## Normální formy a funkční závislosti

- funkční závislosti
	- rozepsání na elementární závislosti
		- tak, aby byl jeden atribut na pravé straně
		- závislosti s více atributy vpravo prostě „rozepíšu“
	- redukce redundantních atributů
		- máme závislosti, kde vpravo je jeden atribut, vlevo jich ale může být více
		- jsou všechny atributy vlevo potřeba?
			- pokud odeberu určitý atribut z levé strany, bude výsledná funkční závislost součástí uzávěru?
			- uzávěr $X^+$ množiny atributů $X$ podle množiny funkčních závislostí $F$ = všechny atributy, které jsou funkčně závislé na $X$ podle $F$
				- jejich závislost lze odvodit pomocí [Armstrongových axiomů](https://en.wikipedia.org/wiki/Armstrong%27s_axioms)
		- jinými slovy
			- máme $X\to y$, uvažujeme o odebrání atributu $a\in X$
			- $a$ můžeme odebrat, pokud $y\in (X\setminus\set{a})^+$ podle $F$
	- odstranění redundantních závislostí
		- závislost je redundantní, pokud může být odvozena z ostatních
		- takto testujeme každou závislost – vyjmeme ji a zkoušíme, zda ji lze odvodit z ostatních závislostí
		- závislost $X\to y$ můžeme odebrat, pokud $y\in X^+$ podle $F\setminus\set{X\to y}$
	- po postupné aplikaci těchto tří kroků (rozepsání, redukce atributů, odstranění závislostí) bychom měli získat minimální pokrytí množiny funkčních závislostí
- nalezení klíčů
	- terminologie
		- množinu všech atributů označíme $A$
		- nadklíč $X$ je taková množina atributů, že $X^+=A$
		- klíč $K$ je taková množina atributů, že $K$ je redukovaný superklíč
			- takových klíčů může být více
	- nalezení 1\. klíče
		- uvažujeme funkční závislost $A\to A$, kde $A$ je množina všech atributů
		- použijeme algoritmus redukce redundantních atributů
	- nalezení dalších klíčů
		- máme známý klíč $K$ a závislost $X\to Y$ takovou, že průnik $K\cap Y$ je neprázdný a $X\not\subseteq K$ (tedy $X$ obsahuje nějaké atributy navíc)
		- pak $K'=(K\cup X)\setminus Y$ je nadklíč $R(A)$, neporovnatelný s $K$ inkluzí
			- ten musíme opět redukovat
- normální formy
	- 1NF (první normální forma)
		- všechny atributy jsou atomického typu (nejsou to seznamy, objekty apod.)
		- předpokládáme, že platí
	- 2NF
		- 1NF + neexistuje závislost neklíčového atributu na **části** klíče
	- 3NF
		- 1NF + neexistuje **tranzitivní** (nepřímá) závislost neklíčového atributu na klíči
		- alternativně: 1NF + každá závislost patří do jedné ze tří skupin:
			- triviální: nadmnožina → podmnožina
			- závislost na (nad)klíči
			- atribut vpravo je součástí nějakého klíče
	- BCNF (Boyceho–Coddova normální forma)
		- 1NF + každý atribut je přímo závislý na klíči
		- alternativně: dovoluje jen triviální závislosti a závislost na (nad)klíči
			- tedy je silnější než 3NF
- dekompozice
	- cíl: aby byl výsledek v 3NF nebo BCNF
	- možný postup dekompozice
		- vyberu první závislost, která brání normální formě $X\to y$
			- relaci rozdělím na dvě
			- jedna relace bude odpovídat $X\to y$
			- v druhé bude vše kromě $y$
				- místo závislostí $y\to *$ tam budou jejich tranzitivní alternativy $X\to *$
			- případně tento krok opakuju
		- bezztrátové spojení
			- pokud provádíme dekompozici relací podle funkčních závislostí, přirozeným spojením rozložených relací získáme původní relaci
		- ale může dojít ke ztrátě funkčních závislostí
			- např. v situaci $a → b$, $b → c$, $c → d$, $d → e$
				- pokud vyjmeme $b→c$, ztratí se závislost $c\to d$ (místo ní tam bude $b\to d$, což platí tranzitivně, ale už ne původní závislost)
			- mohli bychom přidat další tabulku se ztracenou závislostí
	- zachování závislostí při dělení podle normálních forem
		- řetízek funkčních závislostí $a\to b\to c\to d\to e$ jsme dělili od prostředka
		- mohli bychom ho ale dělit od kraje, tak se nám žádná závislost neztratí
		- idea: do tabulky pro závislost $b\to c$ přihodíme i ostatní atributy, které na $b$ závisí
			- tedy nebudeme dělit podle závislosti $b\to c$, ale podle $b\to b^+\setminus\set{b}$, což je $b\to cde$
				- dojde k rozdělení na $R_1(b,c,d,e)$ a $R_2(a,b)$
				- v další iteraci bychom $R_1$ rozdělili na $cde,bc$, potom $de,cd$
				- řetízek závislostí dělíme od kraje
			- obecně pokud závislost $X\to Y$ porušuje NF, pak dělíme podle $X\to X^+\setminus X$

## Transakce

- transakce
	- časová posloupnost operací, která končí příkazem commit nebo abort
	- plánovač zpracovává několik transakcí najednou – řídí, jaká operace se provede dřív
	- rozvrh = pořadí provedení operací
- uspořádatelnost rozvrhu
	- sériový rozvrh – transakce (jejich operace) se provádějí postupně, pro $n$ transakcí existuje $n!$ sériových rozvrhů
	- pro zvýšení efektivity dává smysl střídavě provádět operace z různých transakcí
		- ale prolínání nemůže být libovolné – u dvojic s alespoň jedním zápisem závisí na pořadí operací (dvojice read/read může být v libovolném pořadí)
	- rozvrh je uspořádatelný (serializable), pokud je ekvivalentní libovolnému sériovému rozvrhu
- konfliktní uspořádatelnost
	- konfliktní dvojice: $W(A)\to W(A)$, $R(A)\to W(A)$, $W(A)\to R(A)$
		- operace jsou v různých transakcích
		- šipka odpovídá časové posloupnosti
	- dva rozvrhy jsou konfliktně ekvivalentní, pokud mají stejnou množinu konfliktních dvojic
	- rozvrh je konfliktně uspořádatelný, pokud je konfliktně ekvivalentní nějakému sériovému rozvrhu
	- konfliktní uspořádatelnost nezohledňuje zotavitelnost (abort/rollback) ani insert/delete na databázových objektech
	- detekce konfliktní uspořádatelnosti – pomocí precedenčního grafu
		- vrcholy jsou commitnuté transakce
		- orientované hrany odpovídají konfliktním dvojicím
		- rozvrh je konfliktně uspořádatelný, pokud je graf acyklický
- pohledová uspořádatelnost
	- slabší než konfliktní uspořádatelnost
		- využíváme zde toho, že pokud do konkrétní položky $n$-krát zapisujeme (kde $n\geq 3$) a mezi těmito zápisy ji nečteme, můžeme prvních $n-1$ zápisů provést v libovolném pořadí
	- dva rozvrhy jsou pohledově ekvivalentní pokud platí tyto 3 podmínky:
		- pokud operace $O$ čte počáteční hodnotu $X$ v jednom rozvrhu, platí to i ve druhém
		- pokud operace $O$ zapisuje koncovou hodnotu $X$ v jednom rozvrhu, platí to i ve druhém
		- pokud operace $O_1$ čte $X$ zapsané operací $O_2$, platí to i ve druhém
	- pohledově uspořádatelný rozvrh je pohledově ekvivalentní nějakému sériovému rozvrhu
- zotavitelnost
	- ze všech konfliktních dvojic vyznačíme ty, kde dochází ke čtení nepotvrzených dat
		- poznámka: pokud k jednomu čtení vede („konfliktní“) šipka ze dvou zápisů,  „zotavitelná“ šipka bude jen z toho posledního (protože to jsou ta nepotvrzená data, která se reálně čtou)
	- tak vznikne graf (snad acyklický), který určuje pořadí commitů a případně abortů
	- v zotavitelném rozvrhu může transakce, která četla $X$, commitnout až po commitu transakce, která zapisovala $X$
- zamykací protokol
	- operace
		- $S(A)$ … zamčení sdíleného zámku
		- $X(A)$ … zamčení exkluzivního zámku
		- $U(A)$ … odemčení zámku
	- dobrá formovanost transakcí
		- před $R$ aspoň $S$
		- před $W$ aspoň $X$
		- na konci vše korektně odemknuté
- 2PL (2fázový zamykací protokol)
	- po prvním unlocku už se nesmí zamykat → nejdřív se zamyká, pak se odemyká
	- každý vyhovující rozvrh je konfliktně uspořádatelný, nemusí být zotavitelný
- S2PL (striktní 2fázový zamykací protokol)
	- explicitní unlock je zakázaný
	- odemčení probíhají implicitně s commit/abort
	- je zotavitelný
	- ale může nastat deadlock (to plánovač detekuje, algoritmus opět hledá cykly v grafu závislostí)

## Teorie

### Multimédia

- Popište naivní způsob, jak rozšířit Tabulku pro potřeby hledání v obrázcích. Jaké jsou možnosti a omezení tohoto přístupu?
	- můžeme přidat sloupec, kde budou pro každý obrázek vypsány detekované objekty na obrázku
	- některé objekty klasifikátor nezná nebo je naopak uživatel neumí popsat slovy
	- nalezených výsledků může být hodně (příklad: na všech obrázcích je daný objekt, záleží na jeho vlastnostech)
- Definujte klasický podobnostní model pro dva obrázky, vysvětlete z jakých funkcí se skládá. Na „toy example” ukažte princip hledání v DB, kde je 5 obrázků.
	- spočítáme skóre (vzdálenost) $\delta(f_e(I_q),f_e(I_o))$
		- $\delta$ … skóre
		- $f_e$ … feature extraction
		- $I_q$ … požadovaný obrázek (query)
		- $I_o$ … jeden obrázek z databáze (postupně počítáme skóre pro každý obrázek z databáze)
	- vrátíme obrázky s nejmenší $\delta$
		- $\delta$ může být vzdálenost/metrika → Euklidovská, Manhattanská…
	- dá se taky použít kosinová podobnost … $\frac{f_e(I_q)\cdot f_e(I_o)}{\|f_e(I_q)\|\cdot \|f_e(I_o)\|}$
		- tenhle zlomek se rovná $\cos(\alpha)$, kde $\alpha$ je úhel vektorů $f_e(I_q),f_e(I_o)$
		- obrázky jsou stejné → +1
		- obrázky jsou úplně odlišné → –1
		- takže tady budeme naopak maximalizovat
- Definujte moderní podobnostní model pro text a obrázek, vysvětlete z jakých funkcí se skládá. Na „toy example” ukažte princip hledání v DB, kde je 5 obrázků.
	- pro obrázek použijeme feature extraction
	- pro text použijeme embedding
	- tím dostaneme dva vektory, této dvojici už můžeme přiřadit skóre
- Popište Bayesovský model pro hledání za pomocí zpětné vazby. Popište všechny kroky jedné iterace.
	- obrázky reprezentujeme jako vektory (jejich vzdálenost)
	- vybereme vzorek, který dostatečně pokrývá množinu obrázku, v níž chceme vyhledávat
	- uživatel ze vzorku vybere obrázek, který nejlépe odpovídá tomu, co hledá
	- tak můžeme zmenšit množinu obrázků, v níž vyhledáváme, a proces opakovat

### Moderní DB systémy

- Popište limity relačního modelu pro Big Data, které jsou popsány v přednášce.
	- **škálovatelnost**
	- vendor lock-in u vertikálního škálování
	- síťové problémy u horizontálního škálování
	- joiny a referenční integrita můžou být problematické
- Key-value – popište model, jaké podporuje základní funkce, názvosloví tabulek atp. v Riak, na jaké úkoly je model vhodný a na jaké ne.
	- jako tabulka v relační databázi se sloupci *klíč* a *hodnota*
	- operace: get, put, delete
	- Riak ekvivalenty pro pojmy z relačních databází
		- database instance … Riak cluster
		- table … bucket
			- je to vlastně jmenný prostor pro klíče
		- row … key-value
		- row id … key
	- úlohy: relace (sessions), uživatelské profily a preference, nákupní košík
	- antiúlohy: libovolné vyhledávání, hromadné operace, vztahy mezi daty, provádění více provázaných operací najednou (transakce)
- Column-family – popište model, jaké podporuje základní funkce, názvosloví tabulek atp. v Cassandra, na jaké úkoly je model vhodný a na jaké ne.
	- struktura
		- column family obsahuje řádky (je to kolekce *podobných* řádků)
		- každý řádek má klíč, dále obsahuje sloupce
		- sloupce můžou mít různou interní strukturu
	- Cassandra názvosloví
		- database instance … Cassandra cluster
		- database … keyspace
		- table … column family
		- row … row
		- column (stejný pro všechny řádky) … column (můžou být různé)
	- Cassandra column-families
		- statické – jako relační databáze, každý řádek používá podmnožinu fixní množiny sloupců
		- dynamické – připravené (předpočítané) výsledky dotazů, řádek odpovídá snapshotu dat pro určitý dotaz → každý řádek je pak vlastně sám o sobě seznamem
	- nejsou podporované joiny ani žádné složité dotazy, column-family databáze nesplňují pravidla ACID
	- úlohy: logování, CMS, blogovací platformy
- Document DB – popište model, jaké podporuje základní funkce, názvosloví tabulek atp. v MongoDB, na jaké úkoly je model vhodný a na jaké ne.
	- struktura: key-value, akorát value je JSON (nebo XML…), takže se s hodnotou dá lépe pracovat (stavět indexy apod.)
	- MongoDB názvosloví
		- database instance … MongoDB instance
		- schema … database
		- table … collection
		- row … document
		- row id … \_id
		- join … DBRef
	- úlohy: logování, CMS, blogy, webová/real-time analytika, e-commerce platformy
	- antiúlohy: komplexní transakce s různými operacemi, dotazy s měnící se strukturou agregace
- Graph DB – popište model, jaké podporuje základní funkce, na jaké úkoly je model vhodný a na jaké ne.
	- struktura
		- vrcholy – instance objektů, mají vlastnosti
		- hrany – mají orientaci a typy
	- v relačních databázích obvykle v jedné tabulce reprezentujeme jen jednu vazbu (hranu), tady jich můžeme reprezentovat kolik chceme
	- funkce: přidávání hran a vrcholů, hledání vrcholů, *hledání cest*
	- úlohy: propojená data (sociální sítě apod.), plánování, hledání cest apod. (polohová data), recommendation engines (doporučování podle preferencí přátel…)
	- antiúlohy: hromadné změny dat, velké množství dat (grafová data se špatně distribuují)

### Datové struktury a optimalizace

- Nad jakými sloupci je vhodné vytvořit index založený na $B^+$-stromu / bitmapách? Uveďte příklad.
	- sloupec s mnoha různými hodnotami → $B^+$-strom
	- sloupec s malou variabilitou hodnot (např. boolean) → bitmapa
- Popište změny v rychlosti databázových operací nad tabulkou po vytvoření (no)clusterovaného indexu nad nějakým sloupcem.
	- lineární operace se zrychlí na logaritmické
	- ale může být nutné sekvenčně projít několik bloků
- Popište hlavní rozdíly mezi clusterovaným a neclusterovaným indexem.
	- clusterovaný index jako položky obsahuje odkazy na jednotlivé bloky
	- index může být clusterovaný v situaci, kdy každý blok obsahuje právě položky z konkrétního rozsahu hodnot (a rozsahy na sebe navazují)
- Popište (ne)výhody použití tříděného souboru oproti souboru netříděnému (heap-file) z hlediska rychlosti DB operací pro ukládání záznamů tabulky.
	- lineární operace se zrychlí na logaritmické, ale může být nutné sekvenčně projít několik bloků
	- vkládání se zpomalí z konstantního času na logaritmický