Implementierung von Datenbanksystemen
Wintersemester 2012 / 2013 Professor Ulf Leser
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 seine Themen im Detail.
Der Halbkurs wird von einer Übung begleitet, 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 in Betriebssystemen (Pufferverwaltung, Caching). Die Übung verlangt gute Kenntnisse in C oder 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 Prüfung ist das Bestehen der Übung.
Das Modul ist anrechenbar für
- Diplomstudiengang Informatik, Halbkurs Praktische Informatik, 8SP
- 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
- Multidimensionale Indexstrukturen 1: Partitioned hashing, Grid file
- Multidimensionale Indexstrukturen 2: kd(b) Baum, R Baum
- Grundlagen der Anfragebearbeitung
- Join Methoden - Blocked Nested Loop, Sort-Merge, Hash-Join, Index-Join
- Relationale Anfrageoptimierung
- Datenbankstatistiken; Histogramme; Sampling
- Gastvortrag: Martin Grund, University of Fribourg: Technical Deep-Dive in Column-Oriented In-Memory Database
- Logging und Recovery: REDO/UNDO
- Gastvortrag: Mike Sips, GFZ Potsdam: Spatial Index Structures
- Synchronisierung von Transaktionen
- Big Data Analytics und Map/Reduce Framework
- Abschluss
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