Databaze_MFF

inou žádného z dosud nalezených klíčů, ale BCD+F= {B,C,D}, a tedy více klíčů daného schématu neexistuje Vhodný algoritmus zaručující nalezení všech klíčů navrhli Claudio Lucchesi a Sylvia Osborn:
Závislosti z F upravíme na netriviální, tj. každou závislost X->Y upravíme na X->(Y\X).
Nejprve se nalezne jakoukoli metodou jeden klíč schématu. Označme získaný klíč K. Pak procházíme závislosti z F a pro každou závislost X->Y takovou, že průnik Y a K je neprázdný, vytvoříme množinu (KX)\Y. Pokud tato množina není (nevlastní) nadmnožinou dříve nalezeného klíče, je kandidátem na další klíč - je jen třeba ji redukovat na minimum .
Pro každý nově nalezený klíč postup opakujeme. Hledání skončí, když v některém kroku žádný nový klíč nenalezneme. R={A,B,C,D}, F={BC->D, A->D, BA->C, CA->B, BD->C}.
Nechť již známe klíč AB.
Pouze pravá strana závislosti CA->B má neprázdný průnik s AB. Vytvoříme (ABAC)\B, což dává AC. Snadno zjistíme, že ani samotné A ani samotné C nejsou klíči – a proto AC je další klíč schématu. R={A,B,C,D}, F={BC->D, A->D, BA->C, CA->B, BD->C}.
Známe již klíče AB a AC.
Použitím závislosti BA->C bychom dostali znovu již známý klíč AB.
Musíme tedy zkusit použít závislost BD->C. Vytvoříme (ACBD)\C, což dává ABD, ale to je nadmnožinou AB a tedy není klíčem. V tomto kroku jsme nezískali žádný nový klíč a tedy algoritmus končí.
Databázové systémyDBI002 Antonín Říha
KSI MFF UK
http://www.ms.mff.cuni.cz/~riha/dbs.htm
Minule: počátky relační teorie
--správně navržená tabulka  relace v (3.) NF
--ke zjištění NF – klíče a neklíčové atributy
--zjištěné i odvozené (vyplývající) závislosti (reflexivita,tranzitivita,kompozice) Dána
množina atributů (schéma) R množina (funkčních) závislostí F,
XR, CR.
(X -> C)F+  C X+F - algoritmus příslušnosti -
kde X+F se vytváří na základě reflexivity, tranzitivity a kompozice X+F je největší podmnožina PR taková, že X->P
je-li X+F rovno R, je X (nad)klíč schématu R
ke klíčům a NF se vrátíme později, až budeme probírat postupy, jak těch NF dosáhnout
ale k tomu budou třeba i operace na relacích – relační algebra - relace jako operandy i výsledky Příjmení (všech) učitelů pPŘ(U) příklad na projekci
U (KU,PŘ,KA) select distinct PŘ from U select distinct t.PŘ from U t
Učitelé katedry algebry sKA='Alg'(U) příklad na selekci
select * from U where KA='Alg' U (KU,PŘ,KA) Operace spojení relací je velice důležitá odvozená binární operace: R ABS = sAB (RS), kde QÎ{=,ą,,=}
názvy vyučovaných předmětů pNP(R P.KP=R.KPP)
[připomeňme P(KP,NP,TV,PH), R(KU,KP,DT,HZ,PO)]
zde zároveň vidíme kartézský součin a selekci dle porovnání hodnot dvou atributů (restrikci) ZAM (ČZ,Plat,ČV)
zaměstnanci, kteří berou více než jejich šéf
ČZ,Plat,ČV(ZAMČV=ČZ1&Plat>Plat1
(ČZ®ČZ1,Plat®Plat1,ČV® ČV1(ZAM)))
select t.ČZ,t.Plat,t.ČV from ZAM t, ZAM u
where t.ČV=u.ČZ and t.Plat>u.Plat Přirozené spojení:
R*S = schéma(R)schéma(S)(sR[X]=S[X] (RS)),
kde X= schéma(R)schéma(S)
např. názvy vyučovaných předmětů NP(R*P)
[připomeňme P(KP,NP,TV,PH), R(KU,KP,DT,HZ,PO)] Přirozené spojení:
Nechť x relace nad schématem X, y relace nad schématem Y. Pak přirozené spojení relací x a y (značeno x*y) je největší relace v nad schématem XČY taková, že v[X]  x, v[Y]  y.
Jestliže XÇY=Ć, pak x*y = xy, jestliže X=Y, pak x*y = xÇy.
MUŽ ŽENA DÍTĚ  MUŽ ŽENA …R2 m1 ž1 d1  m1 ž1 m1 ž2 d2 m1 ž2
↓ R1*R2:
MUŽ DÍTĚ …R1 MUŽ ŽENA DÍTĚ m1 d1 m1 ž1 d1
m1 d2 m1 ž1 d2
m1 ž2 d1
m1 ž2 d2 Příklad na rozdíl:
Učitelé, kteří (teď, tj. dle této databáze) nic neučí U \ ( U * KU(R))
(select * from U) except (select * from U natural join (select KU from R))
[U (KU,PŘ,KA), R(KU,KP,DT,HZ,PO)] Příklad na průnik: předměty vyučované KSI i KSVI
KP( KU(σKA='KSVI' U)*  KU,KP( R) 
KU(σKA='KSI' U )*  KU,KP( R) )
[U (KU,PŘ,KA), R(KU,KP,DT,HZ,PO)]
(select KP from R where KU in ( select KU from U where KA='KSVI' ))
intersect
(select KP from R where KU in ( select KU from U where KA='KSI' )) Příklad na sjednocení: relace Spoj(Zac,Kon) reprezentuje přímé spoje, pak výraz
Spoj Č Zac,Kon(Kon®K(Spoj) K=Z Zac®Z(Spoj) )
vytváří relaci - spoje "s nejvýše jednou zastávkou"
(select * from SPOJ) union (select t.ZAC,s.KON from SPOJ t, SPOJ s where t.KON=s.ZAC) zajímavá odvozená operace: Značení: zde R[ATR]znamená ATR(R), R(KU,KP,DT,HZ,PO)
Kódy učitelů, kteří učí každý den
R1:= R[KU]  R[DT] všechny možné páry
R2:= R[KU,DT] páry vyskytující se v rozvrhu
R3:= R1 \ R2 páry nevyskytující se v rozvrhu
R4:= R3[KU] učitelé, pro něž některý pár (a tedy den) chybí
výsledek je pak R[KU] \ R4 po dosazení R[KU] \ ( ( (R[KU]  R[DT]) \ R[KU,DT] ) [KU] )
Definice operace dělení: Nechť x je relace nad schématem X, y relace nad schématem Y, kde YÍX. Pak x ¸ y = x[X-Y] \ ( ( (x[X-Y]  y) \ x ) [X-Y] ).
Kódy učitelů, kteří učí každý den R[KU,DT] ¸R[DT] relační algebra – jazyk procedurální
jedna z vymožeností relačních databází – neprocedurální dotazovací jazyky – (i většina příkazů SQL) Jazyk logiky 1. řádu:
abeceda: proměnné, n-ární funkční symboly, n-ární predikátové symboly, logické spojky, kvantifikátory, rovnost, závorky;
termy: a) proměnné, b) F(T1,...,Tn);
atomické formule: P(T1,...,Tn);
formule: a) atomické, b) pomocí logických spojek, c) pomocí kvantifikátorů
důležité: vázané a volné proměnné Aplikace na databáze je dvojí: I.
Mějme relaci Učitel se schématem U={KU,PŘ,KA}, atributům jsou přiřazeny tzv. domény (obory hodnot).
Přiřadíme formuli U(ku,př,ka), kde U je predikátový symbol a ku,př,ka - proměnné nebo konstanty (obecně termy).
U(358,NOVÁK,KSI) má hodnotu true právě když v tabulceUčitel existuje řádek . dále jsou povoleny ještě porovnávací formule proměnná konstanta, proměnná proměnná
výsledné formule se vytvářejí klasicky - logickými spojkami a kvantifikátory
jde o doménový kalkul
II.
Proměnným se přiřadí celé řádky (n-tice) relací.
Formule U(t) má hodnotu true, jestliže t je řádkem U.
Hodnoty jednotlivých atributů v řádku t se pak zapisují t.KU, t.PŘ, t.KA resp. t[KU], t[PŘ], t[KA]. t.KU – z hlediska logiky = term v relačním modelu – „indexovaná n-tice“
porovnávací formule se vytvářejí z konstant a n-ticových proměnných (většinou indexovaných n-tic) – např. t.KA= ‘KSI’
Jde o n-ticový kalkul. U (KU,PŘ,KA)
Příjmení všech učitelů {(t) : U(PŘ:t)} DRK {(t[PŘ]) : U(t)} NRK
select distinct t.PŘ from U t SQL
Příjmení učitelů katedry algebry { (s) : U(PŘ:s,KA:'Alg') } DRK {(t[PŘ]) : U(t)&t[KA]='Alg'} NRK select * from U where KA='Alg' SQL [připomeňme P(KP,NP,TV,PH), R(KU,KP,DT,HZ,PO)]
Názvy vyučovaných předmětů
{(n) : $k (P(KP:k,NP:n) & R(KP:k))}
{(t[NP]) : P(t) & $R(u)(t[KP]=u[KP])}
select NP from P,R where P.KP=R.KP

