D A T A B Á Z O V É S Y S T É M Y

1(22)

D A T A B Á Z O V É

S Y S T É M Y

Konceptuální úroveň -

vytvářím první model reality ER-model – jednoduchý grafický aparát, dá se jednoduše identifikovat entita – skládá se z vlastností, které chci zpracovávat Chenovo pojetí - u relace se sleduje kardinalita ( kosočtverec, M:N) - podtrhává primární klíč

Logická úroveň -

souvisí s typem software většina modelů je relačních grafové datové modely - hierarchický datový model - síťový datový model - entita přechází na entitní typ (uzel grafu) - podle typu hran (množina – seznam typů a hran, například cyklická, každý uzel je stromem) - objektový přístup (ploché modely) - relační model - zatím nejpoužívanější (SQL, transakce)

Fyzická úroveň -

indexy (smysl, algoritmus tvorby) hashování distribuce databáze (a s ní související problémy)

2(22)


S Y S T É M Y

Konceptuální úroveň ER-model Konceptuální schéma – implementačně nezávislý popis té části reálného světa, která se týká budovaného informačního systému – je pokusem umožnit předem vyjádřit sémantiku budoucích dat v databázi a současně vyjádřit modelový pohled člověka na uvažovanou část reálného světa – nejznámější je E-R model (de facto standard konceptuálního modelování)

Komponenty konceptuálního schématu -

strukturální operační specifikace IO

Čtyři principy modelů (představa, že se svět skládá z objektů a jejich vztahů) -

orientace na objekty – myslí se v objektech a nikoliv v identifikátorech, které je označují funkcionální podstata vztahů – zahrnuje se pojem atributu (E-R modely) nebo funkce ISA-hierarchie – umožňuje práci s nadtypy a podtypy objektů hierarchický mechanismus – objekty lze koncipovat z jiných objektů

E-R diagram -

vzniká jako součet pohledů více lidí (uživatelů) VIEW – je možné se chovat jako k obyčejné tabulce (ačkoliv vlastně virtuální prvek)

Tvorba E-R diagramu -

popis typů entit popis typů vztahů přiřazení atributů jednotlivým typům entit a vztahů formulace integritních omezení

-

entita - odpovídá objektu reálného světa vztah – vazba mezi dvěma (nebo více) entitami atribut – funkce, která přiřazuje entitám či vztahům hodnotu určující některou podstatnou vlastnost entity nebo vztahu identifikační klíč – atribut nebo skupina atributů, jeho hodnota slouží k identifikaci konkrétní entity determinant vztahu – atribut, jenž je definičním oborem funkce, kterou definuje typ vztahu

-

3(22)


S Y S T É M Y

Metody návrhu -

shora dolů – upřesňování typů entit a vztahů zdola nahoru – od atributů k entitám a vztahům zevnitř ven – postupné rozlišování schématu v jedné úrovni abstrakce smíšená technika – vychází ze skeletálního schématu (v hrubých rysech naznačuje modelovaný mikrosvět)

Charakter dat -

to, co se dávalo do registrů, formulářů, šuplíků definice záhlaví - koresponduje s položkou formuláře logický název tabulky logické jméno proměnné (v záhlaví) řádek – odpovídá jednomu formuláři zajímají nás hodnoty, nezáleží na pořadí řádků

-

vstupní data pracovní data výstupní data

-

přechodná data trvalá data

Operace -

uložení aktualizace zrušení přidání odstranění nalezení

Charakter dat v databázi -

perzistentní – trvalá, musí být k dispozici v libovolné době velká – mají obrovský objem spolehlivá – korespondence mezi realitou a daty (obecně je databáze v pořádku vůči nějakému času) - integritní omezení - primární klíč – pokud kombinace atributů je primární klíč, nepovolí se vložení duplicitního záznamu - kardinalita vazby – triggery, insert (maximální kontrola před chybami) - konzistence - data mohou být na více místech, ale musí mít stejnou hodnotu - v rozporu s redundancí - předchází se opakování dat

4(22)


S Y S T É M Y

Historie -

programy pro zpracování dat - vše měly v sobě (typ, algoritmus, data) - nekompatibilní při různých programech data k dispozici z vnějšku (souborový přístup) - ještě nedostatek – soubory se dají sdílet pouze jako celek SŘBD – systém řízení báze dat - úplné oddělení od fyzična - pošlou se dotazy, vrátí se odpovědi - nezajímá, jak je to fyzicky uloženo - propracované sdílení

SŘBD – systém řízení báze dat -

programové vybavení sloužící k udržování kolekcí dat na vnějších mediích poskytujících vhodné prostředky pro vyhledávání, pro víceuživatelský přístup k údajům, ochranu před zneužitím či znehodnocením jakoukoliv technikou.

