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/24 09:55] – [Fyzická vrstva] mistrjirka | statnice: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í, | + | ====== 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 | + | * Obvykle |
| - | * (číselné označení záznamů s časem stoupá). | + | * Nový záznam |
| - | ===== 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 | + | |
| - | příkazy | + | |
| - | * Transaction management | + | |
| - | * Administrace | + | ===== 3. Jazyk SQL ===== |
| + | Structured Query Language (SQL) je jazyk pro práci s relačními databázemi. Obsahuje příkazy | ||
| + | |||
| + | * Transaction management | ||
| + | * Administrace | ||
| ==== 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) === | + | |
| - | | + | * Název |
| - | | + | * Definice |
| - | | + | * Integritní omezení |
| - | | + | |
| - | | + | |
| - | * 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, | + | |
| - | * SELECT - Vybírá data z databáze, umožňuje výběr podmnožiny a řazení dat | + | |
| - | * SELECT + názvy | + | |
| - | * 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 | + | |
| - | * 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ů: | ||
| + | * 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/ | ||
| + | |||
| + | ==== 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, | ||
| + | * Zahrnuje: struktury na disku, indexy, správu stránek a mezipaměti | ||
| - | ==== Charakteristika ==== | ||
| - | < | ||
| - | - Specifikuje jak jsou databázové struktury implementovány ve specifickém prostředí | ||
| - | - Zahrnuje soubory, indexovací struktury a tak dále | ||
| - | </ | ||
| ==== Stránky, sloty a záznamy ==== | ==== Stránky, sloty a záznamy ==== | ||
| - | < | + | |
| - | - Záznamy jsou uloženy na disku v *blocích* (angl. *page*) fixní velikosti | + | |
| - | - Hardware přistupuje | + | |
| - | - Č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í | + | |
| - | - stránky bývají | + | * 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ů |
| - | </ | + | * Záznamy mohou mít **fixní** nebo **variabilní** velikost |
| ==== Buffer management ==== | ==== Buffer management ==== | ||
| - | < | + | |
| - | - *Buffer* | + | * **Buffer** = oblast |
| - | - Každý | + | * Každá stránka je mapována |
| - | </ | + | * Rámec obsahuje: |
| - | ==== Datové soubory | + | * počet referencí |
| - | < | + | * **dirty flag** – značí, že byla změněna a není ještě zapsána |
| - | - *Halda* | + | * Politiky výměny rámců: LRU, Clock, FIFO… |
| - | - Prázdné | + | |
| - | - Všechny operace | + | ==== Organizace datových souborů |
| - | - *Řazený soubor* | + | |
| - | - Rychlé vyhledávání (logaritmická složitost) | + | * **Halda** |
| - | - Pro vkládání | + | * Neuspořádané |
| - | - Ve všem kromě vyhledávání je pomalejší než halda | + | * Vkládání rychlé (O(1)), mazání vytváří volné |
| - | </ | + | * Volné |
| - | ==== Hashované soubory ==== | + | |
| - | < | + | |
| - | - Soubor je organizovaný | + | * **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 |
| - | - Výhodou je rychlé vyhledávání, | + | * Pomalé |
| - | - Většina operací má přibližně složitost $N/K$, kde $K$ je počet kapes | + | * Každá stránka |
| - | </ | + | |
| + | * **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ší, | ||
| ==== Indexové struktury ==== | ==== Indexové struktury ==== | ||
| - | < | + | |
| - | - *Index* | + | * **Index** – pomocná |
| - | - Obsahuje | + | |
| - | - Index může obsahovat celý záznam, pár klíče a odkazu na záznam, nebo pár klíče a seznamu odkazů | + | * Může být: |
| - | - Řazení indexovaných předmětů může být zachováno (*clustered indexing*) nebo nemusí (*unclustered indexing*) | + | * **clustered** – pořadí indexu odpovídá pořadí dat |
| - | </ | + | * **unclustered** – pořadí se neshoduje |
| - | ==== B$^+$-stromy ==== | + | * Typy indexu: |
| - | < | + | * **plný |
| - | - Rozšířený | + | * **klíč |
| - | - Logaritmická složitost | + | * **klíč + seznam ukazatelů** |
| - | - Garantuje využití alespoň 50% stránek | + | |
| - | - Oproti B-stromu jsou všechny klíč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 | + | ==== B⁺-stromy ==== |
| - | </ | + | |
| + | * Varianty | ||
| + | * Všechny záznamy v **listech**, | ||
| + | * 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 ==== | ==== 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, | ||
| + | * 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 závislosti `K' → A`, a získáme nový **minimální** klíč `K'`. | ||
| + | - Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2. | ||
| + | - Pokud už existuje, algoritmus končí. | ||
| + | |||
| + | ==== Normální formy ==== | ||
| + | |||
| + | === První normální forma (1NF) === | ||
| + | * Relace je v 1NF právě tehdy, když: | ||
| + | * Atributy jsou **atomické** (dále nedělitelné). | ||
| + | * Každý řádek tabulky je **jedinečný**. | ||
| + | * K řádkům lze přistupovat podle obsahu (klíčových) atributů. | ||
| + | |||
| + | * Relace **nesplňující** 1NF: | ||
| < | < | ||
| - | - Stejné jako hašovaný soubor, ale obsahuje pouze odkazy na záznamy | + | |**jmeno**|**prijmeni**|**adresa**| |
| + | |---|---|---| | ||
| + | |Josef|Novák|Technická 2, Praha 16627| | ||
| + | |Petr|Pan|Karlovo náměstí 13, Praha 12135| | ||
| </ | </ | ||
| - | ==== Bitmapy ==== | + | |
| + | * Relace **splňující** 1NF: | ||
| < | < | ||
| - | - Vhodné pro atributy, které mohou nabývat malého množství hodnot | + | |**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**| |
| - | - 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í | + | |Josef|Novák|Technivká|2|Praha|16627| |
| - | - Výhody | + | |Petr|Pan|Karlovo náměstí|13|Praha|12135| |
| - | - Nevýhody | + | |
| </ | </ | ||
| - | ===== Funkční závislosti | + | === 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í 3NF, které ještě **není** porušením BCNF: | ||
| + | * 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. | ||
| + | |||
