# 4. Databáze

Principy ukládání dat, databáze. Architektura relačních databází, dotazovací jazyk SQL a jeho části (definice, manipulace, transakce). Jazyk definice datového schématu, DDL. Jazyk manipulace s daty, DML. Relační algebra, integritní omezení, řízení transakcí. Indexování, hašování. Příklady z praxe pro vše výše uvedené. (PV003, PA152)

---

**Dáta** sú údaje, ktoré majú určitú výpovednú hodnotu.
- Môžu byť usporiadané (štruktúrované), ale aj nemusia byť
- Užívateľovi sú k dispozícií v rôznych formách
- Tabulky, grafy, súbory, obrazy, vektory, matice, ...

## Princípy ukladania dát, databáze

### Princípy ukladania dát

Dáta vieme ukladať do súborového systému v rámci **súborovej štruktúry** alebo do **databázového systému** (relačné, dokumentové, grafové, vektorové), ktorý dáta logicky zoskupuje a snaží sa zabezpečiť efektívny prístup k dátam z pohľadu rýchlosti a spolahlivosti a konzistencie dát.

**Súborový systém** využívame zvyčajne na ukladanie neštruktúrovaných dát alebo súborov, napríklad obrázky uploadované skrz webové rozhranie. Vieme využiť cloudové úložiská (Amazon S3 Cloud Storage), lokálne HDD/SSD disky, prípadne zoskupenie diskov skrz RAID. Súborový systém nám zabezpečuje operačný systém a zvolený súborový systém - napr. FAT32, NTFS, EXT4, Btrfs.

- Výhody: menšie systémové nároky, jednoduché na používanie aplikáciami
- Nevýhody: náročné na zaistenie konzistencie, nutnosť riešiť zamýkanie súborov, problematický prístup k transakciám (prepisovanie súborov a riešenie prístupových práv), horšia čitateľnosť a dokumentácia súborového systému

### Databáze

