Enumerating answers to first-order queries over databases of low degree
Enumerating answers to first-order queries over databases of low degree
复制标题
枚举低度数据库上的一阶查询的答案
DOI：
10.1145/2594538.2594539
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Luc Segoufin
中科院分区：
文献类型：
--
作者：
Arnaud Durand;Nicole Schweikardt;Luc Segoufin
如果对于所有的δ，类中除了有限多个数据库之外的所有数据库至多有n个δ，则这类关系数据库是低度的，其中n是数据库的大小。典型的例子是有界度或以logn为界的度的数据库。众所周知，在一类具有低度的数据库上，可以在伪线性时间内，即在以N1+ε为界的时间内，对所有ε检查一阶布尔查询。我们通过考虑查询评估来推广这一结果，我们证明了对查询答案的计数可以在伪线性时间内完成，而对查询答案的枚举可以在经过伪线性时间预处理后以恒定的延迟完成。
A class of relational databases has low degree if for all δ, all but finitely many databases in the class have degree at most nδ, where n is the size of the database. Typical examples are databases of bounded degree or of degree bounded by log n. It is known that over a class of databases having low degree, first-order boolean queries can be checked in pseudo-linear time, i.e. in time bounded by n1+ε, for all ε. We generalise this result by considering query evaluation.We show that counting the number of answers to a query can be done in pseudo-linear time and that enumerating the answers to a query can be done with constant delay after a pseudo-linear time preprocessing.
登录
查看更多内容
从 P 到 NP 的算法
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
B. Moret;H. Shapiro
通讯作者：
H. Shapiro
关于非循环连接查询和常延迟枚举
DOI：
--
发表时间：
2007
期刊：
Annual Conference for Computer Science Logic
影响因子：
--
作者：
Guillaume Bagan;Arnaud Durand;E. Grandjean
通讯作者：
E. Grandjean
线性延迟枚举和一元二阶逻辑
DOI：
10.1016/j.dam.2008.08.021
发表时间：
2009
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
B. Courcelle
通讯作者：
B. Courcelle
有界度结构的一阶查询可以恒定延迟计算
DOI：
--
发表时间：
2005
期刊：
TOCL
影响因子：
--
作者：
Arnaud Durand;E. Grandjean
通讯作者：
E. Grandjean
DOI：
--
发表时间：
2013
期刊：
TOCL
影响因子：
--
作者：
Wojciech Kazana;L. Segoufin
通讯作者：
L. Segoufin