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) PROJ ID NAME DESCRIP 373 Consultant Smalltalk 42 Java Developer Java Product 356 Magazine Multimedia PROJ_EMP table (relation table) ■W 104 32 L105 I 356^=- Stručný přehled lekce * Co je relace a funkce. Reprezentace relací tabulkou a grafem. * Základní vlastnosti binárních relací. * Inverze relace, skládání relací a jeho význam. Petr Hliněný, Fl MU Brno, 2013 Fl: IB000: Relace a jejich použití 4.1 Relace a funkce nad množinami Vedle množin dalším důležitým základním „datovým typem" matematiky jsou relace, kterým vzhledem k jejich mnohotvárnému použití v informatice věnujeme významnou pozornost v této i dvou příštích lekcích. Definice 4.1. Relace mezi množinami Ai,--- ,Ak, pro k g N, je libovolná podmnožina kartézského součinu R C A\ x • • • x Ak . Pokud A\ = • • • = Ak = A, hovoříme o k-ární relaci R na A. c Příklady relací. • {(1, a), (2, a), (2, b)} je relace mezi {1, 2, 3} a {a, b}. • {(i, 2 • i) | i g N} je binární relace na N.c • i + j) | í,j g N} je ternární relace na N. • {3 • i | i 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, 2013 2/19 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 B říká, že / je funkce s def. oborem A a oborení hodnot B. Funkcím se také říká zobrazení. Príklady funkcí jsou třeba následující. • Definujeme funkci / : N —> N předpisem f (x) = x + 8. Pak / = {(x,x+ 8) | x G 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, 2013 4/19 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.d 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, 2013 5/19 Fl: IB000: Relace a jejich použití Nasleduje několik príkladu parciálních funkcí. • Definujeme parciální funkci / : 7L —> N předpisem 3 + x jestliže x > 0. _L jinak. Tj. / = {(x,3 + x) ieN}.c Také funkce / : R —> R daná běžným analytickým předpisem f(x) = \ogx je jen parciální - není definována pro x < Ox Co je relace, přiřazující lidem v ČR jejich (česká) rodná čísla? Petr Hliněný, Fl MU Brno, 2013 6/19 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}.n Dále definujeme tyto množiny („odvozené typy") • JMÉNO = ZNAK15, PŘÍJMENÍ = ZNAK20, VEK = ČÍSLICE3, • ZAMESTNANEC „e" 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 Z Petr Hliněný, Fl MU Brno, 2013 7/19 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) G 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 Pozor, nejedná se o „grafy funkcí" známé třeba z matematické analýzy, c Například mějme M — {a, b, c, d, e, /} a R — {(a, a), (a, b), (b, c), (b, d), (b, e), (b, /). (d, c), (e, c), (/, c), (e, ď), (e, /), (/, b)}, pak: c V případě, že M je nekonečná nebo „velká", může být reprezentace i? jejím grafem nepraktická (záleží také na míře „pravidelnosti" R). Petr Hliněný. Fl MU Brno. 2013 8/19 Fl: IB000: Relace a jejich použití Značení: Binární relaci i? C M x M lze jednoznačně zapsat také pomocí matice relace - matice A typu M x M s hodnotami z {0,1}. a •—1=- a A i 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 Petr Hliněný, Fl MU Brno, 2013 9/19 Fl: IB000: Relace a jejich použití 4.3 Vlastnosti binárních relací Definice 4.4. Nechť R C M x M. Binární relace i? je • reflexivní, právě když pro každé a G M platí (a, a) G i?; • ireflexivní, právě když pro každé a 6 M platí (a, a) 0 R; • symetrická, právě když pro každé a, b G M platí, že jestliže (a, 6) G R, pak také (6, a) G i?; a • antisymetrická, právě když pro každé a, b G M platí, že jestliže Petr Hliněný, Fl MU Brno, 2013 10/19 Fl: IB000: Relace a jejich použití • tranzitivní, právě když pro každé a, b, c G M platí, že jestliže (a, b), (6, c) G fí, pak také (a, c) G i?. a 6 c c 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í).c Pozor, může být relace symetrická i antisymetrická zároveň? nAno! Petr Hliněný, Fl MU Brno, 2013 11/19 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;c • (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 a 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;n • (x, y) G R právě když x má jinou výšku než (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, 2013 12/19 Fl: IB000: Relace a jejich použití Příklad 4.6. Jaké vlastnosti mají následující relace? • Buď ÍJCNxN definovaná takto (x,y) G R právě když x dělí y.c (Částečné uspořádání, ale ne každá dvě čísla jsou porovnatelná.) c • Bud' ÍJCNxN definovaná takto (x,y) G R právě když x a y mají stejný zbytek po dělení číslem 5. (Ekvivalence.) c • Nechť F = {/ | / : N —> N} je množina funkcí. Bud' R C FxF definovaná takto (f,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, 2013 13/19 Fl: IB000: Relace a jejich použití 4.4 Inverzní relace a skládání relací Definice: Nechť R C A x B je binární relace mezi A a B. Inverzní relace k relaci se značí R 1 a je definována takto: ií"1 = {(6, a) | (a, 5) € fi} i? 1 je tedy relace mezi B a A. Petr Hliněný, Fl MU Brno, 2013 14/19 Fl: IB000: Relace a jejich použiti' Definice skládání Definice 4.7. Složení (kompozice) relací R a S. Nechť RQAxBaSQBxC 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) I existuje b G B takové, že (a, b) G -R, (&, c) G 5} Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „S po R". Petr Hliněný, Fl MU Brno, 2013 15/19 Fl: IB000: Relace a jejich použití Několik matematických příkladů skládání relací následuje zde. • J^'' *A = {a,b}, B = {1,2}, C = {X,Y}, * R = {(a, 1), (6,1), (6, 2)}, 5 = {(1,X)}, pak složením vznikne relace * 5ofí = {(a,I),(6,I)}. • Složením funkcí h(x) = x2 a /(x) = x + 1 na R vznikne funkce (foh)(x)=f(h(x)) = X2 + 1.E • Složením těchže funkcí „naopak" ale vznikne funkce (hof) (x) = h(f(x)) (x + 1)2. Poznámka: Nepříjemné je, že v některých oblastech matematiky (například v algebře při skládání 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, 2013 16/19 Fl: IB000: Relace a jejich použití 4.5 Skládání relací „v praxi" Příklad 4.8. 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 r. 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ž těchto „tabulkových" relací zjistíme, kteří studenti majízapsané předměty na kterých fakultách (třeba na Fl)? c 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, 2013 17/19 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 K\. a U C L\ x L2 x • • • x L i, přičemž pro nějaké m < mm(k,£) platí L\ = Kk-m+i,L2 = Kk-m+2, ■ ■ ■ 1 Lm = Kk- Pak relaci T lze složit s relací U na zvolených m složkách Li,... ,Lm („překrytí") s použitím Definice 4.7 takto: • Položme A = K\ x • • • x Kk_m, B = Li x • • - x Lm a C = Lm+i x • • • x Le. • Příslušné relace pak jsou * R = {(a,b) £ Ax B\ (au.. • ^k—mi ^1) • • • ^m) GT}a * S = {(b,Č) G S x C j 6m,cm+i,... q) G r/}. • Nakonec přirozeně položme U om T ~ 5 o i?, takže vyjde U omT = {(a, č) I ex. 6 g B, že (ai,.. .afc-m,&i, ■ ■ .6m) g T a (61,... c«) e í/}. Schematicky pro snažší orientaci: T C (7 c Ä"l X • • • X Kk-mX Kk-m+l x ■■■ x Kk Li x---xLTO xIm+iX'"XL{ Kx x • • ■ x Kk-m x x Lm+i x ■■■ x Le ---„--'---- >-v-' B Petr Hliněný, Fl MU Brno, 2013 C Fl: IB000: Relace a jejich použit Příklad 4.9. Skládání v relační databázi pasažérů a letů u leteckých 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 ČSA 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 posáno výše. pasažér letadlo Petr Josef Pavel ČSA ČSA AirFrance □ Petr Hliněný, Fl MU Brno, 2013 19/19 Fl: IB000: Relace a jejich použití