Enumeration for FO Queries over Nowhere Dense Graphs
Enumeration for FO Queries over Nowhere Dense Graphs
复制标题
无处密集图上 FO 查询的枚举
DOI：
10.1145/3196959.3196971
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Alexandre Vigny
中科院分区：
文献类型：
--
作者：
Nicole Schweikardt;Luc Segoufin;Alexandre Vigny
我们考虑的评价一阶查询的数据库arenowhere density.The概念无处密集类介绍了Nesetril和Ossona德门德斯作为一种形式化的类的“稀疏”的图形和推广许多著名的类的图形，如类的有界度，有界树宽度，或有界扩展。最近Grohe、Kreutzer和Siebertz证明了，在任何稠密类的数据库中，一阶句子都可以在伪线性时间内计算（伪线性时间意味着对于所有ε，存在一个在时间O（n1+ε）内工作的算法，其中ε是数据库的大小）。对于一阶查询的较高的arities，我们表明，在任何无处密集类的数据库，其解决方案的集合可以枚举后的伪线性时间预处理常数延迟。在同一背景下，我们还表明，经过伪线性时间预处理，我们可以在输入的元组，测试在恒定的时间是否是一个解决方案的查询。
We consider the evaluation of first-order queries over classes of databases that arenowhere dense.The notion of nowhere dense classes was introduced by Nesetril and Ossona de Mendez as a formalization of classes of "sparse" graphs and generalizes many well-known classes of graphs, such as classes of bounded degree, bounded tree-width, or bounded expansion. It has recently been shown by Grohe, Kreutzer, and Siebertz that over nowhere dense classes of databases, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all ε there exists an algorithm working in time O(n1+ε), wherenis the size of the database). For first-order queries of higher arities, we show that over any nowhere dense class of databases, the set of their solutions can be enumerated with constant delay after a pseudo-linear time preprocessing. In the same context, we also show that after a pseudo-linear time preprocessing we can, on input of a tuple, test in constant time whether it is a solution to the query.
登录
查看更多内容
具有局部有界扩展的数据库上 FO 查询的恒定延迟枚举
DOI：
--
发表时间：
2017
期刊：
International Conference on Database Theory
影响因子：
--
作者：
L. Segoufin;Alexandre Vigny
通讯作者：
Alexandre Vigny
关于非循环连接查询和常延迟枚举
DOI：
--
发表时间：
2007
期刊：
Annual Conference for Computer Science Logic
影响因子：
--
作者：
Guillaume Bagan;Arnaud Durand;E. Grandjean
通讯作者：
E. Grandjean
在有界度数据库更新下回答 FO MOD 查询
DOI：
10.1145/3232056
发表时间：
2017
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
Christoph Berkholz;Jens Keppeler;Nicole Schweikardt
通讯作者：
Nicole Schweikardt
DOI：
10.1145/3051095
发表时间：
2013-11
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Martin Grohe;S. Kreutzer;S. Siebertz
通讯作者：
Martin Grohe;S. Kreutzer;S. Siebertz
具有易于处理的组合复杂性和高效更新的树枚举
DOI：
10.1145/3294052.3319702
发表时间：
2018
期刊：
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
--
作者：
Antoine Amarilli;P. Bourhis;S. Mengel;Matthias Niewerth
通讯作者：
Matthias Niewerth