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 ith constant delay.
翻译：一种关系数据库的等级较低, 如果所有 $delta>0 美元, 那么该类中除了有限的许多数据库都具有学位, 最多为 $ $ delta} $, 其中美元是数据库的大小。 典型的例子有约束程度或程度的数据库, 由 $ log n$ 约束。 众所周知, 在一个级别较低的数据库类别中, 一等的布尔查询可以以假线性时间来检查, 即所有 $ epsilon> 0 美元, 被 $ $ $ 1 ⁇ ⁇ ⁇ eepsilon} $ 。 我们通过考虑查询评估来概括这一结果。 我们显示, 计算查询的答案数量可以在假线性时间里进行, 在伪线性预处理后, 我们可以在固定的时间里测试给定的图尔是否是查询的解决方案, 或列出对询问的答案, 其持续拖延 。
相关内容
微信扫码咨询专知VIP会员