Databázový systém = databáze + SŘBD

Modely dat: -

hierarchický (strom) síťový (síť) relační (relace)

Podstata databázových systémů a ideální vlastnosti: -

vyšší datová abstrakce nezávislost aplikačních programů na změnách ve fyzickém uložení dat ochrana před neoprávněným přístupem (ochrana heslem) a před poruchami odstranění redundancí (každý údaj uložen pouze jednou) sdílení dat komplexní kontrola nerozpornosti i konzistence (omezující podmínky)

realita→konceptuální úroveň (ER model)→logická úroveň (datový model)→fyzická úroveň→počítač

5(22)


S Y S T É M Y

Logická úroveň Relační model dat -

na logické úrovni záznamy nelze vnitřně strukturovat, záznam (prvek relace, řádek tabulky) může obsahovat pouze atomické hodnoty, a to v jedné úrovni schéma relační DB je popis záhlaví tabulek, relační DB je tvořena množinou tabulek primární klíč – nejmenší množina atributů, jejichž hodnoty jednoznačně identifikují řádky tabulek tabulka neobsahuje stejné řádky

Integrita databáze – korektnost a logická konzistence Integritní omezení – tvrzení, s jejichž pomocí lze částečně specifikovat, jaká omezení či vnitřní vztahy musí splňovat data v DB Konceptuální modelování – přiměřený formální popis aplikace

Relační struktura dat -

relace (tabulka) - záhlaví - metadata popisující vztahy (promítá se struktura z konceptuálního modelu) - jméno – logický název, unikátní v rámci záhlaví - doména – úžeji než typ (lze zakázat znaky apod.), co největší detailnost - data se před uložením kontrolují (například jestli položka musí být definována apod.) - skutečná data

-

stupeň relace – počet sloupců kardinalita relace – počet řádků

-

u relačního modelu se připouští pouze skalární hodnoty (nejmenší sémantická hodnota) doména by měla omezovat relaci porovnání (při dotazu) doména se sestává z dvojice - hlavička H = {A1:D1, A2:D2, … , An:Dn} - tělo B(t) = {r1, … , rm}, ri = {(A1:Vi1), … , (An:Vin)}

-

vlastnosti relací - nezáleží na pořadí - n-tice jsou uspořádané, atributy jsou neuspořádané - neexistují duplicitní n-tice - hodnoty atributů jsou atomické (1. normální forma)

6(22)


S Y S T É M Y

Typy relací -

bázové – základní, fyzicky existující pohledy – virtuální relace, většina operací stejně jako s fyzickou tabulkou snímky – kopie tabulky, pouze ke čtení, obraz databáze v čase výsledky dotazu – nepojmenované mezivýsledky – výsledky poddotazů dočasné – pod patronací systému, uživatel nemusí vědět

Relační databáze – vnímána uživatelem jako kolekce časově proměnných normalizovaných relací – veškerá data jsou reprezentována explicitní hodnotou (nikoliv ukazatele) – propojení – hledá se hodnota přes klíč

Pravidla -

specifická – plynou z logiky aplikace, z reality obecná – týkají se logického modelu (např. primární klíč – unicita)

Klíč -

množina atributů, která má tyto vlastnosti: - jedinečnost (unicita) - minimálnost (neredundance) – nelze žádný klíč vypustit - platnost (validita)

Kandidátní klíče -

-

-

atribut k relace R je kandidátním klíčem na R, právě když splňuje tyto dvě na čase nezávislé podmínky - jednoznačnost – žádné dvě n-tice z R nemají stejnou hodnotu k - minimalita – je-li k složený, nelze vyloučit žádnou komponentu bez ztráty jednoznačnosti získání kandidátních klíčů - vyberu celé záhlaví, náhodně jeden atribut vyčlením a zbytek testuji, jestli určuje jednoznačně - pokud ano, vybírám dále, jinak zkusím další potenciálně různé kandidátní klíče – množina kandidátních klíčů (všechny možné výběry) nedá se testovat z reálných dat

Primární klíč -

vyberu z kandidátních klíčů (nejkratší, nejpřehlednější), systém pak sám kontroluje unicitu a to, jestli je definovaný (musí) alternativní klíče – ostatní kandidátní klíče sekundární klíč - nemusí určovat jednoznačně, podporuje časově kritické operace (vyhledávání)

7(22)


S Y S T É M Y

Referenční integrita -

integritní omezení popisující vztahy mezi daty obsaženými ve dvou relacích cizí klíč

