# Okruhy na zkoušku z databázových systémů - DBI025
*Rozšíření poznámek od skywalker#4369*

* [Relační algebra](#relační-algebra-lecture-6)
* [Funkční závislosti](#funkční-závislosti-lecture-7)
* [Transakce](#transakce-lecture-08)
* [Random](#random-lecture-09-11)

---
* [Stránka předmětu](https://www.ms.mff.cuni.cz/~kopecky/vyuka/dbs/)
* [Záznam cvik 2023](https://su.mff.cuni.cz/view/browse/home/kopeckm3/2023-2024-S1/NDBI025-DBS/Practicals)
	- 9. Relační algebra
	- 14. Řešení zkoušky

- Testy:
	- [Test A-5.1.23](https://www.ms.mff.cuni.cz/~kopecky/vyuka/dbs/siret.ms.mff.cuni.cz/skopal/databaze/zkouska_2023_01_05/A.pdf), [Solution A-5.1.23](https://www.ms.mff.cuni.cz/~kopecky/vyuka/dbs/siret.ms.mff.cuni.cz/skopal/databaze/zkouska_2023_01_05/A_solution.pdf)
	- [Test A-12.1.23](https://www.ms.mff.cuni.cz/~kopecky/vyuka/dbs/siret.ms.mff.cuni.cz/skopal/databaze/zkouska_2023_01_12/A.pdf)
	- [Test B-12.1.23](https://www.ms.mff.cuni.cz/~kopecky/vyuka/dbs/siret.ms.mff.cuni.cz/skopal/databaze/zkouska_2023_01_12/B.pdf)

---
## Relační algebra (Lecture 6)
- [Záznam cvik](https://su.mff.cuni.cz/file/home/kopeckm3/2023-2024-S1/NDBI025-DBS/Practicals/DBS-09-5-wed-1040-RA.mp4)
- pro RA máme tyto operace

| operace | symboly |
| - | - |
| množinové | $\cup ,\cap ,- ,\times $|
| projekce | $R[a, b, c, ...]$ |
| selekce | $R(podmínka)$ |
| spojení | $R*S, R[podmínka]S$ |
| přejmenování | $R<a\rightarrow x, b\rightarrow y, ...>$ |
| dělení | $R\div S$|

- operace dělení nemá přímo svojí alternativu v SQL, většinou se použije pokud hledáme nějaké "všechny"
$R[A]\div S[B], B \subset A$
výsledkem je *největší relace* $X[A-B]$ t.ž. $S \times X \subseteq R$ 
- příklad je lepší:
$Kino(Jméno, Město, Sedadel),Film(Název, Režisér, Země, Cena), Program(Jméno, Název, Kdy, Lístky)$
? Jména kin, kde promítli všechny filmy od Camerona ?
$P[J,N] \div F(R='Cameron')[N] = X$ (výsledek obsahuje pouze [J])
$F(R='Cameron') \times X \subseteq P[J,N] $

```
UČITEL(ID, Jméno, Titul), STUDENT(ID, Jméno, IDVedoucího), IDVedoucího < UČITEL.ID

1. Select * From UČITEL U Inner Join STUDENT S On (U.ID = S.IDVedoucího)
UČITEL[UČITEL.ID=STUDENT.IDVedoucího]STUDENT[UČITEL.ID,UČITEL.Jméno,UČITEL.Titul]
2. Select * From UČITEL U Where ID Not In (Select IDVedoucího From STUDENT)
UČITEL – (UČITEL[UČITEL.ID=STUDENT.IDVedoucího]STUDENT)[UČITEL.ID,UČITEL.Jméno,UČITEL.Titul]
3. Select IDVedoucího From STUDENT Group By IDVedoucího Having Count(*) > 1 
(STUDENT<ID->ID1,Jméno->Jméno1> * STUDENT<ID->ID2,Jméno->Jméno2>)(ID1≠ID2)[IDVedoucího]
```
```
PRODUKT(PID, Název, Váha), OBCHOD(OID, Adresa), PRODÁVÁ(PID, OID, Cena)

1. Select * From OBCHOD Inner Join PRODÁVÁ On (OID = OID) Where Cena<10
Dotaz je špatně, OID = OID !, ale jinak
(OBCHOD*PRODÁVÁ)(Cena<10)[OID, Adresa]
(OBCHOD[OBCHOD.OID=PRODÁVÁ.OID]PRODÁVÁ)(Cena<10)[OID,Adresa], je to to samé
2. Select * From PRODUKT P Where PID Not In (Select PID From PRODÁVÁ)
PRODUKT-(PRODUKT[PRODUKT.PID=PRODAVA.PID]PRODAVA)[PID, Název, Váha]
(PRODUKT[PID]-PRODÁVÁ[PID])*PRODUKT
3. Zapište dotaz bez operátoru dělení PRODÁVÁ[PID, OID] / OBCHOD[OID]
PRODÁVÁ[PID]-((PRODUKT[PID] X OBCHOD[OID] - PRODÁVÁ[PID, OID])[PID])
```
---
## Funkční závislosti (Lecture 7)
- Armstrongovy axiomy
- Pro analýzu funkčních závislostí máme tyto kroky:
	- [1.]() Nalezení minimálního pokrytí FZ
		- [1.A.](#1a-zbavíme-se-atributů-levých-stran) zjednodušíme pravidla, zbavíme se atributů
		- [1.B.](#1b-odstraníme-nadbytečné-redundantní-funkční-závislosti) odstraníme funkční závislosti
	- [2.](#2-určíme-všechny-klíče) Určení všech klíčů schématů
	- [3.](#3-určíme-v-jaké-nf-jsou-fz) Určení, které FZ porušují 2NF, 3NF, BCNF (nejslabší z nich)
	- [4.](#4-převod-na-3nf-nebo-bcnf) Převod na 3NF, nebo BCNF (dekompozice)

### 1.A. Zbavíme se atributů (levých stran)
- pro více-atributové FZ uděláme tranzitivní uzávěr pro jednotlivé atributy
- poté vidíme jaké atributy jsou nadbytečné (může nastat, že není jasné jakého se zbavit, mámě např. dvě možnosti, poté je jedno jaký vybereme)
```
FZ = {ab -> c, c -> d, e -> f, a -> bd}
? a->c:	{a}^+= {a, b, d, c}	=> a->c 
? b->c:	{b}^+= {b} 		≠> b->c 
```
### 1.B. Odstraníme nadbytečné (redundantní) funkční závislosti
- vlastně se zbavujeme pravých částí
- z množiny FZ odstraníme vyšetřovanou FZ a zkoušíme, jestli se lze dovodit stejný výsledek
```
FZ = {a -> c, c -> d, e -> f, a -> bd}
? F-{a->c}, dovodíme a->c, NE
? F-{c->d}, dovodíme c->d, NE
? F-{e->f}, dovodíme e->f, NE
? F-{a->d}, dovodíme a->d, {a}^+= {a, b, c, d} ANO
```
### 2. Určíme všechny klíče
- logická formule:
$\alpha \subset A: \{ \alpha \}^+=A \land \forall a \in \alpha : \{ \alpha - a\}^+ \neq A$
- začneme množinou všech atributů a poté se zbavíme všech "dovoditelných"
```
A = {A, B, C, D, E, F}
FZ = {a -> c, c -> d, e -> f, a -> b}

{A, B, C, D, E, F} 
{A, B, C, D, E,  } E -> F, ANO
{A, B, C, D, E,  } x -> E, NE
{A, B, C,  , E,  } C -> D, ANO
{A, B,  ,  , E,  } A -> C, ANO
{A, B,  ,  , E,  } A -> B, ANO
{A,  ,  ,  , E,  } x -> A, NE

Máme klíč K1 = {A, E}
------------------------------------------------
A = {A, B, C, D, E, F}
FZ = {a -> d, d -> f, d -> a, de -> c, bc -> a}

{A, B, C, D, E, F}
K1 = {B, C, E}
K2 = {B, D, E}
K3 = {B, A, E}
```

### 3. Určíme, v jaké NF jsou FZ
- máme 4 NF (normativní formy):
	- 1.NF
		- Vyžaduje, aby všechny atributy byly základních typů. Většinou se prostě předpokládá.
	- 2.NF
		- Vyžaduje 1. NF. Dále žádný neklíčový atribut nesmí záviset jen na části klíče (může však záviset na celém klíči).
		- *X část klíče -> neklíčový atribut*
	- 3.NF
		- 1.definice
			- Žádný neklíčový atribut není tranzitivně závislý na klíči.
			- *X klíč -> něco -> neklíčový atribut*
		- 2.definice (myslím si, že ta snažší ověřit)
			- Všechny funkční závislosti musí jít rozdělit do následujících 3. kategorií:
			- triviální (levá strana nadmnožina pravé strany)
			- nalevo klíč nebo nadklíč, napravo cokoli
			- nalevo cokoli, napravo něco co **není** **ne**klíčové
	- BCNF (Boyce-Codd)
		- Nejpřísnější, povoluje jen první dvě kategorie z 2. definice 3. NF, tedy jen
		- triviální (levá strana nadmnožina pravé strany)
		- nalevo klíč nebo nadklíč, napravo cokoli
```
A = {A, B, C, D, E, F}
FZ = {a -> c, c -> d, e -> f, a -> b}
K1 = {A, E}
a -> c, X 2.NF (X část klíče -> neklíčový atribut)
c -> d, X 3.NF (A -> c -> d)
e -> f, X 2.NF (X část klíče -> neklíčový atribut)
a -> b, X 2.NF (X část klíče -> neklíčový atribut)
```

### 4. Převod na 3NF, nebo BCNF
- nejspíš povede k nějaké ztrátě informací
- musíme množinu atributů rozložit
```
A = {A, B, C, D, E, F, G, H, K}
FZ = {ab -> c, c -> h, c -> k, h -> eg, k -> ab}
      X 4.NF   X 2.NF  X 4.NF  X 3.NF   X 4.NF
```
- převod na **3NF**, začneme h -> eg, jelikož eg není na levé straně nějaké FZ

| R | F | K | |
| - | - | - | - |
| HEG | h -> eg | {H} | 
| ~~ABCDFHK~~ | ~~ab -> c, ==c -> h==, c -> k, k -> ab~~ | 
| CH | c -> h | {C} | |
| ABCDFK | ab -> c, c -> k, k -> ab | {A,B,D,F} | X DSNF (na levé straně podklíč) |

- pro **DSNF** určitě něco ztratíme, IRL si vybereme to nejmíň důležité

| R | F | K | |
| - | - | - | - |
| HEG | h -> eg | {H} | 
| CH | c -> h | {C} | 
| CK | c -> k | {C} | 
| ~~ABCDF~~ | ~~ab -> c~~ | ~~{A,B,D,F}~~ | ~~X DSNF~~|
| ABC | ab -> c | {A,B} | 
| ABDF |  | {A,B,D,F} | ztratili jsme k -> ab|


---
## Transakce (Lecture 08)
- u transakcí určujeme jejich vlastnosti, tzv. ACID (Atomicity, Consistency, Isolation, Durability)
	- uspořádatelnost
		- [konfliktová uspořádatelnost](#1a-konfliktová-uspořádatelnost)
		- [pohledová uspořádatelnost](#1b-pohledová-uspořádatelnost)
	- zotavitelnost
		- [zotavitelnost](#2a-zotavitelnost)
		- [odolnost vůči kaskádovým abortům](#2b-odolnost-vůči-kaskádovým-abortům)
		- [striktnost](#2c-striktnost)
	- [S2PL](#3-2pl-two-phase-locking-protocol) (strict two-phase locking protocol)
	- [Deadlock](#4-deadlock) (možnost uváznutí)

### 1.A. Konfliktová uspořádatelnost
- uděláme si graf konfliktů (precedenční graf)
	- read-read 	– ok
	- write-read 	– reading uncommitted data
	- read-write 	– unrepeatable reading
	- write-write 	– overwrite of uncommitted data
- když je tam cyklus, tak to není konfliktově uspořádatelné
- pokud je to konfliktově uspořádatelné, tak je to i pohledově uspořádatelné

- alternativně se dá ověřit, jestli to je 2PL (protože to implikuje konfliktovou uspořádatelnost)

### 1.B. Pohledová uspořádatelnost
- aby bylo, tak musíme ověřit, jestli je to pohledově ekvivalentní nějakému sériovému plánu (operace T1, pak T2...)
- což znamená, že najdeme takový příklad sériového plánu:
	- initial read každé entity furt musí být initial
	- final write každé entity furt musí být final
	- kdykoli děláme read A, který čte hodnotu, kterou zapsal nějaký write, tak musí číst tu stejnou hodnotu i v tom ekvivalentním plánu

### 2.A. Zotavitelnost
- všechny transakce ovlivňující (měnící data, které čte) transakci T musely commitnout před tím, než commitne ona.

### 2.B. Odolnost vůči kaskádovým abortům
- čteme jen commited data

### 2.C. Striktnost
- přepisujeme jen commited data

### 3. 2PL? (two-phase locking protocol)
- zámky:
	- exkluzivní zámky
		- X(A), zamyká A tak, že čtení a zápis A je povolen pouze vlastníkovi/zakladateli zámku.
		- lze udělit pouze jedné transakci
	- sdílené zámky
		- S(A), povoleno pouze čtení A - vlastník zámku může číst a má jistotu, že A nemůže změnit
		- může být přidělen (sdílen více transakcemi) (pokud již nebyl přidělen X(A))
	- odemknutí zámku
		- U(A), odemyká A
- 2PL
	- k zámkům přidává ještě jednu podmínku
		- jakmile transakce něco odemkne, tak už nesmí nic zamykat
		- neboli nejdříve se zamyká a poté odemyká
	- když je něco 2PL, tak je to i:
		- konfliktově uspořádatelné
- S2PL
	- všechny zámky se uvolní na konci transakcí (změna oproti 2PL)
	- když je něco S2PL, tak je to i:
		- 2PL (tedy i konfliktově uspořádatelné)
		- zotavitelné
		- odolné vůči kaskádovým abortům

### 4. DEADLOCK?
- během provádění transakce se může stát, že transakce T1 požádá o zámek, který již byl přidělen transakci T2, 
- ale T2 jej nemůže uvolnit, protože čeká na další zámek, který si ponechává T1

---
## Random (Lecture 09-11)
- Lecture 9
	- multimedia retrieval
		- retrieval models
		- interactive search
- Lecture 10
	- modern database systems
	- Big Data
	- NoSQL databases
		- key/value databases
		- column (-family) databases
		- document databases
		- graph databases
	- NewSQL and Array databases
	- Multi-model databases
- Lecture 11
	- Implementation of database structures, optimization