Answering Counting Queries over DL-Lite Ontologies

1 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´errez-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 Calvanese et al. (2008). 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 [Kostylev and Reutter, 2015], 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-Litecore and DL-LiteR), 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 Πp2 -hard (resp. coNEXP-hard) in combined complexity for DL-Litecore (resp. DL-LiteR). 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 [Kostylev and Reutter, 2015] and allows arbitrarily many counting variables.
2. We show that existing complexity results for DL-Litecore and DL-LiteR 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.

1. 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 [Nikolaou et al., 2019]. This motivates us to perform a more thorough investigation of rooted counting queries, which yields several improvements upon existing complexity bounds.
2. 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 ver-

sion of this paper, available on arXiv.

2 Preliminaries

We recall the basics of description logics (DLs), focusing on DL-Lite, see [Baader et al., 2017] for more details.

Syntax and Semantics. A description logic vocabulary consists of a set NC of atomic concepts (unary predicates), a set NR of atomic roles (binary predicates), and a set NI of individual names (constants). By role, we mean either an atomic role P ∈ NR or an inverse role P - (where P ∈ NR). We let N±R denote the set NR ∪ {P - | P ∈ NR} of roles and use the

notation R- to mean P - if R = P ∈ NR 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 ∈ NC and b ∈ NI, and role assertions P(a, b), with P ∈ NR and a, b ∈ NI. 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-Litecore, axioms take the form of concept inclusions B1 ⊑ (¬)B2, where each Bi is either A (for A ∈ NC) or ∃R (with R ∈ N±R ). DL-LiteR TBoxes additionally allow role inclusions R1 ⊑ (¬)R2, where R1, R2 ∈ N±R .

Example 1. Our example KB talks about leading (LeadIn) and supporting actors (SuppIn) in movies:

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 ∈ NC to a subset AI ⊆ ∆I , each P ∈ NR to a binary relation P I ⊆ ∆I × ∆I , and each a ∈ NI to an element aI of ∆I . We make the unique names assumption (UNA) by requiring that aI ̸= bI for every a, b ∈ NI with a ̸= b. The function ·I naturally extends to complex concepts and roles: (∃R)I = {d | ∃d′ : (d, d′ ) ∈ RI }, (P -)I =

{(d1, d2) | (d2, d1) ∈ P I }, (¬B)I = ∆I \ BI , (¬R)I = (∆I ×∆I ) \ RI . A (concept or role) inclusion F ⊑ G is satisfied in I if F I ⊆ GI ; assertion A(b) is satisfied in I if bI ∈ AI ; P(a, b) is satisfied in I if (aI , bI ) ∈ P I . 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(t1) or role atoms P(t1, t2), where A ∈ NC, P ∈ NR, and terms ti are drawn from NI ∪ 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) = aI for a ∈ NI, (ii) σ(t) ∈ AI for every atom A(t) of q, and (iii) (σ(t1), σ(t2)) ∈ P I for every atom P (t1, t2) of q. A tuple a ∈ Ind(A)n is a certain answer to q w.r.t. the KB K iff I |= q(aI ) for every model I of K.

Canonical Model. We recall the definition of the canonical model CK of a DL-LiteR KB K = (T ,A). The domain of CK consists of Ind(A) and all words of the form aR1 . . . Rn, with a ∈ Ind(A), Ri ∈ N±R , and n ⩾ 1, such that:

• K |= ∃R1(a) and there is no R1(a, b) ∈ A;
• for 1 ≤ i < n, T |= ∃Ri ⊑ ∃Ri+1 and Ri ̸= Ri+1.

We interpret individuals as themselves (aCK = a) and atomic concepts and roles as follows:

The term 'canonical model' is motivated by the following well-known property of CK (see e.g. [Calvanese et al., 2007]): Lemma 1. Let K be a satisfiable DL-LiteR KB. Then CK |= K and if I |= K, there is a homomorphism of CK 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 CK.

Note that CK may be infinite. The depth of a TBox T is defined as the maximal length of any word that appears in the domain of CK 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].

3 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 Vc, disjoint fromV.

