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/05/24 10:16] – [Transakce] mistrjirkastatnice: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 11: Line 11:
  
  
-===== Konceptuální modelování ===== +===== 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 (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 diagramy - diagramy zobrazující realnou strukturu systému, pomáhají uvědomit si co je potřeba zavést do databáze. + 
-  * ER - Entity-relationship model +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í. 
-  * Nemá standardy - takže si každý z prdele tahá notaci a je to uplně k hovnu + 
-  * Méně využíván než UML (for good fucking reason too)+  * **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 ==== ==== Entitní typy ====
-Entita je obecně osoba, projekt, nějaký objekt = třída v UML. +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ř. název u projektu) + 
-  * Slabý entitní typ - nemá plný identifikátor, má jeden nebo více částečných id -> jeho identifikace závisí na jiné entitě+  * **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 ==== ==== Atributy ====
-  * Vlastnost entity +  * 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}} {{:statnice:bakalar:pasted:20250520-124031.png}}
-  * Mají název a kardinalitu (množství) 
-  * Složené atributy - basically více atributů složené do jednoho (např. adresa) 
-  * mají datový typ 
  
 ==== Identifikátory ==== ==== Identifikátory ====
-  * Atribut nebo skuipina atributů, která jednoznačně určuje entitu +  * Atribut nebo kombinace atributů, která jednoznačně určuje konkrétní entitu. 
-  * Rozdělení  +  * Rozlišujeme: 
-    * Plné - atribut nebo skupina atributů jedné entity+    * **Plné identifikátory** – skládají se z atributů dané entity
 {{:statnice:bakalar:pasted:20250520-124044.png}} {{:statnice:bakalar:pasted:20250520-124044.png}}
-    * Částečné - pomocí vazby na jinou entitu, dovoluje pouze kardinalitu (1,1) +    * **Čá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}} {{:statnice:bakalar:pasted:20250520-124130.png}}
  
 ==== Vztahové typy ==== ==== 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).
  
-  * Mají název, entity a kardinalitu 
-  * Binární - 2 entity 
-  * N-ární - více než 2 entity, mohou být nahrazeny třídou, která má binární vztahy se všemi entitami ve vztahu 
-  * Rekurzivní - typ vztahu mezi entitami stejného typu 
 {{:statnice:bakalar:pasted:20250520-125915.png}} {{:statnice:bakalar:pasted:20250520-125915.png}}
 +
 ==== ISA hierarchie (is-a hierarchy) ==== ==== ISA hierarchie (is-a hierarchy) ====
-specifický vztah bez názvu a kardinalit+  * 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).
  
-  * Vytváří hierarchii parent-child 
-  * typ entity, která je speicalizací jiné enity 
-  * child může mít max jednoho parent 
 {{:statnice:bakalar:pasted:20250520-130342.png}} {{:statnice:bakalar:pasted:20250520-130342.png}}
  
 ==== Logické modely ==== ==== Logické modely ====
-  * Proces logického modelování +Převádějí konceptuální schéma do technicky orientované reprezentace podle toho, jak budou data uchovávána a dotazována.
-    * Výběr modelu podle charakteristik dat, možností dotazování, použití, požadavky +
-    * Tvorba logického schématu - transformace z konceptuálního schématu do logického +
-=== Tabulkový === +
-  * Struktura - řádky pro entitry a sloupce pro atributy +
-  * Operace - selection, projection, join +
-  * např.: sql +
-=== Objektový ===  +
-  * Struktura - objekty s atributy, používá ukazatele mezi objekty +
-  * Operace - navigation +
-=== Stromový === +
-  * Struktura - vrchol s atributy, hrany mezi vrcholy +
-  * Hieararchie, kategorizace, semi-strukturovaná data +
-  * např.: xml dokumenty, json +
-=== Grafový === +
-  * Struktura vrcholy, hrany, atributy +
-  * Opearce - Obhcázení, porovnávání vzorů, grafové algoritmy +
-  * Např.: síťovy model, REsource Description Framework, FlockDB+
  
 +  * **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
  
-===== Relační databáze ===== +=== Tabulkový model === 
-  * Databáze - Logicky uspořádaný soubor souvisejících dat, obsahuje data, metadata, schéma, omezení integrity atd. +  * Struktura: tabulky – řádky reprezentují entity, sloupce atributy. 
-  * Database management system (DBMS) - Softwarový systém umožňující přístup do databáze, poskytuje mechanismy pro zajištění bezpečnosti a +  * Operace: výběr (selection), projekce (projection), spojení (join). 
-  * spolehlivosti, souběžnost, integritu uložených dat, ... +  * Typický zástupce: **relační databáze (SQL)**
-  * Databázový systém - informační systém obsahující databázi, DBMS, hardware, procesy, osoby... +
-  * Relační databáze - množina relací+
  
