Big Data

Saarbrücker Forscher wollen Datenbanken ’züchten’

Saarbrücker Informatiker entwickeln einen Ansatz zur Optimierung von Datenbanken, der bisher angewendete Herangehensweisen verändern könnte – weg von handgemachten Suchmethoden hin zu automatisch erstellten. Das Team nutzt sogenannte evolutionäre Algorithmen, um die bestmöglichen Ergebnisse zu ’züchten’.

(Bild: Philipp Zapf-Schramm / SIC)

Das Team um Jens Dittrich, Professor für ’Big Data Analytics’ an der Universität des Saarlandes, befasst sich mit Daten und Datenbanken. Ob bei einfachen Suchanfragen im Internet, der Erforschung weltbewegender Ereignisse wie dem Klimawandel oder beim Einsatz und der Entwicklung von Zukunftstechnologien: Daten treiben digitale Technologie und Datenbanken helfen dabei diese Daten zu organisieren, zu speichern und zu analysieren.

Die Saarbrücker Informatiker beschäftigen sich mit sogenannten Indexstrukturen, also der Art und Weise, wie auf eine Datenbank zugegriffen wird. „Indexstrukturen sind für die Arbeit mit Datenbanken unerlässlich, denn damit lassen sich gespeicherte Daten schnell und effizient auffinden. Indexe beschleunigen die Suche enorm, da nicht mehr die gesamte Datenbank durchsucht werden muss“, erläutert Dittrich. Jeder wisse, wie etwa Bibliothekskataloge sortiert seien. „In der Informatik sind die Daten jedoch oft sehr komplex und in gigantischen Mengen vorhanden, so dass man ausgeklügeltere Methoden für das Indexieren benötigt“, so Dittrich weiter.

Indexstrukturen gut erforscht

Indexstrukturen seien in der Informatik deshalb gut erforscht, so die Wissenschaftler. Lange wurden ’von Hand’ Organisationsmethoden entwickelt, die zwar in vielen Anwendungsfällen vergleichsweise gut funktionieren, aber für keinen wirklich optimiert sind. Dittrich und sein Team haben einen Ansatz vorgestellt, mit dem sich für jede Datenbank und jeden Anwendungsfall passgenaue Indexstrukturen automatisch erzeugen lassen sollen.

Die Methode ’Genetische Generische Generierung von Indexstrukturen (GENE)‘ basiert auf sogenannten ’evolutionären Algorithmen’, einer speziellen Art der Optimierungsalgorithmen. Mit diesen wird der natürliche Prozess der Evolution emuliert. „Startpunkt ist ein ‚normaler‘, nicht optimierter Index. Von diesem werden, ähnlich wie in der Evolution, zufällige Mutationen erzeugt. Diese werden gemäß ihrer Leistungsfähigkeit sortiert und nur die besten werden in der nächsten Generation weitergeführt. Diese Schritte werden so lange wiederholt, bis sich keine nennenswerten Verbesserungen mehr zwischen den Generationen einstellen“, erklärt Dittrich.

Bisher wurden Indexstrukturen wie abgeschlossene Systeme behandelt. „Man sagte zum Beispiel, dass für manche Probleme am besten Baumstrukturen als Organisationsmethode passten, während man bei anderen besser Hashtabellen verwenden sollte. Wir aber betrachten alle bisherigen Indexstrukturen so, als hätten sie einen gemeinsamen ’Vorfahren‘“, sagt Dittrich. Das erlaubt den Forschern, diese ’Meta-Indexstruktur‘ zu mutieren und die besten Eigenschaften heute geläufiger Indexstrukturen miteinander zu kombinieren und zwar für jede Datenbank und jeden Anwendungsfall individuell optimiert. „So wollen wir für jede Datenbank eine perfekt passende und effiziente Indexstruktur ‚züchten‘, die die bisherige in der Performanz übertrifft“, erläutert Dittrich. In Vorarbeiten gelang es dem Team, gängige Indexstrukturen, die zuvor über Jahrzehnte hinweg händisch entwickelt wurden, wiederzuentdecken, also automatisch zu erzeugen oder zu replizieren.

Anwendung findet die Methode noch nicht, da es sich dabei um Grundlagenforschung handelt. Da die Menge der produzierten Daten rasant steigt, könnten zukünftig optimierte Methoden, wie die von Jens Dittrich entwickelte, diese Datenmengen schnell durchsuchen und verarbeiten.