Cizí klíč – často se přes něj spojují tabulky (ovšem není primární účel) – položka, která je v jiné tabulce primárním klíčem – plně nezadaný – nepropojí se žádná hodnota – plně zadaný - důležité pro vícesložkové klíče (nelze zadat nekompletně) - existuje bázová relace r1 s primárním klíčem pk takovým, že každá zadaná hodnota fk v r2 je identická s existující hodnotou pk v r1 -

kontrola, jestli existuje – referenční integrita

-

nesymetrický vztah mezi tabulkami operace mazání – jak se zachovat, když smaži pk v r1 (nebezpečné) - katastroficky – smaže i všechny položky s ním v r2 - nastaví na NULL

-

cizí klíče se nemusí jmenovat stejně, někde je to vyžadované (v SQL ne)

Normální formy – kritérium pro kvalitu relačního databázového schématu

Normalizace – proces přechodu k lepšímu relačnímu schématu – relační schéma databáze – dvojice (R, I), R je množina schémat relací a I je množina integritních omezení – normalizace odstraňuje redundanci -

povinné a nepovinné členství ve vtahu - některé typy entit mohou existovat samostatně, některé jsou existenčně svázány s jiným typem entity aktualizační anomálie – je zapotřebí uchovat hodnotu, která je závislá, což činí problémy při mazání (uchová se jinde, aby se nesmazala)

1. normální forma – atomicita atributu 2. normální forma – závislost neklíčových atributů pouze na celém klíči 3. normální forma – v relaci nejsou neklíčové atributy tranzitivně závislé na klíči (někdy se zvažuje, jestli je vhodná)

8(22)


S Y S T É M Y

Výhody normalizace -

excelentní metodologie logického návrhu DB přímý překlad logického schématu do fyzického návrhu RDBM snížení redundance dat ochrana proti anomáliím, které mohou vzniknout při aktualizaci DB (update a delete) možnost restrukturalizace DB (přidání či odstranění atributů a relací) bez nutnosti měnit celý její návrh menší tabulky větší propustnost při I/O operacích díky menšímu počtu sloupců

Relační algebra -

dvojice - nosič, operace relace jazyk vysoké úrovně nepracuje s jednotlivými n-ticemi relací, nýbrž s celými relacemi

-

operace - množinové – množina = tabulka, prvek množiny = entita - průnik, sjednocení, rozdíl - požadavky na vlastnosti argumentu (ekvivalentní záhlaví) - existuje bijekce (propojení) tabulek, odpovídající domény - nesmí být duplicity - kartézský součin – jediná operace, která dovoluje generovat nové záhlaví - speciální - projekce – ze vstupního argumentu generuji novou tabulku (jenom vybrané položky), čímž dojde ke zúžení šířky, vyloučím duplicity - selekce – redukuji tabulku do hloubky pomocí podmínky (elementární nebo zřetězení) - spojení – dá se definovat jako kartézský součin a selekce (podmnožina)

Spojení -

-

univerzální (obecné spojení) – umožňuje i nerovnosti spojení na rovnost – v podmínkách pouze = (může brát i část klíče) přirozené spojení (nejčastější) - prvky nové relace vznikají spojením n-tic z obou relací přes rovnost hodnot na maximální množině společných atributů - pokud jsou vlastnosti odrazem stejné reality, mají stejný název (a musí být stejné), přes ně se spojuje, nemusí to být klíče vnější spojení - snažíme se získat všechny prvky, i když se spojení neúčastní - levé – všechny hodnoty první tabulky s výsledkem spojení (když v druhé tabulce nic není, nulové hodnoty) - pravé – podobně z druhé strany - symetrické – sjednocení levého a pravého

9(22)

D A T A B Á Z O V É A T T T F F F N

B T F N T F N T

A AND B T F N F F F N

S Y S T É M Y A OR B T T T T F N T

NOT A F F F T T T N

Operace dělení -

A = (x1, x2, … , xm, y1, y2, … , yn) B = (y1, y2, … , yn) A divide by B výsledkem je relace se záhlavím x1, … , xm a tělo obsahuje množinu všech n-tic z A takových, že část n-tice v y1, … , yn najde adekvátní v B (inverze ke kartézskému součinu, nepoužívá se)

Relační kalkul -

-

-

