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žinami 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: Nechť jsou množiny a nechť . Pak nazýváme (binární) relací mezi množinami a . Je-li , nazýváme (binární) relací na množině .

Příklady relací:

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ý.

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 mezi množinami a .

Relaci je možné znázornit i tabulkou, která má v záhlaví řádků prvky množiny  a v záhlaví sloupců prvky množiny . Relace  znázorněná na obrázku by se tak pomocí tabulky znázornila takto:

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

Je-li , nazýváme relaci  prázdnou relací. Je-li , nazýváme plnou 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 . Kartézský součin n-prvkové a m-prvkové množiny má  prvků. Počet relací mezi n-prvkovou a m-prvkovou množinou je tak .

Složená relace: Nechť jsou množiny a je binární relace mezi množinami  je binární relace mezi množinami . Složenou relací (čteme sigma po ró) definujeme vztahem

Graficky můžeme skládání relací zobrazit následujícím obrázkem:

Příklad: Máme relace a . Určete složenou relaci .

Řešení

Složením relací vznikne relace: .

Skládání relací obecně není komutativní, je však asociativní. Platí tedy:

Inverzní relace:  Nechť jsou množiny a je binární relace mezi množinami . Relaci definovanou jako nazýváme relací inverzní k relaci . Inverzní relace tedy obsahuje přesně opačné uspořádané dvojice, než původní relace.

V případě znázornění relace pomocí obrázku, bychom inverzní relaci znázornili tímtéž obrázkem, pouze s opačně orientovaný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říklad: Nechť jsou množiny a je relace mezi těmito množinami. Inverzní relací k relaci je relace .