Eine Relation ordnet Elementen einer Menge Elemente einer zweiten Menge zu (oder auch derselben).
Definition: Eine Relation ist eine Teilmenge des kartesischen Produkts zweier Mengen.
- R ⊆ A × B
Für (a,b) ∈ R schreibt man meist a R b. Sehr oft ist A = B.
Relationen können als Funktionen gesehen werden, deren Wertebereich lediglich wahr und falsch umfasst. Man könnte also auch R (a,b) für den Ausdruck der Relation schreiben.
Wichtige Eigenschaften von Relationen sind:
| Die Relation heißt | wenn gilt | und das bedeutet |
|---|---|---|
| reflexiv (A = B) | ∀ a ∈ A: a R a | Jedes Element steht in Relation zu sich selbst |
| symmetrisch (A = B) | ∀ a,b ∈ A: a R b ⇒ b R a | Die Relation ist ungerichtet |
| antisymmetrisch (A = B) | ∀ a,b ∈ A: a R b ∧ b R a ⇒ a = b | Es kann z.B. nicht a kleiner b und b kleiner a sein. |
| transitiv (A = B) | ∀ a,b,c ∈ A: a R b ∧ b R c ⇒ a R c | Anfang und Ende einer verb. Sequenz sind verbunden |
| antitransitiv | ||
| total (A = B) | ∀ a,b ∈ A: a R b ∨ b R a | Je zwei Elemente stehen in Relation |
| linkstotal | ∀ a ∈ A ∃ b ∈ B: a R b | Jedes El. aus A hat einen Partner in B |
| rechtstotal | ∀ b ∈ B ∃ a ∈ A: a R b | Jedes El. aus B hat einen Partner in A |
| linkseindeutig | ∀ a,c ∈ A ∀ b ∈ B: a R b ∧ c R b ⇒ a = c | Kein El. aus B hat mehr als einen Partner in A |
| rechtseindeutig | ∀ a ∈ A ∀ b,c ∈ B: a R b ∧ a R c ⇒ b = c | Kein El. aus A hat mehr als einen Partner in B |
| alternativ oder linear | ∀ a,b: entweder a R b oder b R a |
Relationen werden oft auch mit N:1 oder N:N und dergleichen charakterisiert. Dabei steht 1, wenn es rechts steht, für linkstotal und rechtseindeutig (und umgekehrt). N steht meistens für gar nichts. Manchmal wird auch 0 statt 1 verwendet, um die Totalität wegzulassen.
Wichtige Klassen von Relationen:
- Eine Funktion ist linkstotal und rechtseindeutig (d.h. N:1).
- Eine Ordnungsrelation ist reflexiv, transitiv und antisymmetrisch.
- Eine Äquivalenzrelation ist reflexiv, transitiv und symmetrisch.
Operationen auf ganzen Relationen werden in der relationalen Algebra behandelt.
In der Informatik sind Relationen für relationale Datenbanken wichtig.