druhý formalizmus založený na predikátovém kalkulu 1.-ho řádu tvoří spojení mezi databázemi a matematickou logikou - konstanta – ‘a’, 1, … - proměnné - predikátové symboly (splývají se jmény relací) - kvantifikátory - -\/-, spojky (implies i další), for each, exist pomocí toho píši formule (pravdivé nebo nepravdivé) - vázané a volné proměnné (vázaná je vázána kvantifikátorem) - neměly by se v jednom výrazu vyskytovat se stejnými jmény - dotaz - {x1, x2, … , xn | A(x1, … , xn)}, x1, … , xn jsou volné proměnné ve formuli - odpověď – je dána všemi ohodnoceními volných proměnných v A (= true) pokud je relace nekonečná, odpovědí je nekonečně čísel bezpečný výraz – sémantické a syntaktické omezení (zaručuje konečnost odpovědí – např. zákaz doplňků nekonečných množin) pokud se omezíme na bezpečné výrazy, je síla jazyku stejná (dá se dokázat)

SQL → relační kalkul → relační algebra

Dotazovací jazyk relační algebra -

množina výrazů, které vzniknou zahnízděnými aplikacemi operací relační algebry na relace ze schématu relační DB odpověď na dotaz – vyjádření relační algebry je relace, která vznikne vyhodnocením výrazu dotazu relačně úplný dotazovací jazyk - má prostředky k realizaci všech operací relační jazyk

10(22)


S Y S T É M Y

Minimální množina operací -

sjednocení kartézský součin rozdíl selekce projekce

Dotazovací jazyk relační kalkul -

množina výrazů tvaru (x1, … , xk | A(x1, .. , xk)), kde x1, … , xk jsou volné proměnné (tj. nejsou kvantifikovány) ve formuli odpověď na dotaz vyjádřený výrazem relačního kalkulu je dána všemi ohodnoceními volných proměnných v A takovými, že A po jejich dosazení nabývá hodnoty TRUE DATALOG – rozšiřuje relační systém o rekurzi

Algebraické přepisování -

forma zápisu naznačuje typ zpracování všechny možné zápisy a vyhodnotí se (prakticky to nejde) existují algoritmy, které se snaží stromový zápis důležitá je i fyzická podpora operací (algoritmus)

Základní strategie optimalizace - je na největší možnou míru omezit velikosti mezivýsledků operacemi selekce a projekce Cílem optimalizátoru – je skrýt heuristiky před uživatelem

Architektura DBS z hlediska rozdělení služeb 1. 2. 3. 4.

prezentační služby – poskytují zařízení poskytující I/O prezentační logika - interakce uživatele s počítačem logika aplikace - kalkulace, rozhodnutí, operace, je dána aplikačními programy logika dat - vyjádření operací, které mají být prováděny s databází, které podporují logiku DB (příkazy SQL) 5. datové služby - akce s databází vně logiky dat i realizace definice a manipulace s daty, transakce 6. služby zpracování souborů - získání potřebných dat z disku, práce s vyrovnávací pamětí, služby OS

11(22)


S Y S T É M Y

A – přes terminál k DB: stanice (1) sálový počítač (2 - 6) – DB - primitivní uživatelské rozhraní, špatná rozšiřitelnost, zátěž sítě o prezentační data B – DB jako soubory stanice (1 - 5) file server (6) – DB - file servery zatěžují síť přenosem souborů nutných pro zpracování dotazu C – klient – server stanice (1 - 4) server (5, 6) – DB - pokud se uživatelé nesejdou na stejném řádku D – klient – server stanice (1 - 3) server (3 - 6) – DB - lze zvýšit výkon přidáním klientů, ale při složitých a častých interakcích rapidně klesá výkon - X-terminály – může zatěžovat server E – klient - server s rozdělenou logikou stanice (1, 2, 3, 4) server (3, 4, 5, 6) - aplikace se vhodně rozdělí (ne vždy to tak jde) F – klient – server se třemi vrstvami stanice (1, 2) aplikační server (3) databázový server (4) – DB (5, 6) - řeší všechny problémy, ale není moc rozšířený - databázový server – současný přístup, bezpečnost, centrální zpracování dat, údržba, sdílená integrita

Agendové zpracování -

charakteristické za sálových počítačů - agenda – tvoří ji soubor operací aplikace plná závislost dat na programu nízká efektivita datových struktur a programů typické zpracování v dávkách až při načtení do počítače se kontrolovala vstupní správnost

12(22)

D A T A B Á Z O V É -

-

S Y S T É M Y

data se sbírala jen pro jednu agendu - izolovanost dat, redundance, nekonzistence a neintegrita - redundance – některé informace se v různých agendách opakují - nekonzistence – postupem času se budou hodnoty stejných dat na různých místech rozcházet (oprava neproběhne všude stejně rychle) - integrita – musí být uložena aktuální data (stačí znát integritu k datu v minulosti) obtížná dosažitelnost dat izolovanost dat – roztroušena v různých souborech (a formátech) problematický je současný přístup více uživatelů tyto problémy odstraňuje SŘBD data – údaje získané měřením, pozorováním či zaznamenáním z reálné skutečnosti informace – smysluplné interpretace dat a vztahů mezi nimi informační systém – organizace údajů vhodná pro systémové zpracování dat (sběr, uložení, uchován, zpracování, vyhledávání) a to vše pro účely rozhodování

