statnice:bakalar:b0b36dbs

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== 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]]

  * **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.
  * **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.
  * **Jazyk SQL** – definice schématu. Manipulace s daty (SELECT, INSERT, UPDATE, DELETE). Spojování tabulek, predikáty, řazení, seskupování a agregace, množinové operace, vnořené dotazy. Pohledy (aktualizovatelnost, CHECK OPTION). Procedurální rozšíření (funkce, kurzory, triggery).
  * **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).
  * **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).
  * **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.


===== 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 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
  * 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)
==== Entitní typy ====
Entita je obecně osoba, projekt, nějaký objekt = třída v UML.
  * 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ě

==== Atributy ====
  * Vlastnost entity 
{{: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
  * Rozdělení 
    * Plné - atribut nebo skupina atributů jedné entity
{{:statnice:bakalar:pasted:20250520-124044.png}}
    * Částečné - pomocí vazby na jinou entitu, dovoluje pouze kardinalitu (1,1) 
{{:statnice:bakalar:pasted:20250520-124130.png}}

==== Vztahové typy ====

  * 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

  * 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í
    * 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


===== Relační databáze =====
  * Databáze - Logicky uspořádaný soubor souvisejících dat, obsahuje data, metadata, schéma, omezení integrity atd.
  * Database management system (DBMS) - Softwarový systém umožňující přístup do databáze, poskytuje mechanismy pro zajištění bezpečnosti a
  * spolehlivosti, souběžnost, integritu uložených dat, ...
  * 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 ====
  * Vyjadřuje vhybející informaci
  * Operace s null
  * 3 + null = null
  * 3 < null = uknown
==== Integritní omezení (NOT NULL, UNIQUE, PRIMARY KEY, CHECK, FOREIGN KEY a
referenční akce)  * 
  * Entitní – každý záznam v tabulce má platný a jedinečný primární klíč.
  * Doménová – zajišťují dodržování datových typů/domén definovaných u sloupců databázové tabulky
  * 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
    * UNIQUE - hodnoty musí být unikátní
    * PRIMARY KEY = NOT NULL + UNIQUE
    * FOREIGN KEY - hodnoty klíče v odkazující tabulce musí být v odkazované tabulce
    * CHECK - definuje se podmínka, která musí být splněna

=== 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é
  * 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
  * (číselné označení záznamů s časem stoupá).
===== Jazyk SQL =====
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

==== 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) ===
  * Příkazy pro získání dat z databáze a pro jejich úpravy
  * DML – Data Manipulation Language
  * INSERT INTO – vkládá do databáze nové řádky (záznamy)
  * 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


===== 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).**

==== 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
- Hardware přistupuje pouze k celým stránkám uloženým na disku (čtení i 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
- 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
- Záznamy mohou mít fixní nebo variabilní velikost
- 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
</markdown>
==== 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
- 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
</markdown>
==== Datové soubory ====
<markdown>
- *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
	- 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í
- *Ř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)
	- Pro vkládání má každá stránka prázdný overhead, pokud je zaplněn jsou použity nové stránky
	- Ve všem kromě vyhledávání je pomalejší než halda
</markdown>
==== Hashované soubory ====
<markdown>
- Soubor je organizovaný do tzv. *kapes* (anglicky *buckets*)
- To v jaké kapse je záznam uložený je rozhodnuto na základě hashovací funkce $f$
- Pokud je kapsa plná, je alokována nová stránka a propojena s kapsou formou spojového seznamu
- Výhodou je rychlé vyhledávání, nevýhodou je ale paměťová náročnost (řešeno dynamickým hashováním)
- Většina operací má přibližně složitost $N/K$, kde $K$ je počet kapes
</markdown>
==== Indexové struktury ====
<markdown>
- *Index* je pomocná struktura, která poskytuje rychlé vyhledávání na základě hledaných klíčů
- Obsahuje typicky jenom klíče a odkazy k záznamům, vyžaduje proto výrazně méně místa než datové soubory
- Index může obsahovat celý záznam, pár klíče a odkazu na záznam, nebo pár klíče a seznamu odkazů na záznam
- Řazení indexovaných předmětů může být zachováno (*clustered indexing*) nebo nemusí (*unclustered indexing*)
</markdown>
==== B$^+$-stromy ====
<markdown>
- Rozšířený B-strom
- Logaritmická složitost pro vkládání, vyhledávání podle rovnosti a mazání podle rovnosti
- Garantuje využití alespoň 50% stránek
	- Oproti B-stromu jsou všechny data (klíču jsou stále v B strom struktuře) v listech a stránky příslušné listům jsou provázány pro vykonávání dotazů založených na intervalech
