Relationale Algebra

Die Relationenalgebra oder Relationale Algebra ist eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu verknüpfen und komplexere Informationen daraus herzuleiten.

Es werden Operationen definiert, die sich auf einer Menge von Relationen anwenden lassen. Damit lassen sich bspw. Relationen verknüpfen, filtern oder umbenennen. Die Ergebnisse aller Operationen sind ebenfalls Relationen. Aus diesem Grund bezeichnet man die Relationenalgebra als abgeschlossen.

Ihre Bedeutung hat die Relationenalgebra als theoretische Grundlage für Anfragesprachen in relationalen Datenbanken. Eine praktische Umsetzung findet die Relationenalgebra als Basis der Sprache SQL.

Inhaltsverzeichnis

1 Operationen

1.1 Mengenoperationen

1.1.1 Vereinigung
1.1.2 Differenz
1.1.3 Durchschnitt

1.2 Kartesisches Produkt (Kreuzprodukt)
1.3 Projektion
1.4 Selektion (Restriktion)
1.5 Join

1.5.1 Equi Join
1.5.2 Natural Join

1.6 Umbenennung
1.7 Division

2 Minimale Menge von Operationen

3 Literatur

4 Weblinks

Operationen

Mengenoperationen

Um Mengenoperationen auf R und S durchführen zu können, müssen beide Relationen miteinander kompatibel sein. Die Typkompatibiltät zweier Relationen ist gegeben, wenn

R und S den gleichen Grad (Tupelelementanzahl) haben
die Attributnamen von R und S übereinstimmen
der Wertebereich der Attribute von R und S identisch ist

Hier ein Beispiel:

R:
A	B	C
1	2	3
4	5	6

S:
A	B	C
7	8	9
4	5	6

Vereinigung

Bei der Vereinigung R ∪ S werden alle Tupel der Relation R mit allen Tupeln der Relation S zu einer einzigen Relation vereint. Voraussetzung dafür ist, dass R und S das gleiche Relationenschema haben. Das heißt, sie haben gleiche Attribute und Attributtypen. Duplikate werden bei der Vereinigung gelöscht.

R ∪ S:
A	B	C
7	8	9
4	5	6
1	2	3

Differenz

Bei der Differenz R \ S (auch R - S) werden aus der ersten Relation alle Tupel entfernt, die auch in der zweiten Relation vorhanden sind.

R \ S:
A	B	C
1	2	3

Durchschnitt

Das Ergebnis der Durchschnittsoperation R ∩ S sind all die Tupel, die sich sowohl in R als auch in S finden lassen. Der Mengendurchschnitt lässt sich auch durch die Mengendifferenz ausdrücken: R ∩ S = R - (R - S)

R ∩ S:
A	B	C
4	5	6

Kartesisches Produkt (Kreuzprodukt)

Das Kartesische Produkt R × S ist eine Operation sehr ähnlich dem Kartesischen Produkt aus der Mengenlehre.

Das Resultat des Kartesischen Produkts ist die Menge aller Kombinationen der Tupel aus R und S. Anders umschrieben: jede Zeile der einen Tabelle wird mit jeder Zeile der anderen Tabelle kombiniert. Wenn alle Merkmale (Spalten) verschieden sind, so umfasst die Resultatstabelle die Summe der Merkmale der Ausgangstabellen. Die Anzahl Tupel (Zeilen) im Resultat ist die Multiplikation der Anzahl Zeilen der Ausgangstabellen.

Die mathematische Beschreibung sieht wie folgt aus:

Zwei beliebige Relationen $A = (a 1, a 2,..., a n)$ und $B = (b 1, b 2,..., b m)$ sind gegeben. Das kartesische Produkt ist definiert durch $A\times B=\{(a_1,a_2,...,a_n,b_1,b_2,...,b_m)|(a_1,a_2,...,a_n)\in A\wedge (b_1,b_2,...,b_m)\in B\}$

Ein gutes Beispiel findet sich auf der englischen Wikipedia-Seite: Relational algebra: The Cartesian Product

Projektion

Die Projektion kann auch Attributbeschränkung genannt werden. Sie extrahiert einzelne Attribute aus der ursprünglichen Attributmenge und ist somit als eine Art Selektion auf Spaltenebene zu verstehen.

Definition

Sei R eine Relation über {A₁, ..., A_k} und β ⊆ {A₁, ..., A_k}.

$R[\beta]:=\{t_{|_{\beta}}:t \in R\}$

Die übliche Schreibweise lautet $Π β (R)$

Beispiel

R:
A	B	C
1	2	3
4	5	6

R[A,B]:
A	B
1	2
4	5

R[A]:
A
1
4

Selektion (Restriktion)

