Enumerating Answers to First-Order Queries over Databases of Low Degree

Abstract

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.

References in corpus (1)

• Dynamic Query Evaluation Over Structures with Low Degree