Definition 1. A counting conjunctive query (CCQ) q takes the form q(x) = ∃y∃z ψ(x, y, z), where x ∪ y ⊆ V, z ⊆ Vc, and ψ is a conjunction of concept and role atoms whose terms are drawn from NI ∪ 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 homomorphism 1 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 qI , contains all pairs (a, qIa ), where qIa is the number of distinct c-matches of q(a) in I.

As has been previously noted (see e.g. [Kostylev and Reutter, 2015]), the exact count values of the answers in qI 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 ≤ qIa ≤ 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) ∈ qI .

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, ∅, ˆy) (with ˆy a tuple of variables from Vc 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 Kact = (Tact,Aact). We can use CCQs to count the pairs of actors (leading role, supporting role) having acted together (q1), return movies together with a count of their supporting actors (q2), and count the number of actors having acted with Tom Hanks (q3):

According to our semantics, we have:

• (∅, [2,+∞]) ∈ [q1]Kact , since z2 can be mapped to either berry or hanks, and z1 mapped to the lead actor (which must exist due to Tact). As the lead actors of the two films could be the same, (∅, [3, +∞]) ̸∈ [q1]Kact .
• (cloud, [2, +∞]) ∈ [q2]Kact , mapping z to berry and hanks.
• (∅, 5) ∈ qCKact 3 , since in CKact , we can map z to a named actor or the two elements standing in for the lead actors.
• (∅, [5,+∞]) /∈ [q3]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.

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

4 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-LiteR (which underlies OWL 2 QL) and its sublogic DL-Litecore. We know from [Kostylev and Reutter, 2015] 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.

4.1 General Case

Table 1 displays complexity results for answering general CCQs over DL-Litecore and DL-LiteR 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 [Kostylev and Reutter, 2015]. 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-LiteR (resp. DL-Litecore) 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 fromA 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 CK into I (see Lemma 1) and consider the following mapping f ′ : ∆CK →∆∗ ∪∆CK from [Kostylev and Reutter, 2015]:

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).

We define the interleaving 4 I ′ of I as the image of CK by f ′ , i.e., with domain f ′ (∆CK ) and interpretation function f ′ ◦·CK .

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-LiteR, there can be double-exponentially many equivalence classes, as elements are grouped based upon the properties of their |q|-neighborhoods, while for DL-Litecore, 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 [Kostylev and Reutter, 2015], 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.

4.2 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-LiteR 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 CK 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.

4 We have slightly modified the definition of interleaving to correct a small bug in the definition from [Kostylev and Reutter, 2015].

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

5 Rooted Counting CQs

We next explore whether structural restrictions on CCQs allow us to obtain lower complexity. As the lower bounds from [Kostylev and Reutter, 2015] use disconnected counting variables, a natural idea is to consider the subclass of rooted queries that were introduced in [Bienvenu et al., 2012] 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 {t1, t2} iff t1, t2 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 q2 and q3 are rooted, while q1 is not.

Rootedness has been shown to lower the complexity of reasoning in several settings. Most relevant to us is a recent result by Nikolaou et al. (2019) that rooted CQ answering under bag semantics 5 has tractable data complexity in DL-Litecore, 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-LitecoreTBoxes:

Theorem3. (Implicit in [Nikolaou et al., 2019; Cima et al., 2019]) In DL-Litecore, exhaustive rooted CCQ answering is TC0 -complete 6 w.r.t. data complexity.

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 TC0 due to [Libkin, 2001], see [Cima et al., 2019] for discussion. Moreover, they further show that for a syntactically restricted class of DL-Litecore TBoxes, it is possible to reduce exhaustive rooted CCQ answering to rooted CQ answering under bag semantics. To obtain TC0 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 TC0 circuits. A matching lower bound has not been stated, but can be shown by a simple reduction (using an empty TBox) from the TC0 -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:

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

6 We recall that TC0 is a circuit complexity class defined similarly to AC0 but additionally allowing threshhold gates. It is known that AC0 ⊊ TC0 ⊆ NC1 ⊆ LogSpace ⊆ PTime.

