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

压缩字符串的算法领域涉及直接在压缩字符串上解决基本字符串问题的算法(其中所谓的直线程序(简称SLP)是最常见的压缩方案)。在这个研究项目中，我们希望将这种设置与数据库理论中典型的查询评估框架相结合：我们考虑一类可能的数据库(关系数据库、文档、数据图等)。以及此类数据库的一类查询(关系代数(用于关系数据)、路径查询(用于数据图)、文档拼接器(用于文档)等)，并且感兴趣的计算问题是评估给定数据库上的给定查询。查询评估的特殊功能通常不在压缩字符串的算法的重点中，它们是枚举(即，不是解决决策问题，我们希望枚举具有预处理时间和延迟界限的解集的所有元素)、数据复杂性度量(假设查询与数据相比可以忽略不计，因此我们仅根据数据大小来度量运行时间)、动态设置(我们假设我们使用的是一个数据库，该数据库-通过适当的更新-随着时间的推移而略有变化，并且我们的算法应该利用这种场景，即，我们不是把数据库的每一个小变化都当作一个新的问题实例，而是寻找利用已经预先计算的信息的方法)。我们希望将SLP压缩字符串的算法原理与查询求值范式(重点关注枚举、数据复杂性和动态设置)相结合，从而研究SLP压缩的树、图和关系数据上的查询求值。我们认为，这导致了许多具有实践和理论意义的具有挑战性的研究问题。

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.