Evaluierung von Anfragen für SLP-komprimierte Bäume, Graphen und relationale Daten
Deutsche 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.
Englische Projektbeschreibung
The field of algorithmics on compressed strings is concerned with algorithms that solve
fundamental string problems directly on compressed strings (where so-called straight-line programs
(SLPs, for short) are the most common compression scheme). In this research
project, we want to combine this setting with the query evaluation framework as typically investigated
in database theory: we consider a class of possible databases (relational databases, documents, data
graphs, etc.) and a class of queries for such databases (relational algebra (for relational data), path
queries (for data graphs), document spanners (for documents), etc.), and the computational problem
of interest is to evaluate a given query over a given database.
The special features of query evaluation that are usually not in the focus of algorithmics on
compressed strings are enumeration (i. e., instead of solving decision problems, we want to enumerate
all elements of the solution set with bounds on the preprocessing time and the delay), the data
complexity measure (the queries are assumed to be negligibly small compared to the data, and we
therefore measure running times only in terms of the data size), the dynamic setting (we assume
that we work with one database that – by suitable updates – slightly changes over time, and our
algorithms should exploit this scenario, i. e., instead of treating every small change to the database as
a new problem instance, we look for ways of making use of already pre-computed information).
Combining these two well-established research areas leads to many challenging research question
of both practical and theoretical relevance.
Mittelgeber
DFG Eigene Stelle (Sachbeihilfe)
Laufzeit
Projektstart: 12/2023
Projektende: 11/2026
Forschungsbereiche
Theoretische Informatik
Forschungsfelder
Datenbanktheorie, Theoretische Informatik
