Arnaud Durand
email: arnaud.durand@u-paris.fr

Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration

Keywords: Theory of computation → Database theory, Complexity classes, Finite Model Theory Query evaluation, enumeration algorithm, counting, logic ACM Reference Format:

This paper is devoted to a complexity study of various tasks related to query answering such as deciding if a Boolean query is true or not, counting the size of the answer set or enumerating the results. It is a survey of some of the many tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.

INTRODUCTION

Query answering is a task of major importance in databases that motivates both practical and fundamental research. In particular, a vast literature is devoted to algorithms for efficient query processing and to their complexity. Given a database D and a query φ, the most basic problem is that of computing the set φ(D) of tuples that form the answers when evaluating φ against the database D. When φ is Boolean, the problem reduces only to determine whether φ is true in D.

However, query answering covers a plethora of algorithmic problems for which one has to either find efficient solutions or to understand why it is hard to adapt tractable approaches for providing approximated or partial answers.

One such problem that has received a considerable amount of attention [4, 5, 25, 33-35, 70, 72] is that of counting the number of results (that is, computing the size of φ(D)). The source of this might lay in the following:

• Extracting numerical and statistical information is obtained by counting and by general aggregations (e.g., summing, averaging etc.) • It appears as a key tool in probabilistic databases and reasoning.

Another problem is that of enumerating the results of a query (see [START_REF] Berkholz | Constant delay enumeration for conjunctive queries: a tutorial[END_REF][START_REF] Segoufin | A glimpse on constant delay enumeration[END_REF] for surveys on the problem). The answer set of a query may be of huge size and in many applications one either does not need the whole set (such as when interested in top k answers under some criteria) or one can start exploiting the first answers while waiting for the others. Under this angle, it is interesting to obtain algorithms that offer guarantees for the regularity of the generating process. These guarantees can be expressed, for example, in terms of delay between two consecutive solutions.

Going further, whether it concerns deciding, counting or enumerating all of these tasks can be handled in contexts where the data is known from the beginning and does not change or, by contrast, when data is updated regularly (see [START_REF] Amarilli | Uniform Reliability of Self-Join-Free Conjunctive Queries[END_REF][START_REF] Berkholz | Answering Conjunctive Queries under Updates[END_REF][START_REF] Berkholz | Answering UCQs under Updates and in the Presence of Integrity Constraints[END_REF][START_REF] Idris | The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates[END_REF][START_REF] Idris | Conjunctive Queries with Inequalities Under Updates[END_REF]). In that latter context, the objective is then to answer without starting the computation from scratch.

These few examples illustrate how wide the panel of algorithmic tasks for query answering is. However, query languages may be rather expressive and it is well-known that the complexity of simple and popular query problems may be intractable. For example, evaluating a Boolean conjunctive query over an arbitrary database is known to be NP-complete (when both the structure and the query are regarded as input [START_REF] Chandra | Optimal Implementation of conjunctive queries in relational databases[END_REF]). When a query problem is intractable, one approach to find islands of tractability is by putting structural restrictions either on the class of queries under consideration or on the data and study the effects of these restrictions on the complexity of query answering. This research direction is at the core of many works in the database community.

The objective of this paper is to survey some of the main approaches dedicated to the fine-grained analysis of query problems. The diversity of tasks, from deciding through enumerating to counting, has required along the years the elaboration of a wide spectrum of algorithmic techniques, of structural results for graphs and hypergraphs and of methods for finding lower bounds (see e.g. [1, 2, 4, 8, 11, 21, 22, 28, 31, 32, 36, 37, 42, 44, 59-61, 74, 77]). In a fundamental way, this diversity has also required to think differently what tractability means depending on the contexts. A good example is the notion of constant delay enumeration [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF][START_REF] Durand | First-order queries on structures of bounded degree are computable with constant delay[END_REF] that guarantees a delay depending only on the query size (which is independent on the underlying database) between two outputs of an enumeration problem. This notion has emerged has a central class in a re-think of what tractability means for enumeration in the context of query answering (while in algorithm design, linear or polynomial delay were the paradigm of tractability for years). This survey is not intended to be exhaustive but is aimed at illustrating the methods and approaches that have been at the core of finegrained complexity analysis of queries, in particular for decision problems, counting, and enumerating. Consequently, most of the results will be illustrated through examples.

Structure of the paper. We will survey the complexity of query problems under two main restrictions: on the data set on the one side, and on the structure of the queries on the other side (and sometimes, to some extend, on both).

Data restriction. In Section 3, we examine the complexity of firstorder query languages. As it is well-known that this problem is PSPACE-complete, one turns into restricting the class of databases that are considered as input. It has appeared along the years, that the key notion that leads to tractability is that of sparsity of data (see [START_REF] Nesetril | Sparsity -Graphs, Structures, and Algorithms[END_REF]) and the section is devoted to the survey of the main results in that direction for what concerns decision, counting and enumeration. It turns out that unlike in other domains, tractability for decision will often extend to the two other tasks. This part is completed by Section 3.3, where the case of monadic second-order queries is shortly investigated.

Query restriction. Section 4 is devoted to the wide class of conjunctive queries. It is by far the most developed part of the paper. One fragment that is known for a long time to admit efficient algorithms is that of acyclic conjunctive queries. We examine the complexity of this fragment and show that tractability is, this time, subject to different criteria depending on the algorithmic task under consideration. We then study several extensions of this fragments that enrich its expressive power : taking union of acyclic queries, allowing comparisons or disequalities, and allowing negations. The study of this approach based on query restriction is completed in Section 5 where one studies the classification of counting and enumeration complexity for first-order queries based on restricting their prefixes.

In Section 2, we recall the basic definitions about query problems. We also introduce and motivate different complexity measures suitable for deciding, computing, counting or enumerating the result of a query. To make the main technical sections as self-contained as possible, some of the definitions are introduced only later, when needed. A conclusion is given in Section 6.

References and acknowledgment

Thanks to Florent Capelli, Nofar Carmeli, Liat Peterfreund, Alexandre Vigny for careful reading of parts of this paper.

Material of Section 3 is inspired by the thesis of Alexandre Vigny [START_REF] Vigny | Query enumeration and nowhere dense graphs[END_REF]. Additional surveys can be found also in [START_REF] Segoufin | A glimpse on constant delay enumeration[END_REF], [START_REF] Berkholz | Constant delay enumeration for conjunctive queries: a tutorial[END_REF] (on enumeration for query answering and, in particular, constant delay enumeration), in [START_REF] Strozecki | Enumeration Complexity[END_REF] (on enumeration complexity) and in [START_REF] Capelli | Structural restrictionsof CNF-formulas: applications to model counting and knowledge compilation[END_REF] (connexion with knowledge compilation).

PRELIMINARIES

We suppose the reader familiar with rudiments of (first order and second order) logic [START_REF] Libkin | Elements of Finite Model Theory[END_REF], complexity [START_REF] Arora | Computational Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF], and graph theory [START_REF] Diestel | Graph Theory[END_REF]. We write N to denote the set of non-negative integers, Q to denote the set of rationals, and Q >0 for the set of positive rationals. For n ∈ N, we set [n] = {1, ..., n}. Let L be a subclass of first-order logic, denoted FO, or secondorder logic, denoted SO. We will give the definition of various fragments of FO and SO when needed in the paper.

Databases and queries

A L (σ )-query is a formula in L of signature σ , for some relational signature σ (σ is omitted when it is clear from the context). For φ ∈ L , we denote by var(φ) its set of variables, free(φ) its set of free variables and atom(φ) its set of atomic formulas. We write φ( x, X ) to denote a query whose free first order variables are x, free second order variables are X . The number of free variables is called the arity of the query. A Boolean query (i.e. sentence) φ is a query of arity 0 i.e. with free(φ) = ∅.

Query problem(s)

Given a structure D and a query φ, an answer to φ in D is a tuple ā and a tuple of sets Ā of elements of Dom(D) such that D |= φ( ā, Ā). We write φ(D) for the set of answers to φ in D, i.e. φ(D) = {( ā, Ā) : D |= φ( ā, Ā)}. When φ is a sentence, the answer is a Boolean.

Let L be a logic and C be a class of structures. The query problem (resp. Boolean query or model checking problem) of L over C is the following computational problem: given a (resp. Boolean) query φ ∈ L and a database D ∈ C , compute φ(D) (resp. test if D |= φ).

For the counting problem of L over C , given a formula (resp. sentence) φ ∈ L and a database D ∈ C , the objective is to compute the number of elements of φ(D).

Another important algorithmic task is enumerating solutions. In the context of query problems for a logic L over a class C , the enumeration problem is the following: given φ ∈ L and a database D ∈ C output the elements of φ(D) one by one with no repetition.

When the formula φ is fixed, we denote by ♯•φ and enum•φ the respective counting and enumeration problems.

Model of computation and complexity measures

Recall that P (resp. NP) is the class of problems that can be decided (resp. verified) in polynomial time.

Complexity measures for query problems. Most of the results

given in this paper were designed using Random Access Machines (RAMs) with addition and uniform cost measure as a model of computation. For further details on this model and its use in logic see [START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Grandjean | Graph properties checkable in linear time in the number of vertices[END_REF].

The RAM algorithms will take as input a query φ ∈ L of size k and a database D ∈ C of size n. The complexity of such problems can be evaluated in two well-known contexts:

• Combined complexity were both ||D|| and ||φ|| are taken into account for the complexity evaluation, • Data complexity were only ||D|| is taken into account (i.e. φ being considered as fixed). Unless otherwise specified, or when precise bounds are given, we will often consider the data complexity setting. We then say that an algorithm runs in polynomial time (resp. quasi-linear time, resp. linear time, resp. constant time) if it outputs the solution within

f (k)•n c steps for some c ∈ N (resp. f (k)•n•(log n) O (1) steps, resp. f (k)•n steps, resp. f (k) steps)
, for some computable function f . An algorithm runs in pseudo-linear time if, for all ϵ ∈ Q >0 it outputs the solution within f (k, ϵ)•n 1+ϵ steps, for some function f . Most of the time measures (such as linear time) considered in the paper are rather restrictive so it is necessary to make precise how data is accessed. For example, we assume that the input relational structure comes with a linear order on the domain. If not, we use the one induced by the encoding of the structure as an input to the RAM.

Complexity measures for enumeration.

The first complexity measures for enumeration have been formalized in [START_REF] Johnson | On Generating All Maximal Independent Sets[END_REF]. Algorithms and complexity for enumeration have deserved a lot of attention in the recent years (see the survey [START_REF] Strozecki | Enumeration Complexity[END_REF]).

Formally, the enumeration problem is identical to the classical query problem except that some focus is put on the regularity of the process that leads to the computation of φ(D) It is natural that the dynamic of such a process be measured in terms of delay (i.e. maximal time) between any two consecutive outputs of elements of φ(D). Due to the important differences in size between data and query, it will also appear meaningful in this context to separate the enumeration process itself to the preprocessing time i.e. the time needed to output the first solution and built necessary data structures.

Let δ, p : N × N → N be two functions. We say that the enumeration problem of L over a class C of structures can be solved with delay δ and after a preprocessing of p, if it can be solved by a RAM algorithm which, on input φ ∈ L of size k and D ∈ C of size n, can be decomposed into two phases:

• a preprocessing phase that is performed in time p(k, n), that produces the first solution and

• an enumeration phase that outputs elements of φ(D) with no repetition and a delay in time δ (k, n) between two consecutive outputs.

Note that, under these conditions, φ(D) can be computed in total time:

p(k, n) + |φ(D)| × δ (k, n).
When p(k, n) and δ (k, n) are bounded by a polynomial (in n in the data complexity setting; in n and k in combined complexity) the enumeration problem is said to be solvable in polynomial delay.

In the database context, where the size of data maybe huge, a delay even linear in the size of D can hardly be seen as tractable. Consequently, it is crucial to understand if (and when) enumeration can be handled within a delay independent of the data size. In this view, we consider that a query problem can be enumerated with constant delay after a linear preprocessing, i.e. is in the class Constant-Delay lin introduced in [START_REF] Durand | First-order queries on structures of bounded degree are computable with constant delay[END_REF] Taking into account that the query sizes are usually far smaller than the data sizes, it makes it natural to consider the parameterized version of (below, Boolean) query problems.

p-MC(FO)

Input: A database D and a Boolean query φ Parameter: ||φ|| Output: Does D |= φ Such an approach applies not only for decision but also naturally for function problems. In this paper, we will express that some algorithmic results can not be improved provided some widely believed complexity hypothesis from parameterized complexity hold. For this we recall briefly three useful measures (see [START_REF] Flum | Parameterized Complexity Theory[END_REF]).

Definition 2.2. A parameterized problem (Q, k) is in FPT if there is a computable function f : N → N, c ∈ N and an algorithm that upon input x ∈ Σ * of size n decides if x ∈ Q in time at most: f (k(x)) • n c .
Intuitively, FPT corresponds to our definition of polynomial time in the data complexity setting.

Definition 2.3. Let Σ, Σ 0 be two finite alphabets. A FPT-reduction from (Q, k) over Σ to (Q 0 , k 0 ) over Σ 0 is a mapping R : Σ * → Σ * 0 such that: • For all x ∈ Σ * : x ∈ Q ⇐⇒ R(x) ∈ Q 0 • R is computable by a FPT algorithm • There is a computable function д : N → N such that, for all x ∈ Σ * : k 0 (R(x)) ≤ д(k(x))
The parameterized clique problem is the following: for a graph G = (V , E) and parameter k ∈ N, decide whether there is V ′ ⊆ V of size k such that, for all x, y ∈ V ′ : (x, y) ∈ E. Then,

• W [START_REF] Amarilli | A Circuit-Based Approach to Efficient Enumeration[END_REF] is the the class of problems FPT-reducible to the parameterized clique problem and, • AW[ * ] is the class of problems FPT-reducible to p-MC(FO), the model checking of FO.

FIRST-ORDER QUERIES AND SPARSITY

We consider here L = FO and queries φ(x) ∈ FO with only free first-order variables. It is well known that, given a query φ(x) and a database D, φ(D) can be computed in time

||φ|| × ||D|| h
where h is the maximal number of free variables for a sub-formula of φ [START_REF] Libkin | Elements of Finite Model Theory[END_REF]. Although there could be some variant in the expression of the complexity, under some reasonable complexity assumption (namely that AW[ * ] FPT), there is no hope, for arbitrary databases, to obtain an upper bound where h can be replaced by a constant c ∈ N independent of φ. Indeed, as an obvious consequence, such a bound would lead to an algorithmic breakthrough for problem such as testing if a graph has a clique of a given size that can be generically described by:

∃x 1 . . . ∃x k k i <j=1
x i x j ∧ E(x i , x j ).

For arbitrary first-order queries, one can then hope for more efficient bounds only by restricting the databases as input. In this direction, the notion of sparsity has played a key role [START_REF] Nesetril | Sparsity -Graphs, Structures, and Algorithms[END_REF] as we will show.

The role of sparsity

A first restriction that seems natural to consider is when every elements are in connexion to constantly many others only. Let D = ⟨D; R 1 , . . . , R q ⟩ be a σ -structure for a relational signature σ = {R 1 , . . . , R q }. For each i ≤ q, R i ⊆ D a i . Define the degree of an element x in D, denoted deg D (x) as the total number of tuples of relations R i to which x belongs. One defines the degree of a structure as

deg(D) = max x ∈D (deg D (x)).
A class C of structures is of bounded degree if there exists c ∈ N such that, for all D ∈ C , deg(D) ≤ c. Note that such classes are closed under substructures: if D ′ is a substructure of D and D is of degree bounded by some c ∈ N, then so is D ′ .

By taking advantage of the locality of first-order logic and the fact that in a structure of degree bounded by c ∈ N, for each element of the domain, the number of elements at distance at most d ∈ N is bounded by c d +1 , the following result holds. Theorem 3.1 ( [START_REF] Seese | Linear Time Computable Problems and First-Order Descriptions[END_REF], [START_REF] Kazana | First-order query evaluation on structures of bounded degree[END_REF]). Let C be a class of bounded degree structures. Then, the model-checking problem of first-order queries over C can be decided in time linear in the size of the database i.e. there exists a function f such that, given a sentence φ ∈ FO and D ∈ C , testing whether D |= φ can be done in time f (||φ||) • ||D||. Moreover, function f is such that:

f (||φ||) ≤ 2 2 2 O (||φ ||)
.

From [START_REF] Frick | The complexity of first-order and monadic second-order logic revisited[END_REF], it is known that unless AW[ * ] = FPT, the constant can not be lowered to 2 2 O (||φ ||)

. To which extend could the results from Theorem 3.1 be extended to compute the set φ(D)? In particular, is it possible to generate the elements of φ(D) through a process whose regularity is guaranteed? It turns out that it is indeed the case. Such an investigation leaded to the notion of constant delay enumeration and to the following result(s). Theorem 3.2 ( [START_REF] Durand | First-order queries on structures of bounded degree are computable with constant delay[END_REF], [START_REF] Kazana | First-order query evaluation on structures of bounded degree[END_REF]). Let C be a class of bounded structures. Then, there are algorithms that upon input φ ∈ FO and D ∈ C :

• Output the number of elements of φ(D) in time f (||φ||) • ||D||. • Enumerate φ(D) with constant delay f (||φ||) after precompu- tation time f (||φ||) • ||D|| for some function f , such that f (k) ≤ 2 2 2 O (k ) .
Note that this implies that computing φ(D) when D is of bounded degree can be done in total time:

f (||φ||) • (|φ(D)| + ||D||).
The approach of [START_REF] Durand | First-order queries on structures of bounded degree are computable with constant delay[END_REF] and to some extend some of the works that have followed are based on quantifier elimination methods. They can roughly be described as follows. First, it is convenient to represent bounded degree relations by a collection of partial injective functions. This can be done in different ways. Then, given φ(x) ∈ FO and a database D ∈ C , one constructs:

• a database D ′ ∈ C in time O(f (||φ||) • ||D||) • and φ ′ (x) ∈ FO, quantifier free, in time O(f (||φ||))
for some computable function f such that:

φ(D) = φ ′ (D ′ ).
Once an equivalent quantifier free has been obtained, enumeration becomes easier.

Example 3.3. Let φ(x) = ∃yϕ(x, y), on a vocabulary σ of unary function intepreted as partial injective functions. Let F a σ -structure. We illustrate how to get rid of y. To simplify, let φ(x) be as follows

φ(x) ≡ ∃y [ψ (y) ∧ y f 1 (x 1 ) ∧ • • • ∧ y f k (x k )]
where f 1 , ..., f k ∈ σ . A term of the form f i (x i ) = y above, would have permit to replace immediately y by f i (x i ) everywhere. Let us call ∃ h+1 ψ the condition:

∃ h+1 ψ = ∃x 1 • • • ∃x h+1 h+1 i, j=1 i j x i x j ∧ h+1 i=1 ψ (x i )
Each ∃ h+1 ψ can be computed in O(||F||). Let F ′ be the structure F enriched with these Boolean informations. Given values for x, suppose h ≤ k is the number of distinct values among those of the k terms f i (x i ) such that ψ (f i (x i )) is true; then, formula φ(x) is true if and only if the number of elements b such that F |= ψ (b) holds is strictly greater than h. Consequently, φ(F) = φ ′ (F ′ ) where φ ′ (x) is the (combinatorial involved) quantifier-free formula that look for a possible h ≤ k that satisfy the above condition:

φ ′ (x) ≡ k h=0 P ⊆[k ],Q ⊆P, |Q |=h ψ Q P (x) ∧ ∃ h+1 ψ with ψ Q P (x) ≡ j ∈Q ψ (f j (x j ))∧ i ∈P j ∈Q f i (x i ) = f j (x j )∧ j ∈[k]\P ¬ψ (f j (x j ))
Why is enumeration easier for quantifier-free formulas? Suppose a quantifier-free φ(x, y) is as follows:

φ(x, y) ≡ ψ 1 (x) ∧ ψ 2 (y) ∧ k i=1 y f i (x i )
ψ 2 (y) has one free variable, ψ 2 (F) can easily be computer in linear time. By induction enumerating φ(F) amounts to enumerate tuples

(a, b) with a ∈ ψ 1 (F), b ∈ ψ 2 (F) with at most k exceptions for each fixed a: when k i=1 b f i (a i ) is true.
Hence it can be done with constant delay See Algorithm 1 below (if |ψ 2 (F)| < k an even simpler tratment can be done).

Algorithm 1 Enumerate φ(F) (with the hypothesis that |ψ 2 (F)| ≥ k) 1: for a ∈ ψ 1 (F) do 2: for b ∈ ψ 2 (F) do 3: if D ̸ |= k i=1 b = f i (a i ) then 4: output (a, b)
The results above were the first of a series that prove linear or pseudo-linear model checking and constant delay enumeration for increasingly larger classes C , closed under substructures: graphs of bounded expansion [START_REF] Dvořák | Deciding First-Order Properties for Sparse Graphs[END_REF][START_REF] Kazana | Enumeration of first-order queries on classes of structures with bounded expansion[END_REF], graphs of locally bounded tree-width [START_REF] Frick | Deciding first-order properties of locally tree-decomposable structures[END_REF] (that includes planar and bounded tree-width graph), graphs of locally bounded expansion [START_REF] Segoufin | Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion[END_REF]. Note that numeration results were technically harder and most of the time came significantly later.

All these classes concern structures that can be identified as sparse: the density of tuples compared to elements of the domains is somehow restricted. In [START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF] a notion called nowhere dense graphs was introduced as a formalization of classes of sparse graphs. It appears to encompass all known classes of sparse graphs (planar, bounded tree-width, excluding a minor, locally bounded expansion, etc [START_REF] Nešetřil | On nowhere dense graphs[END_REF]). One way to represent it is through the notion of r -minor defined below. Definition 3.4. Let G = (V , E) be an undirected graph and r be an integer. A graph H = (V ′ , E ′ ) is an r -minor (also named shallow minor or low depth minor) of G if:

• V ′ ⊆ V ,
• for every a i in V ′ , there is a set S i in V such that:

-S i ⊆ N G r (a i ), for every i j we have S i ∩ S j = ∅, and for every i j we have (a i , a j ) is in E ′ if and only if in G there is an edge from a node in S i to a node in S j .

We note H ∈ G▽r the fact that H is an r -minor of G. We also note H ∈ C ▽r the fact that there is a graph G in C such that H is an r -minor of G.

We give below the basic definition of nowhere-dense graphs. It appears to be a very robust notion that can be defined by many other equivalent properties [START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF]. Definition 3.5 ([67]). Let C be a class of graphs. C is nowhere dense if and only if for all r ∈ N there is a N r ∈ N such that K N r C ▽r . Here, K n is the clique with n elements i.e. a graph with n vertices and every possible edges.

Nowhere dense seems to be one of the broadest class of graphs that admit good algorithmic properties. Theorem 3.6 ([53,[START_REF] Schweikardt | Enumeration for FO Queries over Nowhere Dense Graphs[END_REF][START_REF] Vigny | Query enumeration and nowhere dense graphs[END_REF]). Let C be a class of nowhere dense graphs. For every FO formula φ and ϵ > 0, there is an algorithm and a function f such that upon input of a graph

G ∈ C • Decide whether G |= φ in time f (||φ||, ϵ) • ||G || 1+ϵ (when φ is a sentence). • Output the number of solutions of φ(G) in time f (||φ||, ϵ) • ||G || 1+ϵ . • Enumerate φ(D) with delay f (||φ||, ϵ) after precomputation time f (||φ||, ϵ) • ||G || 1+ϵ .
In opposition to nowhere dense, one can define the notion of somewhere dense as follows: A class of graphs C is somewhere dense if and only if it is not nowhere dense [START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF]. Note that none of those two definitions imply closure under subgraphs. However, if a class is nowhere dense (resp. somewhere dense) then its closure by adding every possible subgraph remains nowhere dense (resp. somewhere dense). Combined with the following result, this leads to a complexity dichotomy for classes o structures closed under subgraphs. Theorem 3.7 ( [START_REF] Kreutzer | Parameterized Complexity of First-Order Logic[END_REF]). The model checking problem over somewhere dense classes of graphs that are closed under subgraphs is AW[ * ] complete, and therefore very unlikely to be in FPT.

Recall that one can hope for an efficient enumeration algorithm for a query problem (in the sense of a constant delay algorithms after fixed polynomial time preprocessing), only when its Boolean counterpart, a.k.a. the model checking problem, admits an FPTalgorithm. Hence the result above also implies a dichotomy algorithm for enumeration tasks.

The end of the story for FO?

The results above emphasize the role played by sparsity for tractability of first order queries. They also establish a tractability frontier along the notion of somewhere dense structure for classes closed under subgraphs. But what can be said for arbitrary classes of structures?

Let us consider the class C of graphs of degree O(log n) where n is the number of vertices. For k ∈ N, the graph G that contains:

• a clique of size k, and

• 2 k independent nodes, is in C . Hence,
ϵ > 0, there is a rank N in N such that for every G in C , if |G | > N then d(G) ≤ |G | ϵ , where d(G) is the degree of G.
As shown below, such classes of graphs still admit good algorithms. Theorem 3.9 ( [START_REF] Grohe | Generalized Model-Checking Problems for First-Order Logic[END_REF]). Let C be a class of graphs with low degree. For every FO formula φ and ϵ > 0, there is an algorithm that upon input of a graph G in C decides whether

G |= φ in time O(|G | 1+ϵ ).
This result uses some ideas that where at the core of Theorem 3.1 i.e. the locality of first-order logic. The difficulty when generalizing this to structures with low degree is that a given node does not have a neighborhood of bounded size but only of small size. This makes harder to obtain a constant delay enumeration (and not only an algorithm whose delay could be O(n ϵ ). Fortunately, it is possible to work around this main issue. Theorem 3.10 ( [START_REF] Durand | Enumerating answers to first-order queries over databases of low degree[END_REF]). Let C be a class of graphs with low degree. There is an algorithm which, upon input of a structure D in C and an FO query φ, enumerates the set φ(D) with constant-time delay after a pseudo-linear-time preprocessing.

Beyond the particular case above, some recent tractability results have been obtained by considering first-order interpretations into formerly studied classes (such as bounded degree [START_REF] Gajarský | A New Perspective on FO Model Checking of Dense Graph Classes[END_REF] or bounded expansion [START_REF] Gajarský | First-Order Interpretations of Bounded Expansion Classes[END_REF]).

Monadic queries

Monadic second-order logic, for short MSO extends first-order logic by allowing quantification over sets. When dealing with MSO queries, it is quite natural to look at graphs with bounded treewidth. The so-called Courcelle's theorem below has been one of the most influential tractability result in this area. Theorem 3.11 (Courcelle's theorem [START_REF] Courcelle | Graph Rewriting: An Algebraic and Logic Approach[END_REF]). The model checking problem for MSO queries over classes of structures of bounded treewidth can be solved in linear time.

Following this first result, other algorithms tasks such as counting [START_REF] Arnborg | Easy Problems for Tree-Decomposable Graphs[END_REF] have been proved to be tractable over instances of bounded tree-width for MSO queries.

In contrast with first-order logic, the expressive power of MSO can be very high even on some natural classes of sparse (although of unbounded treewidth) structures. Given m, n ∈ N, a (m, n)-grid is a graph on vertex set {1, ..., m} × {1, ..., n} with edge set:

{((i, j), (i ′ , j ′ ) : (i = i ′ and |j -j ′ | = 1) or (j = j ′ and |i -i ′ | = 1))}.
It is easily seen that MSO formulas can be used to describe a n steps, m space bounded computation of a Turing Machine when evaluated over a colored (m, n)-grid graph. Hence, there is few hope to find tractability results beyond treewidth. It is believed that Courcelle's theorem is somewhat optimal [START_REF] Grohe | Logic, graphs, and algorithms[END_REF] (see also [START_REF] Kreutzer | On the Parameterised Intractability of Monadic Second-Order Logic[END_REF] for partial result under some complexity hypothesis).

Enumeration.

The enumeration problem is also tractable. However with MSO queries we could potentially encounter free set variables i.e. be of the form φ(x, X) where X is a tuple of free second order variables.

This hardly allows constant delay enumeration since the size of a solution might be as large as the input size. Therefore just writing one solution could require linear time and two consecutive solutions may be "far" from each other. Indeed, consider the database D over the domain D = {1, ..., 2n} with one relation E defined by {(a, 1) : a = 1, ..., n} ∪ {(a, 2) : a = n + 1, ..., 2n} and

φ(X ) = ∃x∀y ∈ X E(y, x) ∧ ∀y X ¬E(y, x)
It holds φ(D) = {{1, 2, ..., n}, {n + 1, n + 2, ..., 2n}}. The two solutions are disjoints and no algorithms can produce one after the other in constant time. The good measure for the delay is to take into account the output length.

The result below extends Theorem 3.11. Theorem 3.12 ( [START_REF] Bagan | MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay[END_REF][START_REF] Courcelle | Linear delay enumeration and monadic second-order logic[END_REF]). Let C be a class of structures with bounded tree-width, there is an algorithm and a function f which, upon input of a structure D in C and an MSO query φ, enumerates each solution s of the set φ(D) with linear-time preprocessing and delay f (|φ|) • |s | i.e. linear in the output size.

If φ(x) contains only free first-order variables then the enumeration can be done with delay f (|φ|) i.e in constant delay.

Alternatives proof for the constant delay bound, for queries with free first order variables only has also been found in [START_REF] Kazana | Enumeration of monadic second-order queries on trees[END_REF] using quantifier elimination methods. Additional details can be found in two thesis, [START_REF] Bagan | Algorithmes et complexité des problèmes d'énumération pour l'évaluation de requêtes logiques[END_REF] and [START_REF] Kazana | Query evaluation with constant delay[END_REF]. More recently, by using technics from knwoledge compilation, an alternative proof of Theorem 3.12 has also been given in [START_REF] Amarilli | A Circuit-Based Approach to Efficient Enumeration[END_REF].

ACYCLIC CONJUNCTIVE QUERIES AND BEYOND

In this section, we focus on tractable fragments of FO queries on arbitrary databases. Recall that conjunctive queries, CQ for short, are queries of the form:

φ(x) := ∃y i R i (z i )
where for every i, R i is a relational symbol and z i is a tuple of variables from x and y. The combined complexity of CQ is NP-complete and, as such, the fragment is already too expressive. Below, we survey the complexity of a well-known restriction of CQ called acyclic conjunctive queries, ACQ. It turns out that for all algorithmic tasks under consideration tractability results can be found at the price of introducing new methods and measures. We also investigate possible extensions of ACQ and study their effects on the complexity of query evaluation.

Hypergraph of a query. An finite hypergraph H = (V , E) is a finite set V together with a subset E of the powerset of V , i.e. E ⊆ P(V ). To each query φ, one can associate an hypergraph H = (V , E) whose vertex set is the set var(φ) of variables of φ and hyperedge set is atom(φ) the set of atoms of φ.

Queries. A query is said to be self-join free if no relation symbol is used more than once. A query is Boolean if it has no free variables that is free(φ) = ∅.

Acyclic conjunctive queries

A join tree of an hypergraph H = (V , E) is a tree T whose set of nodes is E the hyperedge set of H and whose edge set is such that:

• for all v ∈ V , {e ∈ E : v ∈ e} the set of nodes of T in which v occurs is a connected sub-tree of T .

A conjunctive query is said to be α-acyclic, for short acyclic, if its associated hypergraph has a join-tree. The class of acyclic queries is denoted by ACQ. There are several notion of acyclicity for hypergraphs (see [START_REF] Beeri | On the Desirability of Acyclic Database Schemes[END_REF][START_REF] Fagin | Degrees of acyclicity for hypergraphs and relational database schemes[END_REF]), α-acyclicity being the most general and admitting a number of alternative characterizations.

Example 4.1. The (path) query φ 1 (x, y, z) := E(x, y) ∧ E(y, z) is acyclic. The (triangle) query φ 2 (x, y, z) := E(x, y) ∧ E(y, z) ∧ E(z, x) is not acyclic. However, the more complex query φ 3 (x, y, z) := E(x, y) ∧ E(y, z) ∧ E(z, x) ∧ T (x, y, z) is acyclic: It admits a join tree with root {x, y, z} that contain as three children {x, y}, {y, z} and {z, x }.

Although this is a large class of queries, acyclic conjunctive queries are sufficiently restricted to obtained quite efficient algorithms as shown in the well-known result below. 4.1.1 Efficient enumeration : from linear to constant delay. Yannakakis result can be turned into an enumeration process that outputs the solution one after the other with a linear delay as remarked in [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF] and shown below.

Theorem 4.3 ([11]

). There is an algorithm which, upon input of a database D and φ ∈ ACQ, enumerates the set φ(D) with linear time preprocessing and linear time delay.

Proof. It is easy to see that Algorithm 2 outputs solutions with a linear delay between each. One needs Theorem 4.2, to prove linearity of the base case (p = 1). The proof follows by induction. □ Algorithm 2 Enumeration of φ(D)

1: if p = 1 then 2:
for a ∈ φ(D) do However, a delay which is linear in the size of the database delay between two solutions can hardly be considered has a very efficient time bound. It is easily seen, for example, that for quantifier free

x 1 , x 2 x 1 , y 1 x 2 , x 3
x 2 , x 3 , y 3 y 3 , y 4 , y 5

x 2 , y 2

Figure 1: A join tree for a query φ(x) ≡ ∃yR(x 1 , x 2 ) ∧ S(x 2 , x 3 , y 3 ) ∧ R(x 1 , y 1 ) ∧ T (y 3 , y 4 , y 5 ) ∧ S(x 2 , y 2 ). A new hyperedge {x 2 , x 3 } ⊆ {x 2 , x 3 , y 3 } is introduced that help forming the join tree above (the subtree of red nodes contains free variables only)

ACQ the delay can be made constant between two solutions. It turns out that constant delay can be achieved when free variables of a query can be grouped together while preserving acyclicity.. Definition 4.4. An acyclic conjunctive query φ(x) is free-connex if the extended query φ ′ (x) := φ(x) ∧ R(x) is acyclic, where R is an arbitrary new symbol.

Alternatively, given an acyclic query φ(x) with hypergraph H = (V , E), φ(x) is free-connex if the hypergraph H = (V , E ∪ {x}) is also acyclic. Note that boolean queries or queries with only one free variable are by definition free-connex. It is not the case for binary queries. The Boolean matrix multiplication query: Π(x, y) = ∃z A(x, z) ∧ B(z, y). Since Π ′ (x, y) = ∃z A(x, z) ∧ B(z, y) ∧ R(x, y) is clearly not acyclic, Π(x, y) is not free-connex.

It turns out that free-connexity is a sufficient restriction to put on acyclic conjunctive queries in order to obtained constant delay enumeration. To see this, remark that being free-connex intuitively permits to treat free variables together in an evaluation algorithm. Equivalently, given a free-connex φ(x) of hypergraph H = (V , E), it can be transformed into an equivalent query φ ′ (x) of hypergraph H ′ = (V , E ′ ) by possibly adding atoms/hyperedges e ′ ⊆ e ∈ E such that the associated join tree of φ ′ (x) contains as root a connected subtree made of free variables only (corresponding to a).

Figure 1 illustrates this property. Given query φ(x)

≡ ∃yR(x 1 , x 2 )∧ S(x 2 , x 3 , y 3 ) ∧ R(x 1 , y 1 ) ∧T (y 3 , y 4 , y 5 ) ∧ S(x 2 , y 2 ), one can introduce a new atom S ′ (x 2 , x 3 ) such that φ(x) ′ ≡ φ(x) ∧ S ′ (x 2 ,
x 3 ) has the described rooted join tree. Given a database D, To enumerate φ(D), one first applies the bottom-up Yannakakis algorithm for acyclic conjunctive query as precomputation steps to filter relations by projecting out existentially quantified variables until only the join R(x 1 , x 2 ) ∧ S ′ (x 2 , x 3 ) remains to be evaluated on the filtered relations. More precisely, one successively computes:

• From here, after sorting R on its second coordinate and S ′ on its first coordinate, enumerating the results i.e. the (a, b, c) s.t. (a, b) ∈ R and (b, c) ∈ S ′ can be easily done with constant delay. This approach yields to the following result.

Theorem 4.6 ([11]

). There is an algorithm which, upon input of a database D and a free-connex acyclic conjunctive query φ, enumerates the set φ(D) with linear-time preprocessing and constant-time delay.

4.1.2 Matching lower bounds. In [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF], it is also proved that, when looking at acyclic conjunctive queries, free-connex is what is needed to obtain constant delay enumeration, assuming some reasonable algorithmic hypothesis.

The Boolean matrix multiplication is the problem defined as follows: given two n × n Boolean matrices A and B, compute their product A × B. This is the problem defined by query Π(x, y) in Example 4.5. Suppose D BM is a database of domain

[n] with binary relations R A , R B such that for all a, b ∈ [n], (a, b) ∈ R A (resp. R B )
iff there is a 1 in line a, column b of matrix A (resp. B). If, on any such D BM , there exists a constant delay algorithm to enumerate Π(D BM ), then, computing the product A×B would need only O(n 2 ) steps.

So far, the best known algorithm for matrix multiplication (based on the Coppersmith-Winograd algorithm [START_REF] Coppersmith | Matrix Multiplication via Arithmetic Progressions[END_REF]) requires than O(n ω ) with ω = 2.37 steps [START_REF] Francois | Powers of tensors and fast matrix multiplication[END_REF]. We call Mat-Mul the widely believed hypothesis that given two such A and B their product can not be computed in quadratic O(n 2 ) time.

In [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF], it is proved, by reduction, that a (self-join free) query that is not free-connex is at least as hard as query Π(x, y). Indeed, let φ(x) ∈ ACQ such that φ is not free-connex. By definition ar(φ) = m ≥ 2. Let n ∈ N and D BM as above. One can construct a database D, on domain {0, ..., n -1} ∪ {⊥} where ⊥ is new symbol, in time linear in ||D BM || such that, up to reordering of variables:

φ(D) = Π(D BM ) × {⊥} m-2
Hence, there is a one-one mapping from φ(D) to Π(D BM ).

Example 4.7. Recall Π(x, y) ≡ ∃z A(x, z) ∧ B(z, y). Let φ(x) ≡ E(x 1 , x 4 ) ∧ S(x 1 , x 1 , x 3 ) ∧ T (x 3 , x 2 , x 4 ). Variable x 1 , x 2 can play the role of x, y in Π(x, y) and x 3 that of z. Database D contains the relations:

E = {(a, ⊥) : a ∈ [n]}, S = {(a, a, b) : (a, b) ∈ A}, T = {(b, c, ⊥) : (b, c) ∈ B}.
The result below formalizes the above discussion. The hardness part of the above characterization can be extended beyond acyclic queries. An hypergraph H is k-uniform if all its hyperedges contain k vertices. An l-hyperclique in a k-uniform hypergraph H is a set V ′ of l > k ≥ 2 vertices, such that every subset of V ′ of size k forms a hyperedge. Finding such an l-hyperclique is conjectured to require more than n k -o (1) (see [START_REF] Lincoln | Tight Hardness for Shortest Cycles and Paths in Sparse Graphs[END_REF]). We refer to the hypothesis that finding a k-hyperclique in a (k -1)-uniform hypergraph H can not be done in O(n k -1 ) as Hyperclique (for k = 3, seeing 2-uniform hypergraphs as graphs, this amounts to find a triangle in a graph in time O(n 2 )). In [START_REF] Brault-Baron | De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre[END_REF], it is shown that assuming Hyperclique, no cyclic query can be enumerated with linear time preprocessing and constant delay. Combining the results of [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF][START_REF] Brault-Baron | De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre[END_REF] we get that assuming both Mat-Mul and Hyperclique, Theorem 4.8 can be generalized to any self-join free φ ∈ CQ. Theorem 4.9 ([11, 18]). Assuming Mat-Mul and Hyperclique, for any self-join free φ ∈ CQ:

• either φ is free-connex and enum•φ ∈ Constant-Delay lin ,

• or enum•φ Constant-Delay lin

Union of conjunctive queries

Definition 4.10. A formula φ(x) is a union of conjunctive query, denoted UCQ, if it is of the form

φ = φ 1 ∨ • • • ∨ φ k where each φ i ∈ CQ, i ≤ k. Let φ = φ 1 ∨ • • • ∨ φ k ∈ UCQ. If each φ i ∈ ACQ is
free connex, it can been shown using technics developed in [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF] that enum•φ ∈ Constant-Delay lin .

However, as remarked in [START_REF] Carmeli | On the Enumeration Complexity of Unions of Conjunctive Queries[END_REF], efficient enumeration can be obtain for union of queries even though some of them are not efficiently enumerable. One can easily anticipate the following situation, given two queries φ 1 (x), φ 2 (x) and a database D:

• φ 2 (D) can be enumerated easily (say constant delay)

• φ 1 (D) can not be enumerated easily (is not free-connex for example) • But each solution of φ 1 (D) can be obtained by constant time computation from some solution of φ 2 (D) In that case enumerating (φ 1 ∨ φ 2 )(D) can be enumerated with constant delay. Indeed, let's consider the following example:

φ 1 (x, y, w) = R 1 (x, z) ∧ R 2 (z, y) ∧ R 3 (x, w) φ 2 (x, y, w) = R 1 (x, y) ∧ R 2 (y, w) (1)
Query φ 2 is free-connex while φ 1 is not. However, for any database D, one remark that any solution of φ 1 (D) can be built from a solution of φ 2 (D): for a tuple (a, b, c) to be in φ 1 (D), there should be an element d in the domain such that (a, d, b) ∈ φ 2 (D). Hence, to enumerate the union, one can proceed as follows: each time a solution (a, d, b) is produced, one look for all c such that R 3 (a, c) is true and enumerate all tuples (a, b, c). No solution of φ 1 (D) will be missed and since φ 2 (D) can be enumerated with constant delay, the total delay for the enumeration of the union can be preserved to be constant (though one also has to deal with duplicates also which can be done. See [START_REF] Carmeli | On the Enumeration Complexity of Unions of Conjunctive Queries[END_REF]). Such an example shows that charting the tractability frontier for union of conjunctive queries is a challenging task.

In [START_REF] Carmeli | On the Enumeration Complexity of Unions of Conjunctive Queries[END_REF] some partial answers to the problem are given. One key concept it that of a query providing variables to some other. • There is a body-homomorphism h from φ 2 to φ 1 i.e. h : var(φ 2 ) → var(φ 1 ) such that for every atom R

(x) ∈ atom(φ 2 ), R(h(x)) ∈ atom(φ 1 ) • h -1 (V 1 ) ⊆ free(φ 2 ) • There is h -1 (V 1 ) ⊆ S ⊆ free(φ 2 ), such that φ 2 is S-connex.
Going back to Equation 1, it is easy to see that φ 2 provides variable set {x, z, y} to φ 1 .

Let us now consider a query φ + 1 (x, y, w) obtained from φ 1 (x, y, w) adding the variables provided by φ 2 (x, y, w) in a new atom P 1 (x, z, y):

φ + 1 (x, y, w) = R 1 (x, z) ∧ R 2 (z, y) ∧ R 3 (x, w) ∧ P 1 (x, z, y). Obviously φ + 1 (x, y, w) is free-connex.
The idea behind this example can be formalized. Given φ = k i=1 φ i ∈ UCQ, with each φ i (x) = h j=1 R j (x j ), a union extension of φ(x) is a syntactic enrichment of the following form:

φ + i (x) = h j=1 R j (x j ) ∧ s j=1 P j (v j )
where each P 1 , ..., P s is a fresh relational symbol and each {v j } is provided to φ i by some φ j (or, more generally, by way of recursion, by a union extension of some φ j ).

Definition 4.12.

Given φ = φ 1 ∨ • • • ∨ φ k ∈ UCQ, query φ is free- connex if each of φ i , i = 1, ...

, k admits a union extension which is free-connex

Building on this, it can be proved that: Theorem 4.13 ([22]). Let φ ∈ UCQ. If φ is free-connex then enum• φ ∈ Constant-Delay lin .

Complete characterizations have been obtained in case φ is the union of two intractable CQ or the union of two particular acyclic conjunctive queries (called Body isomorphic), see [START_REF] Carmeli | On the Enumeration Complexity of Unions of Conjunctive Queries[END_REF]), some lower bound can be proved and it can be shown that free-connexity fully captures tractability. However, proving a full classification for UCQ is an open problem.

Allowing comparisons and disequalities

For numerical data, it could be interesting to extend ACQ by adding comparisons operators such as <, ≤, . In this section, we examine the effect in terms of expressive power of adding such features. Definition 4.14. Let ◁ ∈ {≤, <, }. A formula φ(x) is an acyclic conjunctive query with comparisons in S, i.e. is in ACQ ◁ , if it is of the form:

φ(x) := ∃y ϕ(x) ∧ i z i ◁ z ′ i
where ϕ(x) is an acyclic conjunctive query, each z i , z ′ i are variables among x and y.

In the definition above, comparisons are not taken into account to measure acyclicity. Interpretation of <, ≤, on a database with domain [n] has its obvious meaning.

In [START_REF] Papadimitriou | On the complexity of database queries[END_REF], an interesting example is given that emphasizes the gain of expressive power compared to ACQ when considering ACQ < .

Let G = (V , E) be a graph with V = {0, ..., n -1} (hence implicitly ordered) and k ∈ N. Let D be a database with binary relations P and R over a domain D containing all integers (i + j)n 3 + |ij |n 2 +bn +i for i, j ∈ V and b = 0, 1. Let us denote [i, j, b] such an element of the domain. Let relation P and R be defined as:

• P([i, j, 0], [i, j, 1]) iff (i, j) ∈ E, for all i, j ∈ V (it is also supposed that E has self-loops for each i ∈ V ) • R([i, j, 1], [i, j ′ , 0]) for all i, j, j ′ ∈ V Being a clique can not be defined directly without introducing a cycle. Instead, one plays with the underlying order and define the following φ over existentially quantified variables x i j , y i j for 1 ≤ i, j ≤ k as: 1≤i, j ≤k

P(x i j , y i j )∧ 1≤i, j,l =i+1≤k R(y i j , x il )∧ 1≤i <j ≤k x i j < x ji < y i j
The query φ is clearly acyclic: it consist in k paths of length 2k -1 connecting each x i1 , y i1 , x i2 ,..., y ik . Considered separately, even the graph of comparisons is acyclic. However, it can be shown that:

G has a clique of size k iff D |= φ.

One direction is obvious

: if v 1 , v 2 , v k form a clique in G with v 1 < v 2 < ... < v k . Interpreting x i j by [v i , v j , 0] and y i j = [v i , v j , 1]
the formula is trivially satisfied. For the other direction, one can deduce from the inequalities that, for each i < j if x i j , y i j , x ji , y ji are respectively interpreted by

[v i , v ′ j , 0], [v i , v ′ j , 1], [v j , v ′ i , 0] and [v j , v ′ i , 1] then v i = v ′ i and v j = v ′ j .
Then, the satisfaction of each P(x i j , y i j ) implies that each (v i , v j ) ∈ E and the vertices v 1 , ..., v k form a clique. Formally, this helps proving the following result. Theorem 4.15 ([69]). Evaluating queries in ACQ < and ACQ ≤ is W [1]-complete for both the size of the query and its number of variables as parameters.

However, allowing disequalities only, i.e. atoms of the form x y, leads to a different situation. In [START_REF] Papadimitriou | On the complexity of database queries[END_REF], it is also shown that evaluating a query φ ∈ ACQ on a database D is in FPT with the query size as parameter. More precisely, it can be done in time:

f (||φ||) • ||φ(D)|| • ||D|| • log 2 ||D||. for some function f such that f (||φ||) ≤ 2 O (v log v)
• ||φ|| where v is the number of variables of φ. Surprisingly, using combinatorial arguments, it can be shown that free connexity is still the criteria for fast enumeration even in the the presence of disequalities. A convenient way to see this is through, again, a mechanism of quantifier elimination. One can at the same time eliminate variables and disequality constraints. Let us illustrate the method.

A database D on domain D and relations R 1 , . . . , R s can be seen as a functional structure F = ⟨F ; D, D 1 , . . . , D s , f 1 , . . . , f p ⟩ where p = max i ≤s ar(R i ) and : • For 1 ≤ j ≤ p, f j is a unary function: D ′ → D ∪ {⊥} such that, for every t = (t 1 , . . . , t a i ) ∈ D i , we have f j (t) = t j for 1 ≤ j ≤ a i and a i = arR i , and f j (t) = ⊥ otherwise. Any conjunctive acyclic query with or without disequalities can be transformed into an acyclic conjonctive query (in the graph sense) for this functional representation of data. Indeed, consider the following acyclic queries:

φ(x, y, z) ≡ ∃tR 1 (x, y) ∧ R 2 (y, z) ∧ R 3 (x, z, t) ∧ R 4 (x, y, z, t) ϕ(x, y, z) ≡ φ(x, y, z) ∧ y z ∧ y t ∧ z t
Let T be a join tree for φ. For each atomic subformula A i in φ, one introduce a variable e i and for each connected pair of vertices (A i , A j ) in T , one describe the variables A i and A j have in common by introducing projection functions f 1 , ..., f 4 . The following functional query φ ′ (x, y, z) can be built.

φ ′ (x, y, z) ≡ ∃e 1 e 2 e 3 e 4 D 1 (e 1 ) ∧ D 2 (e 2 ) ∧ D 3 (e 3 ) ∧ D 4 (e 4 )∧ f 1 (e 1 ) = x ∧ f 2 (e 1 ) = y ∧ f 2 (e 2 ) = z∧ f 1 (e 1 ) = f 1 (e 4 ) ∧ f 2 (e 1 ) = f 2 (e 4 )∧ f 1 (e 2 ) = f 2 (e 4 ) ∧ f 2 (e 2 ) = f 3 (e 4 )∧ f 1 (e 3 ) = f 1 (e 4 ) ∧ f 2 (e 3 ) = f 3 (e 4 ) ∧ f 3 (e 3 ) = f 4 (e 4 )
Similarly, ϕ ′ above is the result of the transformation of ϕ:

ϕ ′ (x, y, z) ≡ φ ′ (x, y, z)∧ f 1 (e 1 ) f 2 (e 1 ) ∧ f 2 (e 1 ) f 2 (e 2 ) ∧ f 2 (e 2 ) f 1 (e 1 )
To each query φ of functional signature σ , one can associate its underlying graph G = (V , E) with V = var(φ) and E defined by (x, y) ∈ E iff there exists an atomic formula (x) = д(y) for f , д ∈ σ . A query will be called acyclic if its associated graph is a tree. The graph of formula φ ′ (x, y, z) (and ϕ ′ (x, y, z)) above is easily seen to be acyclic. It is easily seen that a conjunctive query is acyclic, its functional translation is.

Inequality (≤, <) constraints may force a relative ordering between the possible range of the variables and then permit to express global constraints (recall the definition of the k-clique problem by acyclic queries with inequality). By contrast, disequalities only introduces exception in the possible interpretations: a constraint such as x y only says that among the possibly large interpretation set for x and y, one must choose distinct values. Even repeated for all pairs of variables, this could be handled by combinatorial arguments that carry on the formula only. This idea can be handled through the notion of cover of a table below. Definition 4.16. Let E, F be two finite sets and f a tuple of k functions s.t.

f : E → F k . A cover c of a table (E, f) is a tuple (c 1 , . . . , c k ) ∈ (F ∪ {⊔}) k such
that, for all x ∈ E, there exists some i ≤ k, such that c i = f i (x). We denote by covers(E, f) the set of covers of (E, f).

Covers can be compared according to the following definition. Definition 4.17. A cover c ′ is more general than a cover c, denoted

c ′ ≤ c if, for all i ≤ k, either c i = c ′ i or c ′ i = ⊔. A cover c of a table (E, f) is minimal if this table has no more general cover. Example 4.18. Provided c ′ = (2, 1, ⊔) and c = (2, 1, 1) are covers of a set E by a triple f = (f 1 , f 2 , f 3 ) then, c ′ is more general than c.
The minimal cover set min-covers(E, f) is the set of all minimal covers of of (E, f).

A representative set of (E, f) is a subset E ′ ⊆ E such that covers(E, f) = covers(E ′ , f).
Example 4. [START_REF] Capelli | Structural restrictionsof CNF-formulas: applications to model counting and knowledge compilation[END_REF]. Let E = {a, b, c, d, e}, F = {1, 2, 3, 4, 5} and f = (f 1 , f 2 , f 3 ) be the following tuple of unary functions over E:

f 1 f 2 f 3 f 4 a 1 2 4 5 b 1 5 1 5 c 3 2 4 5 d 3 5 3 5 e 5 2 4 5 f 2 2 4 5
The complete cover set of f over T (E, f) contains 64 tuples, that is the following tuples: (1, 2, 3, * 4 ), (1, 5, 4, * 4 ), (3, 2, 1, * 4 ), (⊔, 5, 4, * 4 ) and ( * 1 , * 2 , * 3 , 5) where * 1 ∈ {⊔, 1, 2, 3, 5}, * 2 ∈ {⊔, 2, 5}, * 3 ∈ {⊔, 1, 3, 4} and * 4 ∈ {⊔, 5} (a rough count gives 68 = 2+2+2+2+60 but 4 of them are counted twice). The (smaller) minimal cover set of (E, f) is of size 4:

{(1, 2, 3, ⊔), (3, 2, 1, ⊔), (⊔, 5, 4, ⊔), (⊔, ⊔, ⊔, 5)}. A representative set is {a, b, c, d}. Also, given a k-tuple c = (c 1 , ..., c k ) and i ∈ {1, ..., k}, c -i = (c 1 , .., c i-1 , c i+1 , ..., c k ). Similarly for f -i . Let a ∈ E, and i ∈ {1, ..., k }, let's denote E a i = {x ∈ E : f i (x) f i (a)}. Intuitively, E a i is what remains to be covered of E by c -i when c i = f i (a) has been chosen is some cover c.
The key remarks rely on the following easily proved combinatorial results. For every table (E, f):

(1) |min-covers(E, f)| ≤ k!.

Let E ∅ and a ∈ E. It is easily seen that, for all tuple c: c ∈ covers(E, f) iff there exists i ≤ k, s.t. c i = f i (a) and c -i ∈ covers(E a i , f -i ). When E a i = ∅, the cover can be completed by ⊔ to make it minimal. So, the number of minimal covers for (E, f) is bounded by д(k) verifying: д(0) = 1 and д(i

) = i • д(i -1) for i ≤ k, hence д(k) = k!.
(2) There exists a representative set of cardinality bounded by O(k!).

Easily seen by recursively choosing some a ∈ E at each step of the process described above. Let F be a functional structure. Let φ(x) be an acyclic conjunctive query with disequalities over a signature σ containing only unary function symbols. Let T be the associated tree of φ(x). Suppose φ(x) ≡ ∃zψ (x, z), that z is a leaf of T and y is a variable of x be the parent of z in T . Query φ(x) can be written as follows:

φ(x) ≡ ψ 0 (x)∧ ∃z(P(z)∧ 1≤i ≤m д i (z) = д ′ i (y)∧ 1≤i ≤k f i (z) f ′ i (x))
where each

д i , д ′ i , f i , f ′ i ∈ σ , P(z) is a subformula involving only z. Term f ′ i (x) stands for f ′ i (x j )
for some x j of x. Query φ(x) can be rewritten as:

ψ 0 (x) ∧ ∃z ∈ E(y) 1≤i ≤k f i (z) f ′ i (x)
where E(y) stands as a shortcut for P ∩ i ≤m д -1 i (д ′ i (y)). Note that a partition of the domain can be obtained using pairwise distincts E(y), y ∈ Dom(F). Then, the query can be expressed as:

ψ 0 (x) ∧ f ′ (x) cover(E(y), f).
Considering E ′ (y) a minimal representative set of (E(y), f), query φ(x) can be equivalently seen as:

ψ 0 (x) ∧ f ′ (x) cover(E ′ (y), f) .
But each E ′ (y) is of size bounded by some h = O(k!). Hence, the database F can be enriched into a new database F ′ by adding a linear number of new information bits describing, for each a ∈ F , the content of the minimal representative set E ′ (a) and the full description of its minimal cover. More precisely, let

E j , f i, j , i = 1, ..., k, j = 1, ..., h • y ∈ E j ⇔ |E ′ (y)| ≥ j; • v j (y) is the j t h element of E ′ (y) if |E ′ (y)| ≥ j; otherwise it is an arbitrary value ; • set f i, j = f i • v j . This yields a new formula φ ′ ( x) equivalent to φ(x) φ ′ (x) ≡ 1≤j ≤h ψ j (x) where ψ j (x) ≡ ψ 0 (x) ∧ E j (y) ∧ 1≤i ≤k f i, j (y) f ′ i (x).
Hence, φ(x) can be rewritten into φ ′ (x) a union of acyclic conjunctive queries without existentially quantified variable z such that:

φ(F) = φ ′ (F ′ ).
Database F ′ can be obtained in linear time in ||F||. By iterating this process on Boolean query with a richer one can obtain a union of acyclic and quantifier free conjunctive queries. More generally, the total time to compute the result of an ACQ query can be lowered to:

f (||φ||) • ||φ(D)|| • ||D||.
for some function f and the enumeration of the result can be done in linear (in the size of the database) delay. Combining with methods of theorem 4.8, the following holds. Theorem 4.20 ([11]). Assuming Mat-Mul, any self-join free query φ ∈ ACQ can be enumerated with linear-time preprocessing and constant-time delay if and only if it is free-connex.

Note that the result above implies that for free-connex acyclic queries with inequalities the total time for query answering is

f (||φ||) • (|φ(D)| + ||D||).
Additional extensions for enumeration. Numerous other variants of CQ have been considered from the point of view of enumeration. For example : extensions of CQ with functional dependencies [START_REF] Carmeli | Enumeration Complexity of Conjunctive Queries with Functional Dependencies[END_REF], tree like databases with X properties [START_REF] Bagan | Efficient Enumeration for Conjunctive Queries over X-underbar Structures[END_REF] , random acces random order enumeration for [START_REF] Carmeli | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration[END_REF]. A much thorough review of constant delay enumeration can be found in [START_REF] Berkholz | Constant delay enumeration for conjunctive queries: a tutorial[END_REF].

Counting results of ACQ queries

We consider here the counting problem, denoted ♯CQ, associated to conjunctive query answering, that is: given φ ∈ CQ, given a database D, return |φ(D)| i.e. the number of solutions of query φ over D. Such task is usually harder than deciding. However, as shown in this section, large islands of tractability can be found and the frontier between tractable and intractable problems be delineated.

As a generalization of #3SAT, it is easy to see that counting solutions to quantifier free conjunctive queries, for short the ♯CQ 0 problem, which correspond to queries without projections in the database view, is ♯P-complete. The effect of adding existential quantification (i.e. projections) really increases the expressive power: it is proved that counting solutions of general conjunctive queries becomes even harder than ♯P and that ♯CQ is ♯•NP-complete [START_REF] Bauland | An Algebraic Approach to the Complexity of Generalized Conjunctive Queries[END_REF].

What is the situation for acyclic queries? We first present a tractability result that also hold in the more general context, introduced below, of weighted counting. Let F be a field and D be a finite structure of domain D. A F-weight function for D is a mapping w : D → F. If a is a tuple of elements of D of length k, the weight of a is

w(a) = k i=1 w(a i ).
The weighted counting problem for CQ, denoted ♯ F CQ, is the following problem: given φ ∈ CQ, given D and an F-weighted function w, return the sum of the weights of all solutions, i.e., the value of a∈φ(D) w(a).

When φ is acyclic the counting and the weighted counting problems are respectively denoted by ♯ACQ and ♯ F ACQ.

Not too surprisingly, the weighted counting problem associated to projection (i.e. quantifier) free acyclic query ♯ F ACQ 0 is tractable in a very strong sense (one suppose that, in F, arithmetic operations can be handled in polynomial time). Theorem 4.21. The combined complexity of ♯ F ACQ 0 is polynomial time see [START_REF] Durand | The complexity of weighted counting for acyclic conjunctive queries[END_REF]). In particular, there is an algorithm that upon input a quantifier free acyclic query φ and a database D, output |φ(D)| in time O(||φ|| • ||D|| 2 ) (see [START_REF] Pichler | Tractable counting of the answers to conjunctive queries[END_REF]).

