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

对 SLP 压缩的树、图和关系数据进行查询评估

• 批准号: 522576760
• 负责人: Dr. Markus Schmid
• 金额: --
• 依托单位: Lehrstuhl Logik in der Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/522576760?language=en
• 关键词: Query; Evaluation; Over; SLP; Compressed

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.

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