Relationale Algebra

Grundidee und Bedeutung

Die relationale Algebra ist eine Menge von Operationen zur Verarbeitung von Relationen, also tabellenartig dargestellten Daten. Mit ihr lassen sich Relationen filtern, verknüpfen, zusammenfassen und anderweitig verändern, um Datenbankanfragen auszudrücken. Das Ergebnis jeder Operation ist wieder eine Relation. Diese Eigenschaft heißt Abgeschlossenheit und ermöglicht es, mehrere Operationen zu komplexen Abfragen zusammenzusetzen.

Anfragen werden heute meist in deklarativen Sprachen wie SQL, XQuery, SPARQL oder Datalog formuliert. Ein Datenbanksystem übersetzt sie intern in einen Operatorbaum aus Operationen der relationalen Algebra und zusätzlichen Datenbankoperationen. Der Anfrageoptimierer formt diesen Baum mithilfe relationaler Gesetze um, damit die Anfrage möglichst effizient ausgeführt werden kann. Als direkte Sprache für Endbenutzer ist die relationale Algebra daher kaum noch bedeutsam, als theoretische Grundlage und internes Modell leistungsfähiger Datenbanksysteme jedoch zentral.

Erste Ideen veröffentlichte Alfred Tarski 1941 in „On the calculus of relations“, wobei er Vereinigung, Durchschnitt und Join für zweistellige Relationen behandelte. Ende der 1960er Jahre entwickelte Edgar F. Codd am IBM Research Laboratory in San Jose die Grundlagen der heutigen relationalen Algebra und des relationalen Datenmodells. Daten sollten in Relationen gespeichert und abhängig von der jeweiligen Anfrage unterschiedlich verknüpft werden können, ohne dass Benutzer die interne Speicherung kennen müssen. 1970 stellten Rudolf Bayer und Ed McCreight den B-Baum als effizienten Datenbankindex vor. In den 1970er Jahren entstanden bei IBM SEQUEL, später SQL genannt, und das experimentelle System R; Anfang der 1980er Jahre folgten die kommerziellen Systeme Db2 und Oracle.

Eigenschaften und Grundoperationen

Die relationale Algebra ist prozedural: Ein Ausdruck beschreibt, durch welche Folge von Operationen das Ergebnis entsteht. Im Unterschied zu Kalkülen ist sie sicher, liefert also bei endlichen Eingaben in endlicher Zeit ein endliches Ergebnis.

Eine Abfragesprache heißt relational vollständig, wenn jede Operation der relationalen Algebra durch mindestens einen Ausdruck der Sprache umgesetzt werden kann. Streng relational vollständig ist sie, wenn dafür jeweils genau ein Datenbankoperator genügt. Gilt zusätzlich umgekehrt, dass zu jedem Datenbankoperator eine entsprechende Operation der relationalen Algebra existiert, heißt die Sprache relational äquivalent. Diese Begriffe beschreiben nicht einfach die gesamte Mächtigkeit einer Sprache: Relational vollständige Sprachen können zusätzliche Funktionen besitzen. Die relationale Algebra selbst kann beispielsweise keine transitive Hülle bilden.

Ein übliches minimales und vollständiges System umfasst sechs Grundoperationen:

• Projektion: Auswahl von Attributen beziehungsweise Spalten.
• Selektion: Auswahl von Tupeln beziehungsweise Zeilen.
• Kartesisches Produkt: Bildung aller Tupelkombinationen zweier Relationen.
• Vereinigung: Zusammenfassung der Tupel zweier Relationen.
• Differenz: Entfernung gemeinsam vorkommender Tupel aus der ersten Relation.
• Umbenennung: Änderung von Attribut- oder Relationsnamen.

Alle weiteren Operationen, darunter Joins und Division, können aus diesen Grundoperationen zusammengesetzt werden.

Mengenoperationen, Projektion und Selektion

Für Vereinigung, Schnittmenge und Differenz müssen zwei Relationen typkompatibel beziehungsweise vereinigungsverträglich sein: Sie müssen den gleichen Grad, also gleich viele Attribute, und identische Wertebereiche der entsprechenden Attribute besitzen.

Die Vereinigung R ∪ S enthält alle Tupel, die in R oder S vorkommen: R ∪ S := {t | t ∈ R ∨ t ∈ S}. Duplikate werden entfernt. Die Schnittmenge R ∩ S enthält genau die Tupel beider Relationen: R ∩ S := {t | t ∈ R ∧ t ∈ S}. Sie lässt sich als R ∩ S = R \ (R \ S) ausdrücken.

