Query evaluation is one of the most fundamental tasks of a database system. A large amount of the literature in database theory and the related field of finite or algorithmic model theory is devoted to designing efficient query evaluation algorithms and to pinpointing the exact computational complexity of the task. The query languages that have received the most attention are the conjunctive queries and the more expressive relational calculus. The latter is usually viewed as the “logical core” of SQL, and is equivalent to first-order logic FO. Here, one identifies a database schema and a relational database of that schema with a relational signature and a finite -structure .
Apart from computing the entire query result, the query evaluation tasks usually studied are model-checking (check if the answer of a Boolean query on a database is “yes”) and counting (compute the number of tuples that belong to the result of a non-Boolean query on a database
); the counting problem is also relevant as the basis of computing probabilities. Such a task is regarded to be tractable for a query languageL on a class of databases if it can be solved in time for an arbitrary function and a constant , where is the size of the input query and the size of the input database . The task then is called fixed-parameter tractable (fpt, or “in fpt”), and fixed-parameter linear (fpl, or “in fpl”) in case that .
It is known that on unrestricted databases model-checking is -hard for conjunctive queries , and the counting problem is -hard already for acyclic conjunctive queries . This means that under reasonable complexity theoretic assumptions, both problems are unlikely to be in fpt.
A long line of research has focused on identifying restricted classes of databases on which query evaluation is fixed-parameter tractable for conjunctive queries, FO, or extensions of FO. For example, model-checking and counting for FO (even, for monadic second-order logic) is in fpl on classes of bounded tree-width [3, 2]. Model-checking and counting for FO are in fpl on classes of bounded degree [22, 10], in fpl on planar graphs and in fpt on classes of bounded local tree-width [11, 10], and in fpl on classes of bounded expansion [6, 14].
Grohe, Kreutzer, and Siebertz  recently provided an fpt model-checking algorithm for FO on classes of databases that are effectively nowhere dense. This gives a fairly complete characterisation of the tractability frontier for FO model-checking, as it is known that under reasonable complexity theoretic assumptions, any subgraph-closed class that admits an fpt-algorithm for FO model-checking has to be nowhere dense [15, 6]. The notion of nowhere dense classes was introduced by Nešetřil and Ossona de Mendez  as a formalisation of classes of “sparse” graphs. The precise definition of this notion will be relevant in this paper only in Section 8; for now it should suffice to note that the notion is fairly general, subsumes all classes of databases mentioned above, and there exist nowhere dense classes that do not belong to any of those classes.
The counting problem on nowhere dense classes is known to be in fpt for purely existential FO , but no extension to full FO is known . Here, we obtain this extension as an immediate consequence of our technical main result. We study an extension of FO that allows to express cardinality conditions in a similar way as SQL’s COUNT operator. The corresponding logic was introduced by Kuske and Schweikardt , who showed that model-checking and counting for this logic is fixed-parameter linear on classes of databases of bounded degree. The starting point for the work presented in this paper was the question whether this result can be extended to other “well-behaved” classes of databases, such as the classes mentioned above.
Our first result is that the fixed-parameter tractability of cannot even be generalised to very simple classes of databases of unbounded degree such as unranked trees or strings with a linear order relation. Then, we identify a fragment of which still extends FO and is sufficiently strong to express standard applications of SQL’s COUNT operator. Our main result shows that model-checking and counting for is in fpt on nowhere dense classes of databases. More precisely, for any effectively nowhere dense class of databases we present an algorithm that solves the model-checking problem and the counting problem in time for a computable function and any , where is the size of the input query and is the size of the input database . Algorithms with such performance bounds are often called fixed-parameter almost linear. This generalises the result of  from FO to and solves not only the model-checking but also the counting problem.
Our proof proceeds as follows. First, we reduce the query evaluation problem for to the counting problem for rather restricted FO-formulas (Section 6). Combining this with the results on FO-counting mentioned above, we immediately obtain an fpt-algorithm for on planar graphs and classes of bounded local tree-width , of bounded expansion , and of locally bounded expansion . For nowhere dense classes, though, it is not so easy to generalise the FO model-checking algorithm of  to solve the counting problem. For this, we generalise the notion of “rank-preserving locality” of  from sentences to formulas with free variables and to counting terms (Section 7), which then enables us to lift the model-checking algorithm of  to an algorithm for the counting problem (Section 8).
The rest of the paper is structured as follows. Section 2 provides basic notations, Section 3 recalls the definition of of , Section 4 provides the hardness results for on unranked trees and strings with a linear order, Section 5 introduces and gives a precise formulation of our main result, and Section 9 points out directions for future work.
2 Basic notation
We write , , and for the sets of integers, non-negative integers, and positive integers, resp. For all , we write for the set , and we let . For a -tuple we write to denote its arity . By we denote the empty tuple, i.e., the tuple of arity 0.
A signature is a finite set of relation symbols. Associated with every relation symbol is a non-negative integer called the arity of . The size of a signature is the sum of the arities of its relation symbols. A -structure consists of a finite non-empty set called the universe of , and a relation for each relation symbol . Note that according to these definitions, all signatures and all structures considered in this paper are finite, signatures are relational (i.e., they do not contain constants or function symbols), and signatures may contain relation symbols of arity 0. Note that there are only two 0-ary relations over a set , namely and .
We write to indicate that two -structures and are isomorphic. A -structure is the disjoint union of two -structures and if , , and for all .
Let be a signature with . A -expansion of a -structure is a -structure such that and for every . Conversely, if is a -expansion of , then is called the -reduct of .
A substructure of a -structure is a -structure with universe and for all . For a -structure and a non-empty set , we write to denote the induced substructure of on , i.e., the -structure with universe , where for all .
Throughout this paper, when speaking of graphs we mean undirected graphs. The Gaifman graph of a -structure is the graph with vertex set and an edge between two distinct vertices iff there exists and a tuple such that . The structure is called connected if its Gaifman graph is connected; the connected components of are the connected components of .
The distance between two elements is the minimal number of edges of a path from to in ; if no such path exists, we let . For a tuple and an element we let . For every , the -ball of in is the set . The -neighbourhood of in is defined as .
Let vars be a fixed countably infinite set of variables. A -interpretation consists of a -structure and an assignment in , i.e., . For , for , and for pairwise distinct , we write for the assignment in with for all , and for all . For we let .
The order of a -structure is , and the size of is For a graph we write and to denote its vertex set and edge set, respectively. Sometimes, we will shortly write (or ) to denote an edge between the vertices and . The size of is . Note that up to a constant factor depending on the signature, a structure has the same size as its Gaifman graph.
3 Syntax and semantics of
In , Kuske and Schweikardt introduced the following logic and provided an according notion of Hanf normal form, which was utilised to obtain efficient algorithms for evaluating -queries on classes of structures of bounded degree. The syntax and semantics of is defined as follows (the text is taken almost verbatim from ).
A numerical predicate collection is a triple where is a countable set of predicate names, assigns the arity to every predicate name, and is the semantics of the predicate name . Basic examples of numerical predicates are , , , Prime with , , , . For the remainder of this paper let us fix an arbitrary numerical predicate collection that contains the predicate .
Definition 3.1 ().
Let be a signature. The set of formulas and counting terms for is built according to the following rules:
and are formulas, where and are variables111in particular, if , then is a formula
if and are formulas, then so are and
if is a formula and , then is a formula
if , , and are counting terms, then is a formula
if is a formula, , and is a tuple of pairwise distinct variables, then is a counting term
every integer is a counting term
if and are counting terms, then so are and
if and otherwise; if , and otherwise;
if , and otherwise
By we denote the union of all for arbitrary signatures . An expression is a formula or a counting term. As usual, for a formula and a -interpretation we will often write to indicate that . Accordingly, indicates that . If and are counting terms, then we write for the counting term .
The following -formula expresses that the sum of the numbers of nodes and edges of a directed graph is a prime:
The counting term denotes the out-degree of .
The -formula expresses that the out-degree of is . For better readability of such formulas we will often write “” instead of “”.
expresses that there is some number (represented by a node of out-degree ) such that the number of nodes of out-degree is a prime.
The construct binds the variable , and the construct in a counting term binds the variables from the tuple ; all other occurrences of variables are free. Formally, the set of free variables of an -expression is defined inductively as follows:
We will often write , for with , to indicate that at most the variables from are free in the expression . A sentence is a formula without free variables, a ground term is a counting term without free variables.
Consider an -counting term , for . For a -structure and a tuple , we write or for the integer , where is an assignment in with for all . For an -formula we write or to indicate that . In case that (i.e., is a sentence and is a ground term), we simply write instead of , and we write instead of .
Two formulas or two counting terms and are equivalent (for short, ), if for every -interpretation . The size of an expression is its length when viewed as a word over the alphabet .
4 The hardness of evaluating -queries
In  it was shown that on classes of structures of bounded degree, -query evaluation is fixed-parameter linear (when using oracles for evaluating the numerical predicates in ). In this section, we shall prove that there is no hope of extending this result to even very simple classes of structures of unbounded degree such as trees and words: on these classes, the evaluation problem is as hard as the evaluation problem for first-order logic on arbitrary graphs. The latter is known to be PSPACE-complete  and, in the world of parameterised complexity theory, complete for the class  (also see ). The hardness results hold for all that contain the “equality predicate” or the “positivity predicate” . The -hardness is the more relevant result for us here.222PSPACE-completeness already holds over a fixed structure with two elements. It shows that the evaluation problem is unlikely to have an algorithm running in time for an arbitrary function and constant , where is the size of the input formula and the size of the input structure.
To state our result formally, we focus on the model-checking problem, that is, the query evaluation problem for sentences. The model-checking problem for a logic L on a class of structures is the problem of deciding whether a given structure satisfies a given L-sentence . A polynomial fpt-reduction between two such problems is a polynomial time many-one reduction that, given an instance of the first model-checking problem, computes an instance of the second model-checking problem such that is polynomially bounded in and is polynomially bounded in .
There is a polynomial fpt-reduction from the model-checking problem for FO on the class of all graphs to the model-checking problem for on the class of all trees.
Let be a graph, and let be an FO-sentence in the signature of graphs (consisting of a single binary relation symbol ). W.l.o.g. we assume that for some . We shall define a tree and an -sentence such that satisfies if and only if satisfies . We construct the tree as follows. The vertex set consists of
a “root” vertex
a vertex for every
vertices and for every and
a vertex for every and every neighbour of in
vertices for every , every neighbour of in , and every .
The edge set of consists of
edges for all
edges and for all and
edges and or all , all neighbours of in , and all .
Then, is a tree (of height ) that can be computed from in quadratic time.
To define , we need auxiliary formulas , , …, defining the sets of -vertices, respectively. We start from the observations that the -vertices are the precisely those vertices of degree whose unique neighbour has degree . The vertices are the neighbours of the -vertices, and the -vertices are the neighbours of the -vertices that are not -vertices. The root vertex is the only vertex adjacent to all vertices. The -vertices are the vertices of degree that are not -vertices, and the -vertices are the neighbours of the -vertices.
Note that the vertices of are in one-to-one correspondence to the -vertices of : vertex corresponds to the unique -vertex with exactly -neighbours. To express that there is an edge between -vertices , we say that has a -neighbour such that the number of -neighbours of equals the number of -neighbours of . This is precisely what the following -formulas says:
Now we let be the formula obtained from by replacing each atom by and by relativizing all quantifiers to -vertices, that is, replacing subformulas by . Clearly, can be computed from in polynomial time. Moreover, it should be clear from the construction that satisfies if and only if satisfies . ∎
The parameterised model-checking problem for on the class of all trees is -complete.
We encode strings over the alphabet as structures of signature , where the binary relation is a linear order of , and the unary relation consists of the positions of all s in the string, for each symbol .
There is a polynomial fpt-reduction from the model-checking problem for FO on the class of all graphs to the model-checking for on the class of all strings of alphabet .
We use a similar idea as in the proof of Theorem 4.1. Given a graph with vertex set and an FO-sentence , we construct a string and an -sentence such that satisfies if and only if satisfies .
This time, we use substrings (instead of subtrees) to represent the vertices of . For a vertex with neighbours in , we let be the string
Then we let be the concatenation of the for all . It is easy to complete the proof along the lines of the proof of Theorem 4.1. ∎
The parameterised model-checking problem for on the class of all strings (of alphabet ) is -complete.
5 The fragment of
In this section, we define a fragment of called . This logic is an extension of FO that allows to formulate cardinality conditions concerning terms that have at most one free variable (hence the subscript 1 in “”). The logic is designed in such a way that it, although being relatively expressive, still allows for efficient query evaluation algorithms on well-behaved classes of structures. This paper’s main result shows that -query evaluation is fixed-parameter tractable on nowhere dense classes of structures.
Definition 5.1 ().
Let be a signature.
Definition 5.2 (-queries).
Let be a signature. An -query is of the form
where , are pairwise distinct
variables, are -counting terms
with for each ,
and is an -formula with
When evaluated in a -structure , a query of the form ( ‣ 5.2) returns the result
Let us demonstrate that the usual examples for uses of the COUNT operation in SQL can be expressed in this query language.
In this example we consider -queries where is empty, and deal with the database schema consisting of relations Customer(Id, FirstName, LastName, City, Country, Phone) and Order(Id, OrderDate, OrderNumber, CustomerId, TotalAmount).333taken from 
To list the number of customers in each country, one can use the SQL-statement
SELECT Country, COUNT(Id) FROM Customer GROUP BY Country
or the -query with and with
To return the total number of customers and the total number of orders stored in the database, we can use the SQL-statement444This statement shall work for MySQL, PostgreSQL, and Microsoft SQL server; to make it work for Oracle, the statement has to be appended by the line FROM dual.
SELECT( SELECT COUNT(*) FROM Customer ) AS No_Of_Customers, ( SELECT COUNT(*) FROM Order ) AS No_Of_Orders
or, equivalently, the -query for
with and and where is a sentence that is satisfied by every database, e.g., .
To list the total number of orders for each customer in Berlin, we can use the SQL-statement
SELECT C.FirstName, C.LastName, COUNT(O.Id) FROM Customer C, Order O WHERE C.City = Berlin AND O.CustomerId = C.Id GROUP BY C.FirstName, C.LastName
or, equivalently, the -query
for and and
Here, we use an atomic statement to express that “”. Of course, to avoid such constructions, we could extend the definition of in the usual way by allowing constants taken from a fixed domain dom of potential database entries (cf. ).
Our query language is also capable of expressing more complicated queries:
Consider a numerical predicate collection that contains the equality predicate with . For better readability of formulas we will write instead of .
Consider the signature where is a binary relation symbol and , , are unary relation symbols. We view a -structure as a directed graph where each node may be coloured with 0, 1, 2, or 3 of the colours (red), (blue), and (green).
The ground term specifies the total number of red nodes. The term
specifies the number of directed triangles in which participates. The formula is satisfied by all nodes such that the number of triangles in which participates is the same as the total number of red nodes. The ground term specifies the total number of such nodes. The term
specifies the number of blue neighbours of node .
For the formula the -query
outputs all tuples in of the form such that is the product of the number of blue neighbours of and the number of triangles in which participates, is green, and is a node whose number of blue neighbours is equal to the sum of the number of triangles in which participates and the total number of nodes that participate in exactly as many triangles as there are red nodes.
When speaking of an algorithm with -oracle we mean an algorithm that has available an oracle to decide, at unit cost, whether when given a and a tuple of integers of arity .
The paper’s main result reads as follows (see Section 8 for a precise definition of nowhere dense classes).
Theorem 5.5 (Main Theorem).
Let be an effectively nowhere dense class of structures. There is an algorithm with -oracle which receives as input an , an -query of the form ( ‣ 5.2) for some signature , a -structure from , and a tuple , and decides whether , and if so, computes the numbers for all . The algorithm’s running time is , for a computable function .
Since the counting problem for an -formula for coincides with the task of evaluating the ground term of , we immediately obtain:
On effectively nowhere dense classes , the counting problem for is fixed-parameter almost linear. That is, there is an algorithm with -oracle which receives as input an , an -formula of some signature , and -structure from , and computes the number of tuples with in time , for a computable function .
The first step towards proving Theorem 5.5 is to use a standard construction for getting rid of the free variables. Given a query of the form ( ‣ 5.2), we extend the signature by fresh unary relation symbols and let . Given a -structure and a tuple , we consider the -expansion of where for all .
It is straightforward to translate into a -sentence such that iff ; and similarly, for each we can translate the term into a ground term of signature such that