PB154 Základy databázových systémů

Úvod

DBMS (Database Management System)

softwarový balík spravující kolekce dat, která jsou propojena
vhodný a efektivní
využití: bankovnictví, letectví, školství, obchod, e-shopy

Souborové systémy

vývojový předchůdce uchovávání dat
problémy s konzistencí po úpravách, redundancí, paralelním přístupem uživatelů, atomičností, bezpečností...

Datové modely -- kolekce nástrojů sloužící k popisu dat, jejich vztahů, sémantik a omezení

relační model
model entit a vztahů
objektově orientovaných model
semistrukturovaný model (XML)
starší: síťové a hierarchické modely

DDL (Data Definition Language) -- notace pro reprezentaci schématu databáze, tabulky uchovávané v datovém slovníku, (create, drop table, insert, update)

DML (Data Manipulation Language) -- select, from, where

SQL (Structured Query Langue) -- neprocedurální jazyk, základní příkazy SELECT, FROM a WHERE

Správa uložiště (Storage management) -- problémy: přístup, organizace, indexování a hashování

transakce -- kolekce operací s jednou logickou funkci v databázové aplikaci

Databázové architektury

centralizované
klient-server
paralelní
distribuované

Relační model

atribut -- název sloupce v tabulce, je definován doménou a jménem

doména -- množina povolených hodnot atributu, atributy by měli být atomické

null -- speciální hodnota atributu

schéma -- záhlaví tabulky; uspořádaná n-tice atributů, prázdné relační schéma není povoleno!, př. r(R1) relace r mám relační schéma R1, R1 = jmeno, vek, adresa

relace -- celá tabulka; množina uspořádaných n-tic; podmnožina kartézského součinu domén atributů, které tvoří schéma dané relace, prázdná relace je povolena

uspořádaná n-tice -- řádek v tabulce, je prvkem relace

atomičnost -- atributy dále nelze dělit

null -- prázdná hodnota

kartézský součin -- množina (princip každý s každým)

databáze -- soubor relací

Klíče

superklíč -- libovolná podmnožina atributů jednoznačně určující entitu

kandidátský klíč -- minimální superklíč, neexistuje žádná jeho podmnožiny, která by byla superklíčem (nemůžeme z něj nic odebrat), důkaz, že se jedná o kandidátní klíč: je minimální, odvodíme z něj všechny ostatní atributy

primární klíč -- jeden z kandidátských klíčů

cizí klíč -- atribut, který nabývá hodnoty primárního klíče jiné relace nebo hodnoty NULL

Relační algebra

výsledkem dotazu v relační algebře je relace

Selekce σ

vybere n-tice (řádky), pro které je splněna podmínka p
př. σ KÓD=PB154(předmět) -> | PB154 | Základy DB systémů | 3 | zk. |

σ p (relace)

Projekce Π

vybírá sloupce
! vrací množinu (bez duplicit) !

Π atribut1, atribut2,... (relace)

Přejmenování ρ

změní název relace

ρ nove_jmeno_relace (stare_jmeno_relace)

změní relační schéma

ρ nove_jmeno_relace(atribut1, atribut2) (stare_jmeno_relace)

konstantní relace -- neměnná, př. ρ MOJE_PREDMETY(UCO, KOD) {(123, PB123), (456, VV001)}

Sjednocení ∪

relační schéma se přebírá z první relace
relace musí mít stejný počet atributů a stejnou doménu

Rozdíl --

relace musí mít stejný počet atributů a stejnou doménu

Přiřazení r ← E

přidat řádek: r ← r ∪ E
odebrat řádek: r ← r -- E
aktualizace záznamů: r ← π E1,E2, E3,... (relace)

Kartézský součin ×

všechno se vším
relační schéma = relační schéma 1. relace + relační schéma 2. relace
relace.atribut

Přirozené vnitřní spojení ▷◁

spojení přes stejné hodnoty
to, co je stejné se ve výsledku vyskytne pouze jednou
asociativní
pokud to neexistuje žádný společný atribut, chová se jako kartézský součin
lze vyjádřit pomocí selekce, projekce a kartézského součinu

Přirozené vnější spojení

chybějící části se doplní null hodnotami
plné =▷◁=
pravé -- z pravé relace se bere vše ▷◁=
levé -- z levé relace se bere vše =▷◁

