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 [2026/06/16 21:50] (current) – [Boyce-Coddova normální forma (BCNF)] badinmic
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 430: Line 465:
     * Přísnější než 3NF – eliminují se i závislosti, kde `A` je klíčový atribut, ale `X` není superklíč.     * Přísnější než 3NF – eliminují se i závislosti, kde `A` je klíčový atribut, ale `X` není superklíč.
  
-  * Příklad porušení 3NF, které ještě **není** porušením BCNF:+  * Příklad porušení BCNF, které ještě **není** porušením 3NF:
     * Relace `{__StudentID__, CourseID, Instructor}`     * Relace `{__StudentID__, CourseID, Instructor}`
     * `CourseID` → `Instructor`     * `CourseID` → `Instructor`
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: • b0b33opt • b4b01num • b4b33alg • b4b36sin • be4m33ssu

Navigation

Playground

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