q2:relationenalgebra [Infowiki]

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
=====Relationenalgebra=====
Mit der Grundregel und den Regeln für 1:n- und 1:1-Beziehungen haben wir das Instrumentarium 
zur Verfügung mit dem ein ER-Diagramm auf Relationen abgebildet werden kann. Sind die 
Daten in Tabellen erfasst, so stellt sich nun die Frage, wie mit diesen Tabellen 
gearbeitet werden kann und wie mit Hilfe dieser Tabellen Datenbankabfragen realisiert 
werden können. Wir werden sehen, dass dazu drei Grundoperationen nötig sind: 

  *Selektion
  *Projektion
  *Join

Diese Grundoperationen werden auf Relationen angewendet und können zu mathematischen Termen kombiniert werden. 
Man spricht daher auch von der //Relationenalgebra//.

=====Selektion - Auswahl von Zeilen=====
<WRAP box round>
Sei B eine Bedingung und R eine Relation. Die Bedingung B kann Konstanten und Attribute als Operanden, 
sowie Vergleichsoperatoren (<, <=, =, <>, =>, >) und logische Operatoren (and, or, not) enthalten. 
Dann ist die Selektion σ<sub>B</sub>(R) die Menge aller Datensätze, die die Bedingung B erfüllen.
</WRAP>

**Beispiel**

Gegeben ist die Relation KursLehrerRaum

^KursNr ^Lehrer ^Raum ^
|11 |Müller  |123 |
|12 |Schulze |124 |
|27 |Bauer   |14  |
|15 |Maier   |14  |
|17 |Maier   |17  |
|3  |Zange   |211 |

Die Selektion σ<sub>KursNr > 15</sub>(KursLehrerRaum) erzeugt durch Streichung von Zeilen die Relation:

^KursNr ^Lehrer ^Raum ^
|27 |Bauer   |14  |
|17 |Maier   |17  |

=====Projektion - Auswahl von Spalten=====
<WRAP box round>
Gegeben sei die Relation R(A, B, C, D, E, F, ...).\\
Dann ist π<sub>B, D, E, ...</sub>(R) die Projektion von R auf die Attribute B, D, E, ... 
</WRAP>

Duplikate müssen aus der projizierten Relation entfernt werden, denn mathematisch handelt es sich bei einer Relation um die Menge der Zeilen.

**Beispiel**

Gegeben ist die Relation KursLehrerRaum

^KursNr ^Lehrer ^Raum  ^
|11 |Müller  |123 |
|12 |Schulze |124 |
|27 |Bauer   |18  |
|15 |Maier   |14  |
|17 |Maier   |14  |
|3  |Zange   |211 |

Die Projektion π<sub>Lehrer, Raum</sub>(KursLehrerRaum) erzeugt durch Streichung von Spalten und Elimination der Doubletten die folgende Relation.

^Lehrer ^Raum  ^
|Müller  |123 |
|Schulze |124 |
|Bauer   |18  |
|Maier   |14  |
|Zange   |211 |


Datenbanksysteme entfernen standardmäßig keine Doubletten. Man muss dann spezielle Anweisungen zum Entfernen der Doubletten benutzen (z.B. SELECT DISTINCT)

=====Join - Verbinden von zwei Relationen=====
Bei der Abbildung eines ER-Diagramms auf Relationen werden Daten auf verschiedene Relationen verteilt. Mit der Join-Operation können zwei Relationen mit einem gemeinsamen Attribut zu einer Relation verbunden werden. In der Regel erfolgt die Verknüpfung über einen Primärschlüssel einer ersten Relation und den zugehörigen Fremdschlüssel in einer zweiten Relation. Der Join wird über drei Operationen berechnet: Kreuzprodukt der Relationen, Selektion und Projektion.

====Kreuzprodukt====
Beim Kreuzprodukt wird jede Zeile der ersten Relation mit jeder Zeile der zweiten Relation verbunden. 
  *Hat die erste Relation n Zeilen und die zweite m Zeilen, so besteht das Kreuzprodukt aus n*m Zeilen.
  *Hat die erste Relation n Spalten und die zweite m Spalten, so besteht das Kreuzprodukt aus n+m Spalten.

{{Kreuzprodukt.png}}

