Die Weihnachtsübung zu Grundlagen: Datenbanken

Die Weihnachtsübung zu Grundlagen:
Datenbanken
Chaoran Chen
[email protected]
22.12 - 11.01.2015
Hausaufgabe 1
Die folgende Abbildung zeigt einen Festplattenverbund
bestehend aus vier Laufwerken, auf welchen die Datenblöcke A
bis I gespeichert sind. Die Blöcke P enthalten
Paritätsinformationen.
1. Um welches RAID-Level handelt es sich?
2. Wie viele Festplatten können ausfallen, ohne dass mit
Datenverlust zu rechnen ist? Geben Sie eine allgemeine
Lösung für einen Verbund bestehend aus n Festplatten an.
3. Kann die Ausfallsicherheit erhöht werden? Begründung?
Hausaufgabe 1
4. Welchen weiteren Vorteil bietet das gezeigte
RAID-System neben der Ausfallsicherheit?
5. Nach einem Festplattendefekt, enthalten die Datenblöcke
die folgenden Binärdaten. Rekonstruieren Sie die
Datenblöcke der Disk2 mithilfe der XOR-Verknüpfung.
Hausaufgabe 2
1. Was ist ein Equi-Join?
2. Was spricht gegen die Verwendung des
Hashjoin-Verfahrens bei einem Join, der etwa ein <“
”
-Zeichen im Prädikat enthält?
Hausaufgabe 2
3. Gegeben die Relation Profs = {PersNr , Name} und
Raeume = {PersNr , RaumNr },
3.1 Skizzieren Sie eine geschickte Möglichkeit, den Equi-Join
Profs Raeume durchzuführen.
3.2 Wieso ist dies hier angenehm“ durchführbar?
”
3.3 In welchem Fall wäre selbst ein Ausdruck wie
Profs o
nProfs.PersNr <Raeume.PersNr Raeume angenehm
durchführbar?
4. Der Student Maier hat einen Algorithmus gefunden, der
den Ausdruck A × B in einer Laufzeit von O(| A |)
materialisiert. Was sagen Sie Herrn Maier?
Hausaufgabe 3
Werten Sie den Join R o
nR.A=S.B S mithilfe des Nested-Loopsowie des Sort/Merge-Algorithmus aus. Machen Sie deutlich,
in welcher Reihenfolge die Tupel der beiden Relationen
verglichen werden und kennzeichnen Sie die Tupel, die in die
Ergebnismenge übernommen werden. Vorvollständigen Sie
hierzu die beiden folgenden Tabellen:
Anfragebearbeitung
Physische Optimierung
Implementierung Join
• Mengendifferenz und -durchschnitt können analog zum Join
implementiert werden
• hier nur Equi-Joins
Nested-Loop-Join:
for each r ∈ R
for each s ∈ S
if r .A = s.B then
res := res ∪ (r s)
20 / 49
Anfragebearbeitung
Physische Optimierung
(Sort-)Merge-Join(2)
iterator MergeJoinp
• open
I
I
I
Öffne beide Eingaben
Setze akt auf linke Eingabe
Markiere rechte Eingabe
• close
I Schließe beide Eingabequellen
24 / 49
Anfragebearbeitung
Physische Optimierung
(Sort-)Merge-Join(3)
iterator MergeJoinp
• next
I
Solange Bedingung nicht erfüllt
I
I
I
I
I
I
Setze akt auf Eingabe mit dem kleinsten anliegenden Wert im
Joinattribut
Rufe next auf akt auf
Markiere andere Eingabe
Verbinde linkes und rechtes Tupel
Bewege andere Eingabe vor
Ist Bedingung nicht mehr erfüllt oder andere Eingabe erschöpft?
I
I
Bewege akt vor
Wert des Joinattributes in akt verändert?
⇒ Nein, dann setze andere Eingabe auf Markierung zurück
⇒ Ansonsten markiere die andere Eingabe
25 / 49
Hausaufgabe 3
Werten Sie den Join R o
nR.A=S.B S mithilfe des Nested-Loopsowie des Sort/Merge-Algorithmus aus. Machen Sie deutlich,
in welcher Reihenfolge die Tupel der beiden Relationen
verglichen werden und kennzeichnen Sie die Tupel, die in die
Ergebnismenge übernommen werden. Vorvollständigen Sie
hierzu die beiden folgenden Tabellen: