Databázové systémy

<< 5. Pojem dotazu, dotazovaciho jazyka

Pojem databazovy dotaz pro dane databazove schema oznacuje funkci, ktera je definovana nad prostorem vsech pripustnych databazi s danym schematem. Hodnotou teto funkce bude opet urcita databaze se specifikovanym schematem, jiz nazveme odpoved na dotaz.

Funkce (dotaz) by mela z praktickych duvodu splnovat nasledujici kriteria:

• je vycislitelna (lze pro ni zkonstruovat algoritmus),
• odpoved obsahuje pouze hodnoty z databaze,
• odpoved nezavisi na reprezentaci databaze.

Ke kazdemu vyrazu jazyka by melo byt mozne priradit dotaz - jazyk by mel byt omezeny. V dotazovacim jazyku by melo byt mozne vyjadrit libovolny dotaz - jazyk by mel byt expresivni. Jazyk, jenz je soucasne omezeny a expresivni, se nazyva uplny.

Mnozina vsech dotazu, ktere lze dotazovacim jazykem vyjadrit, se nazyva vyjadrovaci sila dotazovaciho jazyka. Pri porovnavani dvou jazyku oznacime jako silnejsi ten, ktery ma vetsi vyjadrovaci silu. Lze-li jako silnejsi oznacit oba jazyky, jsou navzajem ekvivalentni.

<< 6. Relacni kalkul a algebra

6.1. Relacni algebra

Relacni algebra je nastrojem pro manipulaci relaci. Jde o jazyk, v nemz se nepracuje s n-ticemi relaci (na rozdil od jazyku sitoveho a hierarchickeho modelu), ale s celymi relacemi.

Zakladni prostredky: kartezsky soucin, sjednoceni, prunik a rozdil relaci, dale pak projekce R[C] (zuzeni relace na sloupce s atributy v C), selekce R(c) (zuzeni relaci na radky vyhovujici podmince c), spojeni R*S schemat R(A), S(B) (vysledkem je relace, jejiz projekce na A je z R a projekce na B je z S) a deleni relaci se schematy R(A) a S(B), kde B je podmnozinou A (vysledkem je relace se schematem A-B obsahujici mnozinu takovych n-tic t, ze pro kazdou n-tici z S existuje n-tice r z R tak, ze r[A-B]=t a r[B]=s).

U spojeni rozlisujeme leve c-polospojeni se schematy R a S, jehoz vysledkem jsou ty n-tice relace R*, ktere jsou spojitelne pomoci podminky c. Analogicky se definuje prave polospojeni. Polospojeni pres rovnost se rika prirozene polospojeni.

Leve vnejsi spojeni se schematy R(A) a S(B) vytvori nejvetsi relaci sjednoceni A a B, jejichz projekce na atributy A je relace R, projekce na atributy B se sklada z podmnoziny relace S a radku prazdnych hodnot. Analogicky se definuje prave vnejsi spojeni.

Priklad dotazu v relacni algebre: dodej seznam kin, kde nedavaji zadny film s Marlonem Brando:

   KINO[NAZEV_K] - (FILM(HEREC=Brando)[JMENO_F]*PROGRAM[NAZEV_K,JMENO_F])[NAZEV_K]

6.2. Relacni kalkul

N-ticovy relacni kalkul

Priklad:

   x.NAZEV_K,k.ADRESA,x.JMENO_F,x.DATUM
      where PROGRAM(x) and KINO(k) and k.NAZEV_K = x.NAZEV.K

je totez, co PROGRAM * KINO v relacni algebre

Domenovy relacni kalkul

Priklad:

   adr,d where exists n (PROGRAM(NAZEV_K:n,DATUM:d) and KINO(NAZEV_K:n,ADRESA:adr))

da jako vysledek adresy kin, v nichz se promita (tj. jsouv programu), s daty promitani.

<< 7. Zaklady SQL

Projekce: SELECT
Selekce: FROM
Podminka: WHERE
Seskupeni podle stejnych hodnot: GROUP BY
Kriterium setrideni: ORDER BY

Priklad: Naleznete ISBN knih, jejichz cena neni rovna cene zadne z knih z Velke Britanie.

   SELECT ISBN
   FROM EXEMPLAR
   WHERE CENA NOT IN (SELECT EXEMPLAR.CENA
                      FROM EXEMPLAR
                      WHERE EXEMPLAR.ZEME_VYDANI='GB')

<< 8. Metody navrhu relaci

Navrhem relacniho schematu databaze rozumime jakesi rozmisteni atributu z dane mnoziny do jedntlivych schemat relaci. Obvyklym postupem byva nalezeni funkcnich zavislosti: necht A = {A₁, A₂,..., A_n} je relacni schema, X, Y jsou podmnozinou A. Rekneme, ze Y funkcne zavisi na X (znacime X -> Y), jestlize pro kazdou instanci databaze r nad A plati: pro vsechna t₁, t₂ z r: t₁.X=t₂.X -> t₁.Y=t₂.Y.

Pri navrhu databaze se snazime udrzet "co nejvyssi" normalni formu. Normalni formy jsou definovany takto:

• 1NF: vsem atributum jsou jako domeny prirazeny atomicke typy
• 2NF: 1NF & schema neobsahuje zadne castecne zavislosti neklicovych atributu na klici
• 3NF: 1NF & zadny neklicovy atribut neni tranzitivne zavisly na zadnem klici schematu
• BCNF (Boyce-Coddova): pro kazdou netrivialni zavislost X -> Y plati, ze X je nadmnozinou nejakeho klice schematu

Castecna zavislost je zavislost neklicoveho atributu na podmnozine klice.

Tranzitivni zavislost: atribut C je tranzitivne zavisly na X, pokud plati X -> Y - > C a neplati Y -> X, kde X, Y jsou podmnoziny mnoziny vsech atributu a C se v X ani v Y nevyskytuje.

Trivialni zavislost: pokud Y je podmnozinou X, pak X -> Y.

Dekompozici schematu relace rozumime rozklad mnoziny vsech atributu do podmnozin. Dekompozice ma vlastnost pokryti zavislosti, je-li sjednoceni uzaveru na jednotlivych dekomponovanych funkcnich zavislostech totozny s uzaverem vsech funkcnich zavislosti (uzaver F+ je mnozina vsech funkcnich zavislosti odvoditelnych z F).

Dekompozice by mela mit vlastnost bezeztratoveho spojeni - kazdou pripustnou relaci S* by melo byt mozne rekonstruovat pomoci prirozeneho spojeni S* na atributy jednotlivych relaci dekompozice.

Tvrzeni: Mejme schema R(A,B,C), kde A, B, C jsou disjunktni mnoziny atributu, a funkcni zavislost B -> C. Rozlozime-li R na schemata R1(B,C) a R2(A,B), je takto provedena dekompozice bezeztratova. Naopak, je-li dekompozice R1(B,C) a R2(A,B), musi platit bud B -> C, nebo B -> A.

Dekompozice obecne muze mit vlastnost bezeztratoveho spojeni, nemusi vsak mit vlastnost pokryti zavislosti.

Nyni popiseme dva algoritmy navrhu schematu relacni databaze: shora dolu (dekompozice relacnich schemat) a zdola nahoru (synteza relacnich schemat). Dulezitymi predpoklady jsou predpoklad schematu univerzalni relace (jmeno atributu je jednoznacne a hraje pouze jednu roli) a predpoklad jednoznacnosti vztahu (pro kazdou mnozinu atributu existuje nejvyse jeden typ vztahu). Nasim cilem bude 3NF nebo BCNF, pokusime se o splneni vlastnosti pokryti zavislosti a vlastnosti bezeztratoveho spojeni.

Dekompozice

Vstup: F nad mnozinou atributu O schematu relace R(O)
Vystup: relacni schema databaze R = {Ri(Oi,Fi)} obsazene v RESULT