**Databáza** je usporiadaná množina dát.
- Prístup k uloženým dátam obstaráva **databázový menežmentový systém** (DBMS)
- Databáza spoločne s DBMS tvorí **databázový systém**
- Dáta vieme dotazovať pomocou dotazovacieho jazyka (napr. SQL)
- **Účelom** databázových systémov je **riešit problémy** efektivity, redundancie dát, inkonzistencie, integrity a bezpečnosti
- Štruktúry dát sú uložené oddelene od súborov na disku
- Prístup k dátam je možný len prostredníctvom DBMS
- Dáta je možné vyhodnocovať pomocou vhodných jazykov alebo metód
- Je umožnený prístup viacerých užívateľov, ich správa a oprávnenia
- Problémy inkonzistencie riešia **transakcie** a systém ich vyhodnocovania a plánovania
- Väčšinou chceme, aby transakcie spĺňali **ACID** vlastnosti [Riadenie transakcii](/4fglZcU1QnGSdEthNGIEEQ?#Riadenie-transakcií)

Rozlišujeme **typy** databázových systémov:

- Relačné
- dáta sú štruktúrované, ukladané v tabuľkách
- dáta podliehajú normálovým formám
- používa jazyk SQL, ktorý vychádza z relačnej algebry
- často používa dátové štruktúry ako napríklad B+ stromy, červeno-čierne stromy, R stromy
- používa modelovanie schém pomocou UML ERD diagramu

- Not only SQL (NoSQL)
- vznikli kvôli potrebe horizontálne škálovať
- XML databázy, MongoDB (document-based), Redis (caching, key-value)
- grafové, vektorové, dokumentové ...
- dáta nemusia mať nejakú štruktúru, nepodliehaju normám
- Napríklad MongoDB poskytuje ACID transakcie, ale nie je to bežné u iných DBMS
- v dnešnej dobe často podporované aj v relačných DBMS (Postgres, MSSQL)
- Podpora pre neštrukturovaný JSON, BSON
- CAP theorem
- Pre distribuovaný systém nie je možné poskytovať zároveň konzistenciu dát naprieč clustermi (Consistency), dostupnosť odpovedí node-ov (Availability) a toleranciu prerušenia komunikácie clusterov (Partition tolerance)
- NoSQL databázy používajú Eventual Consistency - ak nenastávajú po nejakú dobu zmeny, tak v tom momente sa stáva databáza konzistentnou
- NewSQL - relačné DBMS, kombinuje flexibilitu NoSQL pre OLTP
- Coachbase, VoltDB, CockroachDB
- Hybrid Transactional-Analytical Processing (HTAP)

Dáta môžu byť ukládané v rôznej orientácii, rozlišujeme kvôli efektivite operácií nad nimi:

- row-oriented
- OLTP (online transaction processing) - klasické RDBMS (MySQL, MSSQL, Postgres, MariaDB, SQLite)
- sú vhodné na rýchly prístup k filtrovaným dátam pomocou WHERE a INSERT nových riadkov
- column-oriented
- sú vhodné na OLAP - analytické databázy napr. DuckDB, RedShift, R dataframes, Pandas
- rýchly prístup k výsledkom projekcie - SELECT ... FROM, pridávanie stĺpcov
- majú lepšiu kompresiu - používajú Run-Length encoding, bitmapy

## Architektúra relačných databáz, dotazovací jazyk SQL a jeho časti (definícia, manipulácia, transakcia)

### Architektúra relačných databáz

**Model dát** je sada nástrojov pre popis dát (syntax a sémantika), vzťahov medzi dátami a podmienkami, ktoré nad nimi platia.

**Relačný model dát** je databázový model založený na **predikátovej logike**.
- Základným princípom je, že všetky dáta sú reprezentované pomocou $n$-árnych relácií
- Na dátach sa operuje pomocou **relačnej algebry**
- Databáze organizované pomocou relačného modelu sa nazývajú **relačné databáze**

**Relačný model dát** sa skladá z nasledujúcich častí:
- **Atribút** - charakteristika, vlastnosť objektu
- Popísaný nejakou **hodnotou**
- Hodnota atribútu má **dátový typ**
- **Doména** - neprázdna množina hodnôt dátového typu atribútu
- Súčasťou každej domény je hodnota $null$
- Doména určuje povolené hodnoty pre daný atribút
- **Relácia** - podmnožina kartézskeho súčinu $n$ domén
- Podmnožina $n$-tíc atribútov
- Nesmie obsahovať duplicitné relácie
- Pokiaľ rôzne relácie obsahujú rovnaký atribút, môže medzi nimi vzinknúť väzba
- Kedže je to množina, nezávisí na poradí $n$-tíc
- Prázdna relácia je validná
- **Relačná schéma** - $n$-tica atribútov
- Určuje názov a záhlavie tabuľky
- Koľko má stĺpcov a ako sa volajú
- **Tabuľka** je reprezentáciou relácie
- Prázdne schéma je zakázané

Relačná databáza je zložená z **tabuliek**, ktoré sú definované **relačnou schémou** a obsahujú $n$-tice **relácie**.

**Kľúč** je podmnožina atribútov, ktorých úlohou je jednoznačne **identifikovať** každú $n$-ticu v relácii.

Rozlišujeme nasledovné kľúče:
- **Superkľúč** - každá podmnožina atribútov, ktorá dokáže splniť podmienku kľúča
- **Kandidátsky kľúč** - minimálny superkľúč
- **Primárny kľúč** - jeden zvolený kandidátsky kľúč
- Pokiaľ sa primárny kľúč skladá z viacerých atribútov, nazýva sa **kompozitný**
- **Cudzí kľúč** - množina atribútov, ktorá je superkľúčom v inej relácii

### Dotazovací jazyk SQL a jeho časti (definícia, manipulácia, transakcia)

Ekvivalentom relačnej algebry je jazyk **SQL** (Structured Query Language).

**SQL** (Structured Query Language) je štandardizovaný **ne**procedurálny dotazovací jazyk používaný pre prácu s dátami v relačných databázach.
- Skladá sa z DDL, DML a DCL
- **DDL** (Data Definition Language) - podjazyk pre definíciu dát, slúži na **špecifikáciu relačnej schémy**
- **DML** (Data Manipulation Language) - podjazyk pre manipuláciu s dátami (výber, vkladanie, úpravu a mazanie = **CRUD operácie**)
- **DCL** (Data Control Language) - podjazyk pre riadenie práce s dátami (**správa transakcií**, oprávnenia)

SQL je často dopĺňaný o funkcionalitu v konkrétnych RDBMS - napr. MSSQL Transact-SQL, Oracle PL/SQL, Postgres PL/pgsql. Hovoríme o **dialektoch** SQL.

Príkazy SQL sa skladajú z nasledujúcich komponentov:
- **Príkaz** (statement)
- SELECT, UPDATE, DELETE, ...
- **Dotaz** (query)
- Príkaz, ktorý vracia reláciu
- SELECT
- **Klauzula** (clause)
- Jednotlivé komponenty príkazov alebo dotazov
- WHERE, GROUP BY, ...
- **Predikát** (predicate)
- Podmienka, ktorá obmedzuje účinky príkazu alebo dotazu
- Je vyhodnotená na základe troj-hodnotovej logiky (TRUE, FALSE, NULL)
- Súčasťou predikátu je **operátor**
- =,<,>, <=,>=
- BETWEEN
- LIKE
- IN, NOT IN
- IS, IS NOT
- LIKE
- **Výraz** (expression)
- Konštanta alebo funkcia vracajúca skalárnu hodnotu
- Textové reťazce sa uzatvárajú do jednoduchých uvodzoviek

SQL pracuje s údajmi o **dátových typoch**:
- char - text s pevnou dĺžkou
- varchar - text s premenlivou dĺžkou
- int - celé číslo
- real, float - reálne číslo
- date,time,timestamp - časový údaj
- numeric, decimal - číslo s pevnou dĺžkou celej a desatinnej časti
- uživateľsky definované (napr. Postgres)

## Jazyk definície datového schématu, DDL

**DDL** (Data Definition Language) - podjazyk pre definíciu dát, slúži na **špecifikáciu relačnej schémy**. Príkazy podjazyka DDL **definujú štruktúru relačnej schémy** (a iných objektov).

**Klauzula CREATE TABLE**

- Vytvorí novú relačnú schému (tabuľku) v databáze
- Špecifikuje názvy a typ jednotlivých atribútov

$$
\text{CREATE TABLE}\ r(a\ t, \ldots)
$$

**Klauzula ALTER TABLE**

- Upraví existujúcu tabuľku
- Operácia môže byť **ADD** alebo **DROP**
- Môže upravovať buď integritné obmedzenia **CONSTRAINT** alebo stĺpec **COLUMN**

$$
\text{ALTER TABLE}\ r\ \text{<ADD|DROP>}\ \text{<COLUMN|CONSTRAINT|INDEX>}\ a
$$

**Klauzula DROP TABLE, DROP VIEW**

- Vymaže existujúcu tabuľku, view

$$
\text{DROP TABLE|VIEW}\ r
$$

**Klauzula CREATE VIEW**

- Vytvorí pohľad na dáta - pomenovaný SELECT uložený v databáze, virtuálna tabuľka
- Možnosť vytvoriť materializovaný view - hodnota tabuľky sa vždy prepočíta vopred (pri zmene)

$$
\text{CREATE <MATERIALIZED> VIEW}\ r\ \text{AS SELECT}\ \ldots
$$

**Klauzula CREATE INDEX**

- Vytvorí index nad stĺpcom alebo stĺpcami v tabuľke, vieme určiť explicitne aj typ
- Zvyčajne vieme aj určiť, či má byt kľúč unikátny (UNIQUE) alebo parciálny (WHERE...)
- V Postgres vieme aj určiť typ indexu pomocou **USING** BTREE, HASH, BRIN, GIST...

$$
\text{CREATE <UNIQUE> INDEX}\ idx\ \text{ON}\ r\ (a,b,c\ldots)
$$

## Jazyk manipulácie s dátami, DML

**DML** (Data Manipulation Language) - podjazyk pre manipuláciu s dátami (výber, vkladanie, úpravu a mazanie = **CRUD operácie**). Výsledkom volania DML príkazov je relácia.
- Príkazy sa môžu vnorovať (SELECT FROM (SELECT FROM ...))
- Typicky využívame operátory SOME, ALL, UNIQUE, IN, NOT IN, EXISTS, NOT EXISTS

### CRUD operácie

Klauzula **AS**

- Zodpovedá operácii premenovania $\rho$
- Používa sa v klauzulách SELECT alebo JOIN
- Premenuje danú reláciu

**Klauzula SELECT**

- Zodpovedá operácii projekcie $\Pi$
- Je používaná k vypísaniu požadovaných atribútov relácie uvedené v klauzli **FROM**
- Zodpovedá operácii kartézskeho súčinu $\times$
- Voliteľne je možné pridať predikát **WHERE**
- Zodpovedá operácii selekcie $\sigma$
- Používame matematické operátory, logické operátory, IS NULL, IS NOT NULL, LIKE, ...
- Na konštanty alebo atribúty v klauzuli **SELECT** vieme aplikovať aritmetické operácie
- Na rozdiel od algebry povoluje duplicity
- Ak chceme vynútiť unikátne záznamy, použijeme klauzulu **SELECT DISTINCT**
- Ak nie, použijeme klauzulu **SELECT ALL** (default hodnota, nemusíme písať)

$$
\text{SELECT <DISTINCT|ALL>}\ a\ \text{FROM}\ r\ \text{WHERE}\ x
$$
**Klauzula INSERT**

- Zodpovedá operácii zjednotenie $\cup$
- Vloží záznam do tabuľky
- Zadané hodnoty musia spĺňať podmienky dátového typu a integrity údajov

$$
\text{INSERT INTO}\ r\ \text{VALUES}\ (a,b,c, \ldots)\
$$

**Klauzula UPDATE**

- Zodpovedá operácii výberu $\sigma$ a zjednotenia $\cup$
- Upraví ľubovolný počet záznamov tabuľky
- Nové hodnoty musia spĺňať podmienky dátového typu, integrity údajov
- Voliteľne je možné pridať predikát **WHERE**

$$
\text{UPDATE}\ r\ \text{SET}\ a=b\ \text{<WHERE}\ x \text{>}
$$

**Klauzula DELETE**

- Zodpovedá operácii výberu $\sigma$
- Odstráni ľubovolný počet záznamov tabuľky
- Voliteľne je možné pridať predikát **WHERE**
$$
\text{DELETE FROM}\ r\ \text{<WHERE}\ x \text{>}
$$

### Agregačné funkcie

**Klauzula GROUP BY**

- Zoskupí atribúty tabuľky, následne je možne vybrať len skupiny
- Na skupinách sa môžu aplikovať agregačné funkcie
- Miesto klauzule WHERE sa používa klauzula **HAVING**
- Agregačné funkcie sú:
- COUNT, AVG, SUM, MIN, MAX
- Ak vynecháme GROUP BY, implikuje sa každý atribút

$$
\text{SELECT}\ a\ \text{FROM}\ r\ \text{GROUP BY}\ a\ \text{<HAVING}\ x \text{>}
$$

### Spájanie tabuliek
**Klauzula NATURAL JOIN**

- Zodpovedá operácii natural join $\Join$
- Kombinácia sa robí na základe stĺpcov so spoločným názvom

$$
\text{SELECT}\ a\ \text{FROM}\ r\ \text{NATURAL JOIN}\ s
$$

**Klauzula INNER JOIN**
- Podobné ako NATURAL JOIN, ale musíme špecifikovať cez aké atribúty sa majú tabuľky spojiť klauzulou **ON**
- Duplicitné stĺpce sa premenujú automaticky
$$
\text{SELECT}\ a\ \text{FROM}\ r\ \text{INNER JOIN}\ s\ \text{ON}\ r.c=s.c
$$

**Klauzula OUTER JOIN**
- Zodpovedá operácii OUTER JOIN $⟖$
- V závislosti na strane sa určuje správanie pri hodnotnách NULL - či sa také riadky vynechajú alebo nie
- Môže byť: LEFT, RIGHT, FULL
$$
\text{SELECT}\ a\ \text{FROM}\ r\ \text{<LEFT|RIGHT|FULL>}\ \text{OUTER JOIN}\ s\ \text{ON}\ r.c=s.c
$$

### Ostatné

**Trigger** (spúštač) v databázi špecifikuje činnosti, ktoré sa majú previesť nad databázovou tabuľkou v prípade definovanej udalosti.
- Udalosťou je zvyčajne vloženie alebo zmazanie dát
- Klauzula UPDATE, DELETE, INSERT
- Prípadne ich kombinácia
- Volitelne sa môže špecifikovať podmienka **WHEN**
- Môže byť INSERTING, UPDATING, DELETING
- Procedúru, ktorá sa má spustiť začína klauzulou **BEGIN** a končí **END**
- Ak chceme aby sa vykonala pre každý riadok tabuľky, navyše vložíme klauzulu **FOR EACH ROW**
- Slúžia na zabezpečenie integrity dát v zložitých databázach
- Je to typ uloženej procedúry

$$
\text{CREATE TRIGGER}\ a\ \text{<BEFORE|AFTER|INSTEAD OF>}\ u\ \text{ON}\ r\ \text{WHEN}\ x
$$

**Uložená procedúra** je užívateľom zadefinovaný príkaz alebo dotaz, ktorý je uložený v databáze a je možné ho kedykoľvek zavolať.
- Majú svoje parametre a lokálne premenné (označované zavináčom)
- Voláme ich klauzulou **EXEC**
- Syntax je závislá na konkrétnom jadre databázy
- Výhody: potenciálne zrýchlenie vďaka plánovaniu, zaistenie transakcie, bezpečnosť
$$
\text{CREATE PROCEDURE}\ a\ @p=\ldots\ \text{AS}\ (...)\ \text{GO}
$$

## Relačná algebra, integritné obmedzenia, riadenie transakcií

### Relačná algebra

**Relačná algebra** je formálny dotazovací jazyk.
- Využíva **6 základných operácií**
- Vstupom operácií môže byť jedna alebo viac relácií a **výstupom je vždy jedna relácia**
- To znamená, že operácie sa dajú reťaziť alebo vnárať

**Operácie**:
- **Selekcia** $\sigma_p(r)=\{ t | t \in r \land P(t) \}$
- Výsledkom je relácia, ktorá spĺňa zadaný predikát $P$
- **Projekcia** $\Pi_{A_1...A_n}(R)$
- Výsledkom je relácia vymenovaných $n$ stĺpcov
- Operácia mení relačnú schému výstupnej tabuľky
- Duplicitné riadky sú odstránené
- **Zjednotenie** $r \cup s = \{ t | t \in r \lor t \in s \}$
- Výsledkom je zjednotenie obidvoch relácií
- Musí platiť, že relácie majú rovnakú aritu (počet atribútov) a kompatibilné domény
- **Rozdiel** $r - s = \{ t | t \in r \land t \notin s \}$
- Výsledkom je rozdiel dvoch relácií
- Musí platiť, že relácie majú rovnakú aritu (počet atribútov) a kompatibilné domény
- **Kartézsky súčin** $r \times s = \{ tq | t \in r \land q \in s \}$
- Výsledkom je kartézsky súčin dvoch relácií
- Musí platiť, že atribúty sú disjunktné - ak majú niektoré atribúty rovnaké meno, musia sa premenovať
- **Premenovanie** $\rho_x(r)$
- Vráti reláciu, ktorej meno a názvy stĺpcov sú potenciálne zmenené podľa $x$
- Príklad $\rho_{m(a,b,c,d)}(r)$ - premenuje $r$ na $m$ a stĺpce na $a,b,c,d$
- Musí platiť, že sa vždy vymenujú všetky názvy stĺpcov, aj keď nemeníme ich meno

**Rozšírené operácie**:
- **Zobecnená projekcia**
- Umožňuje používať v zozname projekcie aritmetické funkcie
- **Agregácia** ${}_{G_1...G_n}\ \mathcal{G}_{F_1(A_1)...F_m(A_m)}(r)$
- Aplikuje agregačnú funkciu $F$ na atribút $A$, pričom atribúty sa zoskupia podľa $G$
- Výsledkom je relácia, ktorá obsahuje pre každú skupinu iba jednu hodnotu
- V prípade, že všetky atribúty $G$ sú $null$, zoskupia sa podľa $null$
- Všetky operácie okrem $count$ vracajú na $null$ číslo $0$
- Agregačné funkcie: avg, min, max, sum, count

### Spojovanie relácií
Relácie spájame pomocou tzv. JOINov (spojení).
- JOIN zjednocuje $n$-tice relácií na základe prieniku hodnôt atribútov

Rozlišujeme druhy JOINov:
- **Natural join** $r \Join s$
- $n$-tice sa zjednotia na základe rovnako pomenovaných atribútov
- Príklad pre $R=(A,B,C,D)$ a $S=(E,B,D)$
- $R \Join S = (A,B,C,D,E)$
- $R \Join S = \Pi_{r.A,r.B,r.C,r.D,s.E}(\sigma_{r.B=s.B \land r.D =s.D}(r \times s))$
- **Outer join**
- Rozšírenie operácie Natural join
- Zabraňuje strate informácií tak, že pridá do výslednej relácie aj $n$-tice ktoré nepatria do spoločného prieniku
- Hodnoty nahradí za $null$
- Môže byť: Left $⟕$, Right $⟖$, Full $⟗$

### Integritné obmedzenia

**Integritné obmedzenie** chráni databázu voči náhodnému poškodeniu.
- Zabezpečujú, že oprávnené zmeny v databáze nevedú k stráte **konzistencie dát**

Zoznam integritných obmedzení:

- NOT NULL - atribút nemôže mať hodnotu NULL
- UNIQUE - každá hodnota atribútu musí byť unikátna
- PRIMARY KEY - definuje primárny kľúč tabuľky
- FOREIGN KEY - zaistí, aby hodnota zodpovedala hodnote kľúča v inej tabuľke
- Zabezpečuje referenčnú integritu
- CHECK - každá hodnota sa skontroluje zadanou podmienkou
- DEFAULT - implicitná hodnota atribútu
- INDEX - pomáha urýchliť databázu, ak často podľa hodnoty vyhľadávame

Príklad (MSSQL T-SQL):

CREATE TABLE person (
	p_id int NOT NULL PRIMARY KEY,
	op char(10) UNIQUE NOT NULL,
	name varchar(255) NOT NULL,
	species varchar(255) DEFAULT ‘human’,
	j_id int FOREIGN KEY REFERENCES job_table (j_id),
	CHECK (p_id > 0)
)

Integritu vieme obmedziť aj definovaním vlastného dátového typu pomocou **CREATE DOMAIN**.

### Riadenie transakcií

**Transakcia** je postupnosť operácií (DML príkazov), ktoré prevedú dátovú schému z jedného konzistentného stavu do druhého.
- Transakcia pracuje s databázou vždy v konzistentnom stave
- Počas vykonávania transakcie sa môže databáza dostať do nekonzistentného stavu ale na konci jej vyhodnotenia platí, že v konzistentnom stave zostane

Transakcia sa riadi pravidlami **ACID**:
- **A**tomicity - príkazy nad DB sa vykonajú všetky úspešne, alebo sa nevykonajú žiadne (COMMIT/ROLLBACK)
- **C**onsistency - po vykonaní príkazov sa neporušia žiadne integritné obmedzenia
- **I**solation - transakcie sú navzájom izolované, zvyčajne určujeme izolačné úrovne podľa potreby
- **D**urability - uložené dáta sa budú dať znova načítať v konzistentnom stave, aj po výskytu chyby (napr. výpadok elektriky, crash) - zvyčajne zaručené uložením na disk

Transakcia sa môže dostať do nasledujúcich **stavov**:
- **Aktívna** (Active)
- Transakcia je v tomto stave na začiatku vyhodnotenia
- Pokiaľ beží, tak v tomto stave zostáva
- **Čiastočne potvrdená** (Partially commited)
- Akonáhle bola vykonaná posledná operácia transakcie
- **Chybujúca** (Failed)
- Po zistení, že beh transakcie nemôže pokračovať
- **Zrušená** (Aborted)
- Potom, čo bola transakcia zrušená a databáza bola vrátená do pôvodného stavu
- **Potvrdená** (Commited)
- Po úspešnom dokončení

Transakcie vieme izolovať v rôznych **úrovniach izolácie**:
- **Read Uncommited**
- Najtolerantnejšia úroveň
- Transakcia vidí zmeny ostatných transakcií okamžite
- Môže nastať problém čítania SELECT nepotvrdených (uncommited) údajov - **dirty read**
- Dva po sebe volané dotazy SELECT vrátia rôzne výsledky - **problém neopakovateľného čítania** (non-repeatable read)
- Po opakovam volaní SELECT nám pribúdaj/miznú riadky - **fantómové dáta** (phantom data)
- **Read Commited**
- Transakcia vidí dáta zmenené konkurentnou transakciou až po potvrdení (commited transaction)
- Rieši problém s **dirty read**s
- **Repeatable Read**
- Je zaručené, že v priebehu transakcie nemôže dojsť k problému neopakovateľného čítania
- Rieši **non-repeatable read**
- **Serializable**
- Najvyššia úroveň zabezpečenia izolácie transakcií
- Pokiaľ sa detekuje, že iná konkurentná transakcia je nad objektom (row, column, table) už potvrdená (commited), zruší sa (rollback)
- Transakcie teda bežia v podstate jedna po druhej (serialized)
- Opravuje **problém fantómov**, ale zamedzuje urýchlovacie triky (read-locking, write-locking, snapshotting)

Vlastnosti transakcií atomickosti (Atomic) a trvanlivosti (Durability) sú implementované pomocou **tieňovej databázy** (shadowing).
- Transakcia sa vykonáva na tieňovej verzii
- V prípade chyby sa tieňová vymaže, inak sa stane tou skutočnou

Transakcie sa môžu spracovávať **paralelne** (súbežne).
- Databáza vytvára pre súbežné transakcie **plán** (schedule) ich spracovania, ktorý musí byť serializovateľný
- Plán môže byť conflict alebo view serializable
- Conflict serializable - kontroluje sa graf závislostí čítaní a zápisov, ak existuje sériový plán volania transakcií (neexistuje cyklus), tak máme garantované, že po vykonaní akéhokoľvek sériového plánu budú dáta v konzistentnom stave a s minimálnym lockovaním objektov databázy (vysoká priepustnosť operácií)
- View serializable - relaxuje podmienku cyklov v conflict serializable pláne, kontroluje sa iba poradie read-write operácií na začiatku, počas behu, a na konci transakcií
- V plánoch nás zaujímajú iba operácie čítania a zápisu
- Paralelný výpočet je rýchlejší, ale môže dojsť k problémom ako napr. deadlock (cyklická závislosť)

## Indexovanie a hashovanie

### Indexovanie
**Indexovanie** je proces, vďaka ktorému zrýchlime prístup k údajom za cenu spomalenia operácií vkladania či odstránenia, ktoré menia dáta indexovaných sĺpcov. Algoritmicky redukujeme počet sekvenčných alebo náhodných prístupov na diskové médium.
- Indexovaný stĺpec má priradenú **indexovaciu tabuľku** - zvyčajne omnoho menšiu než súbor celej tabuľky
- Indexy môžu byť buď **zoradené** (ordered) alebo **hashované** (hashed)

### Zoradené indexy (ordered index)
- Indexové záznamy sú uložené podľa vyhľadávacieho kľúča
- **Primárny index** (primary index) - zoradený sekvenčný súbor
- Vyhľadávací kľúč určuje poradie záznamu v súbore
- Nazývaný aj ako zhlukujúci index (clustering index) - sú podľa neho fyzicky zoradené súbory na disku a môže byť iba jeden v tabuľke
- Nemusí byť vo všetkých prípadoch primárnym kľúčom
- Môže byť hustý (dense) a riedky (sparse)
- **Sekundárny index** (secondary index)
- Vyhľadávací kľúč určuje iné poradie než v zoradenom sekvenčnom súbore
- Nazývaný nezhlukujúci index (non-clustering index)
- Môže byť iba hustý (dense)

Index je **hustý (dense)** práve vtedy, ak existuje indexový záznam pre každú hodnotu v tabuľke.
- Rovnaké hodnoty sa v indexe neopakujú
- Má za následok veľký overhead pri INSERT a DELETE operáciách
- Na druhú stranu je rýchlejší pri operáciách JOIN, WHERE oproti sparse index

Index je **riedky (sparse)** práve vtedy, ak indexový záznam existuje iba pre niektoré hodnoty v tabuľke.
- Musíme najprv nájsť najbližší indexový záznam k našej vyhľadávanej položke
- Následne musíme prechádzať tabuľku sekvenčne
- Zvyčajne pomalší ako dense index ale zaberá menej miesta na disku (ale viacej v RAM)

**Viacúrovňový index (hierarchical index)** používame vtedy, ak sa primárny index nevojde do operačnej pamäte RAM.
- Z primárneho indexu sa spraví niekoľko riedkych (sparse) indexov
- Proces opakujeme ľubovolne-krát

Najpoužívanejšou indexovou štruktúrou v databázach sú **B+ stromy**.
- Jedná sa o viacúrovňový index (hierarchical index) v tvare vyváženého $n$-árneho stromu

Samotné dáta sa ukladajú rôznym spôsobom - napr. v Postgres sú to 8KB stránkovacie súbory, ktoré sú indexované zvoleným indexom.

### Hashované indexy (hash index)
Pri **hashovanom indexe** získavame **kyblíky** (buckets), do ktorých spadajú vyhľadávacie kľúče.
- Sú neefektívne pri vyhľadávaní rozsahov (WHERE a.x BIGGER, LESS THAN b.y)
- Rozlišujeme dynamické a statické hashovanie
- Dynamické umožňuje dynamicky meniť svoju hashovaciu funkciu podľa potrieb velkosti databázy
- Vzniká problém pretečenia kyblíkov (overflow) a kolízií (collisions)
- Riešené cez overflow chaining - closed hashing

**Hashovacia funkcia** je funkcia, ktorá prevádza množinu vyhľadávacích kľúčov na množinu adries jednotlivých kyblíkov.
- Používa sa ako pri vyhľadávaní, tak aj pri pridávaní a mazaní záznamov
- Ideálna hashovacia funkcia je rovnomerná, každý kýblik ma rovnaký počet priradených záznamov
- Snažíme sa minimalizovať možnosť kolízií (slabá, silná bezkolíznosť)

### Využitie pri JOIN operáciách

Indexovanie sa používa pri operáciách:
- Indexed nested-loop join
- Každej $n$-tici nájde druhú pomocou indexu
- Na rozdiel od naivného nested loop joinu nám zlepšuje zložitosť na $O(|R|log|S|)$
- Vhodné aj pre non-equi joins (ON a = b WHERE a.x BIGGER, LESS THAN b.y)
- Merge join
- Relácie sa zoradia podľa indexov a potom sa spoja
- Používa sa na equi-join - podmienky WHERE a = b

Hashovanie sa využíva pri operácii Hash join.
- $n$-tice sa navzájom porovnávajú pomocou obsahu kyblíkov
- Vhodné pre JOIN veľkých tabuliek, dobrá zložitosť $O(R+S)$ ale veľký overhead (najmä RAM)
- Dá sa paralelizovať
- Nevyžaduje indexy na porovnávaných stĺpcoch