一句话：论文将低度数据库上一阶布尔查询的伪线性时间判定推广到查询求值，实现答案计数、常时判定与常延迟枚举。
本文研究低度关系数据库上一阶查询的求值问题。低度类指：对任意 δ>0，除有限多个例外，数据库中元素的度数不超过 n^δ（n 为数据库大小），典型情形包括有界度数据库和度数不超过 log n 的数据库。已知在此类数据库上，一阶布尔查询可在伪线性时间（对任意 ε>0，时间为 n^{1+ε}）内判定。作者将该结果从布尔查询推广到一般查询求值，证明答案计数可在伪线性时间内完成；并且经过伪线性时间预处理后，既能以常数时间判定给定元组是否为查询答案，也能以常数延迟枚举查询的所有答案。该工作统一并强化了低度数据库上查询处理的时间与枚举复杂度上界。
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.
@article{paperbot1703,
title = {Enumerating Answers to First-Order Queries over Databases of Low Degree},
author = {Arnaud Durand and Nicole Schweikardt and Luc Segoufin},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 2},
year = {2022},
doi = {10.46298/lmcs-18(2:7)2022}
}