Meghyn Bienvenu
email: meghyn.bienvenu@u-bordeaux.fr

Quentin Manière
email: quentin.maniere@u-bordeaux.fr

Michaël Thomazo
email: michael.thomazo@inria.fr

Answering Counting Queries over DL-Lite Ontologies

Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. In this paper, we introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries in the presence of DL-Lite ontologies. As it follows from existing work that query answering is intractable and often of high complexity, we consider some practically relevant restrictions, for which we establish improved complexity bounds.

2 Briefly, the upper bound is 0 if the tuple is not a certain answer; otherwise, it is either 1 if z = ∅, else +∞.

3 As usual, |T | (resp. |A|, |q|) denotes the size of T (resp. A, q).

Introduction

Ontology-mediated query answering (OMQA) utilizes ontologies to provide a convenient vocabulary for query formulation and to capture domain knowledge that is exploited during the querying process to obtain more complete sets of answers [Poggi et al., 2008;Bienvenu and Ortiz, 2015;Xiao et al., 2018]. Much of the work on OMQA considers ontologies formulated using description logics (DLs), a family of knowledge representation languages that provide the logical foundations of the OWL web ontology language. Particular attention has been to the DL-Lite family of DLs [Calvanese et al., 2007], which were developed with OMQA in mind and enjoy favorable computational properties.

The vast majority of work on OMQA supposes that user queries are given as conjunctive queries (CQs). However, there are many other kinds of database queries, beyond plain CQs, that are relevant in practice. This motivates research into the feasibility of adopting other database query languages for OMQA. While enriching CQs with either negated atoms or inequalities has been shown to lead to undecidability even in very restricted settings [Gutiérrez-Basulto et al., 2015], the situation is more positive for navigational queries (like regular path queries), which can be adopted without losing decidability, sometimes even retaining tractable data complexity [Bienvenu et al., 2015b].

Aggregate queries, which use numeric operators (e.g. count, sum, max) to summarize selected parts of a dataset, constitute another prominent class of database queries. Although such queries are widely used for data analysis, they have been little explored in context of OMQA. This may be partly due to the fact that it is not at all obvious how to define the semantics of such queries in the OMQA setting. A first exploration of aggregate queries in OMQA was conducted by [START_REF] Calvanese | Aggregate queries over ontologies[END_REF]. They argued that the most straightforward adaptation of classical certain answer semantics to aggregate queries was unsatisfactory, as often values would differ from model to model, leading to no certain answers. For this reason, an epistemic semantics was proposed, in which variables involved in the aggregation are required to match to data constants. However, as discussed in [START_REF] Kostylev | [END_REF], this semantics can also give unintuitive results by ignoring ways of mapping aggregate variables to anonymous elements inferred due the ontology axioms. For instance, if no children of alex are listed in the data, then a query that asks to return the number of children will yield 0 under epistemic semantics, even if it can be inferred (e.g. due to a family tax benefit) that there must be at least 3 children. This led Kostylev and Reutter to define an alternative semantics for two kinds of counting queries (inspired by the COUNT and COUNT DISTINCT in SQL) which adopts a form of certain answer semantics but considers lower and upper bounds on the count value across different models. For the two considered logics (DL-Lite core and DL-Lite R ), only the lower bounds on the count value are non-trivial, and a complexity analysis shows that they are challenging to identify: coNP-data complexity for both logics, and Π p 2 -hard (resp. coNEXP-hard) in combined complexity for DL-Lite core (resp. DL-Lite R ). Several question were left unanswered by their work, including the exact combined complexity, the difficulty of recognizing the optimal lower bound, and the impact of allowing multiple aggregation variables.

This paper returns to the issue of handling counting queries in OMQA and makes several important contributions:

1. We propose a new notion of counting CQ that generalizes the two forms of queries from [START_REF] Kostylev | [END_REF] and allows arbitrarily many counting variables. 2. We show that existing complexity results for DL-Lite core and DL-Lite R KBs continue to hold for our more general notion of counting CQ, and provide an improved coNEXP upper bound for the relevant case of finite-depth TBoxes. 3. We consider the impact of restricting the query structure, focusing on the class of rooted queries, in which every query variable must be connected to an answer variable or individual in the query graph. A recent result, obtained as part of a study of bag semantics for OMQA, identified a case in which rootedness leads to tractable data complexity for counting queries [START_REF] Nikolaou | [END_REF]. This motivates us to perform a more thorough investigation of rooted counting queries, which yields several improvements upon existing complexity bounds. 4. We prove that the problem of identifying the best certain interval is DP-complete in data complexity. Our results close some questions that were left open by the work of Kostylev and Reutter and pave the way for further study of counting and aggregate queries in the OMQA setting.

An appendix with full proofs can be found in the long version of this paper, available on arXiv.

Preliminaries

We recall the basics of description logics (DLs), focusing on DL-Lite, see [START_REF] Baader | [END_REF] for more details. Syntax and Semantics. A description logic vocabulary consists of a set N C of atomic concepts (unary predicates), a set N R of atomic roles (binary predicates), and a set N I of individual names (constants). By role, we mean either an atomic role P ∈ N R or an inverse role P -(where P ∈ N R ). We let N ± R denote the set N R ∪ {P -| P ∈ N R } of roles and use the notation R -to mean P -if R = P ∈ N R and P if R = P -.

A DL knowledge base (KB) is a pair K = (T , A), consisting of an ABox A that contains facts about particular individuals and a TBox T that expresses general knowledge about the domain. Formally, an ABox is a finite set of concept assertions A(b), with A ∈ N C and b ∈ N I , and role assertions P (a, b), with P ∈ N R and a, b ∈ N I . We use Ind(A) to denote the set of individuals in A. A TBox is a finite set of axioms, whose syntax depends on the particular DL. In DL-Lite core , axioms take the form of concept inclusions B 1 (¬)B 2 , where each B i is either A (for A ∈ N C ) or ∃R (with R ∈ N ± R ). DL-Lite R TBoxes additionally allow role inclusions R 1 (¬)R 2 , where R 1 , R 2 ∈ N ± R . Example 1. Our example KB talks about leading (LeadIn) and supporting actors (SuppIn) in movies:

A act = {ActsIn(doona, cloud), SuppIn(berry, cloud), SuppIn(hanks, cloud), SuppIn(hanks, catch)} T act = {LeadIn ActsIn, SuppIn ActsIn, ∃SuppIn -∃LeadIn -} An interpretation takes the form I = (∆ I , • I ), where ∆ I is a non-empty set (the domain of I), and . I is a function that maps each A ∈ N C to a subset A I ⊆ ∆ I , each P ∈ N R to a binary relation P I ⊆ ∆ I × ∆ I , and each a ∈ N I to an element a I of ∆ I . We make the unique names assumption We call I a model of K, written I |= K, if it satisfies all inclusions and assertions in K. A KB is satisfiable if has at least one model. Queries. We recall that a conjunctive query (CQ) takes the form ∃y ψ(x, y), where x and y are tuples of variables drawn from an infinite set of variables V, and ψ is a conjunction of atoms, which can be either concept atoms A(t 1 ) or role atoms P (t 1 , t 2 ), where A ∈ N C , P ∈ N R , and terms t i are drawn from N I ∪ x ∪ y. Consider an interpretation I and CQ q = ∃y ψ(x, y) with |x| = n. A tuple α ∈ ∆ I n is an answer to q in I, written I |= q(α), if there is a homomorphism of q into I, i.e., a function σ that maps the terms of q to elements of ∆ I such that (i) σ(a) = a I for a ∈ N I , (ii) σ(t) ∈ A I for every atom A(t) of q, and (iii) (σ(t 1 ), σ(t 2 )) ∈ P I for every atom P (t 1 , t 2 ) of q. A tuple a ∈ Ind(A) n is a certain answer to q w.r.t. the KB K iff I |= q(a I ) for every model I of K. Canonical Model. We recall the definition of the canonical model C K of a DL-Lite R KB K = (T , A). The domain of C K consists of Ind(A) and all words of the form aR 1 . . . R n , with a ∈ Ind(A), R i ∈ N ± R , and n 1, such that:

• K |= ∃R 1 (a) and there is no R 1 (a, b) ∈ A; • for 1 ≤ i < n, T |= ∃R - i ∃R i+1 and R - i = R i+1 .
We interpret individuals as themselves (a C K = a) and atomic concepts and roles as follows: The term 'canonical model' is motivated by the following well-known property of C K (see e.g. [Calvanese et al., 2007]):

