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é
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í
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
- výsledkem dotazu v relační algebře je relace
- 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)
- vybírá sloupce
- ! vrací množinu (bez duplicit) !
Π atribut1, atribut2,... (relace)
- 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)}
- relační schéma se přebírá z první relace
- relace musí mít stejný počet atributů a stejnou doménu
- relace musí mít stejný počet atributů a stejnou doménu
- přidat řádek:
r ← r ∪ E
- odebrat řádek:
r ← r -- E
- aktualizace záznamů:
r ← π E1,E2, E3,... (relace)
- všechno se vším
- relační schéma = relační schéma 1. relace + relační schéma 2. relace
relace.atribut
- 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
- 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 =▷◁
- 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)
= 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í
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 |
- 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átP(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 relacer
nekonečná
- neprocedurální dotazový jazyk, silou ekvivalentní n-ticovému relačnímu kalkulu
- dotaz je ve tvaru
{< x1, x2, ..., xn > | P(x1, x2,..., xn)}
, kdex1, x2,..., xn
jsou doménové proměnné, P je formule
- 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
- 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
- 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
neboasc
(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
- ...
CREATE TABLE r (A1 D1, A2 D2, ... , An Dn, (integritní-omezení1), ..., (integritní-omezeník))
-- vytvoří relacir
, kdeA
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énud
- ALTER TABLE r DROP a -- smaže atribut
a
z tabulky
- ALTER TABLE r ADD a d -- přidá nový atribut
- 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
- UNIQUE -- unikátní záznamy z množiny
- CHECK p -- p je predikát
- NOT NULL
- PRIMARY KEY
- DATE
- TIME
- TIMESTAMP
- INTERVAL
(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
- 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)
- 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
- 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
- atributy musí být atomické (nedělitelné)
- př. adresa -> adresa_mesto, adresa_ulice, adresa_cislo
- 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
- 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
- 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
- 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
- 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
- nejrychlejší, nejdražší, volatilní
- spravovaná HW sytému
- rychlý přístup, volatilní
- malá nebo drahá pro uložení celé databáze
- 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...)
- 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í)
- 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
...
- 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
- non-volatilní, velmi pomalé (sekvenční přístup), velká kapacita (40--300 GB)
- využití: zálohování, archivace dat
- 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ě)
- halda
- sekvenční
- hashování
- multitable clustering file organization
- buffer
- LRU strategy (Last Recently Used)
- Pinned block
- Toss-immediate strategy
- MRU strategy (Most recently used)
- 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é
- 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í
- 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ů
- 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.
- primární index, rovnost klíče
- primární index, rovnost neklíče
- sekundární index, rovnost neklíče
- primární index, porovnání
- sekundární index, porovnání
- konjunkce selekce s využitím indexu
- konjunkce selekce s využitím složeného indexu
- konjunkce selekce průnikem identifikátorů
- disjunkce selekce sjednocením identifikátorů
- quicksort pro relace, které se vejdou do paměti
- jinak 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é
- 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
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
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.
- 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.
- hashování nebo třídění
- projekce na každé n-tici a eliminace duplicit
- podobné jako eliminace duplicit (třídění a hashování)
- třídění + merge-join nebo hash-join
...
- dynamické programování
= 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
- 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ý
- serializovatelné
- repeatable read
- read commited
- read uncommited