Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Diese Modul vermittelt einen Überblick über Techniken zur Implementierung von (relationalen) Datenbanksystemen. Es behandelt dazu ausgewählte Themen aus allen Ebenen eines DBMS, angefangen bei Satz- und Tabellenverwaltung über (multidimensionale) Indexstrukturen zur Anfrageoptimierung und zum Transaktionsmanagement. Das Modul ist systemnah und behandelt Themen im Detail.

Das Modul beinhaltet auch eine Übung, in der verschiedene Komponenten eines DBMS implementiert werden.

Voraussetzungen

Voraussetzung für den Besuch sind gute Kenntnisse in Algorithmen (Sortieren, Suchen, Baumsuchverfahren), relationalen Datenbanken (SQL, Transaktionen, Schemaentwurf) und Betriebssystemen (Pufferverwaltung, Caching). Die Übung verlangt gute Kenntnisse in C++.

Prüfungen und Anrechenbarkeit

Je nach Teilnehmerzahl sind Prüfungen mündlich oder schriftlich. Die Prüfungsform wird in der ersten Semesterwoche bekannt gegeben. Voraussetzung für die Anmeldung zur Prüfung ist das Bestehen der Übung.

Das Modul ist anrechenbar für

• Master Informatik, 10 SP
• Master Wirtschaftsinformatik, 10 SP

Literatur

• Saake, Heuer, Sattler: "Datenbanken: Implementierungstechniken", MTP Verlag, 2. Auflage, 2005
• Garcia-Molina, Ullman, Widom: “Database System Implementation”, Prentice Hall, 2000
• Weitere Literatur und Links

Themen und Folien

Folien sind hier jeweils nach der Vorlesung als PDF verfügbar. Änderungen möglich. All slides are English, but the course will be held in German.

• Einleitung und Motivation
• Architektur von Datenbanksystemen; Übersicht über die Vorlesungsthemen
• Sekundärspeicher; RAID
• Records und Blöcke
• Caching
• Dateiformate, Indexing
• Extensible and linear Hashing
• B, B+ and Prefix Trees
• Index structures for modern hardware: Cache-Sensitive Skip Lists
• Multidimensionale Indexstrukturen 1: Partitioned hashing, Grid file
• Multidimensionale Indexstrukturen 2: kd(b) Baum, R Baum
• MDIS on modern hardware; the Bubble-Bucket Tree
• Grundlagen der Anfragebearbeitung
• Join Methoden - Blocked Nested Loop, Sort-Merge, Hash-Join, Index-Join
• Set Containment Joins mit PRETTI, PieJoin, und LIMIT+
• Relationale Anfrageoptimierung
• Datenbankstatistiken; Histogramme; Sampling
• Logging und Recovery: REDO/UNDO
• Synchronisierung von Transaktionen
• Abschluss (no slides)

Weitere Materialien und Literatur

• Kemper, Eickel: “Datenbanksysteme – Eine Einführung”, Oldenburg, 5. Auflage 2004
• Härder, Rahm: “Datenbanksysteme. Konzepte und Techniken der Implementierung”, Springer, 2. Auflage 2001
• J. Gray, A. Reuter: Transaction Processing, Morgan Kaufman, San Francisco, USA, 1992