Effizientes Aufz?hlen der Ergebnisse von Pfadanfragen bei Graphdatenbanken

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.