Q2 / Datenbanken

Relationenalgebra

Lösung geprüft

Die Aufgabe der heutigen Stunde ist die Relationenalgebra! Das ist sozusagen das mathematische Gerüst hinter SQL. Statt SELECT … FROM … WHERE schreibt man griechische Buchstaben – gemeint ist aber genau dasselbe. Wer SQL kann, kann das hier auch, man muss nur die drei Symbole zuordnen.

Die drei Operatoren, um die es geht

Die Merkhilfe für die beiden wichtigsten: Sigma steht für Selektion und wählt Zeilen, Pi steht für Projektion und wählt Spalten. Das verwechselt man am Anfang ständig.

Das Datenmodell

Flugzeug(Kennz, Baujahr, Typ, Sitze)
Flugstrecke(FlugNr, Abflugzeit, Dauer, Start, Ziel, Meilen)
Passagier(Pnr, Vorname, Name)
FrequentFlyer(Pnr)                 -- ein Passagier "kann" einer sein
Meilenkonto(Kontonr, Praemienmeilen)

fliegt(Kennz, FlugNr)              -- n:m zwischen Flugzeug und Flugstrecke
gebucht_von(FlugNr, Pnr)           -- n:m zwischen Flugstrecke und Passagier
hat(Pnr, Kontonr)                  -- 1:1 zwischen FrequentFlyer und Meilenkonto

