[dbis logo]

.Forschung.Projekte
[Institut fuer Informatik] [Leerraum] [Humboldt-Universitaet zu Berlin]

DirX-Extend

Das Projekt DirX-Extend schließt an das Projekt DirXQuE³ an. Es besteht aus den zwei Teilprojekten Index-Wizard sowie Query-Generator und Evaluierungsumgebung.

Index-Wizard

DirX ist ein Produkt der Siemens AG, welches große Mengen von hierarchischen Daten mit Hilfe von Datenbanktechnologien verwaltet. Im letzten Projekt DirXQuE³ wurde hierfür eine kostenbasierte Anfrageoptimierung und Anfrageausführung entwickelt. Ein wichtiges Kriterium für die Kostenabschätzung einer Anfrage ist dabei das Vorhandensein von Indizes, da mithilfe von Indizes eine Anfrage entscheidend schneller ausgewertet werden kann. Allerdings ist bei Veränderungen der Datenbasis auch eine aufwendige Indexpflege von Nöten. Die Herausforderung dieses Teilprojektes bestand somit darin, anhand einer gegebenen Menge von Anfragen zu entscheiden, welche Indizes die Kosten der Ausführung weiterer ähnlicher Anfragen senken.

Die erste Aufgabe des Index-Wizard besteht darin, aus den gegebenen Anfragen einer Log-Datei eine Arbeitslast (engl. Workload) zu generieren, d. h. eine weitaus geringere Menge von Anfragen, die repräsentativ für die ursprünglichen Anfragen sind. Dies ist nötig, da die Anfragen später mithilfe des Optimierers DirXQuE³ bewertet werden sollen, was für eine große Anzahl von Anfragen sehr aufwändig ist. Hierzu werden spezielle Algorithmen der Cluster­analyse benutzt, um aus mehreren Anfragen einen Repräsentanten auszuwählen.

Im zweiten Teil werden die Ausführungskosten der Anfragen des Workloads abgeschätzt. Dazu wird für jede Anfrage zunächst die Menge von Indizes bestimmt, die der Optimierer zur Ausführung benutzen könnte. Eine Schwierigkeit entsteht hierbei, falls ein solcher Index in der Datenbank nicht existiert. Dann muss er virtuell angelegt werden, d. h., es wird ein Teil der Datenbank gelesen, um Statistiken und Verteilungen der Werte dieses Indexes zu erstellen. Der Optimierer kann nun für jede Anfrage die Kosten ohne Verwendung von Indizes und mit Indizes abschätzen, ohne die Anfrage selbst auszuführen. Die dabei benutzen Indizes erhalten die Differenz aus den Kosten mit Indizes und ohne Indizes als positiven Nutzen. Für jede Update-Anfrage bekommen zu aktualisierende Indizes negativen Nutzen, da das Updaten eines Indexes Zeit in Anspruch nimmt.

Zum Schluss wird ein Ranking der Indizes bestimmt. Es wird diejenige Menge an Indizes gesucht, die die geringsten Kosten für die gegebene Menge an Anfragen erzeugt, gleichzeitig aber ein Maximum an Speicherplatz nicht überschreitet. Dieses Problem kann auf das in der Informatik bekannte NP-vollständige Rucksack-Problem zurückgeführt werden. Daher werden in der letzten Komponente schnelle Rucksack-Algorithmen mit hoher Approximation angewandt.

Query-Generator

Im zweite Teil dieses Projektes soll ein Anfragegenerator entwickelt werden. Dazu ist eine einfache Sprache zu entwerfen, die es erlaubt Anfragemuster zu spezifizieren und den Generierungsprozess damit zu leiten. Hinzu kommt die Eingabe von Datensätzen, um sinnvolle Anfragen zu generieren, d. h. solche, die auch Ergebnisse zurückliefern.

Projektpartner

  • Siemens Aktiengesellschaft, Berlin und München, Bereich Com ESY SEC DI
  • Humboldt-Innovation GmbH; Prof. Johann-Christoph Freytag, Institut für Informatik


[Punkt]  DFG-Forschergruppe Stratosphere

[Punkt]  DFG-Graduate School SOAMED

[Punkt]  DFG-Graduate School METRIK

[Punkt]  Verweisbasierte Anfrageausführung

[Punkt]  Web of Trusted Data

[Punkt]  Query Optimization in RDF Databases

[Punkt]  DBnovo - Datenbankgestützte Online Sequenzierung



Ansprechpartner

+49 30 2093-3016

+49 30 2093-3944