6.5 Bearbeitung von Join-Anfragen

6.5.2 Semi-Join-Strategien

Diese Vorgehensweise entspricht der Anwendung eines Semi-Joins. Denn es gilt:

R S R (S R) R (S _V (R))

wobei V dem Verbundattribut entspricht (bzw. der Menge der Verbundattribute). Die Join-Berechnung R S läuft demnach in folgenden Schritten ab:

1. In K_R: Bestimmung der Verbundattributwerte _V (R) und Übertragung an K_S

2. In K_S: Bestimmung von Z = (S _V (R)) = (S R) und Übertragung an K_R

3. In K_R: Bestimmung von R Z = R S.

Aufgrund folgender Äquivalenzen

R S R (S R)

R S (R S) S

R S (R S) (S R)

gibt es bei zwei Relationen jedoch insgesamt (wenigstens) drei Semi-Join-Strategien. Die zweite Strategie entspricht der ersten, wobei die Rollen von R und S vertauscht sind (Join-Bildung am S-Knoten). Die dritte Strategie enthält zwei Semi-Joins und kann z.B. sinnvoll sein, wenn das Gesamtergebnis an einem dritten Knoten berechnet werden soll. In letzterem Fall werden insgesamt fünf Teilschritte notwendig:

1a. In K_R: Bestimmung der Verbundattributwerte _V (R) und Übertragung an K_S

1b. In K_S: Bestimmung der Verbundattributwerte _V (S) und Übertragung an K_R

2a. In K_S: Bestimmung von Z1 = (S _V (R)) = (S R) und Übertragung an K

2b. In K_R: Bestimmung von Z2 = (R _V (S)) = (R S) und Übertragung an K

3. In K: Bestimmung von Z1 Z2 = R S.

Dabei entspricht K dem Knoten, an dem das Gesamtergebnis bestimmt wird. Zu beachten ist, daß die Schritte 1a und 1b sowie 2a und 2b jeweils parallel ausgeführt werden können. Die Nachrichtenanzahl hat sich von zwei auf vier erhöht. Wird auf die Parallelbearbeitung der beiden Relationen verzichtet, läßt sich der Übertragungsumfang reduzieren, indem Knoten K_S nur die Join-Attributwerte an K_R (oder umgekehrt) zurückliefert, die tatsächlich im Verbundergebnis erscheinen (s. Aufgabe 6-8:).

Beispiel 6-10

Die drei Semi-Join-Strategien sollen auf die Beispielrelationen in Abb. 6-12 angewendet werden. Wir veranschaulichen die Einzelschritte für den komplizierteren Fall mit zwei parallelen Semi-Joins. Die fünf Schritte liefern folgende Zwischenergebnisse:

1a. In K_R: Bestimmung von _B (R)

1b. In K_S: Bestimmung von _B (S)

2a. In K_S: Bestimmung von Z1 = (S _B (R))

2b. In K_R: Bestimmung von Z2 = (R _B (S))

3. In K: Bestimmung von Z1 Z2 = R S

.

Der Nachrichtenumfang dieser Strategie beträgt #AW = 19. Für die einfachen Semi-Join-Strategien betragen die Kosten #AW=11 bzw. #AW=8 für die Join-Berechnung an K_R bzw. K_S. Diese Kosten erhöhen sich jedoch um 8 Attributwerte, falls das Ergebnis an einen anderen Knoten transferiert werden muß.
Der Vergleich mit den einfachen Join-Strategien (Beispiel 6-8) zeigt, daß die Semi-Join-Methoden den Fetch-As-Needed-Ansätzen nicht nur in der Nachrichtenanzahl, sondern auch im Übertragungsumfang überlegen sind. Gegenüber Ship-Whole sind nur wenige zusätzliche Nachrichten erforderlich, jedoch kann das Übertragungsvolumen deutlich reduziert werden (8 vs. 14 AW).