Die Weihnachtsübung zu Grundlagen: Datenbanken
Transcrição
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: