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

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 金贝棋牌 wiederzuverwenden).
Die Kombination dieser zwei klassischen und etablierten Forschungsbereiche führt zu vielen innovativen und anspruchsvollen Forschungsfragen, von sowohl theoretischer als auch praktischer Relevanz.