Relationale Algebra

Vom ER-Modell zur relationalen Algebra

Das Entity-Relationship-Modell beantwortet die Frage, welche Objekte und Beziehungen eine Datenbank beschreiben soll — doch mit einem Diagramm lässt sich nicht rechnen. Um tatsächlich mit Daten arbeiten zu können, braucht man eine andere Darstellung: Relationen. Eine Relation ist eine Tabelle mit einem festen Schema aus benannten Spalten (Attributen) und einer Menge von Zeilen (Tupeln). Ein ER-Diagramm lässt sich systematisch in ein solches Relationenschema übersetzen, erst dann können Daten gespeichert und verwaltet werden.

Damit stellt sich die Frage: Wie arbeitet man mit Relationen? Die relationale Algebra gibt darauf eine formale Antwort. Sie definiert eine Menge von Operationen, die Relationen als Eingabe nehmen und wieder eine Relation zurückliefern — wie die gewöhnliche Algebra mit Zahlen. Operationen lassen sich so beliebig schachteln und zu komplexen Anfragen zusammensetzen. Entwickelt wurde die relationale Algebra 1970 von Edgar F. Codd, der damit zugleich das relationale Datenbankmodell begründete.

SQL ist im Kern eine lesbare Schreibweise für relationale Algebra: WHERE = Selektion, SELECT = Projektion, JOIN = Verbund.

In der Praxis schreibt man solche Anfragen in SQL — und SQL ist im Kern nichts anderes als eine lesbare Schreibweise für relationale Algebra: WHERE entspricht einer Selektion, SELECT einer Projektion, JOIN einem Verbund. Wer die Algebra versteht, versteht deshalb nicht nur eine Syntax, sondern das Konzept dahinter.

Relation und Relationenschema

Bevor man mit Operationen arbeiten kann, muss klar sein, womit man es eigentlich zu tun hat. Die folgenden Definitionen bauen aufeinander auf:

Begriff	Formal	Tabellen-entsprechung	Beispiel
Domäne	Menge zulässiger Werte	Datentyp einer Spalte	dom(A) = ℤ
Relationen-schema	$R(A_1,\dots ,A_n)$	Tabellenstruktur (Spaltennamen)	$\text{Schueler}(\text{Name}:\text{String},\text{Jahrgang}:\mathbb{Z})$
Tupel	Element $(v_1,\dots ,v_n)$	Eine Zeile	('Amir', 11)
Relation	Endliche Menge von Tupeln	Die gesamte Tabelle mit Daten

Domäne

Eine Domäne $D$ ist eine (nicht leere) Menge zulässiger Werte für ein Attribut $A$ — also der Wertebereich, aus dem ein Attribut seine Werte zieht. Beispiele sind:

• $\text{dom}(A)=\mathbb{Z}$ (ganze Zahlen)
• $\text{dom}(A)=\text{String}$ oder
• eine konkrete Aufzählung wie $\text{dom}(A)=\{\text{11a},\text{11b},\text{12a},\text{12b}\}$.

Jedem Attribut $A$ ist genau eine Domäne $\text{dom}(A)$ zugeordnet.

Schema

Ein Relationenschema (Schema) $R(A_1,A_2,\dots ,A_n)$ ist eine endliche, geordnete Liste von Attributnamen $A_1,\dots ,A_n$, denen jeweils eine Domäne $\text{dom}(A_i)$ zugeordnet ist. Das Schema beschreibt die Struktur einer Tabelle, welche Spalten es gibt und welche Werte darin erlaubt sind, enthält aber selbst noch keine Daten. Man schreibt es zum Beispiel als:

• Schueler(SID: ℤ, Name: String, Klasse: String, Jahrgang: ℤ)

Spielt die Domäne keine Rolle, wird diese oft auch weggelassen:

• Schueler(SID, Name, Klasse, Jahrgang)

Tupel

