--- # System prepended metadata title: 04 Databáze --- # 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{}\ \text{}\ 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 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 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 }\ 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{} $$ **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{} $$ ### 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{} $$ ### 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{}\ \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{}\ 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): ```tsql 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