HyperTrac:Hypergraph Zerlegung und Effiziente Lösbarkeit

Conjunctive Queries (CQs, auch als Select-From-Where Anfragen in der Datenbankanfrage- sprache SQL bekannt) sind die grundlegendste Form von Datenbankanfragen. Ebenso stellen Constraint Satisfaction Problems (CSPs) eine grundlegende Aufgabe in der Künstlichen Intelligenz dar. Für beide Probleme ist bekannt, dass sie eine hohe Komplexität haben. Daher ist die Suche nach Klassen von CQs und CSP mit niedrigerer Komplexität seit vielen Jahren ein aktives Forschungsgebiet. Ein wichtiges Werkzeug, um solche Klassen von CQs und CSPs mit niedrigerer Komplexität zu identifizieren, sind sogenannte Hypergraph Zerlegungen. Diese Techniken wurden erfolgreich zum Lösen von CSPs eingesetzt und haben mittlerweile auch in kommerziellen Datenbanksystemen Eingang gefunden. Es gibt in der Literatur mehrere Arten von Hypergraph Zerlegungen, nämlich hypertree decompositions (HDs), ihre Verallgemeinerung zu generalized hypertree decompositions (GHDs) und die noch allgemeineren fractional hypertree decompositions (FHDs). Allerdings ist die Berechnung einer geeigneten HD, GHD oder FHD selbst wiederum eine schwierige Aufgabe. Es gibt zwar Algorithmen für diese Aufgabe, aber diese funktionieren typischerweise nur für kleine Conjunctive Queries oder kleine Constraint Satisfaction Problems. In diesem Projekt werden wir das Problem der Berechnung der verschiedenen Formen von Hypergraph Zerlegungen (also HDs, GHDs, und FHDs) in Angriff nehmen und zwar sowohl aus einem theoretischen als auch aus einem praktischen Blickwinkel. Einerseits streben wir die Entwicklung von neuen Algorithimen an, die die alten in puncto Geschwindigkeit übertreffen. Und andererseits wollen wir sinnvolle Einschränkungen der CQs or CSPs finden, die noch effizientere Zerlegungsgorithmen ermöglichen.

Die Beantwortung von Benutzer-Anfragen an eine Datenbank oder das Finden von Lösungen, die bestimmte vom Benutzer angegebene Bedingungen erfüllen, sind grundlegende Probleme der Informatik. Es handelt sich dabei jedoch um nicht-triviale Probleme, und selbst moderne Computer können Schwierigkeiten haben, sie in einer akzeptablen Zeit zu lösen. Folglich wurden in der Literatur verschiedene Methoden vorgeschlagen, um ein gegebenes Problem zu zerlegen und die resultierenden Zerlegungen zu verwenden, um schneller Lösungen zu finden. Intuitiv teilen solche Zerlegungen eine komplexe Berechnungsaufgabe in kleinere, überschaubare Teilaufgaben auf. Allerdings kann auch das Finden einer guten Zerlegung selbst ein herausforderndes Problem darstellen. In diesem Projekt haben wir daher zwei Hauptrichtungen verfolgt: Erstens haben wir frühere Methoden zur Berechnung von Zerlegungen erheblich verbessert. Um dieses Ziel zu erreichen, haben wir mehrere Methoden angewandt: Einerseits haben wir parallele Algorithmen entworfen, die auf einem Cluster von Computern ausgeführt werden können. Andererseits haben wir Probleminstanzen, die in der Praxis üblicherweise vorkommen, analysiert und strukturelle Eigenschaften dieser Probleminstanzen identifiziert. Diese Eigenschaften haben wir dann genutzt, um effizientere Algorithmen zu entwerfen. Als Nebenprodukt dieser Arbeit haben wir einen Benchmark von Probleminstanzen erstellt, der auch von anderen Gruppen, die Algorithmen in diesem Bereich entwerfen, für experimentelle Auswertungen verwendet werden kann (und bereits verwendet wurde). Zweitens haben wir an schnellen Lösungsmethoden - viele davon unter Verwendung von Zerlegungen - für verschiedene Probleme in den Bereichen Datenbanken und Künstliche Intelligenz gearbeitet. Im Falle des Datenbankbereichs haben wir daher neuartige Techniken zur Abfrageauswertung und Optimierung verschiedener Abfragesprachen vorgeschlagen. Im Bereich der künstlichen Intelligenz haben wir uns mit verschiedenen Problemen aus so unterschiedlichen Bereichen wie Computational Social Choice und Reasoning befasst. Insbesondere im Bereich der Anfragebeantwortung und -optimierung hat der Einsatz von zerlegungsbasierten Methoden bislang noch nicht Eingang in industrietaugliche Programme gefunden. Dies ist zumindest teilweise darauf zurückzuführen, dass die Berechnung von Zerlegungen als schwierige und daher zeitaufwändige Aufgabe angesehen wird. Mit den in diesem Projekt erzielten Fortschritten bei der Entwicklung neuer Algorithmen (und öffentlich verfügbarer Softwaretools, die diese Algorithmen implementieren) zur Berechnung von Zerlegungen sollte dies kein Hindernis mehr darstellen. Daher wird der natürliche nächste Schritt darin bestehen, auf Zerlegungen basierende Techniken in moderne Datenbanksysteme zu integrieren.