Ein Tupel $t$ über dem Schema $R(A_1,\dots ,A_n)$ ist eine Abbildung, die jedem Attribut $A_i$ genau einen Wert aus $\text{dom}(A_i)$ zuweist:

$t=(v_1,v_2,\dots ,v_n)\text{mit }{v}_i\in \text{dom}(A_i)$

Beispiele sind:

• (1, 'Amir', '12a', 2024)
• (10, 'Inf', 'Fr. Novak')

Relation

Eine Relation $r$ über dem Schema $R(A_1,\dots ,A_n)$ ist eine endliche Teilmenge des kartesischen Produkts der Domänen:

$r\subseteq \text{dom}(A_1)\times \text{dom}(A_2)\times \cdots \times \text{dom}(A_n)$

Das kartesische Produkt enthält alle denkbaren Kombinationen von Werten aus den Domänen, die Relation ist davon eine Auswahl der tatsächlich gespeicherten Tupel. Zum Beispiel ergibt sich für die Mengen $A=\{1,2,3\}$ und $B=\{a,b\}$ für das Produkt:

$A\times B=(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)$

Da eine Relation eine Menge im mathematischen Sinne ist, hat sie zwei wichtige Konsequenzen: Es gibt keine Reihenfolge der Tupel (Zeilen haben keine feste Position), und es gibt keine Duplikate (zwei Tupel, die in allen Attributwerten übereinstimmen, gelten als identisch und kommen nur einmal vor).

Da sich endliche Relationen sehr gut als Tabelle darstellen lassen, werde an vielen Stellen die Begriffe Relation und Tabelle synonym verwendet.

Das Relationenschema ergibt sich direkt aus der Übersetzung des ER-Modells. Jede Entitätsmenge wird zu einem Schema, ihre Attribute bleiben erhalten, und der Primärschlüssel wird übernommen. Beziehungen werden, je nach Kardinalität, entweder als eigene Relation modelliert oder durch einen Fremdschlüssel in einer der beteiligten Relationen ausgedrückt.

Die Grundoperatoren

Damit die Wirkung jeder Operation ohne Umwege ablesbar ist, arbeiten wir in diesem Abschnitt mit kleinen, abstrakten Relationen ($R$, $S$, $U$, $V$, ...) mit einfachen Werten wie $1,2,3$ oder $a,b,c$. Jedes Beispiel nennt zuerst die Eingabe-Relation(en), dann den Ausdruck, dann das Ergebnis. Die Übungsaufgaben am Ende wenden die Operatoren anschließend auf das Schulschema von oben an.

1. Selektion (σ)

Notation: ${\sigma }_{\text{Bedingung}}(\text{Relation})$

Das griechische Sigma ($\sigma$) steht für „select" — die Selektion wählt Zeilen aus, ohne die Struktur zu verändern. Die Selektion filtert Zeilen einer Relation anhand einer Bedingung. Das Ergebnis enthält nur diejenigen Tupel, für die die Bedingung wahr ist. Das Schema (also die Spalten) bleibt dabei unverändert.

Beispiel: ${\sigma }_{A=1}(R)$ (alle Tupel mit $A=1$)

R
A	B	C
1	a	2
2	a	2
3	c	1
1	b	4

→

σA=1(R)
A	B	C
1	a	2
1	b	4

Bedingungen können mit $\wedge$ (UND), $\vee$ (ODER) und $\neg$ (NICHT) kombiniert werden:

Beispiel: ${\sigma }_{A=2\vee B=\text{’c’}}(R)$

R
A	B	C
1	a	2
2	a	2
3	c	1
1	b	4

→

σA=2∨B='c'(R)
A	B	C
2	a	2
3	c	1

2. Projektion (π)

Notation: ${\pi }_{\text{Attributliste}}(\text{Relation})$

Das griechische Pi ($\pi$) steht für „project". Die Projektion wählt Spalten aus einer Relation aus. Alle anderen Spalten werden weggelassen. Doppelte Zeilen werden im Ergebnis automatisch entfernt (da eine Relation per Definition eine Menge ist, also keine Duplikate enthält).

