论文标题
对低度数据库的一阶查询列举答案
Enumerating Answers to First-Order Queries over Databases of Low Degree
论文作者
论文摘要
如果对于所有$δ> 0 $，则一类关系数据库的学位较低，几乎有限的同类数据库最多都具有$ n^δ$，其中$ n $是数据库的大小。典型的示例是有界度的数据库或由$ \ log n $界定的学位。 众所周知，在具有低度，一阶布尔值查询的一类数据库中，可以在伪线性时间内检查，即，对于所有$ n^{1+ε} $，所有$ε> 0 $。我们通过考虑查询评估来概括此结果。 我们表明，计算查询的答案数量可以在伪线性时间内完成，并且在伪线性时间进行预处理后，我们可以在恒定时间内测试给定元组是否是查询或以恒定延迟来枚举查询的答案。
A class of relational databases has low degree if for all $δ>0$, 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.\ for all $ε>0$ in time bounded by $n^{1+ε}$. We generalize 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 after a pseudo-linear time preprocessing we can test in constant time whether a given tuple is a solution to a query or enumerate the answers to a query with constant delay.