-==== Null hodnoty ==== +=== Objektový model === 
-  * Vyjadřuje vhybející informaci +  * Struktura: objekty s atributy, ukazatele mezi objekty. 
-  * Operace s null +  * Operace: navigace pomocí referencí (např. `obj.adresa.mesto`). 
-  * 3 + null = null +  * Používá se např. v objektových databázích. 
-  * 3 < null = uknown + 
-==== Integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a +=== Stromový model === 
-referenční akce)  *  +  * Struktura: uzly (vrcholy) s atributy, hrany jako vztahy. 
-  * Entitní – každý záznam v tabulce má platný a jedinečný primární klíč. +  * Hierarchická data – např. XML, JSON. 
-  * Doménová – zajišťují dodržování datových typů/domén definovaných u sloupců databázové tabulky +  * Vhodné pro semi-strukturovaná data. 
-  * Referenční – zabývají se vztahy dvou tabulek, kde jejich relace je určena vazbou primárního a cizího klíč + 
-    * NOT NULL - hodnoty nesmí být null +=== Grafový model === 
-    * UNIQUE - hodnoty musí být unikátní +  * Struktura: vrcholy, hrany, atributy (může být směrovaný či nesměrovaný). 
-    * PRIMARY KEY = NOT NULL + UNIQUE +  * Operace: prohledávání grafu, porovnávání vzorů, grafové algoritmy. 
-    * FOREIGN KEY - hodnoty klíče v odkazující tabulce musí být v odkazované tabulce +  * Použití např.: RDF, FlockDB, sociální sítě. 
-    * CHECK - definuje se podmínka, která musí být splněna+ 
 +==== 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.
  
-=== Referenční akce === 
-Pokud nejsou nastavené referenční akce a zároveň by operace v odkazované tabulce způsobila porušení cizího klíče v odkazující tabulce, tak by 
-operace byla blokována a generoval by se error message 
-  * Trigger - různé případy změn v tabulce 
-    * ON UPDATE 
-    * ON DELETE 
-  * Akce - co se provede po změne v tabulce 
-    * CASCADE - hodnota je také změněna / odstraněna 
-    * SET NULL - hodnota nastavena na NULL 
-    * SET DEFAULT - hodnota nastavena na výchozí 
-    * NO ACTION - zabraňuje provedení operace 
-    * RESTRICT - podobný no action 
 ==== Umělé identifikátory ==== ==== Umělé identifikátory ====
-  * Zcela automatizované +  * Automaticky generované identifikátory, často celočíselné. 
-  * Obvykle se jedná o celočíselné řady a každý novější záznam dostává číslo vždy o jednotku vyšší než je číslo u posledního vloženého záznamu +  * Obvykle využívají **sekvenci** (např. auto_increment nebo serial). 
-  * (číselné označení záznamů s časem stoupá). +  * Nový záznam získá ID větší než předchozí, čímž vzniká jednoznačný a jednoduše řaditelný klíč. 
-===== Jazyk SQL ===== +  * Používají se, když přirozený klíč neexistuje nebo je příliš komplikovaný. 
-Structured Query Language (SQL) je jazyk pro kladení dotazů do databáze. Obsahuje jak příkazy DML (Data manipulation Language), tak i DDL + 
-příkazy (Data Definition Language). SQL je case insensitive (nerozlišuje mezi velkými a malými písmeny). + 
-  * Transaction management + 
-  * Administrace Databáze+===== 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 ==== ==== Definice schématu ====
-=== Tvorba tabulky === 
-CREATE TABLE  *  
-  * Název tabulky 
-  * Definování sloupců (atributů) - názvy, datové typy, výchozí hodnota 
-  * Definování integritních omezení v rozsahu tabulky 
-=== Úprava schématu === 
-  * ALTER TABLE – změny existujících objektů. 
-    * RENAME TO 
-    * ADD COLUMN 
-    * ALTER COLUMN 
-    * DROP COLUMN 
-    * ADD (constraint definition) 
-    * DROP CONSTRAINT 
-  * DROP TABLE 
  
-=== Manipulace s daty (SELECT, INSERT, UPDATE, DELETE) === +  * **CREATE TABLE** – vytvoření tabulky   
-  * Příkazy pro získání dat z databáze a pro jejich úpravy +    * Název tabulky   
-  * DML – Data Manipulation Language +    * Definice sloupců (název, datový typ, výchozí hodnota)   
-  * INSERT INTO – vkládá do databáze nové řádky (záznamy) +    * Integritní omezení (PRIMARY KEY, NOT NULL, ...)  
-  * UPDATE – mění data v databázi (editace záznamu) +
-  * MERGE – kombinace INSERT a UPDATE – data buď vloží (pokud neexistuje odpovídající klíč), pokud existuje, pak je upraví ve stylu UPDATE. +
-  * DELETE FROM – odstraňuje data (záznamy) z databáze +
-  * EXPLAIN – speciální příkaz, který zobrazuje postup zpracování SQL příkazu. Pomáhá uživateli optimalizovat příkazy tak, aby byly rychlejší. +
-  * SHOW - méně častý příkaz, umožňující zobrazit databáze, tabulky nebo jejich definice +
-  * SELECT - Vybírá data z databáze, umožňuje výběr podmnožiny a řazení dat +
-    * SELECT + názvy sloupců, nebo * , nebo definování nových a agregovaných sloupců +
-      * nové pojmenování sloupců pomocí AS +
-      * ALL - vše +
-      * DISTINCT - odstranění duplicit +
-      * FROM - z které tabulky, poddotazu nebo pohledu +
-      * WHERE - podmínka +
-        * AND, OR, NOT +
-        * predikáty +
-      * GROUP BY - volba atributů pro agregaci +
-      * HAVING - podmínka pro agregovaná data +
-      * ORDER BY - řazení +
-=== Spojování tabulek === +
-  * JOIN +
-    * CROSS JOIN - kartézský součin všech řádků z obou tabulek (všechny kombinace) +
-    * NATURAL JOIN - výsledkem pouze řádky, které mají stejné hodnoty atributů +
-    * INNER JOIN - defaultní JOIN +
-      * podmínka ON +
-      * USING atribut - odpovídá natural join +
-      * pokud bez ON nebo USING - odpovídá cross join +
-    * OUTER JOIN - řádky z inner joinu a řádky, které nemohou být spojeny (hodnoty doplněny NULL) +
-    * LEFT / RIGHT - řádky z levé / pravé tabulky +
-    * FULL - z obou +
-    * UNION JOIN - řádky jsou integrovány do jedné tabulky, žádné řádky nejsou spojeny+
  
 +  * **ALTER TABLE** – úprava existující tabulky  
 +    * RENAME TO  
 +    * ADD COLUMN, ALTER COLUMN, DROP COLUMN  
 +    * ADD CONSTRAINT, DROP CONSTRAINT
  
