Relationale Algebra

Die relationale Algebra ist eine theoretische, prozedurale Anfragesprache für die Manipulation von Relationen. Sie bildet das formale und mathematische Fundament für relationale Datenbanksysteme (DBMS) und deren Abfragesprachen (wie SQL).

Zwei theoretische Kerneigenschaften (Theorie-Fundament)

Die relationale Algebra zeichnet sich durch zwei fundamentale Eigenschaften aus, die für den Betrieb eines DBMS zwingend erforderlich sind:

• Vollständigkeit (Relatonal vollständig): Eine Anfragesprache heißt relational vollständig, wenn ihre Ausdrucksstärke mindestens der der relationalen Algebra entspricht (wichtiger Gradmesser für SQL).
• Abgeschlossenheit: Alle Operatoren operieren auf Relationen und liefern als Ergebnis stets wieder eine neue Relation. Dadurch lassen sich relationale Ausdrücke beliebig tief ineinander verschachteln (die theoretische Grundlage für SQL-Subqueries).

Kriterien für Anfragesprachen

• Ad-Hoc-Formulierung: Benutzer soll eine Anfrage direkt formulieren können, ohne ein vollständiges Programm schreiben zu müssen.
• Deskriptivität / Deklarativität: Der Benutzer formuliert „Was will ich haben?“ und nicht „Wie komme ich an das, was ich haben will?“ (wird in SQL vollendet).
• Mengenorientiertheit: Operationen wirken auf Mengen von Daten, nicht navigierend auf einzelnen Elementen („tuple-at-a-time“).
• Adäquatheit: Alle Konstrukte des zugrundeliegenden Datenmodells werden unterstützt.
• Orthogonalität: Sprachkonstrukte sind in ähnlichen Situationen auch ähnlich anwendbar.
• Optimierbarkeit & Effizienz: Die Sprache besteht aus wenigen Operationen, für die es Optimierungsregeln gibt. Jede Operation ist effizient ausführbar mit einer Komplexität von $\le O(n^2)$, wobei $n$ die Anzahl der Tupel ist.
• Sicherheit: Syntaktisch korrekte Anfragen dürfen niemals in eine Endlosschleife geraten oder ein unendliches Ergebnis liefern.
• Eingeschränktheit: Die Anfragesprache ist keine komplette Programmiersprache (folgt aus Sicherheit, Optimierbarkeit und Effizienz).

Systemische Klassifikation der Operatoren

1. Die 5+1 Basisoperatoren (Minimale Relationenalgebra)

Bilden eine minimale, vollständige und unabhängige Basis. Kein Operator kann weggelassen werden, ohne die Vollständigkeit zu verlieren.

• Vereinigung ($\cup$): $R\cup S\triangleq \{t\mid t\in R\vee t\in S\}$. Sammelt Tupel zweier schemaverträglicher Relationen auf. Automatische Duplikatentfernung.
• Differenz ($-$): $R-S\triangleq \{t\mid t\in R\wedge t\notin S\}$. Eliminiert alle Tupel aus $R$, die auch in $S$ vorkommen. Nicht-kommutativ.
• Kartesisches Produkt ($\times$): Kombiniert jedes Tupel aus $R$ mit jedem Tupel aus $S$. Ergebnisschema enthält $n\cdot m$ Tupel und die Summe der Attribute.
• Projektion ($\pi$): Vertikale Reduktion der Tabelle (${\pi }_{A_1,\dots ,A_n}(R)$). Eliminiert Duplikate.
• Selektion ($\sigma$): Horizontale Filterung (${\sigma }_C(R)$) basierend auf einer Bedingung $C$.
• Umbenennung ($\rho$): Reine Operation am Schema (${\rho }_{S(A_1,\dots ,A_n)}(R)$). Verändert keine Tupel, macht Relationen schemaverträglich.

2. Abgeleitete Operatoren (Redundante Komfortfunktionen)

Dienen in der Praxis als nützliche Abkürzungen und lassen sich auf die Basisoperatoren zurückführen.

• Schnittmenge ($\cap$): $R\cap S\triangleq \{t\mid t\in R\wedge t\in S\}$. Rückführung: $R-(R-S)$.
• Theta-Join (${\bowtie }_{\theta }$): Verallgemeinerung des Joins mit freier Verknüpfungsbedingung. Rückführung: ${\sigma }_{\theta }(R\times S)$.
• Natürlicher Join ($\bowtie$): Bildet Paare, die in allen namensgleichen Attributen übereinstimmen und verschmilzt diese.
• Division ($/$): Findet alle $x$-Tupel aus $R$, die in Kombination mit jedem $y$-Tupel aus $S$ in $R$ erscheinen (für komplexe „Alle“-Abfragen).

3. Erweiterte Operatoren (Praxis- & SQL-Erweiterungen)

• Aggregation & Gruppierung ($\gamma$): Partitioniert Relationen in Gruppen mit identischen Werten, um zustandslose Aggregatfunktionen (SUM, AVG, MIN, MAX, COUNT) lokal zu berechnen.
• Sortierung ($\tau$): Sortiert nach einer Attributliste. WICHTIGER OBSIDIAN-MERKSATZ: Das Ergebnis ist eine Liste, keine Menge. Muss zwingend der letzte Operator eines relationalen Ausdrucks sein!
• Duplikateliminierung ($\delta$): Wandelt eine Multimenge explizit in eine reine Menge um (wichtig für den Übergang von SQL-Bags zu RA-Mengen).
• Semi-Join ($⋉$): Join, bei dem im Endeffekt nur die Attribute der linken Relation erhalten bleiben.
• Outer Joins ($⋊,⋉,\bowtie$): Übernahme von Datensätzen, die keinen Verknüpfungspartner finden, aufgefüllt mit Nullwerten (NULL-Padding).
• Outer Union ($\uplus$): Vereinigung von nicht schemaverträglichen Relationen. Das Ergebnisschema ist die mathematische Vereinigung aller Attribute (fehlende Werte werden mit NULL aufgefüllt).

Algebraische Optimierung (Transformationsregeln)

Ausdrücke werden als Baum dargestellt und vom Query Optimizer vor der Ausführung mathematisch umgeschrieben:

• Kommutativität & Assoziativität des Joins erlauben das freie Umstellen von Tabellenketten.
• Idempotenz der Projektion: ${\pi }_Y({\pi }_{X,Y}(R))={\pi }_Y(R)$
• Selektions-Pushing: ${\pi }_X({\sigma }_{A=a}(R))={\sigma }_{A=a}({\pi }_X(R))$ (Verschieben von Selektionen vor Projektionen zur Reduktion der Datenmenge).
• Distribution: ${\sigma }_{A=a}(R\cup S)={\sigma }_{A=a}(R)\cup {\sigma }_{A=a}(S)$

Links

• ISDA 06 Relationale Algebra.pdf
• ISDA 07 SQL.pdf