Query Evaluation Over SLP-Compressed Trees, Graphs, and Relational Data
Abstract
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.
Principal investigators
Participating organisational units of HU Berlin
Financer
DFG Temporary Positions for Principal Investigators
Duration of project
Start date: 12/2023
End date: 11/2026
