statnice:bakalar:b0b36dbs

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, objektově-relační mapování, noSQL databá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ě.

==== 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.
  1. 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.
  3. Vytvoříme množinu `K' = X ∪ (K \ {y})`. 
     * 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'`.
  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.
  6. 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:
<markdown>
|**jmeno**|**prijmeni**|**adresa**|
|---|---|---|
|Josef|Novák|Technická 2, Praha 16627|
|Petr|Pan|Karlovo náměstí 13, Praha 12135|
</markdown>

  * Relace **splňující** 1NF:
<markdown>
|**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**|
|---|---|---|---|---|---|
|Josef|Novák|Technivká|2|Praha|16627|
|Petr|Pan|Karlovo náměstí|13|Praha|12135|
</markdown>

=== 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í ====
<markdown>
- 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 transakci
</markdown>
==== ACID vlastnosti ====
<markdown>
- K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit:
	- **A**tomicity : transakce atomická - buď se podaří a provede se celá nebo nic. Nelze vykonat jen část transakce.
	- **C**onsistency : transakce - konkrétní transformace stavu, zachování invariant - integritní omezení.
	- **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 ú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 ====
<markdown>
- **akce na objektech :** READ, WRITE, XLOCK, SLOCK, UNLOCK
- **akce globální :** BEGIN, COMMIT, ROLLBACK
</markdown>
==== Transakční historie ====
<markdown>
- Posloupnost akcí několika transakcí, jež zachovává pořadí akcí, v němž byly prováděny
- Historie (rozvrh) se nazývá *sériová*, pokud jsou všechny kroky jedné transakce provedeny před všemi kroky druhé transakce.
</markdown>
==== Serializovatelnost ====
<markdown>
- Teorie: Nechť se transakce $T$ i skládá z následujících elementárních akcí:
	- $\mathrm{READ}_i(A)$ - čtení objektu $A$ v rámci transakce $T_i$
	- $\mathrm{WRITE}_i(A)$ - zápis (přepis) objektu $A$ v rámci transakce $T_i$
	- $\mathrm{ROLLBACK}_i(A)$ - přerušení transakce $T_i$
	- $\mathrm{COMMIT}_i(A)$ - potvrzení transakce $T_i$
- Jsou možné 4 případy:

|   |   |   |
|---|---|---|
|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|
</markdown>
==== Konflikty ====
<markdown>
- *WR konflikt* - jedna transakce data zapíše, druhá je čte předtím než byla commited, tzv. *dirty read*
- *RW konflikt* - transakce čte data a druhá je zapíše předtím než byla ta první ukončena, tzv. *unrepeatable read*
- *WW konflikt* - přepis dat, která ještě nebyla commited, tzv. *blind write*
- Dvě historie jsou *konfliktově ekvivalentní*, pokud sdílí stejné konfliktní páry
- Historie je *konfliktově uspořádatelná*, pokud je konfliktově ekvivalentní s nějakou sériovou historií
- *Precedenční graf* je směrový graf, kde vrcholy jsou transakce a hrany jsou konfliktní páry mezi transakcemi
	- Pokud je acyklický, je historie sériově uspořádatelná
</markdown>
==== Zamykání ====
<markdown>
- Způsob tzv. *pesimistické kontroly* v plánovači transakcí
- *Zamykací protokol* je protokol, který zamyká entity tak, aby byla zabezpečena konfliktní serializovatelnost
- Dva druhy zámků
	- *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$
	- *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í
- Navíc je definována operace odemykání $U(A)$
</markdown>
==== Dvoufázové zamykání (2PL) ====
<markdown>
- Pokud transakce chce číst (zapisovat) entitu $A$, musí nejprve získat sdílený (exkluzivní) zámek na tuto entitu
- Transakce nesmí zažádat o zámek na entitu $A$ pokud jej předtím už uvolnila
- Zajišťuje acykličnost precedenčního grafu
- 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) ===
<markdown>
- Zajišťuje zotavitelnost a kaskádovité přerušování
- Všechny zámky může transakce pustit až poté co je ukončena
</markdown>
==== Uváznutí (deadlock) ====
<markdown>
- Situace, která nastane, když všechny transakce čekají až jiná transakce uvolní zámek
- Lze identifikovat pomocí tzv. *grafu čekání*
	- Vrcholy jsou jednotlivé transakce
	- 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í
</markdown>
=== Metody prevence/řešení uváznutí ===
<markdown>
- Přerušení transakce a restart
- 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)
- 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 ===
<markdown>
- K uváznutí může nastat pokud platí všechny z následujících podmínek
1. *Vzájemné vyloučení* - zdroje nejsou plně sdíleny a jsou drženy exkluzivně
2. *Držení zdrojů* - další zdroje mohou být vyžadovány i když už jsou jiné drženy
3. *Žádná preempce* - zdroje mohou být vypuštěny pouze dobrovolně
4. *Kruhové čekání* - transakce čekají a vyžadují zdroje v kruhu
- Nenaplnění jakékoliv z těchto podmínek stačí na prevenci uváznutí
</markdown>
==== Fantom ====
<markdown>
- Může nastat v databázi, kde jsou vkládány a mazány nové položky
- Jedna transakce pracuje s nějakou množinou entit, zatímco druhá transakce tuto množinu změní
- Může vést k nekonzistentní databázi
- Může nastat i při striktním dvoufázovém zamykání
</markdown>
Trace: • exams • b4m39apg • exams • b4m39viz • b0b36prp • b4m01tal • b4b33rpz • b0b36dbs
Search

Navigation

Print/export

Tools

QR Code