More surprisingly, the effect of adding even a single existential quantification to acyclic queries results in a huge gain of expressive power. Let G = (V , E) be a bipartite graph V = A ∪ B, A = {a 1 , ..., a n }, B = {b 1 , ..., b n }. Let's consider the following queries (a 1 , ..., a n can be viewed as constants):

φ(x 1 , ..., x n ) = n i=1 E(a i , x i ), ψ (x 1 , ..., x n ) = ∃t n i=1 E(a i , x i )∧E(t, x i ) (2)
A careful analysis shows that the number of perfect matchings in G is equal to Consequently, the combined complexity for counting ACQ is #P-complete [START_REF] Pichler | Tractable counting of the answers to conjunctive queries[END_REF] and, as shown by the preceding example, even if the query as only one quantified variable. To summarize: Theorem 4.22. The combined complexity of

|φ(G)| -|ψ (G)|.
• ♯CQ 0 and ♯ACQ are ♯P-complete [START_REF] Pichler | Tractable counting of the answers to conjunctive queries[END_REF] • ♯CQ is ♯•NP-complete [START_REF] Bauland | An Algebraic Approach to the Complexity of Generalized Conjunctive Queries[END_REF] A particularity of formula ψ (x) in Equation 2is that the free variables are not connected to each other and the hypergraph (actually, a graph) of ψ (x) forms a star whose center is the unique quantified variable t. Elaborating on that remark, a new parameter, called quantifier-star size, was introduced in [START_REF] Durand | The complexity of weighted counting for acyclic conjunctive queries[END_REF], to measure how free variables are spread in the formula. This will be central to characterize tractability for counting.

