In normalisierten Datenbanken sind Informationen auf mehrere Tabellen verteilt. Um zusammenhängende Daten gemeinsam abzufragen, müssen die Tabellen verknüpft werden. Diese Verknüpfung heißt in der Relationenalgebra Verbund (englisch join) und entspricht dem SQL-JOIN.
Der natürliche Verbund \( R \bowtie S \) verknüpft zwei Relationen über alle gleichnamigen Attribute. Tupel werden zusammengeführt, wenn die Werte aller gemeinsamen Attribute übereinstimmen. Doppelte Spalten werden entfernt.
Beispiel: SCHÜLER (sid, name, klasse_id) und KLASSE (klasse_id, bezeichnung). Der natürliche Verbund verbindet beide über klasse_id:
schüler ⋈ klasse
sid|name |klasse_id|bezeichnung
---+-----+---------+-----------
1 |Anna | 12 |12a
2 |Ben | 11 |11bIn SQL: SELECT * FROM schüler NATURAL JOIN klasse;.
Der Theta-Verbund kombiniert die Relationen mit einer beliebigen Vergleichsbedingung \( \theta \) (z. B. =, <, >). Formal:
\[ R \bowtie_{\theta} S = \sigma_{\theta}(R \times S) \]
Beispiel: alle Schüler-Tupel, deren klasse_id kleiner ist als kid in KLASSE:
\[ \text{SCHÜLER} \bowtie_{\text{schüler.klasse\_id} < \text{klasse.kid}} \text{KLASSE} \]
SQL: SELECT * FROM schüler s, klasse k WHERE s.klasse_id < k.kid;.
Ein Equi-Join ist ein Theta-Verbund, bei dem die Bedingung ausschließlich Gleichheit ist. Anders als der natürliche Verbund werden hier beide Spalten im Ergebnis behalten:
\[ R \bowtie_{R.A = S.B} S \]
SQL: SELECT * FROM schüler s INNER JOIN klasse k ON s.klasse_id = k.kid;.
Bei den bisher gezeigten Joins fallen Tupel ohne Partner weg. Der Outer Join behält sie und füllt fehlende Werte mit NULL auf. Es gibt drei Varianten: links (\( \mathbin{\unicode{x27D5}} \)), rechts (\( \mathbin{\unicode{x27D6}} \)) und voll (\( \mathbin{\unicode{x27D7}} \)). In SQL: LEFT JOIN, RIGHT JOIN, FULL OUTER JOIN.
Joins sind die wichtigsten Operationen in echten Datenbanken, gleichzeitig aber die teuersten. Datenbanksysteme nutzen Indexe, Hash-Joins und Merge-Joins, um Joins effizient zu berechnen. Für das Abitur reicht es zu wissen: ein natürlicher Verbund läuft im Worst Case in \( \mathcal{O}(n \cdot m) \), kann mit Sortierung und Hashing aber auf \( \mathcal{O}(n + m) \) reduziert werden.
Verwendung des natürlichen Verbunds, obwohl die zu verbindenden Spalten unterschiedliche Namen haben (Ergebnis: kartesisches Produkt!), Vergessen der Join-Bedingung beim Theta-Verbund, Verwechslung von INNER und OUTER JOIN, Pfeilrichtung bei LEFT/RIGHT.
Zusammenfassung: Der natürliche Verbund verbindet über gleichnamige Spalten, der Theta-Verbund über eine beliebige Bedingung, der Equi-Join über Gleichheit. Outer Joins behalten Tupel ohne Partner.
Abitur-Tipp: Skizziere bei Joinaufgaben immer die Zwischenschritte: zuerst das kartesische Produkt, dann die Selektion, schließlich die Projektion.