6.3 Erzeugung von Fragment-Anfragen

6.3.1 Daten-Lokalisierung bei primärer horizontaler Fragmentierung

Die primäre horizontale Fragmentierung (Kap. 5.3) zerlegt eine Relation aufgrund von Selektionsprädikaten auf Attributen der Relation. Die Rekonstruktion der Relation ergibt sich durch Vereinigung der einzelnen Fragmente. Selektionsanfragen auf derart fragmentierten Relationen lassen sich ggf. vereinfachen, falls sie sich auf Fragmentierungsattribute beziehen, welche zur Definition der Fragmentierung verwendet wurden. Damit kann die Anfrage ggf. auf eine Teilmenge der Fragmente begrenzt werden, so daß sich der Verarbeitungsaufwand sowie der Kommunikationsbedarf reduzieren.

Beispiel 6-3

Die Relation KONTO sei folgendermaßen horizontal auf dem Attribut KNR (Kundennummer) fragmentiert:
KONTO1 = KNR "K3" (KONTO)
KONTO2 = "K3" < KNR "K6" (KONTO)
KONTO3 = KNR > "K6" (KONTO)
Folgende Anfrage sei zu bearbeiten:
SELECT * FROM KONTO WHERE KNR="K5"
Im ersten Schritt wird im Operatorbaum für diese Anfrage die Relation KONTO durch den sie rekonstruierenden Operatorbaum ersetzt; das Ergebnis zeigt Abb. 6-7a. Da sich die Selektion auf das Fragmentierungsattribut KNR bezieht, kann eine algebraische Vereinfachung vorgenommen werden. Nach Vertauschung von Vereinigung und Selektion (Vorziehen der Selektionsoperation auf die Fragmente) erkennt man leicht, daß sich auf den Fragmenten KONTO1 und KONTO3 die leere Ergebnismenge ergibt. Die Verarbeitung ist daher auf Fragment KUNDE2 beschränkt, so daß sich der Vereinigungsoperator ebenfalls erübrigt. Damit ergibt sich der in Abb. 6-7b gezeigte Operatorbaum, der lokal an einem Rechner ausführbar ist.

Abb. 6-7: Daten-Lokalisierung bei horizontaler Fragmentierung (Selektion)

Solche Vereinfachungen lassen sich ggf. auch für Join-Anfragen nutzen, falls die beteiligten Relationen horizontal fragmentiert sind. Ein erster Join-Ansatz besteht darin, zunächst für die beteiligten Relationen die Vereinigung der einzelnen Fragmente zu bilden und danach die Join-Berechnung vorzunehmen. Dabei können ggf. wieder einige Fragmente von der Bearbeitung ausgeschlossen werden, falls zusätzliche Selektionsbedingungen auf dem Fragmentierungsattribut vorliegen. Alternativ dazu kann jedoch auch zunächst eine Join-Berechnung zwischen den einzelnen Fragmenten und anschließend eine Vereinigung der Teilergebnisse vorgenommen werden (aufgrund von Regel 12 in Abb. 6-6). Ein Vorteil dabei liegt darin, daß die einzelnen Teil-Joins parallel zueinander ausgeführt werden können. Im schlimmsten Fall ist jedoch für jedes Fragment der ersten Relation eine Join-Berechnung mit jedem Fragment der zweiten Relation erforderlich. Allerdings kann der Aufwand oft erheblich reduziert werden, falls beide Relationen auf dem Join-Attribut fragmentiert sind. Denn dann ist für ein Fragment der einen Relation eine Join-Berechnung i.a. nur mit einer Teilmenge der Fragmente der anderen Relation erforderlich.

Beispiel 6-4

Die Relationen KUNDE und KONTO seien beide horizontal auf dem Attribut KNR (Kundennummer) fragmentiert. Für KONTO unterstellen wir die Fragmentierung aus dem vorherigen Beispiel 6-3; KUNDE sei folgendermaßen zerlegt:
KUNDE1 = KNR "K3" (KUNDE)
KUNDE2 = KNR > "K3" (KUNDE).
Für die Join-Anfrage
SELECT * FROM KUNDE, KONTO
WHERE KUNDE.KNR=KONTO.KNR
ergibt sich damit der in Abb. 6-8a gezeigte Fragment-Ausdruck. Nach Vertauschen der Ausführungsreihenfolge für Vereinigung und Join-Berechnung wäre für jedes der drei KONTO-Fragmente die Join-Bildung mit den beiden KUNDE-Fragmenten erforderlich. Aufgrund der Fragmentierung über das Join-Attribut sowie der Tatsache, daß die Fragmentierungsprädikate für KONTO1 und KUNDE1 übereinstimmen und das Fragmentierungsprädikat für KUNDE2 der Vereinigung der Fragmentierungsprädikate von KONTO2 und KONTO3 entspricht, können jedoch einige Join-Berechnungen eliminiert werden, da sie die leere Ergebnismenge liefern. Dies trifft für die Teil-Joins KONTO1 KUNDE2, KONTO2 KUNDE1 sowie KONTO3 KUNDE1 zu. Der somit reduzierte Operatorbaum ist in Abb. 6-8b gezeigt. Die dabei anfallenden Join-Operationen können parallel berechnet werden. Zudem konnte die bei der Join-Berechnung zu berücksichtigende Datenmenge reduziert werden, da jeder Kontosatz nur mit einer Teilmenge der Kundensätze abgeglichen werden muß und nicht mehr mit der gesamten Kundenrelation wie in der Ausgangslösung.

Abb. 6-8: Daten-Lokalisierung bei horizontaler Fragmentierung (Join-Berechnung)