A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, 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 $\epsilon>0$ in time bounded by $n^{1+\epsilon}$. 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.
翻译：一种关系数据库的等级较低, 如果所有 $delta>0 美元, 那么该类中除了有限的许多数据库都具有学位, 最多为 $ $ delta} $, 其中美元是数据库的大小。 典型的例子有约束程度或程度的数据库, 受 $ log n$ 约束。 众所周知, 对于一个级别较低的数据库类别, 一等布尔查询可以在假线性时间里进行检查, 即\\ 所有 $ epsilon> 0 美元, 受 $ $ $ 1 ⁇ ⁇ eepsilon} 的时间限制。 我们通过考虑查询评价来概括这一结果。 我们显示, 计算查询的答案数量可以在假线性时间里进行, 在假线性预处理后, 我们可以在固定的时间里测试给定的图普是查询的解决方案, 还是用不断的延迟来计算对查询的答案 。
相关内容
微信扫码咨询专知VIP会员