Kalkül (Datenbank)

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 (engl. tuple calculus) und der Bereichskalkül (auch Domänen-Kalkül, engl. domain calculus). Aufgrund ihrer Ähnlichkeit werden sie hier zusammen betrachtet. Es existieren aber noch weitere kalkülartige Anfragesprachen.

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.

Inhaltsverzeichnis

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 \vert x \in \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. , 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 {x1, …, xn | φ(x1, …, xn)}, wobei die xi 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 mit Bestellung: {x, y, z | KUNDE(x,y,z,_) ∧ AUFTRAG(_,x,_,_)}

Waren ohne Bestellung: {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

Literatur

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

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mengenoperationen — In der Theorie der Datenbanken versteht man unter einer Relationenalgebra oder einer Relationalen Algebra eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu… …   Deutsch Wikipedia

  • Projektion (Informatik) — In der Theorie der Datenbanken versteht man unter einer Relationenalgebra oder einer Relationalen Algebra eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu… …   Deutsch Wikipedia

  • Relationenalgebra — In der Theorie der Datenbanken versteht man unter einer Relationenalgebra oder einer Relationalen Algebra eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu… …   Deutsch Wikipedia

  • Relationsalgebra — In der Theorie der Datenbanken versteht man unter einer Relationenalgebra oder einer Relationalen Algebra eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu… …   Deutsch Wikipedia

  • Theta join — In der Theorie der Datenbanken versteht man unter einer Relationenalgebra oder einer Relationalen Algebra eine formale Sprache, mit der sich Anfragen über einem relationalen Schema formulieren lassen. Sie erlaubt es, Relationen miteinander zu… …   Deutsch Wikipedia

  • Continuous Query Language — Die Continuous Query Language (CQL) ist eine deklarative Anfragesprache für Datenströme in Data Stream Management Systemen. Sie stellt eine Erweiterung der SQL dar. Die CQL wurde bis Januar 2006 im Rahmen des STREAM Projekts an der Stanford… …   Deutsch Wikipedia

  • QBE — Query by Example (Suche anhand von Beispielen) bezeichnet ursprünglich eine relationale Datenbankabfragesprache, die von Moshé M. Zloof bei IBM parallel zu System R entwickelt wurde. Sie beruht im wesentlichen auf dem Bereichskalkül. Dabei wird… …   Deutsch Wikipedia

  • Computer Science — Informatik ist die Wissenschaft von der systematischen Verarbeitung von Informationen, insbesondere der automatischen Verarbeitung mit Hilfe von Rechenanlagen. Historisch hat sich die Informatik als Wissenschaft aus der Mathematik entwickelt,… …   Deutsch Wikipedia

  • Computerwissenschaft — Informatik ist die Wissenschaft von der systematischen Verarbeitung von Informationen, insbesondere der automatischen Verarbeitung mit Hilfe von Rechenanlagen. Historisch hat sich die Informatik als Wissenschaft aus der Mathematik entwickelt,… …   Deutsch Wikipedia

  • Otto von Bismarck — Otto von Bismarck, 1890 Otto Eduard Leopold von Bismarck Schönhausen (seit 1865 Graf, seit 1871 Fürst von Bismarck, seit 1890 Herzog zu Lauenburg[1]; * 1. April 1815 in Schönhausen; † 30. Juli …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”