Back To Top

Relationale Algebra, Relationenkalkül


SQL: Mengenkonzepte von SQL bzw. relationale Sprachen

Comelio-Blog SQL Relationale AlgebraFür die Verarbeitung von Daten und die Bestimmung, welche Daten mit welchen Methoden zu bearbeiten sind, benötigt man eine strukturierte Art der Mengendefinition, um Datenmengen zu definieren. Diese Definitionssystematik stellt eine der Sprachen dar, mit denen relationale Datenbanksysteme gesteuert werden können. SQL ist in diesem Sinne nur eine Möglichkeit unter vielen anderen, die vorgeschlagen worden sind, hat sich allerdings als Standard weltweit durchsetzen können. SQL selbst basiert auf zwei Konzepten, die wir in diesem Abschnitt vorstellen. Im direkten Vergleich mit SQL sieht man unmittelbar, welche Teile dieser Konzepte Eingang in SQL gefunden haben.

Grob kann man bei den möglichen Sprachen und Konzepten, mit denen Datenmengen definiert werden können, prozedurale und nicht-prozedurale Ansätze unterscheiden. Bei einem prozeduralen Konzept legt der Benutzer genau fest, wie das System die Daten zu beschaffen und zu verarbeiten hat. Bei einem nicht-prozeduralen Konzept hingegen beschränkt sich der Benutzer auf die Angabe, welche Datenmengen benötigt werden und wie sie zu bearbeiten sind. Er verzichtet also auf die Angabe, wie er diese Daten erhalten will. In den folgenden beiden Abschnitten finden Sie Informationen zu den originären Grundkonzepten für die Entwicklung von SQL bzw. über „Informationen“ die Ursprünge von relationalen Sprachen. Dabei ist die relationale Algebra eine prozedurale Sprache, weil hier die Datenmengen beschrieben werden, während das Relationenkalkül (oder auch relationale Kalkül) eher eine nicht-prozedurale Sprache darstellt.

Relationale Algebra

Comelio-Blog SQL Relationale AlgebraDie relationale Algebra stellt eine theoretische Sprache dar, mit der keine Änderungen an Daten durchgeführt werden können, sondern die nur Möglichkeiten bereitstellt, Datenmengen auszuwählen. Sie lässt also die Definition neuer Relationen auf Basis anderer Relationen zu. Wir verwenden für ihre knappe Darstellung eine geometrische Veranschaulichung. Dazu gibt es in der Literatur unterschiedliche Varianten. Wir haben uns hier bei den einfachen Mengenkonstrukten für die Ihnen aus der Mengenlehre bekannten Strukturen entschieden, während bei den komplexen Operationen eher der tabellenbasierte Ansatz gewählt wird. Für die tatsächliche Verwendung als Sprache existieren verschiedene griechische Symbole, mit denen die Operationen auf Spaltenangaben angewendet werden können. Mit ihnen lässt sich daher durchaus auch eine einfache Arbeit an einem Datenbanksystem durchführen, obwohl SQL natürlich wesentlich mehr Möglichkeiten bereithält.

Operationen I