Let φ(x) be an acyclic conjonctive query, H = (V , E) its associated hypergraph and S ⊆ V such that S = free(φ). We suppose to allege the notation that there is no edges e ∈ E such that e ⊆ S i.e. fully included in the free variables set S. For E ′ ⊆ E, the hypergraph induced by

E ′ is H [E ′ ] = ( e ∈E ′ e, E ′ ). For V ′ ⊆ V , H [V ′ ] = (V ′ , {e ∩ V ′ | e ∈ E,
e ∩ V ′ ∅}). For x, y ∈ V , a path between x and y is a subset of edges e 1 , ..., e k ∈ E such that x ∈ e 1 , y ∈ e k , and for all i ≤ k -1, e i ∩ e i+1 ∅. An independent set I of H is a subset of V such that for all x, y ∈ I there is no e ∈ E such that x ∈ E and y ∈ E.

A central notion in the following is that of S-component, defined in [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF]. A subhypergraph H ′ of H is an S-component if there is an edge e ∈ E ⊈S such that H ′ is the S-component of e.

Example 4.24. In Figure 2 an hypergraph H of an acyclic conjunctive query φ(y) is given with S = free(φ) = {y 1 , ..., y 7 }. It has three S-components are illustrated by Figure 3.

Given S ⊆ V , one can decompose H = (V , E) into disjoint S-components. A measure how S vertices are "spread" into each components through the notion of independence. [START_REF] Durand | The complexity of weighted counting for acyclic conjunctive queries[END_REF]). Let H = (V , E) be a hypergraph, S ⊆ V . and k ∈ N. The S-star size of H is the maximum size of an independent set of an S-component of H . Definition 4.26 (quantified-star size [START_REF] Durand | The complexity of weighted counting for acyclic conjunctive queries[END_REF]). The quantified star size of an acyclic conjunctive formula φ(x) is the S-star size of the hypergraph H associated to φ(x), where S is the set of free variables in ϕ(x).

