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 [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 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í BCNF, které ještě **není** porušením 3NF:
 +    * 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: • magistr • b4b35osy • b0b01ma2 • b4b01dma • b4b01num • b0b36dbs • b4m35ko • b0b33opt

Navigation

Playground

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