Hasso-Plattner-Institut
Prof. Dr. Emmanuel Müller
 

Beschreibung

Der Schwerpunkt der Vorlesung „Indexing Structures for Efficient Database Access“ liegt auf Datenstrukturen für den effizienten Datenzugriff in großen Datenbanken. Die Vorlesung beinhaltet Datenstrukturen für eindimensionale, räumliche, hochdimensionale und metrische Daten. Es werden die grundsätzlichen Problemstellungen für einen effizienten Datenzugriff vorgestellt und algorithmische Lösungen für verschiedene Datentypen vorgestellt. 

 

Datenbanksysteme gehören zu den Grundlagen der heutigen Datenverarbeitung. Sie sind essentieller Bestandteil für die Speicherung, Analyse und Exploration von großen Datenbeständen in Forschung und Wirtschaft. Viele Anwendungen in der Genetik, im Mobilfunk oder im Web sind erst durch Datenbanksysteme ermöglicht worden. Kenntnisse über effiziente Zugriffsmethoden auf komplexe Datenbanksysteme, deren Grundlagen in verschiedenen Datenstrukturen und die effiziente Anfragebearbeitung mit intelligenten Algorithmen sind weiterführende Kenntnisse, die sich ein Informatiker zusätzlich zu seinem Allgemeinwissen über Datenbanksysteme aneignen sollte.

Diese Kenntnisse werden in der Vorlesung vermittelt. Als grundlegende Struktur der Vorlesung werden unterschiedliche Datentypen behandelt:

  • 1-dimensionale Datenräume

  • mehr-dimensionale Datenräume
  • hochdimensionale Datenräume
  • metrische Datenräume

     

Orthogonal dazu werden verschiede Anfragetypen und effiziente Algorithmen zu deren Bearbeitung behandelt. Es werden unterschiedliche Anwendungen von Indexstrukturen untersucht und die Grenzen der klassischen Zugriffsmethoden aufgezeigt. Der Vergleich zwischen verschiedenen Indexstrukturen ist dabei ein essentieller Bestandteil der Vorlesung. Grundlegende Konzepte werden in unterschiedlichen Indexstrukturen eingeführt und dienen als Basis für die zukünftige Entwicklung von neuen Datenstrukturen. Die Vorlesung leistet somit auch einen Beitrag zur Softwareentwicklung und zur Analyse von großen Datenbeständen. In beiden Bereichen ist effizienter Datenzugriff eine immer wichtiger werdende Anforderung im Hinblick auf die Skalierbarkeit der Systeme.

Veranstaltungsplan

Die Vorlesung findet 1x wöchentlich im HS2 statt:

  • Montags 09:15 Uhr - 10:45 Uhr

Die Folien zur Vorlesung befinden sich jeweils vor der Vorlesung im internen Bereich oder als ZIP-Datei.

Datum Thema
MO11.04.
MO18.04.
MO    25.04.
MO02.05.fällt aus - verschoben auf 30.05. um 15:15 Uhr
MO09.05.
MO16.05.fällt aus - Pfingstmontag
MO    23.05.
MO30.05.Nachholtermin vom 02.05. im HS3 um 15:15 Uhr
MO06.06.
MO13.06.
MO20.06.Gastvortrag: Siva Ravada
(Senior Director of Spatial Development, ORACLE)
im HS3 um 15:15 Uhr
MO27.06.
MO04.07.
MO11.07.
MO18.07.Wiederholung + Fragen (Beginn ab 08:00 im HS2)
MO25.07.Klausur im HS2 von 09:15 Uhr bis 11:15 Uhr

 

Literatur

  • A.Kemper, A.Eickler: Datenbanksysteme – Eine Einführung. 6. Aufl. Oldenbourg, 2006 
  • H. Samet: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann 2006
  • C. Böhm, S. Berchtold, D. Keim: Searching in High-Dimensional Spaces: Index Structures for Improving the Performance of Multimedia Databases. ACM Computing Surveys 33(3): 322-373 (2001) 
  • Y. Manolopoulos, A. Nanopoulos, A. Papadopoulos, Y. Theodoridis: R-Trees: Theory and Applications (Advanced Information and Knowledge Processing), Springer 2012