Note that being of quantified star size 1 is equivalent to being free-connex. A class C of acyclic conjunctive queries is of bounded quantified star size if there is a s ∈ N such that every φ ∈ C is of quantified-star size bounded by s.

Example 4.27. In Figure 3, the maximal size of an independent set among all S-components is three. For example : {y 3 , y 5 , y 6 }. Similarly, the quantified star size of formula ψ (x) in Equation 2is n, the domain size of the database.

To understand why the decomposition into S-components has influence on the complexity, let us make several remarks:

• A query φ(x) can be decomposed into φ 1 ∧φ 2 ∧ • • • ∧φ m ∧ψ 0 where m is the number of S-components of it associated hypergraph and ψ 0 is a subformula containing free variables only. • Let i ∈ {1, .., n} and suppose subquery φ i is of maximal quantified-star size s ∈ N. Then, it is not hard to see there exists ϕ 1 , ..., ϕ s atomic formulas of φ i that contains all the free variables free(φ i ) (recall s is the size of the maximal independent set in the S-component associated to φ i ). • Since all free variables of φ i are packed into at most s atomic formulas, given a database D and using technics similar to Yannakakis algorithm one can built a new relation R i = φ i (D) in time O(||D|| s ) and replace each φ i by a new atomic formula ψ i on free variables only. Let's call D ′ the collection of all relations R i • Now the query ψ = ψ 1 ∧ ψ m ∧ ψ 0 is acyclic and is such that ψ (D ′ ) = φ(D). One conclude using Theorem 4.21.

