Eine Algebra$ \mathcal{R} = (R, id, \pi, \sigma, \times, \div, \cup, \cap, \setminus) $ heißt Relationale Algebra wenn die Trägermenge oder -klasse $ R $ eine Menge bzw. Klasse von Relationen mit benannten Attributen ist.
$ id: R \rightarrow R $ ist die so genannte Identitätsfunktion: Es gilt stets $ id(r) = r $
$ \pi_{f_1 \,\text{as}\, a_1, \,\ldots, \,f_n \,\text{as}\, a_n}: R \rightharpoonup R $ sind die so genannten Projektionsfunktionen, die mit Hilfe der Funktionen $f_i$ für jedes Tupel $n$ neue Attribute berechnen. Die neuen Attribute haben die Namen $a_i$.
$ \sigma_b: R \rightharpoonup R $ sind die so genannte Selektionsfunktionen: Mit ihrer Hilfe werden aus einer Relation diejenigen Tupel selektiert, die die Bedingung $b$ erfüllen.
$ \times: R, R \rightharpoonup R $ ist das kartesische Produkt, das zwei Relationen zu einer Relation verknüpft. Für jede mögliche Kombination von zwei Tupeln der Urbildrelationen ist die Konkatenation der beiden Tupel Element der Bildrelation.
$ \div: R, R \rightharpoonup R $ ist die Division. Im Prinzip ist dies die Umkehrfunktion des kartesischen Produktes.
$ \cup: R, R \rightharpoonup R $ ermittelt die Vereinigung zweier (strukturgleicher) Relationen.
$ \cap: R, R \rightharpoonup R $ ermittelt den Durchschnitt zweier (strukturgleicher) Relationen.
$ \setminus: R, R \rightharpoonup R $ ermittelt die Differenz zweier (strukturgleicher) Relationen.
Geschichte
1969/1970 schlägt Edgar Frank Codd vor, Relationen zu verwenden, um große Datenbanken (“large data banks”)
zu verwalten[1][2].
Er definiert dazu insbesondere die beiden relationalen Operationen „Projektion“ und „Join“.
Im ersten Satz des Abstract seines internen Reports „Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks“
von 1969 macht Codd eine geradezu prophetische Aussage:
The large, integrated data banks of the future will
contain many relations of various degrees in stored form. (Codd (1969)[1])
Übersetzung (von Kowarschick):
Die großen, integrierten Datenbanken der Zukunft werden
viele Relationen unterschiedlichsten Grades in gespeicherter Form enthalten.
Ende 1970, d. h. im selben Jahr, in dem Codds Arbeit publik wurde, stellen Rudolf Bayer und Ed McCreight den B-Baum
vor, eine Datenstruktur, die es ermöglicht, Relationen mit einer großen Anzahl von Tupel so auf einer Festplatte zu speichern,
dass der lesende Zugriff auf Tupel sowie die Modifikation von Tupeln hocheffizient erfolgen
kann.[3][4]
In den 70er Jahren begann auf Basis dieser beiden Arbeiten die Erfolgsgeschichte der Relationalen Datenbanken
einschließlich der zugehörigen Sprache SQL.
SQL
Die Relationale Algebra ist Grundlage der Datenbank-Sprache SQL. In SQL
werden allerdings Tabellen an Stelle von Relationen eingesetzt.
Unterschiede
Relation
Tabelle
duplikatfrei: Relationen sind Mengen, daher kommt kein Tupel zweimal vor.
Duplikate: Tabellen sind Listen, daher können gleiche Tupel mehrfach vorkommen.
Allerdings gilt dies in SQL nur bei berechneten Tabellen, nicht aber bei gespeicherten Tabellen.
ungeordnet: Relationen sind Mengen, daher sind die darin enthaltenen Tupel nicht geordnet.
In einer Relationalen Algebra kann es keine Operation zum Sortieren von Relationen geben.
geordnet: Tabellen sind (geordnete) Listen, daher ist die Reihenfolge der Tupel festgelegt.
Allerdings kann man sich bei SQL-Befehlen nicht darauf verlassen, dass das Ergebnis in einer bestimmten Reihenfolge ausgegeben wird. In SQL gibt es daher eine spezielle ORDER-BY-Klausel, um eine bestimmte Reihenfolge zu erzwingen.
Außerdem werden in SQL (tabellen-)Zeilen (Rows) an Stelle von Tupeln verwendet. In Tabellenzeilen sind die einzelnen Spalten benannt und haben überdies eine Position.
Die klassische Tupel-Definition unterscheidet die verschiedenen Attribute anhand ihrer Position. Allerdings ist es nicht unüblich diesen Positionen Namen zu geben. So wird bei einer Raumkoordinate die erste Position i. Allg. mit $x$ bezeichnet, die zweite mit $y$ und die dritte mit $z$.
In Programmiersprachen heißen Tupel, deren Elemente über die Position bestimmt werden, Arrays oder Listen: [35, true, 'Hallo'].
Tupel deren Elemente mittels Identifikatoren bezeichnet werde, heißen Records oder Objekte: {a: 35, b: true, c: 'Hallo'}
Relationale Operationen
Identität
Die Identitätsfunktion verändert eine Tabelle nicht.
Die Identiätsfunktion liefert als Ergebnis stets die Urbildrelation zurück. Das heißt, sie verändert eine Relation nicht.
Die Identitätsfunktion ist die einzige totale Funktion der Relationalen Algebra. Das heißt, sie kann auf jede beliebige Relation angewendet werden.
In SQL wird eine derartige Funktion benötigt, um den gesamten Inhalt einer Relation zu erfragen, da in jeder
SQL-Anweisung zum Lesen von Dateninhalten mindestens eine relationale Operation enthalten sein muss.
In SQL 92[5]
wurde zu diesem Zweck der Befehl table eingeführt, dessen einzige Aufgabe es war, die ihm übergebene
Tabelle (Relation) vollständig auszugeben. Dieser Befehl hat sich jedoch nicht durchgesetzt
(auch wenn PostgreSQL ihn unterstützt[6]).
So ist es kein Wunder, dass diese Identitätsfunktion in SQL 99[7]
nicht mehr enthalten ist. Das ist auch nicht notwendig, da eine Projektion, die alle Attribute einer Relation unverändert zurück gibt,
ebenfalls als Identitätsfunktion verwendet werden kann (siehe nachfolgenden Abschnitt).
Beispiel
$r$
→
$id(r)$
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
a
b
c
5
13
a
d
b
7
17
c
f
g
3
21
→
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
a
b
c
5
13
a
d
b
7
17
c
f
g
3
21
Projektion
Eine Projektionsfunktion entfernt Spalten aus einer Tabelle und sortiert sie gegebenenfalls um.Genauer: Eine Projektionsfunktion berechnet neue Spalteninhalte aus den alten Spalteninhalten. Dabei entstehende Duplikattupel werden ebenfalls entfernt.
Die Projektionsfunktion $\pi$ wurde von Codd eingeführt, um Attribute einer Relation entfernen können. Außerdem führte Codd noch eine Permutationsfunktion ein, um die Reihenfolge der Attribute zu ändern.[1][2]
In der Zwischenzeit wird die Projektionsfunktion allgemeiner definiert. Sie berechnet für jedes Tupel einer Relation aus dessen Attributwerten ein neues Tupel.
Für die Benennung der neuen Attributwerte ist ebenfalls die Projektionsfunktion zuständig. Insbesondere ist die Permutationsfunktion damit überflüssig geworden. Deren
Aufgabe wird von der Projektionsfunktion ebenfalls wahrgenommen.
Beispiele
$r$
→
$\pi_{a_4, a_1}(r)$
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
c
b
c
5
13
a
d
g
7
17
a
f
g
3
21
→
$a_4$
$a_1$
5
c
7
a
3
a
Attribute können auch berechnet und (um-)benannt werden. Duplikate, wie z. B. (a, g, 24), werden (in der Relationalen Algebra, nicht in SQL!) automatisch entfernt.
$r$
→
$\pi_{a_1, a_3, a_4+a_5 \rm{\,as\,} b_1}(r)$
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
c
b
c
5
13
a
d
g
7
17
a
f
g
3
21
→
$a_1$
$a_3$
$b_1$
c
a
18
a
g
24
Die Identitätsfunktion kann – wie es bereits weiter oben angesprochen wurde – mit Hilfe der Projektionsfunktion nachgebildet werden. Allerdings benötigt man für jede
Relation eine spezielle Projektionsfunktion:
$r$
→
$\pi_{a_1, a_2, a_3, a_4, a_5}(r)$
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
c
b
c
5
13
a
d
g
7
17
a
f
g
3
21
→
$a_1$
$a_2$
$a_3$
$a_4$
$a_5$
c
b
c
5
13
a
d
g
7
17
a
f
g
3
21
In SQL kann man abkürzend den Stern „*“ verwenden. Dieser bezeichnet alle Attribute der aktuellen Relation.
Mit R.* werden in SQL alle Attribute der Relation R bezeichnet. Für das obige Beispiel kann man in der
Relationalen Algebra analog folgenden Abkürzungen definieren:
Mit dem Stern-Operator man also eine alternative Definition der Identitätsfunktion mit Hilfe des Projektionsoperators angeben, dieohne die Attributnamen der jeweiligen Relation auskommt. (In SQL ist die Verwendung des Sternoperator allerdings verpönt, da sich die Attribute einer Tabelle im Laufe der Zeit ändern können (Schemaevolution) und sich damit die Bedeutung des Sterns ändert. Das heißt, Anfragen, die einen * enthalten, können plötzlich weniger, mehr oder andere Spalten im Ergebnis liefern.)
