Division

Division
Division


Die Division ist die Umsetzung des "Für-Alle-Quantors" in der relationalen Algebra. Sie beschreibt alle Tupel aus einer Relation, die mit allen anderen Tupeln einer anderen Relation verknüpft sind. Die Division ist eine (ableitbare) Operation der relationalen Algebra. Die Formel zur Ableitung der Division aus Projektion, Differenz und Natural Join findet man weiter unten in diesem Artikel.

Definition:

Wir betrachten zwei Relationen R und S. Die Attribute von S sollen in den Attributen von R enthalten sein, d.h. für alle Attributnamen von S gibt es namensgleiche Attribute in R. Die Attribute der Ergebnismenge der Division entsprechen der Differenzmenge X der Attribute von R und S und erfüllen zusätzlich folgende Bedingung

Die Division R ÷ S besteht aus allen Tupeln x aus X, so dass die folgenden beiden Bedingungen für jedes x aus X gelten:

 Zu jedem s aus S gibt es eine Fortsetzung r aus R, so dass die Projektion von r auf S gleich s ist.
 Die Projektion  von r auf X stimmt mit x überein.

Anschaulich bedeutet die Division, dass die Tupel von R projiziert auf die Differenzmenge X in der Division übrig bleiben, die mit allen Tupeln von S verknüpft sind. Die Division ist nicht kommutativ, d.h. R ÷ S ist ungleich S ÷ R.

Die Division gehört nicht zu den Grundoperatoren der relationalen Algebra, da sie sich durch eine Formel aus Projektion, Differenz und Natural Join ableiten lässt:

 R ÷ S = ∏X(R) - ∏X((∏X(R)*S)-R)(siehe Kemper/Eickler, Seite 92)

Damit die für die Ausführung der Division notwendigen Eigenschaften für die beiden Relationen R und S gegeben sind, müssen gegebenenfalls Projektionen und/oder Umbenennungen als vorbereitende Aktionen durchgeführt werden. Falls bei der Ausführung Tupel mehrfach auftreten, werden diese automatisch eliminiert.

Die Division ist in SQL nicht direkt enthalten, sondern muss durch einen Umweg über ein doppeltes NOT EXISTS oder durch Zählen (siehe: HAVING-Klausel) von Tupeln ausgedrückt werden.

1.Beispiel:

Eine Relation Angestellte hat neben den Angestellten-Daten die Attribute Abteilung und Beruf. Dann beantwortet der nachfolgende Operatorbaum die Frage, in welchen Abteilungen alle Berufe vertreten sind. Hier sind R und S die Relationen R(Ang_Nr, Abteilung, Beruf) und S(Beruf).

2.Beispiel:

Als zweites Beispiel seien folgende Relationen gegeben: Mitarbeiter, Abteilungen und die Abteilungszugehörigkeiten:

 Frage: Welche Mitarbeiter haben in allen Abteilungen gearbeitet? 
 Zeigen Sie Mita_ID, Name, Vorname, Ort, Gehalt an.
Mita_IDNameVornameOrtGehalt
4711MüllerAgatheGummersbach3000,00
4713MeierHugoKöln3400,00
4715SchmittErwinGummersbach2500,00
4717SchmitdElseGummersbach 
Abt_IDBezeichnungBudgetLeiter
10Einkauf240000,004711
20Verkauf350000,004897
30Produktion400000,004715
Abt_IDMita_IDvonbis
10471110.200012.2002
20471101.200302.2007
10471103.200711.2009
30471112.200911.2010
10471310.200112.2003
20471301.200409.2005
30471310.200509.2009
10471510.200012.2004
20471701.200207.2008
30471708.200809.2010
  Mitarbeiter * ( Projektion(Abt_ID, Mita_ID)(Abteilungszugehörigkeiten) ÷ Projektion(Abt_ID)(Abteilungen) )

  R = (Projektion(Abt_ID, Mita_ID)(Abteilungszugehörigkeiten)) =  {Abt_ID, Mita_ID} 
    = { (10,4711), (20,4711), (30,4711), (10,4713), (20,4713), (30,4713), (10,4715), (20,4717) }
  S = Projektion(Abt_ID)(Abteilungen) = {Abt_ID} = {10, 20, 30} 
  X = {Mita_ID}
  Ergebnismenge = {Mita_ID, Name, Vorname, Ort, Gehalt}

  X, das Zwischenergebnis nach der Division ist:
Mita_ID
4711
4713
 Das endgültige Ergebnis nach dem Natural Join von X mit der Mitarbeiter-Tabelle ist:
Mita_IDNameVornameOrtGehalt
4711MüllerAgatheGummersbach3000,00
4713MeierHugoKöln3400,00
  • Die Projektionen sind zum einen notwendig, um die Mengen R und S jeweils auf die semantisch relevanten Informationen zu beschränken (semantisch ohne Bedeutung: Budget, Leiter, von, bis). Semantisch irrelevante Attribute in R können unter Umständen dazu führen, dass keine Tupel gefunden werden, die in allen Attributwerten von X identisch sind. Zudem ist die Menge S so zu begrenzen, dass alle Attribute in R vorkommen (überflüssige Attribute: Bezeichnung, von, bis).
  • Der abschließende Natural Join ermöglicht es nun, die Ergebnismenge um weitere relevante Informationen des Mitarbeiters zu erweitern.
  • Diese Lösung ist nur ein möglicher Lösungsweg, so hätte z.B. der Natural Join auch bereits früher ausgeführt werden können, so dass die Mitarbeiter-Attribute zu R gehört hätten.

siehe auch: Operatorbaum, Projektion, Relationale-Algebra, EXISTS

Quellen:

  • Elmasri, Ramez/Navathe, Shamkant B.: "Grundlagen von Datenbanksystemen" , Pearson Studium, München, 2002, ISBN 3-8273-7021-3
  • Faeskorn-Woyke, Heide/Bertelsmeier, Birgit/Riemer, Petra/Bauer, Elena: "Datenbanksysteme - Theorie und Praxis mit SQL2003, Oracle und MySQL", Pearson Education, München, 2007, ISBN 978-3-8273-7266-6
  • Kemper, Alfons/Eickler, André: "Datenbanksysteme", Oldenbourg, München, 2009, 978-3-486-59018-0
  • Saake, Gunter/Sattler, Kai-Uwe/Heuer, Andreas: "Datenbanken - Konzepte und Sprachen", mitp-Verlag, Redline GmbH, Heidelberg, 2007, ISBN 3-8266-1664-2
  • Vossen, Gottfried: "Datenmodelle, Datenbanksprachen und Datenbankmanagementsysteme", Oldenbourg, München, 2008, ISBN 978-3-486-27574-2

Kategorie: Relationale Algebra, D