Relationale Algebra

Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:

Korrektheit: 2 (teilweise überprüft)

Umfang: 1 (zu gering)

Quellenangaben: 3 (wichtige Quellen vorhanden)

Quellenarten: 5 (ausgezeichnet)

Konformität: 5 (ausgezeichnet)

Definition (Kowarschick (2018))

Eine Algebra $ \mathcal{R} = (R, id, \pi, \sigma, \times, \div, \cup, \cap, \setminus) $ heißt Relationale Algebra wenn die Trägermenge $ R $ eine Menge von Relationen mit benannten Attributen ist.

• $ id: R \rightarrow R $ ist die so genannte Identitätsfunktion: Es gilt stets $ id(r) = r $
• $ \pi $ ist eine abzählbare Menge von (pariellen) Projektionsfunktionen $ \pi_{f_1 \,\text{as}\, a_1, \,\ldots, \,f_n \,\text{as}\, a_n}: R \rightharpoonup R $. Diese berechnen mit Hilfe der Funktionen $f_i$ für jedes Tupel einer Relation $r$ insgesamt $n$ neue Attribue. Die neuen Attribute haben die Namen $a_1$ bis $a_n$. Jeder dieser Funktionen werden die Attribute des jeweiligen Tupels als Argumente übergeben. Das heißt, eine Projektionsfunktion kann nur auf diejenigen Relationen angewendet werden, deren Attribute kompatibel mit den Projektionsfunktionen sind.
• $ \sigma $ ist eine abzählbare Menge von (partiellen) Selektionsfunktionen $ \sigma_b: R \rightharpoonup R $. Mit ihrer Hilfe werden aus einer Relation $r$ diejenigen Tupel selektiert, die die Bedingung $b$ erfüllen, d. h., für die Funktion $b$ den Wert true liefert, wenn sie auf das jeweilige Tupel angewendet wird. Eine Selektionsfunktion kann nur auf diejenigen Relationen angewendet werden, deren Attribute kompatibel mit den Funktion $b$ sind.
• $ \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. Das kartesische Produkt kann nur auf Relationenpaare angewendet werden, deren Attributnamen sich unterscheiden (da ein Tupel mit benannten Attributen keinen Attributnamen mehrfach enthalten kann).
• $ \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. 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))

Ü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.

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 unterschieden werden, heißen Records, Hashmaps/Hasharrays oder auch – z. B. in JavaScript – 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 wurde zu diesem Zweck der Befehl table eingeführt, dessen einzige Aufgabe es ist, die ihm übergebene Tabelle (Relation) vollständig auszugeben. Dieser Befehl ist jedoch 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). PostgreSQL beispielsweise unterstützt ihn dennoch.

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

SQL

TABLE r;  -- seit SQL 92

SELECT a1, a2, a3, a4, a5 FROM r;

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.

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.

Man beachte, dass nur für Tupel mit Positionsattributen der Begriff Permutation sinnvoll ist ([10,30] und [30,10]bezeichnen zwei verschiedene Punkte in einer Ebene). Für Tupel mit Attributnamen benötigt man dagegen keine Funktion, die Attribute vertauscht, da benannte Attribute keine Positionen besitzen ({x: 10, y: 30} und {y: 30, x: 10}bezeichnen denselben Punkt in einer Ebene). Hier muss eine Permutationsfunktion Attributnamen umbenennen können (mittels der $as$-Operation).

Beachten Sie bitte: Die folgenden Beispiele funktionieren sowohl für Positionsattribute als auch für benannte Attribute als auch für Rows, bei denen Attribute sowohl eine Position als auch einen Namen haben.

Beispiele

$r$	→	$\pi_{a_4, \,a_1}(r)$		SQL
$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		SELECT a4, a1 FROM r

Anmerkung: $\pi_{a_4, \,a_1}(r)$ ist eine Abkürzung für $\pi_{a_4 \rm{\,as\,} a_4, \,a_1 \rm{\,as\,} a_1}(r)$.

