Kapitel 16: Verteilte Datenbanken Flashcards
Terminologie verteilter Datenbanken
- Sammlung von Informationseinheiten, verteilt auf mehreren Rechnern, verbunden mittels Kommunikationsnetz
- Kooperation zwischen autonom arbeitenden Stationen, zur Durchführung einer globalen Aufgabe
- z.B. über LAN oder WAN
Aufbau und Entwurf eines verteilten Datenbanksystems
Fragmentierung und Allokation einer Relation
- Fragmentierung: Fragmente enthalten Daten mit gleichem Zugriffsverhalten
- Allokation: Fragmente werden den Stationen zugeordnet
- mit Replikation (redundanzfrei)
- ohne Replikation
Arten der Fragmentierung + Korrektheitsanforderung
- horizontale Fragmentierung: Zerlegung der Relation in disjunkteTupelmengen
- vertikale Fragmentierung: Zusammenfassung von Attributen mit gleichem Zugriffsmuster
- kombinierte Fragmentierung: Anwendung horizontaler und vertikaler Fragmentierung auf dieselbe Relation
- Korrektheitsanforderungen:
- Rekonstruierbarkeit
- Vollständigkeit
- Disjunktheit
Erkläre Horizontale Fragmentierung
sinnvolle Gruppierung der Professoren nach Fakultätszugehörigkeit - 3 Zerlegungsprädikate:
- p1 ≡ Fakultät = ‚Theologie‘
- p2 ≡ Fakultät = ‚Physik‘
- p3 ≡ Fakultät = ‚Philosophie‘
TheolProfs ́ := σp1∧¬p2 ∧¬ p3(Professoren) = σp1(Professoren)
PhysikProfs ́ := σ¬p1∧p2 ∧¬ p3(Professoren) = σp2(Professoren)
PhiloProfs ́ := σ¬p1∧¬p2 ∧p3(Professoren) = σp3(Professoren)
AndereProfs ́:= σ¬p1∧¬p2 ∧¬ p3(Professoren)
Beispiel Vorlesungen aus dem Universitätsschema: Zerlegung in Gruppen mit gleicher SWS-Zahl
2SWSVorls := σSWS=2 (Vorlesungen)
3SWSVorls := σSWS=3 (Vorlesungen)
4SWSVorls := σSWS=4 (Vorlesungen)
Behebung Fragmentierungsproblem bei Horizontaler Fragmentierung
Erkäre vertikale Fragmentierung und deren Probleme
Beliebige vertikale Fragmentierung gewährleistet keine Rekonstruierbarkeit 2 mögliche Ansätze, um Rekonstruierbarkeit zu garantieren:
- jedes Fragment enthält den Primärschlüssel der Originalrelation. Aber: Verletzung der Disjunktheit
- jedem Tupel der Originalrelation wird ein eindeutiges Surrogat (= künstlich erzeugter Objektindikator) zugeordnet, welches in jedes vertikale Fragment des Tupels mit aufgenommen wird
für die Universitätsverwaltung sind PersNr, Name, Gehalt und Steuerklasse interessant:
ProfVerw := Π PersNr, Name, Gehalt, Steuerklasse (Professoren)
für Lehre und Forschung sind dagegen PersNr, Name, Rang,
Raum und Fakultät von Bedeutung:
Profs := Π PersNr, Name, Rang, Raum, Fakultät (Professoren)
Rekonstruktion der Originalrelation Professoren: Professoren = ProfVerw JOIN ProfVerw.PersNr = Profs.PersNr Profs
Welche Formen der kombinierten Fragmentierung gibt es?
Kombinierte Fragmentierung
a ) horizontale Fragmentierung nach vertikaler Fragmentierung
b ) vertikale Fragmentierung nach horizontale
Fall a)
R = R1 JOIN p (R21 ∪ R22 ∪ R23)
Fall b)
R = R1 ∪ R2 ∪ (R31 JOIN R31. κ = R32. κ R32)
Erkläre Allokation
- Dasselbe Fragment kann mehreren Stationen zugeordnet werden
- Allokation für unser Beispiel ohne Replikationen ⇒ redundanzfreie Zuordnung
SVerw –> Verwaltungsrechner –> {ProfVerw}
Erkläre Transparenz und deren Arten in verteilten DB
- Grad der Unabhängigkeit den ein VDBMS dem Benutzer beim Zugriff auf verteilte Daten vermittelt
- Verschiedene Stufen der Transparenz:
- Fragmentierungstransparenz
- Beispielanfrage, die Fragmentierungstransparenz voraussetzt:
select Titel, Name
from Vorlesungen, Professoren where gelesenVon = PersNr;
Beispiel für eine Änderungsoperation, die Fragmentierungs- transparenz voraussetzt:
update Professoren
set Fakultät = ‚Theologie‘
where Name = ‚Sokrates‘;
* Ändern des Attributwertes von Fakultät
Transferieren des Sokrates-Tupels aus Fragment PhiloProfs in das Fragment TheolProfs (= Löschen aus PhiloProfs, Einfügen in TheolProfs)
Ändern der abgeleiteten Fragmentierung von Vorlesungen (= Einfügen der von Sokrates gehaltenen Vorlesungen in
TheolVorls, Löschen der von ihm gehaltenen Vorlesungen aus PhiloVorls)
- Allokationstransparenz
- Benutzer müssen Fragmentierung kennen, aber nicht den „Aufenthaltsort“ eines Fragments
Beispielanfrage:
select Gehalt
from ProfVerw
where Name = ‚Sokrates‘;
* unter Umständen muss Originalrelation rekonstruiert werden
Beispiel:
Verwaltung möchte wissen, wieviel die C4-Professoren der Theologie insgesamt verdienen
da Fragmentierungstransparenz fehlt muss die Anfrage folgendermaßen formuliert werden:
select sum (Gehalt) from ProfVerw, TheolProfs where ProfVerw.PersNr = TheolProfs.PersNr and
Rang = ‚C4‘;
- Lokale Schema-Transparenz
- Der Benutzer muss auch noch den Rechner kennen, auf dem ein Fragment liegt.
Beispielanfrage:
select Name
from TheolProfs at STheol where Rang = ‚C3‘;
* Ist überhaupt Transparenz gegeben?
Lokale Schema-Transparenz setzt voraus, dass alle Rechner dasselbe Datenmodell und dieselbe Anfragesprache verwenden.
⇒ vorherige Anfrage kann somit analog auch an Station SPhilo ausgeführt werden
Dies ist nicht möglich bei Kopplung unterschiedlicher DBMS.
Verwendung grundsätzlich verschiedener Datenmodelle auf lokalen DBMS nennt man „Multi-Database-Systems“ (oft unumgänglich in „realer“ Welt).
Anfragebearbeitung bei horizontaler Fragmentierung
Übersetzung einer SQL-Anfrage auf dem globalen Schema in eine äquivalente Anfrage auf den Fragmenten benötigt 2 Schritte:
- Rekonstruktion aller in der Anfrage vorkommenden globalen Relationen aus den Fragmenten, in die sie während der Fragmentierungsphase zerlegt wurden. Hierfür erhält man einen algebraischen Ausdruck.
- Kombination des Rekonstruktionsausdrucks mit dem algebraischen Anfrageausdruck, der sich aus der Übersetzung der SQL-Anfrage ergibt
Wie könnte eine Optimierung der horizontalen Fragmentierung aussehen?
Anfrageoptimierung bei vertikaler Fragmentierung:
Beispiel:
select Name, Gehalt from Professoren where Gehalt > 80000;
Rolle von JOIN Auswertung bei VDBMS und Möglichkeiten?
- spielt kritischere Rolle als in zentralisierten Datenbanken Problem: Argumente eines Joins zweier Relationen können auf
- unterschiedlichen Stationen des VDBMS liegen
- Betrachtung des allgemeinsten Falles:
- äußere Argumentrelation R ist auf Station StR gespeichert
innere Argumentrelation S ist dem Knoten StS zugeordnet
Ergebnis der Joinberechnung wird auf einem dritten Knoten StResult benötigt
* Mit Filter z.B. Bloom Filter und Hash-Filter
* Ohne Filterung:
* Nested-Loops
* Transfer einer Argumentrelation
* Transfer beider Argumentrelationen
Wie sieht Transaktionskontrolle in VDBMS aus?
- Transaktionen können sich bei VDBMS über mehrere Rechnerknoten erstrecken
- ⇒ Recovery:
- Redo: Wenn eine Station nach einem Fehler wieder anläuft, müssen alle Änderungen einmal abgeschlossener Transaktionen - seien sie lokal auf dieser Station oder global über mehrere Stationen ausgeführt worden - auf den an dieser Station abgelegten Daten wiederhergestellt werden.
- Undo: Die Änderungen noch nicht abgeschlossener lokaler und globaler Transaktionen müssen auf den an der abgestürzten Station vorliegenden Daten rückgängig gemacht werden.
Wie kann das EOT-Problem gelöst werden?
2 Phaen Commit Protokoll:
→ gewährleistet die Atomarität der EOT-Behandlung
- das 2PC-Verfahren wird von sog. Koordinator K
- überwacht
- gewährleistet, dass die n Agenten (=Stationen im VDBMS) A1,…An, die an einer Transaktion beteiligt waren, entweder alle von Transaktion T geänderten Daten festschreiben oder alle Änderungen von T rückgängig machen
Zustandsübergang beim 2PC-Protokoll für Koordinator:
Zustandsübergang beim 2PC-Protokoll für Agenten:
Gehen Sie von folgender kombinierter Fragmentierung der in Abbildung 1 dargestellten Relation Professoren aus:
- Zuerst erfolgt eine vertikale Fragmentierung in
ProfVerw := ΠPersNr, Name, Gehalt, Steuerklasse(Professoren)
Profs := ΠPersNr, Name, Rang, Raum, Fakultät(Professoren)
- Das Fragment Profs wird weiter horizontal fragmentiert in
TheolProfs := σ Fakultät = ’Theologie’(Profs)
PhysikProfs := σ Fakultät = ’Physik’(Profs)
PhiloProfs := σ Fakultät = ’Philosophie’(Profs)
Übersetzen Sie aufbauend auf dieser Fragmentierung die folgende SQL-Anfrage in die kanonische Form.
select Name , Gehalt Rang from Professoren
where Gehalt > 80000;
Optimieren Sie diesen kanonischen Auswertungsplan durch Anwendung algebraischer Trans- formationsregeln (Äquivalenzen).
Überlegen Sie sich, welche Tupel bei der Anwendung des bloomfilterbasierten Joins in Abbildung 1 übertragen werden. Markieren Sie insbesondere, welche Tupel übertragen werden, obwohl sie keinen Joinpartner finden (sog. false drops). Wie kann die Anzahl dieser false drops verringert werden? Welche Eigenschaften sollte die Hashfunktion h(c) die bei dieser Joinbearbeitung verwendet wird erfüllen?
- False Drops sind c7 und c8 die übertragen werden, obwohl sie keinen Joinpartner finden.
- Bei sinnvoller Hashfunktion weniger False Drops je größer der Vektor ist. Gute Hashfunktion! Mehrere Hashfunktionen zu benutzen verbessert auch die Effizienz des Bloomfilters
- Hashfunktion sollte möglichst gleichmäßig verteilen.
Zeigen Sie, dass die Suche in einem Chord-Overlaynetzwerk durch die Nutzung der Fin- gerTabellen in maximal logarithmisch vielen Schritten zur Gro ̈ße des Zahlenrings (bzw. der Anzahl der Stationen) durchgefu ̈hrt werden kann. Verwenden Sie die Suche nach K57 beginnend an Station P11 (siehe Abbildung 1) zur Illustration.
FingerTAbellen P3, P14, P26.
Log: Anhand Abbildung Größe 2^n. Nach log |P| sprüngen ist man wegen der Halbierung der Distanz bei jedem Sprung in einem Abstand von 2^n / |P| zum Peer p. P = Anzahl an Peers