begin RESULT := {R};
      DONE := FALSE;
      Vytvor F;
      while (not DONE) do
        if (v RESULT existuje Ri, ktere neni v BCNF)
          then begin
                 necht X -> Y je netrivialni funkcni zavislost v Ri(O)
                   a necht X -> Oi neni v F+;
                 RESULT := (RESULT - Ri(Oi)) sjednoceno s Ri(Oi - Y) sjednoceno s Rj(XY)
               end;
          else DONE := TRUE
end

Vysledne schema je v BCNF a dekompozice ma vlastnost bezeztratoveho spojeni, nemusi vsak byt zachovana vlastnost pokryti zavislosti.

Synteza

Algoritmus syntezy vychazi ze zadane mnoziny atributu a funkcnich zavislosti. Vytvori se minimalni pokryti (pokryti mnoziny funkcnich zavislosti F je G takova, ze F+ = G+; neredundantni pokryti neobsahuje redundantni zavislosti; minimalni pokryti - neredundantni pokryti, ktere neobsahuje v jednotlivych zavislostech na leve strane zadne redundantni atributy) a zavislosti se roztridi tak, aby v kazde skupine byly zavislosti se stejnou levou stranou. Atributy zavislosti skupiny tvori schema jedne relace vznikle syntezou, atributy leve strany zaroven tvori klic schematu. Schemata s ekvivalentnimi klici je vhodne sloucit do jednoho schematu. Atributy, ktere se v zadne skupine nevyskytuji, lze pripojit k libovolnemu schematu ci pro ne vytvorit samostatnou relaci.

Vysledek syntezy je v 3NF, zavislosti jsou zachovany, bezeztratovost splnena byt nemusi.

<< 9. Transakce, transakcni zpracovani

© Pavel Machek

Transakce

Transakce je operace nad databazi, ktera vypada jako atomicka (z duvodu vykonu se jako atomicka neprovadi). Pred i po provedeni transakce je databaze v konzistentnim stavu. V prubehu provadeni transakce tomu tak byt nemusi.

Transakce by mohla vypadat treba takhle:

Begin_transaction Zmena_cisla_ctenare
  input(stare_cislo, nove_cislo);
  read (temp, CTENAR.C_CT = stare_cislo);
  if temp = empty then begin
    output("ctenar neexistuje")
    ROLLBACK
    end
  else begin 
    modify1(CTENAR, stare_cislo, nove_cislo);
    modify2(VYPUJCKY, stare_cislo, nove_cislo);
    modify3(REZERVACE, stare_cislo, nove_cislo);
    end
COMMIT
end_transaction

ROLLBACK znamena "vrat databazi do stavu, v jakem byla pred zacatkem transakce" (v nasem priklade se provede nop - prazdna transakce, protoze pred ROLLBACK neni zadny zapis). COMMIT znamena "databaze je znovu konzistentni, ucin zmenu permanentni".

Transakce by mela splnovat vlastnosti ACID:

• atomicity- transakce se tvari jako jeden celek, musi bud probehnout cela, nebo vubec ne,
• consistency - transakce transformuje databazi z jednoho konzistentniho stavu do jineho,
• independence - transakce jsou nezavisle, tj. dilci efekty transakce nejsou viditelne jinym transakcim,
• durability - efekty uspesne ukoncene (potvrzene) transakce jsou trvale ulozeny do databaze (take persistence).

Rozvrh (schedule)

Rozvrh je konkretni poradi operaci.

Seriovy rozvrh

Seriovy rozvrh je takovy rozvrh, kde v dany okamzik bezi jen jedina transakce.

Usporadatelnost

Seriove rozvrhy zachovavaji operace kazde transakce pohromade. Pro ziskani korektniho vysledku vsak muzeme pouzit i rozvrhu, kde jsou operace navzajem prokladany (a je to nejspis vyhodnejsi). Prirozenym pozadavkem na korektnost je, aby efekt paralelniho zpracovani transakci byl tyz, jako by byly transakce provedeny v nejakem seriovem rozvrhu.

Uzamykaci protokoly

