Evaluierung von Anfragen für SLP-komprimierte Bäume, Graphen und relationale Daten

• Antragsteller: Dr. Markus Schmid
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 522576760

Das Forschungsfeld der Algorithmen für komprimierte Zeichenketten (Strings) befasst sich mit Algorithmen zum Lösen fundamentaler String-Probleme direkt auf komprimierten Strings als Eingabe (wobei sogenannte "straight-line programs" (SLPs) das gängigste Kompressionsschema darstellen). In diesem Forschungsprojekt möchte ich dieses Szenario mit der Evaluierung von Datenbankanfragen (wie in der Datenbanktheorie untersucht) verbinden: Wir betrachten eine Klasse von Datenbanken (relationale Datenbanken, Dokumente, Graphdatenbanken, etc.) und eine Klasse von Anfragen für solche Datenbanken (relationale Algebra für relationale Daten, Pfadanfragen für Graphdatenbanken, "document spanners" für Dokumente, etc.), und betrachten dann das Problem, eine gegebenen Anfrage für eine gegebene Datenbank zu evaluieren. Die Besonderheiten der Evaluierung von Datenbankanfragen -- die normalerweise nicht zum Fokus des Gebiets der Algorithmen für komprimierte Zeichenketten gehören -- sind Aufzählalgorithmen (anstatt des Lösens eines Entscheidungsproblems interessieren wir uns dafür alle Elemente der Lösungsmenge aufzuzählen, mit beweisbaren oberen Laufzeitschranken für eine Vorverarbeitungsphase und der Verzögerung ("delay") beim Aufzählen), das Komplexitätsmaß der Datenkomplexität (wir betrachten die Anfragen als vernachlässigbar klein im Vergleich zu den Daten, und messen die Laufzeit daher ausschließlich in der Größe der Daten), das dynamische Setting (wir nehmen an, dass wir mit nur einer Datenbank arbeiten, die durch Anwendung geeigneter Updates verändert werden kann, und unsere Algorithmen sollen speziell auf dieses Szenario zugeschnitten sein, d.h. anstatt jede kleine Veränderung der Datenbank als neue Probleminstanz aufzufassen, interessieren wir uns dafür wie wir bereits berechnete Informationen wiederverwenden können). Wir wollen das Prinzip der Algorithmik für SLP-komprimierte Eingaben mit der Evaluierung von Datenbankanfragen verbinden (mit dem Fokus auf Aufzählalgorithmen, Datenkomplexität und dem dynamischen setting), und somit die Evaluierung von Anfragen für SLP-komprimierte Bäume, Graphen und relationale Daten untersuchen. Dies wird zu vielen anspruchsvollen Forschungsfragen von sowohl theoretischer als auch praktischer Relevanz führen.

• DFG-Verfahren: Sachbeihilfen