The evaluation of queries is a central problem in database management systems. Given a query q and a database D the evaluation of q over D consists in computing the set q(D) of all answers to q on D. An interesting case is when the query is boolean (aka the model checking problem, where the answer to the query is either a “yes” or a “no”). Even for boolean query, the problem of computing the answer (with input q and D) is already PSpace-complete. For non-boolean queries, the size of the output can blow up to |D|^r, where r is the arity of q. It is therefore not always realistic to compute the entire set of solutions. Moreover, the time needed to construct the set might not reflect the difficulty of the task.

In this talk we will discuss query enumeration, that is outputting the solutions one by one. Two parameters enter in play, the delay and the preprocessing time. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. We will investigate cases where the delay is constant (does not depend on the size of the database) and the preprocessing is linear (in the size of the database) i.e. constant delay enumeration after linear preprocessing. This is not always possible as this implies a linear model-checking. We will therefore add restriction to the classes of databases and/or queries such as bounded degree databases, tree-like structures, conjunctive queries…