Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b0b36dbs [2025/05/20 13:15] – [Relační databáze] mistrjirka | statnice: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í, | + | ====== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, |
| [[https:// | [[https:// | ||
| Line 11: | Line 11: | ||
| - | ===== Konceptuální modelování ===== | + | ===== 1. Konceptuální modelování ===== |
| - | ER (entitní typy, atributy, identifikátory, | + | **ER (entitní typy, atributy, identifikátory, |
| - | * ER diagramy | + | |
| - | * ER - Entity-relationship | + | 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í. |
| - | | + | |
| - | * Méně využíván než UML (for good fucking reason too) | + | |
| + | | ||
| + | * Pozor: neexistuje striktní standard notace, a proto může být reprezentace různá | ||
| ==== Entitní typy ==== | ==== Entitní typy ==== | ||
| - | Entita | + | Entita |
| - | * Silní | + | |
| - | * Slabý entitní typ - nemá plný identifikátor, | + | * **Silný |
| + | | ||
| ==== Atributy ==== | ==== Atributy ==== | ||
| - | * Vlastnost | + | * Vlastnosti |
| + | * 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Č]`) | ||
| {{: | {{: | ||
| - | * 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 nebo kombinace |
| - | * Rozdělení | + | * Rozlišujeme: |
| - | * Plné - atribut nebo skupina | + | |
| {{: | {{: | ||
| - | * Částečné | + | |
| {{: | {{: | ||
| ==== 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 | ||
| {{: | {{: | ||
| + | |||
| ==== 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 | ||
| {{: | {{: | ||
| ==== Logické modely ==== | ==== Logické modely ==== | ||
| - | * Proces logického modelování | + | Převádějí konceptuální schéma do technicky orientované reprezentace |
| - | * Výběr modelu | + | |
| - | * Tvorba logického schématu - transformace z konceptuálního schématu do logického | + | |
| - | === Tabulkový === | + | |
| - | * Struktura - řádky pro entitry | + | |
| - | * 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, | + | |
| - | * např.: xml dokumenty, json | + | |
| - | === Grafový === | + | |
| - | * Struktura vrcholy, hrany, atributy | + | |
| - | * Opearce - Obhcázení, | + | |
| - | * 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 | + | * Operace: výběr |
| - | * spolehlivosti, | + | * Typický zástupce: |
| - | * Databázový systém - informační systém obsahující databázi, DBMS, hardware, procesy, osoby... | + | |
| - | | + | |
| - | ==== Null hodnoty | + | === Objektový model === |
| - | * Vyjadřuje vhybející informaci | + | * Struktura: objekty s atributy, ukazatele mezi objekty. |
| - | * Operace | + | * 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í | + | === Stromový model === |
| - | referenční akce) * | + | * Struktura: uzly (vrcholy) s atributy, hrany jako vztahy. |
| - | * Entitní | + | * Hierarchická data – např. XML, JSON. |
| - | * Doménová | + | * Vhodné pro semi-strukturovaná data. |
| - | * Referenční – zabývají se vztahy dvou tabulek, | + | |
| - | * NOT NULL - hodnoty | + | === Grafový model === |
| - | * UNIQUE | + | * 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 | + | * Použití např.: RDF, FlockDB, sociální sítě. |
| - | * CHECK - definuje | + | |
| + | ==== 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), | ||
| + | * **relace** | ||
| + | * **atribut** | ||
| + | * 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ů**, | ||
| + | * 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íč**, | ||
| + | |||
| + | * Příklad: | ||
| + | * Uživatel(ID, | ||
| + | * 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ů)**, | ||
| + | * 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` 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í | ||
| + | |||
| + | * **Databáze** | ||
| + | * **DBMS (Database Management System)** | ||
| + | * 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** | ||
| + | |||
| + | ==== 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 | ||
| + | |||
| + | * **Typy omezení:** | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | |||
| + | * **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ě/ | ||
| + | * Akce: | ||
| + | * **CASCADE** – změna/ | ||
| + | * **SET NULL** – odpovídající hodnota se nastaví na NULL. | ||
| + | * **SET DEFAULT** – nastaví se výchozí hodnota. | ||
| + | * **NO ACTION** – akce se **neprovede**, | ||
| + | * **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, |
| - | * Obvykle se jedná o celočíselné | + | * Obvykle |
| - | * (číselné označení záznamů s časem stoupá). | + | * Nový záznam získá ID větší než předchozí, |
| - | ===== Jazyk SQL ===== | + | * Používají |
| - | ===== Fyzická vrstva | + | |
| - | ===== Funkční závislosti ===== | + | |
| + | |||
| + | ===== 3. Jazyk SQL ===== | ||
| + | Structured Query Language (SQL) je jazyk pro práci s relačními databázemi. Obsahuje příkazy DDL (Data Definition Language) pro definici schémat, DML (Data Manipulation Language) pro manipulaci s daty a další. SQL je case-insensitive. | ||
| + | |||
| + | * Transaction management | ||
| + | * Administrace databáze | ||
| + | |||
| + | ==== Definice schématu ==== | ||
| + | |||
| + | * **CREATE TABLE** – vytvoření tabulky | ||
| + | * Název tabulky | ||
| + | * Definice sloupců (název, datový typ, výchozí hodnota) | ||
| + | * Integritní omezení (PRIMARY KEY, NOT NULL, ...) | ||
| + | |||
| + | * **ALTER TABLE** – úprava existující tabulky | ||
| + | * RENAME TO | ||
| + | * ADD COLUMN, ALTER COLUMN, DROP COLUMN | ||
| + | * ADD CONSTRAINT, DROP CONSTRAINT | ||
| + | |||
| + | * **DROP TABLE** – odstranění tabulky | ||
| + | |||
| + | ==== Manipulace s daty (SELECT, INSERT, UPDATE, DELETE) ==== | ||
| + | |||
| + | * **INSERT INTO** – vkládá nové řádky | ||
| + | * **UPDATE** – mění existující záznamy | ||
| + | * **MERGE** – kombinace INSERT a UPDATE podle klíče | ||
| + | * **DELETE FROM** – maže záznamy | ||
| + | * **SELECT** – dotazy nad daty | ||
| + | * SELECT *, nebo konkrétní sloupce | ||
| + | * AS pro aliasy | ||
| + | * ALL, DISTINCT | ||
| + | * FROM, WHERE (včetně predikátů: | ||
| + | * GROUP BY, HAVING | ||
| + | * ORDER BY | ||
| + | |||
| + | * **EXPLAIN** – ukáže plán vykonání dotazu | ||
| + | * **SHOW** – zobrazí informace | ||
| + | |||
| + | ==== 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/ | ||
| + | |||
| + | ==== 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, | ||
| + | |||
| + | * Specifikuje, | ||
| + | * Zahrnuje: struktury na disku, indexy, správu stránek a mezipaměti | ||
| + | |||
| + | ==== Stránky, sloty a záznamy ==== | ||
| + | |||
| + | * Záznamy jsou uloženy na disku ve **stránkách (pages)** fixní velikosti | ||
| + | * Hardware přistupuje k celým stránkám – jak pro čtení, tak pro zápis | ||
| + | * Čas I/O na rotačních discích = doba hledání + rotační zpoždění + přenos | ||
| + | * Stránky jsou rozděleny na **sloty**, ve kterých jsou **záznamy** | ||
| + | * Každý záznam | ||
| + | * Stránky mají hlavičku s informací o obsazenosti slotů | ||
| + | * Záznamy mohou mít **fixní** nebo **variabilní** velikost | ||
| + | |||
| + | ==== Buffer management ==== | ||
| + | |||
| + | * **Buffer** = oblast hlavní paměti, kde jsou dočasně uloženy stránky z disku | ||
| + | * Každá stránka je mapována na **paměťový rámec** | ||
| + | * Rámec obsahuje: | ||
| + | * počet referencí | ||
| + | * **dirty flag** – značí, že byla změněna a není ještě zapsána na disk | ||
| + | * Politiky výměny rámců: LRU, Clock, FIFO… | ||
| + | |||
| + | ==== Organizace datových souborů ==== | ||
| + | |||
| + | * **Halda** | ||
| + | * Neuspořádané záznamy, hledání sekvenčně | ||
| + | * Vkládání rychlé | ||
| + | * Volné stránky spravovány seznamem/ | ||
| + | * Všechny ostatní operace O(n) | ||
| + | |||
| + | * **Seřazený soubor** | ||
| + | * Záznamy uspořádané podle klíče | ||
| + | * Vyhledávání – logaritmická složitost (např. binární vyhledávání) | ||
| + | * Pomalé vkládání a mazání – nutnost přesunu | ||
| + | * Každá stránka má rezervu pro nové záznamy | ||
| + | |||
| + | * **Hašovaný soubor** | ||
| + | * Rozdělen do tzv. **kapes (buckets)** podle hašovací funkce | ||
| + | * Při přeplnění kapsy: připojí se nová stránka (overflow) | ||
| + | * Operace O(1) v průměru, O(n) v nejhorším | ||
| + | * Paměťově náročnější, řešeno dynamickým hašováním | ||
| + | |||
| + | ==== Indexové struktury ==== | ||
| + | |||
| + | * **Index** – pomocná datová struktura pro urychlení dotazů | ||
| + | * Obsahuje klíče a odkazy na záznamy (RIDs) | ||
| + | * Může být: | ||
| + | * **clustered** – pořadí indexu odpovídá pořadí dat | ||
| + | * **unclustered** – pořadí se neshoduje | ||
| + | * Typy indexu: | ||
| + | * **plný | ||
| + | * **klíč + ukazatel na záznam** | ||
| + | * **klíč + seznam ukazatelů** | ||
| + | |||
| + | ==== B⁺-stromy ==== | ||
| + | |||
| + | * Varianty B-stromu optimalizované pro databáze | ||
| + | * Všechny záznamy v **listech**, | ||
| + | * Vnitřní uzly obsahují jen klíče pro navigaci | ||
| + | * Vkládá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 | ||
| + | * Každá hodnota má svůj **bitový vektor**, který ukazuje přítomnost | ||
| + | * Dotazy zpracovány bitovými operacemi (AND, OR…) | ||
| + | * Výhody: rychlost, kompaktnost, | ||
| + | * Nevýhody: nevhodné pro velké domény nebo rozsahové dotazy (O(n)) | ||
| + | |||
| + | |||
| + | ===== 5. Funkční závislosti ===== | ||
| + | **Funkční závislosti (definice, Armstrongovy axiomy), úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, redukovaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).** | ||
| + | |||
| + | * Funkční závislosti určují, jak se hodnoty atributů v tabulce vztahují. | ||
| + | * Jsou klíčové pro návrh databázového schématu a normalizaci. | ||
| + | |||
| + | ==== Definice | ||
| + | * Funkční závislost `X → Y`: hodnoty atributů `X` určují hodnoty atributů `Y`. | ||
| + | * Elementární závislost: na pravé straně je jediný atribut. | ||
| + | * Funkční ekvivalence: | ||
| + | |||
| + | ==== Armstrongovy axiomy | ||
| + | * Triviální závislost: `Y ⊆ X ⇒ X → Y` | ||
| + | * Tranzitivita: | ||
| + | * Kompozice: `X → Y ∧ X → Z ⇒ X → YZ` | ||
| + | * Dekompozice: | ||
| + | |||
| + | ==== Funkční uzávěr | ||
| + | * Uzávěr `F⁺`: všechny závislosti, | ||
| + | |||
| + | ==== Pokrytí a kanonické pokrytí | ||
| + | * Pokrytí `G` množiny `F`: `F⁺ = G⁺` | ||
| + | * Kanonické pokrytí: pokrytí obsahující jen elementární závislosti. | ||
| + | |||
| + | ==== Redundance a neredundantní pokrytí ==== | ||
| + | * Závislost `f` je redundantní v `F`, pokud `F \ {f}⁺ = F⁺` | ||
| + | * Neredundantní pokrytí: žádná závislost není redundantní. | ||
| + | |||
| + | ==== Uzávěr atributů ==== | ||
| + | * Uzávěr atributů `X⁺`: všechny atributy odvoditelné z `X` pomocí `F`. | ||
| + | * `X⁺ = A ⇒ X` je superklíč. | ||
| + | * Redukovaná závislost: žádné redundantní atributy na LHS. | ||
| + | * Klíč: minimální superklíč. | ||
| + | * Klíčový atribut: je v nějakém klíči. | ||
| + | |||
| + | ==== Minimální pokrytí ==== | ||
| + | * Neredundantní kanonické pokrytí s redukovanými závislostmi. | ||
| + | |||
| + | ==== Hledání klíče ==== | ||
| + | * Najdi `X` takové, že `X⁺ = A`, a žádný proper subset `X'` nemá tuto vlastnost. | ||
| + | |||
| + | ==== Lucchesi-Osbornův algoritmus ==== | ||
| + | * Algoritmus k nalezení **všech** klíčů relačního schématu. | ||
| + | - Najdeme jakýkoliv klíč `K`. | ||
| + | - Vybereme funkční závislost `X → y` z `F` takovou, že `y ∈ K`, nebo ukončíme algoritmus pokud taková neexistuje. | ||
| + | - Vytvoříme množinu `K' = X ∪ (K \ {y})`. | ||
| + | * Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč. | ||
| + | - Redukujeme levostranné atributy | ||
| + | - Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2. | ||
| + | - Pokud už existuje, algoritmus končí. | ||
| + | |||
| + | ==== Normální formy ==== | ||
| + | |||
| + | === První normální forma (1NF) === | ||
| + | * Relace je v 1NF právě tehdy, když: | ||
| + | * Atributy jsou **atomické** (dále nedělitelné). | ||
| + | * Každý řádek tabulky je **jedinečný**. | ||
| + | * K řádkům lze přistupovat podle obsahu (klíčových) atributů. | ||
| + | |||
| + | * Relace **nesplňující** 1NF: | ||
| + | < | ||
| + | |**jmeno**|**prijmeni**|**adresa**| | ||
| + | |---|---|---| | ||
| + | |Josef|Novák|Technická 2, Praha 16627| | ||
| + | |Petr|Pan|Karlovo náměstí 13, Praha 12135| | ||
| + | </ | ||
| + | |||
| + | * Relace **splňující** 1NF: | ||
| + | < | ||
| + | |**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**| | ||
| + | |---|---|---|---|---|---| | ||
| + | |Josef|Novák|Technivká|2|Praha|16627| | ||
| + | |Petr|Pan|Karlovo náměstí|13|Praha|12135| | ||
| + | </ | ||
| + | |||
| + | === Druhá normální forma (2NF) === | ||
| + | * Relace je v 2NF právě tehdy, když: | ||
| + | * Je v **1NF**. | ||
| + | * Každý **neklíčový atribut** je **plně funkčně závislý** na **celém** primárním klíči (ne pouze na části složeného klíče). | ||
| + | |||
| + | * Příklad: | ||
| + | * Relace `{__IdStudenta, | ||
| + | * Primární klíč: `{IdStudenta, | ||
| + | * `JmenoStudenta` závisí **jen** na `IdStudenta` | ||
| + | * `Semestr` závisí **jen** na `IdPredmetu` | ||
| + | |||
| + | * Řešení: Rozdělení do menších relací: | ||
| + | * `{__IdStudenta__, | ||
| + | * `{__IdStudenta__, | ||
| + | * `{__IdPredmetu__, | ||
| + | |||
| + | === Třetí normální forma (3NF) === | ||
| + | * Relace je v 3NF právě tehdy, když: | ||
| + | * Je v **2NF** | ||
| + | * Neexistuje **tranzitivní závislost** mezi neklíčovými atributy. | ||
| + | * Každá závislost `X → A`: `X` je superklíč nebo `A` je klíčový atribut. | ||
| + | |||
| + | * Příklad: | ||
| + | * Relace `{__IdStudenta__, | ||
| + | * `IdStudenta` → `Fakulta` | ||
| + | * `Fakulta` → `Dekan` | ||
| + | * `Dekan` je tedy **tranzitivně závislý** na `IdStudenta` | ||
| + | |||
| + | * Řešení: Rozdělení do: | ||
| + | * `{__IdStudenta__, | ||
| + | * `{__Fakulta__, | ||
| + | |||
| + | === 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, | ||
| + | |||
| + | * Příklad porušení BCNF, které ještě **není** porušením 3NF: | ||
| + | * Relace `{__StudentID__, | ||
| + | * `CourseID` → `Instructor` | ||
| + | * `CourseID` není superklíč ⇒ porušení BCNF | ||
| + | |||
| ===== Transakce ===== | ===== Transakce ===== | ||
| + | |||
| + | **Transakce (základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh, historie, uspořádatelnost, | ||
| + | |||
| + | ==== Transakční zpracování ==== | ||
| + | * Transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data. | ||
| + | * Transakce pracuje s konzistentní databází. | ||
| + | * Během spouštění transakce může být databáze v nekonzistentním stavu. | ||
| + | * Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní. | ||
| + | * Dva hlavní problémy: | ||
| + | * Různé výpadky (např. chyba hardware nebo pád systému) | ||
| + | * Souběžné spouštění více transakcí | ||
| + | |||
| + | ==== ACID vlastnosti ==== | ||
| + | * K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit: | ||
| + | * **A**tomicity – transakce je atomická: buď se provede celá, nebo vůbec. | ||
| + | * **C**onsistency – transakce zachovává konzistenci dat a integritní omezení. | ||
| + | * **I**solation – transakce se navzájem neovlivňují (jako by běžely sériově). | ||
| + | * **D**urability – po COMMIT jsou změny trvalé, přežijí i pád systému. | ||
| + | |||
| + | ==== Akce ==== | ||
| + | * **Akce na objektech: | ||
| + | * **Globální akce:** `BEGIN`, `COMMIT`, `ROLLBACK` | ||
| + | |||
| + | ==== Transakční historie ==== | ||
| + | * Posloupnost akcí několika transakcí, zachovávající jejich lokální pořadí. | ||
| + | * Historie (rozvrh) je **sériová**, | ||
| + | |||
| + | ==== 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` | ||
| + | |||
| + | < | ||
| + | | | ||
| + | |---|---|---| | ||
| + | |READI(A) - READJ(A)|Není konflikt|Na pořadí nezávisí| | ||
| + | |READI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam| | ||
| + | |WRITEI(A) - READJ(A)|**Konflikt**|Pořadí má význam| | ||
| + | |WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam| | ||
| + | </ | ||
| + | |||
| + | ==== Konflikty ==== | ||
| + | * **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data. | ||
| + | * **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí. | ||
| + | * **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace. | ||
| + | * **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry. | ||
| + | * **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií. | ||
| + | * **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty. | ||
| + | * Pokud je **acyklický**, | ||
| + | |||
| + | ==== Zamykání ==== | ||
| + | * Způsob **pesimistické kontroly souběhu** pomocí zámků. | ||
| + | * **Zamykací protokol** zajišťuje konfliktní serializovatelnost. | ||
| + | * Typy zámků: | ||
| + | * **XLOCK (exkluzivní zámek)** – pouze pro jednu transakci, umožňuje zápis a čtení. | ||
| + | * **SLOCK (sdílený zámek)** – umožňuje více transakcím číst. | ||
| + | * **UNLOCK** – uvolnění zámku. | ||
| + | |||
| + | ==== Dvoufázové zamykání (2PL) ==== | ||
| + | * Transakce: | ||
| + | * Nejprve pouze **získává** zámky (růstová fáze). | ||
| + | * Poté je **pouze uvolňuje** (klesající fáze). | ||
| + | * Zajišťuje **serializovatelnost**, | ||
| + | |||
| + | === Striktní dvoufázové zamykání (Strict 2PL) === | ||
| + | * Všechny zámky jsou **drženy až do COMMIT/ | ||
| + | * Zajišťuje zotavitelnost i prevenci kaskádového přerušení. | ||
| + | |||
| + | ==== Uváznutí (Deadlock) ==== | ||
| + | * Nastane, když každá transakce čeká na zámek držený jinou transakcí. | ||
| + | * Reprezentace pomocí **grafu čekání**: | ||
| + | * Vrcholy: transakce | ||
| + | * Hrana `T₁ → T₂`: `T₁` čeká na zámek držený `T₂` | ||
| + | * **Cyklus = deadlock** | ||
| + | |||
| + | === Metody prevence a řešení uváznutí === | ||
| + | * **Detekce: | ||
| + | * **Prevence: | ||
| + | * **Wait-Die: | ||
| + | * **Wound-Wait: | ||
| + | * **Strategie výběru oběti:** přeruší se transakce podle délky běhu, počtu zámků apod. | ||
| + | |||
| + | === Coffmanovy podmínky === | ||
| + | Uváznutí může nastat, pokud platí všechny 4 podmínky: | ||
| + | - **Vzájemné vyloučení** – prostředky nejsou sdílené. | ||
| + | - **Zadržení a čekání** – proces drží a zároveň žádá další. | ||
| + | - **Žádná preempce** – prostředky nejsou vynuceně odebrány. | ||
| + | - **Kruhové čekání** – cyklická závislost v čekání. | ||
| + | * Pokud **aspoň jedna podmínka neplatí**, uváznutí nemůže nastat. | ||
| + | |||
| + | ==== Fantom ==== | ||
| + | * Specifický problém u transakcí s dotazy přes množiny záznamů. | ||
| + | * Jedna transakce čte množinu řádků podle podmínky (např. WHERE cena < 1000). | ||
| + | * Jiná transakce mezitím přidá nový záznam, který podmínce odpovídá. | ||
| + | * První transakce je **ovlivněna novým záznamem**, | ||
| + | * Řešení: **zámky na rozsah (range locks)** – např. pomocí indexových struktur. | ||
| + | |||
