Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion
Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion
复制标题
具有局部有界扩展的数据库上 FO 查询的恒定延迟枚举
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Alexandre Vigny
中科院分区：
文献类型：
--
作者：
L. Segoufin;Alexandre Vigny
我们考虑评估的一阶查询类的数据库与本地有界扩展。这个类是由Nesetril和Ossona de Mendez引入的，并且推广了许多众所周知的数据库类，例如有界度，有界树宽度或有界扩展。众所周知，在具有局部有界扩展的数据库类上，一阶句子可以在伪线性时间内进行计算（伪线性时间意味着对于所有的n，存在一个在时间O（n^{1+ n}）内工作的算法）。在这里，我们调查其他情况下，查询不是句子。我们表明，一阶查询可以枚举与恒定延迟后，伪线性预处理的任何一类数据库具有局部有界的扩展。我们还表明，在这种情况下，计数的解决方案的数量可以在伪线性时间。
We consider the evaluation of first-order queries over classes of databases with local bounded expansion. This class was introduced by Nesetril and Ossona de Mendez and generalizes many well known classes of databases, such as bounded degree, bounded tree width or bounded expansion. It is known that over classes of databases with local bounded expansion, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all epsilon there exists an algorithm working in time O(n^{1+epsilon})). Here, we investigate other scenarios, where queries are not sentences. We show that first-order queries can be enumerated with constant delay after a pseudo-linear preprocessing over any class of databases having locally bounded expansion. We also show that, in this context, counting the number of solutions can be done in pseudo-linear time.
DOI：
10.1145/2594538.2594539
发表时间：
2014
期刊：
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
Arnaud Durand;Nicole Schweikardt;Luc Segoufin
通讯作者：
Luc Segoufin