Relace

Slovo relace lze do češtiny přeložit nejpřesněji jako "vztah". Relace nám tedy umožňují dávat dohromady prvky množin, které jsou spolu v nějakém vztahu. Protože dávání prvků dohromady nám umožnily již uspořádané dvojice, triojice, či n-tice, využijeme tohoto aparátu. V kartézském součinu, který obsahuje vždy všechny možné uspořádané n-tice prvků, tak je dohromady každý prvek s každým. Chceme-li nějak specifikovat vztahy mezi těmito prvky, případně popisovat vlastnosti, které musí prvky mít, abychom je dali dohromady, je třeba z kartézského součinu vybírat jen některé n-tice, čili vytvářet jeho podmnožiny.

Jakoukoliv podmnožinu kartézského součinu nazveme relací.   

Nejprve se budeme zabývat relacemi, které vzniknou jako podmnožiny kartézského součinu dvou množin. Dále se budeme zabývat relacemi na množině, čili podmnožinammi druhé kartézské mocniny a v závěru poznatky zobecníme na podmnožiny kartézského součinu n množin.

Celá relační algebra tvoří základ relačních databází. Její pochopení je tedy nutnou podmínkou pro pochopení fungování relačních databází a operací v nich.

Binární relace

Buďte A, B množiny a nechť \rho \subseteq A \times B. Pak ρ nazýváme (binární) relací mezi množinami A a B. Je-li A = B, nazýváme ρ (binární) relací na množině A.

Příklady relací:

\rho \subseteq \mathbb{Z} \times \mathbb{N}, ρ = {(x, y) | x < y} je relace mezi celými a přirozenými čísly, obsahující jen ty uspořádané dvojice, v nichž je první prvek ostře menší než druhý.

idA = {(x, x) | x ∈ A} je tzv. identická relace na množině A.

Relaci je možné znázornit graficky, jak je vidět na následujícím  obrázku, který zachycuje relaci \Re = {(a, r), (b, r), (c, s), (c, t)} mezi množinami A = {a, b, c, d} a B = {r, s, t}

TZI - O11

Relaci je možné znázornit i tabulkou, která má v záhlaví řádků prvky množiny A a v záhlaví sloupců prvky množiny B (případně naopak, záleží na domluvě). Relace \Re znázorněná na obrázku by se pomocí tabulky znázornnila takto:

r
s t
a
1 0 0
b 1 0 0
c 0 1 1
d 0 0 0

Zápis (a, b) ∈ρ někdy nahrazujeme infixovým zápisem a ρ b.

Je-li ρ = ∅, nazýváme relaci ρ prázdnou relací. Je-li \rho = A \times B, nazýváme ρ plnou relací.

Jsou dány množiny A a B, kde |A| = n, |B| = m. Kolik mezi nimi může existovat různých relací?

Protože relace je jakákoliv podmnožina kartézského součinu, je počet různých relací roven počtu podmnožin kartézského součinu. Počet podmnožin k-prvkové množiny je, jak již víme, 2k. Dále víme, že kartézský součin n-prvkové a m-prvkové množiny má nm prvků. Počet reací mezi n-prvkovou a m-prvkovou množinou je tak 2nm

Nechť A, B, C jsou množiny a \rho = A \times B je binární relace mezi množinami A a B a \sigma \subseteq B \times C je binární relací mezi množinami B a C.  Složenou relaci \sigma \circ \rho (čti sigma po ró) definujeme vztahem \sigma \circ \rho = \{ (x,y) \in A \times C | \exists z \in B: (x,z) \in \rho \wedge (z,y) \in \sigma\}.

Princip skládání relací je vidět na následujícím obrázku:

TZI - O12

Relace \Re1={(a,r), (b,r), (c,s), (c,t)},  \Re2={(r,p), (r,q), (r,r), (t,q)}. Jejich složením vznikne relace \Re = \Re2\Re1 ={(a,p), (a,q), (a,r), (b,p), (b,q), (b,r), (c,q)}.

Skládání relací obecně není komuntativní, je však asociativní, tj. \tau \circ (\sigma \circ \rho) = (\tau \circ \sigma) \circ \rho

Nechť A, B jsou množiny a \rho = A \times B je binární relace mezi množinami A a B. Relaci\rho^{-1} definovanou jako \rho^{-1} = \{(a,b) \in B \times A | (b, a) \in \rho\} nazýváme relací inverzní k relaci \rho.

Inverzní relace tedy obsahuje přesně opačné uspořádané dvojice, než původní relace.

Nechť A = {a, b, c} a B = {r, s, t} jsou množiny a ρ = {(a, r), (a, s), (a, t), (b, t), (c, s)} je relace mezi těmito množinami. Inverzní relací k relaci ρ je relace ρ-1 = {(r, a), (s, a), (t, a), (t, b), (s, c)}.

V případě znázornění relace pomocí obrázku, bychom inverzní relaci znázornili tímtéž obrázkem, pouze s opačně orieentovanými šipkami. V případě znázorňování relace pomocí tabulky je tabulka inverzní relace transponovaná (tj. převrácená podle hlavní diagonály).

Připomeňme, že relace mezi množinami je opět množina a má tedy smysl uvažovat množinové operace s relacemi. Můžeme tak vytvářet sjednocení relací (relace obsahující uspořádané dvojice z obou sjednocovaných relací - tj. ty, které jsou v jedné nebo ve druhé), či průnik relací (relaci obsahující uspořádané dvojice, které jsou vv obou pronikaných relacích společnné - tj. ty, které jsou v jedné a zároveň ve druhé).

(Binární) relace na množině

Binární relace na množině mají speciální význam, neboť umožňují zkoumat vlastnosti vztahů mezi prvky patřícími do téže množiny. U relací na množině tedy rozlišujeme vlastnosti, jejichž znalost je pro další studium nutná.

Nechť A je množina a \rho \subseteq A \times A je relace na této množině.

Relace ρ se nazývá reflexivní, jestliže \forall x \in A: (x,x) \in \rho, tedy jestliže každý prvek množiny A je v relaci sám se sebou.

Příkladem reflexivní relace je identita, relace "být menší nebo rovno", relace dělitelnosti, atd.

Platí, že sjednocení a průnik reflexivních relací je opět reflexivní relace. Složením dvou reflexivních relací vznikne opět reflexivní relace. Inverzní relací k reflexivní relaci je reflexivní relace.

Relace ρ se nazývá symetrická, jestliže \forall x, y \in A : (x, y) \in \rho \Rightarrow (y, x) \in \rho, tedy jestliže každá dvojice prvků, která je spolu v relaci, je spolu v relaci i v opačném pořadí.

Příkladem symetrické relace je identita, nerovnost nebo vlastnost typu "mít stejné znaménko".

Platí, že sjednocení a průnik symetrických relací je opět symetrická relace. Inverzní relací k symetrické relaci je táž relace (pro symetrickou relaci tedy platí, že ρ-1 = ρ). Složením symetrických relací vznikne opět symetrická relace.

Relace ρ se nazývá antisymetrická, jestliže \forall x, y \in A : ((x, y) \in \rho \wedge (y, x) \in \rho) \Rightarrow x=y, tedy pokud je daná dvojice prvků v relaci nezávisle na jejich pořadí, pak to nutně musí znamenat, že se jedná o tentýž prvek.

Příkladem antisymetrické relace je relace "být menší nebo rovno". Je zřejmé, že pokud a ≤ b a zároveň  b ≤ a, pak nutně a = b.

Relace ρ se nazývá asymetrická, jestliže \forall x, y \in A : (x, y) \in \rho \Rightarrow (y, x) \notin \rho, tedy pokud platí, že je-li uspořádaná dvojice v relaci, pak opačně uspořádaná dvojice v relaci není.

Příkladm asymetrické relace jsou relace "nerovno", "být menší než" nebo "být větší než".

Relace ρ se nazývá tranzitivní, jestliže \forall x, y, z \in A : ((x, y ) \in \rho \wedge (y, z) \in \rho) \Rightarrow (x, z)  \in \rho, tedy pokud je prvek x v relaci s prvkem y a prvek y je v relaci s prvkem z, je v relaci i prvek x s prvkem z.

Příkladem tranzitivní relace je opět relace "být menší nebo rovno", identita, či relace "být příbuzný" na množině lidí.

Relace ρ se nazývá úplná, jestliže \forall x, y \in A : (x, y) \in \rho \vee (y, x) \in \rho, tedy pokud pro každou dvojici prvků platí, že je buď jeden v relaci s druhým, nebo druhý v relaci s prvním.

Příkladem úplné relace je například relace ≤ na libovolné číselné množině.  Je zřejmé, že pro jakákoliv dvě čísla x, y platí buď x ≤ y, nebo y ≤ x.

Pro úplnost dodejme ještě definici následujících dvou pojmů:

Relace \rho \subseteq A \times A se nazývá

Vzhledem k tomu, že relaci jsme si definovali jako každou podmnožinu kartézského součinu, jsou i uvedené dvě (extrémní) podmnožiny relacemi. Vzhledem k tomu, že se jedná o extrémní podmnožiny, mají i v terminologii relací význačné postavení.

Pozor! Nerpleťte si úplnou a plnou relaci, jedná se o jiné pojmy!

Pokud chceme rozhodnout, zda daná relace některou z uvedených vlastností má, resp. nemá, je třeba postupovat následovně. Musíme si uvědomit, že všechny vlastnosti jsou uvozeny univerzálním kvantifikátorem, tj. tvrzení musí platit pro všechny prvky (resp. všechny dvojice či trojice). Pokud chceme dokázat, že relace uvedenou vlastnost splňuje, je třeba zdůvodnit, že tvrzení bude skutečně pro všechny prvky platit. Chceme-li dokázat, že relace danou vlasnost nemá, stačí nalézt jediný prvek (dvojici, trojici), pro který dané tvrzení neplatí a tím pádem je ukázáno, že tvrzení neplatí pro všechny prvky a relace uvedenou vlastnost nemá. Ukažme si tento postup na příkladu:

