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/06/04 18:13] – [Entitní typy] silní -> silný el_dustostatnice: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 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í 3NF, které ještě **není** porušením BCNF: 
 +    * 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í ====
-<markdown> +  * 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 +
-</markdown>+
 ==== ACID vlastnosti ==== ==== ACID vlastnosti ====
-<markdown> +  * 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.+
  
-</markdown> 
 ==== Akce ==== ==== Akce ====
-<markdown> +  * **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 +
-</markdown>+
 ==== Transakční historie ==== ==== Transakční historie ====
-<markdown> +  * 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. +
-</markdown>+
 ==== Serializovatelnost ==== ==== 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> <markdown>
-- Teorie: Nechť se transakce $T$ i skládá z následujících elementárních akcí: 
- - $\mathrm{READ}_i(A)$ - čtení objektu $A$ v rámci transakce $T_i$ 
- - $\mathrm{WRITE}_i(A)$ - zápis (přepis) objektu $A$ v rámci transakce $T_i$ 
- - $\mathrm{ROLLBACK}_i(A)$ - přerušení transakce $T_i$ 
- - $\mathrm{COMMIT}_i(A)$ - potvrzení transakce $T_i$ 
-- Jsou možné 4 případy: 
- 
 |   |   |   | |   |   |   |
 |---|---|---| |---|---|---|
Line 403: Line 514:
 |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam| |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
 </markdown> </markdown>
 +
 ==== Konflikty ==== ==== Konflikty ====
-<markdown> +  * **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data. 
-- *WR konflikt* - jedna transakce data zapíše, druhá je čte předtím než byla commited, tzv. *dirty read* +  * **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí. 
-- *RW konflikt* - transakce čte data a druhá je zapíše předtím než byla ta první ukončena, tzv. *unrepeatable read* +  * **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace. 
-- *WW konflikt* - přepis dat, která ještě nebyla commited, tzv. *blind write* +  * **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry. 
-- Dvě historie jsou *konfliktově ekvivalentní*, pokud sdílí stejné konfliktní páry +  * **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií. 
-- Historie je *konfliktově uspořádatelná*, pokud je konfliktově ekvivalentní s nějakou sériovou historií +  * **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty. 
-- *Precedenční graf* je směrový graf, kde vrcholy jsou transakce a hrany jsou konfliktní páry mezi transakcemi +    * Pokud je **acyklický**, historie je serializovatelná. 
- - Pokud je acyklický, je historie sériově uspořádatelná +
-</markdown>+
 ==== Zamykání ==== ==== Zamykání ====
-<markdown> +  * 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)$ +
-</markdown>+
 ==== Dvoufázové zamykání (2PL) ==== ==== Dvoufázové zamykání (2PL) ====
-<markdown> +  * 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) +
-</markdown>+
  
 === Striktní dvoufázové zamykání (Strict 2PL) === === Striktní dvoufázové zamykání (Strict 2PL) ===
-<markdown> +  * 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 + 
-</markdown> +==== Uváznutí (Deadlock) ==== 
-==== Uváznutí (deadlock) ==== +  * Nastane, když každá transakce čeká na zámek držený jinou transakcí. 
-<markdown> +  * 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í === 
-</markdown> +  * **Detekce:** pomocí grafu čekání, přeruší se jedna transakce. 
-=== Metody prevence/řešení uváznutí === +  * **Prevence:** 
-<markdown> +    * **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 +
-</markdown>+
 === Coffmanovy podmínky === === Coffmanovy podmínky ===
-<markdown> +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í +
-</markdown>+
 ==== Fantom ==== ==== Fantom ====
-<markdown> +  * 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. 
-</markdown>+

Trace:

Navigation

Playground

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