-===== Fyzická vrstva ===== +  * **DROP TABLE** – odstranění tabulky 
-**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).**+ 
 +==== 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
  
-==== Charakteristika ==== 
-<markdown> 
-- Specifikuje jak jsou databázové struktury implementovány ve specifickém prostředí 
-- Zahrnuje soubory, indexovací struktury a tak dále 
-</markdown> 
 ==== Stránky, sloty a záznamy ==== ==== Stránky, sloty a záznamy ====
-<markdown> + 
-- Záznamy jsou uloženy na disku v *blocích* (angl. *page*) fixní velikosti +  * Záznamy jsou uloženy na disku ve **stránkách (pages)** fixní velikosti   
-- Hardware přistupuje pouze k celým stránkám uloženým na disku (čtení i zápis) +  * Hardware přistupuje k celým stránkám – jak pro čtení, tak pro zápis   
-- Čas, který trvá jedna I/O operace se na rotačním pevném disku spočítá jako součet doby hledání, rotačního zpoždění a přenosu dat +  * Čas I/O na rotačních discích = doba hledání + rotační zpoždění + přenos   
-- stránky bývají rozděleny na *sloty* ve kterých jsou uložené *záznamy*, které jsou identifikované číslem stránky + číslem záznamu +  * Stránky jsou rozděleny na **sloty**, ve kterých jsou **záznamy**   
-- Záznamy mohou mít fixní nebo variabilní velikost +    * Každý záznam je identifikován pomocí (číslo stránky, číslo slotu)   
-- Každá stránka má ještě hlavičku, která obsahuje informace o využití slotů, případně jejich velikosti pokud stránka obsahuje záznamy variabilní velikosti +  * Stránky mají hlavičku s informací o obsazenosti slotů   
-</markdown>+  * Záznamy mohou mít **fixní** nebo **variabilní** velikost 
 ==== Buffer management ==== ==== Buffer management ====
-<markdown> + 
-- *Buffer* je část hlavní paměti, kde jsou dočasně uloženy celé stránky z disku, stránky jsou mapovány na paměťové rámce +  * **Buffer** = oblast hlavní paměti, kde jsou dočasně uloženy stránky z disku   
-- Každý rámec si drží počet referencí na stránku v rámci a *dirty flag*, který označuje změněný záznam, který nebyl zapsán na disk +  * Každá stránka je mapována na **paměťový rámec**   
-</markdown> +  * Rámec obsahuje: 
-==== Datové soubory ==== +    * počet referencí 
-<markdown> +    * **dirty flag** – značí, že byla změněna a není ještě zapsána na disk   
-- *Halda* je druh souboru, kde záznamy nejsou v blocích řazené a záznamy tedy mohou být vyhledávány pouze sekvenčně, vkládat nové záznamy je snadné, ale při mazání může vznikat nevyužité místo +  * Politiky výměny rámců: LRU, Clock, FIFO… 
- - Prázdné stránky jsou udržovány pomocí spojového seznamu nebo tabulky stránek + 
- - Všechny operace mají lineární složitost, až na vkládání, které je konstantní +==== Organizace datových souborů ==== 
-- *Řazený soubor* je druh souboru, kde jsou záznamy řazeny na základě nějakého klíče + 
- - Rychlé vyhledávání (logaritmická složitost) +  * **Halda** 
- - Pro vkládání má každá stránka prázdný overhead, pokud je zaplněn jsou použity nové stránky +    * Neuspořádané záznamy, hledání sekvenčně 
- - Ve všem kromě vyhledávání je pomalejší než halda +    * Vkládání rychlé (O(1)), mazání vytváří volné místo 
-</markdown> +    * Volné stránky spravovány seznamem/tabulkou 
-==== Hashované soubory ==== +    * Všechny ostatní operace O(n) 
-<markdown> + 
-- Soubor je organizovaný do tzv. *kapes* (anglicky *buckets*) +  * **Seřazený soubor** 
-- To v jaké kapse je záznam uložený je rozhodnuto na základě hashovací funkce $f$ +    * Záznamy uspořádané podle klíče 
-- Pokud je kapsa plná, je alokována nová stránka a propojena s kapsou formou spojového seznamu +    * Vyhledávání – logaritmická složitost (např. binární vyhledávání) 
-- Výhodou je rychlé vyhledávání, nevýhodou je ale paměťová náročnost (řešeno dynamickým hashováním) +    * Pomalé vkládání a mazání – nutnost přesunu 
-- Většina operací má přibližně složitost $N/K$, kde $K$ je počet kapes +    * Každá stránka má rezervu pro nové záznamy 
-</markdown>+ 
 +  * **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 ==== ==== Indexové struktury ====
