Relationenalgebra

Die Operanden der Sprache sind Relationen. Als unabhängige Operatoren gibt es Selektion, Projektion, Vereinigung, Mengendifferenz, Kartesisches Produkt, Umbenennung; daraus lassen sich weitere Operatoren Verbund, Durchschnitt, Division ableiten.

Selektion

:

Es werden diejenigen Tupel ausgewählt, die das Selektionsprädikat erfüllen. Die Selektion wird mit $\sigma$ bezeichnet und hat das Selektionsprädikat als Subskript.

Die Projektion

$$\sigma_{Semester > 10}^{}$$(Studenten)

liefert als Ergebnis

MatNr	Name	Semester
24002	Xenokrates	18
25403	Jonas	12

Das Selektionsprädikat wird beschrieben durch eine Formel F mit folgenden Bestandteilen:

• Attributnamen der Argumentrelation R oder Konstanten als Operanden
• arithmetische Vergleichsoperatoren <   =   >   $\leq$     $\geq$
• logische Operatoren: $\wedge$   $\vee$  $\neg$ (und oder nicht)
  

Projektion

:

Bei der Projektion werden Spalten der Argumentrelation extrahiert. Das Operatorsymbol lautet , die gewünschten Attribute werden im Subskript aufgelistet:

$$\Pi_{Rang}^{}$$(Professoren)

liefert als Ergebnis

Rang

C4

C3

Die Attributmenge wird üblicherweise nicht unter Verwendung von Mengenklammern sondern als durch Kommata getrennte Sequenz gegeben. Achtung: Da das Ergebnis wiederum eine Relation ist, existieren per definitionem keine Duplikate ! In der Praxis müssen sie dennoch algorithmisch entfernt werden.

Vereinigung

:

Zwei Relationen mit gleichem Schema können durch die Vereinigung, symbolisiert durch $\cup$, zusammengefaßt werden. Beispiel:

$$\Pi_{PersNr, Name}^{}$$(Assistenten) $$\cup$$ $$\Pi_{PersNr, Name}^{}$$(Professoren)

Mengendifferenz

:

Für zwei Relationen R und S mit gleichem Schema ist die Mengendifferenz R  -  S definiert als die Menge der Tupel, die in R aber nicht in S vorkommen. Beispiel

$$\Pi_{MatrNr}^{}$$(Studenten)  -  $$\Pi_{MatrNr}^{}$$(prüfen)

liefert die Matrikelnummern derjenigen Studenten, die noch nicht geprüft wurden.

Kartesisches Produkt

:

Das kartesische Produkt (Kreuzprodukt) zweier Relationen R und S wird mit R  x  S bezeichnet und enthält alle möglichen Paare von Tupeln aus R und S. Das Schema der Ergebnisrelation, also sch (R  x  S), ist die Vereinigung der Attribute aus sch(R) und sch(S).

Das Kreuzprodukt von Professoren und hören hat 6 Attribute und enthält 91 (= 7  ^.  13) Tupel.

PersNr	name	Rang	Raum	MatNr	VorlNr
2125	Sokrates	C4	226	26120	5001
...	...	...	...	...	...
2125	Sokrates	C4	226	29555	5001
...	...	...	...	...	...
2137	Kant	C4	7	29555	5001

Haben beide Argumentrelationen ein gleichnamiges Attribut A, so kann dies durch Voranstellung des Relationennamen R in der Form R.A identifiziert werden.

Umbenennung von Relationen und Attributen

:

Zum Umbenennen von Relationen und Attributen wird der Operator $\rho$ verwendet, wobei im Subskript entweder der neue Relationenname steht oder die Kombination von neuen und altem Attributnamen durch einen Linkspfeil getrennt. Beispiele:

$$\rho_{Dozenten}^{}$$(Professoren)

$$\rho_{Zimmer \leftarrow Raum}^{}$$(Professoren)

Eine Umbenennung kann dann erforderlich werden, wenn durch das kartesische Produkt Relationen mit identischen Attributnamen kombiniert werden sollen.

Als Beispiel betrachten wir das Problem, die Vorgänger der Vorgänger der Vorlesung mit der Nummer 5216 herausfinden. Hierzu ist ein kartesisches Produkt der Tabelle mit sich selbst erforderlich, nachdem zuvor die Spalten umbenannt worden sind:

$$\Pi_{V1.Vorg\uml {a}nger}^{}$$($$\sigma_{V2.Nachfolger=5216 \wedge V1.Nachfolger = V2.Vorg\uml {a}nger}^{}$$       

      ($$\rho_{V1}^{}$$(voraussetzen) x $$\rho_{V2}^{}$$(voraussetzen)))

Die konstruierte Tabelle hat vier Spalten und enthält das Lösungstupel mit dem Wert 5001 als Vorgänger von 5041, welches wiederum der Vorgänger von 5216 ist:

Vorgänger	Nachfolger	Vorgänger	Nachfolger
5001	5041	5001	5041
...	...	...	...
5001	5041	5041	5216
...	...	...	...
5052	5259	5052	5259

Natürlicher Verbund (Join)

:

Der sogenannte natürliche Verbund zweier Relationen R und S wird mit R  $\bowtie$  S gebildet. Wenn R insgesamt m + k Attribute A₁,..., A_m, B₁,..., B_k und S insgesamt n + k Attribute B₁,..., B_k, C₁,..., C_n hat, dann hat R $\bowtie$ S die Stelligkeit m + k + n. Hierbei wird vorausgesetzt, daß die Attribute A_i und C_j jeweils paarweise verschieden sind. Das Ergebnis von R $\bowtie$ S ist definiert als

R $$\bowtie$$ S  : =  $$\Pi_{A_1, \ldots , A_m, R.B_1, \ldots , R.B_k , C_1, \ldots ,C_n}^{}$$($$\sigma_{R.B_1=S.B_1 \wedge \ldots \wedge R.B_k=S.B_k}^{}$$(R x S))

Es wird also das kartesische Produkt gebildet, aus dem nur diejenigen Tupel selektiert werden, deren Attributwerte für gleichbenannte Attribute der beiden Argumentrelationen gleich sind. Diese gleichbenannten Attribute werden in das Ergebnis nur einmal übernommen.

Die Verknüpfung der Studenten mit ihren Vorlesungen geschieht durch

(Studenten $$\bowtie$$ hören) $$\bowtie$$ Vorlesungen

Das Ergebnis ist eine 7-stellige Relation:

MatrNr	Name	Semester	VorlNr	Titel	SWS	gelesenVon
26120	Fichte	10	5001	Grundzüge	4	2137
25403	Jonas	12	5022	Glaube und Wissen	2	2137
28106	Carnap	3	4052	Wissenschaftstheorie	3	2126
...	...	...	...	...	...	...

Da der Join-Operator assoziativ ist, können wir auch auf die Klammerung verzichten und einfach schreiben

Studenten $$\bowtie$$ hören $$\bowtie$$ Vorlesungen

Wenn zwei Relationen verbunden werden sollen bzgl. zweier Attribute, die zwar die gleiche Bedeutung aber unterschiedliche Benennungen haben, so müssen diese vor dem Join mit dem $\rho$-Operator umbenannt werden. Zum Beispiel liefert

Vorlesungen $$\bowtie$$ $$\rho_{gelesenVon \leftarrow PersNr}^{}$$(Professoren)

die Relation {[VorlNr, Titel, SWS, gelesenVon, Name, Rang, Raum]}

Allgemeiner Join

:

Beim natürlichen Verbund müssen die Werte der gleichbenannten Attribute übereinstimmen. Der allgemeine Join-Operator, auch Theta-Join genannt, erlaubt die Spezifikation eines beliebigen Join-Prädikats $\theta$. Ein Theta-Join R $\bowtie_{\theta}^{}$ S über der Relation R mit den Attributen A₁, A₂,..., A_n und der Relation S mit den Attributen B₁, B₂,..., B_n verlangt die Einhaltung des Prädikats $\theta$, beispielsweise in der Form

R $$\bowtie_{A_1 < B_1 \wedge A_2=B_2 \wedge A_3 < B_5}^{}$$ S

Das Ergebnis ist eine n + m-stellige Relation und läßt sich auch als Kombination von Kreuzprodukt und Selektion schreiben:

R $$\bowtie_{\theta}^{}$$ S : = $$\sigma_{\theta}^{}$$(R x S)

Wenn in der Universitätsdatenbank die Professoren und die Assistenten um das Attribut Gehalt erweitert würden, so könnten wir diejenigen Professoren ermitteln, deren zugeordnete Assistenten mehr als sie selbst verdienen:

Professoren $$\bowtie_{Professoren.Gehalt < Assistenten.Gehalt \wedge Boss = Professoren.PersNr}^{}$$ Assistenten

Die bisher genannten Join-Operatoren werden auch innere Joins genannt ( inner join). Bei ihnen gehen diejenigen Tupel der Argumentrelationen verloren, die keinen Join-Partner gefunden haben. Bei den äußeren Join-Operatoren ( outer joins) werden - je nach Typ des Joins - auch partnerlose Tupel gerettet:

• left outer join: Die Tupel der linken Argumentrelation bleiben erhalten
• right outer join: Die Tupel der rechten Argumentrelation bleiben erhalten
• full outer join: Die Tupel beider Argumentrelationen bleiben erhalten

Somit lassen sich zu zwei Relationen L und R insgesamt vier verschiedene Joins konstruieren:

Mengendurchschnitt

:

Der Mengendurchschnitt (Operatorsymbol $\cap$) ist anwendbar auf zwei Argumentrelationen mit gleichem Schema. Im Ergebnis liegen alle Tupel, die in beiden Argumentrelationen liegen. Beispiel:

$$\Pi_{PersNr}^{}$$($$\rho_{PersNr \leftarrow gelesenVon}^{}$$(Vorlesungen)) $$\cap$$ $$\Pi_{PersNr}^{}$$($$\sigma_{Rang=C4}^{}$$(Professoren))

liefert die Personalnummer aller C4-Professoren, die mindestens eine Vorlesung halten.

Der Mengendurchschnitt läßt sich mithilfe der Mengendifferenz bilden:

R $$\cap$$ S  =  R \ (R \ S)

Division

:

Sei R eine r-stellige Relation, sei S eine s-stellige Relation, deren Attributmenge in R enthalten ist.

Mit der Division

Q  : =  R  ÷  S  : =  {t = t₁, t₂,..., t_{r - s} | $$\forall$$u $$\in$$ S  :  tu $$\in$$ R}

sind alle die Anfangsstücke von R gemeint, zu denen sämtliche Verlängerungen mit Tupeln aus S in der Relation R liegen. Beispiel:

Die Division von R durch S läßt sich schrittweise mithilfe der unabhängigen Operatoren nachvollziehen (zur Vereinfachung werden hier die Attribute statt über ihre Namen über ihren Index projiziert):

T : = $\pi_{1, \ldots, r-s}^{}$(R)	alle Anfangsstücke
T x S	diese kombiniert mit allen Verlängerungen aus S
(T x S)\R	davon nur solche, die nicht in R sind
V : = $\pi_{1, \ldots, r-s}^{}$((T x S)\R)	davon die Anfangsstücke
T\V	davon das Komplement