Vytvareni rozvrhu a testovani jejich usporadatelnosti neni pro praxi zrejme ten nejvhodnejsi zpusob prace. Casove naroky takoveho pristupu by zrejme presahovaly rozumnou miru. Ukazeme dale, ze je mozne konstruovat transakce podle jistych pravidel tak, ze za urcitych predpokladu bude kazdy jejich rozvrh usporadatelny. Soustave takovych pravidel se obecne rika protokol. Nejznamejsi protokoly jsou zalozeny na dynamickem zamykani a odemykani objektu v databazi. Zamykani (operace LOCK) je akce, kterou vyvola transakce na objektu, aby ho ochranila pred pristupem od ostatnich transakci.

Dobre formovana transakce

• Pred pristupem k objektu provadi uzamknuti objektu LOCK(objekt).
• Neprovadi LOCK() na objekt, ktery uz uzamkla.
• Neprovani UNLOCK() na objekt, ktery nezamkla.
• Pred koncem provede UNLOCK() na vsechny objekty, ktere zamkla.

Dvoufazovy uzamykaci protokol

Dvoufazova transakce v prvni fazi uzamyka vse, co je potreba, a od prvniho odemknuti (druha faze) se transakci zamcene objekty pouze odmykaji, tj. neni jiz pouzito zadne operace LOCK. Tedy transakce musi mit vsechny objekty uzamcene pred tim, nez nejaky objekt odemkne.

Usporadatelnost dvoufazoveho protokolu

Jestlize vsechny transakce v dane mnozine transakci jsou dobre formovane a dvoufazove, pak kazdy jejich legalni rozvrh je usporadatelny. (Na druhou stranu, jeste porad tady hrozi deadlock.)

Casova razitka (timestamps)

Jedna se o jinou metodu pro zajisteni usporadatelnosti. Ke kazdemu objektu jsou prirazena dve razitka: cas posledniho cteni (TSR) a cas posledniho zapisu (TSW). Kazda transakce T dostane na svem zacatku hodnotu TS(T), ktera je unikatni a roste (napr. poradove cislo transakce).

• Transakce T vola operaci WRITE(X):
  • jestlize TSR(X) > TS(T), zrus transakci T a proved ROLLBACK(T) (nejaka transakce s razitkem vetsim nez TS(T) jiz cetla X pred tim, nez T melo sanci provest zapis),
  • jestlize TSW(X) > TS(T), zrus operaci WRITE(X) a pokracuj (nejaka transakce s razitkem vetsim nez TS(T) jiz zapisovala X, "nas" zapis by byl prepsan),
  • jinak WRITE(X), TSW(X):=TS(T).
• Transakce T vola operaci READ(X):
  • jestlize TSW(X) > TS(T), zrus transakci T a proved ROLLBACK(T) (nejaka transakce s razitkem vetsim nez TS(T) jiz zapisovala X pred tim, nez T melo sanci cist),
  • jinak READ(X), TSR(X):= max(TS(T),TSR(X)).

Zurnal (log)

Chteli bychom, aby i pri vypadku napajeni byla zachovana konzistence databaze. Popisu jeden z moznych zpusobu - "tvorba zurnalu s odlozenymi realizacemi zmen":
Behem provadeni transakce T jsou vsechny operace WRITE odlozeny do okamziku, nez se transakce dostane do stavu tesne pred operaci COMMIT (PC). Vsechny zmeny jsou zapisovany do zurnalu, jehoz zaznamy obsahuji trojice <T, jmeno_atributu, nova_hodnota>. Na pocatku provadeni transakce T se do zurnalu zapise <T, START>, ve stavu PC <T, COMMIT>. Teprve potom dochazi k zapisu zmen do databaze. Dojde-li k chybe v case pred dosazenim PC, staci informaci v zurnalu ignorovat a spustit RESTART (tj. moznost vzniku nove transakce). V pripade chyby, kdy cas chyby je za pocatkem stavu PC, jsou zaznamy zurnalu k dispozici pro provedeni operace REDO(T), ktera vyuzije zaznamu mezi <T,START> a <T,COMMIT>.