</markdown>
==== Hashovaný index ====
<markdown>
- Stejné jako hašovaný soubor, ale obsahuje pouze odkazy na záznamy
</markdown>
==== Bitmapy ====
<markdown>
- Vhodné pro atributy, které mohou nabývat malého množství hodnot
- Každý atribut je realizován jako vektor bitů, kde $i$-tý bit popisuje jestli atribut nabývá $i$-té hodnoty nebo ne
- Dotazy lze pak provádět pomocí bitových masek a bitwise operací
- Výhody - efektivní, kompaktní, rychlé, snadno paralelizovatelné
- Nevýhody - Pouze pro atributy s doménou malé kardinality, pomalé dotazy na základě rozsahu (lineární v šířce rozsahu)
</markdown>

===== Funkční závislosti =====

**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, reduko-  
vaná závislost, minimální pokrytí). Hledání klíčů (nalezení prvního klíče, Lucchesi-Osborn).  
Normální formy (první, druhá, třetí, Boyceho-Coddova).**

==== Definice ====
<markdown>
- *Funkční závislost* $X\rightarrow Y$ nad schématem $R(A)$ je mapování $f_i:X_i\rightarrow Y_i$, kde $X_i,Y_i \subseteq A$
- U $X\rightarrow Y$ říkáme, že hodnoty v $X$ určují hodnoty v $Y$
- Pokud platí $X\leftarrow Y$ a $Y\leftarrow X$, pak řekneme, že $X\leftrightarrow Y$ jsou *funkčně ekvivalentní*
- Pokud je na pravé straně funkční závislosti jediný atribut $a$, mluvíme o *elementární funkční závislosti*
</markdown>
==== Armstrongovy axiomy ====
<markdown>
1. Triviální funkční závislost: $Y\subseteq X\Rightarrow X\rightarrow Y$
2. Tranzitivita: $(X\rightarrow Y\land Y\rightarrow Z)\Rightarrow X\rightarrow Z$
3. Kompozice: $(X\rightarrow Y\land X\rightarrow Z)\Rightarrow X\rightarrow YZ$
4. Dekompozice: $X\rightarrow YZ\Rightarrow(X\rightarrow Y\land X\rightarrow Z)$
</markdown>
==== Funkční uzávěr ====
<markdown>
- *Uzávěr množiny funkčních závislosti* $F$ je množina všech funkčních závislostí, které lze odvodit z funkčních závislostí v $F$ pomocí Armstrongových axiomů
- Značí se $F^+$
</markdown>
==== Pokrytí ====
<markdown>
- *Pokrytí množiny funkčních závislostí* $F$ je nějaká množina funkčních závislostí $G$ taková, že platí $F^+=G^+$
- *Kanonické pokrytí* je takové pokrytí, které obsahuje pouze elementární funkční závislosti
</markdown>
==== Redundance ====
<markdown>
- Funkční závislost $f$ je *redundantní* v množině $F$, pokud platí $(F-\{f\}^+=F^+)$
- To znamená, že $f$ je odvoditelné ze zbytku množiny $F$
- *Neredundantní pokrytí* množiny $F$ je pak takové pokrytí, které vznikne po odstranění všech redundantních funkčních závislostí z $F$
</markdown>
==== Uzávěr atributů ====
<markdown>
- *Uzávěr atributů* $X^+$ je podmnožina všech atributů z $A$, které lze odvodit z množiny atributů $X$ pomocí funkčních závislostí
- Pokud $X^+=A$, pak říkáme, že $X$ je *super-klíč* (nadklíč)
- Ve funkční závislosti $X\rightarrow Y$ je atribut $a$ *redundantní* když $Y\subseteq(X-a)^+$
- *Redukovaná fukční závislost* neobsahuje žádné redundantní atributy
- Pro $R(A)$ je *klíč* je takový super-klíč, kde je funkční závislost $K\rightarrow A$ redukovaná
- *Klíčový atribut* je atribut, který se nachází v jakémkoliv klíči (klíčů může být víc)
</markdown>
==== Minimální pokrytí ====
<markdown>
- *Minimální pokrytí* je neredundantní kanonické pokrytí, které obsahuje pouze redukované funkční závislosti
</markdown>

