next up previous contents
Next: Normalformen Up: Einführung Previous: Stücklisten

Relationen und Relationenalgebra

Die Implementierung einer Stücklistenverwaltung erfolgt am besten mit einer Datenbank unter Beachtung existierender Datenbank-Standards. Ein weit verbreiteter Standard sind relationale Datenbanken. Für ein gutes Verständis relationaler Datenbanken ist allerdings auch ein Verständnis des zu Grunde liegenden Datenmodells -- der Relationen -- notwendig. Das Relationenmodell geht auf Codd zurück und wurde in [Codd70] zum ersten Mal vorgestelltgif.

Im relationalen Datenmodell hat man Domänen als benannte Mengen von atomaren (= skalaren, elementaren, nicht strukturierten) Werten. Domänen entsprechen also im wesentlichen den Datentypen höherer Programmiersprachen mit impliziter Festlegung der auf diesen Datentypen erlaubten Operationen. Eine Relation ist eine Untermenge des kartesischen Produkts von einer oder mehreren Domänen. Die einzelnen Elemente einer Relation werden Tupel genannt, die selbst wieder aus Attributen bestehen. Relationen haben folgende Eigenschaften:

Wegen der Definition einer Relation als Menge muß jedes Tupel dieser Menge eindeutig identifizierbar sein. Man kann deswegen einen Schlüsselkandidaten wie folgt definieren: Sei R eine Relation mit den Attributen . Die Menge , , heißt Schlüsselkandidat von R genau dann, wenn unabhängig vom Zeitpunkt (also für die gesamte Lebensdauer der Relation) gilt:

  1. Eindeutigkeit: Zu keinem Zeitpunkt gibt es zwei Tupel mit demselben Wert für K (das heißt mit demselben Wert für , demselben Wert für ... und demselben Wert für ).
  2. Minimalität: Keines der Attribute kann weggelassen werden, ohne die Eindeutigkeit von K zu verlieren.
Man kann für jede Relation R einen (beliebigen) Schlüsselkandidaten als Primärschlüssel (primary key) festlegen. Die übrigen Schlüsselkandidaten heißen Alternativschlüssel (alternate keys).

Ein Fremdschlüssel ist eine (möglicherweise nur einelementige) Menge von Attributen einer Relation R, die in einer anderen Relation als Primärschlüssel auftritt. R und sind nicht notwendigerweise voneinander verschieden.

Primärschlüssel kann man im Relationenmodell als symbolische Tupeladressen auffassen. Entsprechend ist ein Fremdschlüssel ein symbolischer Zeiger auf ein bestimmtes Tupel einer Relation.

Im Relationenmodell können Beziehungen zwischen Relationen nur durch Fremdschlüssel dargestellt werden. Mit den folgenden Beziehungen zwischen Relationen kann man Bedingungen für die Integrität der Datenbank aufstellen:

Entitätsintegrität (entity integrity): Für jede definierte Relation muß ein Primärschlüssel festgelegt sein. Kein Attribut, das zum Primärschlüssel einer Relation gehört, darf Nullwerte annehmen. Dabei versteht man unter einem Nullwert eine spezielle Markierung für unbekannte Werte. Diese Markierung darf nicht zum Wertevorrat der entsprechenden Domäne gehören.

Referentielle Integrität (referential integrity): Sei eine Relation, die mit einem Fremdschlüssel F auf eine Relation mit Primärschlüssel P zeigt. Für jeden in auftretenden Wert von F (= symbolischer Zeiger) muß dann gelten:

  1. Er enthält entweder in keiner seiner Komponenten einen Nullwert (vollständig definiert) oder alle seine Komponenten sind mit Nullwerten markiert (vollständig annulliert).
  2. Wenn er vollständig definiert ist, muß in ein Tupel existieren, das diesen Wert als P-Wert aufweist (keine dangling pointers).

In der Relationenalgebra sind die folgenden fünf Grundoperationen [Ull88] definiert:

  1. Vereinigung. Die Vereinigung von zwei Relationen R und S (die Relationen müssen natürlich denselben Aufbau, d.h. gleiche Attributmengen, haben), geschrieben als , ist die Menge der Tupel, die in R oder in S oder in beiden Relationen enthalten sind.
  2. Differenz. Die Differenz von zwei Relationen R und S (die Relationen müssen natürlich kompatibel sein), geschrieben als R - S, ist die Menge der Tupel von R, die nicht auch in S enthalten sind.
  3. Kartesisches Produkt. Seien R und S Relationen mit und Attributen. Dann ist , das kartesische Produkt der Relationen R und S, die Menge aller möglichen ()-Tupel, wobei die ersten Attribute von einem Tupel der Relation R stammen und die letzten Attribute von einem Tupel der Relation S.
  4. Projektion. Die Projektion extrahiert bestimmte Attribute aus einer Relation und bildet somit eine vertikale Teilrelation. Sei R eine Relation mit k Attributen, dann ist mit paarweise unterschiedlichen (j im Bereich 1 bis m) die Projektion der Relation R auf die Komponenten , das heißt die Menge der m-Tupel , sodaß es ein k-Tupel in der Relation R gibt, für das für und gilt.
  5. Selektion. Die Selektion extrahiert aus einer Relation bestimmte Tupel und bildet somit eine horizontale Teilrelation. Die Selektion ist die Menge der Tupel der Relation R, die die Bedingung F erfüllen.




next up previous contents
Next: Normalformen Up: Einführung Previous: Stücklisten



Christoph Steindl
Thu Jul 24 14:37:19 MET DST 1997