Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b0b36dbs [2025/05/24 09:55] – [Fyzická vrstva] mistrjirka
+++ statnice:bakalar:b0b36dbs [2026/06/16 21:50] (current) – [Boyce-Coddova normální forma (BCNF)] badinmic
@@ Line 1: / Line 1: @@
-==== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, objektově-relační mapování, noSQL databáze. ====
+====== Konceptuální a logický datový model, dotazovací jazyk SQL, transakční zpracování, objektově-relační mapování, noSQL databá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]]
@@ 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 ====
-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 ====
-  * 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}}
-  * 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 ====
-  * 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}}
-    * Čá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}}
 ==== 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}}
 ==== 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}}
 ==== 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 ====
-  * 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 ====
-=== 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 ====
-<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 ====
-<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 ====
-<markdown>
-- *Index* je pomocná struktura, která poskytuje rychlé vyhledávání na základě hledaných klíčů
+  * **Index** – pomocná datová struktura pro urychlení dotazů
-- Obsahuje typicky jenom klíče a odkazy k záznamům, vyžaduje proto výrazně méně místa než datové soubory
+    * Obsahuje klíče a odkazy na záznamy (RIDs)
-- 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
+    * 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
-</markdown>
+      * **unclustered** – pořadí se neshoduje
-==== B$^+$-stromy ====
+  * Typy indexu:
-<markdown>
+    * **plný záznam**
-- Rozšířený B-strom
+    * **klíč + ukazatel na záznam**
-- Logaritmická složitost pro vkládání, vyhledávání podle rovnosti a mazání podle rovnosti
+    * **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 ====
-</markdown>
+  * Varianty B-stromu optimalizované pro databáze
+  * Všechny záznamy v **listech**, které jsou propojeny (pro rozsahové dotazy)
+  * Vnitřní uzly obsahují jen klíče pro navigaci
+  * Vkládání, vyhledávání a mazání: O(log n)
+  * Využití alespoň 50 % kapacity uzlů
 ==== Hašovaný index ====
+  * Princip stejný jako u hašovaných souborů
+  * Neobsahuje data, ale pouze ukazatele na záznamy
+  * Rychlé vyhledávání podle rovnosti
+  * Nevhodné pro rozsahové dotazy
+==== Bitmapový index ====
+  * Efektivní pro atributy s malým počtem možných hodnot
+  * Každá hodnota má svůj **bitový vektor**, který ukazuje přítomnost
+  * Dotazy zpracovány bitovými operacemi (AND, OR…)
+  * Výhody: rychlost, kompaktnost, paralelizovatelnost
+  * Nevýhody: nevhodné pro velké domény nebo rozsahové dotazy (O(n))
+===== 5. Funkční závislosti =====
+**Funkční závislosti (definice, Armstrongovy axiomy), úpravy závislostí (funkční uzávěr, pokrytí, kanonické pokrytí, redundantní závislost, neredundantní pokrytí, atributový uzávěr, redukovaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn). Normální formy (první, druhá, třetí, Boyceho-Coddova).**
+  * Funkční závislosti určují, jak se hodnoty atributů v tabulce vztahují.
+  * Jsou klíčové pro návrh databázového schématu a normalizaci.
+==== Definice ====
+  * Funkční závislost `X → Y`: hodnoty atributů `X` určují hodnoty atributů `Y`.
+  * Elementární závislost: na pravé straně je jediný atribut.
+  * Funkční ekvivalence: `X ↔ Y` pokud `X → Y` a `Y → X`.
+==== Armstrongovy axiomy ====
+  * Triviální závislost: `Y ⊆ X ⇒ X → Y`
+  * Tranzitivita: `X → Y ∧ Y → Z ⇒ X → Z`
+  * Kompozice: `X → Y ∧ X → Z ⇒ X → YZ`
+  * Dekompozice: `X → YZ ⇒ X → Y ∧ X → Z`
+==== Funkční uzávěr ====
+  * Uzávěr `F⁺`: všechny závislosti, které lze odvodit z `F` pomocí axiomů.
+==== Pokrytí a kanonické pokrytí ====
+  * Pokrytí `G` množiny `F`: `F⁺ = G⁺`
+  * Kanonické pokrytí: pokrytí obsahující jen elementární závislosti.
+==== Redundance a neredundantní pokrytí ====
+  * Závislost `f` je redundantní v `F`, pokud `F \ {f}⁺ = F⁺`
+  * Neredundantní pokrytí: žádná závislost není redundantní.
+==== Uzávěr atributů ====
+  * Uzávěr atributů `X⁺`: všechny atributy odvoditelné z `X` pomocí `F`.
+  * `X⁺ = A ⇒ X` je superklíč.
+  * Redukovaná závislost: žádné redundantní atributy na LHS.
+  * Klíč: minimální superklíč.
+  * Klíčový atribut: je v nějakém klíči.
+==== Minimální pokrytí ====
+  * Neredundantní kanonické pokrytí s redukovanými závislostmi.
+==== Hledání klíče ====
+  * Najdi `X` takové, že `X⁺ = A`, a žádný proper subset `X'` nemá tuto vlastnost.
+==== Lucchesi-Osbornův algoritmus ====
+  * Algoritmus k nalezení **všech** klíčů relačního schématu.
+  - Najdeme jakýkoliv klíč `K`.
+  - Vybereme funkční závislost `X → y` z `F` takovou, že `y ∈ K`, nebo ukončíme algoritmus pokud taková neexistuje.
+  - Vytvoříme množinu `K' = X ∪ (K \ {y})`.
+     * Jelikož platí `X ∪ (K \ {y}) → A`, je `K'` superklíč.
+  -  Redukujeme levostranné atributy závislosti `K' → A`, a získáme nový **minimální** klíč `K'`.
+  - Pokud `K'` není v množině dosud nalezených klíčů, přidáme jej, položíme `K := K'` a pokračujeme na krok 2.
+  - Pokud už existuje, algoritmus končí.
+==== Normální formy ====
+=== První normální forma (1NF) ===
+  * Relace je v 1NF právě tehdy, když:
+    * Atributy jsou **atomické** (dále nedělitelné).
+    * Každý řádek tabulky je **jedinečný**.
+    * K řádkům lze přistupovat podle obsahu (klíčových) atributů.
+  * Relace **nesplňující** 1NF:
 <markdown>