A C K = {a ∈ Ind(A) | K |= A(a)} ∪ {aR 1 . . . R n ∈ ∆ C K \ Ind(A) | T |= ∃R - n A} P C K = {(
Lemma 1. Let K be a satisfiable DL-Lite R KB. Then C K |= K and if I |= K, there is a homomorphism of C K into I.
A useful corollary is that the certain answers to a CQ q w.r.t. K are the tuples from Ind(A) that are answers to q in C K . Note that C K may be infinite. The depth of a TBox T is defined as the maximal length of any word that appears in the domain of C K for any KB K whose TBox is T . If this number is finite, we say that T is a finite-depth TBox; such TBoxes can be identified in polynomial time [Bienvenu et al., 2015a].

Counting Queries

We now introduce our formalization of counting queries. In addition to the set V of (classical) variables, we assume a second infinite set of counting variables V c , disjoint from V. Definition 1. A counting conjunctive query (CCQ) q takes the form q(x) = ∃y∃z ψ(x, y, z), where x ∪ y ⊆ V, z ⊆ V c , and ψ is a conjunction of concept and role atoms whose terms are drawn from N I ∪ x ∪ y ∪ z. We call x (resp. y, resp. z) the answer (resp. existential, resp. counting) variables of q.

We first define the semantics of counting queries on a single interpretation I, by considering those pairs (a, n) such that n is the number of possible ways to map z into I when x is mapped to a. Such pairs are called the answers to q in I. Definition 2. A match of a CCQ q(x) = ∃y∃z ψ(x, y, z) in I is a homomorphism1 from q into I. If a match σ maps x to a, then the restriction of σ to z is called a counting match (cmatch) of q(a) in I. The set of answers to q in I, denoted q I , contains all pairs (a, q I a ), where q I a is the number of distinct c-matches of q(a) in I.

As has been previously noted (see e.g. [START_REF] Kostylev | [END_REF]), the exact count values of the answers in q I are usually too specific to hold across models. Considering bounds on the exact value provides more insight, while still allowing unnamed elements to be counted. This motivates the following notion of answer interval. Definition 3. The set [q] I of answer intervals for a CCQ q in I contains all pairs (a, [m, M ]) with a ∈ Ind |x| and m, M integers such that m ≤ q I a ≤ M . The set [q] K of certain (counting) answers to q w.r.t. KB K is obtained by considering those answer intervals that hold in all models of K:

[q] K = I|=K [q] I . Note that (a, [m, M ]) ∈ [q] K does not imply that for any n ∈ [m, M ] there exists a model I in which (a, n) ∈ q I .
Definition 1 is a proper generalization of the two forms of counting query considered by Kostylev and Reutter. Reusing their notations, a Cntd()-query q(x, Cntd(z)) = ∃y ψ(x, y, z) corresponds to the CCQ q(x) = ψ(x, y, z), while a Count()-query q(x, Count()) = ∃y ψ(x, y) corresponds to the CCQ q(x) = ψ(x, ∅, ŷ) (with ŷ a tuple of variables from V c in bijection with y). We will use the term exhaustive to refer to the latter CCQs, i.e. those in which every non-answer variable is a counting variable. Example 2. Reconsider the KB K act = (T act , A act ). We can use CCQs to count the pairs of actors (leading role, supporting role) having acted together (q 1 ), return movies together with a count of their supporting actors (q 2 ), and count the number of actors having acted with Tom Hanks (q 3 ):

q 1 = ∃y∃z 1 ∃z 2 LeadIn(z 1 , y) ∧ SuppIn(z 2 , y) q 2 (x) = ∃z SuppIn(z, x) q 3 = ∃y∃z ActsIn(hanks, y) ∧ ActsIn(z, y)
According to our semantics, we have:

• (∅, [2, +∞]) ∈ [q 1 ]
Kact , since z 2 can be mapped to either berry or hanks, and z 1 mapped to the lead actor (which must exist due to T act ). As the lead actors of the two films could be the same,

(∅, [3, +∞]) ∈ [q 1 ] Kact . • (cloud, [2, +∞]) ∈ [q 2 ] Kact , mapping z to berry and hanks. • (∅, 5) ∈ q C K act 3
, since in C Kact , we can map z to a named actor or the two elements standing in for the lead actors.

• (∅, [5, +∞]) / ∈ [q 3 ] Kact , since the lead actors could possibly be the same or one of the named actors. The latter two points show that the canonical model does not yield the minimal number of matches.

Data

Combined

DL-Lite core coNP-c Π p 2 -h, PP-h & in coNEXP DL-Lite R coNP-c coNEXP-h & in coN2EXP coNEXP-c (T of finite depth)

General Counting CQs

We shall consider the following CCQ answering decision problem: given a KB K = (T , A), CCQ q, and candidate answer (a, [m, M ]), decide whether (a, [m, M ]) ∈ [q] K .

As ontology languages, we will consider DL-Lite R (which underlies OWL 2 QL) and its sublogic DL-Lite core . We know from [START_REF] Kostylev | [END_REF] that in these DLs, the least upper bound M can take one of three values (0, 1, or +∞) and is easily computed. The argument 2 transfers to our more general notion of CCQ. We can therefore restrict our attention to identifying certain answers of the form (a, [m, +∞]).

We will consider the two usual complexity measures: combined complexity which is in terms of the size of the whole input (T , A, q, a, m), and data complexity which is only in terms of the size of A and m (T and q are treated as fixed). We will assume that m is given in binary.

General Case

Table 1 displays complexity results for answering general CCQs over DL-Lite core and DL-Lite R TBoxes (we use '-c' and '-h' as abbreviations for '-complete' and '-hard').

With the exception of the PP-hardness result (discussed in Section 6.1), the lower bounds are inherited from [START_REF] Kostylev | [END_REF]. We will thus concentrate on the upper bounds from Table 1, which are obtained by generalizing and clarifying the constructions of Kostylev and Reutter. We give an overview of the proof both to give the flavor of the techniques involved and to enable us to discuss the necessary adaptations used to prove later results.

The proof constructs a decision procedure for the complementary problem of deciding whether (a, [m, +∞]) ∈ [q] K . The latter holds iff there exists a countermodel, i.e., a model of K with fewer than m c-matches of q(a). The main ingredient of the proof is the following theorem, which shows that it is sufficient to consider countermodels of bounded size. Theorem 1. For every DL-Lite R (resp. DL-Lite core ) KB K = (T , A) and CCQ q, if there is a model of K with fewer than m c-matches of q(a), then there exists one of size

3 O(|A| |T | |q|+1 ) (resp. O(|A| |q| )).
With Theorem 1 in hand, we can easily define nondeterministic procedures that witness the complexity upper bounds from Table 1: simply guess an interpretation of polynomial / exponential / double-exponential size (depending on the case) and verify whether it is a countermodel.

The proof of Theorem 1 starts with an arbitrary countermodel I and modifies it in order to make it smaller, being careful not to introduce any new c-matches of q(a). We first identify a relevant subset ∆ * of the domain of I, consisting of the interpretations of all individual names from A and the images of all c-matches of q(a). We then define a new interpretation that intuitively preserves ∆ * and replaces the rest of I with parts of the canonical model, to introduce a more regular structure. Formally, we fix a homomorphism f of C K into I (see Lemma 1) and consider the following mapping [START_REF] Kostylev | [END_REF]:

f : ∆ C K → ∆ * ∪ ∆ C K from
f (d) = f (d) if f (d) ∈ ∆ * d otherwise
We define the interleaving4 I of I as the image of C K by f , i.e., with domain f (∆ C K ) and interpretation function f

•• C K .
It is not difficult to prove that the interleaving I is a model of K. Moreover, by exhibiting a homomorphism ρ from I to I, we can translate matches of I into matches in I. As the images of c-matches of q(a) are contained in ∆ * , which is left unchanged in I , the homomorphism ρ is in fact a one-toone mapping of c-matches of q(a) in I to those in I. This shows that I is also a countermodel.

The interleaving I may be arbitrarily large, even infinite. To reduce its size, an equivalence relation is introduced, and elements from ∆ I \ ∆ * that belong to the same equivalence class are merged (elements from ∆ * are retained). In the case of DL-Lite R , there can be double-exponentially many equivalence classes, as elements are grouped based upon the properties of their |q|-neighborhoods, while for DL-Lite core , we can use a more refined relation with only exponentially many classes. This means that the resulting models are either of single-or double-exponential size w.r.t. combined complexity, depending on the chosen DL.

A crucial final step is to show that the merging of elements does not introduce any new c-matches of q(a), so the resulting model is still a countermodel. This part of the argument, only sketched in [START_REF] Kostylev | [END_REF], requires a detailed and technical analysis of the construction to ensure that this property holds for our more general class of CCQs. We show that this is indeed the case, which answers a question left open by Kostylev and Reutter about counting CQs with both existential variables and multiple counting variables.

Case of Finite-Depth TBoxes

We give an improved upper bound for finite-depth TBoxes (which arguably cover many practical ontologies [Grau et al., 2013]), pinpointing the exact combined complexity. Theorem 2. For finite-depth DL-Lite R TBoxes, CCQ answering is coNEXP-complete w.r.t. combined complexity.

Proof sketch. Fix a KB K = (T , A). If T has finite depth, then C K contains at most |Ind(A)| × |T | |T | elements, which implies that, for every model I of K, the interleaving of I is finite and of single exponential size in |K|. Since the interleaving of a countermodel is itself a countermodel, this shows that the smallest countermodel is of single-exponential size, from which derives the improved coNEXP upper bound.

We note that the proofs of the coNP and Π p 2 lower bounds listed in Table 1 already use finite-depth TBoxes.

Rooted Counting CQs

We next explore whether structural restrictions on CCQs allow us to obtain lower complexity. As the lower bounds from [START_REF] Kostylev | [END_REF] use disconnected counting variables, a natural idea is to consider the subclass of rooted queries that were introduced in [START_REF] Bienvenu | [END_REF] and are believed to capture a large portion of real-world CQs.

Rooted CCQs can be defined analogously to rooted CQs. The definition utilizes the notion of a Gaifman graph of a CCQ, whose vertices are the query terms, and which has an undirected edge {t 1 , t 2 } iff t 1 , t 2 co-occur in a role atom. Definition 4. A CCQ q(x) := ∃y∃zψ(x, y, z) is rooted if every connected component of the Gaifman graph of q contains at least one answer variable or individual name.

Example queries q 2 and q 3 are rooted, while q 1 is not.

Rootedness has been shown to lower the complexity of reasoning in several settings. Most relevant to us is a recent result by [START_REF] Nikolaou | [END_REF] that rooted CQ answering under bag semantics5 has tractable data complexity in DL-Lite core , and furthermore, the same holds for rooted versions of the Count()-queries of Kostylev and Reutter under suitable restrictions on the TBox. These techniques can be adapted to show tractability for arbitrary DL-Lite core TBoxes: [START_REF] Nikolaou | [END_REF][START_REF] Cima | [END_REF]) In DL-Lite core , exhaustive rooted CCQ answering is TC 0 -complete6 w.r.t. data complexity.

Theorem 3. (Implicit in
Proof sketch. Nikolaou et al. prove that answering rooted CQs under bag semantics can be done via a rewriting to BCALC, whose evaluation problem is known to be in TC 0 due to [Libkin, 2001], see [START_REF] Cima | [END_REF] for discussion. Moreover, they further show that for a syntactically restricted class of DL-Lite core TBoxes, it is possible to reduce exhaustive rooted CCQ answering to rooted CQ answering under bag semantics. To obtain TC 0 membership for unrestricted TBoxes, the BCALC rewriting can be adapted to set-based rather than bag interpretations. In the long version, we provide an alternative self-contained proof which directly constructs a family of TC 0 circuits. A matching lower bound has not been stated, but can be shown by a simple reduction (using an empty TBox) from the TC 0 -complete problem that asks, given a binary string s and number k, whether the number of 1-bits in s exceeds k [Aehlig et al., 2007].

The preceding result naturally leads us to ask whether rootedness also bring benefits for general CCQs. Unfortunately, we show that restricting to rooted CCQs (without exhaustiveness) does not allow us to escape existing hardness results:

Theorem 4. In DL-Lite core , rooted CCQ answering is coNPcomplete w.r.t. data complexity.

Proof sketch. The proof borrows some ideas from the proofs of Lemmas 12 and 16 from [START_REF] Kostylev | [END_REF]. It proceeds by reduction from the well-known coNP-complete 3COL problem: given an undirected graph G = (V, E), return yes iff G has no 3-coloring, i.e., a mapping from V to {red, green, blue} such that adjacent vertices map to different colors (equivalently: there is no monochromatic edge).

The reduction uses atomic roles Edge and Vertex to encode the graph and HasCol to assign colors. The TBox T col has a single axiom: ∃Vertex - ∃HasCol. The ABox A G contains an individual v for each vertex v ∈ V and an assertion Edge(u, v) for each edge {u, v} ∈ E. All vertices are connected to a special root individual a: Vertex(a, u), for each u ∈ V. The three colors are represented by individuals r, g and b. To ensure that the query has matches in every model, we include a 'dummy' vertex individual a v and the following assertions: Vertex(a, a v ), Edge(a v , a v ), HasCol(a v , r), HasCol(a v , g), and HasCol(a v , b).

The query q is the conjunction of the two subqueries:

q edge = ∃y c ∃z 1 ∃z 2 Vertex(a, z 1 ) ∧ Vertex(a, z 2 )∧ Edge(z 1 , z 2 ) ∧ HasCol(z 1 , y c ) ∧ HasCol(z 2 , y c ) q col = ∃y ∃z Vertex(a, y) ∧ HasCol(y, z)
serving respectively to detect monochromatic edges and to check whether any additional colors have been introduced. By construction, there are at least 3 c-matches for q(∅) in any model of the KB K col = (T col , A G ). Moreover, it can be verified that (∅, [4, +∞]) is a certain answer to q w.r.t. K col iff G is not 3-colorable.

Theorem 5. In DL-Lite R , rooted CCQ answering is coNEXP-hard w.r.t. combined complexity.

Proof sketch. The proof adapts a reduction from the exponential grid tiling problem (Lemma 18 from [START_REF] Kostylev | [END_REF]), the key difference being the use of existential query variables to access (and count) the colors and bits.

Exhaustive Rooted Counting CQs

We have seen in Section 5 that the rootedness restriction is not by itself sufficient to lower the complexity of CCQ answering, whereas imposing both rootedness and exhaustiveness can sometimes yield better results. This motivates us to take a closer look at the case of exhaustive rooted CCQs. The emerging complexity landscape is summarized in Table 2.

Note that exhaustive CCQs constitute a very natural form of counting query, which ask for the number of different query matches for a given answer tuple. The query q 2 from Example 2 is an exhaustive rooted CCQ.

Exhaustive Rooted CCQs in DL-Lite core

We first consider DL-Lite core KBs and pinpoint the precise combined complexity, which had not yet been considered.

An essential ingredient is the following result that shows that it is possible to focus on query matches in the canonical Theorem 6. For every DL-Lite core KB K and exhaustive rooted CCQ q, it holds that

Data Combined DL-Lite core TC 0 -c PP-c DL-Lite R coNP-c Π p 2 -h, PP-h & in coNEXP
[q] K = [q] C K .
Proof sketch. Exploiting the structure of DL-Lite core canonical models, one can show that if σ 1 , σ 2 are distinct matches of an exhaustive rooted CCQ q in C K , then there exists a vari-

able v such that σ 1 (v) = σ 2 (v) and σ 1 (v), σ 2 (v) ∈ Ind(A).
It follows that if we take an arbitrary model I of K, and let f be a homomorphism of C K into I, then f injectively maps query matches in C K to query matches in I.

We will also use the next lemma, implicit in [START_REF] Bienvenu | [END_REF], constraining the possible images of matches in C K : Lemma 2. For every DL-Lite core TBox T and CCQ q, we can construct in polynomial time a set of words Γ q,T such that for every KB K = (T , A), match σ of q in C K , and variable v of q: σ(v) = aw for some a ∈ Ind(A) and w ∈ Γ q,T .

We are now ready to show that the problem is PP-complete in combined complexity, and hence in PSpace.

Theorem 7. In DL-Lite core , exhaustive rooted CCQ answering is PP-complete w.r.t. combined complexity.

Proof sketch. The class PP contains all decision problems for which there exists a non-deterministic Turing machine (TM) such that, when the input is a 'yes' instance, then at least half of the computation paths accept, while on 'no' instances, less than half of the computation paths accept.

The lower bound is obtained by a reduction from the following PP-complete problem [START_REF] Bailey | [END_REF]: given a propositional formula ψ in CNF and number n, decide whether ψ has at least n satisfying assignments.

We sketch the TM used to show PP membership, which takes as input a DL-Lite core KB K = (T , A), an exhaustive rooted CCQ q(x), and candidate answer (a, [m, +∞]):

Phase 1. The TM constructs the set Γ q,T from Lemma 2.

Phase 2. The TM guesses a mapping σ of the variables in q to elements from {aw | a ∈ Ind(A), w ∈ Γ q,T }. It then compares m with the number C = |Γ q,T | |q| of possible mappings and proceeds accordingly:

• if m ≥ C
2 + 1, the TM guesses an integer i with 0 ≤ i ≤ 2m -3 and accepts iff σ is a c-match of q(a) and i < C;

• if m < C 2 + 1, the TM guesses an integer i with 0 ≤ i ≤ 2C -2m + 1 and accepts iff σ is c-match for q(a) or i < C -2m + 2.
The guessed integer and comparisons ensure a suitable number of accepting paths. It can be verified that at least half of the paths are accepting iff (a, [m, +∞]) ∈ [q] C K .

Exhaustive Rooted CCQs in DL-Lite R

We now turn to DL-Lite R KBs. Our first result is negative: exhaustive rooted CCQs do not enjoy lower data complexity. This is shown by another reduction from 3COL which involves ideas from our proof of Theorem 4 and the proof of Lemma 16 from [START_REF] Kostylev | [END_REF]. Theorem 8. In DL-Lite R , exhaustive rooted CCQ answering is coNP-complete w.r.t. data complexity.

More positively, we can show an improved coNEXP upper bound in combined complexity for exhaustive rooted CCQs. We briefly sketch the proof, which involves highly non-trivial modifications to the argument used for general CCQs.

We first introduce a more refined notion of interleaving, which replaces the mapping f by the following mapping f * :

f * (a) = f (a) f * (ωR) = f (ωR) if f * (ω), f (ωR) ∈ ∆ * f * (ω)R otherwise
It is possible to prove that when q is an exhaustive rooted CCQ, this modified interleaving yields a countermodel. Moreover, it has a very particular structure, essentially corresponding to the canonical model of the restriction of f (C K ) to ∆ * (viewed as an ABox). Importantly, this means that instead of guessing a whole countermodel, it suffices to guess an initial, exponential-size portion (the |q|-neighborhood of ∆ * ), providing the basis for a coNEXP decision procedure. Theorem 9. In DL-Lite R , exhaustive rooted CCQ answering is in coNEXP w.r.t. combined complexity.

Best Certain Answers

The definition of certain answers implies that if (a, [m, M ]) ∈ [q] K , then we also have (a, [m , M ]) ∈ [q] K for every m ≤ m and M ≥ M . It is naturally of interest to focus on certain answers providing the best bounds, i.e., those of the form (a, [min I|=K q I a , max I|=K q I a ]). In this section, we show that the problem of identifying the best lower bound (min I|=K q I a ) is DP-complete in data complexity. It is easily seen that checking whether m is such an optimal bound can be done in DP, by making a call to a coNP oracle (is (a, [m, +∞]) ∈ [q] K ?) and an NP oracle (is (a, [m+1, +∞]) / ∈ [q] K ?). The DP-hardness of this problem was left as an open question by Kostylev and Reutter. Theorem 10. The following problem is DP-hard in data complexity: given a DL-Lite core KB K = (T , A), rooted CCQ q, tuple a, and number m, decide whether m = min I|=K q I a . Proof sketch. We give a reduction from the following problem (DP-complete due to [START_REF] Garey | [END_REF]): given planar graphs G 1 and G 2 , decide if G 1 ∈ 3COL and G 2 / ∈ 3COL. Let the TBox T col and ABoxes A G1 , A G2 be defined as in the proof of Theorem 4. Rename the individuals to ensure

Ind(A G1 ) ∩ Ind(A G2 ) = ∅, then set K = (T col , A G1 ∪ A G2 ).
Let q color 1 and q edge 1 (resp. q color 2 and q edge 2 ) be defined as before, but using disjoint variables and the root individual from the A G1 (resp. A G2 ). The challenge is to make sure that we can determine the 3-colorability status of the two graphs solely by looking at the number of c-matches of the query. To be able to distinguish G 1 from G 2 , we introduce an asymmetry by duplicating the color counter query for G 1 , i.e., create a copy q color 0 of q color 1 that uses fresh variables but the same root individual. We then take the query

q() := q color 0 ∧ q color 1 ∧ q edge 1 ∧ q color 2 ∧ q edge 2 . We claim (a ∅ , [36, +∞]) ∈ [q] K iff G 1 ∈ 3COL and G 2 ∈ 3COL.
This is proven by a case analysis, summarized here:

G 1 ∈ 3COL G 1 / ∈ 3COL G 2 ∈ 3COL 27 (= 3 × 3 × 3) 48 (= 4 × 4 × 3) G 2 / ∈ 3COL 36 (= 3 × 3 × 4) 64 (= 4 × 4 × 4)
Each of the four cells displays the least value of m such that (a ∅ , [m, +∞]) ∈ [q] K , under different assumptions on the 3colorability of G 1 and G 2 . To establish these values, one must first prove that every model has at least this many c-matches, and then exhibit a model that realizes the exact number. For the latter, we utilize our assumption that the graphs are planar, hence 4-colorable [Gonthier, 2008], which we use to show that the minimal number of c-matches is realized in a model that encodes proper 3-or 4-colorings of the graphs.

The preceding reduction can be adapted to show DPhardness also for the two kinds of CCQs from [START_REF] Kostylev | [END_REF], but without the rootedness restriction.

Conclusion & Future Work

We have revisited the issue of counting queries in OMQA and advanced our understanding of the complexity landscape, both by extending existing results to a more general notion of counting CQ and by exploring when structural restrictions on the ontology and query can lead to improved complexity.

There are several natural avenues for future study. A first challenging problem is to provide a full classification of the data complexity of ontology-mediated queries (i.e. queryontology pairs), in order to identify further tractable cases. It would also be relevant to extend the complexity study to DLs with functional roles or quantified number restrictions, which would allow for non-trivial upper bounds on the number of matches. Tackling general CCQs for such DLs will likely require wholly different techniques from the model manipulations used in Section 4. However, a recent result by [START_REF] Cima | [END_REF] shows that the canonical model property (Theorem 6) holds also for DL-Lite F (which extends DL-Lite core with functional roles), and hence both TC 0 data complexity (Theorem 3) and our PP-completeness result (Theorem 7) for exhaustive rooted CCQs transfer to DL-Lite F .

Much remains to be explored for queries involving other kinds of aggregate functions (min, max, sum, average), which manipulate data values. Recent studies of bag semantics for OMQA [START_REF] Nikolaou | [END_REF][START_REF] Cima | [END_REF] and databases with incomplete information [Hernich and Kolaitis, 2017;[START_REF] Console | [END_REF] provide important formal foundations for supporting such queries.

A Proofs for Section 4 (General Counting CQs) Theorem 1. For every DL-Lite R (resp. DL-Lite core ) KB K = (T , A) and CCQ q, if there is a model of K with fewer than m c-matches of q(a), then there exists one of size

7 O(|A| |T | |q|+1 ) (resp. O(|A| |q| )).
We recall the construction of the interleaving and some of its basic properties. We start with an arbitrary countermodel I, and consider the subdomain ∆ * consisting of individual names from A and the images of all c-matches of q(a):

∆ * = {a I | a ∈ Ind(A)} ∪ σ match for q(a) in I σ(z).
We fix a homomorphism f of C K into I (see Lemma 1) and consider the following mapping from [START_REF] Kostylev | [END_REF]:

f : ∆ C K → ∆ * ∪ ∆ C K d → f (d) if f (d) ∈ ∆ * d otherwise
The interleaving8 I of I is defined as the image of C K by f . More precisely, I has domain

f (∆ C K ) = {f (d) | d ∈ ∆ C K } and interpretation function f • • C K , i.e., A I = {f (d) | d ∈ A C K } and R I = {(f (d 1 ), f (d 2 )) | (d 1 , d 2 ) ∈ R C K }.
It will be useful to exhibit a homomorphism from the interleaving into the original model, which will embed matches. Lemma 3. The following mapping is a homomorphism from I to I.

ρ : ∆ I → ∆ I f (d) → f (d).
Proof. We first check that the definition is well-founded, that is: ρ(f (d)) does not depend on the choice of d. To this end, consider

d 1 , d 2 such that f (d 1 ) = f (d 2 ). Since f maps to ∆ * ∪ ∆ C K , we have two cases to examine: • if f (d 1 ) = f (d 2 ) ∈ ∆ * , that means f (d 1 ) = f (d 1 ) and f (d 2 ) = f (d 2 ), thus ensuring f (d 1 ) = f (d 2 ). • if f (d 1 ) = f (d 2 ) ∈ ∆ C K , that means f (d 1 ) = d 1 and f (d 2 ) = d 2 , thus ensuring again f (d 1 ) = f (d 2 ).
In both cases, we obtain f (d 1 ) = f (d 2 ), so the function is well-founded.

To show that ρ is a homomorphism of I into I, we use the definition of f and fact that f is a homomorphism of

C K to I. Suppose first that f (d) ∈ A I . Then d ∈ A C K , and since f is a homomorphism, ρ(f (d)) = f (d) ∈ A I . Suppose next that (f (d 1 ), f (d 2 )) ∈ R I . Then there exist (d 1 , d 2 ) ∈ R C K such that f (d 1 ) = f (d 1 ) and f (d 2 ) = f (d 2 ). Using again the fact that f is a homomorphism, we obtain (f (d 1 ), f (d 2 )) ∈ R I . By the preceding paragraph, this means (f (d 1 ), f (d 2 )) ∈ R I .
Lemma 4. The interleaving I is a model of K.

Proof. We check that all axioms and assertions from the KB are satisfied.

• All ABox assertions from A are satisfied in C K . Since f = f when restricted to the ABox individuals, and f is a homomorphism of C K in I, it follows that these ABox assertions must also be satisfied in I. • Since I maps homomorphically into I (by Lemma 3), any violation of an axiom from the TBox in I implies a similar violation in I. Since I is a model of K, this cannot occur.

Theorem 11. The interleaving I is a countermodel, and every c-match σ in I satisfies that σ(z) ⊆ ∆ * .

Proof. Assume we have a c-match in the interleaving σ : z → ∆ I , which has an associated match σ for q(a). Since ρ is a homomorphism, ρ • σ is a match for q(a) in the original model I, and its restriction to z, that is, ρ • σ, is a c-match in I. Hence, it follows from the definition of

∆ * that (ρ • σ)(z) ⊆ ∆ * . As ρ -1 (∆ * ) = ∆ * , this implies σ(z) ⊆ ∆ * . Moreover, since ρ |∆ * = id, we in fact have ρ • σ = σ.
We have thus shown that every c-match for q(a) in I is also a c-match for q(a) in I, which means the number of c-matches in I cannot exceed the number of c-matches. As I was assumed to be a countermodel (i.e. having less than m c-matches), it follows that the same holds for I .

In general, the interleaving has an unbounded size. To reduce the size, we will merge some domain elements, while paying attention not to introduce any new matches. To decide which elements can be merged, we will look at their local properties, which will be formalized using the following notions of chains and neighbourhoods (as in [START_REF] Kostylev | [END_REF]). Definition 5 (k-chains with respect to a subdomain). A k-chain in a model M with respect to a subdomain D ⊆ ∆ M is a sequence (d 0 , . . . d k ) with d i in ∆ M , such that for all 0 ≤ i < k, we have (i) d i / ∈ D, and (ii) there exists a positive role R i such that Recall that the definition of ∆ I ensures that any d ∈ ∆ I \ ∆ * is actually an element of ∆ C K and therefore we have d = aw for some individual name a and word w. The tree-shaped structure of ∆ C K ensures that there exists a unique prefix r n,d of aw such that :

(d i , d i+1 ) ∈ R M i .
• f (r n,d ) ∈ N n (d, I , ∆ * ) ;

• for any d ∈ N n (d, I , ∆ * ), there exists a unique word w d n,d such that d = f (r n,d w d n,d ). We denote by Ω n the set of words over the alphabet of role names occuring in the TBox T and with length less or equal to 2n.

Local properties around d are then captured by the following function.

χ n,d : Ω n → ∆ * ∪ {∅} w → f (r n,d w) if r n,d w ∈ ∆ C K and f (r n,d w) ∈ ∆ * ∅ otherwise .
The next definition groups together elements having the same local properties.

Definition 7 (Equivalent elements in the interleaving). The equivalence relation ∼ n on ∆ I is defined as follows: We can now define a smaller countermodel for our CCQ q by merging elements with respect to ∼ |q|+1 . We will use d for the equivalence class of d w.r.t. ∼ |q|+1 , and we denote by π the canonical projection, which maps elements to their respective equivalence classes:

• for d ∈ ∆ I \ ∆ * ,
π : ∆ I → ∆ I /∼ |q|+1 d → d
Definition 8 (Reduced interleaving). The reduced interleaving J is the interpretation with domain ∆ I / ∼ |q|+1 and interpretation of individual names, atomic concepts and roles given by

• J := π • • I .
Once again, it follows from the definition that π : I → J is a homomorphism and that J is a model of K. Since we are considering a quotient, we will not be able to build a general homomorphism from J to I as in Lemma 3. However, local solutions are possible. To improve the readability of the following theorem and later material, we introduce the notation ∆ * for the set {σ | σ ∈ ∆ * }.

Theorem 12. For any d ∈ ∆ I , there exists a homomorphism ρ d :

N |q| (d, J , ∆ * ) → N |q| (d, I , ∆ * ) satisfying that : 1. if e ∈ ∆ * , then ρ d (e) = e ; 2. ρ -1 d (∆ * ) = ∆ * .
Let us first explain how this will conclude our proof, through the following consequence. Corollary 1. If I is a countermodel, then its reduced interleaving J is a countermodel.

Proof. Assume we have a match σ in J . Consider a minimal covering of σ(x ∪ y ∪ z) by |q|-neighbourhoods in J : that is a family of neighbourhoods (N |q| (d 1 , J ), . . . N |q| (d l , J )), with l being minimal and such that σ(x∪y∪z)

⊆ l k=1 N |q| (d k , J ).
In particular, the minimality ensures that the only possible overlapping elements between two different neighbourhoods are elements of ∆ * . Along with condition 1 from Theorem 12, this ensures that the following mapping is well defined:

σ : x ∪ y ∪ z → I v → ρ d k (σ(v)) if σ(v) ∈ N |q| (d k , J )
Furthermore, as the mappings ρ d k provided by Theorem 12 are homomorphisms, it follows that σ is a match in I . Hence, by Theorem 11, we have σ (z) ⊆ ∆ * . However, condition 2 from Theorem 12 ensures (ρ

d k ) -1 (∆ * ) = ∆ * , hence σ(z) ⊆ ∆ * .
Therefore, for each z ∈ z, we have σ(z) = {e z } with e z ∈ ∆ * . From condition 1, it follows that σ (z) = e z . In particular, the mapping σ |z → σ |z is injective, so there are at most as many counting matches in J than in I . Hence, if I is a countermodel, then J also is.

Recalling Theorem 11, we obtain that if I is a countermodel, then J also is.

To conclude the proof of Theorem 1, notice that an equivalence class d is fully characterized by :

• |d| mod 2|q| + 3, that is one equivalent class among 2|q| + 3 possible classes,

• w d |q|+1,d , that is a word over an alphabet with at most |T | symbols and a length at most |q| + 1, • χ |q|+1,d , that is a function from words over an alphabet with at most |T | symbols and length at most 2(|q| + 1), to a set with size at most |∆ * | + 1.

Therefore, the amount of possibly different equivalence classes, that is |∆ J |, is at most:

(2|q| + 3) × |T | |q|+2 × (|∆ * | + 1) |T | 2|q|+3 .
Since |∆ * | ≤ |Ind| + n 0 |q| (recall n 0 is the amount of c-matches in I, and that we can assume n 0 ≤ (|Ind| + |T |) |q| ), we have the claimed bounds for the size of J , which proves Theorem 1.

Coming back to the proof of Theorem 12, we start by building the mappings ρ d . To do so, we need to transform k-chains in the reduced interleaving into k-chains in the interleaving.

Definition 9. (primary role, core of a k-chain) Given a couple (d 1 , d 2 ) of elements in ∆ I \ ∆ * (resp (d 1 , d 2 ) in ∆ J \ ∆ * ),
if there exists a positive role R connecting these two elements, then we call the primary role of the edge

(d 1 , d 2 ) the role SN R such that either d 2 = d 1 S or d 1 = d 2 S -(resp w d2 |q|+1,d2 = w d1 |q|,d1 S or w d1 |q|+1,d1 = w d2 |q|,d2 S -). Notice that T |= S R.
The action of a role R on a word w, denoted R w, is either w if w = w R -, or wR otherwise. Given a k-chain C = (d 0 , . . . d k ) in I (resp in J ), we consider its core, denoted C, being the k-sequence of role names such that C i is the primary role of (d i-1 , d i ).

Given the core C of a k-chain C, we define its action on a word w, denoted C w, by

C k • • • C 1 w.
Remark 2. For any couple (d 1 , d 2 ) of elements in ∆ I \ ∆ * , the role S is the primary role of the edge

(d 1 , d 2 ) (in I ) iff S is the primary role of the edge (d 1 , d 2 ) (in J ).
Lemma 5. For any k-chain in J from d to e, we have

w e |q|+1-k,e = w C d |q|+1-k, C d .
Proof. We proceed by a straightforward induction on the length of C. = w S -, then we have :

• If C is a 0-chain, that is e = d,
w C d |q|+1-(k+1), C d = S w ( C1,... C k ) d k (q+1-k,( C1,... C k ) d k = S w d k |q|+1-k,d k = w e |q|+1-(k+1),e .
Otherwise, we have : Intuitively, the latter proof means that C equals C , up to deleting "dummy" steps in both chains, that are subsequences with shape S 1 . . . S p S - p . . . S - 1 . But since the action of such dummy steps on any word is the identity, then the action of C and C on d are equal. Notice that in general, these dummy steps are necessary to go from d to e, hence we cannot get rid of them by asking for some sort of minimality about chains.

w C d |q|+1-(k+1), C d = S w ( C1,... C k ) d k (q+1-(k+2),( C1,... C k ) d k = S w d k |q|+1-(k+2),d k = w e |q|+1-( k+1
This allows us to define an image for elements in a neighbourhood in the reduced interleaving regardless of the k-chain used to reach this element. Lemma 7. The following mapping is well defined : Otherwise, e / ∈ ∆ * , we know that there is a k + 1-chain (d 0 , . . . d k+1 ) linking d and e. In particular, we have a role R such that (d k , e) ∈ R J . From the definition of R J , we can infer the existence of , ∈ ∆ C K such that:

ρ d : N |q| (d, J ) → N |q| (d, I ) e → e if
∼ |q|+1 d k ∼ |q|+1 e,
and either = S -or = S, where S denotes the primary role of the edge (d k , e). We consider these two cases in turn: We now need to prove ρ d is a homomorphism. We start by proving the following lemma, which states the links of an element e 1 to elements in ∆ * fully determines such links for any other element e 2 that is 1-equivalent to e 1 . Lemma 8. If (e 1 , d) ∈ R J for some d ∈ ∆ * , and if e 1 ∼ 1 e 2 , then (e 2 , d) ∈ R I .

• If = S -, we have ρ d,k ( ) ∼ |q|+1-k d k ∼ |q|+1-k due to d k ∈ N k (d,
Proof. The definition of R J provides 1 , δ ∈ ∆ C K such that :

f ( 1 ) = e 1 f (δ) = d ( 1 , δ) ∈ R C K .
Notice that since d ∈ ∆ * , we have d = {d} and therefore f (δ) = d.

• If e 1 ∈ ∆ * , then e 1 = {e 1 }. It follows that f ( 1 ) = e 1 and e 2 = e 1 . We therefore obtain (e 2 , d)

= (e 1 , d) = (f ( 1 ), f (d)) ∈ f (R C K ) = R I . • Otherwise, e 1 /
∈ ∆ * , which means that f ( 1 ) ∈ ∆ * , and hence f ( 1 ) = 1 and f ( 1 ) ∈ ∆ C K \ Ind(A). Then, the definition of R C K provides a role S ∈ N ± R such that T |= S R and either 1 = δS -or δ = 1 S. Let us consider these two cases in turn:

-If 1 = δS -, then the 1-root of f ( 1 ) = is f (δ) and w e1

1,e1 = S -. We thus have: χ 1,f ( 1) (ε) = f (δ) = d (where ε denotes the empty word). But since f ( 1 ) ∼ 1 e 1 ∼ 1 e 2 , we have χ 1,e2 = χ 1,f ( 1) and w e2 1,e2 = w e1 1,e1 . Combining the preceding facts, we obtain (e 2 , d)

= (r 1,e2 w e2 1,e2 , χ 1,e2 (ε)) = (f (r 1,e2 S -), f (r 1,e2 )) ∈ f (R C K ) = R I . -If δ = 1 S, then we have χ 1,f ( 1) (w f ( 1) 1,f ( 1) S) = f (δ) = d. But since f ( 1 ) ∼ 1 e 1 ∼ 1 e 2 , we have χ 1,e2 = χ 1,f ( 1) and w e2 1,e2 = w f ( 1 ) 1,f ( 1) . Hence : (e 2 , d) = (r 1,e2 w e2 1,e2 , χ 1,f ( 1) (w f ( 1) 1,f ( 1) S)) = (r 1,e2 w e2 1,e2 , χ 1,e2 (w e2 1,e2 S)) = (f (r 1,e2 w e2 1,e2 ), f (r 1,e2 w e2 1,e2 S)) ∈ f (R C K ) = R I .
Proof Otherwise, e, e / ∈ ∆ * . Notice that both cannot be in N |q| (d, J ) \ N |q|-1 (d, J ) at the same time. Indeed, if both were, there would be a 2|q| + 1-chain from d to d (recall e, e / ∈ ∆ * ). However, the depth modulo 2|q| + 3 encoded in each equivalent class along this chain only increases or decreases by 1 at each step (since none of its element belongs to ∆ * ). Hence, |d| mod 2|q| + 3 would equal itself up to 2|q| + 1 such 1-steps, which is impossible modulo 2|q| + 3. Therefore, we can assume that e ∈ N |q|-1 (d, J ). We have a k-chain C d→e from d to e, with k < |q|. Complete it by R into a k + 1 chain C d→e to reach e . Since k + 1 ≤ |q|, we have by definition ρ d (e ) = S ρ d (e), with S the primary role of the edge (e, e ). In both cases, ρ d (e ) ending by S -or not, it ensures that (ρ d (e), ρ d (e ) ∈ S I ⊆ R I .

The preservation of positive concepts follows. Indeed, if we have an element e and a concept name A such that e ∈ A J , then, from the definition of A J , either e is the interpretation of an individual name e and B(e) ∈ A for some concept B such that T |= B A, or there exists another element e connected to e by a positive role S such that T |= ∃S -A.

In the first case, we have in particular e ∈ ∆ * , thus ρ d (e) = e = e I ∈ A I since I is a model. In the second case, since ρ d preserves positive roles, we have (ρ d (e ), ρ d (e)) ∈ S I , and therefore ρ d (e) ∈ A I since I is a model.

B Proofs for Section 5 (Rooted Counting CQs)

Theorem 3. (Implicit in [START_REF] Nikolaou | [END_REF][START_REF] Cima | [END_REF]) In DL-Lite core , exhaustive rooted CCQ answering is TC 0 -complete9 w.r.t. data complexity.

Proof. We start with the TC 0 hardness. The reduction from the NUMONES problem works as follows: given an instance (s, k), we create an ABox A s := {R(a, s k ) | s k ∈ s ∧ s k = 1}, along with the empty TBox T = ∅ and exhaustive rooted CCQ q := ∃z R(a, z). It is clear that (∅, [k, +∞]) ∈ [q] (T ,As) ⇐⇒ (s, k) ∈ NUMONES. It can be verified that this simple reduction can be implemented by AC 0 circuits (so constitutes an AC 0 -reduction, as required).

As explained in the body of the paper, TC 0 membership follows from results in [START_REF] Nikolaou | [END_REF]. While that paper only formally states membership in LogSpace, a follow-up paper on bag semantics [START_REF] Cima | [END_REF] states TC 0 membership for DL-Lite F (which properly contains DL-Lite core ), by making use of prior complexity results for bag relational algebra. We believe it is nevertheless instructive to have a direct proof and therefore describe what follows how to construct a family of TC 0 circuits to decide our problem.

We need a family of circuits in order to be able to handle ABoxes of different sizes. More precisely, we will create one circuit for each possible number of individual names. We can assume w.l.o.g. that the same set of individuals, denoted Ind , is used for all of the ABoxes having individuals. Let us now explain how to represent an input (A * , a * , m * ) to the circuit that handles -individual ABoxes.

• Each atomic role P appearing in T and/or q is represented by input gates P(a,b)∈A? for a, b ∈ Ind . The gate P(a,b)∈A? is set to 1 iff P(a, b) ∈ A * .

• Each atomic concept A appearing in T and/or q is represented by input gates A(a)∈A? for a ∈ Ind . The gate A(a)∈A? is set to 1 iff A(a) ∈ A * .

• The tuple a * is represented by input gates a k =a for 1 ≤ k ≤ |x| and a ∈ Ind . The gate is set to 1 iff a * k = a.

• The integer m * is represented in binary by input gates b k =1 for each 0

≤ k < log 2 (|Ind(A * )| + |T |) |q| ).
The gate b k =1 is set to 1 iff the k th bit of m * is 1 (with 0 th -bit being the least significant bit). Regarding the last point, we use the observation from [START_REF] Kostylev | [END_REF]

that if (a * , [m * , +∞]) ∈ [q] (T ,A * ) , then m * cannot exceed (|Ind(A * )| + |T |) |q| = (|Ind | + |T |) |q|
. This is a direct consequence of the fact that every satisfiable DL-Lite R KB K = (T , A) has a model with at most |Ind(A)| + |T | elements.

We now describe the other parts of the circuit. We introduce, for each relevant positive concept C (i.e., atomic concept or existential concept ∃R that uses concept and role names from T and/or q) and each individual name a ∈ Ind , a disjunctive gate ∨ K|=C(a)? taking as inputs: The preceding gates determine the ABox part of the canonical model. We next need to decide the existence of each element of the form aw, where a ∈ Ind(A) and w ∈ Γ q,T \ ε (by Lemma 2, these are the only anonymous elements that can occur in a match for q). For each such aw, we denote by R w the first role name of w and introduce a conjunctive gate ∧ aw∈∆ C K ? which takes as input:

• The negation ¬ ∀b∈Ind(A) ¬R(a,b)? of a disjunctive gate ∨ ∃b∈Ind(A) R(a,b)? taking as inputs the gates:

- P(a,b) for each b ∈ Ind , if R = P ∈ N R . - P(b,a)
for each b ∈ Ind if R = P -with P ∈ N R . which verifies that there is not already a R w -successor to a.

• The gate ∨ K|=∃Rw(a)? that checks that a witnessing R w -successor is needed. The circuit next determines for each mapping σ : x ∪ z → {aw|a ∈ Ind , w ∈ Γ q,T }, whether σ is a match for q(a * ). Notice that, regardless of the input ABox, we can restrict to a set of relevant mappings by keeping only those which map the answer variables x to individuals from Ind and which map variables v 1 , v 2 occurring in a role atom R(v 1 , v 2 ) from q onto either:

• a pair of individual names, or

• a pair w 1 , w 2 such that w 2 = w 1 R or w 1 = R -w 2 .
Similarly, we can restrict the set of relevant mappings by keeping only those which map variable v occuring in a concept atom A(v) from q onto either an individual name, or an element awR, where K |= ∃R -A. Clearly, any mapping σ that does not respect these conditions cannot be a match, due to the definition of R C K . This restriction simplifies the process of checking if a mapping is a match for q(a * ): we are only left with verifying the existence of the anonymous elements in its image, as well as the validity of the atoms mapped onto the ABox part of the canonical model.

For each relevant mapping σ, we introduce a conjunctive gate ∧ σ match ? taking as inputs all gates:

• a k =σ(x k )? for each 1 ≤ k ≤ |x| (to check x is mapped on a * ). • ∧ σ(z)∈∆ C K ? for each z ∈ z such that σ(z) / ∈ Ind (to check for existence of σ(z) under input A * ). • R(σ(v1),σ(v2))∈A? for each v 1 , v 2 ∈ x ∪ z such that R(v 1 , v 2 ) ∈ q and σ(v 1 ), σ(v 2 ) ∈ Ind(A) (
to check the validity of the mapping for pairs of variables mapped on individual names).

• ∨

K|=A(σ(v))? for each v ∈ x ∪ z such that A(v) ∈ q and σ(v) ∈ Ind(A) (to check the validity of the mapping for variables mapped on individual names).

We will next use threshold gates in order to compute the total number of matches. Introduce, for each k = 0, . . . , (Ind × Γ q,T ) |q| , a threshold gate k q C K a ≥k? taking as input every ∧ σ match ? . The gate k q C K a ≥k?

returns 1 iff at least k of its inputs are 1. By construction, the latter holds iff there are at least k matches for q(a * ).

In parallel, we introduce a conjunctive gate ∧ m=k? for each k = 0, . . . , (Ind × Γ q,T ) |q| taking as inputs: • the input gates bj =1? such that the j th bit of the binary encoding of k is 1

• the negation of each input gate bj =1? such that the j th bit of the binary encoding of k is 0

The gate ∧ m=k? returns 1 iff m * = k. We combine the preceding two types of gates to compare m * and the computed number of matches. For each k = 0, . . . , (Ind × Γ q,T ) |q| , we introduce a conjunctive gate ∧ q C K a ≥m? taking as input k q C K a ≥k? and ∧ m=k? . Finally, our output gate is a disjunctive gate ∨ output taking as inputs all gates ∧ q C K a ≥m? . By construction, this gate outputs 1 iff there are at least m * matches of q(a * ) in the canonical model of the considered KB.

The depth of the circuit is 7, and is hence constant, showing membership in TC 0 .

Example 3. Let T be the following DL-Lite core TBox T = {D ∃R, ∃R -∃R} and q be the exhaustive rooted CCQ given by q(x) = ∃z R(x, z) Observe that even if the second axiom from T suggests the need to consider suffixes R . . . R of arbitrary length, we only have Γ q,T = {ε, R}.

We propose to illustrate the construction of the circuit designed for 2-individual ABoxes, with individual names a and b. We thus require log 2 ((2 + 2) 1 ) + 1 = 3 input gates representing the input integer, and we have 6 relevant matches given by:

• (σ 1 ) x → a z → a • (σ 2 ) x → a z → b • (σ 3 ) x → a z → aR • (σ 4 ) x → b z → b • (σ 5 ) x → b z → a • (σ 6 )
x → b z → bR The corresponding circuit is depicted in Figure 1.

Theorem 4. In DL-Lite core , rooted CCQ answering is coNP-complete w.r.t. data complexity.

Proof. We briefly recall the reduction sketched in the body of the paper. Starting from an instance G = (V, E) of the decision problem 3COL, we consider the ABox A G given by:

A G ={Vertex(a, u) | u ∈ V} ∪ {Edge(u 1 , u 2 ) | (u 1 , u 2 ) ∈ E} ∪ {Vertex(a, a v ), Edge(a v , a v ), HasCol(a v , r), HasCol(a v , g), HasCol(a v , b)}
and the TBox T := {∃Vertex - ∃HasCol}, and we denote by K G = (T , A G ) the resulting KB. A part of the canonical model of K G is depicted in Figure 2.

We consider the two following rooted CCQs:

q edge = ∃y c ∃z 1 ∃z 2 Vertex(a, z 1 ) ∧ Vertex(a, z 2 ) ∧ Edge(z 1 , z 2 ) ∧ HasCol(z 1 , y c ) ∧ HasCol(z 2 , y c )
q col = ∃y ∃z Vertex(a, y) ∧ HasCol(y, z)

We let q be the query obtained by taking the conjunction of these two queries and keeping all of the variables existentially quantified. The query q is displayed in Figure 3. The three counting variables (z 1 , z 2 , z) are indicated by large gray dots. It is not hard to see that (a ∅ , [3, +∞]) ∈ [q] K G . Indeed, there are at least 9 matches of q in any model I of K, given by:

z 1 , z 2 , y → a v y c → r | g | b z → r |g | b
These 9 matches give rise to 3 c-matches for q, corresponding to the three ways of mapping counting variable z. To complete the proof, we establish the following claim.

Claim.

(a ∅ , [4, +∞]) ∈ [q] K G ⇐⇒ G / ∈ 3COL. (⇒) Assume (a ∅ , [4, +∞]) ∈ [q] K G ,
and take some possible coloring τ : V → {r, g, b} of the graph G. Let I G τ be the model of K G whose domain is Ind(A G ) and which interprets roles Vertex and Edge exactly following the ABox, and which interprets HasCol according to τ :

HasCol I G τ = {(a v , r), (a v , g), (a v , b)} ∪ {(v, τ (v)) | v ∈ V} Intuitively, I τ is
obtained from the canonical model by replacing the element vHasCol with τ (v).

By hypothesis, there is a fourth c-match σ for q in I G τ . It is easily verified that the additional match can only result from the atom Edge(z 1 , z 2 ) being mapped onto an edge Edge(u 1 , u 2 ) that is different from Edge(a v , a v ). From the definition of I G τ , this implies that the edge (u 1 , u 2 ) of G is monochromatic, both vertices sharing the color σ(y c ). Thus, τ is not a 3-coloring. As this construction holds for any possible coloring τ , we obtain G / ∈ 3COL. • a • a

• u 1 • u 2 • u 1 HasCol • u 2 HasCol • r • g • b • a v V e
z 1 z 2 • y c • y z V e r t e x V e r t e x Vertex HasCol Edge H a s C o l H a s C o l
Figure 3: The rooted CCQ q, which is the conjunction of q edge (left part) and q col (right part).

(⇐) Assume G / ∈ 3COL, and take some model I of K G . By Lemma 1, there is a homomorphism f : C K G → I (which preserves individual names). Define τ : V → ∆ I as follows: τ (u) = f (uHasCol). There are two cases to consider:

• If there exists u ∈ V such that τ (u) /
∈ {r, g, b}, then this provides a match of q in I given by z → τ (u) and y → u I , whose restriction to the counting variables is a new c-match.

• Else, since G / ∈ 3COL, there exists an edge (u 1 , u 2 ) ∈ E such that τ (u 1 ) = τ (u 2 ). It provides a new match given by:

z → r y → a v z 1 → u 1 z 2 → u 2 y c → τ (u 1 ) (= τ (u 2 ))
In both cases, there is a fourth c-match for q. We thus obtain (a ∅ , [4, +∞]) ∈ [q] K G .

Theorem 5. In DL-Lite R , rooted CCQ answering is coNEXP-hard w.r.t. combined complexity.

Proof. The proof is by reduction from the exponential grid tiling problem (EXPTIL). We recall that an instance of this problem consists of a set C of colors, two relations H, V ⊆ C × C that give the horizontal and vertical tiling conditions, and a number n. The task is to decide whether there exists a valid (H, V)-tiling of an 2 n × 2 n grid, i.e., a mapping τ : {0, . . . , 2 n -1} × {0, . . . , 2 n -1} → C such that (τ (i, j), τ (i + 1, j)) ∈ H for every 0 ≤ i < 2 n -1 and (τ (i, j), τ (i, j + 1)) ∈ V for every 0 ≤ j < 2 n -1. In what follows, we consider an instance (n, C, H, V) be an instance of the EXPTIL problem.

To be able to test for the existence of a tiling of a 2 n × 2 n grid, we must start by ensuring we can find such a grid in each model. Furthermore, we will need to detect horizontal and vertical adjacency in this grid, it is thus appropriate to use horizontal/vertical coordinates. To ensure a polynomial reduction, we need to use a binary encoding of these coordinates. We start from a root a and an initial element b and use TBox axioms to build two witnesses to represent the two possible values for the n th bit of the horizontal coordinates:

Roots(a, b) ∃Roots -∃H n 0 ∃Roots -∃H n 1
We use further axioms to generate all possible horizontal coordinates, and we proceed similarly with the vertical coordinates, until we generate all possible pairs of coordinates. Concretely, we include the following axioms:

∃(H i b ) -∃H i-1 b ∃(H 1 b ) -∃V n b ∃(V i b ) -∃V i-1 b for all b, b ∈ {0, 1}, 1 < i ≤ n
The preceding axioms will generate a binary tree of height 2n in the canonical model, whose leaves represent all possible grid positions. We use the following two axioms assign a color to each of the points representing a grid position:

∃(V 1 0 ) -∃HasCol ∃(V 1 1 )
-∃HasCol To help us compare positions, we will include the following TBox axioms, for all b ∈ {0, 1} and 1 ≤ i ≤ n:

∃(H i b ) -∃HasBit b ∃(V i b ) -∃HasBit b
We will also introduce a general role (HV) to more compactly navigate the tree:

H i b HV V i b HV (b ∈ {0, 1}, 1 ≤ i ≤ n)
This completes our description of the TBox. We will finish our description of the ABox later in the proof, but it will be useful to know that it will contain an ABox individual c for every color c ∈ C and two ABox individuals (one, zero) to represent bits.

Let us now define the query q. To keep track of the colors used in a candidate tiling, we will use the following subquery:

q col = ∃y col 0 . . . ∃y col 2n ∃z col Roots(a, y col 0 ) ∧ 2n-1 i=0 HV(y col i , y col i+1 ) ∧ HasCol(y col 2n , z col )
Observe that z col is the only counting variable. We also need to be able to detect if other bits than the intended ones (one, zero) are being used to satisfy the axioms H - b ∃HasBit b and V - b ∃HasBit b . For this purpose, we will introduce the two following subqueries:

q 0 =∃y 0 0 . . . ∃y 0 2n ∃z 0 Roots(a, y 0 0 ) ∧ 2n-1 i=0 HV(y 0 i , y 0 i+1 ) ∧ HasBit 0 (y 0 2n , z 0 ) q 1 =∃y 1 0 . . . ∃y 1 2n ∃z 1 Roots(a, y 1 0 ) ∧ 2n-1 i=0 HV(y 1 i , y 1 i+1 ) ∧ HasBit 1 (y 1 2n , z 1 )
We note that each of the preceding queries has a single counting variable (z 0 or z 1 ). The axioms for HV together with the construction of the ABox will that every element used as a bit (i.e., in the second argument of HasBit) gives rise to a c-match for one of these two queries.

We next discuss the parts of the query that are used to check the tiling conditions. To detect adjacency, we remark that two grid positions (h 1 , v 1 ), (h 2 , v 2 ) ∈ {0, . . . , 2 n -1} × {0, . . . , 2 n -1} are vertically adjacent iff:

• h 1 = h 2 , so the binary encodings of h 1 and h 2 are the same;

• v 2 = v 1 + 1, so the binary encodings of v 2 and v 1 are the same until, at some point, v 2 ends with 1 • 0 k while v 1 ends with 0 • 1 k . To detect a violation of the vertical tiling condition (i.e. two vertically adjacent tiles with colors c and c such that (c, c ) / ∈ V), we need n queries, one for each possible position where the bit from the vertical coordinates differ. For each 1 ≤ k ≤ n, we create a subquery q V,(c,c ),k defined as follows. Note that the variables in q V,(c,c ),k all have the superscript • V,(c,c ),k , which means they do not occur in any other subquery, but these superscripts are omitted in the definition for the sake of readability. q V,(c,c ),k = ∃z∃y l,1 . . . ∃y l,2n ∃y r,1 . . . ∃y r,2n ∃y s,1 . . . ∃y s,n+k Roots(a, z) ∧ HV(z, y l,1 ) ∧ HV(z, y r,1 ) ∧ 2n-1 i=1 HV(y l,i , y l,i+1 ) ∧ HV(y r,i , y r,i+1 )

∧ HasCol(y l,2n , c) ∧ HasCol(y r,2n , c ) ∧ n+k-1 i=1 HasBit(y l,i , y s,i ) ∧ HasBit(y r,i , y s,i ) ∧ HasBit(y l,n+k , zero) ∧ HasBit(y r,n+k , one) ∧ 2n i=n+k+1 HasBit(y l,i , one) ∧ HasBit(y r,i , zero)
Note that z is the only counting variable of q V,(c,c ),k . We can similarly define a set of subqueries q H,(c,c ),k (1 ≤ k ≤ n) that detect violations of the horizontal tiling conditions.

Finally, we let q be the conjunction of the all of the preceding subqueries. It is displayed in Figure 4. The set of counting variables of q is the union of the counting variables of its subqueries. We observe that q is rooted, as it has a single connected component which contains the individual a.

We can now define the ABox, which introduces individuals for the intended colors and bits and a further individual d that serves to ensure that all parts of the query can be matched:

A = {Roots(a, b), Roots(a, d), HV(b, b), HasBit 0 (d, zero), HasBit 1 (d, one)} ∪ {H k b (d, d) | b ∈ {0, 1}, k = 1, . . . n} ∪ {V k b (d, d) | b ∈ {0, 1}, k = 1, . . . n} ∪ {HasCol(d, c) | c ∈ C}.
Let p = |C|, and let K be the KB with the preceding TBox and ABox. A part of the canonical model C K is displayed in Figure 5. To complete the proof, it suffices to establish the following claim: Figure 4: A part of the rooted query q, being the conjunction of q 0 (above left), q 1 (above right), q col (below left), several q V,(c,c ),k (below right, only one is depicted with omitted superscripts), and several q H,(c,c ),k (none is depicted).

• a • y 0 0 • y 0 1 • y 0 2n-1 • y 0 2n z 0 • y 1 0 • y 1 1 • y 1 2n-1 • y 1 2n z 1 • y col 0 • y col 1 • y col 2n-1 • y col 2n z col z • y l,1 • y l,2n-2 • y l,2n-1 • y l,2n • y r,1 • y r,2n-2 • y r,2n-1 • y r,2n • c • c • y s,1 . . . • y s,2n-2 • one • zero R o o
Claim (∅, [p + 1, +∞]) ∈ [q] K ⇐⇒ (n, C, H, V) / ∈ EXPTIL.
The proof of this claim is similar in spirit to the proof of Theorem 4. First observe that there are always at least p c-matches given by mapping the counting variables as follows:

z col → c 1 | . . . | c p z 0 → zero z 1 → one z H,(c,c ),k , z V,(c,c ),k → d
and mapping all of the existential variables to d.

(⇒) Assume (∅, [p + 1, +∞]) ∈ [q] K , and take some potential tiling τ : {0, . . . 2 n -1} × {0, . . . 2 n -1} → {c | c ∈ C}. Let I τ be the model of K that is obtained from C K as follows:

• ∆ Iτ contains all elements from ∆ C K except those anonymous elements whose last symbol is HasCol, HasBit 0 , or HasBit 1 (i.e. witnesses for axioms involving ∃HasCol, ∃HasBit 0 , or ∃HasBit 1 );

• the roles HasCol, HasBit 0 , HasBit 1 are interpreted as follows:

HasBit Iτ 0 :={(d, zero)} ∪ {(bH n hn . . . H k h k H k-1 0 , zero) | h n , . . . h k ∈ {0, 1}, k = 1, . . . n + 1} ∪ {(bH n hn . . . H 1 h1 V n vn . . . V k v k V k-1 0 , zero) | h n , . . . h 1 , v n , . . . v k ∈ {0, 1}, k = 0, . . . n + 1} HasBit Iτ 1 :={(d, one)} ∪ {(bH n hn . . . H k h k H k-1 1 , one) | h n , . . . h k ∈ {0, 1}, k = 1, . . . n + 1} ∪ {(bH n hn . . . H 1 h1 V n vn . . . V k v k V k-1 1 , one) | h n , . . . h 1 , v n , . . . v k ∈ {0, 1}, k = 0, . . . n + 1} HasCol Iτ :={(d, c k ) | k = 1, . . . p} ∪ {(bH n hn . . . H 1 h1 V n vn . . . V 1 v1 , τ (h n . . . h 1 , v n . . . v 1 ) | h n , . . . h 1 , v n , . . . v 1 ∈ {0, 1}}
where by a slight abuse of notation, we use τ (h n . . . h 1 , v n . . . v 1 ) to mean τ (h, v), with h and v the numbers whose binary encodings are h n . . . h 1 and v n . . . v 1 respectively;

• the remaining roles are interpreted exactly as in C K .

The model I τ is displayed in Figure 6. By hypothesis, there is an additional c-match σ for q in I τ . It is easily verified that the additional match can only result from an atom Roots(a, z D,(c,c ),k ), with D ∈ {H, V}, (c, c ) ∈ (C × C) \ D and k ∈ {1, ...n}, being mapped onto Edge(a, b). From the definition of I τ , this implies that there are two horizontally (or vertically) adjacent tiles, which positions are given by the elements σ(y D,(c,c ),k l,2n

) and σ(y

D,(c,c ),k r,2n
), whose respective colors c and c violate D. Thus, τ is not an (H, V)-tiling. As this construction holds for any possible tiling τ , we can infer that (n, C, H, V) / ∈ EXPTIL. (⇐) Assume (n, C, H, V) / ∈ EXPTIL, and take some model I of K. By Lemma 1, there is a homomorphism f : C K → I. Define τ : {0, . . . , 2 n -1} × {0, . . . n} → ∆ I as follows: τ (h n . . . h 1 , v n . . . v 1 ) := f (bH n hn . . . H 1 h1 V n vn . . . V 1 v1 HasCol) (again slightly abusing notation by applying working with binary encodings of numbers). There are three cases to consider:

• a • b • • • • • • • • • • • • • • • • • • • • • zero • one • d • c 1 . . . • c p Roots Roots HV H n 0 H n 1 H 0 0 H 0 1 V n 0 V n 1 V 0 0 V 0 1 HasCol HasCol H k b , V k b H a s C o l H a s C o l H a s B i t1 H a s B it 0 H a s B it 0 H a s B it 0 H a s B it 0 H a s B it 1 H a s B it 1 H a s B it 1
• If there exists (h n . . . h 1 , v n . . . v 1 ) such that τ (h n . . . h 1 , v n . . . v 1 ) / ∈ {c | c ∈ C}, then this provides a match of q in I in which the subquery q col is mapped as follows:

z col → τ (h n . . . h 1 , v n . . . v 1 ) y col 0 → b y col 1 → f (bH n hn ) . . . y col 2n → f (bH n hn . . . H 1 h1 V n vn . . . V 1 v1 ),
and whose restriction to the counting variables provides a new c-match.

• Otherwise, suppose there exists an element that is in the range of HasBit 0 that is not zero, or that is in the range of HasBit 1 but not equal to one, then this also provides a new c-match of q, in which either z 0 or z 1 is mapped to this element. Note that this kind of 'error' may occur at any level of the tree of positions. This is why we included the ABox assertion HV(b, b), which makes it possible for us to loop as long as needed in order to obtain a sufficiently long chain of HV to satisfy the query q 0 or q 1 .

• Else, since (n, C, H, V) / ∈ EXPTIL, there exist two adjacent positions with coordinates (h n . . . h 1 , v n . . . v 1 ) and

(h n . . . h 1 , v n . . . v 1 ) such that (τ (h n . . . h 1 , v n . . . v 1 ), τ (h n . . . h 1 , v n . . . v 1 )) ∈ (C × C) \ D, for D either H or V.
Letting k be the bit from which the encoding of the non-D coordinate differs, we obtain a new c-match for q, in which the subquery q D,(τ (hn...h1,vn...v1),τ (h n ...h 1 ,v n ...v 1 )),k) is satisfied by mapping z D,(τ (hn...h1,vn...v1),τ (h n ...h 1 ,v n ...v 1 )),k) to b.

In every case, there is an additional c-match for q. We thus obtain (a ∅ , [p + 1, +∞])

∈ [q] K . • a • b • • • • • • • • • • • zero • one • d • c 1 . . . • c p Roots Roots HV H n 0 H n 1 H 0 0 H 0 1 V n 0 V n 1 V 0 0 V 0 1 H a s C o l H a sC o l H k b , V k b H a s C o l H a s C o l H a s B i t 1 H a s B i t 0 H a sB it0 Has Bit0 H a s B it 0 H a s B i t 1 H a s B it 1 Ha sB it 1 H a s B i t 1 HasBit 0 Figure 6: A part of Iτ with τ (2 n -1, 2 n -2) = τ (2 n -1, 2 n -1) = c1.
C Proofs for Section 6 (Exhaustive Rooted Counting CQs)

We start by recalling an important property of the canonical model construction for DL-Lite core KBs. Lemma 9. For any role R ∈ N ± R and anonymous element d 1 in the canonical model C K of a DL-Lite core KB K, there is at most one element

d 2 ∈ C K such that (d 1 , d 2 ) ∈ R C K .
Proof. We provide a proof for the sake of completeness. From the definition of R C K , if d 1 is an anonymous domain element and (d 1 , d 2 ) ∈ R C K , then either:

• d 1 = d 2 S -for some role S such that T |= S R, or • d 2 = d 1 S for some role S such that T |= S R.
In both cases, since T is a DL-Lite core TBox, the condition on S holds only if S = R. Moreover, we observe that if the first case holds, i.e., d 1 = d 2 R -, then the definition of ∆ C K prevents the creation of an element d 1 R. It follows that only one of the preceding cases can hold, and so there can be at most one d 2 with (d 1 , d 2 ) ∈ R C K . Theorem 6. For every DL-Lite core KB K and exhaustive rooted CCQ q, it holds that [q] K = [q] C K .

Proof. The general argument was given in the sketch. All that remains to show is that if σ 1 , σ 2 are distinct matches of a exhaustive rooted CCQ q in C K , then there exists a variable v such that σ 1 (v) = σ 2 (v) and σ 1 (v), σ 2 (v) ∈ Ind(A).

Suppose for a contradiction that this is not the case. There there are distinct matches σ 1 , σ 2 of q in C K such that for all variables v such that σ 1 (v) = σ 2 (v), either σ 1 (v) ∈ Ind(A) or σ 2 (v) ∈ Ind(A). As q is exhaustive rooted, every variable v is connected to either an answer variable or individual in the Gaifman graph. Let d(v) denote the length of the shortest path from

v to an answer variable of individual. Note that d(v) = 0 iff v is an answer variable. Since σ 1 and σ 2 are distinct, there exists a variable v such that σ 1 (v) = σ 2 (v). Choose such a variable v * with minimal d-value, i.e., if d(u) < d(v * ), then σ 1 (u) = σ 2 (u).

By assumption, either σ 1 (v * ) ∈ Ind(A) or σ 2 (v * ) ∈ Ind(A). We'll suppose the former (the other case is treated analogously). Note that v * cannot be an answer variable (else we would have σ 1 (v * ) ∈ Ind(A)). It follows that d(v * ) > 0, and so we can find another variable u * and role name R ∈ N ± R , with d(u * ) = d(v * ) -1 and either R(u * , v * ) ∈ q or R -(v * , u * ) ∈ q (recall that if R = P -, then R -= P ). As σ 1 and σ 2 are matches of q in C K , we therefore have (σ

1 (u * ), σ 1 (v * )) ∈ R C K and (σ 2 (u * ), σ 2 (v * )) ∈ R C K . Moreover, since d(u * ) < d(v * ), we have σ 1 (u * ) = σ 2 (u * ).
There are two cases to consider:

• Case 1: σ 1 (u * ) = σ 2 (u * ) = c ∈ Ind(A).
From the proof of Lemma 9, we know that σ 1 (v * ) = cR. The fact that cR ∈ ∆ C K implies that there is no individual b such that (c, b) ∈ R C K . Thus, we must have σ 2 (v * ) = cR, which yields σ 1 (v * ) = σ 2 (v * ), contradicting our earlier assumption.

• Case 2: σ 1 (u * ) = σ 2 (u * ) ∈ Ind(A). By Lemma 9, there is a unique element e such that (σ 1 (u * ), e) ∈ R C K . We thus obtain σ 1 (v * ) = e = σ 2 (v * ), a contradiction.

As both cases lead to a contradiction, it must therefore be the case that the statement holds.

Theorem 7. In DL-Lite core , exhaustive rooted CCQ answering is PP-complete w.r.t. combined complexity.

We start by completing the argument for the PP upper bound.

Proof. Recall the algorithm described in the proof sketch.

Phase 1 The TM deterministically constructs the set Γ q,T of words from Lemma 2. Phase 2 The TM guesses a mapping σ of the variables in q to elements from {aw | a ∈ Ind(A), w ∈ Γ q,T }. It then compares m with the number C = |Γ q,T | |q| of possible mappings and proceeds accordingly:

• if m ≥ C 2 + 1, the TM guesses an integer i with 0 ≤ i ≤ 2m -3 and accepts iff σ is a c-match of q(a) and i < C;

• if m < C
2 +1, the TM guesses an integer i with 0 ≤ i ≤ 2C -2m+1 and accepts iff σ is c-match for q(a) or i < C -2m+2. Due to Theorem 6 and Lemma 2, an input is a 'yes' instance iff q C K a ≥ m (recall that q C K a denotes the exact number of c-matches for q(a) in C K ). To finish the proof of PP membership, we need to examine the number of accepting computation paths for the described TM and show that when q C K a ≥ m, at least half of the computation paths accept, and when q C K a < m, less than half of the computation paths accept. Let us consider the two cases from Phase 2:

• If m C 2 + 1, then the number of accepting computation paths is q C K a × C, corresponding to cases where the TM guesses a mapping that is a c-match, then guess a number 0 ≤ i < C. The total number of computation paths is C × (2m -2), corresponding to a guess of one of the C mappings, then the guess of an integer 0

≤ i ≤ 2m -3. • If m < C 2 + 1, then the number of accepting computation paths is q C K a × (2C -2m + 2) + (C -q C K a ) × (C -2m + 2) = C(C -2m + q C K a + 2
), corresponding to the sum of the number of cases where we guess a c-match followed by an integer 0 ≤ i ≤ 2C-2m+1 and the number of cases where we guess a mapping that is not a c-match followed by an integer i with 0 ≤ i < C -2m + 2. The total number of computation paths is C × (2C -2m + 2) (guess one of the C mappings, then guess an integer 0 ≤ i ≤ 2C -2m + 1).

In both cases, it is easily verified that:

q C K a ≥ m ⇐⇒ #accepting computation paths #possible computation paths > 1 2 .
(Note that in the first case, we always have m ≥ 2, so the value 2m -2 in the denominator is positive, while in the second case, C ≥ 1 implies that the value (2C -2m + 2) in the denominator is positive.)

We next give the proof of PP-hardness.

Proof. We recall that the lower bound is by reduction from the following PP-complete problem: given a propositional formula ψ in CNF and number n, decide whether ψ has at least n satisfying assignments. Consider an instance of this problem, given by the formula ψ := ∃u l k=1 ξ k (with ξ k is a 3-clause) and number N . We consider the KB K ψ = (∅, A ψ ), which has an empty TBox, and whose ABox A ψ contains the following assertions:

• Clause k (a, ξ p k ) for each clause ξ k and each p ∈ {1, ...7}, with each ξ p k representing one of the 7 satisfying assignments for the clause ξ k ;

• Asn 1 (ξ p k , ξ p k (ω 1 k )), Asn 2 (ξ p k , ξ p k (ω 2 k )) and Asn 3 (ξ p k , ξ p k (ω 3 k ))
for each p = 1, ...7 and each clause ξ k , where ξ p k (ω i k ) is the truth value (true or false) assigned by ξ p k to the ith variable occurring in the kth clause.

, 2 , 3 1 , 2 3 1 , 3 2 1 2 , 3 2 1 , 3 3 1 , 2 1 , 2 , 3 1 , 2 , 3 1 , 2 3 1 , 3 2 2 , 3 1 2 1 , 3 3 1 , 2 1 , 2 , 3 Figure 7: The canonical model CK ψ with ψ = (u1 ∨ ¬u2 ∨ ¬u3) ∧ (¬u1 ∨ u3 ∨ u4)
It may be helpful to refer to Figure 7, which depicts the canonical model of C K ψ for an example formula ψ.

As for the query, we consider the following exhaustive rooted CCQ (depicted in Figure 8):

q ψ := ∃z ξ1 . . . ∃z ξ l ∃z u1 . . . ∃z un l k=1 Clause k (a, z ξ k ) ∧ 3 i=1 Asn i (z ξ k , z ω i k ) • a z ξ1 z ξ2 z u1 z u2 z u3 z u4 C l a u s e 1 C l a u s e 2 A s n 1 A s n 2 A s n 3 A s n 1 A s n 2 A s n 3 Figure 8: The query q ψ with ψ = (u1 ∨ ¬u2 ∨ ¬u3) ∧ (¬u1 ∨ u3 ∨ u4)
To complete the proof, we establish the following claim. Claim. (∅, [N, +∞]) ∈ [q ψ ] K ψ ⇐⇒ ψ has at least N satisfiying assignments (⇒) Assume (∅, [N, +∞]) ∈ [q ψ ] K ψ . This implies in particular that there are N c-matches for q ψ in C K ψ . Since the TBox is empty, the domain of C K ψ is Ind(A ψ ), and C K ψ makes true precisely the assertions in A ψ . By examining q ψ and A ψ , we see that each of the matches of q ψ in C K ψ maps each of the variables z ui to either true or false. We can therefore associate with each match σ the following truth assignment for the variables u 1 , . . . , u n : τ σ (u i ) = σ(z ui ). By further examining the definition of the individuals ξ p k and the roles Asn 1 , Asn 2 , Asn 3 , it is easy to verify that each τ σ is a satisfying assignment for ψ. Moreover, since we know we have N such assignments, it only remains to show that each match σ yields a distinct assignment τ σ . To see why this is the case, observe that once we know the images of all of the variables z ui , there is a unique way of mapping the variables z ξp . It follows that ψ has at least N satisfying assignments.

(⇐) Assume ψ has at least N satisfying assignments. Therefore, we have τ 1 , . . . τ N distinct assignments for u 1 , . . . u n satisfying ψ. This ensures that, if we define σ τm (z ui ) = τ m (u i ), we can always extend the mapping σ τm (z ui ) into a match for q ψ , yielding N distinct matches. Note that this holds in any model since we only need the 'ABox part' of the model, hence (∅, [N, +∞]) ∈ [q ψ ] K ψ . Theorem 8. In DL-Lite R , exhaustive rooted CCQ answering is coNP-complete w.r.t. data complexity.

Proof. The main idea is the same as in proof of Theorem 4. However, due to the lack of existential variables, we can no longer 'reach' the colors without taking into account the paths leading to them. To address this difficulty, we translate into our context an idea from [START_REF] Kostylev | [END_REF], which takes advantage of role inclusions.

Starting from an instance G = (V, E) of the decision problem 3COL, we consider the ABox A G given by: We consider the two following exhaustive rooted CCQs: q edge = ∃z c ∃z 1 ∃z 2 Vertex(a, z 1 ) ∧ Vertex(a, z 2 ) ∧ Edge(z 1 , z 2 ) ∧ HasCol(z 1 , z c ) ∧ HasCol(z 2 , z c ) q col = ∃z v ∃z Vertex(a, z v ) ∧ Colors(z v , z) and let q be the query obtained by taking the conjunction of these two queries and keeping all of the variables existentially quantified. The query q is displayed in Figure 10. Observe that while it is similar to the query from the proof of Theorem 4 (see Figure 3), the two existential variables in that query (y c , y) have been replaced with counting variables (z c , z v ), and one of the HasCol atom has been changed to a Colors atom. It is not hard to see that (a ∅ , [3|V| + 1, +∞]) ∈ [q] K G . Indeed, there are at least 3|V| matches of q in any model I of K, obtained as follows:

A G ={Vertex
z 1 , z 2 → a v z c → r z v → u (u ∈ V) z → r | g | b and one additional match given by: z 1 , z 2 , z v → a v z c , z → r To complete the proof, we establish the following claim.

Claim. (∅, [3|V| + 2, +∞]) ∈ [q] K G ⇐⇒ G / ∈ 3COL. The exhaustive rooted CCQ q, which is the conjunction of q edge (left part) and q col (right part).

(⇒) This direction is proven in the same manner as the claim in the proof of Theorem 4. We assume (a ∅ , [3|V| + 2, +∞]) ∈ [q] K G and take a possible coloring τ : V → {r, g, b}. We then use τ to build a model I τ of K G and use the existence of an additional match σ to show that τ contains a monochromatic edge (hence G / ∈ 3COL).

(⇐) Assume G / ∈ 3COL, and take some model I of K G . By Lemma 1, there is a homomorphism f : C K G → I. Define τ : V → ∆ I as follows: τ (u) = f (uHasCol). Note that τ is well defined, as the inclusion ∃Vertex -∃HasCol ensures that there is an element uHasCol in C K G . There are two cases to consider:

• If there exists u ∈ V such that τ (u) / ∈ {r, g, b}, then the axiom HasCol Colors ensures (u I , τ (u)) ∈ Colors I , which provides an additional match of q color in I with z → τ (u) and z v → u I .

• Else, since G / ∈ 3COL, there exists an edge (u 1 , u 2 ) ∈ E such that τ (u 1 ) = τ (u 2 ). It yields a new match given by:

z → r z v → a v z 1 → u 1 z 2 → u 2 z c → τ (u 1 ) (= τ (u 2 ))
In both cases, there is an additional c-match for q. We thus obtain (a ∅ , [3|V| + 2, +∞]) ∈ [q] K G .

Theorem 9. In DL-Lite R , exhaustive rooted CCQ answering is in coNEXP w.r.t. combined complexity.

Proof. We may assume w.l.o.g. that the initial homomorphism f : C K → I is chosen to respect the following property ( ): if w 1 R, w 2 R ∈ ∆ C K and f (w 1 ) = f (w 2 ), then f (w 1 R) = f (w 2 R). Such a homomorphism can easily be built starting from an arbitrary homomorphism g, by choosing a 'main branch' whenever a choice is possible and copying from it. Formally, given a breadth-first ordering of elements in ∆ C K , we start by setting f := g. Then, we explore the elements according to and at each step, say at element w 1 , we explore all elements w 2 such that w 1 w 2 . If ever f (w 1 ) = f (w 2 ), we redefine f (w 2 w) := f (w 1 w) for every word w such that w 1 w, w 2 w ∈ ∆ C K . Since is breadth-first, the image f (w 1 ) will no longer be redefined after step w 1 , which ensures the resulting homomorphism f is well-defined.

Recall that we introduced in the body of the paper a more refined notion of interleaving, which replaces the mapping f by the following mapping f * :

f * : ∆ C K → ∆ * ∪ ∆ C K a → f (a) wR → f (wR) if f * (w), f (wR) ∈ ∆ * f * (w)R otherwise
We let I * be the interpretation obtained by applying f * to C K . It is helpful to observe that I * essentially coincides with the canonical model C K * of the KB K * whose TBox is T and whose ABox A * consists of the facts from ∆ * ∩ f * (C K ) (treating such elements as ABox individuals). More explicitly, A * contains the concept assertion A(t) for each atomic concept A ∈ N C and domain element t ∈ ∆ * ∩ f * (C K ) such that t ∈ f * (A C K ), and the role assertion R(t 1 , t 2 ) for each atomic role R ∈ N R and domain elements t 1 , t 2 ∈ ∆ * ∩ f * (C K ) such that (t 1 , t 2 ) ∈ f * (R C K ).

This alternative way of viewing I * , together with our assumption ( ), makes clear that the following mapping is a homomorphism from I * to I:

  (UNA) by requiring that a I = b I for every a, b ∈ N I with a = b. The function • I naturally extends to complex concepts and roles: (∃R) I = {d | ∃d :(d, d ) ∈ R I }, (P -) I = {(d 1 , d 2 ) | (d 2 , d 1 ) ∈ P I }, (¬B) I = ∆ I \ B I , (¬R) I = ∆ I × ∆ I \ R I . A (concept or role) inclusion F G is satisfied in I if F I ⊆ G I ; assertion A(b) is satisfied in I if b I ∈ A I ; P (a, b) is satisfied in I if (a I , b I ) ∈ P I .

  a, b) | P (a, b) ∈ A} ∪ {(e 1 , e 2 ) | e 2 = e 1 R and T |= R P } ∪ {(e 2 , e 1 ) | e 2 = e 1 R and T |= R P -}

  Note that the final element d k might belong to D. Definition 6 (n-neighbourhood with respect to a subdomain). Consider a model M and an element d ∈ ∆ M . Its nneighbourhood N n (d, M, D) w.r.t. a subdomain D is the set of elements d ∈ ∆ M such that there exists a k-chain (d 0 , . . . d k ) in M with respect to D such that k ≤ n, d 0 = d, and d k = d .

  we have d ∼ n e iff w d n,d = w e n,e , χ n,d = χ n,e , and |d| = |e| mod 2|q| + 3, • for d ∈ ∆ * , d ∼ n e iff d = e. Remark 1. Notice that if d ∼ n e, then d ∼ m e for any m ≤ n. This property will be used several times without mention.

  then C is empty and thus C d = d. • Otherwise, C is a (k + 1)-chain (d, d 1 , . . . d k , e), then consider the primary role S of the edge (d k , e). If w ( C1...C k ) d |q|+1-k,( C1... C k ) d

  ),e . Lemma 6. For any k ≤ |q|, any d, e ∈ ∆ I \ ∆ * , and any two k-chains C and C from d to e in J , we have C d = C d. Proof. Since C and C have the same endpoints d and e, we have C w d |q|+1,d = C w d |q|+1,d . If |w d |q|+1,d | = |q| + 1, then C d = C (r |q+1|,d w d |q|+1,d ) = r |q+1|,d ( C w d |q|+1,d ) = r |q+1|,d ( C w d |q|+1,d ) = C d. Otherwise, |w d |q|+1,d | < |q| + 1, we have r |q|+1,d ∈ ∆ * . Therefore the action of C (resp C ) cannot empty the initial word w d |q|+1,d , since it would lead, by Lemma 6, to an element along C (resp C ) being in ∆ * . Thus, we still have C d = C d.

  e ∈ ∆ * C d with C any k-chain from d to e, with k ≤ |q| otherwise Furthermore, ρ d satisfies that for any e ∈ ∆ J , we have ρ d (e) ∼ 1 e. In particular, it satisfies conditions 1 and 2 from Theorem 12. Proof. It only remains to prove that the action of a k-chain always provide an actual element in ∆ I . We proceed by induction on k, building intermediate mappings ρ d,k : N k (d, J ) → N k (d, I ). We also prove that, at each step, we have for any e ∈ N k (d, J ), ρ d,k (e) ∼ |q|+1-k e. Base case: k = 0. We have N 0 (d, J ) = {d}. If d ∈ ∆ * , we set ρ d,0 := d which is well-defined. Otherwise, consider the 0-chain (d), we have ρ d,0 (d) := ε d = d, which is well defined. In both cases, we obviously have ρ d,0 (d) ∼ |q|+1 d. Induction step: k ⇒ k + 1. Assume the mapping ρ d,k : N k (d, J ) → N k (d, I ) is well defined for some k < |q|. We explain how to extend it to a mapping ρ d,k+1 : N k+1 (d, J ) → N k+1 (d, I ). Consider an element e ∈ N k+1 (d, J ) \ N k (d, J ). If e ∈ ∆ * , then we set ρ d,k+1 (e) := e, which is well-defined and satisfies ρ k+1 (e) ∼ |q|+1-(k+1) e.

  J ) and the assumption for k, which implies that ρ k (d k ) ends with S -. The action of S on ρ d,k (d k ) hence provides the well-defined word obtained from ρ k (d k ) by removing its final symbol S -. Therefore, ρ k+1 (e) is well defined. Since the equivalence class of ρ d,k (d k ) for ∼ |q|+1-k fully determines the equivalence class of its immediate neighbour ρ d,k+1 (e) for ∼ |q|+1-(k+1) , and since we know that ρ d,k (d k ) ∼ |q|+1-k d k by the induction hypothesis, we obtain ρ d,k+1 (e) ∼ |q|+1-(k+1) e. • Otherwise, if = S, the action of S on ρ d,k (d k ) provides ρ d,k (d k )S, which is well defined since and ρ d,k (d k ) must end by the same letter, as the induction hypothesis ensures ∼ 1 ρ d,k (d k ) (recall k < |q|). Again, since the equivalence class of ρ d,k (d k ) for ∼ |q|+1-k fully determines the equivalence class of its immediate neighbour ρ d,k+1 (e) for ∼ |q|+1-(k+1) , and since we know that ρ d,k (d k ) ∼ |q|+1-k d k by the induction hypothesis, we obtain ρ d,k+1 (e) ∼ |q|+1-(k+1) e. The mapping ρ d is obtained as ρ d,|q| . Notice the two conditions are satisfied.

  of Theorem 12. Let e, e ∈ ∆ I , and let R ∈ N R be such that (e, e ) ∈ R J . If e ∈ ∆ * , then Lemma 8 applies by setting (e 1 , e 2 , d, R) := (e , ρ d (e ), e, R) and therefore (ρ d (e), ρ d (e ) ∈ R I . Otherwise, if e ∈ ∆ * , then Lemma 8 also applies, by setting (e 1 , e 2 , d, R) := (e, ρ d (e), e , R) and again (ρ d (e), ρ d (e ) ∈ R I .

  • A(a)∈A? for each atomic concept A such that T |= A C. • P(a,b)∈A? for all b ∈ Ind(A) such that T |= ∃P C. • P(b,a)∈A? for all b ∈ Ind(A) such that T |= ∃P -C.

Figure 1 :

 1 Figure 1: The TC 0 circuit built for 2-individual ABoxes w.r.t. T and q.

Figure 2 :

 2 Figure 2: A part of CK G with (u1, u2) ∈ E.

Figure 5 :

 5 Figure 5: A part of the canonical model CK.

  (a, u) | u ∈ V} ∪ {Edge(u 1 , u 2 ) | (u 1 , u 2 ) ∈ E} ∪ {Vertex(a, a v ), Edge(a v , a v ), HasCol(a v , r)} ∪ {Colors(u, r) | u ∈ V} ∪ {Colors(u, g) | u ∈ V} ∪ {Colors(u, b) | u ∈ V}and the TBox T := {∃Vertex - ∃HasCol, HasCol Colors}, and we denote by K G = (T , A G ) the resulting KB. A part of the canonical model of K G is depicted in Figure9. As in the proof of Theorem 4, we use ∃Vertex - ∃HasCol to assign colors to vertices, and the more general role Colors will be used to detect colors.

Figure 9 :

 9 Figure 9: A part of CK G with (u1, u2) ∈ E.

  Figure10: The exhaustive rooted CCQ q, which is the conjunction of q edge (left part) and q col (right part).

  ρ * : ∆ I * → ∆ I f * (d) → f (d).Indeed, ( ) ensures the choice of d doesn't affect the image f (d), thus ρ * is well-defined. Formally, we proceed by induction on elements ofI * . If f * (d) ∈ ∆ * , then by the definition of f * , we must have either d ∈ Ind with f * (d) = f (d), or d = wR with f * (w) ∈ ∆ * , f (d) ∈ ∆ * and f * (d) = f (d). In both cases, ρ * (f * (d)) = f (d) = f * (d), which is independent from the choice of d. Otherwise, suppose ρ * is well-defined for ω, and consider some f * (d) = ωR / ∈ ∆ * and d such that f * (d ) = f * (d) = ωR. By the definition of f * , we must have d = wR with f * (w) = ω, and same for d , that is, d = w R with f * (w ) = ω. By our inductive assumption, we have ρ * (ω) = f (w) = f (w ). Property ( ) now ensures f (wR) = f (w R), that is ρ * (f * (d)) = ρ * (f * (d )).

Table 1 :

 1 Data and combined complexity of CCQ answering

Table 2 :

 2 Complexity results for exhaustive rooted CCQs model. It can be obtained by adapting a similar result about canonical bag interpretations[START_REF] Nikolaou | [END_REF].

The notion of homomorphism of a CCQ is defined in the same way as for CQs, simply treating variables from Vc like those in V.

We have slightly modified the definition of interleaving to correct a small bug in the definition from[START_REF] Kostylev | [END_REF].

Bag semantics, which underly practical database systems, interprets relations using multisets rather than sets[Albert, 1991].

 6 We recall that TC 0 is a circuit complexity class defined similarly to AC 0 but additionally allowing threshhold gates. It is known that AC 0 TC 0 ⊆ NC 1 ⊆ LogSpace ⊆ PTime.

As usual, |T | (resp. |A|, |q|) denotes the size of T (resp. A, q).

We have slightly modified the definition of interleaving to correct a small bug in the definition from[START_REF] Kostylev | [END_REF].

We recall that TC 0 is a circuit complexity class defined similarly to AC 0 but additionally allowing threshhold gates. It is known that AC 0 TC 0 ⊆ NC 1 ⊆ LogSpace ⊆ PTime.

Acknowledgements

This work was partially supported by ANR project CQFD (ANR-18-CE23-0003).

The mapping ρ * being a homomorphism then follows from the definition of concept and role interpretations in I * . In particular, this means that I * is a model of K. Compared to the homomorphism ρ used to connect the interleaving I with the countermodel I, we have lost the property that ρ -1 (∆ * ) = ∆ * . Therefore, proving that I * is a countermodel requires a different argument that exploits the exhaustive rooted assumption on the query.

Consider a match σ : x ∪ z → ∆ I * of q(a) in I * . Let us first suppose that there is a counting variable z ∈ z such that σ(z) / ∈ ∆ * , in which case we must have σ(z) = tw for some t ∈ ∆ * ∩ f * (C K ) and some non-empty word w. Since q is exhaustive rooted, all intermediate elements tw with w a prefix of w, must be reached by some other counting variables. In particular, one of these counting variables, say z 0 , must map onto tw 0 , with w 0 the first symbol of w. From the definition of f * , we also have a word w t such that f * (w t ) = f (w t ) = t. However, via the homomorphism ρ * , we can transform σ into a match ρ * • σ : x ∪ z → ∆ I in the original countermodel I. In particular, we will have ρ * (σ(z 0 )) = ρ * (tw 0 ) = ρ * (f * (w t )w 0 ) = ρ * (f * (w t w 0 )) = f (w t w 0 ). Thus, f (w t w 0 ) belongs to the image of the match ρ * • σ in I. From the definition of ∆ * , we can thus infer that f (w t w 0 ) ∈ ∆ * . But since f * (w t ) = t ∈ ∆ * and f (w t w 0 ) ∈ ∆ * , we have f * (w t w 0 ) = f (w t w 0 ), and therefore the element tw 0 is not introduced by f * (it would contradict the property ( )), which contradicts z 0 mapping onto this element. Therefore, this situation, that is, the existence of a match in I * with a counting variable mapping outside ∆ * , does not occur. Hence, we have σ(x ∪ z) ⊆ ∆ * . Then since ρ * |∆ * = id, we have ρ * • σ = σ, which shows that the mapping σ → ρ * • σ is injective. This means that I contains at least as many c-matches as I * , and since I is a countermodel, I * must also be a countermodel.

As observed earlier, the obtained countermodel I * has a particular structure: it can be seen as the canonical model of an ABox A * whose size is polynomially bounded by the size of ∆ * , itself being single exponential in the size of the input. The modified interleaving thus allows us to improve the algorithm used in the general case. Indeed, it is now sufficient for a Turing machine to (i) guess an ABox of single-exponential size in |K| and |q|, and (ii) check that the canonical model of the guessed ABox and original TBox contains fewer c-matches for q(a) than the integer provided as input. Importantly, due to our assumption that q is exhaustive rooted, matches cannot reach elements in the canonical model that have depth greater than |q|. There are thus only single-exponentially many domain elements that may appear in the image of a match, and so it is possible to enumerate and count all matches in single-exponential time w.r.t. |K| and |q|.

D Proofs for Section 7 (Best Certain Answers) Theorem 10. The following problem is DP-hard in data complexity: given a DL-Lite core KB K = (T , A), rooted CCQ q, tuple a, and number m, decide whether m = min I|=K q I a .

• Proof. We provide more details on the case analysis mentioned in the body of the paper. In what follows, I will denote an arbitrary model of K = (T col , A G1 ∪ A G2 ). We first remark that every model contains the c-matches given by:

In what follows, we will use I G τ to denote a minimal model of K G complying with a given coloring τ of a graph G, constructed as in the proof of Theorem 4. We observe that if τ 1 and τ 2 are respectively colorings for the graphs G 1 and G 2 , then the interpretation I G1 τ1 ∪ I G2 τ2 which is the disjoint union of I G1 τ1 and I G2 τ2 is a model of the considered KB K. We use such models to establish the minimum number of c-matches in the four different cases:

• G 1 , G 2 ∈ 3COL: We have already seen that every model of K contains at least 27 c-matches. Let τ 1 (resp. τ 2 ) be a 3-coloring for G 1 (resp. G 2 ). Then the model

As G 2 is not 3-colorable, the part of I describing G 2 must either introduce a fourth color, providing a new value for z 2 (hence at least 3 × 3 × 1 × 4 × 1 = 36 c-matches), or contain a monochromatic edge, providing another possible value for (z 2 1 , z 2 2 ) (hence at least 3 2 × 1 × 3 × 2 = 54 c-matches). Therefore, every model contains at least 36 c-matches for q. To show we cannot ensure more than 36 c-matches, let τ 1 (resp. τ 2 ) be a 3-coloring (resp. 4-coloring) for G 1 (resp G 2 ). Then I G1 τ1 ∪ I G2 τ2 has exactly 36 c-matches.

•

The part of I describing G 1 must introduce either a fourth color, providing a new value for z 0 and z 1 (hence at least 4 × 4 × 1 × 3 × 1 = 48 c-matches), or contain a monochromatic edge, providing another possible value for

It follows that every model contains at least 48 c-matches. To show this is the best value that can be attained, let τ 1 (resp. τ 2 ) be a 4-coloring

∈ 3COL: For each of the two graphs, I must introduce either a fourth color or a monochromatic edge. There are four cases to consider:

We therefore see that every model contains at least 64 c-matches of q. To realize the minimal number, we let τ 1 (resp. τ 2 ) be a 4-coloring (resp. 4-coloring) for G 1 (resp. G 2 ) and observe that I G1 τ1 ∪ I G2 τ2 has exactly 64 c-matches. This completes the case analysis, the rest of the argument is contained in the proof sketch.

DP-hardness for Count queries from [START_REF] Kostylev | [END_REF] Proof. We recall that the Count queries from [START_REF] Kostylev | [END_REF] are obtaining by requiring all of the non-answer variables to be counting variables. The queries from the preceding reduction do not satisfy this restriction, as they use existential variables, but we can modify the reduction in order to make it work for such queries.

In the modified reduction, each vertex is described in the ABox with a specific concept, either Vertex 1 or Vertex 2 depending on which graph it appears in. The TBox contains the following axioms:

The subqueries q edge i and q col i are then modified as follows for i ∈ {1, 2}:

and q col 0 is redefined as: ∃z 0 Color 1 (z 0 ). It is easily verified that after these modifications, the query q now corresponds to a Count query as defined in [START_REF] Kostylev | [END_REF]. The query q is displayed in Figure 13, and the slightly ajusted canonical model C K (G 1 ,G 2 ) is displayed in Figure 14.

We can then redo the argument in the same manner as before, and the case analysis will give rise to precisely the same numbers of c-matches.

Figure 13: The Count CQ q, which is the conjunction of q edge 1 , q col 1 , q col 0 (left part) and q edge 2 , q col 2 (right part).

•

DP-hardness for Cntd queries from [START_REF] Kostylev | [END_REF] Proof. We recall that the Cntd queries from [START_REF] Kostylev | [END_REF]] correspond to CCQs with exactly one counting variable. As in the previous reductions, we aim to force additional matches whenever an input graph is not 3-colorable, and the challenge is to track of the amount of colors used to color the two graphs.

Having only a single counting variable forces us to count colors used for G 1 in exactly the same as we count those used for G 2 . In particular, the asymmetry we introduced in the query must now be introduced into the ABox. This is done by considering a copy of our first graph. However, this is not enough as two different graphs could use the same additional color, making it impossible to detect with our single counting variable that both graphs are using more than three colors. Therefore, we will provide a set of basic colors for each graph and additionally check whether a graph uses a color that is intended for another graph. Concretely, we achieve this by connecting vertices from different graphs using a new role Diff, and by adding a new subquery that will generate new c-matches whenever two vertices connected by Diff use the same color.

Let us now give a more formal description of the construction. As mentioned earlier, we will introduce a copy G 0 = (V 0 , E 0 ) of the graph G 1 . Without loss of generality, we can assume that

As ABox individuals, we will use:

• an individual name u for each u ∈ V 0 ∪ V 1 ∪ V 2 , to represent our graphs;

• individuals r 0 , g 0 , b 0 (resp. r 1 , g 1 , b 1 and r 2 , g 2 , b 2 ), intended to color G 0 (resp. G 1 and G 2 );

• auxiliary individuals for vertices (a 0 , a 1 , a 2 , c, d, e) and auxiliary individuals for colors (r, g, b).

We then consider the following ABox: We consider the three following subqueries:

1 ∃y e 2 ∃y e c Aux e (y, y e 1 ) ∧ Edge(y e 1 , y e 2 ) ∧ HasCol(y e 1 , y e c ) ∧ HasCol(y e 2 , y e c ) q col (y) = ∃z HasCol(y, z) and let q = ∃y q dif f (y) ∧ q edge ∧ q col be the complete CCQ, which corresponds to a Cntd query class as there is only one counting variable z. The query q is displayed in Figure 15.

Figure 15: The Cntd CQ q, which is the conjunction of q edge (left part), q dif f (right part) and q col (upper part).

Claim:

We prove this claim using the following case analysis:

To obtain the values in the preceding table, consider an arbitrary model I of K, along with a homomorphism f : C K → I. First observe that there are always 9 c-matches, which are obtained from the matches given by:

Hence q I ∅ ≥ 3 + 3 + 3 = 9. Furthermore, let us define τ I : V 0 ∪ V 1 ∪ V 2 → ∆ I as follows: τ I (u) = f (uHasCol). We'll use the notation τ I (V i ) to refer to the set {τ I (u) | u ∈ V i }. Notice that, if τ I (V i ) ∩ τ I (V j ) = ∅ with i = j, that is, we have u ∈ G i , v ∈ G j with i = j and τ I (u) = τ I (v), then we have 3 additional c-matches corresponding to the matches given by:

Therefore, in such a model I, we have q I ∅ ≥ 9 + 3 = 12, and thus sufficiently many c-matches w.r.t. the numbers in the table. We will therefore assume in the following that τ I (V i ) ∩ τ I (V j ) = ∅ for i = j (assumption (i)).

The same applies in the case where τ I (V i ) ∩ {r j , g j , b j } = ∅ for i = j, as one can exhibit the same three additional cmatches by replacing the individual v by a j in the latter definition of matches. Therefore, we can also assume in what follows that τ I (V i ) ∩ {r j , g j , b j } = ∅ for all i = j (assumption (ii)).

Finally, notice that if τ I introduces a monochromatic edge, i.e. an edge (u, v) ∈ E 0 ∪ E 1 ∪ E 2 such that τ I (u) = τ I (v), we again have 3 additional c-matches obtained from the matches given by:

y e c → τ I (u) Therefore, we can also restrict our attention to models without monochromatic edges (assumption (iii)). Any model that satisfies properties (i), (ii) and (iii) will be called non-trivial.

We now proceed to consider the four cases. In each case, the minimal amount of c-matches is obtained by exhibiting a model built from colorings for each graph that use a minimal amount of colors. The only important difference w.r.t preceding reductions is that when more than one graph utilizes a fourth color, we need to use distinct fourth colors for each graph. We now complete the proof by showing that every non-trivial model has at least the number of c-matches as listed in the table.

• G 1 , G 2 ∈ 3COL: We have already seen that every model contains at least 9 c-matches.

• G 1 / ∈ 3COL, G 2 ∈ 3COL: Since G 0 and G 1 are not 3-colorable, any non-trivial model I must satisfy τ I (V 0 ) ≥ 4 and τ I (V 1 ) ≥ 4, due to assumption (iii). In particular, we have a vertex u 0 ∈ V 0 (resp.

This yields the following matches: • G 1 , G 2 / ∈ 3COL: We can proceed similarly to the two previous cases to exhibit u 0 ∈ V 0 , u 1 ∈ V 1 , u 2 ∈ V 2 that are assigned new colors, providing three new matches given by: which give rise to three new c-matches because of assumptions (i) (the colors τ I (u 0 ), τ I (u 1 ), τ I (u 2 ) are all different) and (ii) (they are also different from the colors in the 9 basic c-matches). Hence, we have that every non-trivial model contains at least 12 matches.