Attribute können auch berechnet und (um-)benannt werden. Duplikate, wie z. B. (a, g, 24), werden in der Relationalen Algebra automatisch entfernt. In SQL werden Duplikate nur dann entfernt, wenn man das Schlüsselwort „DISTINCT“ angibt. SQL liegt eine so genannte Multimengen-Semantik zu Grunde.

$r$	→	$\pi_{a_1, \,a_3, \,a_4+a_5 \rm{\,as\,} b_1}(r)$		SQL
$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		SELECT DISTINCT a4, a3, a4+a5 AS b1 FROM r

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. In der Projektiosnliste müssen alle Attribute der zugehörigen Funktion genau einmal aufgeführt werden:

$r$	→	$\pi_{a_1, \,a_2, \,a_3, \,a_4, \,a_5}(r)$		SQL
$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		SELECT a1, a2, a3, a4, a5 FROM r; SELECT r.* FROM r; SELECT * FROM r;

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:

$ r = \pi_{a_1, \,a_2, \,a_3, \,a_4, \,a_5}(r) = \pi_{r.*}(r) = \pi_{*}(r) = id(r)$

Mit dem Stern-Operator man also eine alternative Definition der Identitätsfunktion mit Hilfe des Projektionsoperators angeben, die ohne 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.)

Selektion

Eine Selektionsfunktion entfernt Zeilen (= Tupel) aus einer Tabelle.

Eine Selektionsfunktion entfernt Zeilen (= Tupel) aus einer Tabelle.

$r$	→	$\sigma_{a_1= \tt{'a'}}(r)$		SQL
$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$ a d g 7 17 a f g 3 21		SELECT * FROM r WHERE a1 = 'a';

$r$	→	$\sigma_{a_1 = \tt{'a'} \,\wedge\, a_5<21}(r)$		SQL
$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$ a d g 7 17		SELECT * FROM r WHERE a1 = 'a' AND a5 < 20;

Kartesisches Produkt

Das Kartesische Produkt verknüpft alle möglichen Tupelpaare zu jeweils einem Tupel, das alle Attribute beider Tupel enthält.

Das Kartesische Produkt verknüpft alle möglichen Tupelpaare zu jeweils einem Tupel, das alle Attribute beider Tupel enthält.

$r$	$\times$	$s$	→	$r $		SQL
$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	$\times$	$b_1$ $b_2$ true 3.14 false 2.71	→	$a_1$ $a_2$ $a_3$ $a_4$ $a_5$ $b_1$ $b_2$ c b c 5 13 true 3.14 a d g 7 17 true 3.14 a f g 3 21 true 3.14 c b c 5 13 false 2.71 a d g 7 17 false 2.71 a f g 3 21 false 2.71		SELECT * FROM r, s

Join

Ein Join ist formal nichts weiter, als ein Kartesisches Produkt gefolgt von einer Selektion.

Quellen

7. Ullman (1988): Jeffrey D. Ullman; Principles of Database and Knowledge-Base Systems – Volume I: Classical Database Systems; Verlag: Computer Science Press; Adresse: New York, Oxford; ISBN: 0-7167-8158-1; Web-Link; 1988; Quellengüte: 5 (Buch)
8. Ullman (1989): Jeffrey D. Ullman; Principles of Database and Knowledge-Base Systems – Volume II: The New Technologies; Verlag: Computer Science Press; Adresse: New York, Oxford; ISBN: 0-7167-8069-O, 0-7167-8182-X; Web-Link; 1989; Quellengüte: 5 (Buch)
9. Garcia-Molina, Ullman, Widom (2002): Hector Garcia-Molina, Jeffrey D. Ullman und Jennifer Widom; Database Systems: The Complete Book; Verlag: Prentice Hall; Adresse: New Jersey, Upper Saddle River; ISBN: 0-13-031995-3; Web-Link; 2002; Quellengüte: 5 (Buch)
10. Elmasri, Navathe (2011): Ramez Elmasri und Shamkant B. Navathe; Fundamentals of Database Systems; Auflage: 3; Verlag: Pearson Studium; ISBN: 978-0-136-08620-8; 2011; Quellengüte: 5 (Buch)

TO BE DONE

$⨝$, $ ⟕ $, $ ⟖ $, $ ⟗ $, $\triangle$