====== 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]]
* **Konceptuální modelování** – ER (entitní typy, atributy, identifikátory, vztahové typy, n-ární, rekurzivní, slabé entitní typy, ISA hierarchie). Logické modely (tabulkový, objektový, stromový, grafový). Relační model (definice, klíč, nadklíč, cizí klíč), transformace ER schématu do relačního schématu.
* **Relační databáze** – datový model, NULL hodnoty, tříhodnotová logika, integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a referenční akce), umělé identifikátory.
* **Jazyk SQL** – definice schématu. Manipulace s daty (SELECT, INSERT, UPDATE, DELETE). Spojování tabulek, predikáty, řazení, seskupování a agregace, množinové operace, vnořené dotazy. Pohledy (aktualizovatelnost, CHECK OPTION). Procedurální rozšíření (funkce, kurzory, triggery).
* **Fyzická vrstva** – bloky, sloty, buffer management. Organizace záznamů (halda, seřazený soubor, hašovaný soubor, složitost operací), indexové struktury (B+-stromy, hašované indexy, bitmapové indexy).
* **Funkční závislosti** – definice, Armstrongovy axiomy, úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, redukovaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).
* **Transakce** – základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh / historie, uspořádatelnost / serializovatelnost. Konfliktová uspořádatelnost (konflikty WR, RW, WW, precedenční graf), zamykací protokoly (dvoufázové a striktní dvoufázové zamykání), uváznutí (deadlock, graf čekání, Coffmanovy podmínky, strategie wait-die a wound-wait), fantom.
===== 1. Konceptuální modelování =====
**ER (entitní typy, atributy, identifikátory, vztahové typy, n-ární, rekurzivní, slabé entitní typy, ISA hierarchie). Logické modely (tabulkový, objektový, stromový, grafový). Relační model (definice, klíč, nadklíč, cizí klíč), transformace ER schématu do relačního schématu.**
ER modely se používají pro návrh databázové struktury na konceptuální úrovni. Slouží jako nástroj pro pochopení domény problému a pomáhají při návrhu databáze před implementací.
* **ER diagramy** – grafická reprezentace reálné struktury systému, pomáhají určit, co se má uložit v databázi.
* **ER (Entity-Relationship) model** – konceptuální model dat a vztahů mezi nimi.
* Pozor: neexistuje striktní standard notace, a proto může být reprezentace různá (často bývá nahrazen nebo doplněn o UML).
==== Entitní typy ====
Entita reprezentuje objekt reálného světa – např. osoba, projekt, dokument. V ER modelu má každá entita typ.
* **Silný entitní typ** – má alespoň jeden plný identifikátor (např. `projekt.nazev`)
* **Slabý entitní typ** – nemá vlastní plný identifikátor, identifikuje se pomocí vztahu k jiné entitě (má částečný identifikátor)
==== Atributy ====
* Vlastnosti entity – např. jméno, datum narození, adresa.
* Každý atribut má:
* název
* datový typ
* kardinalitu (kolik hodnot může obsahovat)
* **Složené atributy** – atribut obsahující další atributy (např. `adresa = [ulice, město, PSČ]`)
{{:statnice:bakalar:pasted:20250520-124031.png}}
==== Identifikátory ====
* Atribut nebo kombinace atributů, která jednoznačně určuje konkrétní entitu.
* Rozlišujeme:
* **Plné identifikátory** – skládají se z atributů dané entity
{{:statnice:bakalar:pasted:20250520-124044.png}}
* **Částečné identifikátory** – určují entitu až ve spojení s jinou entitou (např. číslo položky v objednávce)
{{:statnice:bakalar:pasted:20250520-124130.png}}
==== Vztahové typy ====
* Vztah mezi dvěma nebo více entitami.
* Mají název, zapojené entity a kardinality vztahů.
* Typy:
* **Binární vztah** – mezi dvěma entitami.
* **N-ární vztah** – mezi více než dvěma entitami (možno transformovat na binární vztahy přes pomocnou entitu).
* **Rekurzivní vztah** – entita je ve vztahu sama se sebou (např. zaměstnanec vede jiného zaměstnance).
{{:statnice:bakalar:pasted:20250520-125915.png}}
==== ISA hierarchie (is-a hierarchy) ====
* Hierarchické vztahy mezi entitami typu „je podtypem“ (specializace).
* Např. `Student` je podtypem `Osoba`.
* Vztah nemá název ani kardinalitu.
* Každý podtyp má maximálně jednoho rodiče (single inheritance).
{{:statnice:bakalar:pasted:20250520-130342.png}}
==== Logické modely ====
Převádějí konceptuální schéma do technicky orientované reprezentace podle toho, jak budou data uchovávána a dotazována.
* **Proces logického modelování**:
* Výběr vhodného modelu podle charakteru dat a požadavků na dotazování
* Transformace ER modelu do zvoleného logického modelu
=== Tabulkový model ===
* Struktura: tabulky – řádky reprezentují entity, sloupce atributy.
* Operace: výběr (selection), projekce (projection), spojení (join).
* Typický zástupce: **relační databáze (SQL)**
=== Objektový model ===
* Struktura: objekty s atributy, ukazatele mezi objekty.
* Operace: navigace pomocí referencí (např. `obj.adresa.mesto`).
* Používá se např. v objektových databázích.
=== Stromový model ===
* Struktura: uzly (vrcholy) s atributy, hrany jako vztahy.
* Hierarchická data – např. XML, JSON.
* Vhodné pro semi-strukturovaná data.
=== Grafový model ===
* Struktura: vrcholy, hrany, atributy (může být směrovaný či nesměrovaný).
* Operace: prohledávání grafu, porovnávání vzorů, grafové algoritmy.
* 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 ====
* Každý **entitní typ** → vlastní tabulka.
* Atributy entity se stanou sloupci tabulky.
* Primární identifikátor entity se použije jako **PRIMARY KEY**.
* Každý **slabý entitní typ** → vlastní tabulka.
* Její primární klíč se skládá z částečného identifikátoru + klíče silné entity.
* Vzniká zároveň **FOREIGN KEY** na silný entitní typ.
* **Vztahový typ**:
* **1:N** – cizí klíč přidán na stranu N.
* **M:N** – vytvoří se **nová tabulka**, která má cizí klíče na obě entity.
* **N-ární vztahy** – vytvoří se nová tabulka, která obsahuje cizí klíče na všechny zapojené entity.
* **ISA hierarchie**:
* Možnosti:
* 1 tabulka pro každou třídu (dědičnost přes cizí klíče),
* nebo 1 tabulka pro celou hierarchii (s NULLy pro nepoužité sloupce),
* nebo kombinace (tabulka pro základní typ a tabulky pro specializace).
===== 2. Relační databáze =====
**Datový model, NULL hodnoty, tříhodnotová logika, integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a referenční akce), umělé identifikátory.**
* **Databáze** – logicky uspořádaný soubor souvisejících dat. Obsahuje data, metadata, schéma, integritní omezení, apod.
* **DBMS (Database Management System)** – softwarový systém umožňující přístup do databáze. Zajišťuje:
* bezpečnost
* spolehlivost
* souběžnost
* integritu uložených dat
* **Databázový systém** – zahrnuje databázi, DBMS, hardware, procesy a uživatele.
* **Relační databáze** – množina **relací** (tabulek), každá tabulka odpovídá jedné množině n-tic.
==== NULL hodnoty ====
* Označují **neznámou nebo chybějící hodnotu**.
* V operacích se NULL chová podle **tříhodnotové logiky**:
* `3 + NULL → NULL`
* `3 < NULL → UNKNOWN`
* Výsledkem operací, které zahrnují NULL, může být právě `UNKNOWN`, což ovlivňuje výsledek výrazu (např. ve WHERE klauzulích).
==== Integritní omezení ====
* Zajišťují konzistenci a správnost dat v databázi.
* **Typy omezení:**
* **NOT NULL** – hodnota nesmí být NULL.
* **UNIQUE** – hodnota v daném sloupci musí být jedinečná.
* **PRIMARY KEY** – kombinace `NOT NULL` a `UNIQUE`. Sloupec (nebo kombinace sloupců) jednoznačně identifikuje řádek.
* **FOREIGN KEY** – hodnota musí odpovídat primárnímu klíči jiné tabulky.
* **CHECK** – definuje logickou podmínku, která musí být splněna.
* **Druhy integritních omezení podle významu:**
* **Entitní integrita** – každý řádek má unikátní a neprázdný primární klíč.
* **Doménová integrita** – hodnoty musí odpovídat deklarovaným datovým typům a omezením.
* **Referenční integrita** – vztah mezi dvěma tabulkami (pomocí cizích klíčů).
==== Referenční akce ====
Pokud by operace (např. smazání nebo změna klíče) v **odkazované tabulce** porušila integritu cizích klíčů v jiné tabulce, může být:
* **Zablokována** (výchozí chování), nebo
* **Zpracována pomocí referenčních akcí:**
* ON UPDATE / ON DELETE – určuje chování při změně/mazání klíče.
* Akce:
* **CASCADE** – změna/smazání se propaguje (změní/smaže i odpovídající řádky).
* **SET NULL** – odpovídající hodnota se nastaví na NULL.
* **SET DEFAULT** – nastaví se výchozí hodnota.
* **NO ACTION** – akce se **neprovede**, pokud by došlo k porušení integrity.
* **RESTRICT** – stejné jako NO ACTION, ale kontrola proběhne ihned.
==== Umělé identifikátory ====
* Automaticky generované identifikátory, často celočíselné.
* Obvykle využívají **sekvenci** (např. auto_increment nebo serial).
* Nový záznam získá ID větší než předchozí, čímž vzniká jednoznačný a jednoduše řaditelný klíč.
* Používají se, když přirozený klíč neexistuje nebo je příliš komplikovaný.
===== 3. Jazyk SQL =====
Structured Query Language (SQL) je jazyk pro práci s relačními databázemi. Obsahuje příkazy DDL (Data Definition Language) pro definici schémat, DML (Data Manipulation Language) pro manipulaci s daty a další. SQL je case-insensitive.
* Transaction management
* Administrace databáze
==== Definice schématu ====
* **CREATE TABLE** – vytvoření tabulky
* Název tabulky
* Definice sloupců (název, datový typ, výchozí hodnota)
* Integritní omezení (PRIMARY KEY, NOT NULL, ...)
* **ALTER TABLE** – úprava existující tabulky
* RENAME TO
* ADD COLUMN, ALTER COLUMN, DROP COLUMN
* ADD CONSTRAINT, DROP CONSTRAINT
* **DROP TABLE** – odstranění tabulky
==== Manipulace s daty (SELECT, INSERT, UPDATE, DELETE) ====
* **INSERT INTO** – vkládá nové řádky
* **UPDATE** – mění existující záznamy
* **MERGE** – kombinace INSERT a UPDATE podle klíče
* **DELETE FROM** – maže záznamy
* **SELECT** – dotazy nad daty
* SELECT *, nebo konkrétní sloupce
* AS pro aliasy
* ALL, DISTINCT
* FROM, WHERE (včetně predikátů: AND, OR, NOT)
* GROUP BY, HAVING
* ORDER BY
* **EXPLAIN** – ukáže plán vykonání dotazu
* **SHOW** – zobrazí informace o schématu nebo systému
==== Spojování tabulek ====
* **JOIN**
* CROSS JOIN – kartézský součin
* NATURAL JOIN – spojení na stejné názvy atributů
* INNER JOIN – spojení podle ON nebo USING
* LEFT / RIGHT / FULL OUTER JOIN – i neodpovídající řádky, doplněny NULL
* UNION JOIN – všechna data bez ohledu na spojení
==== Množinové operace ====
* UNION [ALL] – sjednocení výsledků
* INTERSECT – průnik výsledků
* EXCEPT / MINUS – rozdíl množin
* Operandy musí mít stejný počet a typ sloupců
==== Vnořené dotazy ====
* V řádcích (WHERE x IN (SELECT ...))
* V FROM – jako poddotazy („virtuální tabulky“)
* V SELECT – výpočet jedné hodnoty (SELECT (SELECT COUNT(*) ...))
* Korelované – vnořený dotaz závisí na vnějším (WHERE EXISTS (...))
==== Pohledy (views) ====
* CREATE VIEW jméno AS (SELECT …) – vytvoření
* Aktualizovatelnost – platí, pokud je view přímo z jedné tabulky, bez agregací a spojení
* WITH CHECK OPTION – zabrání UPDATE/INSERT, které by zneplatnily podmínky pohledu
==== Procedurální rozšíření SQL ====
* Funkce – vlastní výpočty, vrací skalární nebo tabulkový výsledek
* Kurzory – procházení záznamů jeden po druhém (např. DECLARE, FETCH, CLOSE)
* Triggery – automatické akce při změně dat (AFTER INSERT, BEFORE UPDATE, …)
===== 4. Fyzická vrstva =====
**Fyzická vrstva (bloky, sloty, buffer management). Organizace záznamů (halda, seřazený soubor, hašovaný soubor, složitost operací), indexové struktury (B⁺-stromy, hašované indexy, bitmapové indexy).**
* Specifikuje, jak jsou databázové struktury fyzicky uloženy a spravovány
* Zahrnuje: struktury na disku, indexy, správu stránek a mezipaměti
==== Stránky, sloty a záznamy ====
* Záznamy jsou uloženy na disku ve **stránkách (pages)** fixní velikosti
* Hardware přistupuje k celým stránkám – jak pro čtení, tak pro zápis
* Čas I/O na rotačních discích = doba hledání + rotační zpoždění + přenos
* Stránky jsou rozděleny na **sloty**, ve kterých jsou **záznamy**
* Každý záznam je identifikován pomocí (číslo stránky, číslo slotu)
* Stránky mají hlavičku s informací o obsazenosti slotů
* Záznamy mohou mít **fixní** nebo **variabilní** velikost
==== Buffer management ====
* **Buffer** = oblast hlavní paměti, kde jsou dočasně uloženy stránky z disku
* Každá stránka je mapována na **paměťový rámec**
* Rámec obsahuje:
* počet referencí
* **dirty flag** – značí, že byla změněna a není ještě zapsána na disk
* Politiky výměny rámců: LRU, Clock, FIFO…
==== Organizace datových souborů ====
* **Halda**
* Neuspořádané záznamy, hledání sekvenčně
* Vkládání rychlé (O(1)), mazání vytváří volné místo
* Volné stránky spravovány seznamem/tabulkou
* Všechny ostatní operace O(n)
* **Seřazený soubor**
* Záznamy uspořádané podle klíče
* Vyhledávání – logaritmická složitost (např. binární vyhledávání)
* Pomalé vkládání a mazání – nutnost přesunu
* Každá stránka má rezervu pro nové záznamy
* **Hašovaný soubor**
* Rozdělen do tzv. **kapes (buckets)** podle hašovací funkce
* Při přeplnění kapsy: připojí se nová stránka (overflow)
* Operace O(1) v průměru, O(n) v nejhorším
* Paměťově náročnější, řešeno dynamickým hašováním
==== Indexové struktury ====
* **Index** – pomocná datová struktura pro urychlení dotazů
* Obsahuje klíče a odkazy na záznamy (RIDs)
* Může být:
* **clustered** – pořadí indexu odpovídá pořadí dat
* **unclustered** – pořadí se neshoduje
* Typy indexu:
* **plný záznam**
* **klíč + ukazatel na záznam**
* **klíč + seznam ukazatelů**
==== B⁺-stromy ====
* Varianty B-stromu optimalizované pro databáze
* Všechny záznamy v **listech**, které jsou propojeny (pro rozsahové dotazy)
* Vnitřní uzly obsahují jen klíče pro navigaci
* Vkládání, vyhledávání a mazání: O(log n)
* Využití alespoň 50 % kapacity uzlů
==== Hašovaný index ====
* Princip stejný jako u hašovaných souborů
* Neobsahuje data, ale pouze ukazatele na záznamy
* Rychlé vyhledávání podle rovnosti
* Nevhodné pro rozsahové dotazy
==== Bitmapový index ====
* Efektivní pro atributy s malým počtem možných hodnot
* Každá hodnota má svůj **bitový vektor**, který ukazuje přítomnost
* Dotazy zpracovány bitovými operacemi (AND, OR…)
* Výhody: rychlost, kompaktnost, paralelizovatelnost
* Nevýhody: nevhodné pro velké domény nebo rozsahové dotazy (O(n))
===== 5. Funkční závislosti =====
**Funkční závislosti (definice, Armstrongovy axiomy), úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, redukovaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).**
* Funkční závislosti určují, jak se hodnoty atributů v tabulce vztahují.
* Jsou klíčové pro návrh databázového schématu a normalizaci.
==== Definice ====
* Funkční závislost `X → Y`: hodnoty atributů `X` určují hodnoty atributů `Y`.
* Elementární závislost: na pravé straně je jediný atribut.
* Funkční ekvivalence: `X ↔ Y` pokud `X → Y` a `Y → X`.
==== Armstrongovy axiomy ====
* Triviální závislost: `Y ⊆ X ⇒ X → Y`
* Tranzitivita: `X → Y ∧ Y → Z ⇒ X → Z`
* Kompozice: `X → Y ∧ X → Z ⇒ X → YZ`
* Dekompozice: `X → YZ ⇒ X → Y ∧ X → Z`
==== Funkční uzávěr ====
* Uzávěr `F⁺`: všechny závislosti, které lze odvodit z `F` pomocí axiomů.
==== Pokrytí a kanonické pokrytí ====
* Pokrytí `G` množiny `F`: `F⁺ = G⁺`
* Kanonické pokrytí: pokrytí obsahující jen elementární závislosti.
==== Redundance a neredundantní pokrytí ====
* Závislost `f` je redundantní v `F`, pokud `F \ {f}⁺ = F⁺`
* Neredundantní pokrytí: žádná závislost není redundantní.
==== Uzávěr atributů ====
* Uzávěr atributů `X⁺`: všechny atributy odvoditelné z `X` pomocí `F`.
* `X⁺ = A ⇒ X` je superklíč.
* Redukovaná závislost: žádné redundantní atributy na LHS.
* Klíč: minimální superklíč.
* Klíčový atribut: je v nějakém klíči.
==== Minimální pokrytí ====
* Neredundantní kanonické pokrytí s redukovanými závislostmi.
==== Hledání klíče ====
* Najdi `X` takové, že `X⁺ = A`, a žádný proper subset `X'` nemá tuto vlastnost.
==== Lucchesi-Osbornův algoritmus ====
* Algoritmus k nalezení **všech** klíčů relačního schématu.
- Najdeme jakýkoliv klíč `K`.
- Vybereme funkční závislost `X → y` z `F` takovou, že `y ∈ K`, nebo ukončíme algoritmus pokud taková neexistuje.
- Vytvoříme množinu `K' = X ∪ (K \ {y})`.
* Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč.
- Redukujeme levostranné atributy závislosti `K' → A`, a získáme nový **minimální** klíč `K'`.
- 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 už existuje, algoritmus končí.
==== Normální formy ====
=== První normální forma (1NF) ===
* Relace je v 1NF právě tehdy, když:
* Atributy jsou **atomické** (dále nedělitelné).
* Každý řádek tabulky je **jedinečný**.
* K řádkům lze přistupovat podle obsahu (klíčových) atributů.
* Relace **nesplňující** 1NF:
|**jmeno**|**prijmeni**|**adresa**|
|---|---|---|
|Josef|Novák|Technická 2, Praha 16627|
|Petr|Pan|Karlovo náměstí 13, Praha 12135|
* Relace **splňující** 1NF:
|**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**|
|---|---|---|---|---|---|
|Josef|Novák|Technivká|2|Praha|16627|
|Petr|Pan|Karlovo náměstí|13|Praha|12135|
=== Druhá normální forma (2NF) ===
* Relace je v 2NF právě tehdy, když:
* Je v **1NF**.
* Každý **neklíčový atribut** je **plně funkčně závislý** na **celém** primárním klíči (ne pouze na části složeného klíče).
* Příklad:
* Relace `{__IdStudenta, IdPredmetu__, JmenoStudenta, Semestr}`
* Primární klíč: `{IdStudenta, IdPredmetu}`
* `JmenoStudenta` závisí **jen** na `IdStudenta`
* `Semestr` závisí **jen** na `IdPredmetu`
* Řešení: Rozdělení do menších relací:
* `{__IdStudenta__, IdPredmetu}`
* `{__IdStudenta__, JmenoStudenta}`
* `{__IdPredmetu__, Semestr}`
=== Třetí normální forma (3NF) ===
* Relace je v 3NF právě tehdy, když:
* Je v **2NF**
* Neexistuje **tranzitivní závislost** mezi neklíčovými atributy.
* Každá závislost `X → A`: `X` je superklíč nebo `A` je klíčový atribut.
* Příklad:
* Relace `{__IdStudenta__, JmenoStudenta, Fakulta, Dekan}`
* `IdStudenta` → `Fakulta`
* `Fakulta` → `Dekan`
* `Dekan` je tedy **tranzitivně závislý** na `IdStudenta`
* Řešení: Rozdělení do:
* `{__IdStudenta__, JmenoStudenta, Fakulta}`
* `{__Fakulta__, Dekan}`
=== Boyce-Coddova normální forma (BCNF) ===
* Relace je v **BCNF**, pokud:
* Je v 3NF
* Pro každou netriviální závislost `X → A` musí být `X` **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:
* Relace `{__StudentID__, CourseID, Instructor}`
* `CourseID` → `Instructor`
* `CourseID` není superklíč ⇒ porušení BCNF
===== Transakce =====
**Transakce (základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh, historie, uspořádatelnost, serializovatelnost), konfliktová, uspořádatelnost (konflikty WR, RW, WW, precedenční graf), zamykací protokoly (dvoufázové a striktní dvoufázové zamykání), uváznutí (deadlock, graf čekání, Coffmanovy podmínky, strategie wait-die a wound-wait), fantom.**
==== Transakční zpracování ====
* Transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data.
* Transakce pracuje s konzistentní databází.
* 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í.
* Dva hlavní problémy:
* Různé výpadky (např. chyba hardware nebo pád systému)
* Souběžné spouštění více transakcí
==== ACID vlastnosti ====
* 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.
* **C**onsistency – transakce zachovává konzistenci dat a integritní omezení.
* **I**solation – transakce se navzájem neovlivňují (jako by běžely sériově).
* **D**urability – po COMMIT jsou změny trvalé, přežijí i pád systému.
==== Akce ====
* **Akce na objektech:** `READ`, `WRITE`, `XLOCK`, `SLOCK`, `UNLOCK`
* **Globální akce:** `BEGIN`, `COMMIT`, `ROLLBACK`
==== Transakční historie ====
* Posloupnost akcí několika transakcí, zachovávající jejich lokální pořadí.
* Historie (rozvrh) je **sériová**, pokud transakce probíhají jedna po druhé (žádné prokládání operací).
==== Serializovatelnost ====
* Teorie: transakce se skládají z akcí typu:
* `READ_i(A)` – čtení objektu `A` v transakci `T_i`
* `WRITE_i(A)` – zápis objektu `A` v transakci `T_i`
* `ROLLBACK_i` – přerušení transakce `T_i`
* `COMMIT_i` – potvrzení transakce `T_i`
| | | |
|---|---|---|
|READI(A) - READJ(A)|Není konflikt|Na pořadí nezávisí|
|READI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
|WRITEI(A) - READJ(A)|**Konflikt**|Pořadí má význam|
|WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
==== Konflikty ====
* **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data.
* **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí.
* **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace.
* **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry.
* **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií.
* **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty.
* Pokud je **acyklický**, historie je serializovatelná.
==== Zamykání ====
* Způsob **pesimistické kontroly souběhu** pomocí zámků.
* **Zamykací protokol** zajišťuje konfliktní serializovatelnost.
* Typy zámků:
* **XLOCK (exkluzivní zámek)** – pouze pro jednu transakci, umožňuje zápis a čtení.
* **SLOCK (sdílený zámek)** – umožňuje více transakcím číst.
* **UNLOCK** – uvolnění zámku.
==== Dvoufázové zamykání (2PL) ====
* Transakce:
* Nejprve pouze **získává** zámky (růstová fáze).
* Poté je **pouze uvolňuje** (klesající fáze).
* Zajišťuje **serializovatelnost**, ale **nezajišťuje zotavitelnost** (možné kaskádové zrušení).
=== Striktní dvoufázové zamykání (Strict 2PL) ===
* Všechny zámky jsou **drženy až do COMMIT/ROLLBACK**.
* Zajišťuje zotavitelnost i prevenci kaskádového přerušení.
==== Uváznutí (Deadlock) ====
* Nastane, když každá transakce čeká na zámek držený jinou transakcí.
* Reprezentace pomocí **grafu čekání**:
* Vrcholy: transakce
* Hrana `T₁ → T₂`: `T₁` čeká na zámek držený `T₂`
* **Cyklus = deadlock**
=== Metody prevence a řešení uváznutí ===
* **Detekce:** pomocí grafu čekání, přeruší se jedna transakce.
* **Prevence:**
* **Wait-Die:** starší čeká, mladší umírá (rollback).
* **Wound-Wait:** starší zabije mladší, jinak čeká.
* **Strategie výběru oběti:** přeruší se transakce podle délky běhu, počtu zámků apod.
=== Coffmanovy podmínky ===
Uváznutí může nastat, pokud platí všechny 4 podmínky:
- **Vzájemné vyloučení** – prostředky nejsou sdílené.
- **Zadržení a čekání** – proces drží a zároveň žádá další.
- **Žádná preempce** – prostředky nejsou vynuceně odebrány.
- **Kruhové čekání** – cyklická závislost v čekání.
* Pokud **aspoň jedna podmínka neplatí**, uváznutí nemůže nastat.
==== Fantom ====
* Specifický problém u transakcí s dotazy přes množiny záznamů.
* Jedna transakce čte množinu řádků podle podmínky (např. WHERE cena < 1000).
* Jiná transakce mezitím přidá nový záznam, který podmínce odpovídá.
* První transakce je **ovlivněna novým záznamem**, i když už měla dané zámky.
* Řešení: **zámky na rozsah (range locks)** – např. pomocí indexových struktur.