Evaluierung von Anfragen für SLP-komprimierte Bäume, Graphen und relationale Daten
Projektbeschreibung
Das Forschungsfeld der Algorithmik auf komprimierten Strings (SLP-Algorithmik) befasst sich mit Algorithmen, welche grundlegende Stringprobleme direkt auf komprimierten Eingaben lösen (wobei sogenannte "straight-line programs" (SLPs) das gängigste Kompressionsschema darstellen).
In diesem Forschungsprojekt wollen wir das Gebiet der SLP-Algorithmik mit dem Gebiet der Anfrageevaluierung aus der Datenbanktheorie verbinden. Bei letzterem betrachten wir eine Klasse an Datenbanken (bspw. relationale Datenbanken, Dokumente, Datengraphen, etc.) und eine Klasse von Anfragen (relationale Algebra (für relationale Daten), Pfadanfragen (für Datengraphen), "document spanners" (für Dokumente)), und das für uns relevante Berechnungsproblem besteht darin, eine gegebene Anfrage über einer gegebenen Datenbank auszuwerten.
Spezielle Aspekte der Anfrageevaluierung die im Kontext der SLP-Algorithmik nicht im Fokus stehen sind Aufzählalgorithmen (d.h. anstatt Entscheidungsprobleme zu lösen, sind wir daran interessiert, alle Elemente der Lösungsmenge aufzuzählen, mit beweisbaren Laufzeitgarantien für Vorverarbeitung und "delay"), die Datenkomplexitätssichtweise (Anfragen werden im Vergleich zur Größe der Daten als vernachlässigbar klein angesehen; wir messen die Laufzeit daher nur in Abhängigkeit der Daten), und die dynamische Sichtweise (wir arbeiten mit einer Datenbank, die durch geeignete "updates" verändert werden kann, und unsere Algorithmen sollen dieses Szenario ausnutzen, d.h., anstatt jede minimal veränderte Version der Datenbank als komplett neue Instanz zu betrachten, sind wir daran interessiert, zuvor berechnete Informationen wiederzuverwenden).
Die Kombination dieser zwei klassischen und etablierten Forschungsbereiche führt zu vielen innovativen und anspruchsvollen Forschungsfragen, von sowohl theoretischer als auch praktischer Relevanz.
Projektleitung
Beteiligte Organisationseinheiten der HU
Mittelgeber
DFG Eigene Stelle (Sachbeihilfe)
Laufzeit
Projektstart: 12/2023
Projektende: 11/2026
