dbs2.textile

Datenbanksysteme II

Physische Speicherstrukturen

Die 5-Schichten Architektur

• Satzorientiert – mengenorientiert (impedance mismatch)

Probleme mit Megatron 2002

• Hintergründe zu jedem Problem, was muss ein DBMS alles beachten
• u.a. Nebenläufigkeit, Anfragekontrolle, Puffermanagement (Seiten, Caching, Verdrängungsstrategien, Puffermanager)

interne Speicherstrukturen

• verschiedene Geschwindigkeiten und Preise
• Puffer

Disks

• Aufbau von Festplatten
• Algorithmus evaluieren können an Hand von Metriken, wie Latenzzeit & Seektime

TPMMS

• Aufwandsabschätzung begründen können
• 3x Anzahl Blöcke (Einlesen, sortierte Teillisten Zwischenspeichern, Teillisten wieder einlesen)
• Berechnungsgrenzen (Speichermenge vorgegeben, Größe der Datei angeben können)
• mehrere Phasen MMS erklären können

Zugriffsbeschleunigung

• keine Seektime benötigt in Algorithmen, wie kann man solche Situationen herstellen
• zB. effizientes Ablegen von Daten über mehrere Disks verteilt (Zylinder) => gleichzeitiges Auslesen, unabhängige S-/L-Köpfe
• mehrere Disks, Spiegelung, Elevator Algorithmus (Minimierung der durchschnittlichen Seektime), Prefetching

Raid

• welche Arten von Raidverfahren gibt es (nur Tabellenkopf in Folie 81)
• diese erklären können

Repräsentation

• Typen von Daten, Recordheader, Seitenheader, Aufbau von records

Indexstruktur

Indizes auf sequentiellen Dateien

• dichtbesetzt, dünnbesetzt, mehrstufig
• Benutzung von Indizes soll klar sein (Wieviele Blöcke müssen gelesen werden für “WHERE i > 20”)

Sekundärindizes

• Indirektion, Invertierter Index
• Suchen im Index: binäre Suche, Hash, mehrstufiger Index
• warum lohnt sich eine Indirektion: Pointer reichen schon für Join/Schnittmenge/Vereinigunge/disjunkte Abfrage
• invertierter Index: in der Regel bei Texten verwendet, Speichere ein “Wort” und Liste alle dazugehöriger Werte

B+-Bäume

• dicht- oder dünnbesetzt (Pointer auf einzelne Tupel oder auf Seiten)
• Eigenschaften von Wurzeln, Knoten, Blätter
• warum werden Füllgrade verlangt? Balancierung (maximale Grenze), Effizienz (minimale Grenze)
• durchschnittlicher Füllstand: 3/4
• wie/wann/warum kann man den Füllstand optimieren? Bsp: Daten werden nur noch rechts eingefügt (Bulk-Insert)
• günstig für Bereichsanfragen
• Einfügen, Löschen, Suchen durchführen können

Hash-Indizes

• wie vermeidet man eine feste, vorgegebene Anzahl von Buckets: erweiterbare und lineare Hashtabellen
• einfügen (zeichnen/nachmalen) können
• Hashtabelle zum Überlauf bringen

Multidimensionale Indizes

• ungeschickt: Addition und Konkatenation sind bei Bereichsanfragen, ein-Attribut Anfragen ungünstig
• besser: partitionierte Hashwerte kombinieren
• Gridfiles (einfügen und löschen und dessen Auswirkungen)

Anfrageausführung

Physische Operationen

• es werden die Anzahl von I/O und nicht Anzahl von Vergleichen gemessen
• One-Pass: nested loop join
• Two-pass: Sort- und Hash-basierte Two-Pass-Algorithmen, Index-basierte Algorithmen
• Multi-Pass
• Algorithmen sind prinzipiell gleich, Aufbau muss klar sein
• Kostenabschätzung
• Sort-Merge-Join: Eingaben müssen sortiert vorliegen
• Allgemein: wann ist sortieren sinnvoll und wann nicht

Optimierung

Kostenabschätzung

• Begründungen für die Formeln liefern können
• herleiten von Formeln
• Histogramme (Vor- und Nachteile von Histogrammen diskutieren können: Platz und Aktualisierungsaufwand vs. genauere Abschätzung)

Dynamische Programmierung

• Anfrage, Kardinalitäten werden vorgegeben => nachbauen und begründen können (kein Cross-Join)

Recovery

Fehlerarten

• DBMS hauptsächlich für Systemfehler zuständig
• Medienfehler/ Katastrophe
• Transaktionsfehler

Transaktionen

• Aufschreiben
• Undo- / Redo-Logging, Unterschiede
• zusätzlich Undo-Redo-Logging
• typische Fragen:
  • Führen Sie ein Recovery durch
  • Setzen Sie einen Checkpoint
  • Unterschied Undo (Log schreiben, auf Platte schreiben, commit) /Redo (Log schreiben, commit, auf Platte schreiben)

Web Scale Datamanagement

Inter-Query-Parallelism & Intra-Query-Parallelism

• Unterschiede bennen können
• Inter-Query-Parallelism: mehere Anfragen gleichzeitig (zB. verschiedene Server)
• Intra-Query-Parallelism: Teile einer Anfrage werden parallelisiert, Paritionierung von Daten
• Erläutern/diskutieren der Grafik (Parallel Speedup + Ahmdal’s Law ?)

Map/Reduce

• verstehen
• Anfrage der relationalen Algebra in Map/Reduce Schema übersetzen (typisch: Aggregation)
• Broadcast und Repartition Join

Transactional Processing

• CAP Theorem – Auswahl der verzichtbaren Eigenschaft für Szenario
• ACID und BASE erläutern können
• Two-Phase-Commit / Three-Phase-Commit Schritte benennen und erläutern können
• Distributed Hash Table (Chord(Kette) & CAN)
  • Idee verstehen
  • Vorteile (kürzere Routen / ausfallsicher)

SaaS & Multi-Tenancy

Pivot-Tables

• pivotisieren von Tabellen
• SQL Übersetzung von Tenantsicht auf Pivotschema

Chunk (Bonusaufgabe?)

• SQL Übersetzung von Tenantsicht auf Pivotschema

Virutalization & Load Balancing

Virtualization

• Vorteile/Nachteile

Cache Inclusion Problem

• Problem: Cache Verschwendung

Abschlussgrafik (Folie ??)

• diskutieren können, Nennen von 3 Vorteilen durch Gesamtsicht auf das System vs. Blackboxes