==== Nalezení jednoho klíče ====
<markdown>
- Z triviální funkčí závislosti $A\rightarrow A$ postupně odstraňujeme redundantní atributy na levé straně, dokud tam žádné nezůstanou
- Na levé straně funkčí závislosti pak dostaneme jeden z klíčů $A$
</markdown>
==== Lucchesi-Osbornův algoritmus ====
<markdown>
- Algoritmus k nalezení všech klíčů
1. Najdeme jakýkoliv klíč $K$
2. Vybereme funkční závislost $X\rightarrow y$ z $F$ takovou, že $y\in K$, nebo ukončíme algoritmus pokud neexistuje
3. Protože, platí $X\{K-y\}\rightarrow A$, $X\{K-y\}$ je super-klíč
4. Redukujeme $X\{K-y\}\rightarrow A$ a na levé straně dostaneme nový klíč $K'$, který je jiný než $K$
5. Pokud $K'$ ještě není v množině nalezených klíčů, uložíme jej, položíme $K:=K'$ a pokračujeme na krok 2. Jinak algoritmus končí
</markdown>
==== Normální formy ====

=== První normální forma (1NF) ===
<markdown>
- Relace je v 1NF právě tehdy, když platí současně:
	- atributy jsou atomické (dále nedělitelné)
	- k řádkům relace lze přistupovat podle obsahu (klíčových) atributů
	- řádky tabulky jsou jedinečné
- 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 v 1NF:

|   |   |   |   |   |   |
|---|---|---|---|---|---|
|**jmeno**|**prijmeni**|**ulice**|**cislo**|**mesto**|**psc**|
|Josef|Novák|Technivká|2|Praha|16627|
|Petr|Pan|Karlovo náměstí|13|Praha|12135|
</markdown>
=== Druhá normální forma (2NF) ===
<markdown>
- Relace je v 2NF právě tehdy, když platí zároveň:
	- relace je v 1NF
	- každý neklíčový atribut je plně závislý na každém kandidátním klíči
- Příklad:
	- Mějme relaci _{__IdStudenta, IdPredmetu__, JmenoStudenta, SemestrLZ},_ kde _IdStudenta_ a _IdPredmetu_ tvoří primární klíč.
	- Tato relace není v 2NF, protože _JmenoStudenta_ je závislé pouze na _IdStudenta_ a _SemestrLZ_ je závislé pouze na _IdPredmetu._
- Řešení:
	- Rozdělení relace do tří tabulek
		- _{__IdStudenta__,_ _IdPredmetu__}_
		- _{__IdStudenta,_ _JmenoStudenta}_
		- _{IdPredmetu,_ _Semestr}_

</markdown>
=== Třetí normální forma (3NF) ===
<markdown>
- Relace je v 3NF právě tehdy, když platí:
	- relace je v **2NF**
	- všechny neklíčové atributy musí být vzájemně nezávislé

- Příklad:
	- Mějme relaci _{__IdStudenta__, JmenoStudenta, Fakulta, Dekan} ta_ není ve **3NF**. Sice je ve **2NF**, ale atribut Dekan je funkčně závislý na _Fakulta_ a _Fakulta_ je funkčně závislá na _IdStudenta_ (předpokládáme, že student nemůže být současně studentem více fakult téže university)
	- _IdStudenta_ není funkčně závislá na _Fakulta_. Atribut _Deka_n je tedy transitivně závislý na klíči.
- Řešení:
	- Rozdělíme relaci do tabulek:
		- _{__IdStudenta,_ _JmenoStudenta, Fakulta}_
		- _{Fakulta,_ _Dekan}_
</markdown>
===== Transakce =====
Trace: • a4m33pal • b4b33rpz • b0b36dbs
Search

Navigation

Print/export

Tools

QR Code