Agregace G

pokud není specifikováno, podle čeho se má seskupovat, splaskne se celá funkce
agregační funkce: AVG, COUNT (počet řádků ve skupině), MIN, MAX, SUM (součet)
ignorují se hodnoty NULL (výjimka: COUNT(*))
vrací NULL pokud jsou na vstupu samé NULLy (výjimka: COUNT vrátí 0)

podle_ceho_seskupit G agregacni_funkce (relace)

Null hodnoty

= označení neznámé hodnoty nebo neexistujícího atributu

výsledkem aritmetické výrazu obsahujícího null je null
agregační funkce null ignorují

Porovnávání s null

výraz	vyhodnocení
true AND unknown	unknown
false AND unknown	false
unknown AND unknown	unknown
true OR unknown	true
false OR unknown	unknown
unknown OR unknown	unknown
NOT unknown	unknown

N-ticový relační kalkul

neprocedurální dotazový jazyk, ve kterém jsou dotazy ve tvaru {t|P(t)}
jedná se o množinu všech n-tic t, pro které je predikát P(t) pravdivý
formule se skládá z: množiny atributů a konstant, množiny porovnávacích operátorů (<, =, !=,...), množiny spojek (and, or, not), implikace a kvantifikátorů
pomocí příkazů lze generovat nekonečné množiny, př. {t|!t not in r}, pokud je doména jakéhokoli atributu relace r nekonečná

Doménový relační kalkul

neprocedurální dotazový jazyk, silou ekvivalentní n-ticovému relačnímu kalkulu
dotaz je ve tvaru {< x1, x2, ..., xn > | P(x1, x2,..., xn)}, kde x1, x2,..., xn jsou doménové proměnné, P je formule

SQL (Structure Query Language)

jedná se o tzv. DDL (Data Definition Language)
popisuje schéma relací, doménu hodnot atributů, integritní omezení a další
! nevrací množinu !
jazyk pro práci s daty v relačních databázích
postaven nad relační algebrou
příkazy lze zanořovat

skalární subquery -- je očekávána jedna hodnota

Doménové typy v SQL

char(n) -- přesně daná délka
varchar(n) -- omezenou pouze maximální délkou
int
smallint
numeric(p,d) -- p = přesnost, d = počet číslic za desetinnou čárkou
real, double precision -- přesnost závisí na stroji
float(n) -- přesnost (na n číslic) stanoví uživatel

Základní struktura dotazů

SELECT (projekce) -- SELECT * znamená vyber vše
- AVG (thing) -- průměr
- COUNT (počet), MIN, MAX, SUM
FROM (kartézský součin)
WHERE (selekci) -- využívá: and, or, not
- BETWEEN 900 AND 1000
relace GROUP BY atribut1, atribut2... -- atributy jsou nepovinné
HAVING podminka_s_agregacni_funkci
ORDERED BY -- následuje atribut a decs nebo asc (výchozí)
DISTINCT -- klíčové slovo, které je hned za SELECT, odstraní duplicity
ALL -- klíčové slovo, které je hned za SELECT, ponechá duplicity
SOME
LIKE -- WHERE name LIKE '%dar%' (pokud jméno obsahuje podřetězec dar)
ESCAPE -- LIKE '100 %' ECSAPE '' (obsahuje 100 %)* 'slovo%' -- začíná na slovo
- '%slovo%' -- obsahuje podřetězec slovo
- '_ _ _' -- slovo délky 3
- '_ _ _ %' -- slovo alespoň délky 3
IS NULL
IN -- množina obsahuje zvolený prvek (pes IN zvirata)
NOT IN
EXISTS
ANY()
EXCEPT, UNION, INTERSECT
CREATE TYPE -- vytvoření vlastního datového typu
CREATE DOMAIN -- vytvoření vlastní domény
CREATE INDEX -- vytvoření indexu
...

Manipulace s tabulkou

