Kalkül (Datenbank)

Für die theoretische Betrachtung und die semantisch genaue Definition von Anfragesprachen für Datenbanken werden Kalkülausdrücke genutzt, speziell der Tupelkalkül (englisch tuple calculus) und der Bereichskalkül (auch Domänen-Kalkül, englisch domain calculus). Aufgrund ihrer Ähnlichkeit werden sie hier zusammen betrachtet. Es existieren aber noch weitere kalkülartige Anfragesprachen.

Details

Ausgegangen wird davon, dass Daten in einer Datenbank in einer Anzahl von Tupel (Relationen) gleichen Typs gespeichert sind, d. h. die Komponenten der Tupel in einer Tupelmenge haben alle den gleichen Datentyp, und somit die gleichen Operationen, die auf sie anwendbar sind. Da die Kalküle „nur“ eine theoretische Fundierung darstellen, werden Datentypen hier aber nicht weiter betrachtet, sondern davon ausgegangen, dass die üblichen Operationen gelten.

Die Anfragen, die mit den Kalkülen spezifiziert werden, werden dann als Mengen konstruiert. Diese Konstruktion folgt einer bestimmten Form: Beim Tupelkalkül werden Mengen aus Tupeln konstruiert, beim Bereichskalkül Mengen aus den sog. „Bereichen“, die im Wesentlichen freie Variablen sind, die Werte aus dem Wertebereich der Tupelkomponenten annehmen können. Generell kann aber definiert werden, woher die Daten kommen, wie sie zu verknüpfen sind und welche zusätzlichen Bedingungen gelten sollen.

Kalküle liefern eine sehr mächtige Anfragesprache, was im Bereich der Datenbanken aber nicht erwünscht ist. Es ist z. B. kein Problem, mittels Kalkülausdrücken eine unendliche Ergebnismenge zu spezifizieren, was ein Designprinzip von Anfragesprachen verletzt. Für die allgemeine Datenbanktheorie interessant ist daher die Abgrenzung von sicheren Kalkülausdrücken, die in der Mächtigkeit der relationalen Algebra entsprechen. Kalkülausdrücke sind weiterhin streng relational vollständig.

Für SQL gibt es eine formale Definition mittels des Tupelkalküls. QBE basiert auf dem Bereichskalkül, QUEL ist eine relativ direkte Umsetzung von Teilen des Tupelkalküls.

Allgemeine Form

In der Mathematik kann man eine Menge konstruieren, indem man angibt, was für die einzelnen Elemente gelten soll. Die einfache Form dafür ist {x | Formel}, d. h. ich wähle alle x, für die die Formel gilt, z. B. $\{x\mid x\in \mathbb {N} \ \land \ {2<x<8\}}$ , um die natürlichen Zahlen zwischen 2 und 8 zu erhalten. Angegeben wurde hier, erstens woher die Daten kommen (natürliche Zahlen) und zweitens, was für sie gelten soll (die Formel). x ist eine freie Variable, deren Wertebereich durch die Formel festgelegt wurde. Statt einer einfachen freien Variablen kann auch eine Formel als Ergebnis angegeben werden, z. B. x², um die Quadratzahlen der Zahlen zwischen 2 und 8 zu erhalten. Die allgemeine Form dieser Mengenkonstruktion ist {f(X) | g(Y)}, worin f und g die jeweiligen Formeln und X und Y Mengen von freien Variablen sind.

Für den Datenbankbereich sind die Wertebereiche nun nicht willkürlich festgelegt, sondern sie entstammen den erwähnten Tupelmengen (üblicherweise Relationen, durchaus aber auch Entitäten oder Objektmengen). Die Ergebnisse können entweder als Variablenmengen oder als Tupel angegeben werden, d. h. man konstruiert die Menge als „alle freien Variablen, für die gilt …“ oder als „alle Tupel, für die gilt …“. Ersteres führt zum Bereichskalkül; zweiteres zum Tupelkalkül.

Kalkülformeln

