Query Evaluation Over SLP-Compressed Trees, Graphs, and Relational Data

• Applicant: Dr. Markus Schmid
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 522576760

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). We wish to combine the principle of algorithmics on SLP-compressed strings with the paradigm of query evaluation (focussing on enumeration, data complexity and the dynamic setting); hence, investigating query evaluation over SLP-compressed trees, graphs, and relational data. We believe that this leads to many challenging research questions of both practical and theoretical relevance.

• DFG Programme: Research Grants