-<markdown> 
-- *Index* je pomocná struktura, která poskytuje rychlé vyhledávání na základě hledaných klíčů 
-- Obsahuje typicky jenom klíče a odkazy k záznamům, vyžaduje proto výrazně méně místa než datové soubory 
-- Index může obsahovat celý záznam, pár klíče a odkazu na záznam, nebo pár klíče a seznamu odkazů na záznam 
-- Řazení indexovaných předmětů může být zachováno (*clustered indexing*) nebo nemusí (*unclustered indexing*) 
-</markdown> 
-==== B$^+$-stromy ==== 
-<markdown> 
-- Rozšířený B-strom 
-- Logaritmická složitost pro vkládání, vyhledávání podle rovnosti a mazání podle rovnosti 
-- Garantuje využití alespoň 50% stránek 
- - Oproti B-stromu jsou všechny data (klíču jsou stále v B strom struktuře) v listech a stránky příslušné listům jsou provázány pro vykonávání dotazů založených na intervalech 
-</markdown> 
-==== Hashovaný index ==== 
-<markdown> 
-- Stejné jako hašovaný soubor, ale obsahuje pouze odkazy na záznamy 
-</markdown> 
-==== Bitmapy ==== 
-<markdown> 
-- Vhodné pro atributy, které mohou nabývat malého množství hodnot 
-- Každý atribut je realizován jako vektor bitů, kde $i$-tý bit popisuje jestli atribut nabývá $i$-té hodnoty nebo ne 
-- Dotazy lze pak provádět pomocí bitových masek a bitwise operací 
-- Výhody - efektivní, kompaktní, rychlé, snadno paralelizovatelné 
-- Nevýhody - Pouze pro atributy s doménou malé kardinality, pomalé dotazy na základě rozsahu (lineární v šířce rozsahu) 
-</markdown> 
  
-===== Funkční závislosti =====+  * **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ů**
  
-**Funkční závislosti (definice, Armstrongovy axiomy), úpravy závislostí (funkční uzávěr, pokrytí,   +==== B⁺-stromy ==== 
-kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, reduko-   + 
-vaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn).   +  * Varianty B-stromu optimalizované pro databáze   
-Normální formy (první, druhá, třetí, Boyceho-Coddova).**+  * 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 ==== ==== Definice ====
-<markdown> +  * Funkční závislost `X → Y`: hodnoty atributů `X` určují hodnoty atributů `Y`. 
-- *Funkční závislost* $X\rightarrow Y$ nad schématem $R(A)$ je mapování $f_i:X_i\rightarrow Y_i$, kde $X_i,Y_i \subseteq A$ +  * Elementární závislost: na pravé straně je jediný atribut. 
-- U $X\rightarrow Y$ říkáme, že hodnoty v $X$ určují hodnoty v $Y$ +  * Funkční ekvivalence: `X ↔ Y` pokud `X → Y` a `Y → X`. 
-- Pokud platí $X\leftarrow Y$ a $Y\leftarrow X$, pak řekneme, že $X\leftrightarrow Y$ jsou *funkčně ekvivalentní* +
-- Pokud je na pravé straně funkční závislosti jediný atribut $a$, mluvíme o *elementární funkční závislosti* +
-</markdown>+
 ==== Armstrongovy axiomy ==== ==== Armstrongovy axiomy ====
-<markdown> +  * Triviální závislost: `Y ⊆ X ⇒ X → Y` 
-1. Triviální funkční závislost: $Y\subseteq X\Rightarrow X\rightarrow Y$ +  * Tranzitivita: `X → Y ∧ Y → Z ⇒ X → Z` 
-2. Tranzitivita: $(X\rightarrow Y\land Y\rightarrow Z)\Rightarrow X\rightarrow Z$ +  * Kompozice: `X → Y ∧ X → Z ⇒ X → YZ` 
-3. Kompozice: $(X\rightarrow Y\land X\rightarrow Z)\Rightarrow X\rightarrow YZ$ +  * Dekompozice: `X → YZ ⇒ X → Y ∧ X → Z` 
-4. Dekompozice: $X\rightarrow YZ\Rightarrow(X\rightarrow Y\land X\rightarrow Z)$ +
-</markdown>+
 ==== Funkční uzávěr ==== ==== Funkční uzávěr ====