-- 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|
 </markdown>
-==== Bitmapy ====
+  * Relace **splňující** 1NF:
 <markdown>
-- 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 - efektivní, kompaktní, rychlé, snadno paralelizovatelné
+|Petr|Pan|Karlovo náměstí|13|Praha|12135|
-- 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 =====
+=== Druhá normální forma (2NF) ===
+  * Relace je v 2NF právě tehdy, když:
+    * Je v **1NF**.
+    * Každý **neklíčový atribut** je **plně funkčně závislý** na **celém** primárním klíči (ne pouze na části složeného klíče).
+  * Příklad:
+    * Relace `{__IdStudenta, IdPredmetu__, JmenoStudenta, Semestr}`
+    * Primární klíč: `{IdStudenta, IdPredmetu}`
+    * `JmenoStudenta` závisí **jen** na `IdStudenta`
+    * `Semestr` závisí **jen** na `IdPredmetu`
+  * Řešení: Rozdělení do menších relací:
+    * `{__IdStudenta__, IdPredmetu}`
+    * `{__IdStudenta__, JmenoStudenta}`
+    * `{__IdPredmetu__, Semestr}`
+=== Třetí normální forma (3NF) ===
+  * Relace je v 3NF právě tehdy, když:
+    * Je v **2NF**
+    * Neexistuje **tranzitivní závislost** mezi neklíčovými atributy.
+    * Každá závislost `X → A`: `X` je superklíč nebo `A` je klíčový atribut.
+  * Příklad:
+    * Relace `{__IdStudenta__, JmenoStudenta, Fakulta, Dekan}`
+    * `IdStudenta` → `Fakulta`
+    * `Fakulta` → `Dekan`
+    * `Dekan` je tedy **tranzitivně závislý** na `IdStudenta`
+  * Řešení: Rozdělení do:
+    * `{__IdStudenta__, JmenoStudenta, Fakulta}`
+    * `{__Fakulta__, Dekan}`
+=== Boyce-Coddova normální forma (BCNF) ===
+  * Relace je v **BCNF**, pokud:
+    * Je v 3NF
+    * Pro každou netriviální závislost `X → A` musí být `X` **superklíč**
+    * Přísnější než 3NF – eliminují se i závislosti, kde `A` je klíčový atribut, ale `X` není superklíč.
+  * Příklad porušení BCNF, které ještě **není** porušením 3NF:
+    * Relace `{__StudentID__, CourseID, Instructor}`
+    * `CourseID` → `Instructor`
+    * `CourseID` není superklíč ⇒ porušení BCNF
 ===== Transakce =====
