Consistent query answering (CQA) [2] aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers, called consistent answers, must be true in all repairs, which are consistent databases whose di erence from the inconsistent one is somehow minimal. Consistent answers only allow us to conclude that a tuple is either entailed by all repairs, or is not entailed by some repair. But, as discussed in [4], the former is too strict, while the latter is not very useful in practice. Instead, we would like to know how often a tuple is consistent, i.e., its relative frequency de ned as the ratio between the number of repairs entailing the tuple, and the total number of repairs. The data complexity, i.e., when the query and the set of constraints are xed, of the problem of computing the relative frequency of a tuple has been already studied in [6, 7] for conjunctive queries (CQs) and primary keys (i.e., when each relation has at most one key). We know that computing the total number of repairs is feasible in polynomial time. On the other hand, computing the number of repairs that entail the given tuple is #P-complete. Recall that #P is a hard counting complexity class, which, roughly speaking, collects the function problems that ask for the number of solutions to an NP problem. The above #P-hardness relies on polynomial-time Turing, a.k.a. Cook, reductions. However, as observed in the literature [5, 8], there are problems that are \hard-to-count-easy-to-decide" that cannot be complete (under reasonable assumptions) for #P under standard many-one logspace (or even polynomial-time) reductions. Note that the decision version of a counting problem asks whether the count is greater than zero. In our case, it asks whether a repair entailing a given tuple exists. As stated in [8], Cook reductions blur structural di erences between counting problems and complexity classes. The reason is that #P is not closed under Cook reductions (under reasonable assumptions). Therefore, for such \hard-to-count-easy-to-decide" problems, a crucial question is whether ? This is a short version of the paper [3]. Copyright ' 2019 for the individual papers by the papers authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy.
we can determine their exact complexity w.r.t. subclasses of #P to which they belong. Ideally, we would like to show that such a problem is complete, under logspace reductions, for a class C #P that is closed under such reductions.
Our goal is to perform such a re ned analysis for the data complexity of the problem of counting the number of repairs that entail a given tuple in the case of primary keys. We show that for arbitrary rst-order queries this problem remains #P-complete. For existential positive queries (and CQs as well), we show that our problem cannot be complete (under reasonable assumptions) for #P, or even known classes inside #P. This brings us to our main question whether we can isolate a complexity class C inside #P that is closed under logspace reductions for which our problem (in the case of positive existential queries) is complete under such reductions. Let us stress that there is no guarantee that such a class C exists. This is because we focus on the data complexity of our problem. This means, by convention, that we deal with a family of problems and not a single problem; as usual, each query and set of primary keys gives rise to a new problem. Furthermore, establishing a completeness result for a certain complexity class C boils down to showing that (i) every problem in this family belongs to C, and (ii) there exists one problem that is C-complete. But, there is no guarantee that there exists a problem in this family such that all the other problems of the family are logspace reducible to it. This essentially tells us that the complexity class C inside #P that we are looking might not exist.
Although we do not give a de nite answer to our main question, we make a signi cant step towards such an answer. We isolate a hierarchy of new complexity classes inside #P, called the -hierarchy, which is of independent interest, and show that if the class C that we are looking for exists, then it is one of the levels of the -hierarchy. Moreover, whether C exists boils down to the question whether the -hierarchy collapses. We conjecture that this is not the case. 2
Relational Databases. A (relational) schema S is a nite set of relation
symbols (or predicates) with associated arity. A database D over a schema S is a
set of facts of the form R(t), where R 2 S, and t = t1; : : : ; tn is a tuple of terms
that are drawn from a countably in nite set C of constants. We write dom(D)
for the active domain of D, that is, the set of constants occurring in D.
Primary Key Constraints. A key constraint (or simply key) over a schema
S is an expression of the form key(R) = f1; : : : ; mg, where R 2 S has arity n,
and m n. Such an expression is called an R-key. A database D satis es if, for
every two facts R(t); R(s) 2 D, t[i] = s[i] for each i 2 f1; : : : ; mg implies t = s.
We say that D is consistent w.r.t. a set of keys, written D j= , if D satis es
each key in ; otherwise, it is inconsistent. A set of primary keys is a set of keys
such that, for each predicate R, has at most one R-key. For = R(c1; : : : ; cn),
the key value of w.r.t. , denoted key ( ), is de ned as hR; hc1; : : : ; cmii, if
key(R) = f1; : : : ; mg 2 , and hR; hc1; : : : ; cnii otherwise. Let block ( ; D) =
f 2 D j key ( ) = key ( )g, and block (D) = fblock ( ; D) j 2 Dg.
A repair of D w.r.t. is a database obtained by choosing one fact from each
B 2 block (D). We denote the set of repairs of D w.r.t as rep(D; ).
Queries. A rst-order query Q(x) over a schema S is an expression fx j 'g,
where ' is a rst-order formula with free variables x that mentions only atoms
over S. We write FO, 9FO+ and CQ, for the class of rst-order, existential
positive, and conjunctive queries, respectively. The answer to Q(x) over a database
D, denoted Q(D), is the set of tuples fc 2 dom(D)jxj j D j= '(c)g.
Complexity Toolbox. We recall well-known counting complexity classes, i.e.,
classes of counting functions of the form f0; 1g ! N. FP contains the functions
that are computable in polynomial-time. #P contains the functions that compute
the number of accepting computations of an NP machine. SpanL contains the
functions that compute the number of distinct valid outputs of an NL transducer.
The output of a computation is called valid if the machine halts in an accepting
state. We know that SpanL #P, and the inclusion is strict (under reasonable
assumptions) [
The main concern of this work is the problem of counting the number of repairs that entail a given tuple de ned as follows; Q denotes a class of queries:
INPUT : A database D, a set of primary keys,
a query Q(x) 2 Q, and a tuple t 2 dom(D)jxj.
OUTPUT : jfD0 2 rep(D; ) j t 2 Q(D0)gj.
As usual, we are interested in the data complexity of #CQA(Q), where the set of constraints and the query are xed, and only the database and the tuple are part of the input. To make this notion more precise, we need to de ne the following problem, where Q(x) 2 Q is a query and is a set of primary keys:
INPUT : A database D, and a tuple t 2 dom(D)jxj.
OUTPUT : jfD0 2 rep(D; ) j t 2 Q(D0)gj.
We say that #CQA(Q) is R-complete for C in data complexity, where R is a class of reductions and C a complexity class, if (i) for each query Q 2 Q and set of primary keys, #CQA(Q; ) is in C, and (ii) there exists Q0 2 Q and set 0 of primary keys such that #CQA(Q0; 0) is R-complete for C.
The decision version of #CQA(Q), denoted #CQA>0(Q), simply asks whether jfD0 2 rep(D; ) j t 2 Q(D0)gj > 0. The data complexity of #CQA>0(Q) is de ned in the same way as for #CQA(Q). Henceforth, for clarity, we focus on Boolean queries, but all the results hold even if we consider non-Boolean queries. 4
The complexity of #CQA has been already studied in [
The situation for positive existential queries is more interesting. We can show that in this case we are dealing with a typical \hard-to-count-easy-todecide" problem. In particular, we can show that #CQA>0(9FO+) is tractable, which in turn implies that #CQA(9FO+) is not lmog-complete for #P (unless P = NP). This tells us that for pinpointing the complexity of #CQA(9FO+) we should look for a subclass of #P, which is closed under logspace reductions. The obvious candidate is SpanL. Indeed, we can show that #CQA(9FO+) is in SpanL. However, #CQA(9FO+) is not lmog-complete for SpanL (unless L = NL). Not much is known about subclasses of SpanL for which our problem can be complete under logspace reductions. This brings us to our main question: Research Question: Is there a class C reductions, such that #CQA(9FO+) is
SpanL, which is closed under logspace lmog-complete for C?
Let us stress that since we focus on the data complexity of #CQA(9FO+), as discussed in Section 1, the above question is not trivial in the sense that the existence of the class C is not guaranteed. Although we cannot give a de nite answer to this question, we make a signi cant step towards such an answer. We isolate a hierarchy of new complexity classes inside #P, called the -hierarchy, and show the following; we write [k] for the k-th level of the hierarchy: Theorem 1. The following are equivalent: 1 All the results for #CQA and #CQA>0 in the rest of the paper concern their data complexity. Thus, for brevity, we will sometimes avoid to explicitly mention the term data complexity. 1. There exists a class C SpanL, closed under logspace reductions, such that #CQA(9FO+) is lmog-complete for C. 2. There exists k 0 such that #CQA(9FO+) is lmog-complete for [k]. 3. The -hierarchy collapses.
The above theorem essentially tells that either #CQA(9FO+) is lmog-complete for [k], for some k 0, or there is no complexity class C SpanL, closed under many-one logspace reductions, such that #CQA(9FO+) is lmog-complete for C. Thus, the right complexity class that characterizes the data complexity of our problem, if it exists, is one of the levels of the -hierarchy. 5
The
-hierarchy
We now proceed to introduce our hierarchy of complexity classes. The main
technical challenge is to understand how to limit the computational power of
NL transducers. This will lead to our new complexity classes inside SpanL that
allow us to establish Theorem 1. To this end, we give a semi-formal introduction
to this hierarchy, by presenting a couple of structural properties enjoyed by the
functions therein. For further details, we refer the reader to [
There is a generic paradigm, which we call guess-check-expand, that an NL transducer can follow in order to place problems inside SpanL, assuming that the following structural properties are ful lled: Small Certi cates. A solution (in our case, a repair that entails the query) is witnessed via a small certi cate { by small we mean of logarithmic size { that is veri able in logspace.
For the next property, we rst need to give some auxiliary terminology. Given a sequence of sets S1; : : : ; Sn, an `-selector of it, for ` 0, is a sequence of pairs = (i1; e1); : : : ; (i`; e`), where 1 i1 < : : : < i` n, and ej 2 Sij for each j 2 f1; : : : ; `g. Intuitively, a pair (i; e) in tells us to \keep the element e from the set Si". We can then de ne the cartesian product of S1; : : : ; Sn w.r.t. , denoted [S1; : : : ; Sn] , as S1 Sn , where Si = feg if contains a pair (i; e), otherwise, Si = Si. In simple words, [S1; : : : ; Sn] is the cartesian product of S1; : : : ; Sn with the di erence that ` sets are rst replaced by a singleton set as dictated by the `-selector . We can now discuss the second structural property. For an input instance x, we write sol(x) for the set of solutions, and cert(x) for the set of certi cates that witness a solution of sol(x).
Solutions via Certi cate Expansion. For every input x, there is a sequence of logspace computable sets S1; : : : ; Sn, called solution domains, such that jsol(x)j =
[ [S1; : : : ; Sn] c ; where c is an `-selector for S1; : : : ; Sn determined by the small certi cate c. In fact, there exists a bijection enc from sol(x) to Sc2cert(x)[S1; : : : ; Sn] c , and enc(s) should be understood as an encoding of the solution s.
A function that enjoys the above structural properties can be shown to be in SpanL via a simple guess-check-expand algorithm: 1. (Guess) Guess a candidate small certi cate c. 2. (Check) If c is not a valid certi cate, then reject. 3. (Expand) Expand c into an encoding of a solution witnessed by c using S1; : : : ; Sn as follows: for i = 1 to n, if the `-selector c determined by c mentions (i; e), then output e; otherwise, guess e 2 Si and output e.
It is clear that, on an input x, the above transducer uses logspace in the size of x since the small certi cates are logspace veri able, and the solution domains are logspace computable. Moreover, the number of distinct valid outputs of the transducer coincides with Sc2cert(x)[S1; : : : ; Sn] c , and thus, with jsol(x)j. A transducer of the form above is called k-guess-check-expand, for some integer k 0, if the `-selectors are such that ` k. #CQA(Q; ) via a Guess-Check-Expand Algorithm. It is interesting to observe that the problem #CQA(Q; ), for some UCQ Q and set of primary keys, enjoys the two structural properties de ned above; recall that an existential positive query can be rewritten as a UCQ. More precisely, on input D: { A small certi cate for a repair of rep(D; ) that entails Q is a pair (Q0; h), where Q0 is a disjunct of Q, and h : var(Q0) ! dom(D), such that h(Q0) D and h(Q0) j= . { The sequence of solution domains corresponds to the sequence B1; : : : ; Bn of the sets of block (D), according to some arbitrary, but xed ordering. The `-selector (Q0;h) for B1; : : : ; Bn determined by a certi cate (Q0; h) mentions the pair (i; R(t)), i.e., it keeps the fact R(t) from Bi, i h(Q0) \ Bi = fR(t)g and has an R-key. The latter implies that ` is bounded by the number of atoms with a predicate that has a key over all disjuncts of Q, which does not depend on the input database D. Clearly, the number of repairs of rep(D; ) that entail Q is the number
[ (Q0;h)2cert(D)
[B1; : : : ; Bn] (Q0;h) :
Therefore, the fact that #CQA(Q; ) is in SpanL can be shown via a k-guesscheck-expand algorithm, as the one presented below, where k is the number of atoms in Q with a predicate with a key in : 1. (Guess) Guess a candidate small certi cate (Q0; h). 2. (Check) If h(Q0) * D or h(Q0) 6j= , then reject. 3. (Expand) Expand (Q0; h) into an encoding of a solution witnessed by (Q0; h) as follows: for i = 1 to n, if h(Q0) \ Bi = fR(t)g and has an R-key, then output R(t); otherwise, guess a fact 2 Bi and output . The guess-check-expand paradigm suggests a natural way to de ne a hierarchy of classes inside SpanL. Intuitively, the k-th level of such hierarchy is de ned by considering k-guess-check-expand transducers. This intuition is at the core of the -hierarchy. In particular, for every integer k 0, [k] is the class of functions f : f0; 1g ! N such that, for every x 2 f0; 1g , f (x) is the number of valid distinct outputs of a k-guess-check-expand transducer Mf , with input x. The -hierarchy is de ned as the in nite union = Sk 0 [k].
We proceed to discuss some key properties concerning the -hierarchy. The rst one states that each level of the hierarchy is closed under logspace reductions, which is crucial for our complexity analysis.
0, [k] is closed under logspace reductions. The next result con rms that is a hierarchy of classes inside SpanL:
[0]
SpanL, and = SpanL implies L = NL.
The next result shows that, apart from
consists of \hard" complexity classes:
[0] and [
[
FP, and [
FP implies P = NP.
A direct corollary of Proposition 3 is that [
Having the -hierarchy in place, we are now ready to explain how Theorem 1 is shown. To this end, we concentrate on a parameterized version of #CQA(9FO+), where the so-called keywidth of the query w.r.t. the set of primary keys is bounded by an integer k 0. Formally, the keywidth function (kw) maps pairs of the form (Q; ), where Q 2 9FO+ and is a set of primary keys, to the naturals such that kw (Q; ) = jfR(t) j R(t) occurs in Q; and has an R-keygj. Then: PROBLEM : #CQAkkw (9FO+) INPUT : A database D, a set of primary keys,
and a query Q 2 9FO+ such that kw (Q; ) = k.
OUTPUT : jfD0 2 rep(D; ) j D0 j= Qgj.
The data complexity of the above problem is de ned as expected. Then:
0, #CQAkkw (9FO+) is lmog-complete for [k].
By exploiting Theorem 2, we can now establish our main result (Theorem 1): (1) ) (3). By hypothesis, there is a class C SpanL such that #CQA(9FO+) is lmog-complete for C. Thus, for every Q 2 9FO+ and set of primary keys, #CQA(Q; ) 2 C. Moreover, there exists Q^ and ^ such that #CQA(Q^; ^) is lmog-complete for C, which means that, for every f 2 C, f lmog #CQA(Q^; ^). By Theorem 2, #CQA(Q^; ^) 2 [kw (Q^; ^)]. Since, by Proposition 1, [kw (Q^; ^)] is closed under logspace reductions, we conclude that f 2 C implies f 2 [kw (Q^; ^)], or, in other words, C [kw (Q^; ^)]. Hence, for every Q 2 9FO+ and set of primary keys, #CQA(Q; ) 2 [kw (Q^; ^)]. Since, for every k 0, there exists Q0 and 0 such that #CQA(Q0; 0) is lmog-complete for [k], then Sk 0 [k] = [kw (Q^; ^)]. Hence, the -hierarchy collapses to its kw (Q^; ^)-th level.
(3) ) (2): By hypothesis, the -hierarchy collapses to its k-the level, for some k 0, i.e., = [k]. We proceed to show that (i) for every Q 2 9FO+ and set of primary keys, #CQA(Q; ) 2 [k], and (ii) there exists Q^ and ^ such that #CQA(Q^; ^) is lmog-complete for [k]. For showing (i), x some query Q 2 9FO+ and set of primary keys. By Theorem 2, #CQA(Q; ) 2 [kw (Q; )]. Since [kw (Q; )] = [k], we immediately get that #CQA(Q; ) 2 [k]. Statement (ii) holds trivially since, by Theorem 2, there exists a lmog-complete function for every level of the -hierarchy.
(2) ) (1): Since, for every k 0, [k] is closed under logspace reductions (Proposition 1), and [k] SpanL (Proposition 2), the claim follows. The Next Step. Providing a rm answer to our main question boils down to understanding whether the -hierarchy collapses. Our conjecture is that it does not collapse. Proving or disproving this conjecture is one of our priorities, which will complete the picture concerning the data complexity of #CQA(9FO+). Acknowledgements. This work was supported by the EPSRC grants S003800 EQUID, M025268 VADA, and N023056 MAGIC.