Selektion
Die Selektion stellt eine der beiden Grundformen für die häufigste Abfrage bereit, nämlich die horizontale Auswahl von Zeilen einer Tabelle. Wichtig ist hierbei, dass die Anzahl der Spalten des eingehenden Schemas und des ausgehenden Schemas (also der Tabellen) gleich bleibt. Die Auswahl erfolgt dabei über eine Bedingung, wie Sie sie bereits im letzten Kapitel in einer WHERE–Klausel vorgegeben haben. Damit stellt also die Selektion eine Untermenge gleichen Grades (gleicher Spaltenanzahl) der Obermenge dar.
Sel K_Dauer = 2(Kurs) wählt die Datensätze aus der Tabelle KURS aus, die eine Kursdauer von zwei Tagen aufweisen. Für die Kombination von Bedingungen zu komplexen Prädikaten kann man die logischen Operatoren Λ (UND), Ù (ODER) und ~ (NICHT) verwenden.
Projektion
Eine Projektion stellt ebenfalls eine Auswahl aus einer Tabelle dar. Dabei liegt die Betrachtung jedoch nicht primär auf den einzelnen Zielen, sondern vielmehr auf den Spalten. Die Kardinalität des Schemas bleibt also nicht erhalten. Die Ergebnis- oder die Abfragetabelle wird mindestens eine Spalte weniger als die Original- oder Ursprungstabelle enthalten. Dabei dient als Auswahlkriterium wie immer mindestens eine Bedingung, die in einer Spalte abgefragt wird und auf die ausgewählten Datensätze zutrifft.
Proj K_Titel, K_Untertitel, K_Themen (Kurs) wählt die Spalten K_Titel, K_Untertitel und K_Themen aus der Tabelle KURS aus.
Union (Vereinigung)
Die Operation Union stellt eine Vereinigungsmenge aus zwei Relationen bzw. Tabellen her. Dabei gilt, dass die beiden eingehenden Tabellen das gleiche Schema, also die gleiche Spaltenstruktur haben müssen. Ist diese Bedingung erfüllt, werden die Datensätze der einen Tabelle einfach an die Datensätze der anderen Tabelle angehängt. Es entsteht also eine Tabelle mit den Datensätzen der beiden eingehenden Tabellen ohne eventuelle Duplikate.
Sel TN_Stadt(Teilnehmer) Un Sel U_Stadt(Unternehmen) erzeugt eine Liste aller Städte, in denen entweder Teilnehmer wohnen oder Unternehmen ihren Sitz haben.
Differenz (Differenzmenge)
Die Differenz stellt das logische Gegenstück zur Vereinigung dar. Wiederum müssen die eingehenden Tabellen die Bedingung erfüllen, dass sie das gleiche Schema besitzen. Die Operation T1 – T2 der Differenzbildung verläuft dann so, dass nur die Datensätze in der Ergebnistabelle übrig bleiben, die zur Tabelle T1, aber nicht zur Tabelle T2 gehören. Pro Datensatz wird also ein Vergleich durchgeführt, wobei die Datensätze in T1 entfallen, die in T2 enthalten sind. Sie werden also abgezogen. Wie bei einer Differenzbildung mit Zahlen ist hier ebenfalls zu beachten, dass im Gegensatz zur Vereinigung die Operation nicht symmetrisch ist. Es ist also ein Unterschied, ob T1 von T2 oder T2 von T1 subtrahiert wird.
Sel TN_Stadt(Teilnehmer) - Sel U_Stadt(Unternehmen) erzeugt eine Liste aller Städte, in denen nur Teilnehmer wohnen, aber Unternehmen keinen Sitz haben.
Schnittmenge
Die Schnittmenge ist insoweit mit der Differenzmenge verwandt, als dass ebenfalls zwei Tabellen mit gleichem Schema aufgrund ihrer Datensätze miteinander verglichen werden. Dabei bleiben in der Ergebnistabelle die Datensätze übrig, die in beiden Tabellen vorhanden sind. Die Schnittmenge ist nicht wirklich eine Basisoperation, sondern setzt sich aus zwei Differenzen zusammen: T1 Schn T2 = T1 – (T1 – T2) = T2 – (T2 – T1).
Join (Verbund)
Der Join stellt das Hilfsmittel dar, das zum Einsatz kommt, wenn Beziehungen zwischen den Tabellen über Fremdschlüssel bei einer Abfrage genutzt werden. Die Ergebnistabelle ergibt sich aus den beiden eingehenden Tabellen, indem ein Produkt der Felder gebildet wird, die die Join-Bedingung erfüllen. Folgende Unterarten sind zu berücksichtigen:
  • Theta-Verknüpfung:
    Die Verknüpfungsbedingung wird über einen beliebigen Vergleichsoperator (größer, kleiner, größer/kleiner gleich, gleich, ungleich) eingerichtet.
  • Gleichheitsverknüpfung:
    Dies ist ein Spezialfall der Theta-Verknüpfung, bei der nur über den Gleichheitsoperator eine Verknüpfung eingerichtet wird. (Sel TN_Vorname, TN_Nachname (Teilnehmer)) == Teilnehmer.U_Nr = Unternehmen.U_Nr (Sel U_Name (Unternehmen)) verknüpft die beiden Tabellen TEILNEHMER und UNTERNEHMEN anhand der Unternehmensnummer.
  • Natürliche Verknüpfung:
    Dies ist ein Spezialfall der Gleichheitsverknüpfung, bei der alle Attribute mit gleichem Namen in den eingehenden Relationen verknüpft werden. Diese sollten auch eine übereinstimmende Datenstruktur besitzen, um sinnvolle Verknüpfungen zu ermöglichen. (Sel K_Titel, K_Untertitel, K_Themen (Kurs)) =n= (Sel P_TN1, P_TN2 (Preis)) verknüpft die beiden Tabellen PREIS und KURS über die gemeinsame Spalte P_Nr.
  • (Linke/rechte) Äußere Verknüpfung:
    Einer der beiden Relationen (der linken oder der rechten) wird eine Wertedominanz zugewiesen, sodass auch diejenigen Datensätze in der Ergebnisrelation erscheinen, die über die angegebene Verknüpfungsbedingung eigentlich nicht berücksichtigt werden würden. Die fehlenden Daten werden durch NULL-Werte aufgefüllt. Sel K_Nr (Kurs) =ä= Themenverteilung liefert alle Kursnummern mit Informationen aus der Tabelle THEMENVERTEILUNG und fügt die Nummern der Kurse an, zu denen es keinen Dozenten gibt.