+**Transakce (základní pojmy, ACID vlastnosti, BEGIN a COMMIT, rozvrh, historie, uspořádatelnost, serializovatelnost), konfliktová, uspořádatelnost (konflikty WR, RW, WW, precedenční graf), zamykací protokoly (dvoufázové a striktní dvoufázové zamykání), uváznutí (deadlock, graf čekání, Coffmanovy podmínky, strategie wait-die a wound-wait), fantom.**
+==== Transakční zpracování ====
+  * Transakce je posloupnost operací (část programu), která přistupuje a aktualizuje (mění) data.
+  * Transakce pracuje s konzistentní databází.
+  * Během spouštění transakce může být databáze v nekonzistentním stavu.
+  * Ve chvíli, kdy je transakce úspěšně ukončena, databáze musí být konzistentní.
+  * Dva hlavní problémy:
+    * Různé výpadky (např. chyba hardware nebo pád systému)
+    * Souběžné spouštění více transakcí
+==== ACID vlastnosti ====
+  * K zachování konzistence a integrity databáze, transakční mechanismus musí zajistit:
+    * **A**tomicity – transakce je atomická: buď se provede celá, nebo vůbec.
+    * **C**onsistency – transakce zachovává konzistenci dat a integritní omezení.
+    * **I**solation – transakce se navzájem neovlivňují (jako by běžely sériově).
+    * **D**urability – po COMMIT jsou změny trvalé, přežijí i pád systému.
+==== Akce ====
+  * **Akce na objektech:** `READ`, `WRITE`, `XLOCK`, `SLOCK`, `UNLOCK`
+  * **Globální akce:** `BEGIN`, `COMMIT`, `ROLLBACK`
+==== Transakční historie ====
+  * Posloupnost akcí několika transakcí, zachovávající jejich lokální pořadí.
+  * Historie (rozvrh) je **sériová**, pokud transakce probíhají jedna po druhé (žádné prokládání operací).
+==== Serializovatelnost ====
+  * Teorie: transakce se skládají z akcí typu:
+    * `READ_i(A)` – čtení objektu `A` v transakci `T_i`
+    * `WRITE_i(A)` – zápis objektu `A` v transakci `T_i`
+    * `ROLLBACK_i` – přerušení transakce `T_i`
+    * `COMMIT_i` – potvrzení transakce `T_i`
+<markdown>
+|   |   |   |
+|---|---|---|
+|READI(A) - READJ(A)|Není konflikt|Na pořadí nezávisí|
+|READI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
+|WRITEI(A) - READJ(A)|**Konflikt**|Pořadí má význam|
+|WRITEI(A) - WRITEJ(A)|**Konflikt**|Pořadí má význam|
+</markdown>
+==== Konflikty ====
+  * **WR konflikt (dirty read)** – jedna transakce zapíše, druhá čte nekompletní data.
+  * **RW konflikt (unrepeatable read)** – jedna čte, druhá přepíše data dřív, než první skončí.
+  * **WW konflikt (blind write)** – dvě transakce zapíší na stejné místo bez koordinace.
+  * **Konfliktová ekvivalence** – dvě historie sdílejí stejné konfliktní páry.
+  * **Konfliktová uspořádatelnost** – historie je konfliktově ekvivalentní se sériovou historií.
+  * **Precedenční graf** – směrový graf, kde vrcholy jsou transakce, hrany značí konflikty.
+    * Pokud je **acyklický**, historie je serializovatelná.
+==== Zamykání ====
+  * Způsob **pesimistické kontroly souběhu** pomocí zámků.
+  * **Zamykací protokol** zajišťuje konfliktní serializovatelnost.
+  * Typy zámků:
+    * **XLOCK (exkluzivní zámek)** – pouze pro jednu transakci, umožňuje zápis a čtení.
+    * **SLOCK (sdílený zámek)** – umožňuje více transakcím číst.
+    * **UNLOCK** – uvolnění zámku.
+==== Dvoufázové zamykání (2PL) ====
+  * Transakce:
+    * Nejprve pouze **získává** zámky (růstová fáze).
+    * Poté je **pouze uvolňuje** (klesající fáze).
+  * Zajišťuje **serializovatelnost**, ale **nezajišťuje zotavitelnost** (možné kaskádové zrušení).
+=== Striktní dvoufázové zamykání (Strict 2PL) ===
+  * Všechny zámky jsou **drženy až do COMMIT/ROLLBACK**.
+  * Zajišťuje zotavitelnost i prevenci kaskádového přerušení.
+==== Uváznutí (Deadlock) ====
+  * Nastane, když každá transakce čeká na zámek držený jinou transakcí.
+  * Reprezentace pomocí **grafu čekání**:
+    * Vrcholy: transakce
+    * Hrana `T₁ → T₂`: `T₁` čeká na zámek držený `T₂`
+    * **Cyklus = deadlock**
+=== Metody prevence a řešení uváznutí ===
+  * **Detekce:** pomocí grafu čekání, přeruší se jedna transakce.
+  * **Prevence:**
+    * **Wait-Die:** starší čeká, mladší umírá (rollback).
+    * **Wound-Wait:** starší zabije mladší, jinak čeká.
+  * **Strategie výběru oběti:** přeruší se transakce podle délky běhu, počtu zámků apod.
+=== Coffmanovy podmínky ===
+Uváznutí může nastat, pokud platí všechny 4 podmínky:
+  - **Vzájemné vyloučení** – prostředky nejsou sdílené.
+  - **Zadržení a čekání** – proces drží a zároveň žádá další.
+  - **Žádná preempce** – prostředky nejsou vynuceně odebrány.
+  - **Kruhové čekání** – cyklická závislost v čekání.
+  * Pokud **aspoň jedna podmínka neplatí**, uváznutí nemůže nastat.
+==== Fantom ====
+  * Specifický problém u transakcí s dotazy přes množiny záznamů.
+  * Jedna transakce čte množinu řádků podle podmínky (např. WHERE cena < 1000).
+  * Jiná transakce mezitím přidá nový záznam, který podmínce odpovídá.
+  * První transakce je **ovlivněna novým záznamem**, i když už měla dané zámky.
+  * Řešení: **zámky na rozsah (range locks)** – např. pomocí indexových struktur.

Trace:

Differences

Search

Navigation

Print/export

Tools

QR Code