Die Menge der möglichen Formeln ist ebenfalls auf eine bestimmte Form eingegrenzt, die für die beiden Kalküle sehr ähnlich ist. Dabei werden Terme zu atomaren Formeln, und diese wiederum zu Formeln zusammengesetzt. Wertebereiche freier Variablen werden durch Datenbankprädikate angegeben, wodurch festgelegt wird, woher die Daten kommen (Bereichskalkül: KUNDE(x,y,z), Tupelkalkül: KUNDE(k)).

Terme: Variablen, Konstanten, Funktionsanwendungen
atomare Formeln: Anwendung von Operationen der Datentypen, z. B. <, > auf den Wertebereich der natürlichen Zahlen und Datenbankprädikate
Formeln: Verknüpfung atomarer Formeln mittels Operatoren der booleschen Logik, ∧, ∨, ¬, ∀, ∃

Die Kalküle können so erweitert werden, dass es mit ihnen vergleichsweise einfach möglich ist, Datenbanksprachen wie SQL zu formalisieren. Dazu führt man statt einer Mengensemantik eine Multimengensemantik ein und zusätzlich die Möglichkeit, Formeln – insbesondere die Aggregatfunktionen – im Ergebnisbereich zu verwenden. Weiterhin ist es denkbar, für Datenbankprädikate wiederum Anfragen zu erlauben, so dass die Kalküle abgeschlossen werden.

Bereichskalkül

Die Form ist {x₁, …, x_n | φ(x₁, …, x_n)}, wobei die x_i das Ergebnis als Tupelmengen sind und φ eine Formel ist. Diese Formeln sind wie oben angegeben aufgebaut. In Datenbankprädikaten müssen nicht alle Variablen belegt werden, stattdessen kann auch '_' geschrieben werden, wofür gilt, dass sie jeweils unterschiedliche, unbenannte freie Variablen sind.

Beispiele

Gegeben seien Relationen mit den Relationenschemata KUNDE(kdnr, kname, adresse, ort), AUFTRAG(auftragsnr, kdnr, warennr, menge), WARE(warennr, wname, wpreis).

Orte, in denen es Kunden gibt: {x | KUNDE(_,_,_,x)}

Alle Kunden aus Bremen: {x, y, z | KUNDE(x,y,z,w) ∧ w='Bremen'} oder kurz {x, y, z | KUNDE(x,y,z,'Bremen')}

Kunden, die etwas bestellt haben: {x, y, z | KUNDE(x,y,z,_) ∧ AUFTRAG(_,x,_,_)}

Waren, die nicht bestellt wurden: {x, y | WARE(x,y,_) ∧ ¬AUFTRAG(_,_,x,_)}

Tupelkalkül

Die Form ist {t | φ(t)}. t ist dabei eine Tupelvariable, φ eine Formel wie oben angegeben. Datenbankprädikate werden als R(t) oder t∈R geschrieben, auf einzelne Elemente des Tupels (Attribute) greift man durch eine Punktnotation mit Angabe des Namens aus dem Schema zu, also t.A, oder durch einen Zugriff über den Index t[i].

Beispiele

Mit dem o.a. Schema,

Orte, in denen es Kunden gibt: {t.ort | KUNDE(t)}

Alle Kunden aus Bremen: {t | KUNDE(t) ∧ t.ort='Bremen'}

Kunden mit Bestellung: {t | KUNDE(t) ∧ ∃s(AUFTRAG(s) ∧ s.kdnr=t.kdnr)}

Waren ohne Bestellung: {t | WARE(t) ∧ ¬∃s(AUFTRAG(s) ∧ s.warennr=t.warennr)}

Wie man sieht, werden im Tupelkalkül die Verbundbedingungen explizit angegeben, wogegen ein Verbund im Bereichskalkül durch gleichbenannte Variablen gebildet wird.

Siehe auch

Anwendung der Prädikatenlogik

Literatur

Andreas Heuer, Gunter Saake: Datenbanken: Konzepte und Sprachen, MITP Verlag, ISBN 3-8266-0619-1, S. 297 ff.