Enumerating answers to first-order queries over databases of low degree
Arnaud Durand, Nicole Schweikardt, Luc Segoufin · 2014
A class of relational databases has low degree if for all δ, 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. in time bounded by n1+ε, for all ε. We generalise this result by considering query evaluation.