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

arXiv: https://arxiv.org/abs/2010.08382 · HTML: https://mlsanity.com/paper/2010.08382/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2020.

## Built on by (most cited first, 1 of 1)

- [Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity](https://mlsanity.com/paper/2505.19648/) (2025)

## Abstract (arXiv)

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 n1+ε. 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.