In der Theorie der Datenbanken versteht man unter einer relationalen Algebra oder Relationenalgebra eine Menge von Operationen zur Manipulation von Relationen. Sie ermöglicht es, Relationen zu filtern, zu verknüpfen, zu aggregieren oder anderweitig zu modifizieren, um Anfragen an eine Datenbank zu formulieren.
Normalerweise werden Anfragen und Programme nicht direkt in einer relationalen Algebra formuliert, sondern in einer deklarativen Sprache wie SQL, XQuery SPARQL oder auch Datalog. Diese Programme und Anfragen werden üblicherweise zunächst in eine (i. Allg. erweiterte) relationale Algebra übersetzt. Der entstehende Operatorbaum wird dann mit Hilfe relationaler Gesetze transformiert, um eine möglichst effiziente Auswertung der Anfragen zu ermöglichen., Chapter 11
Geschichte und Bedeutung Im Jahr 1941 stellte Alfred Tarski in seinem Papier „On the calculus of relations“ erstmals Ideen einer relationalen Algebra vor. Insbesondere führte er die relationalen Operationen „Vereinigung“, „Durchschnitt“ und „Join“ ein, wobei er sich allerdings auf zweistellige Relationen beschränkte.
Am Ende seines Artikels erwähnt er, dass er eigentlich nicht so sehr das Ziel hatte, neue Ergebnisse zu präsentieren, als vielmehr das Interesse an einer bestimmten logischen Theorie zu wecken, die bislang nicht beachtet wurde:
Ende der 1960er Jahre entwickelte Edgar F. Codd am IBM Research Laboratory in San Jose die Grundlagen der heutigen relationalen Algebra. Ob ihn die Arbeit Tarskis dazu inspirierte, ist nicht bekannt. Zu Beginn seines Papiers von 1969 stellt er die Behauptung auf, dass das relationale Modell in vielen Aspekten dem Graphenmodell und dem Netzwerkmodell, die zu dieser Zeit „en vogue“ (französisch für „in Mode“) waren, überlegen sei.
Er bezieht sich damit auf die Tatsache, dass die Dauer der Beantwortung von Anfragen sehr stark vom Aufbau des jeweiligen Netzwerks abhängt. Sofern Daten abgerufen werden sollen, die im Netzwerk benachbart sind, muss der Benutzer nur sehr kurz auf eine Antwort warten. Sind die gewünschten Daten jedoch im Netzwerk stark verstreut, kann die Wartezeit unzumutbar lang werden. Die Datenbankentwickler mussten bei der Erstellung eines Netzwerkmodells von vorneherein sämtliche denkbaren Anfragen berücksichtigen, da nachträgliche Änderungen am Datenmodell nur noch sehr schwer umgesetzt werden konnten. Um dieses Problem zu beheben, hatte Codd die Idee, die Daten nicht mehr in einem Netzwerk zu speichern, sondern in Relationen (Tabellen), die je nach Anfrage unterschiedlich miteinander verknüpft werden können:
Er wagte folgende geradezu prophetische Prognose, dass Datenbanken künftig viele Relationen in gespeicherter Form enthalten würden:
Ende 1970, d. h. im selben Jahr, in dem Codds Arbeit publik wurde, stellen Rudolf Bayer und Ed McCreight den B-Baum vor. Dies ist ein Datenbankindex, der 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 1970er Jahren begann auf Basis dieser beiden Arbeiten die Erfolgsgeschichte der Relationalen Datenbanken einschließlich der zugehörigen Sprache SQL. An Codds Arbeitsstätte, d. h. am IBM Research Laboratory in San Jose, wurden die Sprache SEQUEL sowie das experimentelle Datenbanksystem System R entwickelt. Später wurde SEQUEL in SQL umbenannt. Zu Beginn der 1980er Jahre gab es für die Anfragesprache SQL die ersten kommerziellen relationalen Datenbanksysteme: Db2 von IBM und Oracle von Relational Software Inc. Heute ist SQL aus der Welt der Datenbanken nicht mehr wegzudenken (siehe beispielsweise :Kategorie:Relationales Datenbankmanagementsystem). Aber auch diverse weitere Sprachen, wie zunächst QBE oder QUEL und später Datalog, XQuery oder SPARQL, basieren letztendlich auf der Idee Codds, Relationen zum Speichern von Daten einzusetzen.
Als Anfragesprache für Endbenutzer ist die Relationenalgebra heute ohne Bedeutung, datenbank-intern spielt sie jedoch in allen Hochleistungs-Datenbanken eine wesentliche Rolle. Die Datenbanksprache SQL wird in diesen Systemen durch die Anfragebearbeitung des Datenbanksystems intern auf eine Folge von Operationen der Relationenalgebra und weiterer Operationen (wie z. B. für den Zugriff auf Indexe) übersetzt, die durch den Anfrageoptimierer in eine optimale Ausführungsreihenfolge gebracht werden.
Allgemein Eine relationale Algebra definiert Operationen, die sich auf eine Menge von Relationen anwenden lassen. Damit können Relationen beispielsweise gefiltert, verknüpft oder aggregiert werden. 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 Abfragesprachen in relationalen Datenbanken. Hier werden die Operationen der relationalen Algebra in sogenannten Datenbankoperatoren implementiert. Wenn jede Operation der relationalen Algebra in der Abfragesprache durch (mindestens) einen Ausdruck umgesetzt werden kann, heißt sie relational vollständig; der Ausdruck kann hierbei mehrere Datenbankoperatoren verknüpfen. Wenn jede Operation auch durch (genau) einen Datenbankoperator umgesetzt werden kann, heißt sie streng relational vollständig; es darf also immer nur genau ein Datenbankoperator in ein und demselben umsetzenden Ausdruck enthalten sein. Wenn die Bedingung der strengen relationalen Vollständigkeit auch in die andere Richtung gilt, es also zu jedem Datenbankoperator eine entsprechende Operation der relationalen Algebra gibt, dann heißt die Abfragesprache äquivalent zur relationalen Algebra, kurz: relational äquivalent.
Da es für die relationale Algebra (mehrere) minimale Mengen von Operationen gibt, aus denen alle weiteren Operationen zusammengesetzt werden können, reicht es für die (streng) relationale Vollständigkeit aus, die Abfragesprache mit diesen „Basisoperationen“ zu vergleichen. Das folgt daraus, dass die relationale Algebra trivialerweise selbst-äquivalent ist und durch ein minimales System aus Operationen schon vollständig (im Hinblick auf Operationen) beschrieben ist. Ein übliches minimales System aus Operationen besteht aus den sechs Operationen: Projektion, Selektion, Kreuzprodukt, Vereinigung, Differenz und Umbenennung.
Die relationale Algebra wird wegen ihrer theoretischen Klarheit oft als Bewertungsmaßstab für die Mächtigkeit bzw. Ausdruckskraft von Abfragesprachen genutzt, u. a. mittels der gerade beschriebenen Vergleichsbegrifflichkeiten. Allerdings darf man von der größeren Nähe einer Abfragesprache zur relationalen Algebra nicht auf deren größere Mächtigkeit schließen. Abfragesprachen, die relational vollständig oder sogar streng relational vollständig sind, haben oft einen deutlich größeren Funktionsumfang als dies durch die alleinige Umsetzung der Relationen-Algebra-Operationen möglich wäre. Zum Beispiel ist in der relationalen Algebra die Möglichkeit der Bildung der transitiven Hülle einer Relation, was etwa bei rückbezüglichen Relationen interessant ist, nicht gegeben. Von der strengen relationalen Vollständigkeit einer Abfragesprache lässt sich eher auf eine Mindestfunktionalität, von der relationalen Äquivalenz eher auf eine Maximalfunktionalität schließen, während die nichtstrenge relationale Vollständigkeit die wenigsten konkreten Informationen über die Abfragesprache liefert.
Im Gegensatz zu den Kalkülen ist die relationale Algebra sicher, d. h., sie liefert in endlicher Zeit ein endliches Resultat. Eine relationale Algebra ist darüber hinaus ein Beispiel für eine prozedurale Sprache; im Unterschied zu Kalkülen, die meist als deskriptive Sprachen formalisiert sind.
Operationen
Mengenoperationen
Um Mengenoperationen auf den Relationen und durchführen zu können, müssen beide miteinander kompatibel sein. Die Typkompatibilität zweier Relationen ist gegeben, wenn
und den gleichen Grad (Attributelementanzahl) haben der Wertebereich der Attribute von und identisch ist
Die Typkompatibilität wird auch Vereinigungsverträglichkeit genannt.
Vereinigung mini|150px|Vereinigung Bei der Vereinigung werden alle Tupel der Relation mit allen Tupeln der Relation zu einer einzigen Relation vereint. Voraussetzung dafür ist, dass und das gleiche Relationenschema haben. Das heißt, sie haben gleiche Attribute und Attributtypen. Duplikate werden bei der Vereinigung gelöscht.
Definition
Beispiel + : A B C 1 2 3 4 5 6+ : A B C 7 8 9 4 5 6+ : A B C 7 8 9 4 5 6 1 2 3
Voraussetzung Vereinigungsverträglichkeit von und
Schnittmenge (Intersection) mini|150px|Schnitt
Das Ergebnis der Durchschnittsoperation sind all die Tupel, die sich sowohl in als auch in finden lassen. Der Mengendurchschnitt lässt sich auch durch die Mengendifferenz ausdrücken:
Definition
Beispiel + : A B C 1 2 3 4 5 6+ : A B C 7 8 9 4 5 6+ : A B C 4 5 6
Voraussetzung Vereinigungsverträglichkeit von und
Differenz mini|150px|Differenz
Statt der in der Mengenlehre üblichen Schreibweise für die Differenz zweier Mengen, , wird in der relationalen Algebra häufig geschrieben. Es handelt sich hierbei jedoch ausdrücklich nicht um die übliche Subtraktion. Bei der Operation werden aus der Relation alle Tupel entfernt, die auch in der Relation vorhanden sind. Die Differenz (ebenso wie die symmetrische Differenz) ist keine monotone Operation, daher ist auch die relationale Algebra im Vergleich zu anderen deklarativen Anfragesprachen (z. B. Datalog) nicht monoton.
Definition
Beispiel + : A B C 1 2 3 4 5 6+ : A B C 7 8 9 4 5 6+ : A B C 1 2 3
Voraussetzung Vereinigungsverträglichkeit von und
Symmetrische Differenz mini|150px|Symmetrische Differenz
Bei der symmetrischen Differenz handelt es sich um die Menge aller Tupel, die entweder in oder in , aber nicht in beiden gleichzeitig enthalten sind.
Die Operation kann aus den Grundoperationen abgeleitet werden:
Beispiel + : A B C 1 2 3 4 5 6+ : A B C 7 8 9 4 5 6+ : A B C 1 2 3 7 8 9
Voraussetzung Vereinigungsverträglichkeit von R und S
Kartesisches Produkt (Kreuzprodukt) mini|Kartesisches Produkt Das kartesische Produkt ist eine Operation, welche dem kartesischen Produkt aus der Mengenlehre ähnelt.
Das Resultat des kartesischen Produkts ist die Menge aller Kombinationen der Tupel aus und , d. h., 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. Gleichnamige Merkmale der zwei Tabellen werden durch Voranstellen des Tabellennamens referenziert. Die Anzahl der Tupel (Zeilen) in der Resultatstabelle ist das Ergebnis der Multiplikation der Zeilenanzahlen der Ausgangstabellen.
Definition
Zwei beliebige Relationen und sind gegeben. Das kartesische Produkt ist definiert durch
Beispiel + : A B C D 1 2 3 4 4 5 6 7 7 8 9 0+ : E F G 1 2 3 7 8 9+ : 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
Projektion mini|150px|Projektion
Die Projektion entspricht der Projektionsabbildung aus der Mengenlehre und 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, das heißt, die Projektion blendet Spalten aus. Wenn die Attributliste ist, schreibt man oder in der linearen Schreibweise . heißt auch Projektionsliste. Duplikate in der Ergebnisrelation werden eliminiert.
Definition
Sei eine Relation über und .
Die , das heißt, die Tupel erhalten nur die Attribute aus der Attributliste .
Beispiel + : A B C 1 2 3 4 5 6 1 3 8+ A B 1 2 4 5 1 3+ A 1 4
Voraussetzung Die angegebenen Spalten müssen in enthalten sein.
Selektion mini|150px|Selektion