-<markdown> +  * Uzávěr `F⁺`: všechny závislosti, které lze odvodit z `F` pomocí axiomů. 
-- *Uzávěr množiny funkčních závislosti* $F$ je množina všech funkčních závislostí, které lze odvodit z funkčních závislostí v $F$ pomocí Armstrongových axiomů + 
-- Značí se $F^+$ +==== Pokrytí a kanonické pokrytí ==== 
-</markdown> +  * Pokrytí `G` množiny `F`: `F⁺ = G⁺` 
-==== Pokrytí ==== +  * Kanonické pokrytí: pokrytí obsahující jen elementární závislosti. 
-<markdown> + 
-- *Pokrytí množiny funkčních závislostí* $F$ je nějaká množina funkčních závislostí $G$ taková, že platí $F^+=G^+$ +==== Redundance a neredundantní pokrytí ==== 
-- *Kanonické pokrytí* je takové pokrytí, které obsahuje pouze elementární funkční závislosti +  * Závislost `f` je redundantní v `F`, pokud `F \ {f}⁺ = F⁺` 
-</markdown> +  * Neredundantní pokrytí: žádná závislost není redundantní. 
-==== Redundance ==== +
-<markdown> +
-- Funkční závislost $f$ je *redundantní* v množině $F$, pokud platí $(F-\{f\}^+=F^+)$ +
-- To znamená, že $f$ je odvoditelné ze zbytku množiny $F$ +
-- *Neredundantní pokrytí* množiny $F$ je pak takové pokrytí, které vznikne po odstranění všech redundantních funkčních závislostí z $F$ +
-</markdown>+
 ==== Uzávěr atributů ==== ==== Uzávěr atributů ====
-<markdown> +  * Uzávěr atributů `X⁺`: všechny atributy odvoditelné z `X` pomocí `F`. 
-- *Uzávěr atributů* $X^+$ je podmnožina všech atributů z $A$, které lze odvodit z množiny atributů $X$ pomocí funkčních závislostí +  * `X⁺ = A ⇒ X` je superklíč. 
-- Pokud $X^+=A$, pak říkáme, že $X$ je *super-klíč* (nadklíč) +  * Redukovaná závislost: žádné redundantní atributy na LHS. 
-- Ve funkční závislosti $X\rightarrow Y$ je atribut $a$ *redundantní* když $Y\subseteq(X-a)^+$ +  * Klíč: minimální superklíč. 
-- *Redukovaná fukční závislost* neobsahuje žádné redundantní atributy +  * Klíčový atribut: je v nějakém klíči. 
-- Pro $R(A)$ je *klíč* je takový super-klíč, kde je funkční závislost $K\rightarrow A$ redukovaná +
-- *Klíčový atribut* je atribut, který se nachází v jakémkoliv klíči (klíčů může být víc) +
-</markdown>+
 ==== Minimální pokrytí ==== ==== Minimální pokrytí ====
-<markdown> +  * Neredundantní kanonické pokrytí s redukovanými závislostmi. 
-- *Minimální pokrytí* je neredundantní kanonické pokrytí, které obsahuje pouze redukované funkční závislosti + 
-</markdown>+==== Hledání klíče ==== 
 +  * Najdi `X` takové, že `X⁺ = A`, a žádný proper subset `X'` nemá tuto vlastnost.
  
-==== Nalezení jednoho klíče ==== 
-<markdown> 
-- Z triviální funkčí závislosti $A\rightarrow A$ postupně odstraňujeme redundantní atributy na levé straně, dokud tam žádné nezůstanou 
-- Na levé straně funkčí závislosti pak dostaneme jeden z klíčů $A$ 
-</markdown> 
 ==== Lucchesi-Osbornův algoritmus ==== ==== Lucchesi-Osbornův algoritmus ====
-<markdown> +  * Algoritmus k nalezení **všech** klíčů relačního schématu. 
-- Algoritmus k nalezení všech klíčů +  - Najdeme jakýkoliv klíč `K`. 
-1. 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. 
-2. Vybereme funkční závislost $X\rightarrow y$ z $F$ takovou, že $y\in K$, nebo ukončíme algoritmus pokud neexistuje +  - Vytvoříme množinu `K' = X ∪ (K \ {y})`.  
-3. Protože, platí $X\{K-y\}\rightarrow A$, $X\{K-y\}$ je super-klíč +     * Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč. 
-4. Redukujeme $X\{K-y\}\rightarrow A$ a na levé straně dostaneme nový klíč $K'$, který je jiný než $K$ +  -  Redukujeme levostranné atributy závislosti `K' → A`, a získáme nový **minimální** klíč `K'`. 
-5. Pokud $K'$ ještě není v množině nalezených klíčů, uložíme jej, položíme $K:=K'$ a pokračujeme na krok 2. Jinak algoritmus končí +  - Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2. 
-</markdown>+  - Pokud už existuje, algoritmus končí. 
 ==== Normální formy ==== ==== Normální formy ====
  
 === První normální forma (1NF) === === První normální forma (1NF) ===
-<markdown> +  * Relace je v 1NF právě tehdy, když: 
-- Relace je v 1NF právě tehdy, když platí současně: +    * Atributy jsou **atomické** (dále nedělitelné). 
- - atributy jsou atomické (dále nedělitelné) +    * Každý řádek tabulky je **jedinečný**. 
- - k řádkům relace lze přistupovat podle obsahu (klíčových) atributů +    * K řádkům lze přistupovat podle obsahu (klíčových) atributů.
- - řádky tabulky jsou jedinečné +
-- Relace nesplňující 1NF:+
  
