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 Jane Smith 226 0Í Tom Jones 2T4 projjd|name descrip 373 Consultant Smalltalk 42 Java Developer Java Product 356 Magazine Multimedia PROJ_EMP table (relation table) j empid 104 projid •j 104 [l05 02 356 - 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, 2015 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, b 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é G N definujeme Ai x A2 x • • • x Ak = {(ai, fi25 • • • > cLk) I ctí £ Aj pro každé 1 < i < k} . • Například TLZ = TL xTL xTL = k) \ i,j, k G Petr Hliněný, Fl MU Brno, 2015 2/21 Fl: IB000: Relace a jejich použití 4.1 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,A2,--- ,Ak, pro k G N, je libovolná podmnožina kartézského součinu R Q Ai x A2 x • • • x Ak .c Pokud A\ = A2 = • • • = 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) j i G N} je binární relace na N.c • í + j) I í,j G N} je ternární relace na N. • {3 • i I i £ 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, 2015 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 B říká, že / je funkce s def. oborem A a oborem 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, 2015 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 (z 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, 2015 6/21 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, 2015 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}.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, 2015 8/21 Fl: IB000: Relace a jejich použití r 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 Například mějme M = {a, b, c, d, e, /} a R = {(a, a), (a, b), (b, c), (b, ď), (b, e), (b, /). (d, c), (e, c), (/, c), (e, ď), (e, /), (/, b)}, pak: Pozor, nejedná se o „grafy funkcí" známé třeba z matematické analýzy, 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). c Petr Hliněný, Fl MU Brno, 2015 9/21 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 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 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, 2015 10/21 Fl: IB000: Relace a jejich použití 4.3 Vlastnosti binárních relací na množině 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) £ R; • 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 • antisy metrická, právě když pro každé a, 6 G M platí, že jestliže (a, b), (b, a) G i?, pak a = b; » » Petr Hliněný, Fl MU Brno, 2015 11/21 Fl: IB000: Relace a jejich použití r • 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 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 c Petr Hliněný, Fl MU Brno, 2015 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;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, 2015 13/21 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.) 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í: c • 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í (x,y) 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 (x,y), pro které se lze (v grafu relace) dostat z x do y „po šipečkách". Petr Hliněný, Fl MU Brno, 2015 14/21 Fl: IB000: Relace a jejich použití 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^1 a je definována takto: R-1 = {(b,a) | (a,b) e R} A B R A R i? je tedy relace mezi B a A. Petr Hliněný, Fl MU Brno, 2015 15/21 Fl: IB000: Relace a jejich použití 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, (b, c) G S} Složení relací čteme „R složeno s S" nebo (pozor na pořadí!) „S po R". Petr Hliněný, Fl MU Brno, 2015 16/21 Fl: IB000: Relace a jejich použití f- Několik matematických príkladu skladaní relací nasleduje zde. • Je_li *A = {a,b}, B = {1,2}, C = {X,Y}, * R = {(a, 1), (6,1), (b, 2)}, 5 = {(1,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 (foh)(x)=f(h(x)) = x2 + lx • Složením těchže funkcí „naopak" ale vznikne funkce (hof)(x) = h(f(x)) = (X + 1)2.E 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, 2015 17/21 Fl: IB000: Relace a jejich použití Tvrzení 4.8. Nechť RQAxBaSQBxC jsou binární relace. Pak inverzí složené relace S o R je relace (SoR)-1 = dR-1 oS'1. ^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 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, 2015 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 L2 x • • • x L i, přičemž pro nějaké m < min(fc,£) platí Li = Kk-m+i, L2 = Kk_m+2, • • •, Lm = -K"fe- Pak relaci T lze s/ož/'ŕ 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• • • xKk-m, B = Lľx - ■ -xLm a C = Lm+Í x■ ■ ■ xLe. • Příslušné relace pak jsou * R = {(a, 6) G A x B | (ai,... afc_m, 61,... bm) G T} a * S = {(b,Č) G 5 x C j (6i,...6m,cm+i,...Q) G f/}. • Nakonec přirozeně položme U om T ~ 5 o i?, takže vyjde U omT = {(a,č) I ex. 6 e B, že (ai,.. .ak-m,b1:.. .bm) G T a (61,... i'm; ^m+17 ■ • ■ Schematicky pro snadnější orientaci: T C (7 c Ä"i X • • • X iffc-raX X • • • X Kk Li x---xLm xLm+1x---xLe Ki x ■ ■ ■ x Kk-m x x Lm+1 x ■■■ x Le *-„-'--- >-v-' B Petr Hliněný, Fl MU Brno, 2015 C 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, 2015 21/21 Fl: IB000: Relace a jejich použití