6 Verteilte Anfragebearbeitung

Übungsaufgaben

PERSONAL (PNR, PNAME, BERUF, GEHALT)

PROJEKT (PRONR, PRONAME, PROBUDGET)

PMITARBEIT (PNR, PRONR, DAUER).

Bestimmen Sie für die Qualifikationsbedingung der folgenden Anfrage die konjunktive und disjunktive Normalform:

SELECT * FROM PERSONAL
WHERE (PNAME LIKE "M%" AND BERUF = "Techniker") OR
((PNR > 550 OR BERUF="Programmierer") AND GEHALT < 80000)

(Lösung Aufgabe 6-1:)

Vereinfachen Sie die Qualifikationsbedingung der folgenden Anfrage durch Anwendung der Idempotenzregeln:

SELECT * FROM PERSONAL
WHERE PNR > 456 AND
NOT (BERUF = "Techniker" OR GEHALT < 50000) AND
BERUF "Techniker" AND GEHALT < 50000

(Lösung Aufgabe 6-2:)

Führen Sie die Anfragetransformation für folgende Query durch:

SELECT PNAME, PRONAME
FROM PERSONAL P, PROJEKT PT, PMITARBEIT PM
WHERE DAUER > 10 AND P.PNR=PM.PNR AND
BERUF="Programmierer" AND PT.PRONR=PM.PRONR.

Bestimmen Sie den Operatorbaum und führen darauf Vereinfachungen und Restrukturierungen zur algebraischen Optimierung durch.

(Lösung Aufgabe 6-3:)

Gegeben sei folgende horizontale Fragmentierung von Relation PROJEKT:

PROJEKT₁ = _{PROBUDGET < 100000} (PROJEKT)
PROJEKT₂ = _{100000 PROBUDGET 800000} (PROJEKT)
PROJEKT₃ = _{PROBUDGET > 800000} (PROJEKT).

Für PMITARBEIT liege eine abhängige horizontale Fragmentierung vor:

PMITARBEIT₁ = PMITARBEIT PROJEKT₁
PMITARBEIT₂ = PMITARBEIT PROJEKT₂
PMITARBEIT₃ = PMITARBEIT PROJEKT₃.

Bestimmen Sie für die Anfrage

SELECT PNR
FROM PROJEKT PT, PMITARBEIT PM
WHERE DAUER > 10 AND PROBUDGET > 1000000
AND PT.PRONR=PM.PRONR

zunächst den initialen Fragment-Ausdruck. Nehmen Sie algebraische Optimierungen zur weitestgehenden Reduzierung des Ausdrucks vor. (Lösung Aufgabe 6-4:)

Relation PERSONAL sei folgendermaßen fragmentiert:

PERSONAL₁ = _{PNR, PNAME} (_{PNR < 20000} (PERSONAL))
PERSONAL₂ = _{PNR, BERUF, GEHALT} (_{PNR < 20000} (PERSONAL))
PERSONAL₃ = _{PNR 20000} (PERSONAL).

Bestimmen Sie für die Anfrage

SELECT PNAME
FROM PERSONAL
WHERE PNR=4711

zunächst den initialen Fragment-Ausdruck. Nehmen Sie algebraische Optimierungen zur weitestgehenden Reduzierung des Ausdrucks vor. (Lösung Aufgabe 6-5:)

Sei Card (R) = 10000, Card (S) = 1000, JSF (RS) = 0.001. Jede Relation soll 5 Attribute umfassen. Welche Kommunikationskosten ergeben sich für "Ship Whole" bzw. "Fetch as needed" bei Join-Ausführung an K_R bzw. an K_S ? (Lösung Aufgabe 6-6:)

Auf den Relationen PERSONAL und PMITARBEIT sei folgende Join-Query zu bearbeiten:

SELECT P.PNR, PNAME, BERUF, PRONR, DAUER
FROM PERSONAL P, PMITARBEIT PM
WHERE P.PNR=PM.PNR AND P.GEHALT > 60000

Es gelte Card (PERSONAL) = 1000, Card (PMITARBEIT) = 1500; beide Relationen seien an verschiedenen Knoten gespeichert. Die Anfrage soll an einem dritten Knoten K initiiert werden; das Ergebnis ist dort auch auszugeben. Die Gehaltsbedingung soll von 20% der Angestellten erfüllt werden (SF=0.2); 25% der Angestellten sollen in keinem Projekt mitarbeiten.

Bestimmen Sie die Kommunikationskosten (#Nachrichten, #AW) für folgende Join-Strategien:

• Ship-Whole; Join-Berechnung an Knoten K_PMITARBEIT

• Ship-Whole; Join-Berechnung an Knoten K

• Semi-Join; Join-Bestimmung an Knoten K_PERSONAL

• Semi-Join; Join-Berechnung an Knoten K

• Bitvektor-Join; Join-Berechnung an Knoten K

Vor der Übertragung sollen alle anwendbaren Selektionen und Projektionen durchgeführt werden. Die Länge des Bitvektors soll 5 Attributwerten entsprechen; durch Anwendung des Bitvektors soll sich die zurückzuliefernde Tupelanzahl um 5% erhöhen. (Lösung Aufgabe 6-7:)

Wie kann der Übertragungsumfang der in Kap. 6.5.2 vorgestellten Strategie mit zwei Semi-Joins und Join-Berechnung an Knoten K verbessert werden? Hinweis: Reduzieren Sie die Anzahl der Join-Attributwerte, die zwischen den Datenknoten K_R und K_S verschickt werden.

a) Geben Sie alle Einzelschritte an.

b) Wie reduziert sich der Übertragungsumfang für Beispiel 6-10.

(Lösung Aufgabe 6-8:)

Bestimmen Sie für folgende Query

SELECT *
FROM PERSONAL P, PROJEKT PT, PMITARBEIT PM
WHERE P.PNR=PM.PNR AND PT.PRONR=PM.PRONR
AND BERUF="Programmierer".

die Kommunikationskosten für Ship-Whole und Semi-Join-Berechnung mit vollständiger Reduzierung. Jede der drei Relationen sei an einem separaten Knoten gespeichert. Ferner sei Card (PERSONAL) = 1000, Card (PMITARBEIT) = 1500; Card (PROJEKT) = 200. Die Anfrage soll an Knoten K_PERSONAL initiiert werden; das Ergebnis ist dort auch auszugeben. Die Berufsbedingung soll von 10% der Angestellten erfüllt werden (SF=0.1); 25% der Angestellten sollen in keinem Projekt mitarbeiten. (Lösung Aufgabe 6-9:)