Okruhy na zkoušku z databázových systémů - DBI025
Rozšíření poznámek od skywalker#4369
Relační algebra
Řešení zkoušky
Relační algebra (Lecture 6)
pro RA máme tyto operace
operace | symboly |
---|---|
množinové | |
projekce | |
selekce | |
spojení | |
přejmenování | |
dělení |
operace dělení nemá přímo svojí alternativu v SQL, většinou se použije pokud hledáme nějaké "všechny" výsledkem je největší relace t.ž.
příklad je lepší: ? Jména kin, kde promítli všechny filmy od Camerona ? (výsledek obsahuje pouze [J])
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.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:
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} | |
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} | |
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)
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