■r
4   Relace a jejich použití
V lekci si podrobně rozebereme matematický aparát relací (a funkcí), kterému se v jeho abstraktní podobě mnoho pozornosti v dřívější výuce nevěnuje - na rozdíl od naivního pohledu na množiny a na „funkce" ve významu analytických funkcí (jako x + 1 či sinx). Přitom na pojem relace velmi brzy narazí každý informatik už jen při studiu dat a databází a její abstraktní podobu bude potřebovat.
EMPLOYEE table (source)
PROJECT table (target)
EMP ID	NAME	ADDR ID
103	John Doe	305
104	Jane Smith	226
. 0í	Tom Jones	274
PROJ ID	NAME	DESCRIP
379	Consultant	Smalltalk
42	Java Developer	Java Product
356	Magazine	Multimedia
PROJ_EMP table (relation table)
□
Source key
EMPID	PROJID
■104	356 -
-104	92
Ll05	356 —j
Target key
□
Stručný přehled lekce
* Co je relace a funkce. Reprezentace relací tabulkou a grafem
* Základní vlastnosti binárních relací nad množinou.
* Inverze relace, skládání relací a jeho význam.
Petr Hliněný, Fl MU Brno, 2016
1/21
Fl: IB000: Relace a jejich použití
Zopakování kartézského součinu
Definice: Kartézský součin dvou množin A, B definujeme jako množinu všech uspořádaných dvojic ze složek z A a B
Ax B = {(a, b) | a G A, 6 G B} .
Příklady {a, b} x {a} = {(a, a), (6, a)},
{c, d} x {a, 6} = {(c, a), (c, 6), (d, a), (d, 6)}.c
Definice kartézského součinu více množin: Pro každé A; G N definujeme
Ai x A2 x • • • x Ak = {(ai, a2, • • • , a&) | a^G     pro každé 1 < i < k}
Například Z3 = ZxZxZ = {(i, j, fc) | i, j,fc G Z}
Petr Hliněný, Fl MU Brno, 2016
2/21
Fl: IB000: Relace a jejich použití
-FZ
Relace a funkce nad množinami
Vedle množin jsou dalším důležitým základním „datovým typem" matematiky relace, kterým vzhledem k jejich mnohotvárnému použití v informatice věnujeme významnou pozornost v této i příští lekci.
Definice 4.1. Relace mezi množinami Ai,^,--- ,pro k £ N, je libovolná podmnožina kartézského součinu
R ^ Ai x A2 x • • • x Ak .□
Pokud A\ — A2 — • • • = Ak = A, hovoříme o k-ární relaci R na A.
Příklady relací.
• {(1, a), (2, a), (2, b)} je relace mezi {1, 2, 3} a {a, b}.
• {(i, 2 - i) \ i E N} je binární relace na N.c
• {(i, j, i + j) | i, j G N} je ternárnírelace na N.
• {3 • z | z G N} je unární relace na N.c
• Jaký význam vlastně mají unární a nulární relace na A?
Petr Hliněný, Fl MU Brno, 2016
3/21
Fl: IB000: Relace a jejich použití
Funkce mezi množinami
Definice 4.2. (Totální) funkce z množiny A do množiny B
je relace / mezi A a B taková, že pro každé x G A existuje právě jedno y G B
takové, že (x, y) G /.□
Množina A se nazývá definiční obor b množina B obor hodnot funkce /.
Neformálně řečeno, ve funkci / je každé „vstupní" hodnotě x přiřazena jednoznačně „výstupní" hodnota y. (V obecné relaci počty „přiřazených" dvojic neomezujeme...)
Petr Hliněný, Fl MU Brno, 2016
4/21
Fl: IB000: Relace a jejich použití
■r
Značení: Místo (x, y) G / píšeme obvykle f (x) = y.
Zápis / : A —> B říká, že / je funkce s def. oborem A a oborem hodnot B.c Funkcím se také říká zobrazení.
Příklady funkcí jsou třeba následující.
• Definujeme funkci / : N —> N předpisem f (x) = x + 8.
Pak / = {(>, x + 8) | x G N}.n
• Definujeme funkci plus :NxN^N předpisem plus (i, j) = i + j. Pak plus = {(i, j, i + j) | i, j G N}.
Petr Hliněný, Fl MU Brno, 2016
5/21
Fl: IB000: Relace a jejich použití
Parciální (částečné) funkce
Definice: Pokud naši Definici 4.2 upravíme tak, že požadujeme pro každé x G A nejvýše jedno y G B takové, že (x, y) G /, obdržíme definici parciální funkce z A do B.
V parciální funkci / nemusí být pro některé „vstupní" hodnoty x funkční hodnota definována (viz například f (2) v uvedeném obrázku).
Pro nedefinovanou hodnotu používáme znak _L
Petr Hliněný, Fl MU Brno, 2016
6/21
Fl: IB000: Relace a jejich použití
Nasleduje několik příkladů parciálních funkcí. • Definujeme parciální funkci / : Z —> N předpisem
f(x) =
3 + x jestliže x > 0. _L jinak.
Tj. / = {(x,3 + x) | x G N}. □
Také funkce / : R —> R daná běžným analytickým předpisem
/(z) logx
je jen parciální - není definována pro x < O.c
Co je relace, přiřazující lidem v ČR jejich (česká) rodná čísla?
Petr Hliněný, Fl MU Brno, 2016
7/21
Fl: IB000: Relace a jejich použití
4.2   Reprezentace konečných relací
Ukládání dat — především sleduje vztahy mezi objekty (stejně jako relace). ^    relační databáze jako obecná ukázka použití relace.
Příklad 4.3. Tabulka relační databáze prezentuje obecnou relaci.
Definujme následující množiny („elementární typy")
• ZNAK = {a, • • • , z, A, • • • , Z, mezera},
• ČÍSLICE = {0,1,2, 3,4, 5, 6, 7,8,9}.□
Dále definujeme tyto množiny („odvozené typy")
• JMÉNO = ZNAK15,     PŘÍJMENÍ = ZNAK20,     VEK = ČÍSLICE3,
• ZAMESTNANEC „G" JMÉNO x PŘÍJMENÍ x VEK.□
Relaci „typu" ZAMESTNANEC pak lze reprezentovat tabulkou:
jméno	příjmení	VEK
Jan	Novák	42
Petr	Vichr	28
Pavel	Zima	26
Stanislav	Novotný	52
□
Petr Hliněný, Fl MU Brno, 2016
8/21
Fl: IB000: Relace a jejich použití
Reprezentace binárních relací na množině
Značení: Binární relaci R C M x M lze jednoznačně znázornit jejím grafem:
• Prvky M znázorníme jako body v rovině.
• Prvek (a, b) £ R znázorníme jako orientovanou hranu („šipku") z a do b. Je-li a — b, pak je touto hranou „smyčka" na a.c
Například mějme M = {a, 6, c, d, e, /} a R = {(a, a), (a, 6), (6, c), (6, (i), (6, e), (6, /), (d, c), (e, c), (/, c), (e, oř), (e, /), (/, b)}, pak:
c
Pozor, nejedná se o „grafy funkcí" známé třeba z matematické analýzy. □
V případě, že M je nekonečná nebo „velká", může být reprezentace R jejím grafem nepraktická (záleží také na míre „pravidelnosti" R).
Petr Hliněný, Fl MU Brno, 2016 9/21 Fl: IB000: Relace a jejich použití
Značení: Binární relaci R C M x M \ze jednoznačně zapsat také pomocí matice relace - matice A typu M x M s hodnotami z {0,1}.
a
d
c
a	í1	1	0	0	0	
b	0	0	1	1	1	1
c	0	0	0	0	0	0
d	0	0	1	0	0	0
e	0	0	1	1	0	1
f		1	1	0	0	0/
= A
□
A závěrem se můžeme opět vrátit k reprezentaci tabulkou. ..
jméno	příjmení
Jan	Novák
Petr	Vichr
Pavel	Zima
Stanislav	Novotný
Petr Hliněný, Fl MU Brno, 2016
10/21
Fl: IB000: Relace a jejich použití
4.3   Vlastnosti binárních relací na množině Definice 4.4.   Nechť RCM x M. Binární relace R je
• reflexivní, právě když pro každé a G M platí (a, a) G iž;
• ireflexivní, právě když pro každé a G M platí (a, a) 0 iž;
□
symetrická, právě když pro každé a, 6 G M platí, že jestliže (a, 6) G iž, pak také (6, a) G iž;
a
antisymetrická,  právě když pro každé a, 6   G   M platí, že jestliže
(a, 6), (6, a) G iž, pak a — b\
a
b
Petr Hliněný, Fl MU Brno, 2016
11/21
Fl: IB000: Relace a jejich použití
■r
• tranzitivní, právě když pro každé a, 6, c G M platí, že jestliže (a, 6), (6, c) G iž, pak také (a, c) G R.
Následují dva základní typy binárních relací; kde i? je
• relace ekvivalence, právě když je R reflexivní, symetrická a tranzitivní^
• částečné uspořádání, právě když je R reflexivní, antisymetrická a tranzitivní (často říkáme jen uspořádání).
Pozor, může být relace symetrická i antisymetrická zároveň? nAno!
a
b
c
□
Petr Hliněný, Fl MU Brno, 2016
12/21
Fl: IB000: Relace a jejich použití
Ukázkové binární relace
Příklad 4.5. Několik příkladů relací definovaných v přirozeném jazyce.
Nechť M je množina všech studentů 1. ročníku Fl. Uvažme postupně relace R C M x M definované takto
• (x, y) G R právě když x a y mají stejné rodné číslo;
• (x, y) G R právě když x má stejnou výšku jako y (dejme t. na celé mm);c
• (x, y) G R právě když výška x b y se neliší více jak o 2 mm;c
• (x, y) G R právě když x má alespoň takovou výšku jako y;c
• (x, y) G Ä právě když x má jinou výšku než y (dejme tomu na celé mm);c
• (x, y) G R právě když x je zamilován(a) do y.c
Které z nich tedy jsou ekvivalencí nebo uspořádáním? □
Petr Hliněný, Fl MU Brno, 2016
13/21
Fl: IB000: Relace a jejich použití
Příklad 4.6. Jaké vlastnosti mají následující relace?
• Buď fiCNxN definovaná takto G R právě když x dělí y x (Částečné uspořádání, ale ne každá dvě čísla jsou porovnatelná.)
• Buď fiCNxN definovaná takto (x, y) G R právě když x a y mají stejný zbytek po dělení číslem 5. n(Ekvivalence.)
• Nechť F = {f I / : N —>> N} je množina funkcí. Buď R C FxF definovaná takto (/, g) G Ä právě když f (x) < g (x) pro všechna x. □(Ireflexivní, antisymetrická a tranzitivní, ale ne reflexivní - není uspořádáním.)
Co v případě, že naše relace některou z poptávaných vlastností nemá, ale nám by se ta vlastnost hodila? To řeší tzv. uzávěry relací:
• Reflexivní uzávěr přidá do relace všechny dvojice (x,x) nad množinou.
• Symetrický uzávěr zahrne do relace všechny obrácené dvojice k existujícím dvojicím, neboli všechna chybějící pokud (y, x) G R.
• Tranzitivní uzávěr nelze popsat až tak jednoduše, ale stručně řečeno přidává do relace všechny ty dvojice pro které se lze (v grafu relace) dostat z x do y „po šipečkách".
Petr Hliněný, Fl MU Brno, 2016
14/21
Fl: IB000: Relace a jejich použití
4.4   Inverzní relace a skládání relací
Ve výkladu se nyní vrátíme k obecnému pojetí relací mezi množinami.
Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci R se značí R~x a je definována takto:
R-1 = {(6, a) | (a, b) 6 iž}
Petr Hliněný, Fl MU Brno, 2016
15/21
Fl: IB000: Relace a jejich použití
Definice skládání
Definice 4.7. Složení (kompozice) relací R a S.
Nechť RCAxBaSCBxC jsou binární relace. Složení relací R a S (v tomto pořadí!) je relace S o R C A x C definovaná takto:c
S o R = {(a, c)   existuje b £ S takové, že (a, 6) £ iž, (6, c) £ £}
Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „5 po iž".
Petr Hliněný, Fl MU Brno, 2016
16/21
Fl: IB000: Relace a jejich použití
■r
Několik matematických příkladů skladaní relací nasleduje zde.
• Je~'' *A = {a,b},   B = {1,2},   C = {X,Y},
* R = {(a, 1), (b, 1), (b, 2)},   S = {(l,X)}, pak složením vznikne relace
* SoR = {(a,X),(b,X)}. □
• Složením funkcí h(x) = x2 a f (x) = x + 1 na R vznikne funkce
(f o h) (x) =f(h(x)) = x2 + l.u
• Složením těchže funkcí „naopak" ale vznikne funkce
(h o f) (x) = h(f (x)) = (x + lf.u
Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skladaní zobrazení) se setkáme s právě opačným zápisem skládání, kdy se místo S o R píše R • S nebo jen RS.
Petr Hliněný, Fl MU Brno, 2016
17/21
Fl: IB000: Relace a jejich použití
r
Tvrzení 4.8. Nechť RCAxBaSCBxC jsou binární relace. Pak inverzí složené relace S o R je relace
A B
R:
C
:S
vy
(S o R)'1 = nR-1 o S'1.
Petr Hliněný, Fl MU Brno, 2016
18/21
Fl: IB000: Relace a jejich použití
4.5   Skládání relací „v praxi"
Příklad 4.9. Skládání v relační databázi studentů, jejich předmětů a fakult.
Mějme dvě binární relace - jednu R přiř. studentům MU kódy jejich zapsaných předmětů, druhou S přiř. kódy předmětů jejich mateřským fakultám.
R :
student (učo)	předmět (kód)		předmět (kód)	fakulta MU
121334	MA010		MA010	Fl
133935	M4135	S :	IB000	Fl
133935	IA102		IA102	Fl
155878	M1050		M1050	PřF
155878	IB000		M4135	PřF
Jak z těchto „tabulkových" relací zjistíme, kteří studenti mají zapsané předměty na kterých fakultách (třeba na Fl)?
Jedná se jednoduše o složení relací S o R. V našem příkladě třeba:
SoR :
student (učo)	fakulta MU
121334	Fl
133935	Fl
133935	PřF
155878	Fl
155878	PřF
Petr Hliněný, Fl MU Brno, 2016
19/21
Fl: IB000: Relace a jejich použití
Zobecněné skládání relací
Definice: (skládání relací vyšší arity): Mějme relace T C K\ x K2 x • • • x Kk
a U C Li x Z/2 x • • • x Lč, přičemž pro nějaké m < min(fc,^) platí Li = Ä&_m+i, L2 = Kk_m+2, • • • 5 — íífe- ^Pak relaci T lze s/oz/ŕ s relací Č7 na zvolených m složkách Li,... ,Lm („překrytí") s použitím Definice 4.7 takto:
• Položme A = K\ x • • • xKk-m, B = L\ x • • • xLm a C = Lm+i x • • • xl^.
• Příslušné relace pak jsou
* R =      6) G A x B I (ai,... a^_m, 61,... bm) G T} a
* S = {(b,Č) e B x C \ (6i,...6m,cm+i,...q) G f/}. □
• Nakonec přirozeně položme U omT ~ S o R, takže vyjde U omT —
{(a, č) I ex. 6 G 5, že (au .. .ak-m, 61,... 6m) G T a (61,... 6m,cm+i,... q) G í/} . Schematicky pro snadnější orientaci:
?7 C U omT C
\KX x • • • X ZÍ/c-mX    Kk_m+1 x       x Kk		
	Li    x • • • x Lm    xLm+i x • • • x L£	
[^1 X • • • X Zífc-ml x                                        x Lm+i x • • • x L£ b               v                A            s-v-'            K /I		
Petr Hliněný, Fl MU Brno, 2016 20/21 Fl: IB000: Relace a jejich použití
Příklad 4.10. Skládání v relační databázi pasažérů a letů u let. společností.
Podívejme se na příklad hypotetické rezervace letů pro cestující, relace T. Jak známo (tzv. codeshare), letecké společnosti si mezi sebou „dělí" místa v letadlech, takže různé lety (podle kódů) jsou ve skutečnosti realizovány stejným letadlem jedné ze společností. To zase ukazuje relace U.
T :
pasažér	datum	let		datum	let	letadlo
Petr	5.11.	OK535		5.11.	OK535	CSA
Pavel	6.11.	OK535	U :	5.11.	AF2378	ČSA
Jan	5.11.	AF2378		5.11.	DL5457	ČSA
Josef	5.11.	DL5457		6.11.	OK535	AirFrance
Alena	6.11.	AF2378		6.11.	AF2378	AirFrance
Ptáme-li se nyní, setkají se Petr a Josef na palubě stejného letadla? Případně, čí letadlo to bude? Odpovědi nám dá složení relací U o2T, jak je popsáno výše.
pasažér	letadlo
Petr Josef Pavel	CSA ČSA AirFrance
□
Petr Hliněný, Fl MU Brno, 2016
21/21
Fl: IB000: Relace a jejich použití