Relationen Flashcards
Was ist eine Relation?
Eine Relation beschreibt die Beziehung zwischen Elementen von Mengen.
Was ist eine k-stellige Relation oder eine Relation der Stelligkeit/Arität k?
Gegeben Mengen A1, A2, …, Ak, so nennt man R⊆A1x A2x …x Ak eine k-stellige Relation oder eine Relation der Stelligkeit/Arität k.
Was sind die wichtigsten Datenbankoperationen?
Der Join konkateniert jedes Tupel einer Tabelle mit jedem Tupel der anderen Tabelle, wenn die Elemente von bestimmten Spalten übereinstimmen. Die Projektion reduziert jedes Tupel auf die Einträge an bestimmten Positionen.
Was sind binäre Relationen?
Binäre Relationen oder auch 2-stellige Relationen sind Relationen zwischen Elementen zweier Mengen oder auch innerhalb einer einzelnen Menge. Sie ist die Teilmenge des kartesischen Produkts AxB. Binäre Relationen können als Graphen dargestellt werden.
Wie sieht die Infixnotation für binäre Relationen aus?
a R b für (a,b) ∈ R
Was ist die inverse Relation?
R^(-1) := {(b,a)|(a,b) ∈ R}
Was ist ein Digraph?
Ein Digraph steht kurz für einen gerichteten Graphen G = (V,E) und besteht aus einer Knotenmenge V und einer Kantenrelation/-menge E, die eine binäre Relation E⊆VxV darstellt. Ein Digraph ist endlich, falls V endlich ist, ansonsten unendlich. Ein Digraph ist bipartid, falls V=A∪B mit A∩B=∅ und E⊆AxB∪BxA.
Was ist ein Weg/Pfad bei Graphen?
Ein Tupel von Knoten heißt Weg/Pfad, wenn je zwei aufeinanderfolgende Knoten durch eine Kante aus E verbunden sind.
Was ist die Länge eines Pfades?
Die Länge eines Pfades l ist die Anzahl der Kanten (“Schritte”) von einem Knoten zum anderen Knoten.
Wann ist ein Pfad einfach?
Ein Pfad heißt einfach, falls kein Knoten mehrmals in dem Pfad vorkommt (“besucht” wird).
Was ist die maximale Länge, die ein einfacher Pfad in einem endlichen Digraphen haben kann?
|V|-1
Was ist das relationale Produkt?
Sind R⊆AxB sowie S⊆CxD binäre Relationen, dann ist das relationale Produkt von R und S die binäre Relation RS⊆AxD gegeben durch RS={(a,d)| es gibt x∈B∩C mit (a,x)∈R und (x,d)∈S}. Wenn B∩C=∅, dann gilt also RS=∅. Man nennt RS auch die Verkettung von R und S.
Was ist die transitive Hülle?
Die transitive Hülle einer binären Relation R⊆AxA: R^+ := ∪k∈N R^k (alle Pfade, die min. einen Schritt machen).
Was ist die reflexiv-transitive Hülle?
Die reflexiv-transitive Hülle einer binären Relation R⊆AxA: R^* := ∪k∈N0 R^k = R^0∪R^+. v ist von u erreichbar, falls uR^*v
Was sind die Eigenschaften von binären Relationen auf einer Menge?
-reflexiv: IdA⊆R (jeder Knoten hat eine Schleife)
-symmetrisch: falls wann immer (s,t) ∈ R, dann auch (t,s) ∈ R (zwischen je zwei Knoten entweder beide Kanten oder keine)
-asymmetrisch: falls wann immer (s,t) ∈ R, dann immer (t,s) kein Element von R (keine Schleifen und zwischen je zwei verschiedenen Knoten höchstens eine Kante)
-antisymmetrisch: falls wann immer (s,t) ∈ R und auch (t,s) ∈ R, dann s=t (zwischen zwei verschiedenen Knoten existiert höchstens eine Kante)
-transitiv: falls wann immer (s,t) ∈ R und auch (t,u) ∈ R, dann auch (s,u) ∈ R (kommt man mit genau zwei Schritten von s nach u, dann auch genau mit einem)