====Selektion====
Inhaltlich hat natürlich der Kurs 11 mit den Kursen 12, 27, 15, 17 und 3 nichts zu tun. Es interessiert eigentlich nur die Verbindung der Zeilen mit gleicher Kursnummer. Der Join macht daher als nächstes auf dem Kreuzprodukt eine Selektion über die gemeinsame Spalte bei gleichen Werten:

σ<sub>KursThemaStufe.KursNr = KursLehrerRaum.KursNr</sub>(KursThemaStufe ⨉ KursLehrerRaum)

{{Join.png}}

====Projektion====
Die gemeinsame Spalte //KursNr// wird in der Ergebnisrelation nur einmal benötigt, weswegen der Join zum Abschluss mit einer Projektion die zweite KursNr eliminiert. 

====Join====
Als Ergebnis der drei Operationen (Kreuzprodukt, Selektion, Projektion) kommt der sogenannte //Join// (Zeichen: ⨝, Unicode U+2A1D) heraus. Wird das Join-Zeichen (Ersatzsymbol {{JoinSymbol.png}}) bei älterer Software (z. B. Windows XP) nicht richtig angezeigt, so muss ein Zeichensatz, der Unicode-Zeichen darstellen kann, installiert werden ([[http://de.wikipedia.org/wiki/Hilfe:UTF-8-Probleme|UTF-8-Probleme]]).

{{Join2.png}}

<WRAP pre>
KursThemaStufe ⨝ KursLehrerRaum = \\
 π<sub>KursNr, Thema, Stufe, Lehrer, Raum</sub>(\\
 σ<sub>KursThemaStufe.KursNr = KursLehrerRaum.KursNr</sub>(KursThemaStufe ⨉ KursLehrerRaum))
</WRAP>

<WRAP box round>
Der **Join** verbindet zwei Relationen über gemeinsame Spalten bei gleichen Attributwerten.
</WRAP>


=====Join-Varianten=====

Den Join gibt es in verschiedenen Varianten. Grundlage aller Joins ist die Bildung des Kreuzproduktes der beiden beteiligten Relationen. 
Die Varianten unterscheiden sich hinsichtlich der Bildung der anschließenden Selektion. 

Nur der //Natural Join// projiziert doppelte vorkommende Attribute aus. Alle anderen Joins führen keine Projektion aus. 
Dies führt zwangsläufig zu Namenskonflikten, denn wenn zwei Relationen gleichbenannte Attribute haben, so enthält deren Join 
gleichbenannte Attribute, wobei die Attributwerte durchaus unterschiedlich sein können. Auf einer solchen Relation sind die grundlegenden Operationen Selektion und Projektion nicht mehr definiert, weil man bei einem Bezug auf ein doppelt vorkommendes Attribut nicht entscheiden kann, welche Spalte gemeint ist. 

Es gibt zwei Ansätze, dieses Problem zu lösen. Man kann erstens qualifizierende Attributnamen verwenden. Dabei ist der Join R<sub>1</sub> {{JoinSymbol.png}} R<sub>2</sub> der beiden Relationen R<sub>1</sub>(A<sub>1</sub>, A<sub>2</sub>,..., A<sub>n</sub>, B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>) und  R<sub>2</sub>(C<sub>1</sub>, C<sub>2</sub>,...,C<sub>m</sub>, B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>) mit k gleichbenannte Attributen B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub> die Relation 
mit den Attributen (A<sub>1</sub>, A<sub>2</sub>,...,A<sub>n</sub>, R<sub>1</sub>.B<sub>1</sub>, R<sub>1</sub>.B<sub>2</sub>,..., R<sub>1</sub>.B<sub>k</sub>, R<sub>2</sub>.B<sub>1</sub>, R<sub>2</sub>.B<sub>2</sub>,...,R<sub>2</sub>.B<sub>k</sub>, C<sub>1</sub>, C<sub>2</sub>,...,C<sub>m</sub>). Die Qualifizierung besteht also darin, dass man einem Attributnamen die Relation voranstellt, aus der das betreffende Attribut kommt. 

