■r
5   Relace a jejich vlastnosti
V následující lekci si podrobně rozebereme matematický aparát relací, 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 2x, sinx). Přitom na pojem relace velmi brzy narazí každý informatik už jen při studiu dat a databází a jeho pochopení bude nezbytně 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 - reprezentace relací tabulkou a grafem
* Základní vlastnosti binárních relací nad množinou.
* Uzávěry relací. Tranzitivní relace.
Petr Hliněný, Fl MU Brno, 2017
1/15
Fl: IB000: Relace a jejich použití
Zopakování kartézského součinu a relace
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,b G 5}
Definice kartézského součinu více množin: Pro každé A; G N definujeme
Ai x A2 x • • • x Ak = {(ai, a,2, • • • , a*;) | a^G     pro každé 1 < i < k} .
• Například Z3 = ZxZxZ = {(ij,h) \ ij,k G Z}. □
Definice: Relace mezi množinami Ai,^,-- - ,pro A; G N, je libovolná podmnožina kartézského součinu
R C Ai x A2 x • • • x Ak .□
Pokud Ai = A2 = • • • = Ak = A, hovoříme o k-ární relaci R na A.
Petr Hliněný, Fl MU Brno, 2017
2/15
Fl: IB000: Relace a jejich použití
5.1   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 5.1. 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, 2017
3/15
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ě (tj. na papíre).
• 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íře „pravidelnosti" R).
Petr Hliněný, Fl MU Brno, 2017 4/15 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, 2017
5/15
Fl: IB000: Relace a jejich použití
5.2   Vlastnosti binárních relací na množině Definice 5.2.   Nechť RCM x M. Binární relace R je
• reflexivní, právě když pro každé a G M platí (a, a) G R]
• ireflexivní, právě když pro každé a G M platí (a, a) 0 iž;
<^ <x> □
• 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 «cf ^> b
Petr Hliněný, Fl MU Brno, 2017
6/15
Fl: IB000: Relace a jejich použití
r
antisymetrická,  právě když pro každé a, 6   £   M platí, že jestliže
(a, 6), (6, a) £ iž, pak a — b\
a
b
• tranzitivní, právě když pro každé a, 6, c G M platí, že jestliže (a, 6), (6, c) G R, pak také (a, c) G iž.
6
a
c
□
Pozor, může být relace symetrická i antisymetrická zároveň? i
Ano!
Petr Hliněný, Fl MU Brno, 2017
7/15
Fl: IB000: Relace a jejich použití
■r
Ukázkové binární relace
Příklad 5.3. Jak poznat vlastnosti relací z matice:
o o
i i
o o
0 0\
1 1 1 o
i V
/i i
o
1
0
1 1
0 0\
1 1
0 1
1 OJ
Které z vlastností mají binární relace reprezentované těmito maticemi?
Řešení: Ony vlastnosti si probereme jednu po druhé:
• Reflexivní, právě když každý prvek na hlavní diagonále je 1.
• Ireflexivní, právě když je její hlavní diagonála vyplněna nulami.
• Symetrická, právě když je „stejná" v zrcadlovém obraze podle hl. diagonály.
• Antisymetrická, právě když po „přeložení" matice podle hlavní diagonály nebudou nikde mimo tuto diagonálu dvě jedničky „na sobě".
Zbývá posoudit tranzitivitu, což není úplně jednoduché.
□
Petr Hliněný, Fl MU Brno, 2017
8/15
Fl: IB000: Relace a jejich použití
■r
Příklad 5.4. 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 x, y x, y x, y x, y x, y
G R právě když x a y mají stejné rodné číslo;c
G R právě když x má stejnou výšku jako y (dejme t. na celé mm);c
G R právě když výška x b y se neliší více jak o 2 mm;c
G R právě když x má alespoň takovou výšku jako y;c
G R právě když x má jinou výšku než y (dejme tomu na celé mm);c
G R právě když x je zamilován(a) do y.
□
Co dělat v situaci, že naše relace některou z poptávaných vlastností nemá, ale nám by se ta vlastnost hodila? V některých případech lze chybějící vlastnost relaci „doplnit" pomocí takzvaného uzávěru.
• Například reflexivní uzávěr jednoduše přidá do relace všechny dvojice (x, x\\
• Nebo symetrický uzávěr zahrne do relace všechny obrácené dvojice k existujícím dvojicím, čili všechny chybějící (x,y) pokud (y, x) G R.
Petr Hliněný, Fl MU Brno, 2017
9/15
Fl: IB000: Relace a jejich použití
5.3   Uzávěry relací
Princip uzávěru binární relace:
• Naší snahou je danou relaci „obohatit" o zvolenou vlastnost (například proto, že naše data o relaci jsou neúplná a vlastnost je tak poškozena).
• Pochopitelně, ne každou vlastnost relace lze získat přidáváním dalších dvojic; naše uvažovaná vlastnost musí být uzavíratelná.
Fakt: Libovolná kombinace vlastností reflexivita, symetrie, tranzitivita je uzavíratelná vlastnost.
Ireflexivita a antisymetrie nejsou uzavíratelné vlastnosti.
Věta 5.5. Necht V je uzavíratelná vlastnost binárních relací Pak existuje jednoznačná minimální relace Rv D R mající vlastnost V. Platí
Rv= f] S.
sdr, s má v na m
Tuto minimální relaci Rv s vlastností V nazýváme V-uzávěr relace R.
Petr Hliněný, Fl MU Brno, 2017
10/15
Fl: IB000: Relace a jejich použití
Tvrzení 5.6. Nechť R je binární relace na M. Pak platí následující poznatky.
• Reflexivní uzávěr R je přesně relace R U {(x, x) | x G M}.c
• Symetrický uzávěr R je přesně relace
R= {{x, y) | (z, y) G R nebo (y, x) G #}.□
• Tranzitivní uzávěr R je přesně relace R+ = U£i Tl(R), kde T je funkce, která pro každou binární relaci S vrátí relaci
T(S) =/SU{(x,z)    existuje y takové, že (x, y), (y, z) G 5}
a Tz = To • • • o T je z-krát iterovaná aplikace funkce T. v-v-'
z
• Reflexivní a tranzitivní uzávěr i? je přesně relace R* = Q+, kde Q je reflexivní uzávěr R.z
» Reflexivní, symetrický a tranzitivní uzávěr i? (tj. nejmenší ekvivalence ob-sáhující R) je přesně relace kde Q je reflexivní uzávěr Rx
Poznámka: Na pořadí aplikování uzávěrů vlastností záleží! Zhruba řečeno, tranzitivní uzávěr obvykle aplikujeme coby poslední.
Petr Hliněný, Fl MU Brno, 2017
11/15
Fl: IB000: Relace a jejich použití
Tranzitivní uzávěr
Závěrem sezastavíme nad případem tranzitivního uzávěru R+ — \j^=iT"l(R), jehož definice se nezdá až tak „konstruktivní" - co nekonečné sjednocení?
Tvrzení 5.7. Necht R je relace. Pak existuje přirozené m takové, že tranzitivní uzávěr relace R lze zapsat R+ = U™Li Tl(R). □
Důkaz: Pro něj si uvědomme zásadní fakt - pokud Tl+1(R) = Tl(R), tak už platí Ti+k(R) = V(R) pro všechna přirozená k. Neboli je potřeba sjednotit jen tolik prvních členů výrazu U£i Tl(R), dokud se hodnota Tl(R) „zvětšuje", což může nastat jen konečně krát nad konečnou množinou.
•-•-•
□
Petr Hliněný, Fl MU Brno, 2017
12/15
Fl: IB000: Relace a jejich použití
5.4   Tranzitivní relace
Mezi základními vlastnostmi relací popsanými Definicí 5.2 je jedna - tranzitivita, jejíž uchopení a zvládnutí je výrazně těžší než u ostatních vlastností.
• Definice reflexivity, symetrie či antisymetrie nám ihned řeknou, které dvojice v relaci chybí nebo přebývají.
• Avšak vlastnost tranzitivity je fundamentálně induktivní- všimněte si tranzitivního uzávěru, kde po každém přidání dvojice je nutno znovu podmínku tranzitivity kontrolovat, což „indukuje" nové dvojice k přidávání.
Tvrzení 5.8. Mějme relaci R na kon. množině M a necht R+ je tranzitivním uz. R. Pak pro každé x,y G M platí (x, y) G R+ právě tehdy, když existují
zo, £i,... , z*; E M takové, že zo = x^z^ — y 3 (^-i, zi) G R pro i — 1,... , k.c
Tvrzení 5.8 o tranzitivním uzávěru R+ je potřeba (neformálně) číst takto:
Do tranzitivního uzávěru patří všechny ty dvojice (x,y), že v původní relaci R se lze „dostat po šipkách" z x do y. Pro ilustraci:
•-•-•-• ^>
Petr Hliněný, Fl MU Brno, 2017
13/15
Fl: IB000: Relace a jejich použití
S tranzitivními relacemi (mezi objekty) se nejčastěji setkáváme, pokud tyto objekty porovnáváme vztahy „je stejný jako" nebo „je větší/lepší než".
Definice 5.9.   Daná binární relace R 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í).^
Příklad 5.10. Jaké vlastnosti mají následující relace?
• Buď fiCNxN definovaná takto (x,y) 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 R právě když f (x) < g (x) pro všechna x. □(Ireflexivní, antisymetrická a tranzitivní, ale ne reflexivní - není uspořádáním.)
Petr Hliněný, Fl MU Brno, 2017
14/15
Fl: IB000: Relace a jejich použití
Příklad 5.11. Jak vypadá graf relace ekvivalence?n
Poměrně příznačně, jak nám ukazuje následující obrázek (všimněte si absence šipek, která je dána symetrií relace).
9
Neformálně řečeno; ekvivalence je relace R C M x M, taková, že G i?
právě když x a y jsou v nějakém smyslu „stejné" (leží na stejné hromádce).
Tyto hromádky pak nazýváme komponentami či třídami ekvivalence dané relace.
□
Petr Hliněný, Fl MU Brno, 2017
15/15
Fl: IB000: Relace a jejich použití