Summary: Pokus o sepsání témat ke zkoušce

Okruhy na zkoušku z databázových systémů - DBI025

Rozšíření poznámek od skywalker#4369

Relační algebra
Funkční závislosti
Transakce
Random

Stránka předmětu
Záznam cvik 2023
- 1. Relační algebra
- 1. Řešení zkoušky

Testy:

Relační algebra (Lecture 6)

Záznam cvik
pro RA máme tyto operace

operace	symboly
množinové	$∪,∩,−,×\cup ,\cap ,- ,\times$
projekce	$R [a, b, c, ...]$
selekce	$R (p o d m \overset{ı}{ˊ} nka)$
spojení	$R * S, R [p o d m \overset{ı}{ˊ} nka] S$
přejmenování	$R<a→x,b→y,...>R<a\rightarrow x, b\rightarrow y, ...>$
dělení	$R÷SR\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]÷S[B],B⊂AR[A]\div S[B], B \subset A$ výsledkem je největší relace $X [A - B]$ t.ž. $\times X \subseteq R$
příklad je lepší: $K in o (J m \overset{e}{ˊ} n o, M \overset{e}{ˇ} s t o, S e d a d e l), F i l m (N \overset{a}{ˊ} ze v, R e \overset{z}{ˇ} i s \overset{e}{ˊ} r, Z e m \overset{e}{ˇ}, C e na), P ro g r am (J m \overset{e}{ˊ} n o, N \overset{a}{ˊ} ze v, K d y, L \overset{ı}{ˊ} s t k y)$ ? Jména kin, kde promítli všechny filmy od Camerona ? $\div F(R='Cameron')[N] = X$ (výsledek obsahuje pouze [J]) $\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. zjednodušíme pravidla, zbavíme se atributů
  - 1.B. odstraníme funkční závislosti
- 2. Určení všech klíčů schématů
- 3. Určení, které FZ porušují 2NF, 3NF, BCNF (nejslabší z nich)
- 4. 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: $α⊂A:{α}+=A∧∀a∈α:{α−a}+≠A\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í neklíč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
  - pohledová uspořádatelnost
- zotavitelnost
- S2PL (strict two-phase locking protocol)
- 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