select NP from P where exists (select * from R where P.KP=R.KP) Učitelé, kteří nic neučí
{(r,s,t) : U(KU:r,PŘ:s,KA:t)&ŘR(KU:r)}
{(t): U(t)&Ř$R(u)(t[KU]=u[KU])}
select * from U where not exists ( select * from R where KU=U.KU)
pro dotazy jsou velmi důležité volné proměnné –
formule bez volných proměnných může mít hodnotu true/false
pro formule s volnými proměnnými najdeme množinu všech hodnot v databázi, které dávají formuli hodnotu true - a ta množina bude odpovědí na dotaz v doménovém kalkulu - použití téže proměnné ve více tabulkách – přirozené spojení např. {(n) : $k (P(KP:k,NP:n) & R(KP:k))}

ty proměnné popř. indexované - se ještě v zápisech dotazů zdůrazňují - vytváří se tzv. cílový seznam
{(t[NP]) : P(t) & $R(u) (t[KP]=u[KP])} existují zkratky -
např. {(t): U(PŘ:t)} je v plném znění
{(t):U(_,t,_)}
nebo
{(t):su U(s,t,u)}
{(s):U(PŘ:s, KA:'Alg')}
je vlastně
{(s):t U(PŘ:s, KA:t) & t='Alg')}
při použití nerovnosti spíše ten delší zápis používají se ohraničené kvantifikátory
R(x) (P(x))  x(R(x)  P(x))
R(x) (P(x))  x(R(x) P(x))
historicky – spíše jen v n-ticovém kalkulu a jen pro ohraničení proměnné tabulkou – pokud ohraničena podmínkou, užívá se plného znění základní rozdíl mezi algebrou a kalkulem:
při klasické interpretaci kalkul akceptuje i nekonečné odpovědi –
nutno interpretaci omezit na tzv. aktuální doménu databáze
v algebře toto omezení platí „automaticky“ Nechť dána relace FILM(Název,Režisér,Herec)
Pak dotaz {(x): not FILM(‘Šepoty a výkřiky’,’Bergman’, x) }
bez omezení na hodnoty vyskytující se v databázi by dal nekonečnou nebo při nejmenším velmi velkou odpověď závislou na doméně „jméno herce“
je žádoucí , aby odpovědi byly doménově nezávislé {(t): x(R(x))  S(t) } výsledek závisí na velikosti domény pro x a na tom, zda celá ta doména je podmnožinou R
{(t,u): R(u)  S(t) } opět „nebezpečná formule“ (a analogicky pro některé formule s implikací, protože (ab) (a  b)
{(t): x(R(t,x)) } výsledek opět závisí na velikosti domény pro x Možný tvar zápisu dotazu v n-ticovém relačním kalkulu:
{(t1,...,tk ): P1(r1)&...&Pn(rn)&V(r1,...,rn)}, kde
1) k>=n>=1
2) Pi(ri) jsou rozsahové formule pro právě všechny volné proměnné formule V
3) formule V neobsahuje žádné rozsahové formule
4) tj. jsou proměnné nebo indexované proměnné "pokrývající" všechny volné proměnné formule V. tato ohraničená syntax NRK nedovoluje operaci sjednocení
sjednocení je pak nutné zavést jako explicitní spojení výsledků dvou dotazů
ale není to zase tak neobvyklé – zakládá se na tom syntaxe SQL
existuje i „volnější“ syntaktická definice bezpečných formulí, tu v tomto kurzu nebudeme zavádět [U (KU,PŘ,KA), R(KU,KP,DT,HZ,PO)]
Předměty vyučované KSI i KSVI
{(k) : $u ( R(KP:k,KU:u)& U(KU:u,KA:'KSI') )&
$v ( R(KP:k,KU:v)& U(KU:v,KA:'KSVI') ) } [U (KU,PŘ,KA), R(KU,KP,DT,HZ,PO)]
Předměty vyučované KSI i KSVI
{(t[KP]) : R(t)&$R(u)(t[KP]=u[KP])&
$U(x) (t[KU]=x[KU]& x[KA]='KSI')&
$U(y) (u[KU]=y[KU]& y[KA]='KSVI')}
select KP from R x where exists (select KU from U where (KA='KSI') and (KU=x.KU)) and exists (select * from R y where (y.KP=x.KP) and exists (select KU from U where (KA='KSVI') and (KU=y.KU)) Kódy učitelů, kteří učí každý den rozvrhu
{(k) : "d (R(DT:d) Ţ R(KU:k,DT:d))}

{(t[KU]):R(t)& "R(u)$R(v) (v[DT]=u[DT]& t[KU]=v[KU])}
select X.KU from R x where not exists ( select * from R y where not exists ( select * from Rwhere (DT=y.DT) and (KU=x.KU ))) Kódy učitelů, kteří učí každý den, kdy učí Novák (kód 358)
{(k) : "d (R(KU:358, DT:d) Ţ R(KU:k,DT:d))}
{(t[KU]) : R(t)& "R(u)$R(v) (u[KU]=358 Ţ
(v[DT]=u[DT]& t[KU]=v[KU])} {x.KU : R(x)& "R(y)$R(v) (y.KU='358' Ţ (v.DT=y.DT& v.KU=x.KU))}
{x.KU : R(x)& "R(y) (y.KU'358'  $R(v) (v.DT=y.DT& v.KU=x.KU))}
{x.KU : R(x)& Ř$R(y) Ř(y.KU'358'  $R(v) (v.DT=y.DT& v.KU=x.KU))} Kódy učitelů, kteří učí každý den, kdy učí Novák (kód 358)
select x.KU from R x where not exists
( select * from R y where y.KU='358'
and not exists
( select * from R
where (DT=y.DT)and (KU=x.KU) ) ) Zaměstnanci s platem vyšším než plat jejich vedoucího
{(z):$p$č ( ZAM(ČZ:z,Plat:p,ČV:č)&
$q (ZAM(ČZ:č,Plat:q) & p>q ))}
{(t[ČZ]) : ZAM(t)& $ZAM(u) (t[ČV]=u[ČZ] &
t[Plat]>u[Plat])}
ZAM (ČZ,Plat,ČV) Spoje (" přidání jedné hrany")
{(z,k) : Spoj(ZAC:z,KON:k)Ú
$v(Spoj(ZAC:z,KON:v)&Spoj(ZAC:v,KON:k)) }
{(t[ZAC],s[KON]) : Spoj(t)&Spoj(s)&(t=s Ú
t[KON]=s[ZAC])} KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde nepromítají žádný český film.
Algebra:
KINO[názevk] \ (FILM[země='CZ'])*PROG)[názevk] KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde nepromítají žádný český film.
doménový relační kalkul:
{k: KINO(názevk:k) &f(FILM(jménof:f,země:'CZ')& PROG(názevk:k,jménof:f))} KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde nepromítají žádný český film.
n-ticový relační kalkul:
{k.názevk : KINO(k) & PROG(p)FILM(f) ((p.názevk= k.názevk)& (f.jménof=p.jménof)  f.země='CZ')}
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítány všechny filmy natočené po roce 1980.
Algebra: PROG[jménof,názevk](FILM[rok>=1980][jménof])
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítány všechny filmy natočené po roce 1980.
doménový relační kalkul:
{k: KINO(názevk:k)& f (FILM(jménof:f ,rok>1980)  PROG(názevk:k, jménof=f))} KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítány všechny filmy natočené po roce 1980.
n-ticový relační kalkul:
{k.názevk:KINO(k)& FILM(f)(f.rok>=1980 PROG(p)(p.jménof=f.jménof)& (p.názevk=k.názevk)) } KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
Algebra:
KINO[názevk] \ ((KINO*FILM*PROG)[země'USA'])[názevk] KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
doménový relační kalkul:
{k:KINO(názevk:k)&f(PROG(jménof:f,názevk=k)FILM(jménof:f,země:'USA'))}
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
n-ticový relační kalkul:
{k.názevk:KINO(k)&FILM(f)PROG(p) (p.jménof=f.jménof & p.názevk=k.názevk) f.země='USA'}
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Dvě kina s touž množinou filmů.
HRALO:=PROG[názevk,jménof] kino někdy hrálo film NEHRALO:=(KINO[názevk]×FILM[jménof]) \ HRALO kino nikdy nehrálo film
R:=HRALO(názevk->názevk1)* HRALO(názevk->názevk2) obě kina hrála film
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Dvě kina s touž množinou filmů.
S1:=HRALO(názevk->názevk1)*NEHRALO(názevk-> názevk2)
S2:=NEHRALO(názevk->názevk1)* HRALO(názevk-> názevk2) "rozdílové" tabulky
výsledek:= (R[názevk1,názevk2] \ S1[názevk1,názevk2] \ S2[názevk1,názevk2])[názevk1=1980][jménof])
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítány všechny filmy natočené po roce 1980.
doménový relační kalkul:
{k: KINO(názevk:k)& f (FILM(jménof:f ,rok>1980)  PROG(názevk:k, jménof=f))} KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítány všechny filmy natočené po roce 1980.
n-ticový relační kalkul:
{k.názevk:KINO(k)& FILM(f)(f.rok>=1980 PROG(p)(p.jménof=f.jménof)& (p.názevk=k.názevk)) } KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
Algebra:
KINO[názevk] \ ((KINO*FILM*PROG)[země'USA'])[názevk] KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
doménový relační kalkul:
{k:KINO(názevk:k)&f(PROG(jménof:f,názevk=k)FILM(jménof:f,země:'USA'))}
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Kino, kde promítají pouze americké filmy.
n-ticový relační kalkul:
{k.názevk:KINO(k)&FILM(f)PROG(p) (p.jménof=f.jménof & p.názevk=k.názevk) f.země='USA'}
KINO(názevk,majitel,kapacita) FILM(jménof,rok,země) PROG(jménof,názevk,datum)
Dvě kina s touž množinou filmů
{(k1,k2): f (PROG(názevk:k1,jménof:f) PROG(názevk:k2,jménof:f)) }
ÚKOL(IdÚ,VedÚ) PRAC(IdP,Bydliště) DÍLO(IdÚ,IdP)
Kteří pracovníci se podílejí na všech úkolech řešených jen pražskými pracovníky?
 DÍLO  ( DÍLO [IdÚ] \ ( DÍLO * ( PRAC[Bydliště ‘Praha‘] [IdP] ) [IdÚ] ) )
ÚKOL(IdÚ,VedÚ) PRAC(IdP,Bydliště) DÍLO(IdÚ,IdP)
Které dvojice pracovníků nespolupracují ani na jediném úkolu?
{ (p.IdP,q.IdP) : PRAC(p) & PRAC(q) &  DÍLO(d)  DÍLO(f) ( (d.IdP= p.IdP & f.IdP= q.IdP)  d.IdÚ  f.IdÚ ) }
 
ÚKOL(IdÚ,VedÚ) PRAC(IdP,Bydliště) DÍLO(IdÚ,IdP)
Které dvojice pracovníků ře