Decompose and Conquer: Fast Query Processing via Decomposition

Datenbanken sind eine zentrale Komponente in praktisch allen Computer-Anwendungen. Dabei werden die Anforderungen immer höher: sowohl was die immer größeren Datenmengen betrifft als auch immer komplexere Anfragen. Heutige Datenbanken stoßen dabei an ihre Grenzen. So wurde in aktuellen Untersuchungen gezeigt, dass bereits mittelgroße Anfragen mit mehreren Tabellen erhebliche Schwierigkeiten bereiten können. Eine wesentliche Schwäche der heutigen Datenbanktechnologie ist, dass die innere Struktur der Anfragen bei der Bearbeitung nicht ausreichend berücksichtigt wird.

Ein völlig anderer Ansatz zur Beantwortung von Anfragen basiert auf einem berühmten Resultat von Yannakakis, dass sogenannte azylische Anfragen sehr effizient bearbeitet werden können. Dieses Ergebnis wurde in der Folge mit Hilfe von Anfragezerlegungen verallgemeinert. Die Schwäche von diesem Ansatz ist allerdings, dass er zwar die Struktur der Anfrage genau analysiert, jedoch keine (strukturellen und statistischen) Informationen über die Daten berücksichtigt.

Das Ziel in diesem Projekt ist es, diese zwei bislang unabhängigen Ansätze zu vereinen. Und zwar sollen einerseits die Anfrageoptimierungsmethoden der heutigen Datenbanken in die Anfragezerlegung einfließen und andererseits Anfragezerlegungen in die aktuelle Datenbankarchitektur integriert werden. Auf diese Weise soll eine neue Generation von Datenbanktechnologie entstehen, die sowohl mit großen Datenmengen als auch mit großen Anfragen zurechtkommt.