The arguments above give the basic intuition of the result below. The hardness result can be proved by reduction.

Theorem 4.

([34]

). There is an algorithm for the problem ♯ACQ that runs in time (||D|| + ||φ||) O (k ) where k is the quantified star size of the input query Φ. Moreover, if a class of acyclic conjunctive queries does not have a bounded quantifier-star size, then its associated counting problem is #W [START_REF] Amarilli | A Circuit-Based Approach to Efficient Enumeration[END_REF] hard. It is therefore not FPT The quantified star size of a query φ can be computed in polynomial time. See [START_REF] Chen | The logic of counting query answers[END_REF][START_REF] Durand | Structural Tractability of Counting of Solutions to Conjunctive Queries[END_REF] for further use of this measure for the counting complexity of CQ.

Allowing negations: from queries to CSP

A natural extension is to allow negations of atoms in conjunctive queries. However such a possibility results in a huge gain of expressive power even in contexts that were previously tractable. The main reason is related to its connexion with the satisfiability problem and the succinctness it permits. Consider, as an example, the Boolean clause:

x 1 ∨ x 2 ∨ x 3 ∨ x 4 ∨ ¬x 5 ∨ ¬x 6
Such a clause is satisfied by all possible assignments of x 1 , ..., x 6 except (0, 0, 0, 0, 1, 1). By allowing negations, we can see such a clause as the query that tests whether D = ¬R(x 1 , ..., x 6 ) where the domain of D is {0, 1} and R = {(0, 0, 0, 0, 1, 1)}.