Bei der Selektion kann man mit einem Vergleichsausdruck (Prädikat) eine Auswahl von Tupeln festlegen, die in die Ergebnismenge aufgenommen werden sollen.

Sei R eine Relation.

Definition:

$R[\mbox{Ausdruck}] := \{ t | t \in R \wedge t \mbox{ erfuellt Ausdruck} \}$

Schreibweise:

σ A u s d r u c k (R)

Beispiel:

R:
A	B	C
1	2	4
4	6	7
1	6	7
8	6	1

R[A=1]:
A	B	C
1	2	4
1	6	7

R[C>6]:
A	B	C
4	6	7
1	6	7

Join

Ein Join (deutsch Verbund) bezeichnet die beiden hintereinander ausgeführten Operationen kartesisches Produkt und Selektion.

Beispiel:

R:
A	B	C	D
1	2	3	4
4	5	6	7
7	8	9	0

S:
E	F	G
1	2	3
7	8	9

R x S:
A	B	C	D	E	F	G
1	2	3	4	1	2	3
4	5	6	7	1	2	3
7	8	9	0	1	2	3
1	2	3	4	7	8	9
4	5	6	7	7	8	9
7	8	9	0	7	8	9

JOIN(R, R.A <> S.E, S):
A	B	C	D	E	F	G
4	5	6	7	1	2	3
7	8	9	0	1	2	3
1	2	3	4	7	8	9
4	5	6	7	7	8	9

Es gibt 2 Spezialfälle des Join: den Equi-Join und den Natural Join

Equi Join

Beim Equi-Join wird als erstes das kartesische Produkt gebildet. Dann erfolgt die Selektion mit der Bedingung, dass der Inhalt bestimmter Spalten identisch sein muß.

Beispiel:

R:
A	B	C	D
1	2	3	4
4	5	6	7
7	8	9	0

S:
E	F	G
1	2	3
7	8	9

R x S:
A	B	C	D	E	F	G
1	2	3	4	1	2	3
4	5	6	7	1	2	3
7	8	9	0	1	2	3
1	2	3	4	7	8	9
4	5	6	7	7	8	9
7	8	9	0	7	8	9

JOIN(R, R.A = S.E, S):
A	B	C	D	E	F	G
1	2	3	4	1	2	3
7	8	9	0	7	8	9

Natural Join

Der Natural Join setzt sich zusammen aus dem Equi-Join und einer zusätzlichen Ausblendung gleicher Spalten (Projektion).

Beispiel:

R:
A	B	C	D
1	2	3	4
4	5	6	7
7	8	9	0

S:
E	F	G
1	2	3
7	8	9

R x S:
A	B	C	D	E	F	G
1	2	3	4	1	2	3
4	5	6	7	1	2	3
7	8	9	0	1	2	3
1	2	3	4	7	8	9
4	5	6	7	7	8	9
7	8	9	0	7	8	9

JOIN(R, R.A = S.E, S):
A	B	C	D	F	G
1	2	3	4	2	3
7	8	9	0	8	9

Umbenennung

Durch diese Operation können Attribute und Relationen umbenannt werden.

Beispiel:

R:
A	B	C
1	2	3
4	5	6

R[B→X]:
A	X	C
1	2	3
4	5	6

Division

Die Division kann man sich als Gegenoperation (oder Umkehroperation) zum Join vorstellen. Dies ist nicht völlig korrekt, erleichtert aber die Vorstellung.

Seien β und γ mit γ⊆β Attributmengen für R und S.

Definition:
Umgangssprachlich Formulierung (ungenau und unpräzise):

Nur wenn alle aus S Teilmenge von R sind nimmt man dann die Entschränkung von β\γ.

Beispiel:

R:
A	B	C
2	3	1
5	4	1
1	2	3
2	3	2
5	4	7
5	4	2
2	3	7

S:
A	B
2	3
5	4

R÷S
C
1
2
7

Division als Gegenoperation.

Wenn β∩γ=ø und β,γ,R,S≠ø vorausgesetzt ist, dann gilt:

$( R \triangleright\!\!\triangleleft\, S ) :\!\!\!\!\!- S = R$

Minimale Menge von Operationen

Die minimale Menge von Operationen, d.h. die Menge von Operationen die mindestens notwendig ist, um alle Ausdrücke der relationalen Algebra bilden zu können, umfasst

Projektion
Selektion
Kreuzprodukt
Umbenennung
Vereinigung
Differenz

Alle anderen Operationen (z.B. Joins) lassen sich durch diese Grundoperationen nachbilden.

Literatur

Alfons Kemper, André Eickler: Datenbanksysteme - Eine Einführung, ISBN 3486273922
Peter Kandzia und Hans-Joachim Klein: Theoretische Grundlagen relationaler Datenbanksysteme. ISBN 3411148918

Weblinks

Operationen der Relationenalgebra