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/01/25 22:12] – 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 9: Line 9:
   * **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** – 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.   * **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:
 +<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í ====
 +  * 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`
 +
 +<markdown>
 +|   |   |   |
 +|---|---|---|
 +|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 ====
 +  * **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.
  

Trace:

Navigation

Playground

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