Der zweite Ansatz besteht darin, als zusätzliche Operation der Relationenalgebra die [[Relationenalgebra#Umbenennung|Umbenennung]]  einzuführen. Mit der Umbenennung sorgt man dafür, dass alle gleichbenannten Attribute in einer der beiden beteiligten Relationen vor einem Join so umbenannt werden, dass die beiden Relationen keine gleichbenannten Attribute mehr haben. Wir verwenden diesen zweiten Ansatz, weil er erstens die implizite Umbenennung, die beim ersten Ansatze stattfindet, explizit macht und zweitens bei Joins über rekursive Beziehungen (R<sub>1</sub> {{JoinSymbol.png}} R<sub>1</sub>) der erste Ansatz sowieso versagt.

====Natural Join====
Der sogenannte //Natural Join// entspricht im Wesentlichen dem im vorangegangenen Kapitel beschriebenen //Join//.
Allerdings muss berücksichtigt werden, dass in den beiden Relationen, die gejoint werden sollen, mehrere gleichbenannte Attribute vorkommen können. Wenn dies der Fall ist, so findet nach dem Kreuzprodukt eine Selektion über alle Paare gleichbenannter Attribute statt, d.h. es werden nur die Datensätze selektiert, bei denen paarweise die Werte gleichbenannter Spalten gleich sind. 

Dürfen gleichbenannte Attribute nicht zur Bestimmung des Natural Joins herangezogen werden, so benennt man diese Attribute in einer der beiden Relationen um.

Im Unterschied zu allen anderen Join-Varianten projiziert der Natural Join doppelt vorkommende Spalten aus.

<WRAP box round>
Sind R<sub>1</sub>(A<sub>1</sub>, A<sub>2</sub>,...,A<sub>n</sub>, B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>) und  R<sub>2</sub>(C<sub>1</sub>, C<sub>2</sub>,...,C<sub>m</sub>, B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>)\\ 
zwei Relationen mit den k gleichbenannten Attributen B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>,\\
so ist der Natural Join R<sub>1</sub> ⨝ R<sub>2</sub> eine Relation\\
mit den Attributen (A<sub>1</sub>, A<sub>2</sub>,..., A<sub>n</sub>, B<sub>1</sub>, B<sub>2</sub>,...,B<sub>k</sub>, C<sub>1</sub>, C<sub>2</sub>,...,C<sub>m</sub>).
</WRAP>

Haben R<sub>1</sub> und R<sub>2</sub> kein gemeinsames Attribut, so findet keine Selektion statt, aus dem Join wird ein Kreuzprodukt.

====Equi Join====
Beim Equi-Join gibt man unterhalb der Join-Symbols an, welche Attributpaare gleich sein sollen. 

{{equijoin.png}}

====Theta Join====
Der Theta-Join ist eine Verallgemeinerung des Equi-Joins. Als Selektionsbedingungen sind nicht nur Gleichheit, sondern auch andere Vergleichskriterien möglich. Beispiel:

{{thetajoin.png}}


====Outer Join====
Zur Erläuterung der Outer Joins verwenden wir eine Relation Artikel mit den Attributen ANr (Artikelnummer), Name des Artikels und KNr als Fremdschlüssel in die Relation Kategorie, welche ihrerseits die Attribute KNr (Kategorienummer) und Bezeichnung hat. 

Artikel
^ANr  ^Name ^KNr ^
|1 |Schokolade |4 |
|2 |Edamer     |1 |
|3 |Tofu       |NULL |
|4 |Lachs      |2 |

Kategorie
^KNr  ^Bezeichnung |
|1 |Milchprodukte |
|2 |Meeresfrüchte |
|3 |Getränke      |
|4 |Süßwaren      |


====Left Outer Join====
Beim Left Outer Join werden alle Zeilen der //linken// Tabelle in die Ergebnisrelation übernommen. Fehlt bei einer Zeile der Join-Partner, wird mit NULL-Werten aufgefüllt.

^ANr  ^Name  ^KNr ^KNr ^Bezeichnung ^
|1 |Schokolade |4    |4    |Süßwaren      |
|2 |Edamer     |1    |1    |Milchprodukte |
|3 |Tofu       |NULL |NULL |NULL          |
|4 |Lachs      |2    |2    |Meeresfrüchte |


====Right Outer Join====
Beim Right Outer Join werden alle Zeilen der //rechten// Tabelle in die Ergebnisrelation übernommen. Fehlt bei einer Zeile der Join-Partner, wird mit NULL-Werten aufgefüllt.

^ANr  ^Name  ^KNr  ^KNr ^Bezeichnung     ^
|2   |Edamer     |1    |1 |Milchprodukte |
|4   |Lachs      |2    |3 |Meeresfrüchte |
|NULL|NULL       |NULL |3 |Getränke      |
|1   |Schokolade |4    |4 |Süßwaren      |


====Full Outer Join====
Beim Full Outer Join werden alle Zeilen der //linken// und //rechten// Tabelle in die Ergebnisrelation übernommen. Fehlt bei einer Zeile der Join-Partner, wird mit NULL-Werten aufgefüllt.

^ANr ^Name ^KNr ^KNr ^Bezeichnung ^
|1   |Schokolade |4    |4    |Süßwaren      |
|2   |Edamer     |1    |1    |Milchprodukte |
|3   |Tofu       |NULL |NULL |NULL          |
|4   |Lachs      |2    |2    |Meeresfrüchte |
|NULL|NULL       |NULL |3    |Getränke      |

=====Umbenennung - Beseitigung gleichbenannter Attribute=====
Die Umbenennung (engl. rename, grie. Buchstabe rho ρ) als Operation der Relationenalgebra wird zur Lösung von Namenskonflikten bei Join-Operationen benötigt.

<WRAP box round>
Gegeben sei die Relation R(A, B, C, D, E, F, ...). 
Dann ist ρ<sub>A→X, B→Y, D→Z</sub>(R) eine Umbenennung der drei Attribute A, B und D in X, Y und Z. 
Die Relation ρ<sub>A→X, B→Y, D→Z</sub>(R) hat die Attribute (X, Y, C, Z, E, F, ...).
</WRAP>

**Beispiel**

Gegeben ist die Tabelle KursLehrerRaum

^KursNr ^Lehrer ^Raum ^
|11 |Müller  |123 |
|12 |Schulze |124 |
|27 |Bauer   |14  |
|15 |Maier   |14  |
|17 |Maier   |17  |
|3  |Zange   |211 |

Die Umbenennung ρ<sub>KursNr→KursID, Lehrer→Name</sub>(KursLehrerRaum) erzeugt diese Tabelle:

^KursID ^Name ^Raum ^
|11 |Müller  |123 |
|12 |Schulze |124 |
|27 |Bauer   |14  |
|15 |Maier   |14  |
|17 |Maier   |17  |
|3  |Zange   |211 |

=====Mengenoperationen=====
Außer den drei wichtigen Operationen Selektion, Projektion und Join gibt es noch sogenannte Mengenoperationen, wie sie aus der Mengenlehre bekannt sind:
  * Vereinigung  
  * Durchschnitt
  * Differenz


//Vereinigung//
<WRAP box round>
Die Vereinigung A ∪ B zweier Relationen A und B besteht aus allen Datensätzen die in A oder B vorkommen.
</WRAP>

{{AuB.png}}

//Durchschnitt//
<WRAP box round>
Der Durchschnitt A ∩ B besteht aus allen Datensätzen die sowohl in A als auch in B vorkommen.
</WRAP>

{{AgB.png}}

//Differenz//
<WRAP box round>
Die Differenz A\B besteht aus allen Datensätzen die in A, aber nicht in B vorkommen.
</WRAP>

{{AoB.png}}

=====Anwendung=====
Zur Darstellung eines komplexeren Beispiels gehen wir von folgenden Tabellen einer Oberstufenverwaltung aus:

{{JoinAnwendung1.png}}

Es soll die Frage beantwortet werden, welche Mädchen Informatikkurse besuchen und welche Punktzahlen sie dabei erreicht haben.

1. Bestimmung der Informatikkurse

Informatikurse = π<sub>Kurs-Nr</sub>(σ<sub>Fach = 'Informatik'</sub>(Kurs))

{{JoinAnwendung2.png}}

2. Join mit der Besucht-Tabelle über das gemeinsame Schlüsselattribut //Kurs-Nr// liefert die Informatik-Schüler:

Informatikschüler = Informatikkurse {{JoinSymbol.png}} Besucht

{{JoinAnwendung3.png}}

3. Projektion auf die benötigten Attribute Schüler-Nr und Punkte:

InformatikschülerPunkte = π<sub>Schüler-Nr, Punkte</sub>(Informatikschüler)

{{JoinAnwendung4.png}}

4. Join mit Schüler-Tabelle über das gemeinsame Schlüsselattribut Schüler-Nr.

InformatikschülerPunkteName = InformatikschülerPunkte {{JoinSymbol.png}} Schüler

{{JoinAnwendung5.png}}

5. Selektion der Mädchen und Projektion auf die geforderten Angaben.

Ergebnis = π<sub>Punkte, Name, Vorname</sub>σ(<sub>Geschlecht = 'w'</sub>(InformatikschülerPunkteName))

{{JoinAnwendung6.png}}

6. Formal lässt sich die Berechnung der Anfrage durch folgenden Term der Relationenalgebra darstellen:

π<sub>Punkte, Name, Vorname</sub>(σ<sub>Geschlecht = 'w'</sub>(π<sub>Schüler-Nr, Punkte</sub>(π<sub>Kurs-Nr</sub>(σ<sub>Fach = Informatik</sub>(Kurs)) {{JoinSymbol.png}} Besucht) {{JoinSymbol.png}} Schüler))

=====Aufgaben =====
1. Gegeben seien drei Relationen:

{{JoinAnwendung7.png}}

a) Rekonstruiere das ER-Diagramm, aus dem die drei Relationen entstehen.\\
b) Bilde Serviert {{JoinSymbol.png}} Mag. Welche Informationen beinhaltet diese Relation?\\
c) Berechne mit einem Term der Relationenalgebra die Bars, die ein Bier servieren, das Karl mag. \\
d) Berechne die Biersorten, die in den besuchten Bars serviert werden.