Hierarchický systém -

-

-

data uložená do souboru s organizačními atributy entitní typ – vrcholy grafu (metadata) atributy – uvnitř entitního typu síťový model umožňuje cykly - množina entitních typů - C-množiny – uspořádané dvojice hran umožněna vazba 1:N - provedení kruhovým seznamem - v každém záznamu ukazatel na další - na konci opět vstupní bod (pro procházení položek) manipulace (přechody) - nastavení na kořen stromu databáze - horizontálně na další strom (les stromů) - přechod mezi úrovněmi hierarchie - vložení nebo zrušení záznamu na specifikované pozici synovský záznam nemůže existovat bez otcovského vazby M:N se provádějí pomocí dvou vazeb 1:N a pomocné struktury (logický model)

13(22)


S Y S T É M Y

Fyzická úroveň (interní) -

SŘBD -> správce souborů (stránky, bloky) -> správce disku (úroveň disku, I/O operace) databázové struktury mají pevnou strukturu všechny záznamy jsou na stejné úrovni jednoduše algoritmicky zpracovatelný přístup k položkám

-

relační model - mapování IDZ (vnitřní záznam, kde je to uložené) - mapování IDS (fyzická adresa)

-

horší systémy – využívají OS lepší systémy - vytváří i pro nejnižší vrstvy vše vlastní (optimalizace) - informace, ve kterých stránkách a kde je informace uložena - IDZ – dá se rozdělit - adresa stránky - pomocná struktura nebo offset, kde na stránce je záznam

Statická organizace dat -

pro nalezení záznamu s daným klíčem v sekvenčním souboru potřebujeme čas úměrný velikosti souboru (lineární složitost) v index-sekvenčním či indexovém souboru čas konstantní to však platí v ideálním stavu, kdy příliš neaktualizujeme primární soubor odpovídající databázi databáze jsou ale statické a uložené v pevně vymezeném prostoru na disku některé aktualizace vedou k řetězení záznamů ve speciálním prostoru – oblasti přetečení tím se vyhledávání zhoršuje, je nesymetrické a místo konstantního času se postupně dospěje k složitosti lineární

Dynamická organizace dat -

rychlost vyhledávání v nich je stále omezená „rozumnou“ hranicí (složitost je konstantní nebo logaritmická v závislosti na velikosti relace) a paměť potřebná k uložení datové struktury se zvětšuje nebo zmenšuje v souladu s aktualizací relace

SŘBD -

vidí soubor jako soubor uložených záznamů jednoznačně identifikovaných IDZ, které se nemění po dobu života záznamu (nepředpokládají se přesuny ale změny dat) uložený soubor – sekvenční průchod (mohu přeskládat a setřídit) některé systémy potřebovaly vytvořit index pro primární klíč (GUPTA), jiné to dělají samy na pozadí

14(22)


S Y S T É M Y

Shlukování (clustering) -

pro převládající typy dotazů potřebuji propojení tabulek třeba při zakládání definovat jejich fyzické uložení klasicky - systém musí vždy znovu načíst stránky obou tabulek a znovu prvky hledat clustering – tabulky se dají na stejné stránky, takže se načtou najednou

Realizace rychlého vyhledávání -

index hashování

Index -

-

systém ví, že je to soubor vyhledávání v nesetříděném souboru není dobré indexový soubor - tabulka se sloupcem primárních klíčů a sloupcem odkazů na řádky - stejný počet záznamů, ale menší objem (nejsou všechna data) - udržuje se setříděný – vyhledávání třeba půlením intervalů - najdu položku v indexovém souboru a potom jdu přímo na celý záznam hustý index – stejný počet záznamů jako v původní tabulce řídký index – podobné slovníkovému přístupu (index sekvenční přístup) víceúrovňový index – řídký index a za ním hustý index primární – podle primárního klíče sekundární – hledám množinu položek ORACLE – kdy vygeneruji index, rád ho použije, někdy generuje sám

B-strom - cesta při vyhledávání je vždy stejná (dokonale vyvážený) - jednotlivé uzly jsou udržovány setříděné - každý uzel maximálně n následovníků a minimálně m/2 - 1 blok - typicky jedno načtení z disku - obsazuje se typicky 1/2 dat (při vytvoření) - rozdělení uzlu - pokud má počet následovníků přesáhnout m, vzniknou dva uzly po m/2 následovnících a jeden prvek se předá do předchozího uzlu, zvýšení výšky stromu - slévání uzlů - při vybírání prvků (mělo by klesnout pod m/2), snížení výšky stromu B+ strom - implicitně na listové úrovni je kruhový seznam následovníků - výhodné pro rychlý výpis záznamů

15(22)


S Y S T É M Y

Hashování -

-

vstupním parametrem může být třeba primární klíč (nemusí) hashovací funkce - transformace klíče na adresy - počet adres se doporučuje prvočíslo (hashovací funkce pak končí modulo prvočíslo) - měla by prvky rozptýlit rovnoměrně statické hashování - pevně stanovené prvočíslo - konflikt klíčů – zřetězení (může vést k degeneraci, až lineární složitosti vyhledávání) dynamické hashování (Faginovo) - velikost paměti se přizpůsobuje velikosti databáze - klíč – chápe se jako binární číslo - adresář - pomocná struktura (odkazy na stránky – na jedno načtení), na začátku beru jenom 1 bit (2 řádky) - rozdělení stránky - pokud stránku zaplním, rozhashuji záznamy do dvou a přidám jeden bit - pokud druhá stránka není plná (a první se rozdělila), netýká se jí to - sloučení stránek - při mazání, uberu bit - vlastní hashování probíhá jen v první fázi

Základní metody pro výpočet spojení -

-

-

hnízděné cykly - procházím záznamy první tabulky a ke každému hledám příslušné v druhé - dvojitý cyklus – není moc dobré indexované hnízděné cykly - buď si vytvoří systém sám, nebo má explicitně k dispozici - vnější cyklus se prochází sekvenčně (první tabulka) - vnitřní cyklus pomocí indexů (druhá tabulka) vyhledávání setřídění - slévání - indexy pro obě tabulky, jako by obě byly setříděné - jenom se spojuje rozdělení relací – algoritmus GRACE (hashovaná spojení) - pokud se obě tabulky nevlezou do paměti, ale (T1+T2)/n ano, rozdělím prvky do tříd podle zbytku (modulo n) - pak pospojuji části a nakonec dám výsledek dohromady musí se spočítat, co se časově vyplatí není možné vyzkoušet všechny možnosti – heuristika (předvídá, které metody jsou lepší) obecná poučka – selekce a projekce se provádí co možná nejdříve statistiky - počet n-tic v tabulce nr - V(A,R) – kolik prvků má konkrétní hodnotu - nr/V(A,R) – relativní vztažení k počtu prvků - dají se zapojit do optimalizace

16(22)


S Y S T É M Y

Zpracování transakcí Transakce -

posloupnost jistých akcí, které se buď provedou všechny anebo se neprovedou vůbec z hlediska aplikačních programů je to logická jednotka práce odpovídající nějaké akci v reálném světě

Vlastnosti transakcí (ACID) -

atomicita – změny databáze, které transakce provádí, se všechny promítnou do DB nebo je DB uvedena do původního stavu konzistence – transakce transformuje DB z jednoho konzistentního stavu do jiného konzistentního stavu nezávislost – dílčí efekty transakce nejsou viditelné jiným transakcím trvanlivost – efekty úspěšně ukončené (potvrzené) transakce jsou uloženy do DB implicitní zahájení transakce – po provedení první definice databáze nebo databázové operace po potvrzení poslední transakce explicitní zahájení transakce – speciálním příkazem (BEGIN TRANSACTION, COMMIT TRANSACTION)

Rozvrh -

stanovené pořadí provádění operací více transakcí v čase sériový rozvrh – transakce probíhají po sobě v určitém pořadí paralelní rozvrh – transakce probíhají souběžně rozvrhovač - software, který rozhoduje, jakým postupem v čase se transakce zpracovávají - jeho úkolem je vytvářet rozvrh souběžného zpracování, tj. maximalizovat paralelismus transakčního monitoru - test konzistence – databáze je v konzistentním stavu, pokud existuje sériový rozvrh transakcí, který ji uvede do stejného stavu (uspořadatelnost)

READ (X) – přiřazuje hodnotu atributu X lokální proměnné x WRITE (X) – přiřazuje hodnotu lokální proměnné x atributu X ve vyrovnávací paměti

Kurzor -

slouží pro specifikaci množiny řádků, na nichž pak lze operovat způsobem „po jednom“ v čase je pojmenovatelný příkaz SELECT je nutné otevřít příkazem OPEN příkaz FETCH zajistí umístění kurzoru na následující prvek odpovědi dané vyhodnocením příkazu SELECT a dosazení příslušných komponent prvků do proměnných hostitelského jazyka

17(22)


S Y S T É M Y

