Zkouška: kartičky | databazove-systemy

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$

Relační algebra

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

Relační algebra

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^+$ $X^{+}$ množiny atributů $X$ $X$ podle množiny funkčních závislostí $F$ $F$ = všechny atributy, které jsou funkčně závislé na $X$ $X$ podle $F$ $F$
    - jejich závislost lze odvodit pomocí Armstrongových axiomů
- 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í

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

nalezení klíčů

terminologie
- množinu všech atributů označíme $A$
- nadklíč $X$ je taková množina atributů, že $X^+=A$
- klíč $K$ $K$ je taková množina atributů, že $K$ $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$ $K^{'} = (K \cup X) ∖ Y$ je nadklíč $R(A)$ $R (A)$ , neporovnatelný s $K$ $K$ inkluzí
  - ten musíme opět redukovat

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

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

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

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$ $X \to y$
  - relaci rozdělím na dvě
  - jedna relace bude odpovídat $X\to y$
  - v druhé bude vše kromě $y$ $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$ $a \to b$ , $b → c$ $b \to c$ , $c → d$ $c \to d$ , $d → e$ $d \to 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$ $b \to c$ přihodíme i ostatní atributy, které na $b$ $b$ závisí
  - tedy nebudeme dělit podle závislosti $b\to c$ $b \to c$ , ale podle $b\to b^+\setminus\set{b}$ $b \to b^{+} ∖ {b}$ , což je $b\to cde$ $b \to c d e$
    - 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í

Transakce

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

Transakce

konfliktní uspořádatelnost

konfliktní dvojice: $W(A)\to W(A)$ $W (A) \to W (A)$ , $R(A)\to W(A)$ $R (A) \to W (A)$ , $W(A)\to R(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ý

Transakce

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

Transakce

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$

Transakce

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é

Transakce

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ý

Transakce

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

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)

Teorie

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))$ $δ (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)\|}$ $\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

Teorie

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

Teorie

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

Teorie

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é

Teorie

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)

Teorie

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

Teorie

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

Teorie

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í)

Teorie

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

Teorie

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ů

Teorie

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í)

Teorie

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ý