Die Differenz R − S beziehungsweise R \ S enthält die Tupel aus R, die nicht in S vorkommen: R − S := {t | t ∈ R ∧ t ∉ S}. Sie ist keine gewöhnliche Subtraktion und keine monotone Operation. Die symmetrische Differenz enthält Tupel, die in genau einer der beiden Relationen liegen: R △ S := (R \ S) ∪ (S \ R) = (R ∪ S) \ (S ∩ R).

Das kartesische Produkt R × S kombiniert jedes Tupel aus R mit jedem Tupel aus S. Bei unterschiedlichen Attributnamen besitzt das Ergebnis zusammen so viele Attribute wie beide Ausgangsrelationen; seine Tupelzahl ist das Produkt ihrer Tupelzahlen. Gleichnamige Attribute werden durch den vorangestellten Relationsnamen unterschieden.

Die Projektion π_β(R), auch Attributbeschränkung, behält nur die Attribute der Projektionsliste β und entfernt doppelte Ergebniszeilen. Beispielsweise liefert π_{Bezeichnung, Preis}(WARE) die Bezeichnungen und Preise aller Waren. Die Selektion σ_Ausdruck(R) behält dagegen nur Tupel, welche die Selektionsbedingung erfüllen: σ_Ausdruck(R) := {t | t ∈ R ∧ t erfüllt Ausdruck}. Bedingungen können Attribute mit Konstanten oder anderen Attributen vergleichen und mit ∧, ∨ und ¬ verknüpft werden. So wählt σ_{Ort='Bremen'}(LIEFERANT) alle Lieferanten aus Bremen aus.

Die Umbenennung ρ_neu←alt ändert Attribut- oder Relationsnamen. Sie ermöglicht unter anderem Mengenoperationen zwischen unterschiedlich benannten Attributen sowie Produkte und Joins bei gleichen Attributnamen.

Verknüpfungen und Division

Ein Join oder Verbund verbindet zwei Relationen. Der allgemeine θ-Join besteht aus einem kartesischen Produkt und einer anschließenden Selektion: R ⋈_Ausdruck S := σ_Ausdruck(R × S). Die Bedingung vergleicht meist zwei Attribute mit einem passenden Operator θ.

Beim Equi-Join ist die Bedingung eine Gleichheit A = B. Der Natural Join führt einen Equi-Join über alle gleichnamigen Attribute durch und blendet anschließend die doppelt vorkommenden Verbundspalten aus. Ohne gemeinsame Attribute entspricht er dem kartesischen Produkt. Er ist kommutativ und assoziativ: R ⋈ S = S ⋈ R und (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T). Dies ist für die Anfrageoptimierung wichtig.

Der Semi Join R ⋉ S gibt nur die Tupel der linken Relation R zurück, die einen passenden Join-Partner in S besitzen. Der Anti Join ist sein Gegenstück und enthält nur Tupel aus R, für die kein Partner in S existiert; in SQL entspricht dies „NOT EXISTS“.

Outer Joins erhalten zusätzlich Tupel ohne Partner. Ein Left Outer Join bewahrt alle Tupel der linken, ein Right Outer Join alle Tupel der rechten Relation. Ein Full Outer Join kombiniert beide Varianten. Fehlende Attribute werden mit Nullwerten aufgefüllt. Outer Joins können mit einer ausdrücklichen Bedingung oder als Natural Outer Join verwendet werden.

Bei einer Joinverfälschung wird eine Relation in Projektionen zerlegt und anschließend über ein gemeinsames Attribut wieder verbunden. Dabei können zusätzliche, ursprünglich nicht vorhandene Tupel entstehen; allgemein gilt R ⊆ Π_L1(R) ⋈_Aj Π_L2(R).

Die Division beantwortet typische „für alle“-Fragen. Sind β und γ die Attributmengen von R und S mit γ ⊊ β und R′ := β \ γ, dann gilt R ÷ S := π_R′(R) − π_R′((π_R′(R) × S) − R). Das Ergebnis enthält die Werte aus R′, die mit jedem Tupel aus S in R auftreten. Im Artikelbeispiel enthält R Eltern, Kinder und deren Alter; S enthält Maria im Alter 4 und Sabine im Alter 2. R ÷ S liefert genau die Ehepaare, die beide angegebenen Kinder haben, nämlich Moritz und Melanie.

Erweiterungen für SQL-nahe Anfragen