-|   |   |   | +  * Relace **nesplňující** 1NF: 
-|---|---|---|+<markdown>
 |**jmeno**|**prijmeni**|**adresa**| |**jmeno**|**prijmeni**|**adresa**|
 +|---|---|---|
 |Josef|Novák|Technická 2, Praha 16627| |Josef|Novák|Technická 2, Praha 16627|
 |Petr|Pan|Karlovo náměstí 13, Praha 12135| |Petr|Pan|Karlovo náměstí 13, Praha 12135|
 +</markdown>
  
-- Relace v 1NF: +  * Relace **splňující** 1NF: 
- +<markdown>
-|   |   |   |   |   |   | +
-|---|---|---|---|---|---|+
 |**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**| |**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**|
 +|---|---|---|---|---|---|
 |Josef|Novák|Technivká|2|Praha|16627| |Josef|Novák|Technivká|2|Praha|16627|
 |Petr|Pan|Karlovo náměstí|13|Praha|12135| |Petr|Pan|Karlovo náměstí|13|Praha|12135|
 </markdown> </markdown>
 +
 === Druhá normální forma (2NF) === === Druhá normální forma (2NF) ===
-<markdown> +  * Relace je v 2NF právě tehdy, když: 
-- Relace je v 2NF právě tehdy, když platí zároveň: +    * Je v **1NF**. 
- - relace 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). 
- - každý neklíčový atribut je plně závislý na každém kandidátním klíči + 
-- Příklad: +  * Příklad: 
- - Mějme relaci _{__IdStudenta, IdPredmetu__, JmenoStudenta, SemestrLZ},_ kde _IdStudenta_ a _IdPredmetu_ tvoří primární klíč. +    * Relace `{__IdStudenta, IdPredmetu__, JmenoStudenta, Semestr}` 
- - Tato relace není v 2NF, protože _JmenoStudenta_ je závislé pouze na _IdStudenta_ a _SemestrLZ_ je závislé pouze na _IdPredmetu._ +    * Primární klíč: `{IdStudenta, IdPredmetu}` 
-- Řešení: +    * `JmenoStudenta` závisí **jen** na `IdStudenta` 
- - Rozdělení relace do tří tabulek +    * `Semestr` závisí **jen** na `IdPredmetu` 
- - _{__IdStudenta__,_ _IdPredmetu__}_ + 
- - _{__IdStudenta,_ _JmenoStudenta}_ +  * Řešení: Rozdělení do menších relací: 
- - _{IdPredmetu,_ _Semestr}_+    * `{__IdStudenta__, IdPredmetu}` 
 +    * `{__IdStudenta__, JmenoStudenta}` 
 +    * `{__IdPredmetu__, Semestr}`
  
-</markdown> 
 === Třetí normální forma (3NF) === === Třetí normální forma (3NF) ===
-<markdown> +  * Relace je v 3NF právě tehdy, když: 
-- Relace je v 3NF právě tehdy, když platí: +    * Je v **2NF** 
- - relace je v **2NF** +    * Neexistuje **tranzitivní závislost** mezi neklíčovými atributy. 
- - všechny neklíčové atributy musí být vzájemně nezávislé+    * 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 
  
-- Příklad: 
- - Mějme relaci _{__IdStudenta__, JmenoStudenta, Fakulta, Dekan} ta_ není ve **3NF**. Sice je ve **2NF**, ale atribut Dekan je funkčně závislý na _Fakulta_ a _Fakulta_ je funkčně závislá na _IdStudenta_ (předpokládáme, že student nemůže být současně studentem více fakult téže university) 
- - _IdStudenta_ není funkčně závislá na _Fakulta_. Atribut _Deka_n je tedy transitivně závislý na klíči. 
-- Řešení: 
- - Rozdělíme relaci do tabulek: 
- - _{__IdStudenta,_ _JmenoStudenta, Fakulta}_ 
- - _{Fakulta,_ _Dekan}_ 
-</markdown> 
 ===== Transakce ===== ===== Transakce =====
  
Line 359: Line 476:
  
 ==== Transakční zpracování ==== ==== Transakční zpracování ====
-<makrdown> +  * Transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data. 
-- transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data. +  * Transakce pracuje s konzistentní databází. 
-- Transakce pracuje s konzistentní databází. +  * Během spouštění transakce může být databáze v nekonzistentním stavu. 
-- Během spouštění transakce může být databáze v nekonzistentním stavu. +  * Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní. 
-- Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní. +  * Dva hlavní problémy:  
-- Dva hlavní problémy:  +    * Různé výpadky (např. chyba hardware nebo pád systému) 
- - Různé výpadky, např. chyba hardware nebo pád systému +    * Souběžné spouštění více transakcí 
- - Souběžné spouštění více transakci +
-</makrdown>+
 ==== ACID vlastnosti ==== ==== ACID vlastnosti ====