erDiagram
    Flugzeug }o--o{ Flugstrecke : "fliegt (n kann : m kann)"
    Flugstrecke }|--|{ Passagier : "gebucht von (n muss : m muss)"
    Passagier |o--o| "Frequently-Flyer" : "ist (1 kann : 1 kann)"
    "Frequently-Flyer" ||--|| Meilenkonto : "hat (1 muss : 1 muss)"
    Flugzeug {
        string Kennz PK
        int Baujahr
        string Typ
        int Sitze
    }
    Flugstrecke {
        string FlugNr PK
        time Abflugzeit PK
        int Dauer
        string Start
        string Ziel
        int Meilen
    }
    Passagier {
        int Pnr PK
        string Vorname
        string Name
    }
    Meilenkonto {
        int Kontonr
        int Praemienmeilen
    }

Beim Datenmodell oben stehen die Schlüsselattribute jeweils vorne. Bei der Flugstrecke sind das zwei: im ER-Diagramm sind FlugNr und Abflugzeit beide unterstrichen. Eine Flugstrecke wird also erst durch beide zusammen eindeutig – dieselbe Flugnummer kann ja mehrmals am Tag abgehen. Streng genommen müsste gebucht_von deshalb (FlugNr, Abflugzeit, Pnr) heißen. Für die Aufgaben hier reicht die kurze Schreibweise, aber wissen sollte man es.

Aufgabe 1 – Vornamen aller Meyers

π_Vorname( σ_Name='Meyer' (Passagier) )

Von innen nach außen lesen: erst σ die Zeilen heraussuchen, in denen der Nachname Meyer ist, dann π nur die Spalte Vorname behalten. In SQL:

SELECT Vorname FROM Passagier WHERE Name = 'Meyer';

Die Reihenfolge ist wichtig. σ_Name='Meyer'(π_Vorname(Passagier)) wäre falsch – die Projektion hätte die Spalte Name schon weggeworfen, und danach kann man nicht mehr danach filtern.

Aufgabe 2 – Alle Kontonummern

π_Kontonr( Meilenkonto )

Mehr braucht es nicht. Laut ER-Diagramm hat jeder Frequent Flyer genau ein Meilenkonto (1 muss) und jedes Meilenkonto gehört zu genau einem Frequent Flyer. Es gibt also keine Konten ohne Frequent Flyer – alle Kontonummern in der Tabelle sind automatisch die gesuchten.

Ausführlicher ginge auch π_Kontonr(FrequentFlyer ⋈ hat ⋈ Meilenkonto), aber der Join filtert nichts weg. Die Aufgabe sagt „geben Sie den Relationen-Operator an" – Einzahl, also ist die kurze Fassung gemeint.

Aufgabe 3 – Von London nach New York

π_Name( σ_Start='London' ∧ Ziel='New York' (Flugstrecke) ⋈ gebucht_von ⋈ Passagier )

Drei Schritte:

1. σ sucht die passenden Flugstrecken heraus – beide Bedingungen mit ∧ verknüpft
2. ⋈ verbindet über gebucht_von mit den Passagieren
3. π behält nur die Nachnamen

Es sind zwei Joins nötig, weil gebucht_von eine n:m-Beziehung ist – genau wie bei schueler_hat_lehrer muss man über die Verknüpfungstabelle in der Mitte gehen.

Man filtert übrigens zuerst und verbindet danach, nicht umgekehrt. Beides liefert dasselbe Ergebnis, aber so bleibt die Zwischentabelle klein.

Aufgabe 4 – Was macht diese Anfrage?

π_FlugNr( Flugstrecke ⋈ gebucht_von ⋈ Passagier ⋈ FrequentFlyer )

Die Anfrage liefert die Flugnummern aller Flugstrecken, auf denen mindestens ein Frequent Flyer gebucht ist.

Warum? Die Kette verbindet Flugstrecken mit ihren Passagieren und diese dann mit der Tabelle FrequentFlyer. Der Join wirkt dabei wie ein Filter: Passagiere, die keine Frequent Flyer sind, haben dort keinen Eintrag und fallen deshalb raus. Übrig bleiben nur Strecken mit mindestens einem Vielflieger.

Das ist der Punkt, den man in der Antwort nennen sollte: hier steht kein σ, und trotzdem wird gefiltert – nämlich durch den Join selbst. Genau dafür ist INNER JOIN in SQL bekannt.

Und: π entfernt automatisch Doppelte. Eine Strecke mit drei Vielfliegern erscheint also nur einmal, nicht dreimal. In SQL müsste man dafür ausdrücklich DISTINCT schreiben.

Aufgabe 5 – Die zweite Anfrage

π_Kennzeichen( σ_Name='Schmitz' ( σ_Start='Berlin' (Flugstrecke ⋈ Flugzeug)
                                ⋈ gebucht_von ⋈ Passagier ) )

Die Anfrage liefert die Kennzeichen aller Flugzeuge, die auf einer in Berlin startenden Strecke fliegen, auf der ein Passagier namens Schmitz gebucht ist.

Von innen nach außen abgearbeitet:

1. Flugstrecke ⋈ Flugzeug – welches Flugzeug fliegt welche Strecke
2. σ_Start='Berlin' – nur die Strecken, die in Berlin starten
3. ⋈ gebucht_von ⋈ Passagier – die Passagiere dazuholen
4. σ_Name='Schmitz' – nur die Zeilen mit Passagier Schmitz
5. π_Kennzeichen – nur das Flugzeugkennzeichen ausgeben

flowchart TD
    A["Flugstrecke"]
    B["Flugzeug"]
    J1["⋈ welches Flugzeug fliegt welche Strecke"]
    S1["σ Start='Berlin'"]
    C["gebucht_von"]
    D["Passagier"]
    J2["⋈ die Passagiere dazuholen"]
    S2["σ Name='Schmitz'"]
    P["π Kennzeichen"]
    E["Kennzeichen aller Flugzeuge auf einer<br>Berlin-Strecke mit einem Passagier Schmitz"]

    A --> J1
    B --> J1
    J1 --> S1
    S1 --> J2
    C --> J2
    D --> J2
    J2 --> S2
    S2 --> P
    P --> E

Interessant ist, dass die beiden σ an verschiedenen Stellen stehen. Das Start-Kriterium wird früh angewendet, solange nur Strecken und Flugzeuge im Spiel sind. Das Namenskriterium geht erst, nachdem die Passagiere dazugekommen sind – vorher gibt es die Spalte Name gar nicht.

Aufgabe 6 – Müller und Schmitz im selben Flugzeug

Diese Aufgabe ist die schwerste, weil man dieselbe Tabelle zweimal braucht. Der Trick: man baut zwei getrennte Mengen und schneidet sie.

Strecken mit einem Mueller:
  M := π_FlugNr( σ_Name='Müller' (Passagier) ⋈ gebucht_von ⋈ Flugstrecke )

Strecken mit einem Schmitz:
  S := π_FlugNr( σ_Name='Schmitz' (Passagier) ⋈ gebucht_von ⋈ Flugstrecke )

Die gesuchten Strecken:
  M ∩ S

Als ein Ausdruck:

π_FlugNr( σ_Name='Müller' (Passagier) ⋈ gebucht_von ⋈ Flugstrecke )
  ∩
π_FlugNr( σ_Name='Schmitz' (Passagier) ⋈ gebucht_von ⋈ Flugstrecke )

Der Schnitt ∩ liefert die Flugnummern, die in beiden Mengen vorkommen – also Strecken, auf denen sowohl ein Müller als auch ein Schmitz sitzt. Ist das Ergebnis leer, lautet die Antwort auf die Frage „nein".

Warum man das nicht in einem Schritt machen kann

σ_Name='Müller' ∧ Name='Schmitz' (Passagier)      -- FALSCH, immer leer

Das wäre die naheliegende Idee, ergibt aber nie ein Ergebnis: σ arbeitet zeilenweise, und kein einzelner Passagier heißt gleichzeitig Müller und Schmitz. Es sind ja zwei verschiedene Personen gesucht, die dasselbe Flugzeug teilen.

Immer wenn eine Aufgabe zwei verschiedene Zeilen derselben Tabelle miteinander vergleicht, braucht man entweder einen Schnitt wie hier oder einen Self-Join. In SQL würde man es so schreiben:

SELECT DISTINCT g1.FlugNr
FROM   gebucht_von AS g1
INNER JOIN Passagier AS p1 ON g1.Pnr = p1.Pnr
INNER JOIN gebucht_von AS g2 ON g1.FlugNr = g2.FlugNr
INNER JOIN Passagier AS p2 ON g2.Pnr = p2.Pnr
WHERE  p1.Name = 'Müller' AND p2.Name = 'Schmitz';

Dieselbe Tabelle steht zweimal in der Abfrage, einmal als g1 und einmal als g2. Genau das leistet in der Relationenalgebra der Schnitt der beiden Teilmengen.