Die klassische relationale Algebra reicht nicht aus, um alle Eigenschaften von SQL abzubilden. Insbesondere fehlen Nullwerte, GROUP BY/HAVING, Aggregatfunktionen und die Multimengensemantik.

SQL verwendet NULL für fehlende oder unbekannte Werte und prüft sie mit IS NULL. Eine mögliche Erweiterung arbeitet wie SQL mit dreiwertiger Logik: Neben true und false gibt es NULL. Bei AND gilt unter anderem: false AND NULL = false, true AND NULL = NULL und NULL AND NULL = NULL. Auf Nullwerte angewandte Selektions- oder Joinbedingungen ergeben NULL. Diese Behandlung kann bei Unterabfragen Ergebnisse erzeugen, die nicht der Absicht des Benutzers entsprechen, und ist nicht orthogonal, weil die dreiwertige Logik bei Joins auf eine zweiwertige Entscheidung abgebildet wird. Eine Alternative unterscheidet zwei Nullwertarten mit den Bedeutungen „beliebig“ und „nicht definiert“.

Der Gruppierungsoperator γ teilt Tupel nach gleichen Werten einer Attributliste in Gruppen und wendet Aggregatfunktionen wie count, sum, max oder avg auf jede Gruppe an. Das Ergebnis enthält die Gruppierungsattribute und neue Attribute mit den berechneten Werten. Bei leerer Attributliste wird eine Funktion über die gesamte Relation ausgeführt; eine leere Funktionsliste hat keinen Effekt.

SQL-Ergebnisse sind normalerweise Multimengen, in denen ein Element mehrfach vorkommen darf. Dies spart die zusätzliche Duplikatentfernung. Streng genommen lassen sich deshalb nur SQL-Anfragen mit DISTINCT unmittelbar in die klassische mengenbasierte Algebra übersetzen. Eine erweiterte Algebra kann eine Funktion bag-to-set zur Entfernung von Duplikaten sowie multiset-basierte Grundoperationen verwenden; bei abgeleiteten Operationen ist dabei besondere Vorsicht nötig.

Geschachtelte Datenmodelle und Anwendungsbeispiel

Das NF²-Modell, kurz für Non-first-normal-form beziehungsweise NFNF, hebt die Forderung der 1. Normalform nach atomaren Attributwerten auf. Attribute dürfen Mengen, Mengen von Mengen oder selbst wieder Relationen enthalten. Neben angepassten klassischen Operationen gibt es die Nestung ν und die Entnestung μ. Die Nestung fasst mehrere Attribute unter einem neuen Attributnamen zu einer Unterrelation zusammen; die Entnestung hebt eine solche Schachtelung auf. Damit lassen sich NF²-Relationen in die 1. Normalform und zurück überführen, wobei die Operationen im Allgemeinen nicht bijektiv sind. NF² benötigt keine Fremdschlüssel.

eNF² bedeutet „erweiterte NF²-Relationen“ und verallgemeinert dieses Modell erheblich. Es unterstützt atomare und konstruierte Datentypen wie Tupel, Mengen und Listen auf oberster Ebene sowie als geschachtelte Subtypen. Damit können etwa Messreihen, Polygone und mehrdimensionale Matrizen dargestellt werden, wie sie in Geoinformationssystemen, CAM, CAD und Robotik vorkommen. Die SQL-artige Heidelberg Database Language (HDBL) liefert bei jeder Anfrage wieder ein legales eNF²-Datenobjekt, das gespeichert oder in weiteren geschachtelten Ausdrücken verwendet werden kann.

Ein typisches komplexes Beispiel nutzt die Relationen KUNDE(Kundennr, Name, Wohnort, Kontostand), LIEFERANT(Lieferantennr, Name, Ort, Telefon) und WARE(Warennr, Bezeichnung, Lieferantennr, Preis). Die Telefonnummern aller Lieferanten, die Gemüse in Bremen liefern, erhält man durch π_{Telefon}(σ_{Bezeichnung='Gemüse' ∧ Ort='Bremen' ∧ LIEFERANT.Lieferantennr=WARE.Lieferantennr}(LIEFERANT × WARE)). Dabei erzeugt das Produkt mögliche Kombinationen, die Selektion wählt passende Ware-Lieferant-Paare und die Projektion behält nur die Telefonnummer. Alle Orte mit mindestens einem Lieferanten und mindestens einem Kunden liefert π_{Ort}(ρ_{Ort←Wohnort}(KUNDE)) ∩ π_{Ort}(LIEFERANT).