-<makrdown> +  * K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit: 
-- K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit: +    * **A**tomicity – transakce je atomická: buď se provede celá, nebo vůbec. 
- - **A**tomicity : transakce atomická - buď se podaří a provede se celá nebo nic. Nelze vykonat jen část transakce. +    * **C**onsistency – transakce zachovává konzistenci dat a integritní omezení. 
- - **C**onsistency : transakce - konkrétní transformace stavu, zachování invariant - integritní omezení. +    * **I**solation – transakce se navzájem neovlivňují (jako by běžely sériově). 
- - **I**solation : (isolace = serializovatelnost). I když jsou transakce vykonány zároveň, tak výsledek je stejný. jako by byly vykonány jedna po druhé. +    * **D**urability – po COMMIT jsou změny trvalé, přežijí i pád systému.
- - **D**urability : po úspěšném vykonání transakce (commit) jsou změny stavu databáze trvalé a to i v případě poruchy systému - zotavení chyb.+
  
-</makrdown> 
 ==== Akce ==== ==== Akce ====
-<makrdown> +  * **Akce na objektech:** `READ`, `WRITE`, `XLOCK`, `SLOCK`, `UNLOCK` 
-- **akce na objektech :** READ, WRITE, XLOCK, SLOCK, UNLOCK +  * **Globální akce:** `BEGIN`, `COMMIT`, `ROLLBACK` 
-- **akce globální :** BEGIN, COMMIT, ROLLBACK +
-</makrdown>+
 ==== Transakční historie ==== ==== Transakční historie ====
-<makrdown> +  * Posloupnost akcí několika transakcí, zachovávající jejich lokální pořadí. 
-- Posloupnost akcí několika transakcí, jež zachovává pořadí akcí, v němž byly prováděny +  * Historie (rozvrh) je **sériová**, pokud transakce probíhají jedna po druhé (žádné prokládání operací). 
-- Historie (rozvrh) se nazývá *sériová*, pokud jsou všechny kroky jedné transakce provedeny před všemi kroky druhé transakce. +
-</makrdown>+
 ==== Serializovatelnost ==== ==== Serializovatelnost ====
-<makrdown> +  * Teorie: transakce se skládají z akcí typu: 
-- Teorie: Nechť se transakce $T$ i skládá z následujících elementárních akcí: +    * `READ_i(A)` – čtení objektu `A` v transakci `T_i` 
- - $\mathrm{READ}_i(A)$ - čtení objektu $A$ v rámci transakce $T_i$ +    * `WRITE_i(A)` – zápis objektu `A` v transakci `T_i` 
- - $\mathrm{WRITE}_i(A)$ - zápis (přepis) objektu $A$ v rámci transakce $T_i$ +    * `ROLLBACK_i` – přerušení transakce `T_i` 
- - $\mathrm{ROLLBACK}_i(A)$ - přerušení transakce $T_i$ +    * `COMMIT_i` – potvrzení transakce `T_i`
- - $\mathrm{COMMIT}_i(A)$ - potvrzení transakce $T_i$ +
-- Jsou možné 4 případy:+
  
 +<markdown>
 |   |   |   | |   |   |   |
 |---|---|---| |---|---|---|
