论文标题
对低度的结构的动态查询评估
Dynamic Query Evaluation Over Structures with Low Degree
论文作者
论文摘要
我们考虑对具有有限程度和低度的数据库类别的一阶查询进行评估。更确切地说，给定查询和数据库，我们希望有效测试是否有解决方案，计算有多少解决方案或能够列举所有解决方案的集合。 有限程度和低度是自然的概念，两者都产生有效的算法。例如，Berkholz，Keppeler和Schweikardt在2017年表明，在有限度的数据库中，不仅可以有效地测试，计数和枚举任何一阶查询，而且当数据库本身更新时，可以更新所使用的数据结构。 本文将现有的结果扩展到两个方向。首先，我们表明，在具有低度的数据库中，有一个数据结构，使我们能够测试，计数和列举一阶查询的解决方案。当数据库更新时，该数据结构也可以有效地重新计算。其次，对于具有有限程度的数据库类别的类别，我们表明，在不增加预处理时间的情况下，我们可以计算一个数据结构，该数据结构不取决于查询，而仅取决于其量词等级。因此，我们可以执行单个预处理，以后可以用于许多查询。
We consider the evaluation of first-order queries over classes of databases that have bounded degree and low degree. More precisely, given a query and a database, we want to efficiently test whether there is a solution, count how many solutions there are, or be able to enumerate the set of all solutions. Bounded and low degree are rather natural notions and both yield efficient algorithms. For example, Berkholz, Keppeler, and Schweikardt showed in 2017 that over databases of bounded degree, not only any first order query can efficiently be tested, counted and enumerated, but the data structure used can be updated when the database itself is updated. This paper extends existing results in two directions. First, we show that over classes of databases with low degree, there is a data structure that enables us to test, count and enumerate the solutions of first order queries. This data structure can also be efficiently recomputed when the database is updated. Secondly, for classes of databases with bounded degree we show that, without increasing the preprocessing time, we can compute a data structure that does not depend on the query but only on its quantifier rank. We can therefore perform a single preprocessing that can later be used for many queries.