It is then clear that α-acyclic queries can not be tractable. Indeed let φ(x) be any conjunctive query. Extending the notion of acyclicity to negative atoms as well, the query φ ′ (x) = φ(x)∧¬R(x) where R is a new relation symbol is acyclic. Upon a database D, defining D ′ as D extended with the empty relation R, it is clear that: φ(D) = φ ′ (D ′ ).

Tractability fragments have to be searched into a more restricted version of acyclicity for hypergraph: β-acyclicity. Definition 4.29. A query is β-acyclic if its associated hypergraph H is α-acyclic and all its subhypergraphs H ′ ⊆ H are also αacyclic. Definition 4.30. A negative conjunctive query, NCQ, over a signature σ is a formula of the form

φ(x) ≡ ∃y i ¬R i (z i )
where z i is a tuple of variables from x and y, R i ∈ σ . A NCQ query is β-acyclic if its associated hypergraph is β-acyclic.

We call Triangle the hypothesis that the existence of a triangle in a graph of n vertices can not be decided in time O(n 2 log n). The following result holds. Theorem 4.31 ([17]). Assuming Triangle, an NCQ is decidable in quasi-linear time iff it is β-acyclic.

Roughly speaking, an NCQ can be seen as a negative encoding of constraint satisfaction problems (CSP) in the context where the arity of constraints is not fixed (under the simpler form of a sat problem, each disjunctive clause is represented by a negative atom ¬R(x) for which the associated relation R contains only one element). To prove the quasi-linear time algorithm of Theorem 4.31 two main tools are used:

• the well-known Davis-Putnam resolution procedure that replace two clauses of the form C 1 ∨ x, C 2 ∨ ¬x, by their resolvent C 1 ∨ C 2 . • Hypergraphs that are β-acyclic can be characterized in terms of an an elimination ordering of their vertices (through the notion of nest point [START_REF] Duris | Some characterizations of γ and β -acyclicity of hypergraphs[END_REF]). This ordering will be used to drive the Davis-Putnam procedure in the choice of the resolvent variable.

Partial characterizations for the complexity of signed queries, i.e. of queries having both negative and positive atoms are given in [START_REF] Brault-Baron | De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre[END_REF].

Complexity issues for CSP, in particular their counting versions, based on formula restrictions has deserved a lot of attentions [START_REF] Sigve | Solving #SAT and MAXSAT by Dynamic Programming[END_REF][START_REF] Samer | Algorithms for propositional model counting[END_REF]. New measures based on hypergraph decompositions and interesting connexions with domains such as knowledge compilation have been established that have helped understanding where the frontier for tractability is (see [START_REF] Capelli | Structural restrictionsof CNF-formulas: applications to model counting and knowledge compilation[END_REF] for a survey and [START_REF] Capelli | Understanding the complexity of #SAT using knowledge compilation[END_REF] also for the special case of weighted counting for β-acyclic CSP).

PREFIX RESTRICTED QUERIES FOR COUNTING AND ENUMERATION

In this part we study the more unusual setting of FO with second order free variables. More precisely, we consider FO queries of the form φ(x, X) where x and X are respectively free first-order and second-order variables. Recalling Fagin's theorem [START_REF] Fagin | Generalized first-order spectra and polynomial-time recognizable sets[END_REF], it is clear that a such query language is highly expressive. One approach to find tractable fragments is to restrict the quantifier prefixes of formulas. For any k, the fragments Σ k and Π k of FO are the classes of all formulae in prenex normal form with a quantifier prefix with k alternations starting with an existential or an universal quantifier, respectively. When restricted to relations only as second order variables, we call this fragments Σ rel k , Π rel k . The well-known examples below shed some light on the expressiveness of queries under these restrictions.

Example 5.1. Let DNF (resp. 3DNF) be the problem of deciding if a propositional formula in disjunctive normal-form (resp. with at most 3 literals per clause) is satisfiable. Let σ 3DNF = (D 0 , D 1 , D 2 , D 3 ). Given a 3DNF-formula φ over variables V , we construct a corresponding σ -structure A φ with universe V such that for any x 1 , x 2 , x 3 ∈ V , D i (x 1 , x 2 , x 3 ) holds iff 1≤j ≤i ¬x j ∧ i <j ≤3 x j appears as a disjunct. Now consider the σ -formula Φ 0 (T ) below: Φ 0 (T ) ≡ ∃x∃y∃z D 0 (x, y, z) ∧ T (x) ∧ T (y) ∧ T (z) ∨ D 1 (x, y, z) ∧ ¬T (x) ∧ T (y) ∧ T (z) ∨ D 2 (x, y, z) ∧ ¬T (x) ∧ ¬T (y) ∧ T (z) ∨ D 3 (x, y, z) ∧ ¬T (x) ∧ ¬T (y) ∧ ¬T (z) Formula Φ 1 is in Σ rel 1 . Moreover, there is a bijection between the set of relations T such that A φ |= Φ 0 (T ) and the set of satisfying assignments of φ.

To express DNF, one can consider the language with predicate V for variables, D for disjunct (whose union represent the domain) and two predicate P(d, v) (resp. N (d, v)) representing the fact that variable v appears positively (resp. negatively) in disjunct D and write the following Φ 2 ∈ Σ rel 2 :

Φ 2 ≡ ∃d∃v D(d) ∧ (P(d, v) → T (v)) ∧ (N (d, v) → ¬T (v))

Example 5.2. The formula Ψ 0 ∈ Σ 0 and Ψ 1 ∈ Π rel 1 below express respectively the existence of a 3-clique (on an ordered graph) and of a clique:

Ψ 0 (v) ≡ v 1 < v 2 < v 3 ∧ E(v 1 , v 2 ) ∧ E(v 2 , v 3 ) ∧ E(v 3 , v 1 ) Ψ 1 (T ) ≡ ∀v 1 ∀v 2 T (v 1 ) ∧ T (v 2 ) → E(v 1 , v 2 )

Counting

In [START_REF] Saluja | Descriptive complexity of #P functions[END_REF], the prefix restricted approach has been used to characterized counting classes above ♯P.

#Σ rel 0 = #Π rel 0 ⊂ #Σ rel 1 ⊂ #Π rel 1 ⊂ #Σ rel 2 ⊂ #Π rel 2 = #FO rel = ♯P.
Moreover, every function in #Σ rel 0 is computable in polynomial time. In [START_REF] Arenas | Descriptive Complexity for counting complexity classes[END_REF] a quantitative extension of second-order logic, called QSO is defined that allow to use first-order and second-order sum and product as closure operators on top of second-order formulas. The restriction of QSO to first-order and second-order sum, called ΣQSO(FO), provides a hierarchy, ΣQSO(Σ rel i ), ΣQSO(Π rel i ) for i ≥ 0 similar (in spirit but different on the lowest classes) to the one of [START_REF] Saluja | Descriptive complexity of #P functions[END_REF]. In [START_REF] Durand | Descriptive Complexity of #AC 0 Functions[END_REF], an analog of [START_REF] Saluja | Descriptive complexity of #P functions[END_REF] that allows quantifications over functions too is studied. As expected the hierarchy is shorter :

#Σ 0 ⊂ #AC 0 ⊂ ⊂ #Σ 1 ⊂ #Π 1 = #FO = ♯P. (3)
where #AC 0 is the class of functions that computes the number of accepting proof trees of FO-uniform families of circuit (or similarly that counts the number of skolem functions for existentially quantified variables of a FO formula). Not surprisingly with counting problems, the classes in the hierarchies become expressive quite fast. For example, already #Σ rel 1 contains ♯P-complete problems (#3DNF in Example 5.1). However, for such functions, it can be worth to relaxe the constraint of exact and certain computations and look for algorithms that provide good approximations with high probability for them. This is done through the concept of randomized approximation that follows. Definition 5.4. Let f : {0, 1} * → N be a counting problem. f is said to have a fully polynomial-time randomized approximation scheme (FPRAS), if there is a randomized algorithm M working on inputs (x, ϵ) with x ∈ {0, 1} * , ϵ ∈ Q such that for all such inputs:

• Pr |M(x, )f (x)| > • | f (x)| < 1 4 , where M(x, ϵ) is the random variable describing the output of M on input (x, ϵ),

• the running time of M on input (x, ϵ) is bounded by a polynomial in |x |, 1 ϵ .

One early and celebrated FPRAS was obtained in [START_REF] Karp | Monte-Carlo Approximation Algorithms for Enumeration Problems[END_REF] for the problem ♯DNF. It served as an inspirational method for proving that #Σ rel 1 (and even some syntactic extension of it) admits a FPRAS. It is also the case for the distinct classes: #Σ 1 (from [START_REF] Durand | Descriptive Complexity of #AC 0 Functions[END_REF]) and ΣQSO(Σ rel 1 ) (from [START_REF] Arenas | Descriptive Complexity for counting complexity classes[END_REF]). Finding good approximation algorithms for aggregate functions (and the related problem of random algorithm for uniform generation) has deserved even more attention recently (see for example [START_REF] Arenas | Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation[END_REF]) although it is not clear yet if classes that admit FPRAS can be characterized.

Enumeration

One can define similarly enumeration classes related to prefix restricted classes of queries. Given a class L , enum • L notes the collection of enum•φ problems for φ ∈ L . In [START_REF] Durand | Enumeration Complexity of Logical Query Problems with Second-order Variables[END_REF], a characterization of an hierarchy of enumeration problems is given. Theorem 5.5 ([37]). On linearly ordered structures, the following hold:

enum•Σ 0 ⊊ enum•Σ 1 ⊊ enum•Π 1 ⊊ enum•Σ 2 ⊊ enum•Π 2 .

Moreover:

• enum•Σ 0 can be enumerated with polynomial time precomputation and constant delay • enum•Σ 1 can be enumerated with polynomial delay • enum•Π 1 can not be enumerated with polynomial delay unless P = NP.

Since a formula φ(x, X) ∈ Σ 0 has second-order free variable the constant delay bound is questionable at first sight. The algortihmic model used is the following: it has an output tape on which the current output is written. During the enumeration phase the algorithm only modifies the content of this tape to transform the previous solution into a new one. In the Σ 0 case, by relating to the well-known problem of Gray code enumeration, one can find an enumeration ordering such that the delta between two consecutive solutions only affects a constant part of the output and thus can be performed in constant time resulting in a procedure with delta-constant delay (see also [START_REF] Arenas | Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation[END_REF] for additional results on the subject).

CONCLUSION

In this paper we have presented a subjective panorama on the complexity of query evaluations. We have put the focus on new complexity measures that have been introduced (in particular to deal with enumeration), structural decompositions and parameters that allows to design efficient algorithms and conditional lower bounds.

We have considered various algoritmic task related to query answering such as decision, computation of the answer set, counting, enumeration. Some new framework such as query evaluation under updates (see [START_REF] Amarilli | Uniform Reliability of Self-Join-Free Conjunctive Queries[END_REF][START_REF] Berkholz | Answering Conjunctive Queries under Updates[END_REF][START_REF] Berkholz | Answering UCQs under Updates and in the Presence of Integrity Constraints[END_REF][START_REF] Idris | The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates[END_REF][START_REF] Idris | Conjunctive Queries with Inequalities Under Updates[END_REF]) for which counting or enumerating make sense, have been ignored in the paper. They have developped so deeply in the last years that they deserve independent surveys.

A

  signature σ is a finite set of relation R and function f symbols, each of them associated with a fixed arity ar(R), ar(f ) ∈ N. The arity of σ , is the maximal arity of its symbols. A structure D over σ , or a σ -structure (σ is omitted when it is clear from the context) consists of a non-empty finite set Dom(D) (often D, for short) called the domain of D, an ar(R)-ary relation R D ⊆ Dom(D) ar(R) for each relation symbol R ∈ σ and ar(f )-ary function f D : Dom(D) ar(R) → Dom(D) for each function symbol f ∈ σ . When σ contains relation symbols only, a σ -structure is said to be relational. In most context below, a database is a finite relational structure. The cardinality of a finite set A is denoted |A|. We define the size ||D|| of D as ||D|| = |σ |+|Dom(D)|+ R ∈σ |R D |•ar(R). It corresponds to the size of a reasonable encoding of D. Also, ||φ|| denotes the size of φ i.e. the number of symbols necessary to describe φ.

2. 3 . 2

 32 Complexity measures for counting. Let Σ be an alphabet. A predicate B ∈ Σ * × Σ * is polynomially balanced if there exists c ∈ N such that, for all x, y ∈ Σ * , (x, y) ∈ B implies that |y| ≤ |x | c . Given a polynomially balanced binary predicate B ∈ Σ * × Σ * , the counting function associated to B, is the function ♯ •B : Σ * → N such that, for all x ∈ Σ * : ♯•B(x) = |{y : (x, y) ∈ B}|. Definition 2.1. ♯•P, or equivalently ♯P, (resp. ♯•NP) the class of counting functions associated to predicates B ∈ P (resp. B ∈ NP).

Theorem 4 . 2 (

 42 [START_REF] Yannakakis | Algorithms for Acyclic Database Schemes[END_REF]). There is an algorithm which, upon input of a database D and φ(x) ∈ ACQ, computes the set φ(D) in timeO(||φ|| • ||D|| • ||φ(D)||).

ψ 1 6 : 8 :

 168 (x 1 ) ≡ ∃x 2 . . . ∃x p φ(x 1 , . . . x p ) for a ∈ ψ (D) do 7: let φ a ≡ φ(a, x 2 , . . . , x p ) for b ∈ φ a (D) do 9: output (a, b)

Example 4 . 5 .

 45 The query: φ(x, y) = ∃w∃z E(x, w) ∧ E(y, z) ∧ B(z). is free-connex because the query φ ′ (x, y) = ∃w∃z E(x, w)∧E(y, z)∧ B(z) ∧ R(x, y) is still acyclic.

  S ← {(a, b, c) : there exists d, e : S(a, b, c) and T (c, d, e)} • S ′ ← {(a, b) : there exists c : S(a, b, c)} • R ← {(a, b) : there exists c : R(a, b) and R(a, c)} • R ← {(a, b) : there exists c : R(a, b) and S(b, c)}

Theorem 4 . 8 (

 48 [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF]). Assuming Mat-Mul, for any self-join free, φ ∈ ACQ the following statements are equivalent:• φ is free-connex,• there is an algorithm which, upon an input database D, enumerates the set φ(D) with linear-time preprocessing and constanttime delay, • there is an algorithm which, upon an input database D, computes the set φ(D) in time O(||D|| + ||φ(D)||)

Definition 4 . 11 .

 411 Let φ 1 , φ 2 ∈ CQ. Query φ 2 provides a set of variables V 1 to φ 1 if:

•

  D, D 1 , . . . , D s are disjoint unary relations so that the domain F of F is the disjoint union of D, D 1 , .., D s and {⊥} i.e. F = D ⊎ D 1 ⊎ . . . ⊎ D 1 ⊎ {⊥} • For each i = 1, . . . , s, D i is a set of elements representing tuples in R i , and ⊥ is an extra element.

9 Figure 2 :

 92 Figure 2: The hypergraph H of a query φ(y) with S = free(φ) = {y 1 , ..., y 7 }.

Definition 4 .

 4 23 (S-component). Let H = (V , E), S be as above. The S-component of e ∈ E is the hypergraph H [E ′ ] where E ′ is the set of all edges e ′ ∈ E ⊈S such that there is a path from e -S to e ′ -S in H [V -S].

9 Figure 3 :

 93 Figure 3: The decomposition of hypergraph H of Figure 2 into three edge distinct S-components. The central component (in yellow) contains an independent set of size 3 which is here the maximal size among all independent set of Scomponents

  Given a class L (here a prefix class) we denote by ♯L , the class of functions ♯•φ : D -→ |φ(D)| = |{(a, A) : D |= φ(a, A)}| for formulas φ(x, X) ∈ L . It holds that: Theorem 5.3 ([72]). On ordered structures: