The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b0b36dbs [2025/06/04 22:20] – [Normální formy] zapleka3statnice:bakalar:b0b36dbs [2025/06/14 21:53] (current) – [Transformace ER schématu do relačního schématu] prokop
Line 1: Line 1:
-==== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, objektově-relační mapování, noSQL databáze. ====+====== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, objektově-relační mapování, noSQL databáze. ======
  
 [[https://fel.cvut.cz/cz/education/bk/predmety/50/10/p5010606.html|B0B36DBS]] [[https://www.ksi.mff.cuni.cz/~svoboda/courses/202-B0B36DBS/|Webové stránky předmětu]] [[https://fel.cvut.cz/cz/education/bk/predmety/50/10/p5010606.html|B0B36DBS]] [[https://www.ksi.mff.cuni.cz/~svoboda/courses/202-B0B36DBS/|Webové stránky předmětu]]
Line 88: Line 88:
   * Operace: prohledávání grafu, porovnávání vzorů, grafové algoritmy.   * Operace: prohledávání grafu, porovnávání vzorů, grafové algoritmy.
   * Použití např.: RDF, FlockDB, sociální sítě.   * Použití např.: RDF, FlockDB, sociální sítě.
 +
 +==== Relační model ====
 +
 +=== Definice ===
 +  * Relační model je **teoretický základ relačních databází**.
 +  * Informace jsou uloženy v **relacích** (tabulkách), kde:
 +    * **relace** = množina n-tic (řádků),
 +    * **atribut** = sloupec tabulky,
 +    * každá relace má svůj **název** a **schéma** (atributy a jejich domény).
 +
 +  * Relace je matematicky definována jako **množina** (žádné duplicitní řádky).
 +
 +=== Klíč (Key) ===
 +  * Klíč je **množina atributů**, která **jednoznačně identifikuje každý řádek** (n-tici) v relaci.
 +  * Pokud existuje více klíčů, označujeme jeden jako **primární klíč** (primary key).
 +  * Klíč musí být **minimální** – žádný jeho podmnožinový soubor nesmí být klíčem.
 +
 +=== Nadklíč (Superkey) ===
 +  * Nadklíč je **množina atributů, která jednoznačně identifikuje řádky**, ale **nemusí být minimální**.
 +  * Každý **klíč je zároveň nadklíč**, ale ne každý nadklíč je klíč.
 +  
 +  * Příklad:
 +    * Uživatel(ID, jméno, e-mail)
 +    * Nadklíč: {ID, jméno}, {ID, e-mail}, {ID, jméno, e-mail}
 +    * Klíč: {ID}
 +
 +=== Cizí klíč (Foreign Key) ===
 +  * Cizí klíč je **atribut (nebo více atributů)**, který odkazuje na **primární klíč jiné relace**.
 +  * Zajišťuje **referenční integritu** mezi dvěma tabulkami.
 +  * Při vkládání nebo mazání hodnot musí být zachována návaznost mezi tabulkami.
 +
 +  * Příklad:
 +    * Tabulka `Objednávka`(ID, zákazník_id)
 +    * `zákazník_id` je cizí klíč do `Zákazník`(ID)
 +
  
 ==== Transformace ER schématu do relačního schématu ==== ==== Transformace ER schématu do relačního schématu ====
Line 360: Line 395:
 ==== Lucchesi-Osbornův algoritmus ==== ==== Lucchesi-Osbornův algoritmus ====
   * Algoritmus k nalezení **všech** klíčů relačního schématu.   * Algoritmus k nalezení **všech** klíčů relačního schématu.
-  1. Najdeme jakýkoliv klíč `K`. +  - Najdeme jakýkoliv klíč `K`. 
-  2. Vybereme funkční závislost `X → y` z `F` takovou, že `y ∈ K`, nebo ukončíme algoritmus pokud taková neexistuje. +  - Vybereme funkční závislost `X → y` z `F` takovou, že `y ∈ K`, nebo ukončíme algoritmus pokud taková neexistuje. 
-  3. Vytvoříme množinu `K' = X ∪ (K \ {y})`. +  - Vytvoříme množinu `K' = X ∪ (K \ {y})`. 
      * Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč.      * Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč.
-  4. Redukujeme levostranné atributy závislosti `K' → A`, a získáme nový **minimální** klíč `K'`. +  -  Redukujeme levostranné atributy závislosti `K' → A`, a získáme nový **minimální** klíč `K'`. 
-  5. Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2. +  - Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2. 
-  6. Pokud už existuje, algoritmus končí.+  - Pokud už existuje, algoritmus končí.
  
 ==== Normální formy ==== ==== Normální formy ====
Line 441: Line 476:
  
 ==== Transakční zpracování ==== ==== Transakční zpracování ====
-<markdown> +  * Transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data. 
-- transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data. +  * Transakce pracuje s konzistentní databází. 
-- Transakce pracuje s konzistentní databází. +  * Během spouštění transakce může být databáze v nekonzistentním stavu. 
-- Během spouštění transakce může být databáze v nekonzistentním stavu. +  * Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní. 
-- Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní. +  * Dva hlavní problémy:  
-- Dva hlavní problémy:  +    * Různé výpadky (např. chyba hardware nebo pád systému) 
- - Různé výpadky, např. chyba hardware nebo pád systému +    * Souběžné spouštění více transakcí 
- - Souběžné spouštění více transakci +
-</markdown>+
 ==== ACID vlastnosti ==== ==== ACID vlastnosti ====
-<markdown> +  * K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit: 
-- K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit: +    * **A**tomicity – transakce je atomická: buď se provede celá, nebo vůbec. 
- - **A**tomicity : transakce atomická - buď se podaří a provede se celá nebo nic. Nelze vykonat jen část transakce. +    * **C**onsistency – transakce zachovává konzistenci dat a integritní omezení. 
- - **C**onsistency : transakce - konkrétní transformace stavu, zachování invariant - integritní omezení. +    * **I**solation – transakce se navzájem neovlivňují (jako by běžely sériově). 
- - **I**solation : (isolace = serializovatelnost). I když jsou transakce vykonány zároveň, tak výsledek je stejný. jako by byly vykonány jedna po druhé. +    * **D**urability – po COMMIT jsou změny trvalé, přežijí i pád systému.
- - **D**urability : po úspěšném vykonání transakce (commit) jsou změny stavu databáze trvalé a to i v případě poruchy systému - zotavení chyb.+
  
-</markdown> 
 ==== Akce ==== ==== Akce ====
-<markdown> +  * **Akce na objektech:** `READ`, `WRITE`, `XLOCK`, `SLOCK`, `UNLOCK` 
-- **akce na objektech :** READ, WRITE, XLOCK, SLOCK, UNLOCK +  * **Globální akce:** `BEGIN`, `COMMIT`, `ROLLBACK` 
-- **akce globální :** BEGIN, COMMIT, ROLLBACK +
-</markdown>+
 ==== Transakční historie ==== ==== Transakční historie ====
-<markdown> +  * Posloupnost akcí několika transakcí, zachovávající jejich lokální pořadí. 
-- Posloupnost akcí několika transakcí, jež zachovává pořadí akcí, v němž byly prováděny +  * Historie (rozvrh) je **sériová**, pokud transakce probíhají jedna po druhé (žádné prokládání operací). 
-- Historie (rozvrh) se nazývá *sériová*, pokud jsou všechny kroky jedné transakce provedeny před všemi kroky druhé transakce. +
-</markdown>+
 ==== Serializovatelnost ==== ==== Serializovatelnost ====
-<markdown> +  * Teorie: transakce se skládají z akcí typu: 
-- Teorie: Nechť se transakce $T$ i skládá z následujících elementárních akcí: +    * `READ_i(A)` – čtení objektu `A` v transakci `T_i` 
- - $\mathrm{READ}_i(A)$ - čtení objektu $A$ v rámci transakce $T_i$ +    * `WRITE_i(A)` – zápis objektu `A` v transakci `T_i` 
- - $\mathrm{WRITE}_i(A)$ - zápis (přepis) objektu $A$ v rámci transakce $T_i$ +    * `ROLLBACK_i` – přerušení transakce `T_i` 
- - $\mathrm{ROLLBACK}_i(A)$ - přerušení transakce $T_i$ +    * `COMMIT_i` – potvrzení transakce `T_i`
- - $\mathrm{COMMIT}_i(A)$ - potvrzení transakce $T_i$ +
-- Jsou možné 4 případy:+
  
 +<markdown>
 |   |   |   | |   |   |   |
 |---|---|---| |---|---|---|
Line 485: Line 514:
 |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam| |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
 </markdown> </markdown>
 +
 ==== Konflikty ==== ==== Konflikty ====
-<markdown> +  * **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data. 
-- *WR konflikt* - jedna transakce data zapíše, druhá je čte předtím než byla commited, tzv. *dirty read* +  * **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí. 
-- *RW konflikt* - transakce čte data a druhá je zapíše předtím než byla ta první ukončena, tzv. *unrepeatable read* +  * **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace. 
-- *WW konflikt* - přepis dat, která ještě nebyla commited, tzv. *blind write* +  * **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry. 
-- Dvě historie jsou *konfliktově ekvivalentní*, pokud sdílí stejné konfliktní páry +  * **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií. 
-- Historie je *konfliktově uspořádatelná*, pokud je konfliktově ekvivalentní s nějakou sériovou historií +  * **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty. 
-- *Precedenční graf* je směrový graf, kde vrcholy jsou transakce a hrany jsou konfliktní páry mezi transakcemi +    * Pokud je **acyklický**, historie je serializovatelná. 
- - Pokud je acyklický, je historie sériově uspořádatelná +
-</markdown>+
 ==== Zamykání ==== ==== Zamykání ====
-<markdown> +  * Způsob **pesimistické kontroly souběhu** pomocí zámků. 
-- Způsob tzv. *pesimistické kontroly* v plánovači transakcí +  * **Zamykací protokol** zajišťuje konfliktní serializovatelnost. 
-- *Zamykací protokol* je protokol, který zamyká entity tak, aby byla zabezpečena konfliktní serializovatelnost +  * Typy zámků: 
-- Dva druhy zámků +    * **XLOCK (exkluzivní zámek)** – pouze pro jednu transakci, umožňuje zápis a čtení. 
- - *Exkluzivní zámek* $X(A)$ je zámek, který může držet pouze jedna transakce, pouze transakce, která drží zámek $X(A)$, pak může přistupovat k entitě $A$ +    * **SLOCK (sdílený zámek)** – umožňuje více transakcím číst. 
- - *Sdílený zámek* $S(A)$ je zámek, který může být držen více transakcemi, ale umožňuje pouze zápis, nikoliv čtení +    * **UNLOCK** – uvolnění zámku. 
-- Navíc je definována operace odemykání $U(A)$ +
-</markdown>+
 ==== Dvoufázové zamykání (2PL) ==== ==== Dvoufázové zamykání (2PL) ====
-<markdown> +  * Transakce: 
-- Pokud transakce chce číst (zapisovat) entitu $A$, musí nejprve získat sdílený (exkluzivní) zámek na tuto entitu +    * Nejprve pouze **získává** zámky (růstová fáze). 
-- Transakce nesmí zažádat o zámek na entitu $A$ pokud jej předtím už uvolnila +    * Poté je **pouze uvolňuje** (klesající fáze). 
-- Zajišťuje acykličnost precedenčního grafu +  * Zajišťuje **serializovatelnost**, ale **nezajišťuje zotavitelnost** (možné kaskádové zrušení).
-- Nezajišťuje zotavitelnost (může se stále stát, že transakce uvolní všechny zámky, jiná po ní pokračuje a je ukončena a potom je první transakce přerušena) +
-</markdown>+
  
 === Striktní dvoufázové zamykání (Strict 2PL) === === Striktní dvoufázové zamykání (Strict 2PL) ===
-<markdown> +  * Všechny zámky jsou **drženy až do COMMIT/ROLLBACK**. 
-- Zajišťuje zotavitelnost a kaskádovité přerušování +  * Zajišťuje zotavitelnost i prevenci kaskádového přerušení. 
-- Všechny zámky může transakce pustit až poté co je ukončena + 
-</markdown> +==== Uváznutí (Deadlock) ==== 
-==== Uváznutí (deadlock) ==== +  * Nastane, když každá transakce čeká na zámek držený jinou transakcí. 
-<markdown> +  * Reprezentace pomocí **grafu čekání**: 
-- Situace, která nastane, když všechny transakce čekají až jiná transakce uvolní zámek +    * Vrcholy: transakce 
-- Lze identifikovat pomocí tzv. *grafu čekání* +    * Hrana `T₁ → T₂`: `T₁` čeká na zámek držený `T₂` 
- - Vrcholy jsou jednotlivé transakce +    * **Cyklus = deadlock** 
- - Hrana z $T_1$ do $T_2$ říká, že transakce $T_1$ čeká až $T_2$ uvolní zámek + 
- - Pokud je v grafu cyklus, došlo k uváznutí +=== Metody prevence a řešení uváznutí === 
-</markdown> +  * **Detekce:** pomocí grafu čekání, přeruší se jedna transakce. 
-=== Metody prevence/řešení uváznutí === +  * **Prevence:** 
-<markdown> +    * **Wait-Die:** starší čeká, mladší umírá (rollback). 
-- Přerušení transakce a restart +    * **Wound-Wait:** starší zabije mladší, jinak čeká. 
-- Detekce uváznutí pomocí grafu čekání a přerušení transakce na základě nějakého kritéria (například transakce, která vykonala nejméně práce) +  * **Strategie výběru oběti:** přeruší se transakce podle délky běhu, počtu zámků apod. 
-- Dvě strategie na předcházení uváznutí, využívá priority transakcí: +
- - *wait-die* - pokud má čekající transakce vyšší prioritu tak čeká dále, pokud ne, tak je ukončena +
- - *wound-wait* - pokud má čekající transakce vyšší prioritu tak ukončí transakci, která drží zámek, který potřebuje, jinak čeká dále +
-</markdown>+
 === Coffmanovy podmínky === === Coffmanovy podmínky ===
-<markdown> +Uváznutí může nastat, pokud platí všechny 4 podmínky: 
-- K uváznutí může nastat pokud platí všechny z následujících podmínek +  - **Vzájemné vyloučení** – prostředky nejsou sdílené. 
-1. *Vzájemné vyloučení* - zdroje nejsou plně sdíleny a jsou drženy exkluzivně +  - **Zadržení a čekání** – proces drží a zároveň žádá další. 
-2. *Držení zdrojů* - další zdroje mohou být vyžadovány i když už jsou jiné drženy +  - **Žádná preempce** – prostředky nejsou vynuceně odebrány. 
-3. *Žádná preempce* - zdroje mohou být vypuštěny pouze dobrovolně +  - **Kruhové čekání** – cyklická závislost v čekání. 
-4. *Kruhové čekání* - transakce čekají a vyžadují zdroje v kruhu +  * Pokud **aspoň jedna podmínka neplatí**, uváznutí nemůže nastat. 
-- Nenaplnění jakékoliv z těchto podmínek stačí na prevenci uváznutí +
-</markdown>+
 ==== Fantom ==== ==== Fantom ====
-<markdown> +  * Specifický problém u transakcí s dotazy přes množiny záznamů. 
-- Může nastat v databázi, kde jsou vkládány a mazány nové položky +  * Jedna transakce čte množinu řádků podle podmínky (např. WHERE cena < 1000). 
-- Jedna transakce pracuje s nějakou množinou entit, zatímco druhá transakce tuto množinu změní +  * Jiná transakce mezitím přidá nový záznam, který podmínce odpovídá. 
-- Může vést k nekonzistentní databázi +  * První transakce je **ovlivněna novým záznamem**, i když už měla dané zámky. 
-- Může nastat i při striktním dvoufázovém zamykání +  * Řešení: **zámky na rozsah (range locks)** – např. pomocí indexových struktur. 
-</markdown>+

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b0b36dbs (generated for current page)