Optimistické systémy - pracují v prostředí, kde je konflikt minimální - nevěnuje se sofistikovanější analýze (jednoduché testy) - pokud nekorektní – transakce se vrátí a provedou se v jiném pořadí Pesimistické systémy - rozšiřují model (zápis a čtení) o operace uzamykání

Možné chyby Dočasná aktualizace -

0. nebo 1. úroveň transakce pracuje s hodnotou, která již není aktuální (jiná transakce ji změnila), takže ji při uložení přepíše špatně

Neopakovatelné čtení -

2. úroveň transakce T1 používající daný kurzor, se snaží znovu přečíst řádek, který již jednou četla, ten však již obsahuje jiné hodnoty díky aktualizaci transakcí T2, která probíhá paralelně

Fantom -

2. úroveň transakce T přečte množinu řádků a zpracovává je, mezi tím dojde ke změně těchto řádků transakcí T1, použije-li pak T týž příkaz, obdrží již jinou množinu řádků

Zamykání a odemykání Zamykání - akce, kterou vyvolá transakce na objektu, aby ho ochránila před přístupem od ostatních transakcí Odemknutí – akce uvolňující objekt pro zpracování dalšími transakcemi Uváznutí – v jedné transakci chceme uzamknout to, co je již uzamknuté druhou transakcí a naopak

Podmínky zachování uspořádání (ekvivalence rozvrhů) -

jestliže v se v jednom rozvrhu vyskytuje READ(A) v transakci Ti a tato hodnota vznikla z WRITE(A) v transakci Tj, pak toto musí být zachováno i v jiném rozvrhu jestliže se v jednom rozvrhu vyvolá poslední WRITE(A) transakcí Tj, pak totéž musí být zachováno v jiném rozvrhu

Uspořadatelnost – rozvrh je uspořadatelný, existuje-li sériový rozvrh s ním ekvivalentní

18(22)


S Y S T É M Y

Legální rozvrh -

objekt může v daném čase být uzamčen nejvýše jednou transakcí objekt musí být uzamknutý, kdykoliv jej transakce potřebuje pokud je objekt uzamčený jinou transakcí, musí se čekat

Dobře formovaná transakce -

nezamyká objekt, který již zamkla neodemyká objekt, který nezamkla po ukončení odemyká všechny objekty, které zamkla

Dvoufázová transakce -

první fáze - uzamkne vše, co je potřeba (pokud je něco zamčeného, všechno opět odemkne) druhá fáze (od prvního odemknutí) – objekty již pouze odemyká

-

jsou-li všechny transakce v dané množině transakcí dobře formulované a dvoufázové, pak každý jejich legální rozvrh je uspořádaný

Dvoufázový uzamykací protokol - protokol, v němž každá transakce je dvoufázová -

jsou-li všechny transakce v dané množině transakcí dobře formované a dvoufázové, pak každý jejich legální rozvrh je uspořadatelný

Zámky -

pro tabulku, řádek, položku pro čtení (sdílené) – uzamyká objekty, které chceme pouze číst pro zápis (exkluzivní, výlučný) – na objekty pro operace READ a WRITE neviditelné zámky (vytváří je sám systém)

Zjištění uváznutí Precedenční graf -

vrcholy = transakce potenciální hrany – čekání na transakci cyklus - možné uváznutí, třeba rozbít (ROLLBACK jedné transakce) - některé se snaží rozpoznat délku transakce (vyberou tu nejkratší)

Stavy transakce -

PC A

aktivní (A) – stav od počátku provádění transakce F částečně potvrzený (PC) – stav po provedení poslední operace transakce chybný (F) – v normálním průběhu transakce nelze pokračovat zrušený (AB) – po skončení operace ROLLBACK potvrzený (C) – nastane po úspěšném zakončení, tj. po potvrzení operace COMMIT

C AB

19(22)


S Y S T É M Y

Obnova po poruše -

transakce, které byly úspěšně uloženy – v pořádku transakce, které skončily před poruchou, ale nebyly uloženy – obnoví se z logfile a uloží transakce, které přerušila porucha – pomocí logfile se provede ROLLBACK

LogFile (žurnál) -

záznamy o všech změnách, které transakce vykonaly na DB (operace WRITE(X) a fyzická změna DB OUTPUT(X)) dostatečně velký (2-3 dny) zapisuje se stále dokola

Algoritmus UNDO-REDO -

oprava systému po krachu - vytvoří dva seznamy UNDO a REDO, do UNDO dá všechny transakce z posledního kontrolního bodu - prohledává žurnál dopředu, pokud narazí na začátek další transakce, uloží do UNDO, pokud konec, přesune do REDO - zpětným chodem čte žurnál a provádí ROLLBACK (seznam UNDO) - opět projde žurnál dopředu a provede transakce REDO

