Theoretische Grundlagen der effizienten Aufzählung von Anfrageergebnissen

• Antragstellerin: Professorin Dr. Nicole Schweikardt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2016 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 316451603

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.

• DFG-Verfahren: Sachbeihilfen