Rozhodněte, zda relace \rho = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} \mid a \mbox{ div } 2 = b \mbox{ div } 2\} je reflexivní, symetrická, asymetrická, antisymetrická, tranzitivní, úplná.

Řešení:

Nyní se podívejme na speciální kategorie relací, a těmi jsou ekvivalence a uspořádání.

Relace, která je zároveň reflexivní, symetrická a tranzitivní, se nazývá ekvivalence.  

Ekvivalence je určitým zobecněním rovnosti (tedy identity). Je zřejmé, že rovnost splňuje všechny tři požadované vlastnosti ekvivalence, tj. je reflexivní (každý prvek je roven sám sobě), symetrická (je-li jeden roven druhému, je i druhý roven prvnímu), i tranzitivní (pokud a = bb = c, pak i a = c. Existují však i jiné vlastnosti, které splňují tyto tři podmínky. Jejich společným jmenovatelem je to, že v definici relace musí být popsána vlastnost, která je stejná pro prvky, které spolu jsou v relaci. Typickými příklady tak jsou "dávat po dělení číslem  m stejný zbytek", "mít stejné znaménko", apod.

Příklad:

Dokažte, že relace \rho = \{(a,b) \in \mathbb{N}^2 | (a \bmod 5) = (b \bmod 5) \} je ekvivalence.

Řešení: Je třeba ověřit, že uvedená relace je reflexivní, symetrická a tranzitivní.

Ukázali jsme, že uvedená relace je reflexivní, symetrická a tranzitivní, je to tedy ekvivalence.

Je dobré si uvědomit, že je-li relace reflexivní, nemůže být asymetrická. K vyvrácení asymetrie dokonce stačí i slabší tvrzení, a to, že existuje prvek, který je sám se sebou v relaci. Kdyby taková relace byla asymetrická, musel by tento prvek sám se sebou v relaci být a zároveň nebýt, což je spor.

Dále je dobré si uvědomit, že je-li neprázdná relace symetrická, pak nemůže být antisymetrická. Neprázdná relace totiž obsahuje alespoň jednu uspořádanou dvojici (a,b). Je-li symetrická, pak navíc nutně obsahuje i dvojici (b,a), což je v rozporu s definicí asymetrie.

Relace, která je zároveň reflexivní, antisymetrická a tranzitivní, se nazývá uspořádání.

Uspořádání zde máme, podobně jako tomu bylo v případě ekvivalence, definováno velmi obecně, tj. jde nám o to, abychom byli schopné vybudovat na prvcích dané množiny stromovou strukturu. Nechceme tedy uspořádat prvky množiny do jediného řetězce, jak by mohlo z významu slova "uspořádání" plynout, obecnost spočívá právě v tom, že jeden prvek může mít v daném uspořádání více následníků, vždy má však jen jediného předchůdce.

Typickým uspořádáním je relace ≤, tedy "být menší nebo rovno".

Příklad:

Dokažte, že relace \rho = \{(a,b) \in \mathbb{Z}^2 \mid (a \leq b) \} je uspořádání.

Řešení: Je třeba ověřit, že uvvedená relace je reflexivní, antisymetrická a tranzitivní.

Uvedená relace je reflexivní, antisymetrická a tranzitivní, je to tedy uspořádání.

Zatímco klasické uspořádání ≤ tvoří na číselných množinách jediný řetězec (jedná se úplnou relaci), zmíněnou stromovou strukturu dostaneme pomocí relace dělitelnosti na množině přirozených čísel.

Řekneme, že číslo a dělí číslo b a píšeme a|b, právě tehdy, když existuje přirozené číslo c takové, že ac = b. Někdy též říkáme, že a je dělitelem, čísla b, nebo že číslo b je dělitelné číslem a, případně, že číslo b je násobkem čísla a.

Nyní definujeme relaci \rho = \{(a,b) \in \mathbb{N}^2; a|b\}, tedy \rho = \{(a,b) \in \mathbb{N}^2| \exists c \in \mathbb{N}: a \cdot c = b\} a ukažme, že se jedná o relaci uspořádání.

Opět bude třeba ověřit, že uvedená relace je reflexivní, antisymetrická a trannzitivní:

Tím jsme dokázali vše potřebné pro tvrzení, že relace dělitelnosti je uspořádání. Není to však relace úplná (např. čísla 3 a 5 nejsou v relaci v žádném uspořádání), proto nelze podle relace dělitelnosti uspořádat všechna přirozená čísla do jediného řetězce, ale uspořádání má stromovou strukturu.

Vzpomeňme si nyní na definici podmnožiny. Dá se snadno dokázat, že množinová inkluze definuje na určité množině množin M relaci uspořádání:

Pokuste se uvedené vztahy dokázat na základě definice podmnožiny.

Další příklady relací, včetně animovaných appletů vytvořených v programu GeoGebra, naleznete zde.