Theoretische Grundlagen der effizienten Aufz?hlung von Anfrageergebnissen

Die effiziente Auswertung von Anfragen ist eine der zentralen Aufgaben von Datenbanksystemen. Die theoretischen Grundlagen der Anfrageauswertung beruhen auf einem engen Zusammenhang zwischen der Datenbanktheorie und der mathematischen Logik, aus deren Sicht eine relationale Datenbank einer endlichen relationalen Struktur und eine Anfrage einer Logik-Formel entspricht. Im Bereich der Logik in der Informatik und der Datenbanktheorie wurden seit 2007 eine Reihe von Ergebnissen erzielt, die sich mit der effizienten Aufz?hlung von Anfrageergebnissen besch?ftigen. Das Ziel in diesem Szenario ist, bei Eingabe einer Struktur (d.h. Datenbank) und einer Logik-Formel (d.h. Anfrage) nach einer m?glichst kurzen Vorverarbeitungsphase die Anfrageergebnisse nach und nach zu erzeugen und dabei Garantien über die maximal ben?tigte Wartezeit zwischen der Ausgabe zweier Ergebnistupel einzuhalten. Die zur Zeit bekannten diesbezüglichen Algorithmen halten gute Worst-Case- Garantien ein, haben aber die unerfreuliche Eigenschaft, dass sie auf fast allen Eingaben auch tats?chlich die Worst-Case Laufzeit aufweisen. Ziel des Projekts ist, dieses Worst-Case Verhalten zu überwinden. Wir wollen Begriffe der "Komplexit?ts-Zertifikate" und der "Instanz-Optimalit?t" finden, die für das Problem der Aufz?hlung von Anfrageergebnissen geeignet sind, und wir wollen Methoden zur Aufz?hlung von Anfrageergebnissen entwickeln, die in diesem Sinne Instanz-optimal sind. Des Weiteren wollen wir untersuchen, inwieweit Datenbank-Aktualisierungen bei der effizienten Aufz?hlung der Anfrageergebnisse unterstützt werden k?nnen.Diese Fragestellung wurde in der Literatur bisher nur wenig beachtet, so dass existierende Methoden nach erfolgter Datenbank-Aktualisierung i.d.R. die gesamte Vorverarbeitungsphase von Neuem durchlaufen müssen. Die Anfragesprachen, die wir im Rahmen des Projekts betrachten wollen, sind geeignete Fragmente der Logik erster Stufe oder der monadischen Logik zweiter Stufe. Bei Bedarf werden wir das Augenmerk jeweils auf geeignete Klassen von Datenbanken einschr?nken, u.a. Klassen beschr?nkten Grades oder beschr?nkter Expansion. Wir wollen jeweils die "Grenzen der Machbarkeit" identifizieren, also bei gegebener Klasse von Strukturen m?glichst gro?e Logik-Fragmente und bei gegebener Logik m?glichst gro?e Strukturklassen finden, für die eine effiziente Aufz?hlung der Anfrageergebnisse m?glich ist. Um untere Schanken nachzuweisen, werden wir u.a. Methoden des noch jungen Gebiets der "feink?rnigen Komplexit?tstheorie" nutzen.