CREATE TABLE r (A1 D1, A2 D2, ... , An Dn, (integritní-omezení1), ..., (integritní-omezeník)) -- vytvoří relaci r, kde A je jméno atributu, D je datový typ hodnot v doméně atributu
puvodni_jmeno AS nove_jmeno - přejmenování
INSERT INTO tabulka VALUES('obsahsloupce1', 'obsah_sloupce2',...) -- vloží nový záznam do tabulky
DELETE FROM tabulka -- smaže veškerý obsah tabulky
DELETE FROM tabulka WHERE podminka -- smaže položky splňující podmínku
UPDATE r SET A1=e ... WHERE
DROP TABLE tabulka -- smaže tabulku a veškerý její obsah
ALTER TABLE -- změna tabulky:
- ALTER TABLE r ADD a d -- přidá nový atribut a a jeho doménu d
- ALTER TABLE r DROP a -- smaže atribut a z tabulky

Spojení

používají se jako subquery ve FROM části
(NATURAL) INNER JOIN - přirozené vnitřní spojení (spojí se pouze to, co je v obou relacích)
LEFT OUTER JOIN - levé vnější spojení (levá relace se vezme celá)
RIGHT OUTER JOIN - pravé vnější spojení (pravá relace se vezme celá)
FULL OUTER JOIN - úplné vnější spojení (obě relace jsou obsaženy, to co chybí je doplněno NULL hodnotami)
INNER JOIN ON podmínka
INNER JOIN USING (seznam atributů)

view -- relace, která je "virtuálně" zprostředkována uživateli, CREATE VIEW v AS query

blob (binary large object), clob (character large object) -- vrací pouze pointer, nikoli samotné data

trigger -- příkaz, který je vykonán automaticky systémem, jako vedlejší efekt modifikace databáze (INSERT, DELETE, UPDATE), může být omezen na určitý atribut, může se zreplikovat provedenou akci na další data, např. při změně výše DPH se automaticky přepočítá cena

Integritní omezení

UNIQUE -- unikátní záznamy z množiny
CHECK p -- p je predikát
NOT NULL
PRIMARY KEY

Datové typy -- datum a čas

DATE
TIME
TIMESTAMP
INTERVAL

RE model

(Entity-Relationship Model)

databáze může být reprezentována pomocí kolekce entit nebo vztahů mezi entitami

entita -- existující objekt rozlišitelný od ostatních, má atributy ("vlastnosti")

entitní množina -- množina entit stejného typu, které sdílejí stejné vlastnosti

vztah -- propojení více entit

množina vztahů -- matematická relace mezi 2 a více entitami, může k ní patřit nějaká vlastnost

stupeň množiny vztahů -- většinou binární (vztah mezi dvěma entitami)

kardinalita -- one to one, one to many, many to one, many to many

Atribut

jednoduchý (např. město) vs. složený (např. adresa)
jednohodnotový (např. jméno) vs. vícehodnotový (např. telefonní číslo)
odvozený -- vypočítá se z jiného atributu (např. věk)

E-R diagram

entitní množina = obdélník
množina vztahů = diamant
atributy jsou vypsány uvnitř obdélníku
primární klíč je podtržen
to, co je one má šipku; to, co je many šipku nemá
každá entita z entitní množiny musí mít alespoň jeden vztah z množiny vztahů = dvojtá čára kolem diamantu a vztahové čáry od dané entitní množiny

Slabá entitní množina

nemá primární klíč
její existence závisí na existenci identifikační entitní množiny
je propojena pomocí totálního one-to-many vztahu z identifikační do slabé entitní množiny
diamant je dvojitý
parciální klíč (discriminator) -- atributy rozlišující jednotlivé entity v slabé entitní množině, podtržení přerušovanou čarou
primární klíč je tvořen primárním klíčem silné entitní množiny a parciálním klíčem

specializace (top-down postup) -- rozklad jedné velké entitní množiny na menší

dědičnost atributů -- podřazená entitní množina dědí všechny atributy a vztahy ze své nadřazené entitní množiny, se kterou je propojena; OR -- šipky do nadřazené se po cestě spojí, XOR -- do nadřazené vedou dvě šipky

generalizace (bottom-up postup) -- kombinace více entitních množin, které sdílí stejné vlastnosti do nadřazené entitní množiny

agregace -- uzavření ER-diagramu do obdélníčku a napojení na další entitní množiny

UML (Unified Modeling Language) -- podobné ER diagramům

Normalizace schématu

1. Normální forma

atributy musí být atomické (nedělitelné)
př. adresa -> adresa_mesto, adresa_ulice, adresa_cislo

2. Normální forma

splňuje požadavky 1. NF
každý atribut je součástí kandidátního klíče
nebo není částečně závislý na žádném kandidátním klíči

3. Normální forma

splňuje požadavky 1. a 2. NF
atribut je součástí některého kandidátního klíče
nebo není tranzitivně závislý na žádném superklíči

Boyce-Coddova normální forma (BCNF)

splňuje požadavky 1., 2. i 3. NF
α → β je triviální závislost
α je superklíč
! nemusí zachovat funkční závislosti !
nemusíme kontrolovat ztrátovost

Funkční závislosti

Armstrongovy axiomy

pokud β ⊆ α, pak α -> β (reflexivita)
pokud α -> β, pak γ, α -> γ, β (rozšíření)
pokud α -> β a β -> γ, pak α -> γ (tranzitivita)

uzávěr funkčních závislostí -- z dané množiny funkčních závislostí vyvozujeme nové a tím postupně rozšiřujeme množinu, proces opakujeme, dokud dvě po sobě jdoucí iterace nevrátí stejný výsledek; využití: test superklíče, funkčních závislostí uzávěru F

Úložiště a souborové systémy

Klasifikace fyzických úložných médií

rychlost přístupu, cena za jednotku dat, spolehlivost
volatilní -- ztratí obsah po vypnutí
non-volatilní -- obsah zůstává i po vypnutí
spolehlivost zvýšíme redundancí
výkonnost zvýšíme paralelismem

Cache

nejrychlejší, nejdražší, volatilní
spravovaná HW sytému

Hlavní paměť

rychlý přístup, volatilní
malá nebo drahá pro uložení celé databáze

Flash paměť

přístup srovnatelný s hlavní pamětí, zápis a mazání je pomalé
data přežijí i při výpadku elektřiny
přežije pouze omezený počet přepisů
velmi rozšířené u různých zařízení (USB, fotoaparáty, mobily...)

Magnetické disky

dokáží uchovat celou databázi
pomalá, protože se data nejdřív přepíší na hlavní paměť
přímý přístup (nikoli sekvenční jako na magnetických páskách)
přežije selhání systému i elektřiny
čtecí hlava, sektory, cylindry, plotny
standardy diskového rozhraní: ARA, SATA, SCSI, SAS
parametry: přístupový čas (seek time, rotation latency), data-transfer rate, MTTF (Mean Time To Failure) -- čas, který by měl disk běžet bez selhání
výtahový algoritmus (rozvrhování)

RAID úrovně

Level 0: bez redundance
Level 1: zrcadlení disků
Level 2: Memory-Style Error-Correction Codes
Level 3: Bit-Interleaved Parity
Level 4: Block-Interleaved Parity
Level 5: Block-Interleaved Distributed Parity
Level 6: P+Q Redundance

...

Optické disky

non-volatilní, zápis a čtení je pomalejší než u magnetických disků
CD-ROM (640 MB), DVD (4.7--17 G), Blu-ray (27--54 GB)
CD-R, DVD-R, DVD+R, CD-RW, DVD-RW, DVD+RW, DVD-RAM)
juke-box

Pásková úložiště

non-volatilní, velmi pomalé (sekvenční přístup), velká kapacita (40--300 GB)
využití: zálohování, archivace dat

Hierarchie úložišť

primární úložiště -- nejrychlejší, volatilní (cache, hlavní paměť)
sekundární úložiště (on-line úložiště) -- non-volatilní, mírně rychlejší přístup (flash paměť, magnetické disky)
terciální úložiště (off-line úložiště) -- non-volatilní, pomalý přístup (magnetické pásky, optická úložiště)

Organizace souborů a záznamů

halda
sekvenční
hashování
multitable clustering file organization

Přístup v úložišti

buffer
LRU strategy (Last Recently Used)
Pinned block
Toss-immediate strategy
MRU strategy (Most recently used)

B+-stromy

n-ární strom, kde n značí počet pointerů z uzlu
klíčů je n-1
každý listový uzel je naplněn alespoň polovinou klíčů (zaokrouhleno nahoru)
každý vnitřní uzel má alespoň n/2 pointerů
vyvážené
všechny větve v B-stromech i B+-stromech mají stejnou délku
hodnoty klíčů v každém uzlu jsou uspořádané

Hashování

