4. Relační algebra Databáze použité v příkladech FIRMA ZAMĚSTNANEC (Číslo, Příjmení, Jméno, Pohlaví, Plat, Oddělení, Nadřízený) ODDĚLENÍ (Číslo, Název, Místo, Vedoucí) PROJEKT (Číslo, Název, Oddělení) PRÁCE (Číslo, Zaměstnanec, Projekt, Hodiny) DÍTĚ (Číslo, Rodič, Jméno) KNIHOVNA KNIHA (CisloKnihy, Název, Autor, Ţánr, Rok) ŢÁNR (Id, Název) VÝTISK (EvidCislo, CisloKnihy, Nakladatel, Pořízeno, Cena, Jazyk) AUTOR (Id, Příjmení, Jméno, Stát) ČTENÁŘ (Id, Příjmení, Jméno, Město, Ulice, PSČ, DatumOd, DatumDo) VÝPŮJČKA (Id, Výtisk, Čtenář, Půjčeno, Vráceno ) REZERVACE (Id, CisloKnihy, Čtenář, Datum) NAKLADATELSTVÍ (Id, Název, Město, Stát) FILMY – nenormalizovaná DB filmů!!! KINO (NázevK, Adresa) PROGRAM (NázevK, JménoF, Datum) FILM (JménoF, Herec, Rok) BANKA – nenormalizovaná DB !!! KLIENT (Číslo, Jméno, Osoba, Adresa) POHYB (Druh, Konto, Identifikace, Datum, Měna, Částka) KONTO (Číslo, Majitel, Datum, Zůstatek, Měna)
Operace kartézský součin ( součin ) sjednocení průnik rozdíl projekce selekce ( restrikce ) spojení
x předpokládá kompatibilní operandy tj. stejný řád relací a rovnost domén, které si odpovídají specificky databázové operace x
Selekce selekční podmínka(jméno
relace)
jméno relace(selekční podmínka)
Příklad 4.1 : Relace ZAMĚSTNANEC (Osobní_číslo, Jméno, Příjmení, Adresa, Oddělení, Plat, Nadřízený) Vybereme podmnoţinu n-tic z relace ZAMĚSTNANEC, kteří pracují v oddělení 4 Oddělení = 4(ZAMĚSTNANEC)
Příklad 4.2 : Relace ZAMĚSTNANEC (Osobní_číslo, Jméno, Příjmení, Oddělení, Plat, Nadřízený) Vybereme podmnoţinu n-tic z relace ZAMĚSTNANEC, kteří mají plat menší neţ 15 000 Plat
15000(ZAMĚSTNANEC)
Relace, která je výsledkem selekce, má tytéţ atributy jako relace původní. Podmínka pouţitá v selekci můţe být tvaru Jméno atributu Jméno atributu
operátor porovnání operátor porovnání
Jméno atributu Konstanta
Operátor porovnání je z mnoţiny , , , , , , konstanta je z domény daného atributu. Podmínky mohou být libovolně spojovány pomocí AND, OR, NOT Příklad 4.3 : (Plat
10000 AND Oddělení =1) OR ( Plat 20000 AND Oddělení=3) (ZAMĚSTNANEC)
Selekce je komutativní tj. podm1( podm2(Relace))
=
podm2( podm1(Relace))
podm1( podm2...( podmn(Relace)..))=
podm1 AND podm2 AND …podmn(Relace)
Poznámka: Pořadí podmínek v konjunkci by mělo být stanoveno smysluplně – závisí na tom rychlost vyhodnocení dotazu Příklad 4.4: Výběr záznamů praţských zaměstnanců z oddělení 5 Předpoklad: firma má cca 1000 zaměstnanců, 10 oddělení pouze desetina není z Prahy předpokládáme rovnoměrné rozloţení zaměstnanců na odd. Adresa obsahuje 'Praha' ( Oddělení = 5 (ZAMĚSTNANEC))
Oddělení = 5
(
Adresa obsahuje 'Praha'
(ZAMĚSTNANEC))
cca 1000+100 porovnání cca 1000+900 porovnání
Projekce ΠSeznam atributů (Jméno relace) Jméno relace[Seznam atributů] Příklad 4.5 : Zajímají nás jména, příjmení a plat zaměstnanců
ΠJméno, Příjmení, Plat (ZAMĚSTNANEC) Příklad 4.6 : Názvy a sídla nakladatelství Relace NAKLADATELSTVÍ (Id_nakladatelství, Název, Město, Ulice, Stát, Majitel)
Π Název, Město, Stát (NAKLADATELSTVÍ) NAKLADATELSTVÍ [Název, Město, Stát ]
ΠSeznam atr1 (ΠSeznam atr2 (Jméno relace))= ΠSeznam atr1 (Jméno relace) platí jen tehdy, je-li seznam atr1 podmnoţinou seznam atr2. Příklad 4.7 :
ΠJméno, Příjmení, Plat (
Oddělení = 4(ZAMĚSTNANEC))
ZAMĚSTNANEC (Oddělení = 4)[Jméno, Příjmení, Plat] Můţeme pojmenovat jednotlivé výsledné relace a rozepsat
ODD4
(
Oddělení = 4(ZAMĚSTNANEC)
VYSLEDEK
ΠJméno, Příjmení, Plat (ODD4)
Příklad 4.8 :Vypsat čísla všech zaměstnanců, kteří buďto pracují na odd 5, nebo jsou přímými nadřízenými zaměstnance pracujícího na odd 5. ZAMĚSTNANEC (Číslo, Příjmení, Jméno, Město, Ulice, PSČ, Oddělení, Nadřízený)
ODD5_ZAM
(
Oddělení = 5(ZAMĚSTNANEC)
VYSL1
ΠČíslo (ODD5_ZAM)
VYSL2
ΠNadřízený(VYSL1)
VYSLEDEK
VYSL1 VYSL2
Množinové operace – sjednocení, průnik, rozdíl relací – dá se pouţít na kompatibilní relace.
Konvence – atributy výsledné relace označujeme jmény podle první relace, duplicitní záznamy se odstraňují ( při sjednocení )
Komutativita, asociativita R
S=S
R, (R
R
S=S
R, R
S) (S
T=S
(R
T)=(R
S)
T) T
Kartézský součin ( kříţový součin, kříţové spojení ) nevyţaduje kompatibilní operandy. Výsledek R( A1, A2 , . . . , Aa ) x S( B1, B2 , . . . , Bm ) je relace Q (A1, A2 , . . . , Aa, B1, B2 , . . . , Bm ), která má n+m atributů a obsahuje záznam pro kaţdou kombinaci záznamů vţdy jeden z R a druhý z S. Příklad 4.9 : Potřebujeme vypsat seznam dětí všech zaměstnaných ţen
ŢENY_ZAM ŢENY
Pohlaví = „Z“ (ZAMĚSTNANEC)
ΠČíslo, Jméno, Příjmení (ŢENY_ZAM)
DĚTI_ŢEN ŢENY x DĚTI AKT_DĚTI
Číslo = Číslo_ rodiče (DĚTI_ŢEN)
VYSLEDEK
Π Jméno, Příjmení, Akt_děti.Jméno (AKT_DĚTI)
SPOJENÍ se pouţívá, pokud potřebujeme zkombinovat související (navzájem si odpovídající) záznamy ze dvou relací do jediného záznamu. Příklad 4.10: Vypsat jména, příjmení manaţerů včetně oddělení, které vedou Relace ZAMĚSTNANEC (Osobní_číslo, Jméno, Příjmení, Oddělení, Plat, Nadřízený) ODDĚLENÍ (Číslo, Název, Vedoucí)
MANAŢER ODDĚLENÍ |×| Vedoucí = Číslo ZAMĚSTNANEC VYSLEDEK
Π Jméno, Příjmení, Název (MANAŢER)
Příklad 4.10‘ : pomocí jiného způsobu zápisu (ZAMĚSTNANEC [Číslo = Vedoucí]ODDĚLENÍ)[Jméno, Příjmení, Název]
Příklad 4.11: Vypsat názvy knih, které má vypůjčeny čtenář Petr Svoboda databáze KNIHOVNA z příkladu 3.16
PŮJČENO
Vráceno = null
VÝPŮJČKY_S
(
VÝPŮJČKA
Příjmení='Svoboda' AND Jméno='Petr'
ČTENÁŘ)
|×| Číslo průkazky=Čtenář PŮJČENO VÝTISKY _S VYDÁNÍ_S NÁZVY_S
Π Evidenční_číslo (VÝPŮJČKY _S * VÝTISK) Π Kniha (VÝTISKY _S |×| Vydání = Číslo_vydání VYDÁNÍ) Π Název (VYDÁNÍ _S * KNIHY)
Obecně
R × Spojovací podmínka S R [Spojovací podmínka] S Výsledek spojení R( A1, A2 , . . . , Aa ) a S( B1, B2 , . . . , Bm ) je relace Q (A1, A2 , . . . , Aa, B1, B2 , . . . , Bm ), Q obsahuje jeden záznam pro kaţdou kombinaci záznamů – vţdy jeden z R a jeden z S -tak, ţe tato kombinace vyhovuje spojovací podmínce. Ještě obecněji spojovací podmínka můţe mít formu Podmínka1 AND podmínka2 AND . . . . podmínkan , kde kaţdá podmínka je tvaru Ai θ Bj , Ai je atribut z R, Bj je atribut z S, Ai a Bj mají tutéţ doménu a θ je jeden z operátorů , , , , , tzv. THETA SPOJENÍ EQUIJOIN – spojení přes rovnost PŘIROZENÉ SPOJENÍ (*)
Příklad 4.12: Relace ODDĚLENÍ (Číslo_odd, Název, Vedoucí) PROJEKT (Číslo, Název, Číslo_odd, Datum_zahájení) ODD ODDĚLENÍ (Číslo_odd, Název) PROJ_ODD PROJEKT * ODD Atribut Číslo_odd se nazývá spojující atribut
Příklad 4.13: Najít adresu kina, kde je na programu Forest Gump Relace KINO (NázevK, AdresaK) PROGRAM (NázevF, NázevK, Datum, Hodina) NázevK, AdresaK
(
NázevK
(
NázevF = “Forest Gump“
(PROGRAM)) * KINO)
Obecná definice přirozeného spojení
Q R* ( seznam1 ) , ( seznam2 ) S V tomto případě seznam1 specifikuje seznam i atributů z R a seznam2 určuje seznam i atributů z S. Seznamy jsou pouţity k sestavení podmínek testujících shodnost mezi dvojicemi odpovídajících atributů, podmínek jsou pak spolu spojeny pomocí spojky and.Ve výsledné relaci jsou ponechány pouze atributy ze seznamu1. Můţe se stát, ţe výsledkem bude prázdná relace. Obecně, pokud R se skládá z nR n-tic a S z ns n-tic, můţe mít výsledek spojující operace mezi R a S celkem 0 aţ nR * nS n-tic. Poměr mezi výsledkem spojení a maximální hodnotou nR * nS udává tzv. spojovací selektivitu, coţ je vlastnost kaţdé spojovací podmínky. Není-li uvedena ţádná spojovací podmínka, dostáváme vlastně kartézský součin – kříţové spojení. Operace relační algebry , , , , tvoří úplnou množinu, neboť kaţdá další operace relační algebry se dá vyjádřit jako kombinace těchto operací.
R
S
(R
S ) – (( R – S )
R × Spojovací podmínka S
( S – R ))
selekční podmínka(RxS)
Polospojení Levé polospojení relací se schématy R(A) a R(B) se dá definovat pomocí spojení a projekce jako A
( R × t1
t2
S)
dle jiného způsobu zápisu
R < t1
t2 ] S = (R [ t1
t2 ] S ) [A]
Pravé polospojení Polospojení přes rovnost – polospojení přes rovnost vybraných společných atributů Přirozené polospojení – polospojení přes rovnost všech společných atributů
Příklad 4.14 : R
A 8 1 1 3 3 7
B 2 2 1 6 8 2
C 3 3 4 7 9 5
S
B 2 2 1 2
C 4 3 4 3
D 2 2 5 4
U
A 8 1 1
B 2 2 1
C 3 3 4
E 3 3 6 7
T je levé polospojení R < A
A 1 1
B 2 1
C 3 4
U je levé přirozené polospojení přes atributy B, C
Příklad 4.15 : Najdi kina, kde nedávají ţádný film s Michel Pffeifer KINO[NázevK] – ((FILM(Herec=”Pffeifer Michel”)[NázevF])*(PROGRAM[NázevK, NázevF]))[NázevK] Strom dotazu příkladu 4.15
[NázevK]
[NázevK]
KINO
* [NázevF] (Herec = “Pffeifer Michel“)
FILM Vnější spojení levé ( event. pravé ) Přirozené vnější spojení
[NázevK, NázevF]
PROGRAM
N-ticový relační kalkul pouţívá přirozený pohled na relaci jako na mnoţinu n-tic (řádků, záznamů ) Termy
- n-ticové proměnné - komponenty n-ticových proměnných ( tečková notace ) - atomické konstanty ( hodnoty přímo z nějaké domény )
Predikátové symboly
,
,
,
,
,
NRK je zaloţen na pojmu formule ( podobný smysl jako v predikátové logice ) Atomická formule
R(x) x.A x.A
R relace, x n-ticová proměnná A, B atributy, x, y n-ticové proměnné k konstanta
y.B k
Logické spojky and, or, not, implies Příklad 4.16 : dotaz „najdi adresy všech kin“ x.Adresa where KINO(x) jiná syntaxe ( vlastně projekce
Adresa
( KINO) )
Příklad 4.17 : dotaz „najdi všechny herce hrající ve filmu “Top Gun“ film.Herec where FILM(film) and film.NázevF =“ Top Gun“ ( vlastně selekce a projekce
Herec
(
NázevF = “Top Gun“
(FILM)) )
Příklad 4.18 : Najdi všechna kina, kde hrají film “Matrix” x.NázevK where PROGRAM(x) and x.NázevF=“Matrix”
Příklad 4.19 : Najdi všechny praţské firmy mající konto v bance x.Jméno where KLIENT(x) and x.Adresa like “Praha” and x.Osoba=”P” Obecně dotazy mají tvar : Kvantifikátory
seznam komponent-proměnných where formule
existenční univerzální
exists forall
Příklad 4.20: p.Název_k where PROGRAM(p) and exists f ( FILM(f) and p. NázevF = f. NázevF and f.Herec = “Hanks Tom“ )
Příklad 4.21: p.NázevF where PROGRAM(p) and forall x (PROGRAM(x) implies exists y (PROGRAM(y) and y.NázevK = x.NázevK and p.NázevF = y. NázevF) ) Zobecnění
exists x (F(x))
(1)
přepíšeme, pokud omezíme x na relaci R jako exists x ( R(x) and F’(x) )
(2)
podobně forall x ( F(x) )
(3)
zobecníme jako forall x ( R(x) and F’(x) )
(4)
kde výrazy (2) a (4) definují tzv. omezené kvantifikátory, které můţeme psát jako exists x
R ( G(x) )
forall x
R ( G(x) )
kde formule G neobsahuje výskyty proměnné x s kvantifikátory exists nebo forall Příklad 4.22: p.NázevK where PROGRAM(p) and forall f
FILM (f .Herec=“Gibson Mel“ implies exists q
PROGRAM
(q.NázevK=p.NázevK and q.NázevF=f.NázevF))
Příklad 4.23: p.NázevK where PROGRAM(p) and forall f
FILM (f .Herec=“ Gibson Mel“ implies not exists q
(q.NázevK=p.NázevK and q.NázevF=f.NázevF))
PROGRAM
Doménový relační kalkul Souvisí těsněji s predikátovou logikou, pouţívá jednoduché proměnné. Je-li R( A, B, C ) schéma relace, pak R(x, y, z) znamená totéţ jako R(u) v n-ticovém kalkulu. Atomické formule se zapisují i s atributy (konvence zajišťující nezávislost atributů na pořadí) tj. místo R(x, y, z) píšeme R(A:x, B:y, C:z) Termy - proměnné a konstanty Atomické formule
R(A1:t1 , A2:t2 , . . . , An:tn) t1
t2
Formule se tvoří stejně jako v NRK, princip vyuţití formulí v dotazech je podobný jako v NRK. Příklad 4.24: projekce adr where exists k ( KINO ( NázevK :k, Adresa:adr )) Příklad 4.25: selekce h where exists r ( FILM (NázevF: “Titanic“, Herec : h, Rok : R ) ) Příklad 4.26: spojení nazK, adr, nazF, dat where ( PROGRAM ( NázevK : nazK, NázevF: nazF, Datum:dat) and KINO ( NázevK:nazK, Adresa: adr ) ) Konvence vynechávat exists ve formulích tvaru exists x ( R( . . . , A:x, . . . ) , kde x není vícekrát ve formuli Příklad 4.27 :
adr where ( KINO ( Adresa : adr ) ) h where ( FILM (NázevF: “Titanic“, Herec : h ) )
Příloha 1 : část relačního schématu BANKA – uvaţujme následující relace KLIENT
Číslo 00001 00002 00003 00004 00005 00006 00007
Jméno Suchánek Jakub GAMA s. r. o. ALEA s. r. o. Vrána Jiří EKOSTAV a. s. Janoušek Pavel Dvorský Petr
POHYB
Druh
Účet
Identifikace
Datum
Měna
1 2 2 1 1 1 2 2 2 2 2 1 1 1
AX 00112233 AX 00221111 BX 01010202 BX 03132333 CX 01010100 CX 22112244 BX 03132333 CX 01010100 AX 45674567 BX 00025678 BX 00032345 BX 00121444 AX 00221111 CX 01010100
001 003 001 133-66-89/0100 199-58-699/0800 2951-856/4200 002 001 17-44-694/7100 19-25-169/7100 135-1587/4200 17-258-23/7100 148-568/0600 126-235/0800
12.09.97 13.09.97 14.09.97 13.09.97 14.09.97 15.09.97 16.09.97 17.09.97 18.09.97 19.09.97 11.09.97 13.09.97 14.09.97 15.09.97
CZK DEM GBP DEM ATS ATS CND DEM DEM DEM ITL DEM USD CZK
ÚČET
Číslo AX 00112233 AX 00221111 AX 12345678 AX 32132132 AX 45674567 BX 00025678 BX 00032345 BX 00121444 BX 00123123 BX 01010202 BX 03132333 CX 01010100 CX 22112244
Majitel 00001 00004 00006 00001 00006 00002 00005 00005 00002 00003 00005 00003 00005
Osoba F P P F P P F
Datum 25.01.1996 17.04.1994 29.07.1995 24.05.1997 28.10.1996 17.04.1998 19.07.1996 27.12.1997 08.11.1993 14.03.1987 25.02.1987 30.05.1970 18.06.1970
Adresa Praha, Dukelská 10 Brno, Blahoslavova 113 Písek, Praţská 1425 Praha, Vladislavova 1512 Č. Budějovice, Lidická 12 Písek, Táborská 177 Č. Budějovice, Česká 501
Zůstatek 25 000 175 000 80 000 12 000 235 000 758 000 4 250 600 78 000 115 000 175 000 265 000 1 250 000 758 000
Měna CZK DEM USD DEM CZK CZK ATS GBP ATS NLG DEM CZK CZK
Částka 17 500 24 860 13 500 28 600 65 000 19 800 7 200 29 500 36 400 145 000 25 150 000 24 300 49 100 2 564 000
Příloha 2 : část relačního schématu FILMOVÁ DISTRIBUCE – uvaţujme následující relace
KINO
NázevK Vesmír Orion Blaník Ponrepo
PROGRAM NázevK Vesmír Vesmír Vesmír Orion Orion Orion Orion Orion Orion Orion Blaník Blaník Blaník Ponrepo FILM
Adresa ČB, Lannova 110 Písek, Blahoslavova 113 ČB, Lidická 12 Tábor, Česká 501
NázevF Kolja Forest Gump Forest Gump Titanic Smrtonosná zbraň Matrix Top Gun Forest Gump Síť Apollo 13 Nebezpečné myšlenky Matrix Matrix Kleopatra
NázevF Kolja Forest Gump Nebezpečné myšlenky Apollo 13 Smrtonosná zbraň Smrtonosná zbraň Kleopatra Kleopatra Top Gun Top Gun Titanic Titanic Síť Nebezpečná rychlost Nebezpečná rychlost Matrix
Datum 12.09.2007 13.09.2007 14.09.2007 13.09.2007 14.09.2007 15.09.2007 16.09.2007 17.09.2007 18.09.2007 19.09.2007 11.09.2007 13.09.2007 14.09.2007 15.09.2007
Herec Svěrák Zdeněk Hanks Tom Pfeiffer Michel Hanks Tom Gibson Mel Glover Dan Burton Richard Taylor Elisabeth Cruise Tom Kilmer Val DiCaprio Leonardo Winslet Kate Bullock Sandra Bullock Sandra Reeves Keanu Reeves Keanu
Rok 1996 1994 1995 1993 1987 1987 1970 1970 1986 1986 1997 1997 1995 1994 1994 1999
Ještě několik příkladů na závěr NRK 1. Vypsat, které filmy z roku 1998 se hrají v kině Blaník p.JménoF where (PROGRAM(p) and p.NázevK=”Blaník and exists f (FILM(f) and f. NázevF =p. NázevF and f.Rok=1998) 2. Vypsat firmy, které mají pouze devizová konta k.Jméno where KLIENT(k) and k.osoba=”P” and not exists t ( t.majitel=k.číslo and t.kod=”CZK”)
ÚČET
2’. Vypsat firmy, které mají pouze devizová konta k.Jméno where KLIENT(k) and k.osoba=”P” and forall t ( t.majitel=k.číslo implies t.kod <>”CZK”)
ÚČET
3. Zjistit jména lidí (fyzických osob), kteří měli v uplynulém měsíci jednotlivý příjem více než 1000000 Kč k.Jméno where KLIENT(k) and k.osoba=”F” and exists t (ÚČET (t) and t.majitel=k.cislo and exists p (POHYB(p) and p.Účet=t.cislo and p.Druh=1 and p.Mena=”CZK” and p.Castka>1000000))
Relační algebra 3.
((POHYB(Druh=1 and Měna =”CZK” and Částka>1000000)) [Účet= Číslo] ÚČET [Majitel=Číslo] (KLIENT(osoba=”F”) [Číslo,Jméno])) [Jméno]
3.
jiná notace Jméno
(
osoba=”F” KLIENT)* Majitel=Číslo ÚČET
Druh=1 and Měna =”CZK” and Částka>1000000 POHYB)
* Číslo=Účet(
3’. Jméno
(
Jméno,Číslo
* Majitel=Číslo * Číslo=Účet
(
(
(
osoba=”F” KLIENT))
Číslo, Majitel ÚČET) Účet(
Druh=1 and Měna =”CZK” and Částka>1000000 POHYB))
DRK 4. Film, který dávají ve všech kinech, kde něco hrají f where forall k (PROGRAM (NázevK:k) implies PROGRAM (NázevF:f, NázevK:k)) f where not exists k (PROGRAM (NázevK:k) and not PROGRAM (NázevF:f, NázevK:k)) 5. Kino, v němž nedávají žádný film k where not exists f (FILM (NázevF:f) and PROGRAM (NázevF:f, NázevK:k)) 6. Kino, kde dávají všechny filmy s Keanu Reevesem k where forall f (FILM (JménoF:f, Herec:”Reeves Keanu”) implies PROGRAM (NázevK:k, NázevF:f))
Literatura: [1] ELMASRI, R., NAVATHE, S., B. Fundamentals of Database Systems, 5th edition. AddisonWesley, 2007. ISBN 978-03-213-6957-4. [2] SILBERSCHATZ, A., KORTH H. F., SUDARSHAN S. Database System Concepts, 5th edition, New York: McGraw-Hill, 2006. ISBN 978-0-07-295886-7 [3] CONOLLY, T., BEGG, C., HOLOWZAK R. Profesionální průvodce tvorbou databází. Praha: Computer Press, a. s., 2009. ISBN 978-80-251-2328-7. [4] HERNANDEZ, M., J. Návrh databází. Praha: Grada, 2006. ISBN 80-247-0900-7. [5] POKORNÝ, J. Databázová abeceda. Veletiny: Science, 1998, ISBN 80-86083-02-2. [6] POKORNÝ, J., HALAŠKA, I. Databázové systémy, 2. vydání. Praha Vydavatelství ČVUT, 2003, ISBN 80-01-02789-9.
