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í nad množinou. * Inverze relace, skládání relací a jeho význam. Petr Hliněný, Fl MU Brno, 2014 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), ( 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, 2014 2/20 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,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, 2014 3/20 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, 2014 5/20 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, 2014 6/20 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, 2014 7/20 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, 2014 8/20 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 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 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). Petr Hliněný. Fl MU Brno. 2014 9/20 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 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, 2014 10/20 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) G 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 • antisymetrická, právě když pro každé a, b G M platí, že jestliže Petr Hliněný, Fl MU Brno, 2014 11/20 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 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, 2014 12/20 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, 2014 13/20 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, 2014 14/20 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^1 a je definována takto: R-1 = {(b,a) | (a,b) e R} i? je tedy relace mezi B a A. Petr Hliněný, Fl MU Brno, 2014 15/20 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, (&, 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, 2014 16/20 Fl: IB000: Relace a jejich použití :f- 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), (b, 2)}, S = {(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 + l)2x 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 skladaní, kdy se místo S o R píše R ■ S nebo jen RS. Petr Hliněný, Fl MU Brno, 2014 17/20 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, 2014 18/20 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 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, • • •, 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• • • xKk-m, B = LLx- ■ - xLm a C = Lm+Í x• • • xLe. • Příslušné relace pak jsou * R = {(a, b) g A x B I (ai,... afc_m, 61,... 6m) g T} a * 5 = {(&,č) 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, • • -&m) g T a (61,... 6 ce) g í/}. Schematicky pro snadnější orientaci: T C Ä"i x T T _ /XI r- 1., Li x---xLm xLm+ix---xL£ ^ 7" , 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 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, 2014 20/20 Fl: IB000: Relace a jejich použití