bucket
hashovací funkce by měla být uniformní (průměrný počet prvků je ve všech bucketech stejný) a náhodná
otevřené (na jeden index se uloží pouze jeden prvek) vs. zavřené (bucket = linked list) hashování
statické (mapuje hodnoty na omezený počet indexů) vs. dynamické (počet indexů se může v průběhu dynamicky měnit, např. extendable hashing) hashování

Zpracovávání dotazů

parsování a překlad -- překlad do interní formy a následně do relační algebry, kontrola syntaxe a verifikace vztahů
optimalizace -- vybere mezi všemi ekvivalentními plány evaluace ten s nejnižšími nároky (čas na zodpovězení dotazu: seeks, blocks transfers)
vyhodnocení -- plán evaluace dotazů

Operace selekce

Algoritmus A1

lineární prohledávání
file scan
projde každý blok souboru a ověří všechny záznamy, jestli nesplňují podmínku

Binární vyhledávání nemá smysl, protože data nejsou seřazena.

Algoritmus A2

primární index, rovnost klíče

Algoritmus A3

primární index, rovnost neklíče

Algoritmus A4

sekundární index, rovnost neklíče

Algoritmus A5

primární index, porovnání

Algoritmus A6

sekundární index, porovnání

Algoritmus A7

konjunkce selekce s využitím indexu

Algoritmus A8

konjunkce selekce s využitím složeného indexu

Algoritmus A9

konjunkce selekce průnikem identifikátorů

Algoritmus A10

disjunkce selekce sjednocením identifikátorů

Sorty

quicksort pro relace, které se vejdou do paměti
jinak externí merge sort

Externí merge-sort

vytvoř uspořádané části, i=0
- načti M (velikost paměti ve stránkách) bloků relace do paměti
- setřiď vnitřní paměťové bloky
- zapiš data a zvyš i
mergni části, N<M
- použij N bloků paměti na buffer vstupních částí + 1 blok na buffer výstup
- načti první blok každé části do buffer stránky
- opakuj: vyber první záznam (v setříděném pořadí) ze všech buffer stránek, zapiš jej na output buffer, smaž záznam z jeho vstupního bufferu, pokud jsou buffer stránky, načti další blok
- dokud nejsou všechny buffer stránky prázdné

Joiny

nested-loop join -- theta join (dva for vnořené cykly)
block nested-loop join -- (čtyři vnořené for cykly -- popárování bloků vnitřní a vnější relace)
indexed nested-loop join -- podobné jako nested-loop join, akorát používá k vyhledání vhodné n-tice z vnitřní relace index
merge-join
hash-join -- equi-joiny a natural joiny

Nested-Loop Join

Slouží k výpočtu theta joinu.

pro každou n-tici tr z relace r:
    pro každou n-tici ts z relace s:
        otestuj, jestli dvojce (tr,ts) splňuje podmínku theta,
        pokud ano, přidej jejich tr.ts do výsledku

r je vnější relace a s je vnitřní relace

Block Nested-Loop Join

To stejné jako Nested-Loop Join, akorát nejdřív dvěma vnořenými cykly prochází celé bloky relací a až pak z nich prochází n-tice.

Hash-join

Využívá se u equi-joinu a natural joinu.
Hashovací funkce h je využitá k rozdělení n-tic z obou relací.
Shodné atributy jsou přiřazeny do stejných bucketů, takže potom už stačí jen spojit odpovídající buckety.

Eliminace duplicit

hashování nebo třídění

Projekce

projekce na každé n-tici a eliminace duplicit

Agregace

podobné jako eliminace duplicit (třídění a hashování)

Množinové operace

třídění + merge-join nebo hash-join

...

Optimalizace dotazů

dynamické programování

Transakce

= jednotka vyhodnocování programu, který přistupuje a případně mění různé datové položky.

ACID (Atomicity, Consistency, Isolation, Durability)

atomičnost, konzistence, izolace, trvanlivost

Status transakce

aktivní
částečně committed
failed
zrušená
committed

rozvrhy

serializovatelnost -- jaké procesy mohou běžet současně, aniž by porušily ACID, proces je serializovatelný právě tehdy, když je precendenční graf acyklický

Úrovně konzistence v SQL-92

serializovatelné
repeatable read
read commited
read uncommited

Files

PB154.md

Latest commit

History