20(22)


S Y S T É M Y

Objektově orientované databáze Hlavní přínosy objektové technologie v DB -

přímý vztah ke konceptuálnímu modelování, objekty reálného světa lze reprezentovat velmi přirozeně jako složité objekty část funkcí specifikovaných dříve v aplikačních programech se přenáší do definice objektu (zapouzdření), tj. i programy se stávají součástí DB

OOSŘBD by měl vyhovovat -

měl by být SŘBD (perzistence objektů na vnějších pamětech, souběžný přístup více uživatelů, spolehlivost dat, administrátorské dotazy) měl by být OO (existence identity objektu, existence typu nebo tříd, zapouzdření, polymorfizmus, dědění, složité objekty, rozšiřitelnost a výpočetní úplnost)

-

objekt - je dán hodnotami svých atributů a množinou operací, které definují jeho chování - identita je nezávislá na hodnotě objektu - rovné objekty nemusí být identické

-

typ OOSŘBD - popisuje společné struktury množiny objektů se stejnými atributy a operacemi

-

třída - může produkovat nové objekty, může sdružovat všechny potřebné objekty je to realizace typu

Zapouzdření – objekty dané třídy mohou být přistupovány pouze přes dané rozhraní – hodnoty atributu objektů nejsou obecně přístupné z programovacího jazyka Polymorfizmus – schopnost operací fungovat na objektech více než jednoho typu Dědění – odvozování nových tříd z tříd existujících

21(22)


S Y S T É M Y

Proces normalizace -

v době, kdy máme popsané schéma databáze (záhlaví a integritní omezení) - funkční závislosti – určují sémantiku máme z logického schématu vytvořit fyzické tabulky - test na výši normální formy (většinou rozbití tabulek na více menších)

-

nechť mezi X,Y atributy je relace, kterou značíme funkční závislostí R. X → R.Y - platí tehdy, když ke ∀x odpovídá právě nebo nejvýše jedno y

-

kandidátní klíče – závislost vzájemná ( K1 ↔ K 2 )

-

návrh shora dolů (někdy se jde odspodu)

-

z funkčních závislostí můžeme najít primární (kandidátní) klíče – levé strany závislostí

-

tranzitivní závislost (není ve 3NF) rozbíjí se na více tabulek také by zbytečně zabíralo místo

-

rozbíjení tabulek - hlavní tabulka – klíč a všechny levé strany funkčních závislostí - další tabulky – určují funkční závislosti

-

B

A

C A

B

B

C

je to na úkor rychlosti – tabulky se musí skládat při smazání položky (A,B,C) mohu ztratit informaci o funkční závislosti – rozbitím tabulky předejdu také jednodušší pří ošetřování změn zadání funkční závislost – závislost mezi atributy 1nf

2nf

3nf

BCNF

1NF - všechny jednoduché domény obsahují pouze atomické hodnoty - existují snahy to porušovat (blob, podřetězec) 2NF - každý neklíčový atribut je plně závislý na primárním klíči (+ 1NF) - nemusím se zabývat u jednosložkových klíčů - týká se vícesložkových klíčů - negativně - podmnožina klíčů nesmí sama určovat nějaký atribut - řeší se rozbitím tabulky

4nf

5nf

22(22)


S Y S T É M Y

3NF - každý neklíčový atribut je netranzitivně závislý na primárním klíči - neexistuje funkční závislost mezi neklíčovými atributy

-

převést do 3NF – mělo by se podařit skoro všech do vyšších NF – nemusím transformovat (pokud to ale jde, je to výhodné)

BCNF – Boyce-Coddova - každý determinant je kandidátním klíčem (levá strana vztahu) - nemusí existovat odstranění vadné závislosti - může existovat více kandidátních klíčů (i složených) a mohou se i překrývat 4NF - multifunkční závislost – vícehodnotové závislosti, aby se neporušila 1NF (rozhodí se do více řádků) - R je relace s atributy ABC, pak platí vícehodnotová závislost R. A → R.B ⇔ hodnoty {bi } pro dané hodnoty (a,c) závisí pouze na hodnotě A a ne na C (jakoby A klíčem) R. A → R.B ⇔ R. A → R.C - existuje-li vícehodnotová závislost v R, pak jsou všechny atributy R také fčně závislé na A - nejde vždy realizovat (někdy jen částečně) 5NF - ideální by bylo tabulku dekomponovat pouze na dvojice (prakticky nejde) - každá závislost na spojení v R je důsledkem kandidátních klíčů R - join dependency – závislost na spojení

D A T A B Á Z O V É S Y S T É M Y

Recommend Documents