Beispiel: ${\pi }_{B,C}(R)$ (nur die Spalten $B$ und $C$)

Die Kombination $(a,2)$ erscheint nur einmal, obwohl sie in der Eingabe zweimal vorkommt (bei $A=1$ und bei $A=2$).

R
A	B	C
1	a	2
2	a	2
3	c	1
1	b	4

→

πB,C(R)
B	C
a	2
c	1
b	4

3. Kombination von Selektion und Projektion

Da jede Operation wieder eine Relation liefert, können Operationen problemlos verschachtelt werden. Um nur die $B$-Werte aller Tupel mit $A=1$ zu erhalten:

$${\pi }_B\left({\sigma }_{A=1}(R)\right)$$

Die Auswertung erfolgt von innen nach außen: zuerst wird selektiert (Zeilen filtern), dann projiziert (Spalten auswählen).

R
A	B	C
1	a	2
2	a	2
3	c	1
1	b	4

→

πB(σA=1(R))
B
a
b

4. Umbenennung (ρ)

Das griechische Rho ($\rho$) steht für „rename". Notation: ${\rho }_{\text{neuerName}}(\text{Relation})$ oder ${\rho }_{\text{neuerName}(A_1\to B_1,A_2\to B_2,\dots )}(\text{Relation})$

Die Umbenennung gibt einer Relation oder einzelnen Attributen einen neuen Namen. Das ist besonders wichtig, wenn zwei Relationen mit gleichen Attributnamen verknüpft werden sollen.

Beispiel: Die Relation $R$ soll unter dem neuen Namen $S$ geführt werden und ihre Attribute in $X,$ $Y,$ $Z$ umbenennen:

$${\rho }_{S(A\to X,B\to Y,C\to Z)}(R)$$ Die Menge der Tupel bleibt identisch, nur das Schema ändert sich.

R
A	B	C
1	a	2
2	a	2
3	c	1
1	b	4

→

S
X	Y	Z
1	a	2
2	a	2
3	c	1
1	b	4

5. Vereinigung (∪)

Notation: $R\cup S$

Die Vereinigung fügt die Tupel zweier Relationen zusammen. Doppelte Tupel werden automatisch entfernt. Beide Relationen müssen vereinigungskompatibel sein, d. h. sie müssen die gleiche Anzahl an Attributen mit kompatiblen Datentypen haben.

Vereinigungskompatibel: gleiche Attributanzahl und Domänen, Attributnamen dürfen abweichen. $$R\cup S$$

R
A	B
1	2
1	3

S
C	D
1	2
2	3

→

R ∪ S
A	B
1	2
1	3
2	3

Das Tupel $(1,2)$ kommt in beiden Relationen vor und erscheint im Ergebnis deshalb nur einmal.

6. Differenz (−)

Notation: $R-S$

Die Differenz liefert alle Tupel, die in $R$, aber nicht in $S$ enthalten sind. Auch hier gilt die Voraussetzung der Vereinigungskompatibilität.

$$R-S$$

R
A	B
1	2
1	3

S
C	D
1	2
2	3

→

R − S
A	B
1	3

7. Schnittmenge (∩)

Notation: $R\cap S$

Die Gültigkeit von $R\cap S=R-(R-S)$ lässt sich einfach mit einem Mengendiagramm (Venn-Diagramm) zeigen. Die Schnittmenge liefert alle Tupel, die sowohl in $R$ als auch in $S$ enthalten sind. Die Schnittmenge ist kein eigenständiger Grundoperator, sondern lässt sich durch Differenz ausdrücken: $R\cap S=R-(R-S)$. Sie wird dennoch häufig als abgeleiteter Operator verwendet, da sie ausdrucksstärker ist.

$$R\cap S$$

R
A	B
1	2
1	3

S
C	D
1	2
2	3

→

R ∩ S
A	B
1	2

8. Kreuzprodukt (×)

Notation: $R\times S$

Das Kreuzprodukt (kartesisches Produkt) kombiniert jede Zeile von $R$ mit jeder Zeile von $S$. Wenn $R$ $n$ Tupel und $S$ $m$ Tupel hat, enthält das Ergebnis $n\cdot m$ Tupel. Das Ergebnis-Schema enthält alle Attribute beider Relationen.

$$R\times S$$ Das Kreuzprodukt allein ist selten sinnvoll, weil es auch inhaltlich zusammenhanglose Kombinationen erzeugt. Es dient vielmehr als Grundbaustein für den Verbund (Join).

R
A	B
1	2
1	3

S
C	D
1	2
2	3

→

R × S
A	B	C	D
1	2	1	2
1	2	2	3
1	3	1	2
1	3	2	3

9. Verbund / Join (⋈)

Theta-Join

Notation: $R\underset{\text{Bedingung}}{\bowtie }S$

Der Verbund (englisch: Join) ist die wichtigste Operation zum Verknüpfen von Relationen. Ein Theta-Join ist im Wesentlichen ein Kreuzprodukt, auf das anschließend eine Selektion angewendet wird:

$$R\underset{\text{Bed.}}{\bowtie }S={\sigma }_{\text{Bed.}}(R\times S)$$

Die Bedingung kann ein beliebiger Vergleichsausdruck ($=$, $<$, $>$, $\le$, $\ge$, $\ne$) sein.

Mit der Punktnotation (R.A,S.A) können gleich benannte Attribute verschiedener Relationen angesprochen werden. Nur Tupel, für die $A$ in $R$ dem Wert $A$ in $S$ entspricht:

$$R\underset{R.A=S.A}{\bowtie }S$$

R
A	B
1	x
2	y
3	z

S
A	B
2	100
3	200
4	300

→

R ⋈R.A=S.A S
R.A	R.B	S.A	S.B
2	y	2	100
3	z	3	200

Natural Join (natürlicher Verbund)

Der Natural Join ($\bowtie$ ohne Bedingung) verbindet automatisch über alle Attribute, die in beiden Relationen gleich benannt sind, und liefert dabei keine doppelten Spalten. Er ist besonders kompakt zu schreiben.

$$X\bowtie Y$$

Verknüpft wird über das gleichnamige Attribut $A$:

X
A	B
1	a
2	a
3	c

Y
A	C
1	3
2	2
1	2

→

X ⋈ Y
A	B	C
1	a	3
1	a	2
2	a	2

Mehrere gleichnamige Attribute ($A$ und $C$) werden ebenfalls berücksichtigt. Nur Tupel, bei denen beide Werte übereinstimmen, landen im Ergebnis:

U
A	B	C
1	a	2
2	a	2
3	c	1

V
A	C	D
1	3	a
2	2	b
1	2	c

→

U ⋈ V
A	B	C	D
1	a	2	c
2	a	2	b

Zusammenfassung der Operatoren

¹ AS ist kein eigenständiger Operator, sondern Syntax innerhalb von SELECT oder FROM.

Operator	Symbol	Zweck	SQL
Selektion	$\sigma$	Zeilen filtern	WHERE
Projektion	$\pi$	Spalten auswählen	SELECT
Umbenennung	$\rho$	Attribute/Relation umbenennen	AS ¹
Vereinigung	$\cup$	Zeilen zusammenführen	UNION
Differenz	$-$	Zeilen subtrahieren	EXCEPT
Schnittmenge	$\cap$	Gemeinsame Zeilen	INTERSECT
Kreuzprodukt	$\times$	Alle Kombinationen	CROSS JOIN
Verbund	$\bowtie$	Verknüpfung nach Bedingung	JOIN

Training: Operatoren anwenden

Gegeben seien drei Relationen $P$, $Q$ und $T$:

P
A	B
a	c
b	c
c	f

Q
B	C
c	f
e	g
c	g

T
C
f
g

Berechne die folgenden Ausdrücke von Hand. Gib jeweils das vollständige Ergebnis als Relation an.

(a) $P\cup Q$	(f) ${\rho }_{M(A\to X,B\to Y)}(P)$
(b) $P-Q$	(g) $P\bowtie Q$
(c) $P\cap Q$	(h) $Q\times P$
(d) ${\pi }_A(P)$	(i) $P\underset{P.B\ge Q.C}{\bowtie }Q$
(e) ${\sigma }_{B=‘c‘}(P)$	(j) ${\pi }_A(P)-{\pi }_A(P\bowtie Q)$ (Beschreibe die Operation in Worten.)

Übungsaufgaben mit Schulschema

Die Übungsaufgaben in diesem Dokument beziehen sich auf das folgende Schema einer Schulverwaltung:

Primärschlüssel sind unterstrichen (SID) und Fremdschlüssel mit ↑ markiert (↑FID).

• Schueler (SID, Name, Klasse)
• Fach (FID, Bezeichnung, Lehrkraft)
• Kurs (↑SID, ↑FID, Note)

Schueler
SID	Name	Klasse
1	Amir	12
2	Lena	12
3	Jonas	12
4	Mia	11
5	Tobias	11

Fach
FID	Bezeichnung	Lehrkraft
10	Inf	Fr. Novak
20	Ma	Hr. Wagner
30	Eng	Fr. Petersen

Kurs
SID	FID	Note
1	10	2
1	20	1
2	10	3
2	30	2
3	10	1
3	20	2
4	20	4
5	30	3

Training: Selektion und Projektion

Aufgabe 1 — Selektion und Projektion

1. Formuliere einen Ausdruck der relationalen Algebra, der alle Kurse mit der Note 1 liefert.
2. Formuliere einen Ausdruck, der nur die Namen aller Schülerinnen und Schüler ausgibt, ohne weitere Attribute.
3. Welche Schülerinnen und Schüler befinden sich in der Klasse 11? Gib nur ihre Namen und SIDs aus.

Training: Verbund (Join)

Aufgabe 2 — Verbund (Join)

1. Formuliere einen Ausdruck, der die Namen aller Schülerinnen und Schüler und die von ihnen erhaltenen Noten ausgibt.
2. Erweitere den Ausdruck aus (1) so, dass auch die Bezeichnung des zugehörigen Faches mit ausgegeben wird.
3. Welche Schülerinnen und Schüler (Name) werden von Fr. Novak unterrichtet?

Training: Mengenoperationen

Aufgabe 3 — Mengenoperationen (Ohne Verwendung von Join.)

1. Formuliere einen Ausdruck, der die SIDs aller Schüler liefert, die Informatik (FID=10) oder Englisch (FID=30) belegen (oder beides).
2. Welche Schüler (SID) belegen sowohl Informatik als auch Mathematik?
3. Welche Schüler (SID) belegen Informatik, aber nicht Mathematik?

Training: Komplexe Anfragen

Aufgabe 4 — Komplexe Anfragen

1. Gib die Namen aller Schülerinnen und Schüler aus der Klasse 12 aus, die in irgendeinem Fach die Note 1 erhalten haben.
2. Gib für jeden Schüler, der Informatik belegt, dessen Namen und die zugehörige Note aus.
3. Welche Lehrkräfte unterrichten Schülerinnen und Schüler aus der Klasse 12? Gib nur die Namen der Lehrkräfte aus.

Aufgabe 5

Gegeben sei folgende Erweiterung des Schemas:

• Raum (RID, Bezeichnung, Gebaeude)
• Unterricht (↑FID, ↑RID, Wochentag, Stunde)

1. In welchen Räumen findet Informatikunterricht statt? Gib die Raumbezeichnungen aus.
2. Formuliere einen Ausdruck, der alle Fächer ausgibt (Bezeichnung), die in Gebäude „B" unterrichtet werden.
3. Welche Schülerinnen und Schüler (Name) belegen ein Fach, das montags ($\text{Wochentag}=\text{’Montag’}$) stattfindet?