Theorem 4. In DL-Litecore, 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 [Kostylev and Reutter, 2015]. 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 Tcol has a single axiom: ∃Vertex- ⊑ ∃HasCol. The ABox AG 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 av and the following assertions: Vertex(a, av), Edge(av, av), HasCol(av, r), HasCol(av, g), and HasCol(av, b).

The query q is the conjunction of the two subqueries:

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 Kcol = (Tcol,AG). Moreover, it can be verified that (∅, [4,+∞]) is a certain answer to q w.r.t. Kcol iff G is not 3-colorable.

Theorem 5. In DL-LiteR, 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 [Kostylev and Reutter, 2015]), the key difference being the use of existential query variables to access (and count) the colors and bits.

6 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 q2 from Example 2 is an exhaustive rooted CCQ.

6.1 Exhaustive Rooted CCQs in DL-Litecore

We first consider DL-Litecore 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 model. It can be obtained by adapting a similar result about canonical bag interpretations [Nikolaou et al., 2019].

Theorem 6. For every DL-Litecore KB K and exhaustive rooted CCQ q, it holds that [q]K = [q]CK .

Proof sketch. Exploiting the structure of DL-Litecore canonical models, one can show that if σ1, σ2 are distinct matches of an exhaustive rooted CCQ q in CK, then there exists a variable 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 CK into I, then f injectively maps query matches in CK to query matches in I.

We will also use the next lemma, implicit in [Bienvenu et al., 2013], constraining the possible images of matches in CK:

Lemma 2. For every DL-Litecore 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 CK, 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-Litecore, 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 [Bailey et al., 2007]: 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-Litecore 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 TMguesses 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 ≥ C2 + 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 < C2 + 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]CK .

6.2 Exhaustive Rooted CCQs in DL-LiteR

We now turn to DL-LiteR 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 [Kostylev and Reutter, 2015].

Theorem8. In DL-LiteR, 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 ∗ :

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(CK) 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.

Theorem9. In DL-LiteR, exhaustive rooted CCQ answering is in coNEXP w.r.t. combined complexity.

7 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, [minI|=K qIa , maxI|=K qIa ]).

In this section, we show that the problem of identifying the best lower bound (minI|=K qIa ) 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-Litecore KB K = (T , A), rooted CCQ q, tuple a, and number m, decide whether m = minI|=K qIa .

Proof sketch. We give a reduction from the following problem (DP-complete due to [Garey et al., 1976]): given planar graphs G1 and G2, decide if G1 ∈ 3COL and G2 /∈ 3COL.

Let the TBox Tcol and ABoxes AG1 ,AG2 be defined as in the proof of Theorem 4. Rename the individuals to ensure Ind(AG1 ) ∩ Ind(AG2 ) = ∅, then set K = (Tcol, AG1 ∪ AG2 ). Let qcolor 1 and qedge 1 (resp. qcolor 2 and qedge 2 ) be defined as before, but using disjoint variables and the root individual from the AG1 (resp. AG2 ). 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 G1 from G2, we introduce an asymmetry by duplicating the color counter query for G1, i.e., create a copy qcolor 0 of qcolor 1 that uses fresh variables but the same root individual. We then take the query

We claim (a∅, [36, +∞]) ∈ [q]K iff G1 ∈ 3COL and G2 ̸∈ 3COL. This is proven by a case analysis, summarized here:

Each of the four cells displays the least value of m such that (a∅, [m, +∞]) ∈ [q]K, under different assumptions on the 3colorability of G1 and G2. 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 [Kostylev and Reutter, 2015], but without the rootedness restriction.

8 Conclusion &FutureWork

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 Cima et al. (2019) shows that the canonical model property (Theorem 6) holds also for DL-LiteF (which extends DL-Litecore with functional roles), and hence both TC0 data complexity (Theorem 3) and our PP-completeness result (Theorem 7) for exhaustive rooted CCQs transfer to DL-LiteF.

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 [Nikolaou et al., 2019; Cima et al., 2019] and databases with incomplete information [Hernich and Kolaitis, 2017; Console et al., 2017] provide important formal foundations for supporting such queries.

Acknowledgements

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