Přednášky

umožní ji verifikovat a ověřit úplnost datového modelu * Modelování funkcí způsoby modelování funkcí
hierarchie funkcí
události – spouštěče funkcí
DFD – data flow diagramy, diagramy toků dat
stavové diagramy
Petriho sítě
různé úrovně abstrakce
(pracovní) funkce v organizaci
proces v konceptuálním modelu
procedura, program v programové úrovni * Hierarchie funkcí funkce je něco, co organizace dělá
založení nového abonenta v evidenci vstupenek
odstranění studenta ze seznamu aktivních studentů
funkce má mít výstižné jméno a popis
identifikuj, změň, odstraň, odešli, spočítej,...
např. „založ nový požadavek na reservaci“
v popisu funkce specifikujeme CO chceme udělat, nikoli JAK
nezmiňují se organisační struktury (oddělení...) či role uživatelů (ředitel...)
vyloučit informace typu KDE, KDO, KDY, JAK * Hierarchie funkcí v analýze shora dolů
určíme funkci a případně ji rozdělíme na podfunkce
dílčí funkce
vzniká tak strom (hierarchie) funkcí
pořadí funkcí na stejné úrovni stromu neurčuje pořadí
při dekompozici musí dílčí funkce úplně a beze zbytku pokrýt nadřazenou funkci, nesmí se překrývat a musí být nutné
událost může fungovat jako spouštěč, trigger nějaké funkce
listy stromu – atomické, nevyžadují již dekompozici * Hierarchie funkcí * Hierarchie funkcí typy funkcí
atomické – dále nedělitelné
elementární – mohou se skládat z dílčích funkcí, ale vždy se provedou celé nebo nic (obdoba transakcí – viz další přednášky)
převod peněz mezi účty
odečíst peníze z jednoho účtu
přičíst peníze na druhý účet
společná – funkce, která se v hierarchii vyskytuje vícekrát
lze ji navrhnout, popsat a implementovat pouze jednou * Hierarchie funkcí funkční analýza
objevování funkcí
interview se zákazníkem
pozor, pracovníci mají tendenci leckteré funkce považovat za tak samozřejmé, že se o nich ani nezmíní
další zdroje informací, analogie z jiných společností...
postup shora dolů nebo zdola nahoru
obojí lze kombinovat a vzájemně doplňovat a testovat
schema funkcí má být
přesné a srozumitelné
úplné
stručné ve výrazivu
vyvážené * Hierarchie funkcí vztah funkcí ke konceptuálnímu schematu
během návrhu testovat zda
existují funkce, které zmiňují dané entity
existují funkce, které vytvářejí, mění či odstraňují entity, vztahy, hodnoty atributů v koncept. schematu
specifikace funkce
popis její logiky, tj. jak se provádí
popis algoritmu
časově náročné
provádí se především u klíčových a složitých funkcí
měl by být natolik exaktní, aby umožnil jednoznačnou implementaci
* DFD model toků dat
místo funkcí se obvykle hovoří o procesech
konstrukty
proces (process)
reprezentuje aktivitu v IS
transformuje informace
předává informaci jiným procesům
může pokrývat několik pracovních funkcí
tok dat (data flow)
výměna informace mezi procesy
sklad dat (data store)
místo, kde jsou uložena data – šanon, databáze... * DFD rozhraní (interface), někdy se nazývá terminátor
např. externí uživatel
při dekomponovaném schematu může reprezentovat část IS popsanou jinde
diagram toků dat
funkční popis systému, nikoli popis implementace
orientovaný graf
uzly: procesy, rozhraní, sklady
hrany: toky dat
je dobré všechno nějak pojmenovat, i hlavní toky dat
někdy lze procesy vnořovat do sebe
někdy se (vcelku rozumně) požaduje, aby mezi skladem a rozhraním byl vždy aspoň jeden proces * DFD * DFD použití DFD ve funkční analýze
můžeme nejprve definovat hierarchii funkcí a poté z identifikovaných funkcí konstruovat DFD
seskupování funkcí do procesů
různé metodologie
posloupnost kroků
identifikuj rozhraní
identifikuj I/O toky dat mezi rozhraním a IS
navrhni skeletální DFD
zjemňuj DFD libovolnou strategií
tak dlouho, až jsou obsaženy všechny požadavky, ale schema ještě není procedurální * DFD opět různé strategie návrhu
shora dolů
zjemňování
zdola nahoru
nejprve izolované procesy, které se postupně spojují
zevnitř ven
lze postupovat od rozhraní nebo od dat. skladu
smíšená
jakákoli strategie je vlastně transformací diagramu od počátečního stavu ke koncovému * DFD obecná doporučení
schema má ukazovat CO, nikoli JAK
nezjemňovat, přechází-li v procedurální popis
nezjemňovat, ztrácí-li se globální struktura
naskenovat obr. 3.19 a 3.20 * DFD posouzení kvality
funkční nezávislost
každý proces je autonomní, může být analyzován a měněn nezávisle na zbytku systému
úplnost
DFD pokrývá všechny rysy aplikace
korektnost
zachování ekvivalence hranic po zjemnění
čitelnost
minimalita
procesy a sklady se nepřekrývají * DFD ekvivalence hranic * DFD integrace datové a funkční analýzy
vzájemné ovlivňování
například zjemnění schematu funkcí vyvolá nutnost zjemnit i ER model
např. rozdělíme proces na dva, čímž je indukována nutnost zavést do ER modelu ISA hierarchii
kontrola vzájemné úplnosti
každý pojem, zmiňovaný v tocích dat a zásobárnách, se vyskytuje v ER schematu
každý datový prvek ER modelu musí mít k sobě proces, který jej vytváří, mění, odstraňuje *
Databázové systémy 2 Kapitola 5
Funkční závislosti Motivace normalizace relací
úprava struktury tak, aby relační schema dobře reprezentovalo data, aby byla omezena redundance a přitom se neztratily vazby mezi daty
příklad
mějme relaci
PROGRAM(název_k, jméno_f, adresa, datum)
problémy
některá informace bude zbytečně opakována víckrát
adresa kina bude uložena tolikrát, kolik filmů je v kině na programu
změní-li se jméno ulice, musíme přepisovat mnoho
nehraje-li kino nic, ztrácíme jeho adresu * Motivace řešení
dekompozice na dvě schemata relací
KINO(název_k, adresa)
PROGRAM(název_k, jméno_f, datum)
všechny problémy zmizely
obecně
redundance – ukládání stejné informace víckrát na různých místech (zvyšuje prostorové nároky)
mohou nastat aktualizační anomálie (insert/delete/update)
při vložení dat příslušejících jedné entitě je potřeba zároveň vložit data do jiné entity
při vymazání dat příslušejících jedné entitě je potřeba vymazat data patřící jiné entitě
pokud se změní jedna kopie redundantních dat, je třeba změnit i ostatní kopie, jinak se databáze stane nekonzistentní
řešení: normalizace schematu
* Motivace co je důvodem problémů v příkladu?
hodnoty některých atributů závisejí na hodnotách jiných atributů
ke každému kinu přísluší právě jedna adresa
pro každé kino a film existuje nejvýše jedno datum, kdy se film dává
v podstatě jde o funkci: přiřazení hodnoty jiné hodnotě
speciální případ IO
funkční závislosti
je to něco jiného, než jsme řešili na předchozí přednášce!
název_k  adresa
{název_k, jméno_f}  datum
* Funkční závislosti závislost mezi dvěma množinami atributů v rámci jednoho schematu relace
závislost mezi daty (nikoli mezi entitami a daty ap.)
je to IO – vymezuje množinu přípustných relací
funkční závislost (FZ) X  Y nad schématem R(A)
zobrazení fi : Xi  Yi
Xi,Yi A
i = 1..počet závislostí pro R(A)
n-tice z Xi funkčně určuje m-tici z Yi
m-tice z Yi funkčně závisí na n-tici z Xi
hodnoty atributů X společně určují hodnoty atrib. Y
zobecnění principu klíče * Funkční závislosti funkční závislost
vyplývá z obecné (konceptuální) závislosti dat, nikoli z jejich konkrétní podoby
např. máme tabulku studijních výsledků
podle těchto dat to vypadá, že student  známka
to ale ve skutečnosti určitě obecně neplatí, je to pouze náhoda
student předmět známka Novák Teorie obvodů 3 Novák Úvod do algebry 3 Haničinec Teorie obvodů 1 Haničinec Matematika 1 1 * Funkční závislosti základní vlastnosti
pokud X  Y a zároveň Y  X, pak jsou X a Y funkčně ekvivalentní, X  Y
pokud X  a, kde a  A, tj. na pravé straně je jeden atribut, závislost se nazývá elementární
redefinice klíče
máme-li R(A) a K  A, pak K je klíčem schematu R, jestliže platí
K  A
neexistuje K‘  K taková, že K‘  A * Funkční závislosti armstrongova pravidla
mějme R(A) a množinu funkčních závislostí F
nechť X, Y, Z  A
jestliže Y  X, potom X  Y
triviální FZ, axiom (např. AB  A)
jestliže X  Y a Y  Z, potom X  Z
tranzitivita
jestliže X  Y a X  Z, pak X  YZ
kompozice
jestliže X  YZ, pak X  Y a X  Z
dekompozice
* Funkční závislosti armstrongova pravidla
jsou korektní
co z F odvodíme, platí pro libovolnou instanci R
jsou úplná
lze jimi odvodit všechny FZ platné ve všech instancích R
jsou nezávislá
odstraněním kteréhokoli z nich odstraníme podmínku úplnosti
* Funkční závislosti příklad aplikace Armstrongových pravidel
F = {P  U, HM  P, HU  M, PS  Z, , HS  M}
co platí
HM  H (triviální)
HU  H (triviální)
HU  HM (kompozice HU  H a HU  M)
HM  U (tranzitivita HM  P a P  U)
HM  HU (kompozice HM  U a HM  H)
HM a HU jsou funkčně ekvivalentní, HM  HU * Funkční závislosti příklad aplikace Armstrongových pravidel
R(a,b,c,d,e,f)
F = {ab  c, ac  d, cd  ed, e  f}
co lze odvodit
ab  a (triviální)
ab  ac (kompozice s ab  c)
ab  d (tranzitivita s ac  d)
ab  cd (kompozice s ab  c)
ab  ed (tranzitivita s cd  ed)
ab  e (dekompozice)
ab  f (tranzitivita) * Funkční závislosti uzávěr F+ množiny funkčních závislostí F
množina všech FZ odvoditelných z FZ ve F
závislost f je redundantní v F, jestliže
(F – {f})+ = F+
tj. f lze odvodit
pokrytí množiny funkčních závislostí F
množina G taková, že G+ = F+
kanonické
na pravé straně pouze jednotlivé atributy
neredundantní
neobsahuje redundantní FZ
není dáno jednoznačně, záleží na pořadí odebírání FZ * Funkční závislosti uzávěr množiny atributů X+ vzhledem k F
množina atributů funkčně závislých na X
redundantní atribut
mějme ve F závislost XY
mějme AX takový, že (X-A)+ = X+
pak A je v X pro danou závislost redundantní
minimální pokrytí
takové pokrytí, které nemá v závislostech na levé straně žádné redundantní atributy * Funkční závislosti redundantní FZ je nejlépe odstraňovat z uzávěru množiny F+
náročné
obvyklý postup optimalizace množiny F
vytvořit kanonické pokrytí ... F’
odstranit z FZ v F’ redundantní atributy ... F’’
odstranit z F’’ redundantní závislosti ... F’’’
F’’’ je minimální pokrytí * Funkční závislosti Příklad nalezení min. pokrytí:
R(A,B,C,D), F={AAC, BAC, DAB}
kanonické pokrytí (vpravo vždy jediný atribut):
F’={AA, AC, BA, BC, DA, DB}
všechny závislosti redukované, netřeba odstraňovat redundantní atributy (vlevo vždy jediný atribut)
odstranit redundantní závislosti
AA lze odstranit, je triviální
AC nelze odstranit (kdyby ano, pak A+=A)
BA nelze odstranit (kdyby ano, pak B+=BC)
BC lze odstranit (neb BA a AC)
DA lze odstranit (neb DB a BA)
DB nelze odstranit (kdyby ano, pak D+=D)
* Funkční závislosti Příklad nalezení min. pokrytí:
R(A,B,C,D), F={AAC, BAC, DAB}
minimální pokrytí:
F’’’={AC, BA, DB}
* Funkční závislosti tranzitivní závislost na klíči
nechť A není ani klíč ani nadklíč a nechť existuje závislost A  B
pak B je tranzitivně závislé na klíči
z definice klíče K dostaneme, že K  A
jelikož A  B, pak K  A  B *
Databázové systémy 2 Kapitola 6
Normalizace Normální formy aby schema relace splňovalo jisté požadavky (např. na malou redundanci, odstranění aktualizačních anomálnií atd.), zavádíme tzv. normální formy
první
druhá
třetí
Boyce-Coddova
(čtvrtá, pátá)
* První normální forma (1NF) každý atribut schématu je elementární a nestrukturovaný
tj. databáze je plochá, tabulka je skutečně dvojrozměrný objekt * První normální forma (1NF) každý atribut schématu je elementární a nestrukturovaný
tj. databáze je plochá, tabulka je skutečně dvojrozměrný objekt
OSOBA(jméno, rč, č_op) je v 1NF
OSOBA(jméno, rč, adresa(město, ulice, čp)) není v 1NF
* Druhá normální forma (2NF) neexistují závislosti atributů na podmnožině žádného klíče
např. PROGRAM(název_k, jméno_f, adresa, datum) není v 2NF, neboť platí, že název_k  adresa
klíč klíčové atributy neklíčový atribut * Třetí normální forma (3NF) nejdůležitější
žádný neklíčový atribut není tranzitivně závislý na žádném klíči
splněno, platí-li pro každou X  a (kde X  A, a  A) aspoň jedna z podmínek
závislost je triviální
X je nadklíč
a je částí klíče
klíč a Y * Třetí normální forma (3NF) příklad
Firma Sídlo PSČ Frantova firma Praha 11800 Martinova firma Ostrava 70833 Pavlova firma Brno 22012 Viktorova firma Praha 11000 Pepova firma Brno 22012 Firma  všechno
PSČ  Sídlo
je ve 2NF, není ve 3NF (tranzitivní závislost Sídla na klíči přes PSČ)
důsledek: redundance hodnot Sídla * Třetí normální forma (3NF) příklad - řešení
Firma PSČ Frantova firma 11800 Martinova firma 70833 Pavlova firma 22012 Viktorova firma 11000 Pepova firma 22012 PSČ Sídlo 11800 Praha 70833 Ostrava 22012 Brno 11000 Praha Firma  všechno PSČ  všechno
obě schémata jsou ve 3NF * Boyce-Coddova norm. forma (BCNF) každý atribut je netranzitivně závislý na klíči
tj. pro každou netriviální závislost X  Y platí, že X obsahuje klíč schematu
splněno, platí-li pro každou X  a (kde X  A, a  A) aspoň jedna z podmínek
závislost je triviální
X je nadklíč * Boyce-Coddova norm. forma (BCNF) příklad Destinace Pilot Letadlo Den Paříž kpt. Ptáček Boeing #1 pondělí Paříž kpt. Ptáček Boeing #2 úterý Berlín kpt. Vogel Airbus #1 pondělí Pilot, Den  všechno
Letadlo, Den  všechno
Destinace  Pilot
je ve 3NF, není v BCNF (Pilot závisí na Destinaci, což není nadklíč)
důsledek: redundance hodnot Pilot
* Boyce-Coddova norm. forma (BCNF) příklad Destinace Pilot Paříž kpt. Ptáček Berlín kpt. Vogel Destinace Letadlo Den Paříž Boeing #1 pondělí Paříž Boeing #2 úterý Berlín Airbus #1 pondělí Destinace  Pilot Letadlo, Den  všechno
nyní jsou obě schémata je v BCNF
* Návrh schematu databáze dva způsoby návrhu
na prvotní množině relačních schemat (vzniklé např. převodem z E-R modelu) provádím normalizaci na jednotlivých schematech
riziko přílišného rozdrobení modelu
vezmu všechny atributy všech relací a pomocí funkčních závislostí mezi nimi rozpoznávám entity
menší riziko rozdrobení
modelujeme na úrovni atributů, což není moc intuitivní
přístupy lze různě kombinovat * Návrh schematu databáze normalizace schematu
zatím jsme normálními formami řešili problém aktualizačních anomálií a redundance
nevhodná normalizace ale může vést k jiným potížím
je nutné, aby normalizovaná schemata
měla stejnou sémantiku (pokrytí závislostí)
obsahovala stejná data (bezeztrátové spojení) * Návrh schematu databáze pokrytí závislostí
v původním schematu existovala množina funkčních závislostí (řekněme F)
množina funkčních závislostí na nových schematech musí tvořit pokrytí F, tj. všechny původní FZ musí být i nadále odvoditelné
tj. F+ = (i=1..nFi)+
kde Fi je množina FZ pro dekomponované schema Ri
* Návrh schematu databáze pokrytí závislostí - příklad
Firma Sídlo Nadmořská výška Sun Santa Clara 25 mnm Oracle Redwood 20 mnm Microsoft Redmond 10 mnm IBM New York 15 mnm Firma Sídlo Sun Santa Clara Oracle Redwood Microsoft Redmond IBM New York Sídlo Nadmořská výška Santa Clara 25 mnm Redwood 20 mnm Redmond 10 mnm New York 15 mnm Firma, Sídlo  Nadmořská výška Firma Sídlo pokrytí zachováno Firma Nadmořská výška Sun 25 mnm Oracle 20 mnm Microsoft 10 mnm IBM 15 mnm Firma Sídlo Sun Santa Clara Oracle Redwood Microsoft Redmond IBM New York Firma Sídlo pokrytí porušeno, ztratili jsme
Sídlo  Nadmořská výška
* Návrh schematu databáze bezeztrátové spojení
původní relační schema (před dekompozicí) by se mělo dát zrekonstruovat z dekomponovaných schemat
pro každou přípustnou relaci R‘ by mělo platit
R’ = *i=1..n R’[Ai],
kde Ai jsou atributy dílčích relací po dekompozici
tedy spojení projekcí původní relace na množiny atributů nových relací musí vést k původní relaci * Návrh schematu databáze bezeztrátové spojení – negativní příklad Firma Používá DBMS Spravuje dat Sun Oracle 50 TB Sun DB2 10 GB Microsoft MSSQL 30 TB Microsoft Oracle 30 TB Firma Používá DBMS Sun Oracle Sun DB2 Microsoft MSSQL Microsoft Oracle Firma Spravuje dat Sun 50 TB Sun 10 GB Microsoft 30 TB Firma Používá DBMS Spravuje dat Sun Oracle 50 TB Sun Oracle 10 GB Sun DB2 10 GB Sun DB2 50 TB Microsoft MSSQL 30 TB Microsoft Oracle 30 TB Firma, Používá DBMS Firma, Používá DBMS Firma, Spravuje dat Firma, Používá DBMS, Spravuje dat „rekonstrukce“ (přirozené spojení) * Návrh schematu databáze jak zajistit bezeztrátové spojení
mějme schema R(A,B,C) (A, B, C jsou disjunktní množiny atributů) a funkční závislost BC. Pak dekompozice na R1(B,C) a R2(A,B) je bezeztrátová.
naopak, je-li dekompozice R1(B,C) a R2(A,B) bezeztrátová, musí platit buď BC nebo BA.
dekomponujeme tedy podle kritické funkční závislosti *
Databázové systémy 2 Kapitola 7
Pokročilejší rysy jazyka SQL Datové typy PostgreSQL široká škála nativních datových typů
číselné (numeric)
znakové (character)
binární (binary)
datum a čas (date and time)
boolean
výčtové (enumerated)
geometrické (geometric)
pole (arrays)
kompozitní datové typy (composite types)
řetězce bitů (bit strings)
a další... (síťové adresy, XML, měnové, OID,...)
lze přidávat další datové typy
* Datové typy PostgreSQL číselné
celočíselné typy různé délky
integer
serial – automatické číslo
čísla s plovoucí řádovou čárkou
real
speciální hodnoty Infinity, -Infinity a NaN
desetinná čísla s pevnou řádovou čárkou
decimal (totéž co numeric) – velmi pomalé operace, přesnost až 1000 cifer * Datové typy PostgreSQL znakové
char(n) – řetězec délky přesně n
varchar(n) – řetězec proměnné délky, max n
text – řetězec neomezené délky
char je v případě potřeby doplněn zprava na stanovenou délku mezerami
tyto mezery nejsou signifikantní, tj. neberou se v potaz
varchar naproti tomu se ukládá přesně tak, jak je, tzn. že případné mezery JSOU signifikantní
char neumožňuje uložit např. byte s hodnotou 0 * Datové typy PostgreSQL binární
bytea – řetězec bytů proměnné délky
analogické datovému typu BLOB z SQL standardu
některé znaky se musí zadávat pomocí tzv. escape sekvencí ve tvaru
E’\\000’ * Datové typy PostgreSQL datum a čas
timestamp – časové razítko
time
interval
umožňují též uchovávat informaci o časovém pásmu
různé formáty data a času
1999-01-08, January 8, 1999, 1/8/1999, 990108,...
speciální hodnoty
now
today, tomorrow, yesterday
infinity, -infinity
... * Datové typy PostgreSQL boolean
boolean
kromě TRUE/FALSE lze použít rovněž
t/f
y/n
yes/no
on/off
1/0 * Datové typy PostgreSQL výčtové typy
enum
nutno je vytvořit, poté se použijí dle jména (mood)
CREATE TYPE mood AS ENUM (’sad’, ’ok’, ’happy’);
je definováno uspořádání, a to podle pořadí, v jakém byly prvky definovány
i když více výčtových typů obsahuje tentýž identifikátor, nelze porovnávat relačními operátory
* Datové typy PostgreSQL geometrické typy
point
line
box
circle
2D objekty
bitové řetězce
posloupnosti 0 a 1
bit(n)
bit varying(n)
INSERT INTO test VALUES (B’101’, B’00’);
* Datové typy PostgreSQL pole
[]
lze použít skoro na jakýkoli datový typ: text[][]
velmi mnoho možností použití
CREATE TABLE sal_emp (
name text, pay_by_quarter integer[], schedule text[][] );
INSERT INTO sal_emp
VALUES (’Bill’,
ARRAY[10000, 10000, 10000, 10000],
’{{"meeting", "lunch"}, {"training", "presentation"}}’);
SELECT pay_by_quarter[2:3] FROM sal_emp; * Datové typy PostgreSQL kompozitní typy
obdoba tabulky
velmi mnoho možností použití
přístup k prvkům tečkovou notací
jeden „kompozitní“ řádek lze ad hoc zkonstruovat příkazem ROW
ROW(1, 2.5, ’this is a test’);
CREATE TYPE complex AS (
r double precision,
i double precision
); * Přetypování datové typy lze do jisté míry převádět jeden na druhý
implicitní konverze
explicitní konverze
CAST (expression AS type)
expression::type
CAST ( 12.0 AS text );
12.0::text; * Dostupné funkce a operátory existují myriády vestavěných funkcí a operátorů pro všemožné operace nad datovými typy
logické (AND, OR, NOT)
relační (, =, >=, 500;
-- vybere záznamy jen z tabulky cities
SELECT name, altitude FROM ONLY cities WHERE ...;
* Schemata databáze je členěna do hierarchické struktury
nejvyšší je cluster
cluster obsahuje pojmenované databáze
databáze obsahuje pojmenovaná schemata
schema obsahuje tabulky a další objekty
dvě schemata mohou obsahovat tabulku stejného jména
schemata nejsou tak striktně oddělena jako databáze, uživatel (připojí-li se k DB) může používat všechna, má-li na to oprávně