Line 402: Line 513:
 |WRITEI(A) - READJ(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| |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
 +</markdown>
  
 ==== Konflikty ==== ==== Konflikty ====
-- *WR konflikt* - jedna transakce data zapíše, druhá je čte předtím než byla commited, tzv. *dirty read* +  * **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data. 
-- *RW konflikt* - transakce čte data a druhá je zapíše předtím než byla ta první ukončena, tzv. *unrepeatable read* +  * **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí. 
-- *WW konflikt* - přepis dat, která ještě nebyla commited, tzv. *blind write* +  * **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace. 
-- Dvě historie jsou *konfliktově ekvivalentní*, pokud sdílí stejné konfliktní páry +  * **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry. 
-- Historie je *konfliktově uspořádatelná*, pokud je konfliktově ekvivalentní s nějakou sériovou historií +  * **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií. 
-- *Precedenční graf* je směrový graf, kde vrcholy jsou transakce a hrany jsou konfliktní páry mezi transakcemi +  * **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty. 
- - Pokud je acyklický, je historie sériově uspořádatelná +    * Pokud je **acyklický**, historie je serializovatelná. 
-</makrdown>+
 ==== Zamykání ==== ==== Zamykání ====
-<makrdown> +  * Způsob **pesimistické kontroly souběhu** pomocí zámků. 
-- Způsob tzv. *pesimistické kontroly* v plánovači transakcí +  * **Zamykací protokol** zajišťuje konfliktní serializovatelnost. 
-- *Zamykací protokol* je protokol, který zamyká entity tak, aby byla zabezpečena konfliktní serializovatelnost +  * Typy zámků: 
-- Dva druhy zámků +    * **XLOCK (exkluzivní zámek)** – pouze pro jednu transakci, umožňuje zápis a čtení. 
- - *Exkluzivní zámek* $X(A)$ je zámek, který může držet pouze jedna transakce, pouze transakce, která drží zámek $X(A)$, pak může přistupovat k entitě $A$ +    * **SLOCK (sdílený zámek)** – umožňuje více transakcím číst. 
- - *Sdílený zámek* $S(A)$ je zámek, který může být držen více transakcemi, ale umožňuje pouze zápis, nikoliv čtení +    * **UNLOCK** – uvolnění zámku. 
-- Navíc je definována operace odemykání $U(A)$ +
-</makrdown>+
 ==== Dvoufázové zamykání (2PL) ==== ==== Dvoufázové zamykání (2PL) ====
-<makrdown> +  * Transakce: 
-- Pokud transakce chce číst (zapisovat) entitu $A$, musí nejprve získat sdílený (exkluzivní) zámek na tuto entitu +    * Nejprve pouze **získává** zámky (růstová fáze). 
-- Transakce nesmí zažádat o zámek na entitu $A$ pokud jej předtím už uvolnila +    * Poté je **pouze uvolňuje** (klesající fáze). 
-- Zajišťuje acykličnost precedenčního grafu +  * Zajišťuje **serializovatelnost**, ale **nezajišťuje zotavitelnost** (možné kaskádové zrušení).
-- Nezajišťuje zotavitelnost (může se stále stát, že transakce uvolní všechny zámky, jiná po ní pokračuje a je ukončena a potom je první transakce přerušena) +
-</makrdown>+
  
 === Striktní dvoufázové zamykání (Strict 2PL) === === Striktní dvoufázové zamykání (Strict 2PL) ===
-<makrdown> +  * Všechny zámky jsou **drženy až do COMMIT/ROLLBACK**. 
-- Zajišťuje zotavitelnost a kaskádovité přerušování +  * Zajišťuje zotavitelnost i prevenci kaskádového přerušení. 
-- Všechny zámky může transakce pustit až poté co je ukončena + 
-</makrdown> +==== Uváznutí (Deadlock) ==== 
-==== Uváznutí (deadlock) ==== +  * Nastane, když každá transakce čeká na zámek držený jinou transakcí. 
-<makrdown> +  * Reprezentace pomocí **grafu čekání**: 
-- Situace, která nastane, když všechny transakce čekají až jiná transakce uvolní zámek +    * Vrcholy: transakce 
-- Lze identifikovat pomocí tzv. *grafu čekání* +    * Hrana `T₁ → T₂`: `T₁` čeká na zámek držený `T₂` 
- - Vrcholy jsou jednotlivé transakce +    * **Cyklus = deadlock** 
- - Hrana z $T_1$ do $T_2$ říká, že transakce $T_1$ čeká až $T_2$ uvolní zámek + 
- - Pokud je v grafu cyklus, došlo k uváznutí +=== Metody prevence a řešení uváznutí === 
-</makrdown> +  * **Detekce:** pomocí grafu čekání, přeruší se jedna transakce. 
-=== Metody prevence/řešení uváznutí === +  * **Prevence:** 
-<makrdown> +    * **Wait-Die:** starší čeká, mladší umírá (rollback). 
-- Přerušení transakce a restart +    * **Wound-Wait:** starší zabije mladší, jinak čeká. 
-- Detekce uváznutí pomocí grafu čekání a přerušení transakce na základě nějakého kritéria (například transakce, která vykonala nejméně práce) +  * **Strategie výběru oběti:** přeruší se transakce podle délky běhu, počtu zámků apod. 
-- Dvě strategie na předcházení uváznutí, využívá priority transakcí: +
- - *wait-die* - pokud má čekající transakce vyšší prioritu tak čeká dále, pokud ne, tak je ukončena +
- - *wound-wait* - pokud má čekající transakce vyšší prioritu tak ukončí transakci, která drží zámek, který potřebuje, jinak čeká dále +
-</makrdown>+
 === Coffmanovy podmínky === === Coffmanovy podmínky ===
-<makrdown> +Uváznutí může nastat, pokud platí všechny 4 podmínky: 
-- K uváznutí může nastat pokud platí všechny z následujících podmínek +  - **Vzájemné vyloučení** – prostředky nejsou sdílené. 
-1. *Vzájemné vyloučení* - zdroje nejsou plně sdíleny a jsou drženy exkluzivně +  - **Zadržení a čekání** – proces drží a zároveň žádá další. 
-2. *Držení zdrojů* - další zdroje mohou být vyžadovány i když už jsou jiné drženy +  - **Žádná preempce** – prostředky nejsou vynuceně odebrány. 
-3. *Žádná preempce* - zdroje mohou být vypuštěny pouze dobrovolně +  - **Kruhové čekání** – cyklická závislost v čekání. 
-4. *Kruhové čekání* - transakce čekají a vyžadují zdroje v kruhu +  * Pokud **aspoň jedna podmínka neplatí**, uváznutí nemůže nastat. 
-- Nenaplnění jakékoliv z těchto podmínek stačí na prevenci uváznutí +
-</makrdown>+
 ==== Fantom ==== ==== Fantom ====
-<makrdown> +  * Specifický problém u transakcí s dotazy přes množiny záznamů. 
-- Může nastat v databázi, kde jsou vkládány a mazány nové položky +  * Jedna transakce čte množinu řádků podle podmínky (např. WHERE cena < 1000). 
-- Jedna transakce pracuje s nějakou množinou entit, zatímco druhá transakce tuto množinu změní +  * Jiná transakce mezitím přidá nový záznam, který podmínce odpovídá. 
-- Může vést k nekonzistentní databázi +  * První transakce je **ovlivněna novým záznamem**, i když už měla dané zámky. 
-- Může nastat i při striktním dvoufázovém zamykání +  * Řešení: **zámky na rozsah (range locks)** – např. pomocí indexových struktur. 
-</makrdown>+

Trace:

Navigation

Playground

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