Im Beispiel aus der Abbildung gelangt man zur Ergebnistabelle, indem die Zuordnungen verglichen werden. Da in T1 zum Feld a1 das Feld b1 gehört, gelangt in der Ergebnistabelle aus T2 das Feld c1 in die erste Reihe, da in T2 das Feld b1 (das ja auch in T1 vorhanden ist) zu c1 gehört. Gleich verhält es sich mit der zweiten und dritten Zeile, da hier wiederum eine Verbindung über b1 und über b2 besteht. Die vierte Zeile von T1 dagegen findet keine Entsprechung in T2, da b4 nur in T1 auftritt. Daher wird es nicht Teil der Ergebnistabelle. In dieser Konstruktion würde ein so genannter innerer Verbund verwendet werden.
Division
Die Division stellt eine Operation dar, die auf zwei eingehende Tabellen angewandt werden kann, die die zum Teil die gleichen Daten haben. Dabei wird eine Ergebnistabelle erzeugt, die Werte von T1 enthält, die nicht zu T2 gehören, aber als zugehörige Werte die von T1 enthalten.
In der Abbildung gelangt man zur Ergebnistabelle, indem man in einem Datenvergleich feststellt, dass lediglich a und c von T1 gleichzeitig als zugeordnete Werte x und y aus T2 enthalten. Sie bleiben also übrig. Wie die Differenzmenge ist auch die Divisionsoperation nicht symmetrisch. Das Ergebnis wird sich also ggf. ändern, sobald die beiden Tabellen (Dividend und Divisor) vertauscht werden.
(Kartesisches) Produkt
Ein Produkt aus zwei eingehenden Tabellen stellt die Tabelle dar, die eine Verknüpfung beider Wertemengen enthält, sodass sämtliche Kombinationsmöglichkeiten entstehen. Damit ist das kartesische Produkt eine Unterart des Verbunds, da hier ebenfalls zwei Tabellen miteinander verknüpft werden. In unserem Beispiel gelangt man also zur Ergebnistabelle, indem jeder Wert der Tabelle T1 (a, b, c) mit jedem Wert der Tabelle T2 (x, y) als Paar verknüpft wird. Da die Reihenfolge der Spalten im relationalen Datenmodell unerheblich ist, ergeben sich also 3 * 2 = 6 Kombinationsmöglichkeiten. Damit ist das kartesische Produkt eine Unterart des Verbunds, da hier ebenfalls zwei Tabellen miteinander verknüpft werden.

Operationen II

Relationenkalkül

Comelio-Blog SQL Relationale AlgebraWährend bei der Formulierung eines Ausdrucks in der relationalen Algebra auch die Reihenfolge und die Art und Weise der Datenbeschaffung festgelegt wird, entfällt das Wie bei der Verwendung des Relationenkalküls. Man konzentriert sich ausdrücklich auf die Beschreibung der Datenmenge im Hinblick auf das Was, also im Hinblick darauf, welche Daten abzurufen sind. Die Sprachsyntax oder die mathematische Logik beruht auf einem Bereich der symbolischen Logik, die Prädikatenkalkül genannt wird.

Ein Prädikat repräsentiert dabei eine Funktion, die einen Wahrheitswert liefert, in dem Argumente mit anderen Ausdrücken verarbeitet werden. Dieser zurückgelieferte Ausdruck wird auch als Aussage bezeichnet. Er weist entweder den Wert TRUE oder FALSE auf. Enthält ein Prädikat eine Variable wie „x ist ein Kurs, der zwei Tage dauert“, so wird die Aussage für einige Datensätze den Ausdruck WAHR zurückliefern, während dies für andere Datensätze nicht der Fall ist. In einer mathematisch verständlichen Variante erhält man die Formulierung {x | P(x)}, die die Menge aller x beschreibt, für die P von x wahr ist. Diese Mengendefinitionen können dann sowohl mit den üblichen logischen Operatoren kombiniert wie auch durch Eigenschaftsbeschreibungen für P(x) ersetzt werden.

Im Zusammenhang mit Datenbanken taucht dieses Prädikatenkalkül in zwei Varianten auf:

  • Tupel-Kalkül:
    Für die Definition von wahren Prädikaten bzw. das Auffinden von Datensätzen, die das Prädikat zu einer wahren Aussage machen, verwendet man Tupelvariablen. Dies sind Variablen, deren Wertebereich mit dem (Werte-)Bereich in einer Relation übereinstimmt und daher ein Prädikat zu einer wahren Aussage macht. In der Formulierung RANGE OF K IS Kurs wird der Bereich KURS für die Variable K definiert. In einer als Formel bezeichneten Formulierung der Form {K | K.K_Dauer = 2 } findet man alle Datensätze mit einer Kursdauer von zwei Tagen.
  • Wertebereichskalkül:
    Für die Verwendung des Wertebereichskalküls setzt man Variablen ein, deren Werte aus Wertebereichen und nicht aus Tupeln der Relationen bestehen.