UČEBNÍ TEXTY OSTRAVSKÉ UNIVERZITY __________________________________________________ Přírodovědecká fakulta
RELAČNÍ DATABÁZE (DISTANČNÍ VÝUKOVÁ OPORA)
Zdeňka Telnarová
Aktualizovaná verze 2006 _____________________________________________ Ostravská univerzita
OBSAH 1 Modul 1 ....................................................................................................................................................... 6 1.1 Relační datový model .............................................................................................................................. 6
1.1.1 Úvod ................................................................................................................................. 6 1.1.2 Operace relační algebry ................................................................................................... 9 1.1.2.1 Nejpoužívanější operace ............................................................................................... 9 1.1.2.2 Základní množinové operace aplikované na relace..................................................... 11 1.1.3 Normalizace relačních schémat...................................................................................... 13 1.1.3.1 První normální forma relace ........................................................................................ 13 1.1.3.2 Funkční závislosti atributů ........................................................................................... 13 1.1.3.3 Druhá normální forma relace ....................................................................................... 13 1.1.3.4 Třetí normální forma relace ......................................................................................... 14 1.1.4 Transformace konceptuálních schémat.......................................................................... 14 1.1.4.1 Nejpoužívanější konstruktory E - R modelu................................................................. 14 1.1.4.2 Principy transformace E-R schématu do relačního ..................................................... 15 1.1.5 Integrita relačních schémat............................................................................................. 17 1.1.5.1 Referenční integrita ..................................................................................................... 17 1.1.5.2 Způsoby zachování referenční integrity....................................................................... 18 2 Modul 2 ..................................................................................................................................................... 21 2.1 Úvod do databázových jazyků............................................................................................................... 21
2.1.1 Opakování některých pojmů predikátové logiky ............................................................. 21 2.1.1.1 Symboly predikátové logiky ......................................................................................... 21 2.1.1.2. Konstrukty predikátové logiky ..................................................................................... 21 2.1.1.3. Interpretace formulí..................................................................................................... 22 2.1.2 Databázové jazyky.......................................................................................................... 22 2.1.2.1 Definice dotazu ............................................................................................................ 23 2.2 Relační algebra a relační kalkul ............................................................................................................ 24
2.2.1 Operace relační algebry ................................................................................................. 25 2.2.2 Další operace relační algebry ......................................................................................... 27 2.2.3 Přepisovací jazyk relační algebry ................................................................................... 29 2.2.4 Relační kalkul ................................................................................................................. 30 2.2.4.1 Abeceda n-ticového relačního kalkulu ......................................................................... 30 2.2.4.2 Formule relačního kalkulu............................................................................................ 30 2.2.4.3 Přepis z relační algebry do relačního n-ticového kalkulu............................................. 31 2.2.4.4 Přepisovací jazyk n-ticového relačního kalkulu .......................................................... 32
2
2.2.4.5 Obecný tvar existenčně kvantifikovaných formulí........................................................ 34 2.2.4.6 Obecný tvar univerzálně kvantifikovaných formulí....................................................... 34 2.2.4.7 Doménový relační kalkul.............................................................................................. 35 2.2.4.8 Atomické formule doménového relačního kalkulu ....................................................... 35 2.2.4.9 Věta o ekvivalenci........................................................................................................ 36 2.3 Řešené příklady v relační algebře a relačním kalkulu........................................................................... 37 3 Modul 3 ..................................................................................................................................................... 43 3.1 Jazyk SQL ............................................................................................................................................. 43
3.1.1 Části jazyka SQL ............................................................................................................ 44 3.1.2 Základní příkazy DDL ..................................................................................................... 44 3.1.3 Základní příkazy DML..................................................................................................... 46 3.1.4 Základní příkazy DQL ..................................................................................................... 48 3.2 Řešení příklady na dotazování v SQL, definování schématu a manipulaci s daty .............................. 61 4 Modul 4 ..................................................................................................................................................... 67 4.1 QBE - Query By Example...................................................................................................................... 67
4.1.1 Agregační funkce v QBE ................................................................................................ 69 4.1.2 Manipulace v QBE .......................................................................................................... 70 4.1.3 Inkluze ............................................................................................................................ 70 4.2 Řešené příklady v QBE ......................................................................................................................... 73 5 Modul 5 ..................................................................................................................................................... 76 5.1 Transakce - základní pojmy a vlastnosti ............................................................................................... 76
5.1.1 Vlastnosti transakcí......................................................................................................... 76 5.1.2 Globální a lokální transakce ........................................................................................... 76 5.1.3 Distribuovaný databázový systém .................................................................................. 77 5.2 Dvoufázový potvrzovací protokol .......................................................................................................... 78
5.2.1 Výpadky uzlů a přerušení transakce............................................................................... 79 5.3 Transakce jako jednotka zotavení z chyb ............................................................................................. 80
5.3.1 Žurnály(log files) ............................................................................................................. 81 5.3.2 Kontrolní body- checkpoints: .......................................................................................... 81 5.3.3 UNDO / REDO algoritmus .............................................................................................. 81 5.4 Synchronizace ....................................................................................................................................... 83
5.4.1 Dvoufázový uzamykací protokol ..................................................................................... 83 5.4.2 Globální uváznutí............................................................................................................ 84 5.4.3 Transakce v SQL ............................................................................................................ 85 6 Modul 6 ..................................................................................................................................................... 86 6.1 Přehled architektur databázových systémů........................................................................................... 86
3
6.1.1 Distribuce globálních relací............................................................................................. 87 6.1.2 Základy replikace dat...................................................................................................... 90 6.2 Zpracování dotazů v distribuované prostředí ........................................................................................ 92 6.3 Metody výpočtu spojení......................................................................................................................... 98 7 Modul 7 ................................................................................................................................................... 104 7.1 Objektově orientovaná analýza a návrh .............................................................................................. 104
7.1.1. Úvod ............................................................................................................................ 104 7.1.2 Nedostatky relačních SŘBD ......................................................................................... 104 7.1.3 Objektově orientovaná metodika .................................................................................. 105 7.1.4 Další objektově orientované metodologie.................................................................... 105 7.1.5 Požadavky, kladené na OODBS................................................................................... 107 7.1.6 Objektově orientované SŘBD....................................................................................... 107 7.1.7 Hlavní přínosy objektové technologie ........................................................................... 108 7.1.8 Kriteria kladená na OOSŘBD ....................................................................................... 108 7.1.9 Tři základní modely objektové metodologie.................................................................. 108 7.2 Model objektů ..................................................................................................................................... 109
7.2.1 Základní charakteristiky ................................................................................................ 110 7.2.1 Základní pojmy ............................................................................................................. 110 7.3 Dynamický a funkční model ................................................................................................................ 112
7.3.1 Dynamický model ......................................................................................................... 112 7.3.2 Základní pojmy ............................................................................................................ 113 7.3.3 Funkční model .............................................................................................................. 113 7.3.4 Základní pojmy ............................................................................................................. 113 7.4 Deduktivní pravidla při analýze a návrhu IS ....................................................................................... 114
7.4.1 Úvod do deduktivních pravidel...................................................................................... 114 7.4.2 Stratifikace .................................................................................................................... 115 7.4.3 Všeobecné principy dobře formovaných deduktivních pravidel.................................... 116 7.4.4 Využití deduktivních pravidel pro odvozování dat......................................................... 116 7.4.5 Příklady implementace v jazyku Chimera..................................................................... 117 7.4.6 Srovnání relačního a objektového pojetí ...................................................................... 119 7.4.7 Využití deduktivních pravidel pro definování integritních omezení ............................... 121 7.4.7.1 Vestavěná a generická integritní omezení................................................................ 122 7.4.7.2 Generické integritní omezení..................................................................................... 122 7.5 Řešené příklady deduktivních pravidel................................................................................................ 124
Použitá literatura.................................................................................................................... 131
4
5
1 MODUL 1 1.1 RELAČNÍ DATOVÝ MODEL Cíl: Cílem této kapitoly je, aby si čtenář zopakoval základní znalosti o relačních datových modelech, jak se s nimi již seznámil v předmětu Úvod do databází. Kapitola přináší základní ideje, na kterých je relační datový model založen, definici relačního modelu dat, základní pojmy. Čtenář si rovněž zopakuje základní manipulační prostředky, které lze v relačním datovém modelu nad daty využít. Po prostudování textu by měl mít čtenář přesnou představu o strukturách, do kterých se ukládají data v databázi. Dále by měl již naprosto přesně umět definovat pojmy uvedené v klíčových slovech. Co se týká databázových operací, čtenář by měl po přečtení této kapitoly mít základní přehled o operacích relační algebry. V následujících textech ještě bude databázovým operacím věnována značná pozornost. Pro správné navržení relačního schématu dat je nutné dodržovat pravidla normalizace, kterou si čtenář v této kapitole rovněž zopakuje, stejně jako integritní omezení schémat a pravidla pro transformaci konceptuálních schémat na datová relační schémata. Klíčová slova: RMD, databázová relace, NF, doména, primární klíč, cizí klíč, operace relační algebry, integritní omezení, transformace konceptuálních schémat.
Průvodce studiem: RMD má jediný konstrukt, kterým je databázová relace. Proto při transformaci konceptuálního modelu na model relační je třeba celou složitou realitu transformovat na množinu vcelku jednoduchých relací. Již tento fakt naznačuje, že bude skutečně velmi složité a někdy dokonce nemožné realitu natolik zjednodušit. Tato úvaha vede ke snaze vývoje datových modelů založených na objektových principech. To je ovšem v této kapitole ještě téma předčasné, přesto je dobré si uvedenou skutečnost uvědomit.
1.1.1 Úvod Relační datový model (RDM) byl poprvé popsán v roce 1970 E.F. Coddem a je zatím nejrozšířenějším datovým modelem, na kterém je založen návrh a tvorba databází. Základní ideje relačního modelu •
RMD důsledně odděluje data, která jsou chápána jako relace, od jejich implementace.
•
Přístup k datům je symetrický, tj. při manipulaci s daty se nezajímáme o přístupové mechanizmy k datům.
•
Pro manipulaci s algebra.
daty jsou k dispozici dva
6
silné prostředky - relační kalkul a relační
•
Pro omezení redundance normalizovat relace.
dat v
relační databázi
jsou navrženy pojmy umožňující
Základní definice RMD Mějme množiny D1, D2, D3,.......Dn. Z každé vyberme 1 prvek. Tím vytvoříme uspořádanou n-tici. Kartézský součin D1 x D2... je množina všech posloupností (x1,x2,...) kde x1 je prvkem D1 , x2 je prvkem D2... Relace je každá podmnožina kartézského součinu. Z hlediska databázových systémů jsou množiny D1, D2,.. množiny hodnot atributů a označují se jako tzv.domény. Od matematické relace se liší databázová relace v několika aspektech •
Relace je vybavena pomocnou strukturou, které se říká schéma relace. Schéma relace se skládá ze jména relace, jmen atributů a domén.
•
Prvky domén, ze kterých se berou jednotlivé komponenty prvků relace, jsou atomické (dále nedělitelné) hodnoty. Tomuto omezení se říká 1.normální forma relací (1NF).
Schéma relace R se vytvoří nad množinou atributů A1:D1,...An:Dn, kde Ai jsou jména atributů a Di jsou domény. Dvojici Ai:Di se říká atribut relace. Schéma relace lze zapsat R(A1:D1,....An:Dn). Relace R nad množinou A je libovolná podmnožina kartézského součinu domén D1 x ... x Dn. Doména náležící atributu C se označuje jako dom(C). Domény jsou obvykle primitivní typy dat (STRING, INTEGER...). Prvkům relace se říká n-tice, přičemž n určuje řád relace. Relační schéma databáze je dvojice (R,I), kde R je množina schémat relací a I je množina integritních omezení. Jedno z významných IO na relaci R(A) je existence primárního klíče. Primární klíč je množina atributů K z A, jejichž hodnoty jednoznačně určují (identifikují) n-tice relace R. K je minimální v tom smyslu, že nelze odebrat žádný atribut, aniž by to narušilo identifikační vlastnost. Atribut, který je součástí nějakého klíče se nazývá klíčový. Atributy, které nejsou součástí žádného klíče se nazývají neklíčové. Z podstaty RMD vyplývá, že každá relace má primární klíč. Protože relace jsou množiny, nesmí relace obsahovat duplicitní prvky. Dalším důležitým IO je referenční integrita. Toto omezení popisuje vztahy mezi daty ve dvou relacích. Atribut, kterého se referenční integrita týká, se nazývá cizí klíč (foreign key). Takové dvě relace se obvykle nazývají master/ detail, resp. parent/child, resp. independent/dependent. Česky obvykle hlavní/závislá někdy taky nezávislá/závislá, nadřazená/podřízená. Cizí klíč je atribut relace, který je v nadřazené relaci primárním klíčem.
Příklad: Hlavní tabulka: UČITEL(ČÍSLO, JMÉNO, PLAT, PŘÍPLATEK,...) Závislá tabulka: PŘEDMĚT(ZKRATKA, NÁZEV,......,GARANT) ČÍSLO z relace UČITEL je primárním klíčem a objevuje se v relaci PŘEDMĚT jako atribut GARANT. Atribut GARANT je cizí klíč. Jméno cizího klíče nemusí být stejné jako jméno
7
primárního klíče nadřazené relaci, ale cizí klíč musí být definován nad stejnou doménou, nad jakou je definován příslušný primární klíč nadřazené relace. Přípustnou relační databází se schématem (R, I) nazýváme množinu relací R1,...Rk takových, že jejich prvky vyhovují I. O takové množině relací říkáme, že je konzistentní. Formou reprezentace relací může být dvojrozměrná tabulka. Podmínky, které musí splňovat relační tabulka •
Všechny hodnoty v tabulce musí být elementární - tj. dále nedělitelné - podmínka 1NF.
•
Sloupce mohou být v libovolném pořadí.
•
Řádky mohou být v libovolném pořadí.
•
Sloupce musí být homogenní, tzn. domény).
•
Každému sloupci musí být přiřazeno jednoznačné jméno.
•
V relační tabulce nesmí být dva zcela stejné řádky. Tzn., že každý řádek je jednoznačně rozlišitelný.
ve sloupci musí být údaje stejného typu (z jedné
Shrnutí: Doména je množina hodnot stejného datového typu. Tyto hodnoty popisují nějakou vlastnost objektu. Relace je každá podmnožina kartézského součinu, jejíž konkrétní n-tice vznikly vybráním příslušných prvků z domén. Atribut je pojmenování pro každé užití hodnoty z domény v relaci. Záhlaví relace obsahuje jméno relace a jména atributů v relaci. Je v čase neměnné. Tělo relace obsahuje v čase proměnnou množinu n-tic hodnot, jejichž pořadí je dáno záhlavím relace. Stupeň relace je počet atributů relace. Kardinalita relace je počet řádků relace. Primární klíč je atribut nebo skupina atributů, který jednoznačně určuje n-tice relace. Pokud je třeba použít více atributů pro jednoznačné určení n-tice, potom hovoříme o tzv. složeném primárním klíči. Pokud je více atributů, které splňují pravidlo pro primární klíč, jeden zvolíme jako primární a ostatní jsou alternativní klíče. Definice primárního klíče: Primární klíč je podmnožina atributů relace, která: 1) jednoznačně identifikuje každý prvek relace 2) 2) není redundantní, tj. žádný její atribut nelze vynechat, aniž by podmínka 1) přestala platit. Pokud více atributů může splňovat výše uvedenou definici, jedná se pak o tzv. kandidáty primárního klíče. Primární klíč v relaci smí být pouze jeden, ostatní kandidáti se stávají tzv. alternativními klíči.
Kontrolní otázky: 1. Co je to databázová relace a čím se liší od relace matematické?
8
2. Jak lze vytvořit každou instanci databázové relace? 3. Čím lze identifikovat jednotlivé n-tice relace? 4. Kolik může mít relace primárních klíčů?
Pojmy k zapamatování: Doména Atribut Relace Kandidát primárního klíče Primární klíč Alternativní klíč Kardinalita relace Stupeň relace Cizí klíč 1NF
1.1.2 Operace relační algebry
Průvodce studiem: Operace relační algebry, ať již speciální operace (projekce, selekce a spojení) nebo operace množinové jsou základem mnoha dotazovacích jazyků a jsou základem (spolu s relačním kalkulem) pro pochopení problematiky dotazování a následně získávání informací z databáze. Jedná se o širokou problematiku, které bude věnován dostatečný prostor v následujících kapitolách, proto jsou zde umístěny pouze základní informace, které jsou opakováním z předmětu Úvod do databází. Relační algebra je nástrojem pro manipulaci s relacemi. Je to jazyk, který pracuje s celými relacemi. Operátory relační algebry se aplikují na relace a výsledkem jsou opět relace.
1.1.2.1 Nejpoužívanější operace •
Projekce
•
Selekce
•
Spojení
Projekce Umožňuje potlačit označené atributy v relaci. Umožňuje přejít z relace o n sloupcích na relaci o p sloupcích, přičemž p < n. Nově vzniklá relace bude obsahovat p sloupců. Může
9
obsahovat i méně řádků než původní relace, protože duplicitní řádky se v relaci nesmějí vyskytovat. Selekce Někdy se vyskytuje termín restrikce. Operací selekce vznikne nová relace vybráním řádků z původní relace na základě logické podmínky. Podmínka je zadána Booleovským výrazem (pomocí logických spojek and, or, not), jehož atomické formule mají tvar t1θ t2, kde θ je <,>,=,<=,>=,<>, ti je buď konstanta nebo jméno atributu. Spojení Spojení dvou relací vytvoří třetí relaci. Výsledná relace vždy obsahuje všechny kombinace, které vyhovují zadané podmínce. Podmínka vyjadřuje vztah mezi dvěma relacemi. Spojení relací se zajišťuje pomocí společného atributu. Jednotlivé řádky z 1.relace se spojí s příslušnými řádky z 2.relace. Relace se nespojují podle názvů atributů, ale podle jejich hodnot. Definice: Spojení relací R a S podle podmínky θ na atributu A z R a atributu B z S je relace R[ A θ B] S = { rs ⏐ r ∈ R ∧ s ∈ S ∧ rR[A] θ rS[B]} kde rR[A], rS[B] jsou hodnoty atributů A, resp. B relací R, resp. S. 3 druhy spojení 1. spojení na rovnost atribut1 = atribut2 2. spojení na nerovnost atribut1 <> atribut2 3.vnější spojení - INKLUZE Funguje stejně jako spojení na rovnost s tím rozdílem, že do výsledné relace se přidají i nespojené řádky z první relace (ev. z druhé relace, ev. z obou relací). Pak příslušné atributy nejsou vyplněny (nabývají hodnoty NULL).
Příklad: Relace 1 Číslo
Jméno
Město
Ulice
1
Jiří
Kladno
Pražská 32
19
2
Karel
Praha
Evropská 1
17
3
Jan
Brno
Tichého 43
16
4
Karel
Brno
Dlouhá 21
19
5
Tomáš
Praha
Široká 7
20
10
Věk
Relace 2 ČísloS
Č-typu
Rok-výroby
Cena
1
101
1988
100
1
701
1989
105
2
101
1990
200
7
701
1991
300
Podmínka pro spojení na rovnost: Číslo → Relace 1 = ČísloS → Relace 2 Vznikne nová relace: Číslo
Jméno
Město
1
Jiří
Kladno
1
Jiří
2
Karel
Ulice
Věk
Čtypu
Rokvýroby
Cena
Pražská 32
19
101
1988
100
Kladno
Pražská 32
19
701
1989
105
Praha
Evropská 1
17
101
1990
200
Zavedeme jednoduchý jazyk pro vyjádření operací relační algebry:
Příklad: Z relace AUTA vybereme všechna identifikační čísla, názvy a rok výroby aut, jejichž cena je menší než 150 000 Kč. Klíčová slova budou podtržena. restrict AUTA where cena < 150000 giving MEZIVYS1 project MEZIVYS1 over ident_a, nazev_a, rok_vyr, cena giving VYSL Tuto operaci provedeme pomocí vhnízdění (nesting): project (restrict AUTA where cena < 150000) over ident_a, nazev_a, rok_vyr, cena giving VYSL
1.1.2.2 Základní množinové operace aplikované na relace Podmínky pro všechny množinové operace: •
Obě relace jsou stejného stupně, tj. mají stejný počet sloupců.
•
Každý i-tý atribut z obou relací je definován na stejné doméně.
Sjednocení
R∪S = {t ⏐ t ∈ R ∨ t ∈ S}
11
Sjednocení vytvoří novou relaci, která obsahuje n-tice obou výchozích relací. Pokud mají tyto relace některé n-tice shodné, ve výsledné relaci se objeví pouze jednou. Průnik
R∩S = {t ⏐ t ∈ R ∧ t ∈ S} Výsledná relace bude obsahovat pouze totožné n-tice obou relací. Množinový rozdíl
R - S = {t | t ∈ R ∧ t ∉ S} Nová relace bude obsahovat všechny n-tice první relace, ale pouze ty, které se nevyskytují v druhé relaci. Symetrický rozdíl Nová relace bude obsahovat všechny n-tice obou relací, s výjimkou těch, které se vyskytují v obou relacích. Kartézský součin Již není typickou množinovou operací, protože nesplňuje její 2 podmínky. R x S relace R stupně m a relace S stupně n je relace stupně m+n, která je definována:
R x S = {rs | r ∈ R ∧ s ∈ S} kde rs představuje prvek relace (r1, r2, ...rm,s1,s2,....sn) r,s označuje prvky relací R a S. Kartézský součin vytvoří novou relaci tak, že spojuje n-tice z obou relací systémem každý s každým. Počet n-tic (kardinalita) nové relace je součinem kardinalit obou vstupních relací.
Kontrolní otázky: 1. Jaké typy operací spojení znáte? 2. Co musí platit o relacích, pokud na ně chceme uplatnit operaci sjednocení, průniku či rozdílu? 3. Jaká je kardinalita a studeň relace, která je výsledkem operace kartézský součin? 4. Ze kterých operací lze odvodit operaci spojení?
12
Pojmy k zapamatování: Projekce Selekce Spojení Sjednocení Průnik Rozdíl Kartézský součin
1.1.3 Normalizace relačních schémat 1.1.3.1 První normální forma relace Báze dat je nejjednodušší a nejpřehlednější, jsou-li relace, které ji reprezentují, definovány nad doménami, jejichž prvky jsou jednoduché (nejsou to opět relace, či jiné struktury). O takových relacích se říká, že jsou v první normální formě a příslušné atributy se nazývají jednoduchými. Relace je v první normální formě (1NF), jsou-li všechny její atributy atomické (nedělitelné) Atributy, které nejsou jednoduché, jsou složené. Některé relace v první normální formě však mají i negativní vlastnosti z hlediska redundance a konzistence dat. Problémy spojené s redundancí dat vyplývají zpravidla ze skutečnosti, že hodnota některého atributu může zcela určovat hodnoty jiných atributů. Sdružování takových atributů v jedné relaci se ukazuje jako nevhodné. Problematice dekompozice relací neboli jejich normalizaci budou proto věnovány následující odstavce.
1.1.3.2 Funkční závislosti atributů Problém, který byl nastíněn v předcházejícím odstavci, spočívá ve vzájemných závislostech atributů jedné relace. Pro tuto závislost se zpravidla používá termínu funkční závislost, i když z hlediska matematického nejde o funkci, stejně jako pojem relace zcela neodpovídá matematickému pojetí (v databázovém pojetí se totiž relace stejně jako funkční závislosti mění v čase ). Nechť R(A:D) je relační schéma a X, Y jsou jednoduché nebo složené atributy. Atribut Y je funkčně závislý na atributu X, (X→Y ), platí-li pro každou instanci (n-tici) relace R, že pro libovolné dva prvky relace, které se shodují v hodnotě atributu X, platí, že se shodují i v atributu Y. Jinými slovy: Atribut Y je funkčně závislý na atributu X, je-li ke každé hodnotě atributu X přiřazena právě jedna hodnota atributu Y. Atribut Y je úplně funkčně závislý na složeném atributu X, je-li na X funkčně závislý a zároveň není funkčně závislý na žádné z jeho složek.
1.1.3.3 Druhá normální forma relace Samotný požadavek, aby se relace nacházela v první normální formě, tj. aby každý atribut relace byl definován na jednoduché doméně, nevede vždy k nejžádanějším výsledkům.
13
Relace R je ve druhé normální formě (2NF), je-li v první normální formě a jestliže pro každý neklíčový atribut platí, že je úplně funkčně závislý na primárním klíči. Proces transformace relace z nižší normální formy (zde v 1.NF) na relaci ve vyšší normální formě (zde ve 2.NF) se nazývá normalizace relace. Relace v některé z vyšších normálních forem je zároveň relací ve všech vůči ní nižších normálních formách. Je zřejmé, že vyšší normální formu relace lze vytvořit vhodnou dekompozicí relace původní. Požaduje se však, aby výchozí relace byla z výsledných komponent rekonstruovatelná, tj. aby při dekompozici nedošlo ke ztrátě informace.
1.1.3.4 Třetí normální forma relace Nechť X, Y, Z jsou atributy (jednoduché nebo složené) daného relačního schématu a nechť mezi dvojicemi atributů platí:
Pak je atribut Z tranzitivně závislý na atributu X. Nutnost podmínky nezávislosti X na Y vyplývá ze skutečnosti, že v opačném případě by v každém relačním schématu se dvěma a více možnými klíči byly všechny neklíčové atributy tranzitivně závislé na kterémkoliv z klíčů. Relace R je v třetí normální formě (3NF), je-li ve druhé normální formě a platí-li, že žádný neklíčový atribut není tranzitivně závislý na žádném klíči relace R. Z definice relace ve třetí normální formě vyplývají tyto její vlastnosti •
Žádný neklíčový atribut relace není ani částečně ani tranzitivně závislý na nějakém klíči relace, jsou pouze úplně funkčně závislé na primárním klíči.
•
Neklíčové atributy jsou navzájem nezávislé.
Problémy, které mohou u relací v třetí normální formě nastat, mohou však vyplynout ze vzájemně částečně nebo tranzitivně závislých klíčových atributů. Kandidátní klíče, pokud nejsou jednoduché, se totiž mohou částečně překrývat. Dekompozice relací, které vedou ke třetí normální formě, mohou navíc být nejednoznačné a vést k nestejně kvalitním výsledkům. Nedostatky plynoucí ze vzájemných závislostí klíčových atributů eliminuje Boyce - Coddova normální forma BCNF, která vylučuje všechny netriviální funkční závislosti atributů kromě závislostí na klíčích relace. Schéma relace R(A:D) je v Boyce-Coddově normální formě ( BCNF), je-li v první normální formě a platí-li pro každou funkční závislost atributu A na atributu X , která není triviální, že X je klíčem v R a A je neklíčový atribut. Je zřejmé, že každé relační schéma, které je v BCNF je též ve třetí normální formě, nikoliv však naopak. Existují relační schémata ve třetí normální formě, která nejsou v BCNF.
1.1.4 Transformace konceptuálních schémat 1.1.4.1 Nejpoužívanější konstruktory E - R modelu ENTITA •
Obecná (bez rozlišení druhu). 14
•
Silná (kmenová, základní, regulární), tj. taková, která existuje nezávisle na jiných entitách.
•
Slabá (popisná) je entita, která je identifikačně závislá na jiné entitě, resp. na jiných entitách.
•
Vazební (asociativní) je entita, která realizuje vazbu mezi entitami.
•
Generalizace (nadtyp).
•
Specializace (podtyp).
VZTAH •
n -ární vztah je vztah obecně mezi n entitami.
•
Binární vztah existuje mezi dvěma entitami.
•
Kardinalita vztahu vyjadřuje max. a min. počet výskytů zúčastněných entit ve vztahu.
•
Existenční závislost (někdy také označována jako tzv. povinné členství ve vztahu) vyjadřuje tu skutečnost, že instance existenčně závislé entity nemohou existovat, aniž by vstoupily do vztahu s nadřazenou entitou.
•
Identifikační závislost je silnější formou existenční závislosti. Identifikačně závislá entita je rovněž existenčně závislá a navíc její instance nelze identifikovat pomocí vlastních atributů a k identifikaci takové entity se používá identifikační klíč nadřazené entity.
ATTRIBUT •
Jednoduchý, tj. dále nedělitelný.
•
Složený z více atributů.
•
Základní, tj. takový, který nelze odvodit z jiných atributů.
•
Odvoditelný z jiných atributů.
•
Vícehodnotový, tj. takový který v rámci jedné instance entity může nabývat více hodnot.
KLÍČ •
Identifikační - slouží k identifikaci jednotlivých instancí entity. V rámci jedné entity smí být pouze jeden.
•
Alternativní - Kandidát na identifikační klíč, který však nebyl vybrán. Slouží k rychlému vyhledávání.
•
Cizí klíč umožňuje modelovat vztahy mezi entitami. Je to atribut entity, který je v nadřazené entitě identifikačním klíčem.
•
Inverzní klíč slouží k rychlému vyhledávání. Jeho hodnoty v rámci jedné entity mohou být duplicitní.
1.1.4.2 Principy transformace E-R schématu do relačního Entitní a vztahové typy se převádějí na relace. Čtenář relačního schématu, který nezná konceptuální schéma tedy obecně nemusí být schopen rozlišit, která relace odpovídá entitnímu a která vztahovému typu. Převedení silného entitního typu •
Entita se převede na relaci.
15
•
Identifikační klíč se převede na primární klíč.
•
Popisné atributy definují domény relace.
Problém může nastat v souvislosti s normalizací relací. Cílem je, aby výsledná relace byla aspoň v 3. NF nebo v BCNF. Dekompozice pak způsobí nárůst relací, které nemají odpovídající entity v E-R diagramu. Do jisté míry toto lze řešit pohledy. Reprezentace vztahů vztahy 1 : 1 a) Má-li E1 i E2 nepovinné členství ve vztahu V, definují se 3 relace E1 - R1 , E2 - R2 , V - R. R bude obsahovat klíče schémat R1 a R2 ,jako cizí klíče. Libovolný z nich může v R být primárním klíčem. Další atributy v R budou odpovídat atributům ve V. b) Má-li E1 nepovinné a E2 povinné (nebo obráceně). Budou se vytvářet pouze relace R1 a R2. Existenční závislost E2 na E1 vyjádříme tak, že k R2 připojíme jako cizí klíč klíčové atributy R1. Atributy vztahu V budou umístěny do R2. c) Mají-li oba povinné členství, můžeme vytvořit jediné schéma relace R, které vznikne z těchto dvou entit. Primárním klíčem bude libovolný z identifikačních klíčů, přidáme atributy V. vztahy 1 : N Ve vztahu s kardinalitou 1 : N je entita vstupující n -ti instancemi determinantem vztahu.
do vztahu nazývána
a) Má-li determinant (E1) povinnou účast ve vztahu V, definujeme 2 relace R1 a R2. Ke schématu R1 připojíme klíčové atributy R2. Primární klíč R1 odpovídá identifikačnímu klíči determinantu E1. b) Má-li determinant (E1) nepovinnou účast ve vztahu V, definujeme tři relace R1, R2, R. R bude obsahovat klíče schémat R1 a R2 jako cizí klíče. Klíč schématu R1 bude v R primárním klíčem. Další atributy budou odpovídat atributům vztahu V. Reprezentace vícehodnotových atributů
Příklad: Následující příklad ukazuje možnost výskytu vícehodnotového atributu v konceptuálním modelu a jeho transformaci. Analytik sestavil konceptuální schéma tak, že použil vícehodnotový atribut ZAMĚSTNANEC (OSOBNÍ ČÍSLO, ..... RODNÉ_ČÍSLO_DÍTĚTE: Multi) To konceptuální model připouští Jak převést takovou entitu na relace? 1. Některé relační SŘBD připouštějí tabulky s vícehodnotovými sloupci 2. Jestliže se vícehodnotový atribut váže na maximální počet výskytů m a databázový model připouští hodnotu NULL ve sloupci tabulky, budou atributy v tabulce RODNÉ_ČÍSLO_DÍTĚTE_ i pro i = 1,.... m a nevyužité atributy budou mít hodnotu NULL. 3. Zavést dvě relace: 16
ZAMĚSTNANEC (OSOBNÍ ČÍSLO, ....) DATA_NAROZENÍ (OSOBNÍ ČÍSLO, RODNÉ ČÍSLO DÍTĚTE) Každému dítěti bude odpovídat jedna n -tice v relaci data_narození. Konstrukce klíče je nejednoznačná a) Klíčem může bát složený klíč např. OSOBNÍ ČÍSLO, RODNÉ ČÍSLO DÍTĚTE b) Klíčem může být pouze vícehodnotový atribut RODNÉ ČÍSLO DÍTĚTE Reprezentace slabého entitního typu Slabý entitní typ je reprezentován relací, který kromě svých atributů mái atributy identifikačního vlastníka. Je třeba dbát na to, aby identifikační vlastník byl pouze jeden. Identifikační klíč je pak tvořen množinou atributů slabého entitního typu + atributy identifikačního vlastníka.
1.1.5 Integrita relačních schémat Požadavek integrity dat v databázi (jejich souladu se zobrazovaným světem objektů) vede k nutnosti definovat pro domény atributů jednotlivých relačních schémat a jejich vzájemné vztahy jistá omezení, která zabraňují možnostem atributů nabývat nereálných hodnot. Tato omezení se formulují pomocí soustavy uzavřených logických formulí v jazyce predikátové logiky. Pro relační báze dat je kromě skutečnosti, že entity i vztahy se reprezentují stejným způsobem, tj. pomocí relací, charakteristickým rysem i to, že splňují tři pravidla integrity. Prvním z těchto pravidel je pravidlo entitní integrity pro relační báze dat a spočívá v požadavku, aby primární klíč relace měl pro všechny její prvky (n-tice) svou hodnotu. Druhé pravidlo integrity je doménová integrita, která požaduje, aby hodnoty atributů odpovídaly předem definovaným doménám (množinám hodnot atributů). Základní definicí domény je datový typ atributu. Kromě toho je však možno definovat podmínky platnosti (logické formule), které musí být při vkládání dat do databáze splněny. Třetí je pravidlo referenční integrity (vztahové), které se týká možností používání "cizích" klíčů relací a spočívá v požadavku, aby ke každé definované hodnotě cizího klíče existovala odpovídající hodnota primárního klíče nadřazené relace. Tomuto tématu se budeme věnovat podrobněji.
1.1.5.1 Referenční integrita K definování referenční integrity slouží primární klíč (Primary Key) nezávislé entity a cizí klíč (Foreign Key) závislé entity. Na primární klíč jsou kladeny následující podmínky •
Hodnota primárního klíče musí být unikátní.
•
Entitní typ může mít pouze jeden primární klíč.
•
Primární klíč může být i složený klíč, tj. složený z více atributů.
•
Každá složka primárního klíče musí být definována jako NOT NULL.
Podmínky kladené na cizí klíč •
Cizí klíč a primární klíč se musí skládat ze stejného počtu atributů.
•
Odpovídající atributy musí být definovány nad stejnými doménami a jejich pořadí musí být stejné.
17
•
Závislý entitní typ může mít více cizích klíčů z více nadřazených entit.
•
Cizí klíč může nabývat hodnoty NULL, pokud definuje pouze existenční typ vztahu.
•
Cizí klíč nesmí nabývat hodnoty NULL, pokud definuje identifikační typ vztahu.
•
Cizí klíč nabývá hodnoty NULL, pokud aspoň jedna jeho složka nabývá hodnoty NULL.
Pro nezávislé entitní typy je referenční integrita hlídána u operací DELETE a UPDATE. Pro závislé entitní typy je hlídána operace INSERT a UPDATE.
1.1.5.2 Způsoby zachování referenční integrity RESTRICT - při mazání a aktualizaci v nezávislém entitním typu se restriktivně vyžaduje, aby v podřízeném entitním typu byla nejdříve vymazána nebo aktualizována svázaná instance. Neníli tomu tak, mazání resp. aktualizace v nadřazeném entitním typu je zakázáno. Zápis nové instance do podřízeného entitního typu je zakázán, nenachází-li se odpovídající instance v nadřazeném entitním typu. CASCADE - způsobí kaskádovou aktualizaci resp. mazání v podřízeném entitním typu při aktualizaci resp. mazání v entitním typu nadřízeném. Tento způsob může způsobit kaskádovité mazání velkého počtu instancí, proto je třeba jeho použití bedlivě zvážit. SET NULL - při aktualizačních operacích je možno z důvodu zachování referenční integrity použít nastavení cizího klíče na hodnotu NULL. Tento způsob nelze použít u identifikačního typu vztahu, kde cizí klíč podřízeného entitního typu je součástí primárního klíče. Primární klíč (a to žádná jeho složka, pokud se jedná o složený klíč) nesmí nabývat hodnoty NULL.
Příklad: Příklad demonstruje jedno z možných nastavení pravidel pro zachování referenční integrity. Typ entity/operace
Identifikační vztah
Existenční vztah
Závislá/Delete
Bez omezení
Bez omezení
Závislá/Insert
Restrict
Set Null
Závislá/Update
Restrict
Set Null
Nezávislá/Delete
Cascade
Set Null
Nezávislá/Insert
Bez omezení
Bez omezení
Nezávislá/Update
Cascade
Set Null
18
Shrnutí: Prostředkem pro správné navržení relačních schémat s důrazem na odstranění redundance dat je normalizace relačních schémat. Je založena na odhalování funkčních závislostí mezi jednotlivými atributy relace. Podmínkou je, aby byly všechny relace v relačním schématu minimálně v 3NF. Při transformaci konceptuálních schémat na relační datová schémata je třeba se držet navržených postupů a především se zabývat typy vztahů mezi jednotlivými entitami, povinným či nepovinným členstvím ve vztahu, typy atributů (vícehodnotový atribut, složený atribut, atd). Relační datové schéma disponuje mocným nástrojem pro udržování konzistence databáze a tímto nástrojem jsou integritní omezení. Existují tři typy integritních omezení, které je třeba při definici schématu databáze definovat. Jedná se o IO doménové, entitní a referenční.
Kontrolní otázky: 1. Co je základní vlastností atributů navržených relací pro určení normální formy? 2. Jaké znáte normální formy a co vyjadřují? 3. Jaký je postup při transformaci E-R modelu na relační datový model? 4. Co je to referenční integrita a jak je možné ji hlídat?
Pojmy k zapamatování: 1NF, 2NF, 3NF, BCNF Transformace konceptuálních schémat Doménová integrita Entitní integrita Referenční integrita
Průvodce studiem: Tato kapitola byla poněkud obsáhlá, ale doufám, že jste ji bez komplikací zvládli. Přece jen se jedná o opakování, čili o věci, které by vám měly být známy. Pokud po prostudování této kapitoly ještě stále existují místa, která vám nejsou jasná, ev. máte o něčem pochybnosti, nerozpakujte se kontaktovat tutora, ev. vyvolat diskusi se svými spolužáky. Pro čtení
19
následujících kapitol je totiž bezpodmínečně nutné, abyste tuto opakovací kapitolu zvládli na výbornou!
20
2 MODUL 2 2.1 ÚVOD DO DATABÁZOVÝCH JAZYKŮ Cíl: Cílem této kapitoly je připomenout čtenáři základní pojmy predikátové logiky, se kterými budou pracovat další kapitoly. Dalším cílem je seznámit čtenáře s pojmem databázové jazyky a provést jejich rozčlenění. Čtenář po prostudování kapitoly by měl umět vyjmenovat symboly a konstrukty predikátové logiky. Dále by měl umět definovat, co to jsou dotazovací jazyky a z jakých částí se skládají a měl by umět definovat, co je to v relačním pojetí dotaz a odpověď. Klíčová slova: JDD, JMD, JRD, dotazovací jazyk, dotaz, relační algebra, relační kalkul, term, atomická formule, formule.
2.1.1 Opakování některých pojmů predikátové logiky
Průvodce studium: Pro definování dotazů v relačních databázích se neobejdeme bez znalostí predikátové logiky. To základní a nejdůležitější, co potřebujete vědět z této oblasti logiky, vám předkládá kapitola 2.1.1. Samozřejmě není možné se pouštět do podrobných definic a důkazů, jsou zde uvedeny pouze základní pojmy. Pokud vám nebude cokoli jasné, bude potřeba sáhnout po učebnici nebo skriptech z logiky. Mohu doporučit [7].
2.1.1.1 Symboly predikátové logiky 1) proměnné
a, b, c, x, y.....
2) n-ární funkční symboly
0-ární funkční symbol je konstanta n-ární predikátové symboly
3)logické spojky
¬, ∧, ∨, →, ↔
4) kvantifikátory
∀,∃
2.1.1.2. Konstrukty predikátové logiky 1) TERM Termem může být konstanta, proměnná, funkce. Vyhodnocením termu se získá prvek množiny hodnot (universa discursu). Př. sin(x), a2 - a + 1, 5, y..... 2) ATOMICKÁ FORMULE
21
Se skládá z predikátového symbolu, za kterým v závorkách je term. Př. R(x), kde x je n-ticová proměnná, do které se ukládají hodnoty n atributů relace R (n-tice relace R), R je jméno relace (predikátový symbol). Vyhodnocením atomické formule se získá hodnota true nebo false. 3) FORMULE Z atomických formulí lze vytvářet formule pomocí: •
Logických spojek.
•
Kvantifikátorů.
Hodnota formule je vždy true nebo false. Proměnná ve formuli (n-ticová proměnná) může být buď volná nebo vázaná. Proměnná x je vázaná ve formuli A, jestliže A tvoří dosah kvantifikátoru obsahujícího x. Formule, které obsahují alespoň jednu volnou proměnnou, se nazývají otevřené.
2.1.1.3. Interpretace formulí Interpretace I se skládá z: 1) Neprázdné množiny U, která se nazývá doména. 2) Množiny n-árních funkcí f pro každý funkční symbol. 3) Množiny n-árních relací R pro každý predikátový symbol. Ohodnocení h proměnných v interpretaci I je funkce: h : Var U, kde Var je množina všech proměnných, U jsou jména prvků světa objektů. Formule A je splněna v interpretaci I, jestliže je pravdivá pro každé ohodnocení proměnných h.
2.1.2 Databázové jazyky Databázové jazyky, dodávané s příslušným systémem řízení báze dat (SŘBD), se obecně dělí na: 1) Jazyky pro definici dat JDD, angl. DDL (Data Definition Language) Jsou určeny pro správce databáze. Jazyky obsahují prostředky pro definice a modifikaci schématu databáze, definice relací a integritních omezení. Dále prostředky pro definování tzv. pohledů. 2) Jazyky pro manipulaci dat JMD, angl. DML (Data Manipulation Language) Tyto jazyky transformují jeden stav databáze do druhého a představují následující operace: •
Přidávání dat do databáze (INSERT).
•
Odebírání dat z databáze (DELETE).
•
Změna dat v databázi (UPDATE).
Veškeré operace musí být vykonány tak, aby nebyla narušena integrita dat. O integritu databáze se stará SŘBD na základě definovaných integritních omezení. 3) Jazyky pro řízení dat JRD, angl. DCL (Data Control Language) Prostředky pro zpracování transakcí, prostředky administrace databáze atd.
22
4) Jazyky pro dotazování - dotazovací jazyky, angl. DQL (Data Query Language) Jazyky pro dotazování (získávání informací z databáze) jsou nejpouživanějšími. V relačních databázích dotazování vychází ze dvou teoretických základů, z relační algebry a relačního kalkulu. Vhodnou interpretací dat uložených v databází lze z databáze získat informace. Proces interpretace dat se dá jednoduše vyjádřit jako proces tvorby dotazu (formule dotazu), vyhodnocení dotazu a poskytnutí odpovědi. V relačních databázích je odpovědí relace, jejíž ntice splňují podmínky, tj. ohodnocují formuli dotazu jako true. Rozlišujeme tyto dotazovací jazyky: a) Navigační (procedurální, preskriptivní, algebraické). Při formulaci dotazu je třeba zadat algoritmus, jako posloupnost operací prováděných nad relacemi, který zajistí výběr příslušných dat. Navigační jazyky jsou založeny na relační algebře. b) Specifikační (neprocedurální, deskriptivní, deklarativní). Požadavky na výběr se zadávají jako predikát, charakterizující výslednou relaci. Výsledek výběru dat je relace, jejíž n-tice splňují podmínky výběru uvedené ve formuli. Specifikační jazyky jsou založeny na relačním kalkulu. Každý požadavek zadaný v relační algebře se dá vyjádřit v relačním kalkulu a naopak!
2.1.2.1 Definice dotazu Dotaz typu S je funkce q, která pro každou databázi S* poskytne odpověď q(S*), případně je na S* nedefinována. V relačních databázích je q (S*) opět relace. Dotazovací jazyky obsahují: 1) Porovnávací operátory 2) Logické spojky 3) Aritmetické operátory 4) Množinové operátory 5) Relační operátory (projekce, selekce, spojení) 6) Množinové funkce (COUNT) 7) Agregační funkce (MAX, MIN, SUM.......) 8) Operátory pro práci s časem Nejpoužívanější relační dotazovací jazyky: SQL, QUEL, QBE
Shrnutí: Systémy řízení báze dat, založené na relačním datovém modelu, disponují poměrně velmi dobře propracovaným aparátem tzv. databázových jazyků. Databázové jazyky jsou členěny na jazyky pro definování dat, jazyky pro manipulaci s daty, jazyky pro řízení dat a dotazovací jazyky. Nejfrekventovaněji používané jsou operace dotazovacích jazyků, protože se používají k získávání informací z databáze. Dotazovací jazyky v relační modelu jsou založeny na relační algebře (vychází z množinové matematiky, kterou rozšiřuje o speciální operace) a na relačním kalkulu (vychází z predikátové logiky 1. řádu).
23
Kontrolní otázky: 1. Co je to n-ticová proměnná? 2. Co je to term a jakých hodnot může nabývat? 3. Co je to formule a jakých hodnot může nabývat? 4. Jak se člení databázové jazyky v relačních SŘBD? 5. Co je to dotaz, co je to odpověď?
Pojmy k zapamatování: JDD JMD JRD Dotazovací jazyky Dotaz - odpověď Relační algebra Relační kalkul Term Atomická formule Formule
2.2 RELAČNÍ ALGEBRA A RELAČNÍ KALKUL Cíl: Kapitola Relační algebra a relační kalkul je z hlediska dalšího pochopení problematiky dotazování v prostředí relačních databází klíčovou. Čtenář po jejím prostudování by měl znát veškeré operace relační algebry a relačního kalkulu a to jak z definice, tak pomocí přepisovacího jazyka. Každý dotaz na data by měl být schopen zapsat v obou dotazovacích jazycích. Každý dotaz v relační algebře by měl umět přepsat do relačního kalkulu a opačně. Klíčová slova: Základní operace relační algebry, odvozené operace, přepisovací jazyk relační algebry, relační kalkul, přepisovací jazyk relačního kalkulu, věta o ekvivalenci. Relační algebra je procedurální jazyk. Skládá se z množiny operací, které jsou uplatňovány na jednu nebo dvě relace. Výsledkem operace relační algebry je opět relace. Soubor základních
24
operací relační algebry představuje operace sjednocení, rozdíl, součin, projekce a selekce. Ostatní operace jako je průnik, podíl a spojení jsou operace, které se dají vyjádřit pomocí základních operací a neovlivňují výběrovou schopnost relační algebry.
2.2.1 Operace relační algebry Sjednocení
UNION
je binární operace, která se uplatňuje na relace stejného stupně, jejich atributy jsou definovány nad týmiž doménami. Výsledná relace obsahuje řádky buď jedné nebo druhé relace. Duplicitní řádky nejsou připuštěny. Sjednocení relací R a S se označuje R∪S a je definováno R∪S = {t ⏐ t ∈ R ∨ t ∈ S}
Příklad: R:
A
B
x
C
D
5
y
8
y
9
z
5
z
1
z
1
R∪S : x
5
y
9
z
1
y
8
z
5
Rozdíl
S:
DIFFERENCE
je binární operace, která se uplatňuje na relace stejného stupně, jejich atributy jsou definovány nad týmiž doménami. Výsledná relace obsahuje řádky relace R, které neobsahuje relace S. Rozdíl relací R a S se označuje R - S a je definován R - S = {t | t ∈ R ∧ t ∉ S}
Příklad: R - S: x
5
y
9
25
Součin
CARTESIAN PRODUCT
je binární operace nad relací R stupně n a relací S stupně m. Součin se označuje R x S a je definován R x S = {rs | r ∈ R ∧ s ∈ S} rs = (r1, r2, ...., rn, s1, s2, ..., sm). Stupeň výsledné relace je n+m, kardinalita výsledné relace je n*m.
Příklad: R:
A
B
x
C
D
5
y
8
y
9
z
5
z
1
z
1
R x S: x
5
y
8
x
5
z
5
x
5
z
1
y
9
y
8
y
9
z
5
y
9
z
1
z
1
y
8
z
1
z
5
z
1
z
1
Projekce
S:
PROJECT
Nechť R je relace stupně n. Projekcí je nazýván výběr specifikovaných atributů Ai1,...Aim, kde 1 ≤ ij ≤ n a je označován jako R[A]. Projekce je definována R[ A ] = { r[ A ] r ∈ R }, kde r[ A ] = (ri1, ......, rim)
Příklad: R:
A
B
C
R[A]: A
R[A,B]:
a
1
x
a
a
1
b
2
y
b
b
2
c
3
z
c
c
3
a
4
x
a
4
26
A
B
Selekce
SELECTION
Nechť R je relace stupně n a ϕ( r ) je výraz tvaru i θ ‘a’ , ‘a’ θ i resp. i θ j, kde i, j jsou indexy komponent, a je prvek domény , θ je binární predikát (např. <, =, >, ≥, ≠, ≤). Výběr z relace R podle ϕ se označuje R(ϕ) a je definován R(ϕ) = {r ⏐ r ∈ R ∧ ϕ( r ) }
Příklad: R:
A
B
C
a
1
b
R( A = ‘a’ ):
A
B
C
x
a
1
x
2
y
a
4
a
c
3
z
a
4
a
R( A = C):
A
B
C
a
4
a
2.2.2 Další operace relační algebry Následující operace se dají vyjádřit pomocí základních operací relační algebry Průnik
INTERSECT
je binární operace, která se uplatňuje na relace stejného stupně, jejich atributy jsou definovány nad týmiž doménami. Výsledná relace obsahuje řádky jak jedné tak druhé relace. Duplicitní řádky nejsou připuštěny. Průnik relací R a S se označuje R∩S a je definováno R∩S = {t ⏐ t ∈ R ∧ t ∈ S} platí: R ∩ S = R - (R -S)
Příklad: R:
R ∩ S:
A
B
x
S:
C
D
5
y
8
y
9
z
5
z
1
z
1
A
B
z
1
27
Spojení
JOIN
Nechť R je relace stupně m a S je relace stupně n. R[ i θ j] S je spojení relací R a S podle θ na i - tém atributu relace R a j - tém atributu relace S a je definováno R[ i θ j] S = { rs ⏐ r ∈ R ∧ s ∈ S ∧ r[i] θ s[ j]} Platí: R[ i θ j] S = (R x S)[ i θ (m + j)], pro i ∈ { 1,2, ...., m}, j ∈ {1, 2, ..., n}
Příklad: R:
R[ A = C]S:
Podíl
A
B
x
S:
C
D
5
y
8
y
9
z
5
z
1
z
1
A
B
C
D
y
9
y
8
z
1
z
5
z
1
z
1
QUOTIENT
Mějme relaci R stupně m a relaci S stupně n, kde m > n ∧ S ≠ 0. Podíl R ÷S je relace stupně r - s, a je definován R ÷S = R[i1, ..., ir-s] - ((R[i1, ..., ir-s] x S) - R)[i1, ..., ir-s]
Příklad: R:
A
B
C
D
a
b
c
a
b
b
c
S:
X
Y
d
c
d
e
f
e
f
e
f
28
e
d
c
d
e
d
e
f
Operaci R ÷S rozdělíme na jednotlivé kroky 1. R[A, B]:
A
B
a
b
b
c
e
d
2. V = R[ A, B] x S:
A
B
X
Y
a
b
c
d
a
b
e
f
b
c
c
d
b
c
e
f
e
d
c
d
e
d
e
f
A
B
b
c
A
B
a
b
e
d
3. (V - R)[A, B]:
4. R[A, B] - (V - R)[A, B]:
2.2.3 Přepisovací jazyk relační algebry Sjednocení Union Relace1 and Relace2 Rozdíl Minus Relace1 and Relace2 Součin Cartesian Relace1 and Relace2 Projekce Project Relace over Seznam_Atributů Selekce Restrict Relace where podmínka Průnik Intersect Relace1 and Relace2
29
Spojení Join Relace1 and Relace2 over Atribut Dělení Devide Relace1 by Relace2
2.2.4 Relační kalkul Relační kalkul vychází z predikátové logiky 1. řádu a v relačních databázích se vyskytuje ve dvou formách. Jedná se o n-ticový a doménový relační kalkul.
2.2.4.1 Abeceda n-ticového relačního kalkulu 1. Individuové konstanty (prvky domén, např. '2', 'P3'...) 2. Indexové konstanty (přirozená čísla, případně jména atributů) pomocí těchto konstant se odvoláváme na jednotlivé komponenty n-ticových proměnných 3. n-ticové proměnné, jejich oborem hodnot jsou n-tice prvků domén 4. Predikátové konstanty:
unární: {R/R je jméno relace} binární: =, <, >, ≠, ≥, ≤
5. Logické symboly:
∃, ∀, ¬, ∧, ∨
6. Oddělovače:
[, ], (, )
Atomické formule relačního kalkulu: 1. R(s) R.....unární predikát (jméno relace) s......n-ticová proměnná Tato atomická formule znázorňuje tvrzení, že hodnota n-ticové proměnné s je prvkem relace R s[i] θ u[j] s[i] θ 'a' 'a' θ s[i] s,u.....n-ticové proměnné i,j.......indexové konstanty 'a'.......individuová konstanta θ.......binární predikát n-ticové proměnné mohou být volné nebo vázané N-ticová proměnná s je vázaná ve formuli A, jestliže A tvoří dosah kvantifikátoru obsahující s.
2.2.4.2 Formule relačního kalkulu 1. Každá atomická formule je formule 2. Jsou -li Φ1 , Φ2 formule, pak jsou formulemi i Φ1 ∧ Φ2 , Φ1 ∨ Φ2 , ¬ Φ1
30
3. Je-li Φ formule a s volná proměnná, pak ∃ s (Φ) a ∀ s (Φ) se stává v těchto formulích vázanou
jsou rovněž formule. Proměnná
4. Nic jiného není formule.
2.2.4.3 Přepis z relační algebry do relačního n-ticového kalkulu Sjednocení
{t|t ∈ R t∈ S}
R∪S {t|R(t) ∨ S(t)}
Rozdíl
{t|t∈ R t ∉ S}
R-S {t|R(t) ∧ ¬S(t)}
Součin
RxS
R stupně n, S stupně m
{t(n+m) | ( ∃ u(n)) ( ∃ v(m)) (R(u) ∧S(v) ∧t[1] =u[1] ∧ .... ∧ t [n] =u[n] ∧t[n+1] = v[1] ∧ ...∧ t[n+m]=v[m])} R[i1, i2, ..., im]
Projekce
{t(m) | ( ∃ u) (R(u) ∧ t[1]=u[i1]∧ ...∧ t[m] =u[im] Selekce
R(ϕ)
{t |R(t) ∧ ϕ}
Příklad: Příklady požadavků v relačním kalkulu D1: vyučující, kteří vyučují aspoň jeden předmět {t(1)| ∃ r(V(r)∧ t[1] = r[1])} rel. algebra
V[1]
D2: nevyučují žádný předmět {t(1) | ∃ s ∀r(U(s) ∧ t[1] = s[1] ∧( ¬V(r)∨ t[1]≠r[1]))} rel. algebra
U[1]-V[1]
D3: vyučují předmět P2 rel.algebra
{t(1) | ∃ r(V(r) ∧t[1] = r[1] ∧r[2] = ‘P2’)}
V[2=1]{’P2’}[1]
D4: vyučují alespoň jeden předmět, ale ne P2 {t(1) | ∃ s ∀r(V(s) ∧ t[1] = s[1] ∧( ¬V(r)∨ t[1]≠r[1] ∨ r[2] ≠ ‘P2’))} rel. algebra
V[1]-((V[2=1]{’P2’}[1]
D5: nevyučují předmět P2
31
{t(1) | ∃ s ∀r(U(s) ∧ t[1] = s[1] ∧( ¬V(r)∨ t[1]≠r[1] ∨ r[2] ≠ ‘P2’))} rel. algebra
U[1]-((V[2=1]{’P2’}[1]
D6: vyučují jiný předmět než P2 rel. algebra
{t(1) | ∃ r (V(r) ∧ t[1] = r[1] ∧ r[2] ≠ ‘P2’))}
V[2≠1]{’P2’}[1]
D7: vyučují pouze předmět P2 {t(1) | ∃ s ∀r(V(s) ∧ t[1] = s[1] ∧ s[2] = ‘P2’ ∧( ¬V(r)∨ t[1]≠r[1] ∨ r[2] = ‘P2’))} rel. algebra
((V[2=1]{’P2’}[1])-((V[2≠1]{’P2’})[1])
2.2.4.4 Přepisovací jazyk n-ticového relačního kalkulu Pro přepis dotazu v relačním kalkulu slouží jednoduchý přepisovací jazyk, v němž má dotaz následující syntaxi: seznam_hodnot WHERE formule Seznam hodnot představuje především seznam atributů, spojených n-ticovou proměnnou s danou relací, dále může obsahovat agregační funkce, resp. aritmetické výrazy. Formule se skládá z atomických formulí s unárním predikátem (jména relací s příslušnými n-ticovými proměnnými), atomických formulí s binárním predikátem (porovnávací operátory), logických spojek a kvantifikátorů. Kvantifikátory v relačním kalkulu jsou: •
Existenční - v přepisovacím jazyku používáme klíčové slovo EXISTS
•
Univerzální - v přepisovacím jazyku používáme klíčové slovo FORALL
Příklad: Následující příklady jsou použity z publikace [5]. Mějme následující schéma databáze: KINO (NÁZEV_K, ADRESA) FILM (JMÉNO_F, HEREC, ROK) PROGRAM (NÁZEV_K, JMÉNO_F, DATUM) Veškeré následující příklady budou pracovat s výše uvedeným schématem. Příklad 1: Najděte adresy všech kin. x.ADRESA where KINO (x) Pro formuli KINO (x) hledáme všechna TRUE ohodnocení proměnné x a z nich bereme komponentu x.ADRESA V relační algebře jde o projekci KINO [ADRESA]
32
Příklad 2: Najděte herce, kteří hrají ve filmu Černí baroni. film.HEREC where FILM (film) and film.JMÉNO_F = ´Černí baroni´ V relační algebře jde o selekci FILM (JMÉNO_F = ´Černí baroni´) Příklad 3: Proveďte spojení relací PROGRAM a KINO na rovnost. x.NÁZEV_K, k.ADRESA, x.JMÉNO_F, x.DATUM where PROGRAM (x) and exists k(KINO (k) and k.NÁZEV_K = x.NÁZEV_K)
Příklad: Dotaz s existenčním kvantifikátorem. Ve kterých kinech je možné vidět herce M. Brando. Algoritmus: 1. pro každý řádek p tabulky PROGRAM nalezneme řádky f tabulky FILM, které obsahují stejné jméno filmu. p.JMÉNO_F = f.JMÉNO_F 2. v řádcích f zkontrolujeme, zda f. HEREC = M. Brando 3. v případě nalezení alespoň jednoho takového řádku f splňující podmínky 1 a 2 vložíme p. NÁZEV_K do odpovědi. výraz v NRK: p.NÁZEV_K where PROGRAM (p) and exists f(FILM (f) and p.JMÉNO_F = f.JMÉNO_F and f.HEREC = ´M. Brando´)
Příklad: Dotaz s univerzálním kvantifikátorem. Najdi film, který dávají ve všech kinech, která něco hrají. Algoritmus: 1. zafixujeme řádek p tabulky PROGRAM 2. procházíme tabulku PROGRAM po řádcích x tak, že pro každý právě prohlížený řádek x hledáme další řádek y, pro který platí: x.NÁZEV_K = y.NÁZEV_K a dále platí, že p.JMÉNO_F = y.JMÉNO_F 3. opakujeme kroky 1 a 2 do vyčerpání tabulky PROGRAM
33
výraz v NRK: p.JMÉNO_F where PROGRAM(p) and forall x (PROGRAM(x) and exists y (PROGRAM (y) and y.NÁZEV_K = x.NÁZEV_K and p.JMÉNO_F = y.JMÉNO_F))
2.2.4.5 Obecný tvar existenčně kvantifikovaných formulí EXISTS x (R(x) and F´(x))
(1)
R(x) označuje, že proměnné se hledají v R* F´(x) je podmínkou výběru
2.2.4.6 Obecný tvar univerzálně kvantifikovaných formulí FORALL x (R(x) and F´(x))
(2)
Výrazy (1) a (2) definují omezené kvantifikátory, které se zapisují EXISTS
x Є R(G(x))
FORALL x Є R(G(x))
G(x) je formule, která neobsahuje exists a forall. Proměnná x ve formuli G splňující tuto vlastnost se nazývá volná proměnná.
Příklady: 1. Zobrazte všechna kina, v nichž hrají všechny filmy s M. Brando. p.NÁZEV_K where PROGRAM (p) and forall f(FILM(f) where f.HEREC = ´M. Brando´ and exists q(PROGRAM(q) and q.NÁZEV_K = p.NÁZEV_K and q.JMÉNO_F = f.JMÉNO_F) 2. Najdi průměrné množství dodaných knih do knihoven mn where mn = AVG (DODÁVÁ, MNOŽSTVÍ) 3. Najdi průměrné množství různých množství dodaných knih musíme nejdříve provést projekci relace DODÁVÁ na atributu MNOŽSTVÍ a teprve pak uplatníme agregační funkci mn where mn = AVG (x.MNOŽSTVÍ where DODÁVÁ (x), MNOŽSTVÍ) 4. Najdi průměrné množství dodaných knih pro každou knihovnu x.NÁZEV_K, mn where DODÁVÁ (x) and mn = AVG (y where DODÁVÁ (y) and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) 5. Najdi průměr různých množství dodaných knih pro každou knihovnu
34
x.NÁZEV_K, mn where DODÁVÁ(x) and mn = AVG (y.MNOŽSTVÍ where DODÁVÁ(y) and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) 6. Vyber knihovny, do kterých bylo dodáno více než 50 knih x.NÁZEV_K where DODÁVÁ (x) and sum (y where DODÁVÁ (y) and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) > 50 7. Najdi pro každou knihovnu minimální a maximální počet dodaných knih x.NÁZEV_K, mi, ma where DODÁVÁ (x) and mi = min (y where DODÁVÁ(y) and y.NÁZEV_K = x.NÁZEV_K, MNOŽSTVÍ) and ma = max (z where DODÁVÁ(z) and z.NÁZEV_K = x.NÁZEV_K, MNOŽSTVÍ) 8. Najdi knihovny, kde množství do nich dodávaných knih z Čapkova knihkupectví je menší než 20. x.NÁZEV_K where DODÁVÁ (x) and sum (y where DODÁVÁ (y) and x.NÁZEV_K = y.NÁZEV_K and x.JMÉNO_K = "Čapkovo", MNOŽSTVÍ) <20
2.2.4.7 Doménový relační kalkul Nepoužívá n-ticové proměnné, ale jednoduché proměnné. Relace v DRK: R (A : x, B : y, C : z)
x, y, z...... proměnné
obecně: R (A1 : t1, .......An : tn ) Obor hodnot proměnných v doménovém relačním kalkulu jsou prvky domén. n-ticový kalkul využívá n-ticové proměnné, doménový kalkul využívá doménové proměnné. Doménové proměnné nejsou strukturovány, neexistují tedy indexové proměnné a indexové konstanty. Predikáty příslušnosti k relaci: n-ticový kalkul............unární predikát R(x) doménový kalkul........n-arní, n závisí na stupni relace
2.2.4.8 Atomické formule doménového relačního kalkulu 1. R(x1,.......xn) R je jméno relace stupně n, xi, n ≥ i ≥ 1 35
doménové proměnné nebo individuové konstanty. Tato formule představuje tvrzení, že n-tice hodnot x1, ... xn je prvkem relace R 2. x θ y, kde x, y jsou doménové proměnné nebo individuové konstanty, θ je binární predikát Výraz doménového relačního kalkulu: {x1,x2,.......xn | Φ (x1,x2,.....,xn)}
2.2.4.9 Věta o ekvivalenci Bezpečný výraz: je výraz n-ticového nebo doménového relačního kalkulu, který nedovolí definování nekonečných relací 1. Ke každému výrazu relační algebry existuje ekvivalentní bezpečný výraz doménového relačního kalkulu (ekvivalentní výraz je takový, který definuje tutéž relaci) Důkaz pro 5 základních operací relační algebry a) E = E1 ∪ E2
se převede na F1 ∨ F2
operace sjednocení relací se převede na formuli F = F1 ∨ F2 s využitím logického operátoru (nebo) se převede na F1 ∧¬F2
b) E = E1 - E2
operace rozdílu se převede na konjunkci negace c) E = E1 [Xi1, ......Xik]
projekce
nechť formule F1(X1,......Xn) produkuje relaci E1 Nechť {j1,....jn-k} je seznam nepatřící do {i1, ....ik} pak výraz E relační algebry lze nahradit: F(Xi1, .... Xik) = (∃ Xj1 )(∃ Xj2)........(∃ Xjn-k) F1(X1, ...Xn) d) E = E1 x E2 operace kartézského součinu se převede na operaci logické konjunkce F(X1, ...Xn,Y1, .....Yn)=F1(X1, ....Xn) ∧ F2(Y1, ....Ym) e) E = R[ϕ]
selekce
se převede na F1 ∧ Xi θ Xj resp. F1 ∧ Xi θ a kde F1 je formule tvořící E Xi, Xj jsou atributy relace R a je konstanta θ je porovnávací nebo logický operátor 2. Ke každému bezpečnému výrazu doménového relačního kalkulu existuje ekvivalentní bezpečný výraz n-ticového relačního kalkulu
36
a)F1∨ F2 = {x |F1 (x) ∨ F2 (x)} b) F1∨ ¬ F2 = {x |F1 (x) ∨ ¬ F2 (x)} c){x (k) | ∃ s(F1(s) ∧ x[1]=s[i1] .....x[k]=s[ik] )} d){ x (n+m) | ∃s ∃r (F1(s) ∧ F2(r) ∧ x[1]=s[1] ∧ ....x[n]=s[n] ∧ x[n+1] =r[1] ∧... ∧x[n+m] =r[m])} e){x F1(x) ∧ ϕ´}
3. Ke každému bezpečnému výrazu n-ticového relačního kalkulu existuje ekvivalentní výraz relační algebry
Kontrolní otázky: 1. Co je to n-ticová proměnná? 2. Co je to term a jakých hodnot může nabývat? 3. Co je to formule a jakých hodnot může nabývat? 4. Jak se člení databázové jazyky v relačních SŘBD? 5. Co je to dotaz, co je to odpověď?
Pojmy k zapamatování: JDD JMD JRD Dotazovací jazyky Dotaz - odpověď Relační algebra Relační kalkul Term Atomická formule Formule
2.3 ŘEŠENÉ PŘÍKLADY KALKULU
V
RELAČNÍ ALGEBŘE A RELAČNÍM
Cíl:
37
Cílem této kapitoly je na řešených příkladech ukázat možnosti relační algebry a relačního kalkulu. Dotazy jsou prováděny nad jednoduchou databází popsanou v úvodu. Čtenář po pečlivém prostudování této a předchozí kapitoly by měl být schopen zapsat jakýkoli dotaz v relační algebře resp. v relačním kalkulu. Proto po této kapitole následuje korespondenční úkol.
Klíčová slova: Základní operace relační algebry, odvozené operace, přepisovací jazyk relační algebry, relační kalkul, přepisovací jazyk relačního kalkulu. Příklady, které v této kapitole najdete, jsou použity z publikace [5].
Příklad č. 1 Mějme relace:
KNIHKUPEC(JMÉNO_K, ADRESA, …) KNIHOVNA(NÁZEV_K, ….) DODÁVÁ(JMÉNO_K, NÁZEV_K, …)
Najděte jména a adresy knihkupců, kteří dodávají knihy do všech knihoven. Dotaz zapište v n-ticovém relačním kalkulu a využijte univerzální kvantifikátor. Řešení: x.JMÉNO_K, x.ADRESA where KNIHKUPEC(x) and forall y(KNIHOVNA(y) and exists z(DODÁVÁ(z) and z.JMÉNO_K=x.JMÉNO_K and z.NÁZEV_K=y.NÁZEV_K))
Příklad č. 2 Najděte jména a adresy knihkupců, kteří dodávají knihy do všech knihoven. Dotaz zapište v n-ticovém relačním kalkulu a využijte existenční kvantifikátor. Řešení: x.JMÉNO_K, x.ADRESA where KNIHKUPEC(x) and not exists y(KNIHOVNA(y) and not exists z(DODÁVÁ(z) and z.JMÉNO_K=x.JMÉNO_K and z.NÁZEV_K=y.NÁZEV_K))
Příklad č. 3
38
Proveďte spojení relací KNIHA(ISBN, AUTOR, TITUL) a REZERV(ISBN, Č_ČT, D_REZ) včetně projekce všech neduplicitních atributů v relační algebře a to jak z definice, tak s využitím jednoduchého přepisovacího jazyka. Řešení: KNIHA [ISBN=ISBN] REZERV [ISBN, AUTOR, Č_ČT, D_REZ] project(join KNIHA and REZERV over ISBN) over ISBN, AUTOR, TITUL, Č_ČT, D_REZ
Příklad č. 4 Proveďte spojení relací KNIHA(ISBN, AUTOR, TITUL) a REZERV(ISBN, Č_ČT, D_REZ) včetně projekce všech neduplicitních atributů v relačním kalkulu Řešení: x.ISBN, x.AUTOR, x.TITUL, y.Č_ČT, y.D_REZ where KNIHA(x) and exists y(REZERV(y) and x.ISBN=y.ISBN)
Příklad č. 5 Mějme relaci: STUDENT(ČÍS_SKUPINY, JMÉNO, PŘÍJMENÍ, MAT, BYDLIŠTĚ,...) Formulujte následující dotaz v relační algebře jak z definice, tak použitím přepisovacího jazyka. Najděte jména a příjmení studentů, kteří chodí do stejné skupiny jako student Novák a nemají ještě vykonanou zkoušku z matematiky (v atributu MAT je prázdný řetězec). Řešení: STUDENT(ČÍS_SKUPINY=STUDENT(PŘÍJMENÍ = (MAT= ‚‘)))[JMÉNO, PŘÍJMENÍ]
'Novák‘)[ČÍS_SKUPINY](STUDENT
project(restrict STUDENT where ČÍS_SKUPINY=(project(restrict STUDENT where PŘÍJMENÍ = 'Novák') over ČÍS_SKUPINY) and MAT='') over JMÉNO, PŘÍJMENÍ
Příklad č. 6 Formulujte následující dotaz na relaci z příkladu 5 v relační algebře jak z definice, tak použitím přepisovacího jazyka. Najděte jména a příjmení všech studentů, kteří chodí do stejné skupiny jako student Král a nebydlí v Ostravě. Řešení: STUDENT(ČÍS_SKUPINY=STUDENT(PŘÍJMENÍ (BYDLIŠTĚ <> 'OSTRAVA‘)))[JMÉNO, PŘÍJMENÍ] 39
=
‚Král‘)[ČÍS_SKUPINY](STUDENT
project(restrict STUDENT where SKUPINA=(project(restrict STUDENT where PŘÍJMENÍ = 'Král') over SKUPINA)) and BYDLIŠTĚ not='OSTRAVA') over JMÉNO, PŘÍJMENÍ
40
Příklad č. 7 Mějme relaci R
a
x
a
y
a
z
b
x
c
y
a relaci S
x z
Vypočtěte relaci, která vznikne podílem relací R a S Řešení: a
Příklad č. 8 Mějme relace: KINO(NÁZEV_K, ADRESA) FILM(JMÉNO_F, HEREC, ROK) PROGRAM(NÁZEV_K, JMÉNO_F, DATUM) Zapište v relační algebře z definice i v přepisovacím jazyku dotaz: Najděte název kina a jeho adresu, kde dávají film Kolja. Řešení: (PROGRAM(JMÉNO_F = 'Kolja‘ [NÁZEV_K = NÁZEV_K]) [NÁZEV_K=NÁZEV_K] KINO [NÁZEV_K,ADRESA] project(join(restrict PROGRAM where JMÉNO_F = 'Kolja') and KINO over NÁZEV_K) over NÁZEV_K, ADRESA
Příklad č. 9 Zapište dotaz z příkladu č. 8 v relačním kalkulu. Řešení: x.NÁZEV_K, x.ADRESA where KINO(x) and exists p(PROGRAM(p) and x.NÁZEV_K = p.NÁZEV_K and p.JMÉNO_F = 'Kolja')
41
Příklad č. 10 Interpretujte dotaz: PROGRAM[NÁZEV_K, JMÉNO_F]
FILM(HEREC = 'Menšík')[JMÉNO_F]
Řešení: Ve kterých kinech hrají kromě jiného všechny filmy s Menšíkem?
Příklad č. 11 Přepište předchozí dotaz s použitím základních operací relační algebry (z definice). Řešení: PROGRAM[NÁZEV_K] – ((PROGRAM[NÁZEV_K] x FILM(HEREC = 'Menšík‘) [JMÉNO_F]) – PROGRAM [NÁZEV_K, JMÉNO_F] ) [NÁZEV_K]
Příklad č. 12 Mějme relace: KNIHKUPEC(JMÉNO_K, ADRESA, …) KNIHOVNA(NÁZEV_K, ….) DODÁVÁ(JMÉNO_K, NÁZEV_K, MNOŽSTVÍ,…) Z relace DODAVÁ vyberte názvy knihoven (atr. NÁZEV_K), do kterých bylo dodáno více než 50 knih. Informace o jednotlivých dodávkách je v atributu MNOŽSTVÍ. Dotaz zapište v relačním kalkulu. Řešení: x.NÁZEV_K where DODAVÁ(x) and sum(y where DODAVÁ(y) and x.NÁZEV_K = y.NÁZEV_K, MNOZSTVÍ) > 50
Příklad č. 13 Dotaz PROGRAM[NÁZEV_K, JMÉNO_F]
FILM(HEREC = Menšík)[JMÉNO_F]
přepište do základních operací relační algebry a využijte přepisovací jazyk. Pro Kartézský součin použijte následující syntaxi: Cartesian Relace 1 and relace 2.
42
Řešení: Minus(project PROGRAM over NÁZEV_K and project(minus(cartesian(project(restrict FILM where HEREC='Menšík')over JMÉNO_F)and project PROGRAM over NÁZEV_K) and project PROGRAM over NÁZEV_K, JMÉNO_F )over NÁZEV_K
Příklad č. 14 Dotaz PROGRAM[NÁZEV_K, JMÉNO_F] FILM(HEREC = Menšík)[JMÉNO_F] přepište přepisovacím jazykem. Pro operaci dělení použijte následující syntaxi: Devide Relace 1 by Relace 2 Řešení: PROGRAM[NÁZEV_K, JMÉNO_F] FILM(HEREC = 'Menšík')[JMÉNO_F] Devide (project PROGRAM over NÁZEV_K, JMÉNO_F by project(restrict(FILM where HEREC='Menšík')over JMÉNO_F))
Průvodce studiem: Pokud jste si pozorně prostudovali teoretické kapitoly o relační algebře a relačním kalkulu a byly Vám jasné příklady, uvedené v této kapitole, nebude zajisté pro Vás velkým problémem vypracovat korespondenční úkol, jehož zadání následuje. Pokud si ještě nejste jistí, raději se na řešené příklady podívejte ještě jednou, ať zbytečně neztrácíte čas. Přeji Vám mnoho úspěchů při řešení korespondenčního úkolu.
3 MODUL 3 3.1 JAZYK SQL Cíl: Po prostudování této kapitoly bude čtenář znát jednotlivé části databázového jazyka a základní příkazy jazyka SQL. Bude umět pracovat s tříhodnotovou logikou a přepisovat dotazy zapsané v relační algebře, resp. v relačním kalkulu do SQL. Bude umět používat aritmetiku a agregační funkce v SQL, stejně jako množinové operátory. Bude umět sestavit souhrnný a skupinový dotaz v SQL, manipulovat s kvantifikátory a kolekcemi. Klíčová slova: DDL, DML, DQL, DCL, agregační funkce, kolekce, existenční kvantifikátor, souhrnný dotaz, skupinový dotaz.
43
3.1.1 Části jazyka SQL Jazyk SQL (jako většina databázových jazyků) se skládá z následujících částí: 1. Jazyk pro definování dat (Data Definition Language) – DDL. 2. Jazyk pro manipulaci s daty (Data Manipulation Language) – DML. 3. Dotazovací jazyk (Data Query Language) – DQL. 4. Jazyk pro správu dat (Data Control Language) – DCL.
3.1.2 Základní příkazy DDL Poznámky k syntaxi: velkým písmem - klíčová slova odtrženě - defaultní hodnota () - údaj je nutno zapsat do () [ ] - volitelný údaj ... - více výrazů stejného typu, jako před čárkou { } - výběr z uvedených možností CREATE TABLE Syntaxe: CREATE TABLE jméno-tabulky (atribut datový-typ [NOT NULL] [,...] [PRIMARY KEY (atribut, ..)] [FOREIGN KEY jméno (atribut, ...) REFERENCES nadřazená-tabulka [ON DELETE {RESTRICT, CASCADE, SET NULL}]]) Vytvoří schéma tabulky včetně primárního a cizích klíčů.
Příklad 1: CREATE TABLE Zaměstnanec (Číslo Integer NOT NULL, Jméno Varchar(20), Příjmení Varchar(20), PRIMARY KEY(Číslo)) Vytvoří tabulku Zaměstnanec s atributy Číslo, Jméno a Příjmení a příslušnými datovými typy. Dále definuje primární klíč atribut Číslo.
Příklad 2: 44
CREATE TABLE Plat (Číslo Integer NOT NULL, Datum Date NOT NULL, Tarif, PRIMARY KEY (Číslo, Datum), FOREIGN KEY Má (Číslo) REFERENCES Zaměstnanec ON DELETE CASCADE) Vytvoří tabulku Plat a příslušnými atributy, složený primární klíč Číslo+Datum a cizí klíč Má přidáním atributu (primárního klíče) Číslo z tabulky Zaměstnanec. Protože cizí klíč je součástí primárního klíče podřízené tabulky, jedná se o identifikační typ závislosti. Referenční integrita bude hlídána při mazání záznamů z nadřízené tabulky. Dojte-li k výmazu záznamu z tabulky Zaměstnanec, vymažou se automaticky všechny záznamy z tabulky Plat, které mají hodnotu cizího klíče rovnu hodnotě primárního klíče mazaného záznamu. CREATE INDEX Syntaxe: CREATE [UNIQUE] INDEX jméno-indexu ON jméno-tabulky (atribut [{ ASC, DESC}][, ...] ) Vytvoří index na primární, alternativní nebo inverzní klíč. UNIQUE - vytvoří index na alternativní klíč implicitně - inverzní klíč
Příklad 3: CREATE INDEX IE1 ON Zaměstnanec (Jméno, Příjmení) Vytvoří index IE na složený inverzní klíč (Jméno+Příjmení) tabulky Zaměstnanec. ALTER TABLE Syntaxe: ALTER TABLE jméno-tabulky DROP COLUMN atribut [ ,...] ADD (atribut datový-typ[NOT NULL]) RENAME COLUMN atribut TO nový_atribut MODIFY (atribut {nový-datový-typ, NULL, NOT NULL}) Změní strukturu tabulky smazáním, přidáním nebo přejmenováním atributu (ů), resp. změní jejich datový typ (doménu). Příkaz lze rovněž použít pro přejmenování tabulky.
Příklad 4: 45
ALTER TABLE Zaměstnanec ADD (Datum-narození DATE) CREATE VIEW Syntaxe: CREATE VIEW jméno-pohledu [(atribut [,...])] AS SELECT Vytvoří pohled na základě výběru dat z existující tabulky či tabulek. Specifikace výběru je zapsána za klauzulí SELECT. K takto vytvořeným pohledům je možno vytvořit různá přístupová práva.
Příklad 5: CREATE VIEW Pražák AS SELECT Č-ČT, Jméno, Adresa FROM Čtenář WHERE Adresa LIKE "%Praha%" Vytvoří virtuální tabulku (pohled), do kterého vloží z tabulky Čtenář pouze atributy Jméno a Adresa a pouze ty řádky, které mají v hodnotě atributu Adresa řetězec "Praha". DROP Syntaxe: DROP {TABLE jméno-tabulky, VIEW jméno-pohledu, INDEX jméno-indexu} Zruší ze schématu databáze tabulku, pohled nebo index.
3.1.3 Základní příkazy DML DELETE Syntaxe: DELETE FROM { jméno-tabulky, jméno-pohledu} [ WHERE podmínka] Příkaz vymaže ze specifikované tabulky nebo pohledu řádky, které splňují specifikovanou podmínku. Není-li podmínka specifikována, vymaže všechny řádky tabulky nebo pohledu. Tabulka ve schématu zůstane, ale bude prázdná.
46
Příklad 6: DELETE FROM Zaměstnanec WHERE Číslo=1000 Vymaže z tabulky zaměstnance s číslem 1000. INSERT Syntaxe: INSERT INTO { jméno-tabulky, jméno-pohledu} [ atribut [, ...]] {VALUES (hodnota [, ...], SELECT} Vloží do specifikované tabulky hodnoty specifikovaným atributům. Není-li výčet atributů uveden, vkládají se hodnoty do jednotlivých atributů tak, jak jsou uvedeny ve struktuře tabulky. Hodnoty je možno buď zapsat přímo do příkazu nebo vybrat specifikovaným příkazem SELECT.
Příklad 7: INSERT INTO Zaměstnanec (Číslo, Jméno, Příjmení) VALUES (1234, "Jan", "Novák") Vloží řádek do tabulky Zaměstnanec. Výčet atributů je nutno uvést, protože se nezadává hodnota do atributu Datum-narození
Příklad 8: INSERT INTO Zaměstnanec SELECT Číslo, Jméno, Funkce="Zaměstnanec"
Příjmení,
Datum-narození
FROM
Osoba
WHERE
Vloží do tabulky Čtenář řádek (řádky), jehož (jejichž) hodnoty nalezne v tabulce Osoba na řádcích, kde hodnota atributu Funkce je Zaměstnanec.
UPDATE Syntaxe: UPDATE { jméno-tabulky, jméno-pohledu} SET atribut = výraz [WHERE podmínka]
47
Změní hodnotu atributu na hodnotu zadanou výrazem v případě, je-li splněna podmínka. Není-li podmínka uvedena, ke změně hodnoty dojde vždy.
Příklad 9: UPDATE Plat SET Tarif = 30000 WHERE Číslo = 1234 Změní tarifní plat v tabulce Plat na 30000 u zaměstnance s číslem 1234.
3.1.4 Základní příkazy DQL Obecná konstrukce příkazu SELECT SELECT A1, A2,.....Aj FROM
R1, R2,......Rk
WHERE
podmínka výběru specifikována formulí
A1, A2,.........Aj
atributy, které budou zahrnuty do odpovědi ( PROJEKCE)
R1, R2,...........Rk
relace, ze kterých se budou data vybírat
Tuto konstrukci lze přepsat do relační algebry: (R1 x R2 x ....... x Rk) ( ) [A1, A2, ..........Aj]
Příklady jednoduchých dotazů: 1. Vypište tabulku jmen čtenářů s adresou: SELECT JMÉNO, ADRESA FROM ČTENÁŘ 2. Odstraňte duplicity: SELECT DISTINCT JMÉNO, ADRESA FROM ČTENÁŘ 3. Výslednou relaci na výstupu uspořádejte podle jména: SELECT DISTINCT JMÉNO, ADRERA FROM ČTENÁŘ ORDER BY JMÉNO ASC 4. Vypište z relace EXEMPLÁŘ n-tice týkající se nákupu po 1. 1. 2002. Vyberte všechny atributy: SELECT * FROM ČTENÁŘ WHERE D_NÁKUP > "01/01/02"
48
Příklad na operátor BETWEEN: D_NÁKUP > "01/01/01" AND D_NÁKUP < "01/01/02" lze zapsat: D_NÁKUP BETWEEN "01/01/01" AND "01/01/02"
Příklady na dotaz na více tabulek: 1. Najděte autory, jejichž některé tituly jsou rezervovány do 31. 12. 2002 SELECT DISTINCT AUTOR FROM KNIHA, REZERV WHERE KNIHA. ISBN = REZERV. ISBN AND D_REZ < "12/31/02" 2. Vytvořte kartézský součin relací KNIHA a EXEMPLÁŘ SELECT DISTINCT * FROM KNIHA, EXEMPLÁŘ 3. Najděte dvojice čtenářů, kteří mají stejnou adresu SELECT PRVNÍ.Č_ČT, DRUHÝ.Č_ČT FROM ČTENÁŘ PRVNÍ, ČTENÁŘ DRUHÝ WHERE PRVNÍ. ADRESA = DRUHÝ. ADRESA AND PRVNÍ. Č_ČT < DRUHÝ. Č_ČT Zavedení tříhodnotové logiky A
B
A and B
A or B
not A
TRUE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
FALSE
TRUE
FALSE
TRUE
NEDEF
NEDEF
TRUE
FALSE
FALSE
TRUE
FALSE
TRUE
TRUE
FALSE
FALSE
FALSE
FALSE
TRUE
FALSE
NEDEF
FALSE
NEDEF
TRUE
NEDEF
TRUE
NEDEF
TRUE
NEDEF
NEDEF
FALSE
FALSE
NEDEF
NEDEF
NEDEF
NEDEF
NEDEF
NEDEF
NEDEF
Sémantika porovnávání
49
x θ y = NEDEF, jestliže aspoň jedna hodnota x nebo y je NULL. Z toho plyne, že NULL = NULL se vyhodnocuje jako NEDEF. θ ........... operátor porovnávání (≥, ≤, <, >, =, <>)
Příklady na aritmetiku a agregační funkce: 1. Najdi všechny exempláře vydané v SRN a jejich cenu v EUR SELECT ISBN, INV_Č, CENA /35 FROM EXEMPLÁŘ WHERE ZEMĚ_VYDÁNÍ = "SRN" 2. Jak velký je celkový počet čtenářů SELECT COUNT (*) FROM ČTENÁŘ 3. Najdi celkový počet čtenářů, kteří mají rezervovanou nějakou knihu SELECT COUNT (DISTINCT Č_ČT) FROM REZERV Pozn.: bez duplicit 4. Najdi počet knih v knihovně, které byly vydány ve Velké Británii SELECT COUNT (*) FROM EXEMPLÁŘ WHERE ZEMĚ_VYDÁNÍ = "GB" Pozn.:včetně duplicit SUM a AVG, není zadáno DISTINCT počítají s duplicitami Obecný zápis projekce SELECT [DISTINCT / ALL] {hodnotový výraz 1 [, hodnotový výraz 2]........} hodnotový výraz je kombinace aritmetických výrazů a agregačních funkcí agregační funkce: COUNT, SUM, MAX, MIN, AVG Konstrukt GROUP BY Umožní vytvářet podmnožiny podle výběrového kritéria. Relace se konceptuálně rozdělí na dvě skupiny.
Příklady na skupiny: 1. Najdi pro každého čtenáře počet vypůjčených knih SELECT Č_ČT, COUNT (DISTINCT INV_Č) FROM VÝPUJČKA GROUP BY Č_ČT
50
Skupina se vytvoří na základě hodnoty atributu Č_ČT. Na každou skupinu se aplikuje agregační funkce COUNT. Klauzule HAVING Umožní vybrat pouze některé ze skupin vytvořených konstruktem GROUP BY. Za HAVING je možno použít i agregační fce. 2. Najdi ty čtenáře, kteří mají půjčeno více než 5 knih SELECT Č_ČT, COUNT (DISTINCT INV_Č) FROM VÝPUJČKA GROUP BY Č_ČT HAVING 5 < COUNT (DISTINCT INV_Č) Do výsledné tabulky ( relace) je možno vkládat i konstanty. 3. SELECT Č_ČT, "SI PUJČIL", COUNT (INV_Č), "KNIH" FROM VÝPUJČKA GROUP BY Č_ČT HAVING 5 < COUNT (INV_Č) Přepis dotazů z relačního kalkulu do SQL
Příklady: 1. Najdi průměrné množství dodaných knih do knihoven V relačním kalkulu: mn where mn = AVG (DODÁVÁ, MNOŽSTVÍ) V SQL: SELECT "MN = ", AVG (MNOŽSTVÍ) FROM DODÁVÁ Najdi průměrné množství různých množství dodaných knih V relačním kalkulu: musíme nejdříve provést projekci relace DODÁVÁ na atributu MNOŽSTVÍ a teprve pak uplatníme agregační funkci mn where mn = AVG (x.MNOŽSTVÍ where DODÁVÁ (x), MNOŽSTVÍ) SQL vyřeší "různých" pouhou klauzulí DISTINCT tedy: SELECT ´MN=´, AVG (DISTINCT MNOŽSTVÍ) FROM DODÁVÁ 2. Najdi průměrné množství dodaných knih pro každou knihovnu V relačním kalkulu: x.NÁZEV_K, mn where DODÁVÁ (x) and mn = AVG (y where DODÁVÁ (y)
51
and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) V SQL: SELECT NÁZEV_K, "MN =", AVG (MNOŽSTVÍ) FROM DODÁVÁ GROUP BY NÁZEV_K Najdi průměr různých množství dodaných knih pro každou knihovnu V relačním kalkulu: x.NÁZEV_K, mn where DODÁVÁ(x) and mn = AVG (y.MNOŽSTVÍ where DODÁVÁ(y) and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) V SQL: SELECT NÁZEV_K, "MN =", AVG (DISTINCT MNOŽSTVÍ) FROM DODÁVÁ GROUP BY NÁZEV_K 3. Vyber knihovny, do kterých bylo dodáno více než 50 knih V relačním kalkulu: x.NÁZEV_K where DODÁVÁ (x) and sum (y where DODÁVÁ (y) and x.NÁZEV_K = y.NÁZEV_K, MNOŽSTVÍ) > 50 V SQL: SELECT DISTINCT NÁZEV_K FROM DODÁVÁ WHERE 50 < (SELECT SUM (MNOŽSTVÍ) FROM DODÁVÁ Y WHERE DODÁVÁ.NÁZEV_K = Y.NÁZEV_K) 4. Najdi pro každou knihovnu minimální a maximální počet dodaných knih V relačním kalkulu: x.NÁZEV_K, mi, ma where DODÁVÁ (x) and mi = min (y where DODÁVÁ(y) and y.NÁZEV_K = x.NÁZEV_K, MNOŽSTVÍ) and ma = max (z where DODÁVÁ(z) and z.NÁZEV_K = x.NÁZEV_K, MNOŽSTVÍ) V SQL: SELECT NÁZEV_K, ´MI = ´, MIN (MNOŽSTVÍ), ´MA =´, MAX(MNOŽSTVÍ) FROM DODÁVÁ GROUP BY NÁZEV_K 5. Najdi knihovny, kde množství do nich dodávaných knih z Čapkova knihkupectví je menší než 20. V relačním kalkulu:
52
x.NÁZEV_K where DODÁVÁ (x) and sum (y where DODÁVÁ (y) and x.NÁZEV_K = y.NÁZEV_K and x.JMÉNO_K = "Čapkovo", MNOŽSTVÍ) <20 V SQL: SELECT DISTINCT NÁZEV_K FROM DODÁVÁ WHERE 20 > (SELECT SUM (MNOŽSTVÍ) FROM DODÁVÁ X WHERE DODÁVÁ.NÁZEV_K = X.NÁZEV_K AND X.JMÉNO_K = ´Čapkovo´) Manipulace s množinami v SQL Manipulovat s množinami umožňují dotazy, které vedou k vhnízdění SELECT - FROM WHERE. Konstrukt IN p IN A kde p je prvkem A
Příklad na vhnízdění: Najdi čísla čtenářů, kteří mají zapůjčeny nějaké knihy a rezervovány ještě tituly do 31. 12. 2002. SELECT Č_ČT FROM REZERV WHERE D_REZ < ´12/31/02´AND Č_ČT IN (SELECT Č_ČT FROM VYPUJČKA)
Příklad na výčet hodnot: Najdi všechny exempláře knih, které byly vydány v GB, F, D. SELECT INV_Č, ZEMĚ_VYDÁNÍ FROM EXEMPLÁŘ WHERE ZEMĚ_VYDÁNÍ IN (´GB´, ´F´, ´D´) Konstrukt > ALL Konstrukt vyjadřuje, že hodnota zadaného atributu je větší než všechny prvky ze specifikované množiny. 53
! = ALL
je ekvivalentní
NOT IN
Porovnávací operátory lze použít tehdy, máme-li zaručeno, že výsledek hnízděného dotazu bude právě jedna hodnota (nebo je použit některý z konstruktů).
Příklad: Najdi ISBN knih dražších než jakákoli kniha z GB. SELECT ISBN FROM EXEMPLÁŘ WHERE CENA > ALL (SELECT EXEMPLÁŘ, CENA FROM EXEMPLÁŘ WHERE EXEMPLÁŘ.ZEMĚ_VYDÁNÍ = ´GB´)
Příklad: Vypiš všechny řádové pracovníky týmů, tj. ty, kteří nejsou vedoucími. Uspořádej výstup podle abecedy. SELECT a.příjmení FROM TYMY A WHERE NOT EMPTY (a. vedoucí) AND a. rodné_č not in (SELECT b. vedoucí FROM TYMY b where a.rodné_č = b.vedoucí) ORDER BY a. příjmení Funkce EMPTY ( ) se použije k odfiltrování řádků těch pracovníků, kteří nejsou zařazeni do týmu. Konstrukty porovnání > SOME < SOME = SOME (totéž jako IN) >ALL
54
Příklad: Najdi jména a adresy knihkupců, kteří dodávají knihy do všech knihoven. V rel. kalkulu: x.JMÉNO_K, x.MĚSTO where KNIHKUPEC(x) and forall y(KNIHOVNA(y) and exists z (DODÁVÁ(z) and z.JMÉNO_K = x.JMÉNO_K and z.NÁZEV_K = y.NÁZEV_K)) EXISTS a FORALL jsou svázány transformací: FORALL x (p(x)) = not EXISTS x (not p(x)) Proto jakýkoliv výraz, který obsahuje FORALL můžeme nahradit výrazem s EXISTS a opačně. FORALL x EXIST y (y > x) je totéž jako NOT EXISTS x (NOT EXISTS y (y > x)) Každá kniha má název, tzn. že neexistuje kniha bez názvu Převedeme výraz v relačním kalkulu na výraz bez kvantifikátoru FORALL: x.JMÉNO_K, x.MĚSTO where KNIHKUPEC (x) and not exists y(KNIHOVNA(y) and not exists z(DODÁVÁ(z) and z.JMÉNO_K = x.JMÉNO_K and z.NÁZEV_K = y.NÁZEV_K)) Tento výraz budeme transformovat do SQL: SELECT DISTINCT x.JMÉNO_K, x.MĚSTO FROM KNIHKUPEC x WHERE NOT EXISTS (SELECT DISTINCT y.* FROM KNIHOVNA y WHERE NOT EXISTS (SELECT DISTINCT z.* FROM DODÁVÁ z WHERE z.JMÉNO_K = x.JMÉNO_K AND z.NÁZEV_K = y.NÁZEV_K)) Pozn.: JMÉNO_K ... jméno knihkupce NÁZEV_K ... název knihovny Upozornění: SQL nemá univerzální kvantifikátor obsahuje však EXISTS, ten není stejný jako EXISTS v rel. kalkulu. Je to test na neprázdnost množiny specifikované za EXISTS.
Příklad: Najdi jména čtenářů, kteří mají rezervovanou nějakou knihu, resp. najdi jména čtenářů takových, že existuje kniha, kterou mají rezervovanou. SELECT JMÉNO
55
FROM ČTENÁŘ WHERE EXISTS (SELECT * FROM REZERV WHERE Č_ČT = ČTENÁŘ.Č_ČT) Sémantika výrazu EXISTS Výraz se vyhodnotí jako TRUE, je-li množina daná výrazem (SELECT*......) neprázdná. Výraz s EXISTS se dá negovat:
Příklad: Najdi čísla čtenářů taková, že neexistuje jimi rezervovaná kniha, která by byla od B. Němcové. (Původní dotaz: Najdi čísla čtenářů takových, že nemají rezervovanou žádnou knihu B. Němcové). SELECT Č_ČT FROM REZERV x WHERE NOT EXISTS (SELECT * FROM REZERV WHERE x.Č_ČT = Č_ČT AND ISBN IN (SELECT ISBN FROM KNIHA WHERE AUTOR = ´B. Němcová´)) Dotazem získáme ty čtenáře, pro které platí, že množina jejich rezervací, které se týkají knih B. Němcové je prázdná. Vztah EXISTS v relačním kalkulu a SQL exists y R (.......) EXISTS (SELECT DISTINCT Y.* FROM R Y WHERE......) Sémantika v relačním kalkulu Výraz nabude hodnoty TRUE, jestliže existuje takový řádek y z relace R, že je splněna formule (.....). Sémantika v SQL Výraz nabude hodnoty TRUE, je-li výsledek vyhodnocení příkazu SELECT za EXISTS neprázdnou množinou z relace R. Konstrukce jsou tedy ekvivalentní. Upozornění: Konstrukce jsou ekvivalentní pouze v dvouhodnotové logice. EXISTS v SQL dává FALSE i tehdy, kdy množina za SELECT je prázdná proto, že podmínky byly vyhodnoceny jako NEDEF. Používání prázdných hodnot
56
Rozšíření sémantiky: •
NULL v aritmetickém výrazu dává výsledek NULL.
•
NULL v porovnávacím výrazu dává výsledek NEDEF.
V porovnávacím výrazu není možno použít konstantu NULL. Operátor IS NULL Operátor IS NULL se používá v porovnávacích výrazech.
Příklad: Vypiš inventární čísla exemplářů, které nebyly nakoupeny (např. získány darem) SELECT INV_Č FROM EXEMPLÁŘ WHERE D_NÁKUP IS NULL Funkce MAX, MIN, SUM a AVG aplikované na prázdnou množinu dávají vždy hodnotu NULL. Funkce COUNT aplikovaná na prázdnou množinu dává Výskyt prázdných množin vede k tomu, že výrazy s IN a EXISTS se chovají jinak.
Příklad: Najdi ISBN knih, jejichž cena není rovna ceně žádné z knih z Velké Británie . Použitím IN SELECT ISBN FROM EXIMPLÁŘ WHERE CENA NOT IN (SELECT EXEMPLÁŘ. CENA FROM EXEMPLÁŘ WHERE EXEMPLÁŘ.ZEMĚ_VYDÁNÍ = ´GB´) Použitím EXISTS SELECT ISBN FROM EXEMPLÁŘ x WHERE NOT EXISTS (SELECT EXEMPLÁŘ.* FROM EXEMPLÁŘ WHERE EXEMPLÁŘ.ZEMĚ_VYDÁNÍ = ´GB´ AND x. CENA = EXEMPLÁŘ.CENA)
57
Rozebereme případ, kdy existuje právě jedna britská kniha a to s neznámou cenou. Vyhodnocení SELECTu (1) Množina za NOT IN obsahuje pouze NULL, podmínka za vnějším WHERE bude vyhodnocena jako nedefinovaná. Z toho vyplývá, že pro každý exemplář bude odpověď prázdná množina. Vyhodnocení SELECTu (2) Vhnízděný SELECT dává prázdnou množinu a odpovědi budou vyhovovat všechny exempláře, tj. všechna ISBN. Práce s kolekcemi v SQL Pro práci slouží nerelační operátor SELECT ALL.
Příklad: Mějme relaci S s atributem A a relaci T s atributy A, C. S
A
T
A
C
1
1
3
1
1
4
0
6
4
1
SELECT ALL S . A, T . C FROM S, T WHERE S . A = T . A A
C
1
3
1
3
1
4
1
4
Práce s řetězci znaků Používají se konstrukt LIKE - umožňuje pracovat s podřetězci hodnot atributů. Typ atributů: CHAR, VARCHAR Jméno atributů: LIKE řetězcová - konstanta
58
Příklad: Příklady použití LIKE: AUTOR LIKE ´JI%´: libovolná délka, začína na ´ji......´ AUTOR LIKE ´K-´: dvoupísmenové jméno, začíná na K..... AUTOR LIKE ´%d--´: minimálně třípísmenové jméno od konce d ADRESA LICE ´%PRAHA%´: adresa, kdekoli obsahující slovo ´Praha´ Sémantika příkazu SELECT Vytvoř virtuální tabulku s čísly čtenářů, jmény a počtem výpůjček u čtenářů, kteří mají vypůjčeno více než 5 exemplářů. Tabulku setříďte sestupně podle počtu výpůjček a v rámci toho vzestupně podle jmen čtenářů. SELECT Č_ČT, JMÉNO, COUNT (INV_Č) FROM VÝPUJČKA, ČTENÁŘ WHERE VÝPUJČKA.Č_ČT = ČTENÁŘ.Č_ČT GROUP BY VÝPUJČKA.Č_ČT HAVING COUNT (INV_Č) > ´5´ ORDER BY 3 DESC, JMÉNO ASC Procedurální sémantika: 1. Vytvoří se VÝPUJČKA x ČTENÁŘ 2. Vyhodnocením podmínky za WHERE se relace z kroku 1 zúží na spojení na rovnost na atributech Č_ČT. 3. Relace z kroku 2 se rozdělí na podskupiny podle hodnot atributu Č_ČT. 4. Ze skupin kroku 3. se vyberou jen ty skupiny, kde počet inventárních čísel je větší než 5 5. Každá skupina z kroku 4. přispívá do jednoho řádku výsledné relace. 6. Relace z kroku 5 je uspořádána (v souladu s ORDER BY). Protože třetí sloupec výsledné relace nemá jméno, je atribut zadán číslem. Operátor ANY SELECT * FROM Prodavač WHERE Město = ANY (SELECT Město FROM Zákazník) Vyberou se všechna města z relace Zákazník a výraz se vyhodnotí TRUE, jestliže některé z nich je rovno městu z relace Prodavač. Místo ANY můžeme použít IN
59
SELECT * FROM Prodavač WHERE Město IN (SELECT Město FROM Zákazník) Operátor ALL SELECT * FROM Zákazník WHERE daňová_sazba > ALL (SELECT daňová_sazba FROM Zákazník WHERE Město = ´Ostrava´) Vyber všechny záznamy z relace Zákazník, pro které platí, že daňová sazba je větší než daňová sazba u všech zákazníků z Ostravy. Tentýž dotaz s použitím EXISTS SELECT * FROM Zákazník a WHERE NOT EXISTS (SELECT * FROM Zákazník b WHERE a.daňová_sazba < = b.daňová_sazba AND a.Město = ´Ostrava´)
Kontrolní otázky: 1. Jaké znáte příkazy jazyka SQL pro definování struktury databáze a její modifikaci? 2. K čemu slouží příkaz Select? 3. Proč je nutné zavádět do dotazovacích jazyků tříhodnotovou logiku? 4. Jak lze porovnávat obsah atributu s databázovou hodnotou NULL? 5. Co to jsou agregační funkce a jaké agregační funkce znáte? 6. Napište syntaxi příkazu Select. 7. Jak lze využít vnízděných dotazů a jak je lze v SQL zapsat?
Pojmy k zapamatování:
60
DDL DML DQL DCL Agregační funkce Kolekce Existenční kvantifikátor Souhrnný dotaz Skupinový dotaz Vhnízdění
Průvodce studiem: Kapitola, kterou jste právě dočetli obsahovala mnoho informací a rovněž si kladla za cíl Vás naučit mnoha praktickým dovednostem. Pokud jste vše pochopili, je to naprosto skvělé. Pokud ne, projděte si předcházející kapitoly ještě jednou a máte ještě možnost prostudovat následující kapitolu, která obsahuje množství dalších řešených příkladů. Znáte-li již teď všechny možnosti jazyka SQL, jak byly popsány v této kapitole, můžete rovnou přistoupit k řešení korespondenčního úkolu č.2. Gratuluji Vám a hlavně oceňuji Vaši píli.
3.2 ŘEŠENÍ PŘÍKLADY NA DOTAZOVÁNÍ V SCHÉMATU A MANIPULACI S DATY
SQL, DEFINOVÁNÍ
Cíl: Cílem této kapitoly je naučit čtenáře přepisovat dotazy formulované v přirozeném jazyce do jazyka SQL. Po prostudování této kapitoly by již měl být čtenář schopen samostatně vytvářet dotazy v SQL a to i složitější dotazy. Dále po prostudování této kapitoly by měl čtenář umět vytvořit schéma databáze, modifikovat její strukturu a manipulovat s daty pomocí příkazů jazyka SQL. Klíčová slova: Schéma databáze, Select, Create, Alter, Insert, Delete, Update
Průvodce studiem: Následující řešené příklady jsou dotazy nad databází Lázně, jejíž schéma je následující:
61
Příklady: 1. Vypište všechna jména hostů, kteří přijeli do lázní a setřiďte je podle výšky vzestupně. select jmeno from host order by hmotab_vyska 2. Vypište hosty, kteří mají výšku 165-175 cm. select jmeno from host where hmotab_vyska between 165 and 175 3. Vypište názvy pokojů setříděně sestupně. select nazev from pokoj order by nazev desc 4. Z tabulky Vazeni zobrazte ty hosty, jejichž hmotnost při kterémkoli vážení byla nižší než 80 kg. select host_rod_cislo from vazeni where hmotnost <80 5. Zobrazte ty hosty, kteří byli zváženi v den příjezdu do lázní. select host_rod_cislo from vazeni where vazeni_datum = khostu_prijezd 62
6. Vypište ty hosty, kteří byli zváženi nejpozději do týdne po příjezdu do lázní. select host_rod_cislo, vazeni_datum, khostu_prijezd +7 > Vazeni_datum
khostu_prijezd
from
vazeni
where
7. Zobrazte popis pokoje s názvem alabastr. select popis from pokoj where nazev = 'alabastr' 8. Zobrazte názvy a popisy pokojů s názvem alabastr nebo moře. select popis from pokoj where nazev = 'alabastr' or nazev = 'moře' 9. Zobrazte hosty, kteří ještě neodjeli z lázní. select host_rod_cislo from kniha_hostu where odjezd is null 10. Zobrazte rodná čísla hostů a názvy pokojů, na kterých jsou umístěni. select host_rod_cislo, pokoj_nazev from kniha_hostu 11. Zobrazte rodná čísla a jména hostů a všechny jejich zvážené hmotnosti. select x.host_rod_cislo, jmeno, x.host_rod_cislo=y.host_rod_cislo
hmotnost
from
host
x,
vazeni
y
where
12. Kolik si připlatil Jiří Hroch za dodatečnou péči? select priplatek, jmeno from host x, dodatecna_pece y, pece_cenik z where x.host_rod_cislo=y.host_rod_cislo and y.pece_cenik_id=z.pece_cenik_id and jmeno = 'Jiří Hroch' 13. Pro každého hosta zobrazte poměr jeho výšky a váhy. select hmotab_vyska/hmotnost x.host_rod_cislo=y.host_rod_cislo
from
vazeni
x,
host
y
where
se zaokrouhlením na 2 des. místa: select round(hmotab_vyska/hmotnost, x.host_rod_cislo=y.host_rod_cislo
2)
from
vazeni
x,
host
y
where
14. Zobrazte přepočtené příplatky při 15% zdražení. select priplatek, priplatek*1.15 from pece_cenik 15. Kolik je celkem v lázních hostů? select count(*) from kniha_hostu where odjezd is null 16. Jaká je průměrná hmotnost všech zvážených hmotností? select avg(hmotnost) from vazeni 17. Kolik měří nejvyšší host? select max(hmotab_vyska) from host 18. Kolik by zaplatil host, pokud by si zaplatil všechny nabízené dodatečné péče právě jednou? select sum(priplatek) from pece_cenik 19. Pro každého hosta zobrazte průměrnou hmotnost (zaokrouhleně na 2 des. místa) všech zvážených hmotností.
63
select host_rod_cislo, round(avg(hmotnost),2) from vazeni group by host_rod_cislo Pokud chceme zobrazit jméno: select jmeno, round(avg(hmotnost),2) from vazeni x, host y where x.host_rod_cislo = y.host_rod_cislo group by jmeno Ale pozor! můžeme mít více pacientů se stejným jménem. 20. Kolik bylo který den provedeno vážení? select vazeni_datum, count(hmotnost) from vazeni group by vazeni_datum 21. Zobrazte všechny hosty, kteří si připlatili Speciální dietu. select jmeno from host x, x.host_rod_cislo=y.host_rod_cislo nazev_cenik='speciální dieta'
dodatecna_pece y, pece_cenik z where and y.pece_cenik_id=z.pece_cenik_id and
22. Zjistěte, který pokoj zůstal neobsazen. select x.nazev from pokoj x where not exists ( select y.pokoj_nazev from kniha_hostu y where y.pokoj_nazev=x.nazev) nebo select x.nazev from pokoj x where x.nazev not in ( select y.pokoj_nazev from kniha_hostu y where y.pokoj_nazev=x.nazev) 23. Kteří z hostů nemají žádnou dodatečnou péči. select x.host_rod_cislo from host x where not exists (select y.host_rod_cislo from dodatecna_pece y where x.host_rod_cislo=y.host_rod_cislo) 24. Který host zatím nebyl zvážen? select x.host_rod_cislo from host x where not exists (select y.host_rod_cislo from vazeni y where x.host_rod_cislo=y.host_rod_cislo) 25. Který host má větší než průměrnou hmotnost? select x.host_rod_cislo, x.hmotnost from vazeni x where avg(y.hmotnost) from vazeni y)
x.hmotnost > (select
26. Zobrazte názvy dodatečných péčí se stejnou cenou. select x.pece_cenik_id, x.nazev_cenik, x.priplatek from pece_cenik x where x.priplatek in (select y.priplatek from pece_cenik y where x.pece_cenik_id <> y.pece_cenik_id) 27. Kdo z hostů byl zvážen více než 3 krát? select host_rod_cislo, count(hmotnost) from vazeni group by host_rod_cislo having count(hmotnost) >3 28. Kdo z hostů má stejnou výšku jako host Jiří Hroch? select x.host_rod_cislo, jmeno from host x where x.hmotab_vyska=(select y.hmotab_vyska from host y where y.jmeno='Jiří Hroch'and x.jmeno <> 'Jiří Hroch') 29. Zobrazte ty hosty, kteří přijeli do lázní minimálně podruhé. select distinct x.host_rod_cislo from kniha_hostu x where exists
64
(select y.host_rod_cislo from kniha_hostu y where x.host_rod_cislo=y.host_rod_cislo and x.khostu_prijezd <> y.khostu_prijezd) se jmény select distinct z.jmeno,x.host_rod_cislo from x.host_rod_cislo = z.host_rod_cislo and exists
kniha_hostu
x,
host
z
where
(select y.host_rod_cislo from kniha_hostu y where x.host_rod_cislo=y.host_rod_cislo and x.khostu_prijezd <> y.khostu_prijezd) 30. Zobrazte názvy pokojů, které mají stejnou kategorii a stejný popis jako pokoj zlato. select x.nazev from pokoj x where exists (select y.nazev from pokoj y where y.nazev = 'zlato' and x.nazev <> 'zlato' and x.kategoriecenik_id = y.kategoriecenik_id and x.popis = y.popis)
Průvodce studiem: Následující řešené příklady jsou příklady jazyka pro definování dat a manipulaci s daty.
Příklady: 1. Vytvořte tabulku Oddeleni s atributy Kod a Nazev: CREATE TABLE ODDELENI ( KOD
NUMBER
NOT NULL,
NAZEV CHAR (10)) 2. Na Kod vytvořte PK. ALTER TABLE ODDELENI ADD [CONSTRAINT PKODDELENI] PRIMARY KEY (KOD) 3.
Vytvořte tabulku Zaměstnanec: Cislo - PK Jmeno- vše velkým písmem Oddeleni - FK s odkazem na tabulku Oddeleni a její PK - Kod Datum nástupu je implicitně nastaven na systémové datum Plat větší než 500 Kč.
CREATE TABLE Zaměstnanec (Cislo NUMBER
[CONSTRAINT pk_Cislo] PRIMARY KEY,
Jmeno VARCHAR2(10)
[CONSTRAINT nn_Jmeno] NOT NULL 65
[CONSTRAINT upper_Jmeno] CHECK (Jmeno = UPPER(Jmeno)), Zarazeni VARCHAR2(9), Oddeleni NUMBER
[CONSTRAINT Oddeleni(Kod),
fk_Oddeleni]
REFERENCES
Nastup DATE
DEFAULT SYSDATE,
Plat NUMBER(10,2)
[CONSTRAINT ck_Plat] CHECK (Plat > 500))
4. Vytvořte tabulku Informace, která se skládá z položek: Rodne_cislo char(10), Datum_prijezdu Date, Text char(250). Create table Informace (Rodne_cislo char(10),Datum_prijezdu date, Text char(250)) 5. Na sloupec Rodne_cislo a Datum_prijezdu vytvořte unikátní index. Create unique index inkey1 on Informace (Rodne_cislo, Datum_prijezdu) size 200 rows 6. Do tabulky Informace vložte sloupec Duvernost Alter table Informace add Duvernost integer 7. Změňte délku atributu Text na 100 znaků Alter table Informace modify (Text char(100)) 8. Vložte do tabulky Informace řádek '5357227455','20.1.1993','nedává spropisné',10 Insert into Informace values ('5357227455','20.1.1993','nedává spropisné',10) 9. Smažte z tabulky Informace řádek s hodnotou atributu Duvernost = 10 Delete from Informace where Duvernost = 10 10. Smažte index infkey1 Drop index infkey1 11. Zrušte tabulku Informace Drop table Informace 12. Vytvořte tabulku Pacient s atributy RC char(10), Jmeno char(15), Prijmeni char(15), Datum_narozeni Date, Pojistovna char(25) Create table Pacient (RC char(10), Jmeno char(15), Prijmeni char(15), Datum_narozeni Date, Pojistovna char(25)) 13. Vytvořte tabulku Pojistovna s atributy Kod number a Nazev char(20) a Kod nastavte jako PK. Create table Pojistovna (Kod number primary key, Nazev char(20)) 14. Změňte strukturu tabulky Pacient tím, že nastavte RC jako PK. Alter table Pacient add primary key (RC) 15. Změňte datový typ atributu Pojistovna tabulky Pacient na number Alter table Pacient modify Pojistovna number
66
16. Vytvořte vazbu mezi tabulkami Pojistovna a Pacient takovou, že každý Pacient musí být pojištěn u jedné pojišťovny. Alter table Pacient add foreign key (Pojistovna) references Pojistovna(Kod) 17. Vložte do tabulky Pojistovna řádek Kod=111, Nazev=VZP Insert into Pojistovna values (111,'VZP') 18. Vložte do tabulky Pacient dva pacienty s následujícími atributy: 5562290800,Jan, Novotný, 1.1.1990,VZP 5205130045, Karel, Vlach, 31.12.2001, VZP Insert into Pacient values ('5562290800','Jan','Novotný', '1.1.90','111') Insert into Pacient values ('5205130045','Karel','Vlach', '31.12.2001','111')
Pojmy k zapamatování: Schéma databáze Select Create Alter Insert Delete Update
Průvodce studiem: Po prostudování teoretické kapitoly a dvou procvičovacích kapitol již jistě dobře ovládáte jazyk SQL a tudíž můžete bez obav přistoupit k řešení korespondenčního. Přeji Vám k jeho řešení hodně klidu a pohody.
4 MODUL 4 4.1 QBE - QUERY BY EXAMPLE Cíl: Cílem této kapitoly je ozřejmit možnosti QBE a naznačit jeho srovnání s SQL. Čtenář po prostudování této kapitoly bude umět jakýkoli dotaz, vyslovený v přirozeném jazyce, který lze zapsat v SQL, zapsat do QBE. Bude umět používat agregační funkce v QBE a provádět manipulační operace založené na akčních dotazech. 67
Klíčová slova: QBE, agregační funkce, speciální operátory, vkládání dat, mazání dat, manipulace s daty. QBE je jazyk založený na doménovém relačním kalkulu. Jazyk používá speciální editor, pomocí kterého se na obrazovce počítače zobrazí jeden nebo více formulář dotazu. V záhlaví každého formuláře je jméno relace a jména atributů. Jazyk QBE implicitně odstraňuje z odpovědi dotazu duplicitní instance.
Průvodce studiem: Základní pojmový aparát jste si už osvojili, proto problematiku QBE budete studovat na jednotlivých příkladech.
Příklady na dotazování v QBE: Mějme schéma databáze: Učitelé(č_učitele, jméno_u, katedra) Předměty(č_před, název_p, semestr) Skupiny(č_skupiny, obor, ročník) Studenti(č_stud, jméno_s, č_skupiny) Lekce(č_lekce, č_skupiny, č_učitele, č_předmětu) Dotaz 1: Najděte jména všech učitelů. Učitelé
č_učitele
jméno
katedra
P. Dotaz 2: Najděte, na které katedře učí učitel Král. Učitelé
č_učitele
jméno
katedra
Král
P.
č_učitele
jméno
katedra
_a
P.
Dotaz 3: Najděte pro každého učitele čísla lekcí, které vyučuje. Učitelé
68
Lekce
č_lekce
č_skupiny
P.
č_učitele
č_předmětu
_a
_a je vzorový prvek, pomocí kterého je realizována operace spojení. Do výsledné relace se umístí pouze ty instance relace Učitelé a relace Lekce, kde hodnota atributu č_učitele z relace Učitelé bude rovna hodnotě atributu z relace Lekce. Dotaz 4: Najděte lekce, ve kterých učí učitel Král. select x.č_lekce from Lekce x, Učitelé y where x.č_učitele=y.č_učitele and jméno=”Král” Učitelé
Lekce
č_učitele
jméno
_a
Král
č_lekce
č_skupiny
katedra
č_učitele
P.
č_předmětu
_a
4.1.1 Agregační funkce v QBE Agregačními funkcemi v jazyce QBE jsou funkce SUM.(suma), AVG.(průměrná hodnota), MAX.(maximální hodnota), MIN.(minimální hodnota), CNT.(count - počet hodnot). Speciální operátor ALL. zahrnuje duplicitní hodnoty, UN. vyloučí duplicity. Operátor ALL. pracuje s kolekcemi, operátor UN. s množinami. Dotaz 5: Zobrazte počet učitelů z relace Učitelé. Učitelé
č_učitele
jméno
katedra
P. CNT. Dotaz 6: Zobrazte maximální číslo lekce. Lekce
č_lekce
č_skupiny
č_učitele
č_předmětu
P.MAX. Dotaz 7: Zobrazte počet skupin 1.ročníku. Skupiny
č_skupiny
obor
P.CNT.
ročník =1
V uvedených dotazech jsme agregační funkci aplikovali na celou relaci. Chceme-li aplikovat agregační funkci na podmnožinu relace, kterou získáme na základě selekčního kritéria, musíme použít skupinový operátor G. Operátor G má stejnou funkci jako konstrukt Group by v SQL. Vyvoří tedy skupiny na základě stejné hodnoty definovaného atributu.
69
Dotaz 8: Zobrazte počty učitelů na jednotlivých katedrách. Učitelé
č_učitele
jméno
P. CNT.
katedra P.G.
Dotaz 9: Zobrazte počet studentů a č_skupiny, kde je celkový počet studentů ve skupině menší než 10. Skupiny
č_skupiny
obor
ročník
jméno_s
č_skupiny
P. _a Studenti
č_stud P.CNT. < 10
_a
Dotaz 10: Zobrazte počet studentů a č_skupiny, kde je celkový počet studentů Informatiky ve skupině menší než 10. Skupiny
Studenti
č_skupiny
obor
P. -_a
Informatika
č_stud
jméno_s
P.CNT. < 10
ročník
č_skupiny _a
4.1.2 Manipulace v QBE Vkládání dat Vkládání lze provádět do jedné n-tice (jeden řádek tabulky), pak stačí editovat jeden formulář dotazu a to je formulář dotazu vznesený na tabulku, do níž vkládáme data. Pokud vkládáme data do více n-tic na základě výběru těchto dat z jiné tabulky resp. z jiných tabulek, je třeba použít formulář dotazu na všechny tabulky. Ta tabulka, do níž se data vkládají, se nazývá cílová, ostatní tabulky se nazývají zdrojové.
4.1.3 Inkluze Inkluze neboli vnější spojení je operace, při které se k n-ticím spojeným ze dvou relací na rovnost přidají ještě n-tice levé (left join) nebo pravé /right join) relace. Příklad: Najděte učitelé, kteří nevyučují v žádných lekcích. Učitelé
Lekce
č_učitele
jméno
_a!
P.
č_lekce
č_skupiny
70
č_učitele
katedra
č_předmětu
Is null
_a
_a! vzorový prvek pro operaci ikluze.
Příklady na vkládání dat: Příklad 1: Do tabulky Učitelé vložte záznam : 100, Jan Novák, Informatika Učitelé
č_učitele
jméno
katedra
I.
100
Jan Novák
Informatika
Příklad 2: Mějme tabulku Učitelé_I, která bude mít stejnou strukturu jako tabulka Učitelé. Do tabulky Učitelé_I vložte všechny řádky z tabulky Učitelé, pro něž katedra = Matematika. Tabulka Učitelé bude zdrojovou tabulkou, tabulka Učitelé_I bude cílovou tabulkou. Učitelé_I
č_učitele
jméno
katedra
I.
_a
_b
_c
Učitelé
č_učitele
jméno
katedra
_a
_b
_c, Informatika
Mazání dat Mazat můžeme jeden nebo více řádků tabulky. Řádky určené ke smazání se získají na základě vyhodnocení podmínky uvedené ve formuláři. Není-li uvedena podmínka, vymažou se všechny řádky z tabulky a tabulka zůstane prázdná.
Příklad na mazání dat: Z tabulky Učitelé smažte všechny řádky, u nichž hodnota atributu katedra = Matematika. Učitelé
č_učitele
jméno
katedra Matematika
D. Modifikace dat
Při modifikování dat lze změnit hodnotu atributu resp. atributů v dané tabulce. Stejně jako v předchozích případech potřebujeme formulář dotazu, do kterého zapíšeme atribut, jehož hodnotu chceme měnit a jak. Lze změnit hodnotu bez jakýchkoli podmínek, resp. za podmínky. Nová hodnota může být zadána jako konstanta resp. vypočtená hodnota vycházející ze staré hodnoty atributu.
71
Příklady na modifikaci dat: Příklad 1: V tabulce Skupiny změňte hodnotu atributu ročník na 2 u všech řádků tabulky. Skupiny
č_skupiny
obor
ročník 2
U. Příklad 2:
V tabulce Učitelé změňte u všech učitelů č_učitele na č_učitele + 100, u nichž katedra = Chemie. Učitelé
č_učitele
jméno
katedra
U.
_x+100
_y
Chemie
_x
_y
Chemie
Při změně hodnoty atributu, vycházející ze staré hodnoty, je zapotřebí dvou řádků formuláře dotazu. Jeden řádek představuje starou hodnotu atributu č_učitele, druhý specifikuje aktualizovanou hodnotu.
Pojmy k zapamatování: QBE Agregační funkce Speciální operátory Vkládání dat Mazání dat Manipulace s daty
Kontrolní otázky: 1. Na jakých principech je založen jazyk QBE? 2. Jak lze definovat dotaz na spojení v QBE? 3. Jak lze v QBE zadat agregační funkce? 4. Co je to vzorový prvek?
72
4.2 ŘEŠENÉ PŘÍKLADY V QBE Cíl: Cílem této kapitoly je naučit čtenáře přepisovat dotazy formulované v přirozeném jazyce do jazyka QBE. Po prostudování této kapitoly by již měl být čtenář schopen samostatně vytvářet dotazy v QBE a to i složitější dotazy. Dále po prostudování této kapitoly by měl čtenář umět manipulovat s daty pomocí příkazů jazyka QBE. Klíčová slova: Schéma databáze, Select, Create, Alter, Insert, Delete, Update
Průvodce studiem: Následující řešené příklady jsou dotazy nad jednoduchou databází, jejíž schéma je vždy uvedeno v úvodu příkladu. Jakmile si pozorně prostudujete i tuto kapitolu, budete schoni bez potíží zvládnout korespondenční úkol, který následuje. 1. Z relace ČTENÁŘ(Č_ČT, JMÉNO, ADRESA) operací projekce vyberte atributy Č_ČT a JMÉNO.
P. AO DO (n)
příkaz projekce uspořádat vzestupně uspořádat sestupně pořadí položek pro uspořádání
2. Z relace EXEMPLÁŘ(ISBN, INV_Č, D_NÁKUP) vyberte selekcí pouze ty řádky, u nichž D_NÁKUP > 20. 03.95.
P.
pod názvem relace znamení projekci všech atributů.
3. Z relace EXEMPLÁŘ(ISBN, INV_Č, D_NÁKUP) vyberte selekcí pouze ty řádky, u nichž D_NÁKUP > 20. 03.95 nebo < 20. 04. 95.
73
4. Z relace EXEMPLÁŘ(ISBN, INV_Č, D_NÁKUP) vyberte selekcí pouze ty řádky, u nichž D_NÁKUP > 20. 03.95 a zároveň < 20. 04. 95.
5. Relaci KNIHA(ISBN, AUTOR, TITUL) spojte s relací REZERV(ISBN, Č_ČT, D_REZ) na rovnost hodnot atributu ISBN. používají se proměnné - vzorové prvky (zde označené _IS). Atributy přes které se spojuje musí být definovány nad stejnou doménou.
Tento způsob spojování odpovídá v relační algebře spojení na rovnost. (P(A, B, C) * R(C, D)) [A, D]
P[C = C] R[A, D]
V relačním kalkulu jde o použití existenčního kvantifikátoru. x . A, y . D where R(y) and exists x(P(x) and x . C = y . C) 6. Vyberte zákazníky, kteří mají rezervovanou kazetu, pro jejíž hudbu neexistuje interpretace Armstrongem.
V relačním kalkulu: y.Č_Z where REZERVACE (y) and not exists x KAZETA (x.NÁZEV = y.NÁZEV and x.INTERPRET = ´Armstrong´) 7. Vyberte zákazníky, kteří mají rezervovanou kazetu, která není interpretována Armstrongem.
74
V relačním kalkulu: y.Č_Z where REZERVACE(y) and exists x KAZETA (x.NÁZEV = y.NÁZEV and x.INTERPRET = ´Armstrong´) 8. Odstraňte všechny knihy K. H. Borovského z relace KNIHA.
9. Odstraňte ty rezervace čtenáře H56, které se týkají stejného ISBN jako má čtenář H66.
10. Zobrazte počty výpůjček jednotlivých čtenářů (zobrazte i ty, kteří nemají vypůjčeno nic).
Vhodným umístěním operátoru ! získáme levé či pravé vnější spojení. CALC COUNT lze nahradit P.CNT. (jak bylo uvedeno ve výkladové části).
Průvodce studiem: Dejte si kratičkou pauzu a pak se pusťte do vypracování korespondenčního úkolu.
75
5 MODUL 5 5.1 TRANSAKCE - ZÁKLADNÍ POJMY A VLASTNOSTI Cíl: Cílem je seznámit čtenáře se základními pojmy, užívanými v transakčním zpracování relačních systémů řízení báze dat. Po prostudování kapitoly by měl čtenář umět definovat transakci a vyjmenovat vlastnosti transakcí. Dále by měl umět vysvětlit pojen distribuovaný databázový systém Klíčová slova: Transakce, atomičnost, izolovaná vratnost, pernamentnost, uspořádatelnost, globální a lokální transakce, distribuovaný databázový systém Transakce je spojení logicky k sobě patřících operací. Musí být vykonány všechny operace, které jsou součástí transakce nebo musí být databáze uvedena do stavu před započetím transakce. Transakce převádí databázi z jednoho konzistentního stavu do druhého konzistentního stavu. Konzistence je nutnou a postačující podmínkou úspěšného ukončení transakce.
5.1.1 Vlastnosti transakcí Atomičnost Na celou posloupnost operací se nahlíží jako na jednu logickou jednotku. Tato může být provedena jako celek. Nemůže-li být započatá transakce provedena, musí být všechny provedené změny vráceny vrácení transakce (ROLLBACK). Izolovaná vratnost Vracením transakce není postižena žádná jiná transakce nebo tato musí být také vrácena. Efekt indukovaného vrácení se označuje jako řetězové vrácení (cascading rollback) nebo jako tzv. dominový efekt. Pernamentnost (durability) Změny provedené úspěšnými transakcemi jsou skutečně uloženy v bázi dat a již nemohou být ztraceny. Uspořádatelnost Se požaduje v souvislosti s distribuovanými databázemi. Výsledek distribuovaného zpracování lze získat sériovým provedením posloupnosti těchto transakcí.
5.1.2 Globální a lokální transakce Lokální transakce ke svému provedení potřebuje přístup k datům jen na jediném uzlu. Nepožaduje spolupráci s jinými uzly. Globální transakce přesahuje rozsah jednoho uzlu (nazývá se též distribuovaná).
76
5.1.3 Distribuovaný databázový systém Máme množinu uzlů a spojení mezi nimi. Báze dat je fragmentována a alokována na více uzlech (bližší informace k této problematice najdete v modulu 6). Globální transakce startuje z jednoho uzlu a šíří se podle potřeby do dalších uzlů. Rozpadá se do dílčích (lokálních) transakcí. Ty plní dílčí úkoly. Primární transakce - Primární uzel Primární transakce řídí běh celé globální transakce.
Aplikační program Modul řízení transakcí Komunikační modul
Modul řízení dat 1
Modul řízení dat 2
Operační systém 1
Operační systém 2
Hardware 1
Hardware 2
Fyzická data 1
Fyzická data 2
Modul řízení transakcí Zpracovává uživatelské transakce: •
analýza požadavků transakce
•
rozdělení transakce dle distribuce databáze
•
sestavení výsledku z podtransakcí
•
předání výsledků uživateli
Modul řízení dat •
čtení hodnot z lokální databáze
•
odesílání hodnot modulu řízení transakcí
77
•
zápis hodnot do dané lokální databáze
Pojmy k zapamatování: Transakce Atomičnost Izolovaná vratnost Pernamentnost Uspořádatelnost Globální a lokální transakce Distribuovaný databázový systém
Kontrolní otázky: 1. Definujte transakci. 2. Jaké jsou základní vlastnosti transakcí? 3. Co to je modul řízení transakcí? 4. Co to je primární transkace?
5.2 DVOUFÁZOVÝ POTVRZOVACÍ PROTOKOL Cíl: Po prostudování této kapitoly by měl čtenář umět vysvětlit principy dvoufázového potvrzovacího protokolu a způsoby řešení výpadků jednotlivých uzlů distribuovaného databázového systému Klíčová slova: Globální (primární) transakce, dílčí transakce, commit, abort, time out. Principem distribuovaných databází je skutečnost, že globální databáze je rozdělena do dílčích částí, které jsou umístěny na různých uzlech. Z toho vyplývá, že je-li třeba vykonat nějakou transakci, tato musí být rozdělena na dílčí transakce, které jsou vykonány na příslušných uzlech. Na těchto uzlech jsou prováděny změny na datech. Změny nesmí být zpřístupněny jiným transakcím (jiným uzlům), dokud není provedena globální transakce (vlastnost izolované vratnosti). Nemůže-li být aspoň jedna dílčí transakce úspěšně provedena, musí být všechny dílčí transakce vráceny zpět. Primární transakce je tedy rozdělena na více dílčích transakcí, které jsou vykonány na jednotlivých uzlech. Pro potvrzení správnosti se využije dvoufázový potvrzovací protokol.
78
FÁZE 1: Dílčí transakce, která provedla COMMIT (byla úspěšně ukončena), hlásí primární transakci (RC - hlášení). Provedené změny ještě nezpřístupní pro další transakce. FÁZE 2 - FÁZE JIŠTĚNÍ: Koordinátor primární transakce shromáždí RC-hlášení všech dílčích podtransakcí a vydá jim povolení (GLOBÁLNÍ COMMIT) ke zviditelnění změn. Hlásí-li některá dílčí transakce ABORT nebo není-li schopna dosáhnout RC-bodu v určitém časovém intervalu, primární transakce vysílá ABORT všem dílčím transakcím. Celá globální transakce bude vrácena zpět. SŘBD se musí postarat o skutečné provedení změn po provedení příkazu COMMIT. Po ukončení fáze jištění může transakce zpřístupnit provedené změny jiným transakcím. Pak teprve následuje vlastní konec transakce.
5.2.1 Výpadky uzlů a přerušení transakce 1.
Podtransakci není možno inicializovat .
2.
Primární transakce neobdrží od lokální zprávu o dosažení RC - bodu.
3.
Lokální uzel není schopen informovat o dosažení RC – bodu.
4.
Primární transakce obdržela zprávu RC nebo ABORT, ale nemůže zaslat globální zprávu COMMIT nebo ABORT.
Časové ohraničení čekání time out Řešení Případ 1: Primární transakce neobdrží zprávu o iniciování podtransakce. •
Pokusí se iniciovat podtransakci na jiném uzlu (pokud to lze).
•
Transakce nesmí být provedena na původním uzlu.
•
Dostane-li primární transakce z tohoto uzlu RC - hlášení, musí poslat zprávu ABORT.
•
Pokud nelze inicializovat podtransakci na jiném uzlu, pošle primární transakce všem zúčastněným uzlům zprávu ABORT.
Případ 2: Primární transakce obecně neví, zda podtransakce "spadla" ještě před dosažením RC - bodu nebo až po něm. •
Primární transakce vyšle na všechny zúčastněné podtransakce zprávu ABORT.
Případ 3: Neví se, zda lokální uzel stihnul přijat zprávu COMMIT resp. ABORT od primární transakce. •
Primární transakce proto musí zůstat aktivní dokud tuto zprávu uzlu nedoručí.
Případ 4: Chybové situace u primárních transakcí. •
Všechny podtransakce již poslaly RC-hlášení primární transakcí - samy nemohou způsobit globální ABORT, protože všechny hlásily RC obecně se dá jen čekat.
•
Alespoň jedna podtransakce hlásila ABORT podtransakce mohou provést lokální abort.
•
Nejsou ještě dodána všechna hlášení, lze buď čekat nebo globální transakci vrátit zpět.
79
nemůže nastat globální COMMIT
ostatní
Pojmy k zapamatování: Globální (primární) transakce Dílčí transakce Commit Abort Time out
Kontrolní otázky: 1. Co je to globální (primární) transakce? 2. Co je to dílčí transakce? 3. Kdy jsou zpřístupněny změny po vykonání transakce? 4. Jaké mohou nastat chybové situace při vykonávání transakce?
5.3 TRANSAKCE JAKO JEDNOTKA ZOTAVENÍ Z CHYB Cíl: Cílem této kapitoly je vysvětlit proces zotavení databáze z chyby, která vznikla při vykonání transakce. Čtenář by měl umět vysvětlit, v jakých stavem se může transakce nacházet, k čemu slouží žurnál, jak se provádí zápis o kontrolním bodu a jaké jsou algoritmy pro zotavení z chyby. Měl by minimálně umět popsat dvě možné strategie zotavení z chyb. Klíčová slova: Stavy transakce, žurnál, kontrolní bod, UNDO/REDO algoritmus Zotavení z chyby je obnova konzistentního stavu databáze po vzniklé chybě. Jedná se o následující činnosti: •
Vrácení přerušených transakcí.
•
Činnost po opětovném spuštění SŘBD:
•
Zaznamenání změn uzavřených transakcí ze žurnálu.
•
Vrácení neuzavřených transakcí.
•
Automatické znovuspuštění vrácených transakcí.
80
5.3.1 Žurnály(log files) Žurnály jsou soubory, které uchovávají informace o průběhu transakcí, a slouží k zotavení databáze po vzniklé chybě. Žurnály jsou v každém uzlu sítě a obsahují záznamy, popisující celou historii každé transakce. Stavy transakce Aktivní (A): Od počátku provádění transakce. Čá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): Nastane po skončení operace ROLLBACK. Potvrzený (C): Po úspěšném vykonání COMMIT.
5.3.2 Kontrolní body- checkpoints: Kontrolní body jsou body tc, kdy dochází k odeslání obsahu vyrovnávacích pamětí na disk a zápisu kontrolního záznamu (checkpoint record) do žurnálu. Tento záznam obsahuje seznam všech transakcí, které se v době tc prováděly, tj. započaly a nebyly uvedeny do stavu C.
5.3.3 UNDO / REDO algoritmus Je založen na bezprostředních aktualizacích databáze, kdy databáze je aktualizována před dosažením stavu PC. Zotavení databáze při chybě je možné ze žurnálu. Každá změna musí být do žurnálu zahrnuta před aktualizaci databáze. Žurnál drží záznamy obsahující položky: T, START T, jméno atributu, st_hodnota, n_hodnota ... ... T, COMMIT Algoritmus: 1. Vytvoří se dva seznamy transakcí označené UNDO a REDO. Do seznamu UNDO se uloží všechny transakce ze záznamu kontrolního bodu. Seznam REDO bude prázdný. 2. Započne prohledávání žurnálu od okamžiku tc dopředu. 3. Narazí-li se na začátek další transakce T, přidá se T do seznamu UNDO. 4. Je-li v žurnálu nalezen COMMIT pro transakci T, odstraní se T ze seznamu UNDO a převede se do seznamu REDO. 5. Na konci žurnálu jsou seznamy UNDO a REDO kompletní.
81
Příklad:
Transakce T1 byla ukončena před stavem tc Transakce T2 začala před tc, byla ukončena před tf Transakce T3 začala před tc, nebyla ukončena před tf Transakce T4 začala po tc, byla ukončena před tf Transakce T5 začala za tc, nebyla ukončena před tf Databáze musí být po transakcích T3 a T5 uvedena do původního stavu. Transakce T2 a T4 musí být provedeny znovu. Transakce T1 se neuvažuje, protože její operace byly fyzicky v čase tc již realizovány. Pro náš příklad jsou seznamy: UNDO obsahuje transakce T3 a T5 REDO obsahuje transakce T2 a T4 Zotavení po chybě: •
Zpracování zpětným chodem v žurnálu transakce u UNDO seznamu.
•
Zpracování chodem vpřed transakce z REDO seznamu.
Kromě strategie bezprostřední realizace změn bývá rovněž používána strategie odložené realizace změn. Ta je založena na přepisu obsahu bufferů na disk až po globálním commitu transakce. Nedosáhne-li transakce globálního commitu, změny na disku se neuskuteční. Při této strategii se do žurnálu zapisují pouze nové hodnoty atributů pro chod vpřed při zotavení z chyby. Algoritmus, který využívá této strategie, se nazývá REDO algoritmus.
82
Pojmy k zapamatování: Stavy transakce Žurnál Kontrolní bod UNDO/REDO algoritmus REDO algoritmus
Kontrolní otázky: 1. V jakých stavech se může nacházet transakce? 2. Co je to žurnál? 3. Popište UNDO/REDO algoritmus 4. Jaké znáte strategie realizace změny databáze.
5.4 SYNCHRONIZACE Cíl: Po prostudování této kapitoly by měl čtenář umět vysvětlit princip uzamykacího protokolu, vysvětlit pojem uváznutí a dokumentovat jej na příkladu. Dále by měl umět vyjmenovat a vysvětlit způsoby řešení uváznutí. Dále by měl umět vyjmenovat základní příkazy data control language v SQL. Klíčová slova: Uzamykání, uváznutí, čekací graf, časová razítka, transakce v SQL Synchronizace vychází z předpokladu, že operace v rámci transakce musí být prováděny ve stanoveném pořadí. Zachování pořadí = sériový rozvrh. Je-li výsledek transakce stejný, jako v sériovém rozvrhu, může se pořadí vykonání operací měnit, resp. operace mohou být prováděny paralelně. Řízení synchronizace vychází obvykle z uzamykacích protokolů .
5.4.1 Dvoufázový uzamykací protokol Každý objekt, ke kterému je přistupováno, musí být nejprve uzamčen. Uzamykací modul musí přezkoušet v tabulce zámků, zda nehrozí konflikt. Lze-li příslušný objekt uzamknout, provede se záznam do tabulky zámků objekt se uzamkne. Zámky dílčí transakce budou platit tak dlouho, dokud nenastane globální COMMIT nebo ABORT. Centrální uzamykání Jeden uzel udržuje centrální tabulku zámků pro všechny zúčastněné uzly. V tomto uzlu je možno centrálně rozeznat uváznutí. 83
Decentralizované uzamykání Každý uzel vede vlastní tabulku zámků. Tento způsob je méně náročný na komunikaci a zabezpečuje větší nezávislost uzlů. Jsou zde větší potíže s rozpoznáním globálního uváznutí. Každý lokální čekací graf má navíc jeden vstup / výstup (EX), který modeluje vztahy k okolním uzlům.
5.4.2 Globální uváznutí Vznikne tehdy, když transakce cyklicky čekají na uvolnění uzamčených objektů nebo jiných systémových zdrojů.
Příklad: Transakce T1 má uzamčen objekt A a čeká na poskytnutí zámku pro objekt B. Objekt B drží uzamčen transakce T2, která zároveň čeká na poskytnutí zámku pro objekt A. Rozpoznání uváznutí Na základě čekacích grafů (wait - for graphs), kde: transakce jsou uzly grafu a vztahy "čekání na" jsou orientované hrany. Např. Transakce Ti čeká na uvolnění zámku transakce Tj se vyjádří :
Ti
Tj
Rozpoznání uváznutí je převedeno na problém nalezení všech kružnic v čekacím grafu. Podněty ke zkoumání možného uváznutí 1.
Překročení určité čekací doby při požadavku na uzamčení objektu.
2.
Požadavek na uzamčení objektu nebyl akceptován.
3.
Uváznutí lze zkoumat periodicky.
Vyhnutí se uváznutí Jedná se o metoda tzv.časových razítek. Všechny dílčí transakce jedné globální transakce nesou časové razítko své primární transakce. Nechť transakce R požaduje zámek pro objekt a dostane se do konfliktu s transakcí O, která tento zámek vlastní. TS(R), TS(O) jsou časová razítka pro transakci R resp. O. Dvě možnosti vyhnutí se uváznutí: 1. "Wait - Die" metoda if TS(R) < TS(O) then wait else die 2. "Wound - Wait" metoda if TS(R) < TS(O) then wount else wait Wait: Čekání na konec nebo přerušení transakce O (uvolnění zámku). Die, Wound: Přerušení transakce R a její následné vrácení. U Die vychází aktivita od mladší transakce (s větším časovým razítkem). Jakmile se pokusí uzavřít objekt už uzamčený starší transakcí, 84
způsobí tím své vlastní přerušení. U Wound je aktivní starší transakce. Pokusí-li se uzavřít objekt, který má uzamčen mladší transakce, pak se pokusí tuto mladší transakci zrušit.
5.4.3 Transakce v SQL Transakce je posloupnost příkazů jazyka SQL, formující jednotku zotavení z chyb a souběžného zpracování. První příkaz v SQL znamená počátek transakce. Každá transakce končí vyvoláním buď příkazu COMMIT (normální ukončení) nebo ROLLBACK (vrácení transakce). V případě chyby se zpracování transakce přeruší a databáze se uvede do stavu před transakcí. V opačném případě - provedení příkazů, dokončení transakce, vytvoření nové verze databáze. Je-li specifikován "savepoint", ROLLBACK způsobí návrat k tomuto bodu. Bod lze nastavit příkazem SAVEPOINT. ROLLBACK k bodu savepoint neuvolňuje LOG soubory (žurnály). ROLLBACK bez specifikovaného savepoint uvolňuje LOG soubory(žurnály).
Příklad: SQL> COMMIT označení konce transakce a začátek nové transakce SQL Command........ SQL> ROLLBACK předcházející 3 příkazy se neprovedou
Pojmy k zapamatování: Uzamykání Uváznutí Čekací graf Časová razítka Transakce v SQL
Kontrolní otázky: 1. Jak funguje dvoufázový uzamykací protokol? 2. Co je to uváznutí a jak se rozpozná? 3. Sestrojte na konkrétním příkladu čekací graf. 4. Vysvětlete metodu časových razítek.
85
6 MODUL 6 6.1 PŘEHLED ARCHITEKTUR DATABÁZOVÝCH SYSTÉMŮ Cíl: Po prostudování této kapitoly by měl čtenář umět zhodnotit různé architektury databázových systémů. Dále by měl umět popsat fáze a způsoby fragmentace globální databáze a alokace dílčích fragmentů. Měl by umět na příkladu vysvětlit přínos replikovaných distribuovaných databází. Klíčová slova: Distribuovaná databáze, replikovaná databáze, fragmentace, alokace, replikační server, přenosový textový protokol. Ve vývoji databázových systémů můžeme sledovat následující etapy: 1. Centrální databáze •
Data uložena na jednom, společném místě.
•
Centralizovaně organizována správa.
•
Požadavky zpracovávány v jednom centru, velká zátěž komunikačních linek .
2. Skupina lokálních databází •
Data fyzicky rozptýlena v různých místech v lokalitě jejich vzniku.
•
Lokálně organizovaná správa.
•
Problémy s pohybem dat mezi lokalitami zejména při spojení s centrem.
3. Systém distribuovaných souborů •
Data fyzicky rozptýlena na různých místech v lokalitě jejich vzniku.
•
Lokálně organizovaná správa.
•
Pohyb dat mezi lokalitami zajištěn pomocí přenosových souborů.
4. Distribuovaná databáze •
Data fyzicky rozptýlena na různých místech s lokální autonomií.
•
Logicky centralizovaný pohled na data s globálním řízením.
•
Globální transakce s dvoufázovým potvrzovacím protokolem.
•
Problém s přístupovou rychlostí při napojení na geograficky vzdálenou databázi.
86
5. Distribuovaná replikovaná databáze •
Jeden logický objekt lze nalézt na několika uzlech s lokální autonomií.
•
Logicky centralizovaný pohled na data s globálním řízením.
•
Problémy s přístupovou rychlostí jsou řešeny redundancí dat a zpracováním požadavků v lokální databázi.
•
Globální transakce jsou řešeny systémovou koordinací, obvykle unikátními analytickými způsoby, které souvisí s povahou řešeného problému.
Vývoj spěje od centralizovaného k distribuovanému zpracování s využitím replikace. Hlavní výhoda: •
Lokální autonomie v uzlech sítě.
•
Možnost pracovat s lokálními daty v místě jejich vzniku.
6.1.1 Distribuce globálních relací Data v distribuované databázi jsou organizována na logické úrovni jako relace. Uživatel specifikuje dotazy ke globálním relacím. Tyto dotazy musí SŘBD přeformulovat vzhledem k fyzickému umístění těchto relací. Globální relace je rozdělena do množiny dílčích relací umístěných v uzlech sítě. Tyto dílčí relace jsou realizovány pomocí souborů na fyzické úrovni. Fragmentace a alokace Požadavek nezávislosti dat na aplikačních programech dotaz by neměl být zatížen: •
Místem fyzického uložení dat.
•
Způsobem distribuce globálních dat do dílčích relací.
•
Způsobem několikanásobného uložení dat (redundance).
Fragmentace je rozložení globálních relací do logických dílčích relací. Dílčí relace jsou pak jednotlivými fragmenty. Alokace je určení místa uložení (případně redundantní uložení) pro jednotlivé fragmenty. Existuje několik možností rozdělení globální relace a podle toho taky rozlišujeme typy fragmentací: 1. Nefragmentované vložení (triviální případ). 2. Horizontální fragmentace. 3. Vertikální fragmentace. 4. Kombinovaná fragmentace. Horizontální fragmentace Jedná se o takové rozdělení globální relace R na dílčí relace Rj, že R lze obdržet jako sjednocení dílčích relací R := Rj, j = 1, 2,.......,p
87
Příklad: Máme globální relaci DODAVATEL. Tuto relaci rozdělme do 3 dílčích relací tak, že 1. dílčí relace bude obsahovat všechny dodavatele z Hamburgu, 2. dílčí relace všechny dodavatele z Hagenu a 3. dílčí relace všechny zbývající dodavatele. DODAVATEL1 := DODAVATEL (MĚSTO = ´Hamburg´) DODAVATEL2 := DODAVATEL (MĚSTO = ´Hagen´) DODAVATEL3 := DODAVATEL (MĚSTO <> ´Hagen´ and MĚSTO <> ´Hamburg´) Globální relaci získáme: DODAVATEL = DODAVATELi, I = 1, 2, 3 Vertikální fragmentace Při vertikální fragmentaci globální relace jsou jednotlivé dílčí relace definovány jako její projekce. Globální relace je pak definována jako spojení dílčích relací. Pro vertikální fragmentaci musí platit, že po spojení dílčích relací (fragmentů) dostaneme původní relaci. Této vlastnosti se říká bezztrátovost. Aby vertikální fragmentace byla bezztrátová, musí být v každé dílčí relaci obsažen klíč globální relace. R := R1 * R2 * ............* Rn
Příklad: Relaci ZAMĚST vertikálně fragmentujte a to tak, že jméno a adresa tvoří jednu dílčí relaci, osobní číslo šéfa a číslo oddělení druhou relaci a třetí dílčí relaci tvoří jméno a plat. Klíčovým atributem globální relace je OS_ČÍS. ZAMĚST (OS_ČÍSLO, JMÉNO, ADRESA, PLAT, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ) ZAMĚST1 := ZAMĚST[ OS_ČÍSLO, JMÉNO, ADRESA] ZAMĚST2 := ZAMĚST[ OS_ČÍSLO, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ] ZAMĚST3 := ZAMĚST[ OS_ČÍSLO, JMÉNO, PLAT] Globální relace ZAMĚST = ZAMĚST1 * ZAMĚST2 * ZAMĚST3 Kombinovaná fragmentace Tatáž globální relace může být fragmentována zároveň horizontálně i vertikálně.
Příklad: Relaci ZAMĚST vložte jako dílčí relaci s OS_ČÍS a PLAT a dílčí relaci, kde se plat vyskytovat nebude. Dílčí relaci bez platu horizontálně rozdělte podle podmínek.
88
ČÍS_ODDĚLENÍ < 300 a ČÍS_ODDĚLENÍ >= 300. ZAMĚST1 := ZAMĚST[ OS_ČÍSLO, JMÉNO, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ, ADRESA] ZAMĚST2 := ZAMĚST[ OS_ČÍSLO, PLAT] ZAMĚST11 := ZAMĚST1[ ČÍS_ODDĚLENÍ < 300] ZAMĚST12 := ZAMĚST1[ ČÍS_ODDĚLENÍ >= 300] ZAMĚST11 := ZAMĚST[ OS_ČÍSLO, JMÉNO, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ, ADRESA] (ČÍS_ODDĚLENÍ < 300) ZAMĚST12 := ZAMĚST[ OS_ČÍSLO, JMÉNO, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ, ADRESA] (ČÍS_ODDĚLENÍ >= 300) ZAMĚST := ZAMĚST1 * ZAMĚST2 ZAMĚST := (ZAMĚST11 ZAMĚST12) * ZAMĚST2 Alokace Základní 2 hlediska pro alokaci: 1. Efektivita pří zpracování dotazů tak, aby cena dotazů a aktualizací byla co nejmenší. Do ceny se zahrnuje čas přenosu a čas vyhodnocení odpovědi. 2. Zajištění vysoké dostupnosti dat - v případě výpadku jednoho uzlu zajistit další zpracování redundantní uložení dat. Optimální distribuce dat Obecně mohou být distribuována jak data tak funkce. Distribuce funkcí: Jisté transakce (res. druhy transakcí) jsou přiřazeny jistým uzlům. Nějaký uzel převezme funkci transakčního monitoru pro jistou třídu transakcí. Na jednom uzlu může být umístěno více transakčních monitorů a mohou být uzly, na kterých žádný transakční monitor není.
Příklad: Příklad zpracování dotazu nebo příkazu změny: •
Na libovolném uzlu i bude inicializován dotaz nebo aktualizační příkaz.
•
Příkaz bude předán příslušnému uzlu j, který má roli transakčního monitoru (může být i = j).
•
V případě dotazu vybere uzel j ten vhodný datový uzel k, který je k vyhodnocení dotazu potřebný. V případě změny posílá uzel j příkaz změny na všechbny takové uzly, které obsahují kopie pozměňovaných dat. (Může nastat i = j = k).
•
Obecně lze předpokládat, že distribuovaný databázový systém má N uzlů, M transakčních monitorů a data jsou rozdělena na P částí. Pro optimalizaci distribuce dat se sestaví matematický model obsahující následující veličiny:
Matice: Qn,m,p...........odhad počtu dotazů 89
Un,m,p...........odhad počtu příkazů změn C qn,n...........průměrná cena za jednotku dotazu z uzlu i do uzlu j (i, j = 1.....N) C n,n...........průměrná cena za jednotku aktualizace mezi uzly i a j (i, j = 1.....N) Proměnné: Gp.....velikost fragmentu p (p = 1....P) Sj.....cena paměti za jednotku dat na uzlu j (j = 1......N) Kj....paměťová kapacita uzlu j (j = 1.......N)
6.1.2 Základy replikace dat Replikace dat je vytvoření kopií dat na všechny uzly, kde očekáváme, že budou data potřebná. Základním principem replikace je uchování replik dat tam, kde budou nejvíce využívána. Replikace optimalizuje nároky na přenos dat v sítích a snižuje průměrnou dobu odezvy. Cena za replikaci vyšší nároky na kapacitu disků. Základní příčina replikace Snaha minimalizovat přenos dat v rozlehlé síti WAN. Velká centrální databáze je rozdělena na menší části při zachování jediného logického pohledu na data. Přičemž průměty dat na různá fyzická místa jsou provedeny vícenásobně. Výhoda spočívá v lokální autonomii na jednotlivých uzlech. Replikované distribuované databáze jsou založeny na principu přenosu dat z uzlu vzniku či změny do ostatních uzlů. Základní možnosti přenosu změn 1. Okamžitě po ukončení lokální transakce na jednom uzlu do uzlů jiných. Používá upravenou variantu dvoufázového potvrzování. 2. Přenos změny odděleně od doby vzniku. Tato technologie rozděluje proces replikace na dvě fáze: •
Uchovávání záznamů o provedených změnách dat.
•
Až je naplněn určitý objem změn přenos na další uzly.
3. Přenos změn se provádí v pevně naplánované době. Umožňuje přenos velkého objemu dat v době malého provozu v síti (v nočních hodinách). Koordinace fáze změn a přenosu Replikační server, který je umístěn v centru sítě, řídí proces replikace. Obsahuje repliky všech dat distribuovaných v síti. Satelity jsou ostatní místa zpracování dat, označovaná jako uzly. Obsahují systémovou databázi, což jsou systémové tabulky, které popisují mechanismus replikace. Logická replikovaná databáze celého distribuovaného systému je horizontálně fragmentována na dílčí databáze. Alokace každého z fragmentů je jak v centrální replikované databázi (na replikačním serveru), tak na příslušných satelitech. Členění databáze z pohledu replikace •
Privátní data: jsou k dispozici pouze na daném uzlu.
•
Systémová data: obvykle se nacházejí shodná na všech uzlech sítě.
90
•
Replikovaná data.
Příklad: Příklad replikace v provozu Úkol replikačního procesu je zpracovávat všechny změny, které uživatelé v replikovaných databázích provedli za celou dobu od poslední replikace. To vyžaduje: 1. Průběžné zapisování změn do změnového zásobníku. 2. Čtení zásobníku a rozeslání změn a jejich promítnutí do cílových databázích. Systémová databáze obsahuje popis rozprostření replikovaných databází. 3. Do doby ukončení replikačního procesu zůstávají změny v místě jejich vzniku. Spuštění replikačního procesu inicializuje operační systém svými prostředky, na základě nastavených časových požadavků v systémové databázi. Obvykle se proces spouštění replikace realizuje jednou denně ve stejný čas (nejčastěji v noci), přičemž existuje možnost spustit replikaci kdykoli ručně. Takto nastartovaný replikační proces se týká změn s vysokou prioritou, kdy promítnutí změn do všech databází je neodkladné. Aktivace replikace je prováděna v centrálním uzlu sítě, ten nastartuje potřebné procesy ve všech satelitních uzlech. V průběhu replikačního procesu se vytváří textový protokol. Postup při replikaci 1. Testování stavu přenosových tras a stavu všech databází, které se mají replikace zúčastnit. Pokud jsou některé přenosové trasy mimo provoz, tyto satelitní uzly jsou z replikace vynechány. 2. Zaslání výzev z centra satelitním uzlům, aby zahájily generování přenosových souborů (ty zahrnují změny provedené na příslušném uzlu). 3. Zasílání zakódovaných, komprimovaných přenosových souborů ze satelitů do centra. Centrum postupně přijímá přenosové soubory. 4. Po obdržení přenosových souborů od všech aktivních satelitů zahajuje centrum promítání změn do centrální databáze. O této činnosti se pořizuje protokol. 5. Centrum generuje přenosové soubory obsahující změny pro satelitní databáze. Jsou to změny za dobu od poslední replikace. Soubory jsou zakódovány a komprimovány a přeneseny na příslušné satelity. Současně dostanou satelity pokyn, aby obdržená data promítly do svých databází. 6. Centrum od satelitů očekává potvrzení o úspěšném promítnutí změn do satelitních databází. Na závěr se vypíše tabulka stavu všech satelitů po replikaci. Její kontrolu získá správce distribuované replikované databáze přehled o úspěšnosti replikace. 7. Replikační proces dává správci nástroje, jimiž může provádět replikaci i pro přerušené linky přenosem dat na magnetických médiích.
91
Pojmy k zapamatování: Distribuovaná databáze Replikovaná databáze Fragmentace Alokace Replikační server Přenosový textový protokol
Kontrolní otázky: 1. Jaké znáte architektury databázových systémů? 2. Jaké znáte typy fragmentací a v čem spočívají? 3. Jaké jsou základní aspekty optimální alokace fragmentů? 4. Vysvětlete princip replikace dat.
6.2 ZPRACOVÁNÍ DOTAZŮ V DISTRIBUOVANÉ PROSTŘEDÍ Cíl: Cílem této kapitoly je na příkladech ukázat optimalizaci vyhodnocování dotazů. Čtenář by měl umět vyjmenovat situace, u kterých se aplikuje optimalizační mechanizmus a na čem je tento mechanizmus založen. Klíčová slova: Dotaz nad globální relací, dotaz nad dílčí relací, společný výraz dotazu, vyhodnocovací strom dotazu, pravidla pro rozpoznání společné části výrazu. Základní podmínkou kladenou na relační systém řízení báze dat je, aby formulace dotazu byla nezávislá na fyzické implementaci databáze. SŘBD musí být schopen přeformulovat dotaz tak, aby doba zpracování byla optimální. Optimalizace zahrnuje 1. Transformaci dotazu nad globálními relacemi na dotazy nad dílčími relacemi (fragmenty). 2. Rozpoznání společné části dotazu s cílem vyhodnotit je pouze jednou. 3. Odstranění přebytečných částí výrazu. 4. Paralelní zpracování jednotlivých částí dotazu s důrazem na výpočet spojení.
92
Situace 1:
Příklad 1: Globální relace DÍL má 12 000 n-tic, které jsou horizontálně rozděleny do 3 částí. Chceme provést dotaz DÍL (CENA > 7 000). K tomu je třeba, aby bylo formálně popsáno rozdělení globální relace na fragmenty. Schéma relační databáze: ZAMĚST (OS_ČÍS, JMÉNO, PLAT, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ, ADRESA) ODDĚLENÍ (ČÍS_ODDĚLENÍ, NÁZEV ODDĚLENÍ, OBOR, OS_ČÍS_ŠÉFA) DÍL (ČÍS_DÍLU, ČÍS_DODAVATELE, CENA) DODAVATEL ( ČÍS_DODAVATELE, JMÉNO_DODAVATELE, MĚSTO) Globální relace DÍL je rozdělena: DÍL1 := DÍL (0 < ČÍS_DÍLU =< 5 000) DÍL2 := DÍL (5 000 < ČÍS_DÍLU =< 8 000) DÍL3 := DÍL (8 000 < ČÍS_DÍLU =< 11 999) DÍL = DÍL1 DÍL2 DÍL3 Formulace dotazu: Q1 := DÍL (CENA > 7 000) Transformace dotazu: Q´1 := (DÍL1 DÍL2 DÍL3) (CENA > 7 000) Q´´1 := DÍL1 (CENA > 7 000) DÍL2 (CENA > 7 000) DÍL3 (CENA > 7 000) Na jednotlivých uzlech bude nejprve vyhodnocena selekce, pak dojde ke sjednocení.
Příklad 2: Předpokládejme následující fragmentaci relace DODAVATEL: DODAVATEL1 := DODAVATEL (MĚSTO = ´Hamburg´) DODAVATEL2 := DODAVATEL (MĚSTO = ´Hagen´) DODAVATEL3 := DODAVATEL (MĚSTO <> ´Hagen´ and MĚSTO <> ´Hamburg´) DODAVATEL := DODAVATEL1 DODAVATEL2 DODAVATEL3 (MĚSTO = ´Hagen´) Formulace dotazu:
93
Q2 := DODAVATEL (MĚSTO = ´Hagen´) Transformace dotazu: Q´2 := DODAVATEL1 DODAVATEL2 DODAVATEL3 (MĚSTO = ´Hagen´) Q´´2 := DODAVATEL1 (MĚSTO = ´Hagen´) DODAVATEL3 (MĚSTO = ´Hagen´)
DODAVATEL2 (MĚSTO = ´Hagen´)
Poddodazy, jejichž vyhodnocením se získají prázdné množiny, se vyloučí. Proto se celý dotaz redukuje na: Q´´2 := DODAVATEL2 (MĚSTO = ´Hagen´) Situace 2:
Příklad 3: Schéma relační databáze: ZAMĚST (OS_ČÍS, JMÉNO, PLAT, OS_ČÍS_ŠÉFA, ČÍS_ODDĚLENÍ, ADRESA) ODDĚLENÍ (ČÍS_ODDĚLENÍ, NÁZEV ODDĚLENÍ, OBOR, OS_ČÍS_ŠÉFA) Dotaz: Najděte jména a osobní čísla všech zaměstnanců, kteří pracují na stejném oddělení, jako vedoucí s osobním číslem 5822 a nemají plat vyšší než 10 000 Kč. Formulace dotazu: Q3 := (ZAMĚST ZAMĚST.ČÍS_ODDĚLENÍ = ODDĚLENÍ.ČÍS_ODDĚLENÍ (ODDĚLENÍ (OS_ČÍS_ŠÉFA = 5822)) - ZAMĚST (PLAT > 10 000) ZAMĚST.ČÍS_ODDĚLENÍ = ODDĚLENÍ.ČÍS_ODDĚLENÍ (ODDĚLENÍ (OS_ČÍS_ŠÉFA = 5822))) OS_ČÍSLO, JMÉNO
94
K tomuto dotazu sestrojíme strom:
[OS_ČÍSLO, JMÉNO]
[ ČÍS_ODDĚLENÍ = ČÍS_ODDĚLENÍ]
ZAMĚST
[ ČÍS_ODDĚLENÍ = ČÍS_ODDĚLENÍ]
( OS_ČÍS_ŠÉFA = 5822 )
( PLAT > 10.000 )
( OS_ČÍS_ŠÉFA = 5822 )
ODDĚLENÍ
ZAMĚST
ODDĚLENÍ
Oba podstromy jsou si podobné. Liší se pouze v selekci pro plat zaměstnance. Transformujeme pravý podstrom:
( PLAT > 10 000 )
[ ČÍS_ODDĚLENÍ = ČÍS_ODDĚLENÍ ]
ZAMĚST
( OS_ČÍSLO_ŠÉFA = 5822 ) ODDĚLENÍ 95
Po eliminaci společného podvýrazu: [ OS ČÍSLO, JMÉNO
odčítání ( PLAT > 10 000)
[ ČÍS ODDĚLENÍ = ČÍS ODDĚLENÍ ]
ZAMĚST
( OS ČÍS ŠÉFA = 5822 ) ODDĚLENÍ
Pozn. Od všech odečítáme ty, kteří mají plat > 10 000 Kč. Situace 3: Kromě odstranění přebytečných poddotazů je třeba odstranit i podvýrazy, jejichž vyhodnocení do konečného výsledku nic nepřinese. Tyto podvýrazy lze rozpoznat pomocí následujících pravidel: 1. R * R = R 2. R ∪ R = R 3. R – R = ∅ 4. R * R(Φ) = R(Φ) 5. R ∪ R(Φ) = R 6. R - R(Φ) = R(non Φ)
96
7. R(Φ1) * R(Φ2) = R(Φ1 and Φ2) 8. R(Φ1) ∪ R(Φ2) = R(Φ1 or Φ2) 9. R(Φ1) - R(Φ2) = R(Φ1 and non Φ2)
Příklad 4: Na dotaz Q3 použijte zjednodušující pravidlo č. 6. Podmínka selekce bude (PLAT > 10 000) jejíž negace je (PLAT 10 000). [ OS_ČÍSLO, JMÉNO ]
( PLAT ≤ 10 000 )
[ ČÍS_ODDĚLENÍ = ČÍS_ODDĚLENÍ ]
ZAMĚST
( OS_ČÍS_ŠÉFA = 5822 )
ODDĚLENÍ
Situace 4: Nejčastější využití paralelního zpracování dotazů se uplatňuje na operaci spojení. Realizace operace spojení relací totiž představuje krizový faktor z hlediska celého výkonu SŘBD.
Pojmy k zapamatování: Dotaz nad globální relací Dotaz nad dílčí relací Společný výraz dotazu Vyhodnocovací strom dotazu Pravidla pro rozpoznání společné části výrazu
97
Kontrolní otázky: 1. Které situace zahrnuje optimalizace vyhodnocování dotazu? 2. Na příkladu uveďte sestrojení stromu pro vyhodnocení dotazu. 3. Jaká znáte pravidla pro rozpoznání společné části dotazu?
6.3 METODY VÝPOČTU SPOJENÍ Cíl: Čtenář po prostudování této kapitoly bude umět vyjmenovat metody výpočtu operace spojení včetně jejich výhod a nevýhod. Bude umět popsat algoritmy jednotlivých metod. Klíčová slova: Vnořená smyčka, třídění a slévání, polospojení, hašování, Grace algoritmus. A) Spojení vytvářené vnořenou smyčkou(vnořený cyklus) Pomocí vnějšího cyklu se sekvenčně prohledávají n-tice relace vnější, pomocí vnitřního cyklu se k odpovídající vnější¨n-tici vyšetřují všechny spojitelné n-tice vnitřní relace. V případě distribuované databáze je tato metoda nevhodná, protože je značně náročná na komunikaci. V případě, že nelze použít jiný způsob spojení, přenese se menší relace na uzel větší relace a ke spojení relací dojde na jednom uzlu. B) Spojení vytvářené tříděním a sléváním Může být použito, jestliže obě zúčastněné relace mají vlastní indexy pro atributy, přes které se spojuje. Oba indexy jsou paralelně prohledávány a n-tice porovnávány, aby se nalezly všechny ty, které splňují podmínku spojení. Není třeba rozlišovat vnitřní a vnější relaci.
98
Příklad: uzel U1 R1
uzel U2
A1
A2
1
R2
B1
B2
B3
9
1
5
0
2
7
1
6
9
3
5
2
2
3
4
3
5
1
1
5
6
7
2
0
5
9
6
8
6
7
1
9
2
6
8
0
9
1
index na B3: 0013669 uzel U3
R:= R1 [ A1 = B3 ] R2
A1
A3
B1
B2
B3
1
9
5
1
1
3
5
2
2
3
9
1
1
6
9
Tato metoda je vhodnější. V případě, nesplňuje-li relace podmínku této metody, je vhodné zvážit, zda je lepší obě relace podle spojovacího atributu setřídit a pak použít s p o j e n í s l é v á n í m nebo aplikovat s p o j e n í v n o ř e n o u s m y č k o u na nesetříděné relace. C) Metoda polospojení Tato metoda pomáhá redukovat náklady na komunikaci. Nechť R1(A) je relace na uzlu U1 a R2(B) relace na uzlu U2. Výsledek p ř i r o z e n é h o s p o j e n í R : = R 1 * R 2 má být uložen na uzlu U1. K r o k 1 : Na uzlu U1 bude spočtena r e l a c e R 1 1 : = R [ A 1 ] a poslána na uzel U2. K r o k 2 : Na uzlu U2 bude vypočítáno p o l o s p o j e n í R 2 1 : = R 2 * R 1 1 a R21 se pošle na uzel U1. K r o k 3 : Na uzlu U1 se vypočte R : = R 1 * R 2 1 . Výsledek je ekvivalentní R . = R 1 * R 2 .
99
Příklad: Uzel U1 R11:= R1[A1]
A1 1 2 3 4 5 7 8 9 uzel U2
R21:= R2[B3 = A1]R11
B1
B2
B3
1
6
9
2
2
3
5
1
1
uzel U1 R:= R1[A1 = B3]R21
A1
A2
B1
B2
B3
1
9
5
1
1
3
5
2
2
3
9
1
1
6
9
D) Spojení vytvářené pomocí hašování Je modifikací polospojení, kdy místo hodnot atributů se přenášejí mezi uzly tzv. h a š o v a n é f i l t r y . Filtry jsou kratší než hodnoty atributů. Vytvářejí se aplikováním h a š o v a c í f u n k c e f na hodnotu atributu α. H a š o v a n ý f i l t r pro celou relaci označujeme HF ( R • A ), h a š o v a n ý f i l t r n a r e l a c i R s a t r i b u t y A a vypočteme jej pomocí o p e r a c e O R z hašovaných filtrů hodnot atributů.
100
Spojení klasickým hašováním je nejjednodušší variantou spojení pomocí hašování. Ve vnitřní paměti se alokuje prostor, do kterého lze hašovat celou relaci R. Po zahašování relace R do vnitřní paměti se sekvenčně čte relace S, hašuje se hodnota S•A pro každý prvek z S. Je-li splněna podmínka spojení, generuje se odpovídající n-tice výsledku. Spojení s rozdělováním relací V obecném případě, kdy se relace R ( ani S ) nevejde do vnitřní paměti, rozdělují se relace R a S na vhodné disjunktní podmnožiny ( kapsy ) a spojují se pouze korespondující podmnožiny. Budeme předpokládat, že kapsy nepřetékají. 2 fáze algoritmu: • rozdělení R a S • části R se hašují do vnitřní paměti, čtou se n-tice z odpovídající části S, hašováním hodnoty S•A se najdou odpovědi a generují se spojené n-tice do výsledku GRACE algoritmus s ukládáním rozdělených relací Algoritmus probíhá v následujících krocích: 1. Zvol hašovací funkci h tak, že relaci R lze rozdělit do m částí přibližně stejné délky 2. Čti relaci R a hašuj ji do vyrovnávacích pamětí. Kdykoliv se buffer naplní, zapiš ho na disk. Po přečtení celé relace R zapiš všechny buffery na disk. 3. Čti relaci S a zpracuj ji stejně jako relaci R. 4. Čti Si a hašuj ji do paměti. 5. Čti n-tice z Ri a hašuj je na hodnotě atributu A. Existuje-li odpovídající n-tice relace Si,
generuj výsledek.
101
Příklad: Pro jednoduchost, relace R i S obsahují pouze atribut A. Jako hašovací funkce je zvolena K mod 3, kde K je z dom(A). S
A
R
A
4
6
6
10
1
15
9
7
19
13
14
18
17
16
11
17
18
K mod 3
R0
S0
R1
S1
R2
S2
6
6
10
4
17
14
15
9
7
1
17
18
18
13
19
11
16 R*S 6 18 17
102
Pojmy k zapamatování: Vnořená smyčka Třídění a slévání Polospojení Hašování Grace algoritmus
Kontrolní otázky: 1. Jaké znáte metody výpočtu spojení? 2. Jak probíhá metoda polospojení? 3. Srovnejte jednotlivé metody výpočtu spojení a uveďte situace, ve kterých je vhodné je použít.
103
7 MODUL 7 7.1 OBJEKTOVĚ ORIENTOVANÁ ANALÝZA A NÁVRH Cíl: Cílem je seznámit ze základními bariérami relačních databázových systémů a možností řešení těchto bariér. Po prostudování této kapitoly bude čtenář schopen vyjmenovat í nedostatky a bariéry relačního datového modelu a bude schopen popsat základní principy objektového a deduktivního přístupu k databázovému modelování. Klíčová slova: Objektový přístup, perzistence, identifikace, verze objektu, objektová technologie, objektový model, funkční model, dynamický model objektové aplikace
7.1.1. Úvod K vývoji informačních systémů v současné době existují dva hlavní přístupy - strukturovaný a objektově orientovaný. Hlavním účelem strukturovaného přístupu je strukturovat postup při tvorbě informačního systému, zatímco hlavním účelem objektově orientovaného přístupu je vytvářet opakovaně využitelné komponenty. Objektový přístup vychází z přirozeného způsobu lidského myšlení, strukturovaný přístup je konstrukcí lidského intelektu. Dle názoru mnoha odborníků v této problematice budou obě metodologie, jak strukturovaná tak objektová, ještě velmi dlouho a úspěšně žít a fungovat vedle sebe. Strukturovaná analýza se dělí na: •
Tvorbu datového modelu
•
Tvorbu funkčního modelu
•
Tvorbu modelu uživatelského rozhraní
Strukturovaná analýza vede k využití relačních SŘBD. Relační modely ovšem v některých případech (některých typech aplikačních domén) vykazují nedostatky, jejichž částečný výčet je uveden níže.
7.1.2 Nedostatky relačních SŘBD •
Malá modelovací schopnost pro objekty reálného světa. Složitá realita je transformována na jednoduché databázové relace, což v některých případech až nepřípustně zjednodušuje.
•
Složité objekty vedou k velkému množství tabulek, špatnou orientaci v něm.
•
Oddělení vlastností objektů od jejich chování v tom smyslu, že v datovém modelu je věnována pozornost pouze vlastnostech, zatímco chování objektů je řešeno na úrovni funkčního modelu. Jinými slovy v relačním datovém modelu není místo pro definování chování jednotlivých objektů, resp. entit.
•
Nedostatečná úroveň abstrakce dat, relační SŘBD poskytuje pouze základní datové typy.
104
což způsobuje složitost modelu a
Objektový přístup neodděluje data a funkce. Data a funkce chápe jako vlastnosti jednotlivých objektů.
7.1.3 Objektově orientovaná metodika Pro seznámení s objektově orientovanou metodikou lze vybrat hned z několika metodologií, které byly na tomto poli vyvinuty. Všechny metodiky vycházejí z modelování reality pomocí jistých nástrojů. V průběhu strukturované analýzy a návrhu se vytváří model datový, funkční a model uživatelského rozhraní. Objektový přístup neodděluje data a funkce. Chápe data a funkce jako vlastnosti objektů. Pro vysvětlení objektově orientovaného přístupu k modelování využijeme metodiku "Object Modelling Technology - OMT", jejíž autorem je pan James Rumbaugh. Metodologie OMT vychází ze tří základních modelů - model objektů, dynamický model a funkční model. Model objektů popisuje statické struktury - data systému, vzájemné vztahy mezi třídami objektů, jejich atributy a operace. Dynamický model je modelem chování systému v čase, zachycuje tok řídících informací. Tento model zahrnuje i diagram přechodu stavů pro každou třídu. Funkční model popisuje transformace dat, ke kterým v popisovaném systému dochází. Je obdobou diagramu datových toků používaného v metodikách strukturovaného návrhu.
7.1.4 Další objektově orientované metodologie Následuje stručný popis některých dalších objektově orientovaných metodologií Booch metodologie určuje následující kroky vývoje modelu: •
identifikace objektů a jejich atributů
•
identifikace operací každého objektu
•
identifikace viditelnosti atributů a operací každého objektu pro ostatní objekty
•
vybudování rozhraní
•
implementace objektů
Identifikované a definované objekty jsou základem pro moduly systému. Důraz je kladen na vytvoření čtyř diagramů. Hardware Diagram (zobrazuje propojení definovaných procesů, zařízení, sítí...), Class Structure Diagram (zobrazuje vazby mezi třídami a jejich objekty), Object Diagram (zobrazuje viditelnost objektu ve vztahu k druhým objektům) a Architecture Diagram (zobrazuje fyzický návrh systému). Metodologie je dobře použitelná pro systémy reálného času. Jacobson metodologie vychází z modelování jednání - Use Case Driven.V etapě analýzy jsou rozpracovány dva modely - model požadavků a analytický model. Model požadavků je tvořen skupinou případů jednání, modelem zkoumané oblasti a popisem rozhraní systému. Analytický model pokrývá dělení systému do logické struktury objektů, rozlišených na objekty rozhraní, objekty modelu a řídící objekty. Objekty jsou identifikované z jednání, která jsou analyzována a dekomponována. Některé jsou identifikovány atributy objektů. Ve fázi návrhu je vytvořen blokový model skupinou blokových diagramů, ve kterých je taky zachycena komunikace mezi bloky. Blokový model je následně implementován. Metodologie je silnou podporou v řešení úvodních kroků specifikace systému.
105
Martin/Odell metodologie zahrnuje etapy Information Strategy Planning - řešení cílů, kritických faktorů, Business Area Analysis - tvorba OO modelů jednotlivých aplikačních oblastí, System Design - řešení modelu systému, Construction - implementace. Etapa Business Area Analysis je členěna do následujících fází: •
analýza struktuty objektů představuje celkový model struktury objektových typů pokrývajících jednotlivé diagramy jako objektové typy a jejich asociace, hierarchie objektových typů, nadtypy a podtypy, kompozice složených objektů.
•
analýza chování objektů představuje celkový model Activity Schema Model, který se skládá z Object Flow Diagrams, Operation Diagrams, Event Diagrams a State Transition Diagrams. Model řeší v jakých stavech se objekt může nacházet, jaké přechody stavů nastávají, jaké události nastávají, které operace následují, jaká součinnost nastává mezi objekty, jaké podmínky spuštění vyvolávají operaci jako reakci na událost, jak jsou operace reprezentovány metodami.
Wirfs/Brock metodologie Etapa analýzy, ve které se kompletuje a specifikuje návrh systému, probíhá v těchto krocích: •
zkonstruování grafů hierarchií, které zobrazují vazby dědičnosti mezi třídami
•
určení, které třídy jsou abstraktní a které konkrétní
•
nakreslení diagramů pro zobrazení odpovědností sdílených třídami
•
výstavba a ověření detailní hierarchie tříd
•
zkonstruování kontraktů definovaných při každé třídě
•
nakreslení kompletního grafu spoluprací pro systém
•
určení možných subsystémů v návrhu, které představuje vyhledání častých a složených spoluprací
•
zjednodušení spolupráce mezi subsystémy a v subsystémech
Metodologie Coada a Yourdona zavádí v objektovém modelu pojem vrstev. Vrstva subjektů rozděluje všechny objekty modelovaného IS do skupin. Vazby uvnitř subjektu by měly být těsnější než vazby mimo subjekt. Model dělíme na subjekty, jestliže je velký a tudíž chceme práci na modelu rozdělit mezi více lidí. Systém vrstev v modelu je charakterizován vrstvou tříd a objektů, vrstvou struktur (strukturami se rozumí vztahy "generalizace - specializace" a "celek - část"), vrstvou atributů, která charakterizuje atributy, tj.data zapouzdřená v jednotlivých třídách a objektech a vrstvou služeb určující služby, které každý objekt (třída) poskytuje a spojení zprávami, jimiž se ostatní objekty těchto služeb dožadují. OOM podle Coada a Yourdona taky dává návod, jak nalézat třídy a objekty, jak definovat služby, jak definovat atributy, jak definovat struktury, jak odhalovat subjekty. Zavedením vrstev do objektového modelu lze snadněji systém analyzovat. Dalším krokem je sestavení samotného objektového modelu. Lze vysledovat pět kroků k sestavení objektového modelu cestou tzv. transakční analýzy: •
sepíšeme seznamy vnějších událostí, vstupů, výstupů
•
z událostí, vstupů a výstupů vytvoříme popis tzv. transakcí
•
inventarizujeme objekty a jejich atributy, služby, struktury, sjednotíme identifikátory 106
•
nakreslíme objektový model pro každou transakci
•
objektové modely jednotlivých transakcí spojíme do celkového modelu
•
pokusíme se do modelu doplnit další strukturní vazby
7.1.5 Požadavky, kladené na OODBS 1. Perzistence Základní vlastností objektů v objektovém datovém modelu je, že objekty musí existovat i potom, co zanikl program, který je vytvořil. Obecně rozlišujeme dva typy objektů: a) volativní (objekty v OP) b) perzistentní: každý objekt je identifikován ukazatelem (object Identifier). Perzistence je vlastnost instance, nikoli třídy. Objekty dané třídy mohou existovat jak v perzistentních, tak i ve volativních instancích. S perzistentními a volativními objekty se musí pracovat stejným způsobem. Identifikace objektu musí být: a) Nezávislá na místě (souvislost s tzv. fragmentováním a replikací). b) Nezávislá na obsahu, tzn. že identita objektu musí být zachována i při změnách hodnot objektu. c) Nezávislá na struktuře, tzn. že identita objektu musí být zachována i při změně jeho struktury. 2. Verze objektu Databáze by měla uchovávat historii vývoje objektu v čase. 3. Podmínky a akce Systém musí umět reagovat na splnění určitých podmínek vyvoláním příslušných metod objektu. 4. Omezení Pro udržení konzistence databáze je nutné mít možnost omezit přístup k některým objektům.
7.1.6 Objektově orientované SŘBD Existují aplikace, kde použití relačních SŘBD je nevhodné nebo nemožné. Důvodem je především příliš složitá modelovaná realita, jejíž převedení na relační datový model by způsobilo nepřijatelné zjednodušení. Součástí tohoto problému je existence multimediálních, složitě strukturovaných dat. V takovém případě je vhodnější využít řešení pomocí OOSŘBD. Objektová technologie a) Databázová technologie. b) Objektově orientované programování. c) Objektově orientovaná analýza a návrh. d) Modelování procesů. e) Implementace a testování. Aplikace vhodné pro OOSŘBD a) Geografické informační systémy. b) Návrh logických obvodů pomocí počítače. c) Monitorování a řízení procesů v reálném čase. 107
d) Řízení dat pro správu telefonní sítě. e)atd. Obecnější třídy aplikací a) Databáze na podporu návrhu (CAD/CAM/CASE). b) Multimediální databáze. c) Báze znalostí.
7.1.7 Hlavní přínosy objektové technologie 1. Přímý vztah ke konceptuálnímu modelování (objekty reálného světa lze reprezentovat jako složité objekty). 2. Část funkcí, specifikovaných dříve v aplikačních programech, se přenáší do definice objektů (zapouzdření). Programy se stávají součástí databáze. 3. OOSŘBD mohou pracovat s bohatě strukturovanými objekty, vhodnými pro modelování nejkomplikovanější reality. 7.1.8 Kriteria kladená na OOSŘBD 1. Zajištění perzistence objektů na vnějších pamětech. 2. Souběžný přístup více uživatelů. 3. Spolehlivost dat. 4. Možnost ad noc dotazů. 5. Existence identity objektů. 6. Existence typů nebo tříd. 7. Zapouzdření . 8. Polymorfismus. 9. Dědění. 10. Složité objekty. 11. Rozšiřitelnost. 12. Výpočetní úplnost.
7.1.9 Tři základní modely objektové metodologie Následující tři typy modelů v objektové metodologii jsou pouze vyjmenována. Blíže se s nimi čtenář seznámí v následující kapitole. Model objektů •
Popisuje statické struktury
•
Jednotlivé třídy objektů
•
Vzájemné vztahy mezi třídami objektů
•
Atributy a operace tříd 108
Dynamický model Je modelem chování systému v čase, zachycuje tok řídících informací. Funkční model Popisuje transformace dat, modely jsou vzájemně propojeny.
Pojmy k zapamatování: Objektový přístup Perzistence Identifikace Verze objektu Objektová technologie Objektový model Funkční model Dynamický model Objektové aplikace
Kontrolní otázky: 1. Co jsou hlavní nedostatky relačních SŘBD? 2. Vyjmenujte hlavní požadavky, kladené na objektově orientované systémy řízení báze dat. 3. Jaké jsou dva základní směry vývoje OOSŘBD? 4. Jaké znáte modely objektové metodologie.
7.2 MODEL OBJEKTŮ Cíl: Cílem této krátké kapitoly je seznámit čtenáře se základními pojmy objektového modelu dat. Jedná se o zavedení pojmového aparátu. Čtenář by si měl osvojit pojmový aparát, uvedený v této kapitole. Klíčová slova: Objekt, třída, atribut, operace, metoda, polymorfismus, dědičnost, zapouzdření, spojení, vztah, agregace, generalizace.
109
Průvodce studiem V této kapitole si pořádně prostudujte pojmový aparát a pokud možno se definice naučte zpaměti. Definice jsou do značné míry zjednodušení a to proto, abyste nemuseli příliš zatěžovat paměť.
7.2.1 Základní charakteristiky Objekt je cokoliv, co má v kontextu aplikace význam, u čeho má smysl popisovat vlastnosti. Objekt má svou identitu, lze jej odlišit od jiných objektů. Objekt je instancí (prvkem) třídy. Třída objektů popisuje skupinu objektů podobných vlastností (atributů), společného chování (operací) a shodných vztahů k jiným objektům a stejného významu. Atribut objektu je datový údaj spojený s objektem, např. Jméno, Věk, Váha jsou atributy objektu Člověk. Na rozdíl od objektu atribut, jako datový údaj, nemá svou identitu. Operace je akce nebo transformace prováděná objektem nebo na objekt aplikovatelná. Příklad: Otevři, Zavři jsou operace objektu Ventil. Metoda je implementací operace. Polymorfismus je pojem, který označuje vlastnost, kterou táž operace může být v různých objektech realizována různým způsobem. Mezi třídami objektů mohou být hierarchické vztahy. Např. podtřídami třídy Soubor mohou být třídy pro jednotlivé formáty souborů ASCII, PCX, TIFF, DBF atd. Dědičnost je vlastnost objektově orientovaných systémů umožňující sdílení atributů a metod třídami v rámci jejich hierarchie. Příklad: Všechny podtřídy třídy Soubor mohou sdílet atributy Jméno, Čas_poslední_změny, Délka a metodu Zobraz_základní_údaje. Metoda Print je pak realizována odlišně pro každou podtřídu. Encapsulation - skrývání informace je princip spočívající v tom, že se striktně oddělují vnější projevy objektu od jeho vnitřní struktury. Objekt se navenek projevuje jen operacemi. Je-li třeba měnit hodnoty atributů objektu, nelze je prostě přepsat, je třeba vyvolat operaci objektu, která požadované změny provede. Spojení je fyzický nebo konceptuální spoj mezi instancemi objektů. Např. pan Novák pracuje_pro firmu Microsoft. Spojení je instance vztahu. Vztah popisuje množinu spojení se shodnou strukturou a významem. Kvalita vztahu je dána jeho multiplicitou a jeho atributy. Multiplicita vypovídá o tom, kolik instancí jedné třídy může být ve vztahu ke každé z instancí druhé třídy. Vztah Pracuje_pro je vztah mezi objekty Člověk a Firma. Jedná se o vztah typu N:M, protože člověk může pracovat pro více firem a firma může zadávat práci více lidem. Přitom může existovat člověk, který nepracuje pro žádnou firmu, tak firma, která nezadává práci žádnému člověku. Vztah může mít atribut Výše_odměny. Agregace je vztah vyjadřující, že objekt je částí jiného objektu. Agregace je vztah tranzitivní a asymetrický. Generalizace je vztah mezi třídou a jejími podtřídami. Pomocí generalizace zachycujeme hierarchii tříd.
7.2.1 Základní pojmy OBJEKT
Je cokoli, u čeho má smysl popisovat vlastnosti. Objekt má svou identitu, lze jej odlišit od jiných objektů. Objekt je instancí (prvkem) třídy. TŘÍDA
Popisuje skupinu objektů obdobných vlastností (atributu), společného chování (operací) a shodných vztahů k jiným objektům. ATRIBUT
Je datový údaj spojený s objektem např. věk, váha, barva, výkon, atd. Na rozdíl od objektu, atribut nemá svou identitu.
110
OPERACE
Je akce nebo transformace prováděná objektem nebo na objekt aplikovatelná. Např. Otevři, Zavři jsou operace objektu Ventil. METODA
Je implementací operace.
Příklad: Příklad: Mějme objekt Soubor a operaci Tisk, která způsobí vytištění informace uložené v souboru na tiskárně. Operace Tisk musí být implementována různě pro odlišné typy souborů. S obrázkem uloženým jako komprimovaná bitová mapa operace Tisk zacházejí jinak než s ASCII souborem. Konkrétní provedení operace Tisk je v obou případech realizováno rozdílnými úseky kódu programu. POLYMORFISMUS
Je vlastnost, kdy tatáž operace muže být v různých objektech realizována různým způsobem. DĚDIČNOST
Umožňuje sdílení atributů a metod mezi třídami v rámci jejich hierarchie. ZAPOUZDŘENÍ (ENCAPSULATION) Objekty dané třídy mohou být zpřístupněny pouze přes dané rozhraní. Hodnoty atributů objektů nejsou obecně přístupné, uživatel smí používat jen nabídnuté operace. Objekt se projevuje jen operacemi. Je-li třeba měnit hodnoty atributu objektu, je třeba vyvolat operaci objektu. SPOJENÍ
Je spoj mezi instancemi objektů. Spojení je definováno jako n-tice, uspořádaný seznam instancí objektu. Např. pan Novák pracuje_ pro firmu KOMIX. VZTAH
Popisuje množinu spojení se shodnou strukturou a významem. Kvalita vztahu se popisuje obdobně jako v E - R diagramech.
AGREGACE
Je vztah vyjadřující, že jeden objekt je částí jiného objektu. Agregace je vztah tranzitivní a asymetrický. Je-li objekt 1 částí objektu 2 a ten částí objektu 3, pak je objekt 1 částí objektu 3 (tranzitivita). Je-li objekt 1 částí objektu 2, pak objekt 2 není částí objektu 1 (asymetrie). GENERALIZACE
Je vztah mezi třídou a jejími podtřídami. Pomocí generalizace se zachycuje hierarchie tříd.
Pojmy k zapamatování: Objekt Třída
111
Atribut Operace Metoda Polymorfismus Dědičnost Zapouzdření Spojení Vztah Agregace Generalizace
7.3 DYNAMICKÝ A FUNKČNÍ MODEL Cíl: Cílem této krátké kapitoly je seznámit čtenáře s základními pojmy dynamického a funkčního modelu dat stejně jako s jejich základní filosofií. V této kapitole se především jedná o zavedení pojmového aparátu. Čtenář by si měl osvojit pojmový aparát, uvedený v této kapitole. Klíčová slova: Událost, stav, stavový diagram, proces, aktor, datastor, řídící tok
7.3.1 Dynamický model Dynamický model obsahuje prostředky pro popis toku řízení, interakcí mezi objekty a pro sekvenci operací v systému paralelně pracujících objektů. Základní pojmy, se kterými dynamický model pracuje jsou události a stavy. Událost reprezentuje vnější stimul a stav objektu je abstrakcí zachycující hodnoty všech vnitřních proměnných a jeho vztahů. Stav objektu se může změnit jen příchodem nějaké události. Události mohou být ve vzájemném vztahu - mohou být na sobě závislé nebo mohou nastávat na sobě nezávisle. Událost je jednosměrný přenos informace mezi dvěma objekty. Odezva objektu je tedy taky událostí. Odezva objektu na událost závisí jak na události samé, tak na stavu objektu. Příklad: Zašle-li dodavatel odběrateli fakturu na zboží, může být odezvou odběratele provedení platby (je-li ve sravu "solventní") nebo zaslání faktury dodavatel žádnou odezvu nevyvolá (odběratel je ve stavu "nesolventní"). K provedení platby dojde až po přechodu odběratele do stavu "solventní". I události můžeme rozdělit do jistých tříd, které jsme schopni popsat pomocí atributů. Například odjezd vlaku (Typ_vlaku, Čas_odjezdu, Odkud, Směr). Dynamické chování popisujeme stavovým diagramem. Stavový diagram se obvykle znázorňuje orientovaným grafem, jehož uzly odpovídají stavům a hrany zachycují přechody mezi nimi. Jeden ze stavů je označen jako inicializační. Diagram může mít také jeden nebo několik koncových stavů. Hrany popisujeme událostmi, které přechod vyvolají. Chceme-li vyjádřit, že jistá událost vyvolá přechod ze stavu do stavu jen za určitých, omezujících podmínek, pak tuto podmínku zapíšeme do hranatých závorek za název události. Stav systému je dán stavem všech jeho objektů.
112
7.3.2 Základní pojmy UDÁLOST
Reprezentuje vnější stimul. Události mohou být na sobě závislé nebo mohou nastávat nezávisle. Událost je jednosměrný přenos informace mezi objekty. Odezva objektu je taky událost, události můžeme popsat pomocí atributu. Např. odjezd_vlaku (typ_vlaku, cas_odjezdu, odkud, smer). STAV
Je abstrakcí, zachycující hodnoty všech vnitřních proměnných objektů, stav objektu se může změnit jen příchodem nějaké události. Dynamické chování se popisuje stavovým diagramem. Stavový diagram je orientovaný graf, jehož uzly odpovídají stavům a hrany popisují události, které vyvolají přechod ze stavu do stavu.
7.3.3 Funkční model Funkční model zachycuje, jakými transformacemi prochází vstupní hodnoty v procesu zpracování a jak se z nich odvozují výstupy. Funkční model je budován pomocí diagramů datových toků (DFD). DFD je graf zachycující tok dat systémem od jejich vstupu přes interní transformace prováděné procesy až po výstupy. Data mohou být interně ukládána do tzv. datastorů. DFD nezachycuje časové změny ani nezachycuje příslušnost dat k objektům, to je zachyceno v objektovém modelu. Procesy provádějí transformaci dat. Proces má jeden nebo více vstupů - vstupních datových toků. Komplikované procesy lze dekomponovat na jednodušší. Tato dekompozice se zachycuje v hierarchii DFD. Procesy odpovídají operacím objektů. Bývají implementovány jako metody objektů. Aktor je aktivní prvek, který produkuje nebo konzumuje data. Místo termínu aktor se rovněž používá termín terminátor, protože buď z něho datový tok vychází nebo v něm končí. Datastor symbolizuje pasivní objekt, do něhož lze data uložit pro pozdější použití. Data uložená v datastoru mohou být zpracovávána v libovolném pořadí. Na pořadí ukládání nezáleží. Proces může data uložená v datastoru modifikovat, nebo je z něho vymazat. Řídící tok je rozšíření symboliky tradičních DFD. Znázorňuje logický signál, jehož hodnota ovlivňuje zpracování dat procesem, do něhož vstupuje. Dynamický a funkční model užívá již známé techniky zasazené do jiného kontextu.
7.3.4 Základní pojmy PROCESY
Provádějí transformaci dat a bývají implementovány jako metody objektu. AKTOR
Aktivní objekt, který produkuje nebo konzumuje data. Někdy se označuje jako TERMINÁTOR. DATASTOR
Pasivní objekt, do nějž se dají data uložit pro pozdější použití. ŘÍDÍCÍ TOK
Znázorňuje logický signál, jehož hodnota ovlivňuje zpracování dat procesem.
Pojmy k zapamatování: Událost
113
Stav Stavový diagram Proces Aktor Datastor Řídící tok
7.4 DEDUKTIVNÍ PRAVIDLA PŘI ANALÝZE A NÁVRHU IS Cíl: Cílem této kapitoly je seznámit čtenáře se základy deduktivních pravidel, na kterých jsou založeny deduktivní databáze. Pravidla jsou vysvětlena jak na relačním modelu, tak na modelu objektovém. Čtenář by měl po prostudování této kapitoly znát, jak vypadá deduktivní pravidlo, k čemu je možno jej při analýze a návrhu databází použít a v čem je jeho přínos. Měl by vědět, co je to stratifikace, bezpečnost pravidel. dále by měl vědět, jakým způsobem je možno pomocí deduktivních pravidel odvozovat databázové koncepty a definovat integritní omezení. Klíčová slova: Deduktivní pravidlo, stratifikace, bezpečnost, odvozené koncepty, relační pojetí faktů, objektové pojetí faktů, vestavěná IO, generická IO.
7.4.1 Úvod do deduktivních pravidel Deduktivní pravidlo je výraz ve tvaru:
kde hlava je atomická formule a tělo je libovolná formule. Každá proměnná v hlavě pravidla se musí vyskytovat rovněž v těle pravidla. Existují čtyři typy deduktivních pravidel dle toho, co je těmito pravidly definováno. Jedná se o pravidla definující třídy, pravidla definující pohledy, pravidla definující atributy a pravidla definující integritní omezení. K definování téhož konceptu je možno použít několik pravidel.
Příklad: Pro definování platu je možno použít následujících deduktivních pravidel:
114
7.4.2 Stratifikace Deduktivní pravidla mohou na sobě navzájem záviset různým způsobem, buď hierarchicky nebo rekurzivně. Tato závislost může být vyjádřena tvrzením, že koncepty odvoditelné na vyšší úrovni mohou výt vyhodnoceny pouze pokud koncepty na nižší úrovni, na nichž jsou tyto koncepty vyšší úrovně závislé, již byly dříve vyhodnoceny. Každá úroveň je označována “strata” a celkové vytváření úrovní se nazývá stratifikace množiny pravidel. Tento proces musí být pečlivě kontrolován, pokud se v pravidlech objeví negace. Negativní literály v deklarativních výrazech nemohou produkovat žádná nová tvrzení, ale mohou pouze potvrdit nebo vyvrátit tvrzení vytvořená v průběhu vyhodnocení jejich pozitivních výskytů se stejnými proměnnými. Před vyhodnocením negace je třeba znát všechna pozitivní fakta, ze kterých může být vyjádřen závěr ve formě negace. Máme-li např. definována tvrzení kdo je koho potomkem, pak pouze jejich plný výčet umožňuje potvrdit či vyvrátit tvrzení kdo koho potomkem není. Stratifikace nemůže být dosaženo, pokud existuje odvozený koncept, který závisí jak rekurzivně, tak negativně na sobě samém. Množina pravidel obsahující takovýto rekurzivní cyklus, který zahrnuje negace, se nazývá nestratifikovatelná.
Příklad:
Obě pravidla je třeba umístit na stejnou úroveň, protože jsou rekurzivně závislá. Zároveň by však měla být umístěna do různých úrovní, protože jeden na druhém negativně závisí. Taková situace je označována jako logický paradox a musí jí být zabráněno. Další paradoxní situace může nastat, pokud k odvození konceptu je třeba vypočítat agregační funkci, jejímž elementem je odvozovaný koncept. Tuto situaci uveďme na příkladu:
115
Příklad:
Zaměstnanec X má stejný příjem jako zaměstnanec Y, jestliže X má plat rovný aritmetickému průměru platů zaměstnanců se stejným příjmem jako Y.Takovéto rekurzivní cykly zahrnující agregační funkce musí být rovněž vyloučeny. Stratifikovaná množina pravidel je pak množina pravidel, která vylučuje negační a agregační paradox.
7.4.3 Všeobecné principy dobře formovaných deduktivních pravidel Pravidla musí splňovat několik syntaktických a sémantických požadavků, aby mohla být vyhodnocena. Tyto požadavky lze shrnout do následujících bodů: •
Pravidla musí být v omezeném rozsahu, tzn. všechny jejich proměnné musí být omezeny vhodnými formulemi.
•
Pravidla musí být bezpečná, tzn. všechny proměnné v hlavě pravidla se musí objevit minimálně v jedné pozitivní formuli v těle pravidla.
•
Pravidla s negativními formulemi musí být stratifikována, tzn. nesmí být rekurzivně použita v těle jiných pravidel tak, aby vytvářela cyklus rekurzivních pravidel, která vyvolávají negativní formuli.
•
Pravidla s termy musí být stratifikována, tzn. že nesmí být rekurzivně použity v těle ostatních pravidel tak, aby tvořila cyklus rekurzivních pravidel, které volají množinu termů.
7.4.4 Využití deduktivních pravidel pro odvozování dat Deduktivní pravidla mohou být rozdělena na pravidla pro odvozování dat a pravidla pro integritní omezení. Pravidla pro odvozování dat odvozují atributy, pohledy a odvozené třídy. Integritní omezení jsou chápána jako implicitní (fixní formát) nebo jako uživatel definovaná (generic formát). Návrh deduktivních pravidel je iniciován v průběhu analýzy. Během návrh může být objeveno mnoho dalších požadavků. Návrhář může definovat všechna odvozená data, která obohatí znalosti podporované systémem a odhalí všechny zdroje kontrol konzistence, které mohou být formulovány jako integritní omezení. Velkou výhodou deduktivních pravidel je jejich deklarativnost. Deklarativnost umožňuje popis znalostí, které nevyžadují žádné procedurální detaily a tudíž je naprosto nezávislý popis pravidel od jejich implementace. Na druhé straně z toho vyplývají i omezení v nemožnosti vyjádřit procedurální rysy, které jsou někdy zapotřebí. Jsou-li deduktivní pravidla pro odvozování dat transformována do aktivních pravidel, dochází k tzv. materializaci dat. V takovém případě jsou odvozená data extenzionálně uložena v databázi. 116
Jazyky pro definování pravidel (Prolog nebo Datalog) jsou používány v kontextu relačních databází. V případě použití objektově orientovaných databází, objektová reprezentace vede k různým stylům pravidel. Proměnné odkazují na objekty spíše než na hodnoty a přístup k jednotlivých hodnotám atributů se realizuje prostřednictvím tečkové notace.
7.4.5 Příklady implementace v jazyku Chimera Odvozování tříd Využitím deduktivních pravidel lze odvodit další třídy, jejichž populace závisí na hodnotě nějakého atributu definované supertřídy. Populace mohou být odvozeny pouze pro subtřídy pomocí pravidel, která jsou definována v supertřídách.
Příklad:
Tímto způsobem lze odvodit třídu zaměstnanec ze supertřídy osoba, použitím deduktivního pravidla. Jestliže Osoba změní profesi - zaměstnanec, musí být automaticky vyňata z třídy Zaměstnanec. Odvozování pohledů Pohledy jsou chápány jako virtuální objekty, které vzniknou vyhodnocením dotazu a tím usnadňují tvorbu aplikace. K pohledům lze nastavit individuální přístup pro aplikace, což umožňuje vytvářet mechanizmus ochran. Data jsou vybírána z více tříd a k těmto datům je nastaven selektivní přístup.
Příklad:
Odvozování atributů Jednou z důležitých aplikací deduktivních pravidel je výpočet odvozených atributů, tj. takových atributů, jejichž hodnota může být odvozena z hodnot jiných atributů. Návrhář by měl odpovědět 117
na následující otázku: Existují nějaké atributy, jejichž hodnoty mohou být odvozeny? Příklad odvozeného atributu by mohl být následující:
Příklad: Mějme atribut datum narození u třídy Osoba. Z atributu datum narození odvoďte atribut věk. Define object class Osoba Attributes Datum_narození:Date, Věk:integer derived End
Define external formula castToVěk(in D:date, out A:integer) End Define implementation for Osoba Attributes Self.Věk = I := integer(I), castToVěk(Self.Datum_narození, I) End Speciální pozornost je třeba věnovat rekurzívním atributům. Nejjednodušší a nejpoužívanější forma rekurze je tranzitivní uzávěr binárního vztahu. Vztah je modelován tak, že typ atributu objektu odkazuje zpět na tento objekt. Tento typ vztahu bývá nazýván kruhovým vztahem.
Příklad: Mějme následující fragment schématu databáze : Define object class Osoba Attributes Děti: set-of(Osoba), Rodiče:set-of(Osoba), derived, Sourozenci:set-of(Osoba), derived, Předci:set-of(Osoba), derived End 118
Využitím deduktivních pravidel můžeme navrhnout odvozené rekurzivní atributy Rodiče, Sourozenci, Předci a Bratranci např. následujícím způsobem:
Za odvozené atributy budeme považovat atributy označené “derived”, které jsou odvozeny na základě deduktivního pravidla, které může být rekurzivní.
7.4.6 Srovnání relačního a objektového pojetí Relační pojetí faktů Fakta v deduktivně relační technologii jsou reprezentována relacemi, které jsou chápány jako atomické formule (logická reprezentace znalostí).
Příklad: osoba(Jméno, Adresa, Pohlaví) rodič(Rodič, Dítě) partner(Manžel, Manželka) Objektové pojetí faktů Fakta jsou v deduktivně objektové technologie reprezentována jako třídy objektů (rámcová – frame- reprezentace znalostí).
Příklad: Object osoba s atributy jméno:string adresa:string
119
sex:string dítě: set-of osoba partner: osoba Deduktivními pravidly můžeme odvozovat pohledy. Pohledy jsou podobné relacím, ale jejich ntice nejsou uloženy v databázi. Mohou se vypočítat pomocí dotazovacího jazyka nebo deduktivních pravidel. V objektovém pohledu deduktivní pravidla mohou odvozovat pohledy nebo atributy. Pohledy pro relační styl matka(Matka, Dítě) sestra(Jméno, Jméno) předek(Jméno, Jméno) Odvozené atributy pro objektový styl rodič: set-of(osoba) matka:osoba sestra: set-of(osoba) předek:set-of(osoba)
Příklad: Všechny tyto odvozené fakty můžeme vyjádřit pomocí pravidel. V relačním stylu
V objektovém stylu
120
Na tomto příkladu je ukázáno, jak může být deduktivních pravidel použito k vyjádření inverzních vztahů (rodič, dítě). Nejfrekventovanější použití rekurzívních pravidel je pro vyjádření tranzitivního uzávěru binárních vztahů. V uvedeném případě pohled předek definujeme jako tranzitivní uzávěr relace rodič. Tranzitivní uzávěr vyžaduje dvě pravidla, startovací pravidlo (nerekurzivní) - zabezpečující bázi rekurze a rekurzivní pravidlo-zabezpečující indukci. Objektový styl se vyhne zavádění existenčně kvantifikované proměnné Z (v relačním stylu) vyjádřením cesty, která kombinuje atributy rodič a předek (Y.rodič.předek)
7.4.7 Využití deduktivních pravidel pro definování integritních omezení Integritní omezení jsou vyjadřována pomocí deduktivních pravidel, přičemž databázi vyhovuje dané integritní omezení, je-li hodnota pravidla “false”. Databáze není konzistentní, je-li hodnota deduktivního pravidla “true”. Integritní omezení je výraz ve tvaru:
Integritní_omezení_jméno ← formule
Kde formule se skládá z relací resp. tříd Integritní omezení můžeme rozdělit na omezení bezprostřední a omezení s odloženým vyhodnocením. Kontrola omezení s odloženým vyhodnocením je prováděna po commitu transakce, tzn. nejdříve je provedena celá transakce (např. aktualizace dat) a pak je kontrolována integrita dat. U bezprostřední kontroly je kontrola provedena po každé specifické operaci (nazývané řádek transakce). V obou případech, sémantika kontroly omezení je následující. Jestliže po výpočtu příslušného deduktivního pravidla dojde k produkci hodnot do hlavy pravidla, tyto hodnoty jsou chápány jako 121
nepovolená data a transakce je zrušena. Operace prováděné transakcí jsou zrušeny a databáze je uvedena do stavu před započetím transakce.
7.4.7.1 Vestavěná a generická integritní omezení Další možné členění integritních omezení je na IO vestavěná (ve fixním formátu, implicitní, build in) a IO generická. Vestavěná IO Lze rozlišovat následující vestavěná integritní omezení: •
Not Null atributy jsou atributy, které musí být známy, tzn. nesmí nabývat hodnoty Null
•
Primary key je kolekce atributů, které jednoznačně identifikují každou instanci třídy
•
Unikátní atribut je kolekce atributů, jejichž hodnota je unikátní pro každou instanci třídy
•
Kardinalita je integritní omezení, které určuje počet objektů, které mohou být asociovány ve vztahu.
•
Kardinalita může být vyjádřena:
•
o
min, max – minimální, resp. maximální počet objektů vstupujících do vztahu
o
*, nule nebo více objektů vstupuje do vztahu
o
+, jeden nebo více objektů vstupuje do vztahu
Referenční integrita je omezení binárního vztahu v tom smyslu, že jedna třída je označena jako tzv. “odkazující” a druhá jako tzv. “odkazovaná”. Pro odkazovanou třídu to znamená, že nemůže v rámci této třídy existovat objekt, který by nevstupoval do vztahu s objektem třídy odkazující. Standardní způsoby zachování referenční integrity jsou “Restrict” a “Cascade”.
7.4.7.2 Generické integritní omezení Konvenční databázové systémy podporují výše uvedená integritní omezení, která jsou rovněž nazývána integritní omezení ve fixním formátu. Existují i další integritní omezení v tzn. generickém formátu, která závisejí na specifikované aplikační doméně. Tato omezení mohou být podporována v jejich plné obecnosti pouze novými generacemi databázových systémů. Generická integritní omezení mají dva rozměry: •
Statická a dynamická omezení
Statická omezení mohou být vyhodnocena v jednoduchém stavu databáze, tzv. v kontextu objektů a vztahů. Tato omezení dále můžeme rozdělit na omezení bezprostřední a s odloženým vyhodnocením (viz výše). Dynamická omezení srovnávají dva stavy databáze, nazývané inicializační a koncový stav a jsou navrhována pro monitorování změn stavů. Rovněž dynamické omezení můžeme rozdělit na s bezprostřední a odloženým vyhodnocení. •
Rozsah omezení
Omezení definovaná v kontextu specifikovaných tříd jsou nazývána cílená omezení. Jedná se o predikát, který dohlíží na stav individuálních cílových objektů a poskytuje pro každý cílový objekt specifickou pravdivostní hodnotu. Predikát může taky odkazovat na ostatní objekty, které jsou spojeny vztahem s cílovým objektem.
122
Příklad: Zaměstnanec jde do důchodu, pokud má věk větší než 60 let nebo má odpracováno více než 35 let. Všechna ostatní omezení jsou nazývána necílená omezení. Např. Student musí udělat zkoušky Kurzů, které navštěvuje. Generická integritní omezení jsou tvořena ve fázi návrhu, kdy jsou transformována do deduktivních pravidel.
Pojmy k zapamatování: Deduktivní pravidlo Stratifikace Bezpečnost Odvozené koncepty Relační pojetí faktů Objektové pojetí faktů Vestavěná IO Generická IO
Kontrolní otázky: 1. Jaký je tvar deduktivního pravidla a z čeho vychází? 2. K čemu se dají využít deduktivní pravidla? 3. Co musí splňovat deduktivní pravidla, aby byla korektními definicemi odvozených konceptů? 4. Co musí splňovat deduktivní pravidla, aby byla korektními definicemi integritních omezení? 5. Jaká znáte integritní omezení a kdy se spouští jejich vyhodnocení? 6. Jaké koncepty lze odvodit pomocí deduktivních pravidel?
123
7.5 ŘEŠENÉ PŘÍKLADY DEDUKTIVNÍCH PRAVIDEL Cíl: Cílem této kapitoly je naučit (společně s předchozí kapitolou, kde již byla celá řada příkladů uvedena) na praktických příkladech psát deduktivní pravidla pro od odvozování různých konceptů a definování integritních omezení. Čtenář by měl po prostudování této kapitoly umět napsat deduktivní pravidlo pro odvození tříd, atributů (včetně rekurzivních), pohledů a integritních omezení různého typu. Klíčová slova: Intenzionální nerekurzivní atribut, intenzionální rekurzivní atribut, intenzionální třída, inverzní atribut, io ve fixním formátu, referenční integrita, generická integrita 1. Definice intenzionálního nerekurzivního atributu kredity_za_semestr
Příklad: Mějme třídu Student následujícího schématu: Individual Student in Class with attributes id_cislo : String; jmeno : String; obor : String; rocnik : Integer; kontakt : String; studijni_vysledky : Vysledky End Přidejme do schématu atribut kredity_za_semestr, který bude odvoditelný pomocí deduktivního pravidla: Individual Student with attributes kredity_za_semestr : Integer derived End Pro výpočet počtu kreditů za jednotlivé semestry požijeme extérní formuli CastToPocet_kreditu, jejímž vstupním parametrem bude semestr a výstupním parametrem bude počet získaných kreditů. Define external formula CastToPocet_kreditu (in semestr: integer, out I integer) End
124
Této formule využijeme při definování deduktivního pravidla pro odvození atributu kredity_za_semestr: Define implementation for Student with attributes intereg(I), CastToPocet_kreditu Self.kredity_za_semestr = I (Self.studijni_vysledky.semestr, I) End 2. Definice intenzionálního nerekurzivního atributu pocet_studentu_ve_skupine
Příklad: Individual Skupina in Class with attributes cislo_skupiny : Integer; studenti : Student; studuje : Kurz; pocet_studentu_ve_skupine : Integer derived End Define implementation for Skupina with attributes Self.pocet_studentu_ve_skupine = X
Integer(X). X = count(Self.studenti)
End
3. Definice intenzionálního rekurzivního atributu předpoklady
Příklad: (Definice využívá rekurzivního pravidla, které se skládá z báze a indukce).
125
Mějme třídu Kurz následujícího schématu: Individual Kurz in Class with attributes cislo_kurzu : Integer; nazev : String; vyuk_material : Vyukovy_material; test : Test; ukoncen : String; je_veden : Tutor; studuje : Skupina; pozadavek : Kurz; predpoklady : set-of(Kurz), derived End Odvoďme rekurzivní atribut predpoklady, který je uzávěrem kruhového vztahu. Define implementation for Kurz with attributes X in Self.predpoklady
Kurz(X), X in Self.pozadavek;
X in Self.predpoklady
Kurz(X), X in Self.pozadavek.predpoklady
End 4. Definice intenzionální třídy Ucitel_katedry_informatiky
Příklad: Mějme třídu Učitel následujícího schématu: Individual Ucitel in Class with attributes osobni_cislo : Integer; jmeno : String; katedra : String; kontakt : String; komunikace : Komunikace End
126
Definujme novou třídu Ucitel_katedry_informatiky Define implementation for class Ucitel population Ucitel(X), X.katedra = Informatika
Ucitel_katedry_informatiky(X) End
5. Definice intenzionální třídy Tutor_kurzu_databaze
Příklad: Mějme třídu Tutor následujícího schématu: Individual Tutor isA Ucitel with attributes vede:Kurz End Definujme novou třídu Tutor_kurzu_databaze: Define implementation for class Tutor with population Tutor_kurzu_databaze(X)
Tutor(X), X.vede = Databaze
End
127
6. Pravidla pro definování IO ve fixním formátu
Příklad: id_cislo not null Add immediate constraint null_id_cislo for Student as null_id_cislo(Self)
Self.id_cislo = null
End id_cislo primary key Add immediate constraint primary_key for Student as primary_key(Self)
Student(X), X! X.id_cislo = Self.id_cislo
End 7. Pravidla pro odvozování inverzního atributu
Příklad: Individual Ucitel in Class with attributes komunikace : set of(Komunikace) End Individual Komunikace in Class with attributes ucitel : set-of(Ucitel) End Define implementation for Komunikace with attributes X in Self.ucitel
Ucitel(X), X.komunikuje = Self
End
128
8. Pravidla pro definování referenční integrity
Příklad: Individual Skupina in Class with attributes studenti : Student, notnull End Add defered constraint je_slozen for Skupina as je_slozen(Self)
Self.studenti = null
End 9. Pravidla pro generická IO
Příklad: ročník Studenta je celé číslo v rozsahu 1-5 Add immediate constraint vadny_rocnik for Student as vadny_rocnik(Self) vadny_rocnik(Self)
Self.rocnik < 1; Self.rocnik >5
End katedra Učitele je jedna z hodnot { Matematika, Informatika, Chemie, Fyzika, Biologie, Geologie} Add immediate constraint vadna_katedra for Ucitel not Self.katedra in { Matematika, Informatika, as vadna_katedra(Self) Chemie, Fyzika, Biologie, Geologie} End
129
cislo_skupiny je kladné Add immediate constraint vadne_cislo_skupiny for Skupina as vadne_cislo_skupiny(Self)
Self.cislo_skupiny <= 0
End cislo_kurzu je kladné Add immediate constraint vadne_cislo_kurzu for Kurz as vadne_cislo_kurzu(Self)
Self.cislo_kurzu <= 0
End cislo_testu je v rozsahu 1-500 Add immediate constraint vadne_cislo_testu for Test as vadne_cislo_testu(Self) vadne_cislo_testu(Self)
Self.cislo_testu < 1; Self.cislo_testu > 500
End pozadovane_kredity >= ziskane_kredity Add defered constraint vadne_kredity for Vysledky as vadne_kredity(Self)
Self.ziskane_kredity >= Self.pozadovane_kredity
End 10. Pravidlo pro inverzní vztah
Příklad: Define implementation for Kurz with attributes X in Self.studuje
Skupina(X), X.studuje = Self
End
130
Průvodce studiem Je za vámi opět kus práce. Pokud jste vše pochopili a jste schopní napsat deduktivní pravidla podobného charakteru, jak bylo uvedeno v řešených příkladech, můžete přikročit k vypracování korespondenčního úkolu. Bude to již poslední korespondenční úkol, který v tomto předmětu musíte splnit. Proto si na chvíli oddychněte a příliš dlouho vypracování neodkládejte. Přeji mnoho úspěchů.
Použitá literatura 1. Ceri, S., Fraternali, P.: Database Applications with Objects and Rules, Addison-Wesley, England, 1997 2. Date, C.J. : An Introduction to Database Systems. Addison - Wesley Publishing Company, USA, 1990 3. Gruber, M.: Understanding SQL, Sybex, USA, 1990 4. Havlát, T., Benešovský, M. : Úvod do databázových systémů. Skripta přírodovědecké‚ fakulty UJEP, Brno, 1987 5. Korth, H.F., Silberschatz, A. : Database system concepts. McGraw-Hill, Inc., 1991 6. Pokorný, J. : Dotazovací jazyky v databázových syst‚mech. Skripta MFF UK v Praze, SPN Praha, 1986 7. Pokorný, J. : Databázové technologie. Sborník semináře MOP, MFF UK Praha, 1990 8. Pokorný, J. : Počítačové‚ databáze. Kancelářské stroje, informační středisko, Praha, 1991 9. Pokorný, J. : Databázové‚ Academia, Praha, 1992
systémy
a
jejich
použití
v informačních systémech.
10. Pokorný, J., Halaška, I. : Databázové‚ systémy. Vybrané‚ kapitoly a cvičení. Skripta el. fakulty ČVUT, Praha, 1992 11. Pokorný, J.: Dotazovací jazyky, Science, 1994 12. Pokorný, J.: Základy implementace souborů a databází, Karolinum Praha, 1997 13. Telnarová, Z., Lukasová, A., Matula, P.: Úvod do databázové technologie. Skripta OU Ostrava, 1999 14. Telnarová, Z.: Databázové systémy a jejich využití v IS. Skripta OU, Ostrava, 2001 15. Ullman, D.J.: Principles of database and knowledge-base systems, Volume I, Computer Sc. Press, 1988 16. Ullman, D.J.: Principles of database and knowledge-base systems, Volume II, Computer Sc. Press, 1989 17. Wagner, G.: Foundations of Knowledge Systems, Kluwer, London 1998 18. Zaniolo, C,., Ceri, S., Faloutsos, Ch., Snodgrass, R., Subrahmanian, V., S., Zigari, R.: Advanced database systems, Morgan Kaufmann Publisher, Sna Francisco, 1997 131
