Detailseite
Projekt Druckansicht

Theoretische Grundlagen der effizienten Aufzählung von Anfrageergebnissen

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2016 bis 2019
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 316451603
 
Erstellungsjahr 2021

Zusammenfassung der Projektergebnisse

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. Ziel des Projekts war die Erforschung der theoretischen Grundlagen der effizienten Aufzählung von Anfrageergebnissen. Dabei haben wir uns auch der Frage gewidmet, inwieweit Datenbank-Aktualisierungen bei der effizienten Aufzählung der Anfrageergebnisse unterstützt werden können. Die Anfragesprachen, die im Fokus des Projekts standen, sind geeignete Fragmente der Logik erster Stufe oder deren Erweiterung um bestimmte Zählmechanismen. In einigen Szenarien haben wir das Augenmerk jeweils auf geeignete Klassen von Datenbanken eingeschränkt, u.a. Klassen beschränkten Grades oder so genannte nirgends-dichte Klassen (engl.: nowhere dense classes). Wir wollten 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 Schranken nachzuweisen, haben wir u.a. Methoden des noch jungen Gebiets der "feinkörnigen Komplexitätstheorie"genutzt.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung