Effizientes Aufzählen der Ergebnisse von Pfadanfragen bei Graphdatenbanken

• Antragsteller: Dr. Markus Schmid
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416776735

Das Hauptziel des beantragten Projekts ist die Entwicklung und theoretische Untersuchung von effizienten Algorithmen zum Auswerten (insbesondere dem Aufzählen der Ergebnisse) von Pfadanfragen auf Graphdatenbanken (formalisiert: endliche, gerichtete, kantenbeschriftete Graphen), sowohl im statischen (d.h. die Datenbank wird als unveränderliches Objekt betrachtet) als auch im dynamischen Fall (d.h. die Datenbank kann verändert werden, bspw. durch das Einfügen oder Löschen einzelner Datensätze). Wir konzentrieren uns dabei auf Pfadanfragesprachen, die reguläre Ausdrücke (und Varianten davon) als grundlegenden Mechanismus zum Navigieren in den Graphdatenbanken verwenden. Die Güte der Algorithmen (d.h. asympotische "worst-case" Laufzeit) wird in der "preprocessing"-Zeit und dem "delay" zwischen aufgezählten Elementen (und im dynamischen Fall in der benötigten "update"-Zeit) gemessen, bezüglich Datenkomplexität, d.h. nur in Abhängigkeit der Größe der Datenbank, wobei die Größe der Anfrage als Konstante angesehen wird. Unser Ziel ist polynomielles preprocessing mit Laufzeitpolynomen geringen Grades, konstanter delay und polylogarithmische, sublineare oder auch lineare update-Zeiten. Falls es uns für bestimmte Anfrageklassen nicht gelingen sollte, diese starken Bedingungen zu erfüllen, so versuchen wir dies mit unteren Komplexitätsschranken zu belegen (im Sinne der "fine-grained complexity}"); prinzipiell konzentrieren wir uns darauf, handhabbare (bezüglich der Effizienz der Algorithmen) Teilklassen von Anfragesprachen zu finden und dazu passende Dichotomien aufzuzeigen.Ein konzeptionelles Augenmerk wird auf der Verwendbarkeit algorithmischer Methoden der formalen Sprachen, Automatentheorie, Wortkombinatorik und String-Algorithmik liegen; an dieser Stelle sei darauf hingewiesen, dass in unserer Formalisierung Graphdatenbanken mit (nichtdeterministischen) endlichen Automaten ohne Anfangs- und Endzustände identisch sind. Die Literatur der Datenbanktheorie enthält zwar bereits grundlegende, automatenbasierte algorithmische Ansätze zur Auswertung von (auf regulären Ausdrücken basierenden) Pfadanfragesprachen, allerdings scheint sich die systematische Untersuchung dieses Zusammenhangs in einem noch rudimentären Zustand zu befinden. Insbesondere das diesbezügliche Potenzial der zahlreichen algorithmischen Techniken, kombinatorischen Erkenntnisse und Datenstrukturen, die im Bereich der String-Algorithmik erfolgreich zur Anwendung kommen, ist so gut wie nicht untersucht. Des Weiteren führt der dynamische Fall der Auswertung von Pfadanfragesprachen bei Datenbanken direkt zu Fragestellungen bezüglich nichtdeterministischen Automaten als dynamische Datenstrukturen, ein Aspekt, der in der Literatur der klassischen Automatentheorie bisher wenig Beachtung fand.

• DFG-Verfahren: Sachbeihilfen