2. Gegeben seien folgende Relationen für drei Entitätstypen und eine ternäre Beziehung (# ist das Zeichen für Nummer):

{{ERLieferung.png}}

Lieferanten(L#, LName, Status, Stadt)\\
Teile (T#, TName, Farbe, Gewicht, Stadt)\\
Projekte (P#, PName, Stadt)\\
Lieferungen (L#, T#, P#, Anzahl)

Hierbei bedeutet Stadt einmal die Stadt, in der ein Lieferant sitzt, die Stadt, in der das entsprechende Teil hergestellt wird, bzw. die Stadt, in der ein Projekt stattfindet. Löse die folgenden Aufgaben durch Operationen aus der Relationenalgebra:

a) Finde alle Lieferungen mit Anzahlen zwischen 300 und 750 und gib alle dazu in der Relation Lieferungen verzeichneten Informationen aus.\\
b) Gib alle Städte aus, in denen Lieferanten sitzen.\\
c) Gib alle vorkommenden Paarungen TName, Stadt aus.\\
d) Finde alle schwarzen Teile. Gib ihre Nummer und ihren Namen aus.\\
e) Finde alle Lieferanten, die in einer Einzellieferung mehr als 150 Teile geliefert haben. Gib ihren Namen aus.\\
f) Finde alle Teile, die von Lieferanten in London geliefert wurden. Gib davon die Teilenummer aus. Ändere so, dass der Teilenamen ausgegeben wird.\\
g) Finde alle Orte, in denen sowohl Projekte als auch Lieferanten beheimatet sind.\\
h) Finde alle Projekte, die mindestens einen Lieferanten für das Projekt im gleichen Ort haben. Gib die Projektnummer aus.\\
i) Finde alle Teile, die der Lieferant Lux geliefert hat. Gib alle Teilinformationen von diesen Teilen aus.

3. Gib Lösungen der Übungen 1 bis 5 zur Lektion 3 des [http://www.imoodle.de/sqltutorial/index.html |interaktiven SQL-Tutorials] als Terme der Relationenalgebra an.

4. Bestimme jeweils einen Relationenalgebraterm:

a) Für die rekursive Beziehung [[Spezielle_Beziehungen#rekursive_Beziehungen|ist_Vorgesetzter_von]] mit der Relation Mitarbeiter(__Personalnummer__, Nachname, Vorname, ↑VorgesetztenPersonalnummer) sollen die Mitarbeiter, die den Vorgesetzten //Paul Schmidt// haben, bestimmt werden. 

b) Es soll eine Relation mit Name und Vorname aller Mitarbeiter erzeugt werden, die zu jedem Mitarbeiter auch Name und Vorname des Vorgesetzten enthält.

=====Weblinks=====

Wikibooks: http://de.wikibooks.org/wiki/Relationenalgebra_und_SQL