Counting answers to a query is an essential operation in data management, and is supported by virtually every relational database management system (RDBMS). In this paper, we focus on counting answers over a knowledge base (KB), which may be viewed as a database (DB) enriched with background knowledge about the domain of interest. Our work falls within the scope of Ontology Mediated Query Answering (OMQA) 1 [7,3], where the background knowledge takes the form of a set of logical statements, called TBox, and the data is represented as a set of facts, called ABox. TBoxes are in general expressed in Description Logics (DLs), which are decidable fragments of first-order (FO) logic.

In this setting, counting answers to a query over a KB may require operations that go beyond counting ABox facts, as one also needs to take into account facts that can be inferred through the TBox. For instance, consider a scenario where a central repository keeps track of aggregated information about universities, such as their size, measured in number of students. And assume that these universities also keep detailed records about enrollment. These data sources may be integrated into a DL KB with a TBox of the form:

And an ABox of the form:

Uni(UniBZ), BigUni(UW), BigUni(TUW), . . . , region(UniBZ, SouthTyrol), region(UW, Vienna), region(TUW, Vienna), . . . , enrolledIn(Alice, UniBZ), enrolledIn(Bob, UW), enrolledIn(Carol, TUW), . . .

In practice, the information about enrollment in such KB may be incomplete. First, aggregated data about a whole university may be available, but not the detailed records. The opposite may also hold: detailed records may be provided by a university, but the central repository may not have an aggregated value for it. In such scenarios, even if the data is incomplete, one may still want to compute a lower bound on the number of enrollments of students within each region. In more formal terms, one might be interested in counting the number of answers, as in the following query: q(count(x, y)) ← enrolledIn(x, y) ∧ region(y, Vienna)

Answering such query may require arithmetic operations that combine numbers present in number restrictions in the TBox, and numbers obtained by counting ABox statements. For instance, in this example, assume that TUW and UW are the only two universities in the KB that are registered in the region of Vienna. Assume also that UW does not share enrollment records, whereas TUW shares them, however they may be incomplete (for instance, because some faculties within TUW have not yet communicated their information regarding enrollments). Then, the output value for count(x, y) should be the sum of: 20 000 on the one hand (for UW ), and the largest value between 20 000 and n on the other hand (for TUW ), where n is the number of enrollment records shared by TUW.

Query answering over DL KBs has been extensively studied for boolean and enumeration queries. With respect to the focus of this paper, a relevant result [6] is that for conjunctive queries (CQs) and unions of CQs (UCQs), answering a query over a KB expressed in certain lightweight DLs can be performed by rewriting it, according to the axioms in the TBox, into a relational algebra (RA) query over the ABox. This property, called FO rewritability, allows one to use an RDBMS for the evaluation of the rewritten query, thus leveraging already mature optimization techniques implemented in such systems. Among these DLs, the DL-Lite family [6,1] has been widely studied and adopted in OMQA/OBDA systems, resulting in the OWL 2 QL standard [13].

In comparison, the problem of counting answers to a CQ over a DL-Lite KB has seen little interest in the literature. A seminal result was provided in [11], showing that the problem is significantly harder already for relatively inexpressive DLs, with a shift from AC 0 -membership to coNP-completeness in data complexity, i.e., assuming the sizes of the query and TBox to be fixed. Another key result was provided in [14], but for a slightly different semantics called bag semantics: for certain variants of DL-Lite, CQs that are rooted (i.e., with at least one constant or answer variable) can be rewritten into a variant of bag RA. However, this result is provided for DLs without number restrictions (like ≥ 1000 enrolledIn − in the example above). In addition, because bag semantics differs from the count semantics studied in [11], this rewritability result does not directly apply to our setting. Finally, in [4,5], it was shown that under count semantics (and for some variants of DL-Lite), rooted2 CQs can be rewritten into a variant of RA with aggregation and arithmetic functions. However, the provided rewriting algorithm may yield a query whose size is polynomial in the values of the numbers that occur in the TBox, i.e., exponential in the binary representation of such numbers, which is impractical.

In this paper, we improve upon this last result, showing how for the same DL, and under count semantics, rooted CQs can be rewritten into a different extension of RA, such that the number of algebraic operators in the output query does not depend on the numbers that occur in the TBox, but only on the number of axioms of the TBox. As a consequence, the size of the resulting query is polynomial in the numbers that appear in the number restrictions of the TBox, even when such numbers are represented in binary. This is an important step towards efficient query answering in such setting.

We assume mutually disjoint countably infinite sets N I of individuals (a.k.a. constants), N E of anonymous individuals (induced by existential quantification), N V of variables, N C of concept names (i.e., unary predicates, denoted with A), and N R of role names (i.e., binary predicates, denoted with P ). An atom is an expression of the form A(s) or P (s, t), with A ∈ N C , P ∈ N R , and s, t ∈ N I ∪ N E ∪ N V . In the following, boldface letters like t denote tuples, and we sometimes treat tuples as sets. If t = (t 1 , .., t n ) is a tuple and f a function defined for each t i , we use f (t) to denote the tuple (f (t 1 ), .., f (t n )).

An interpretation I is a FO structure ∆ I , • I , where the domain ∆ I is a non-empty subset of N I ∪ N E , and the interpretation function • I maps each constant c ∈ N I to itself (c I = c, or in other words, we adopt the standard names assumption), each concept name A ∈ N C to a set A I ⊆ ∆ I , and each role name P ∈ N R to a binary relation P I ⊆ ∆ I × ∆ I .

If I = ∆ I , . I is an interpretation, we may use I to denote the set of atoms

S is a set of unary and binary atoms with arguments in N I ∪ N E , we may view it as the interpretation ∆ S , • S , where ∆ S is the union of the arguments of all atoms in S, and • S is defined by A S = {s | A(s) ∈ S}, for A ∈ N C , and

A KB is a pair K = T , A , where A, called ABox, is a finite set of atoms with arguments in N I , and T , called TBox, is a finite set of axioms. In this paper, we focus on (fragments of) DL-Lite HN - core [4,5], a member of the the DL-Lite family [1] where each axiom is a concept inclusion of the form B C or a role inclusion of the form R 1 R 2 , following the grammar of Figure 1. From now on, we use the symbols B, C, P and R in accordance with this grammar, and we call these elements respectively basic concepts, concepts, atomic roles and roles. Concepts of the form ≥ n R are called number restrictions. The fragment of DL-Lite HN - core that disallows role inclusions and number restrictions where n > 1 is called DL-Lite core [1].

The evaluation C I (resp. R I ) of a concept C (resp. role R) over interpretation an I is defined inductively over the structure of C (resp. R) as usual (see [2] for a definition). An interpretation I is a model of T , A iff A ⊆ I holds, and

A KB is satisfiable iff it admits at least one model. For readability, in what follows we focus on satisfiable KBs, that is, we use "a KB" as a shortcut for "a satisfiable KB".

A conjunctive query (CQ) q is an expression of the form q(x) ← p 1 (t 1 ), . . . , p n (t n ), where x ⊆ N V , and each p i (t i ) is an atom with arguments in N V ∪ N I . In addition, we require safeness, i.e., x ⊆ t 1 ∪ • • • ∪ t n . We use dist(q) to denote x, called the distinguished variables of q, and we use body(q) to denote {p 1 (t 1 ), . . . , p n (t n )}. The Gaifman graph G q of q is the undirected graph whose vertices are the variables appearing in body(q), and that contains an edge between x 1 and x 2 iff P (x 1 , x 2 ) ∈ body(q) for some role P . Following [14], we call a CQ q rooted if each connected component in G q contains at least one constant or distinguished variable.

We adopt the semantics proposed in [11] for counting answers to a CQ over a KB, which we call count semantics. If f is a function and D a subset of its domain, then we use f | D to denote f restricted to D. A match for a CQ q over an interpretation I is a homomorphism from body(q) to I. Let M be the set of matches for q over I, let ω be a mapping from dist(q) to N I , and let Γ = {γ ∈ M | γ| dist(q) = ω}. Then the pair ω, |Γ | is an answer to q over I iff |Γ | ≥ 1. And we use ans(q, I) to denote the set of answers to q over I. Finally, a pair ω, k is a certain answer to q over a KB K (under count semantics) iff k is the largest element of N ∪ {+∞} such that, for each model I of K, ω, k I ∈ ans(q, I) for some k I ≥ k. We use certAns(q, K) to denote the set of certain answers to q over K.

A property that has been extensively studied in the OBDA/OMQA literature is FO rewritability [6,1]. Query answering for a class Q of queries is FO rewritable for a DL L iff, for every L TBox T and Q-query q, there is a FO query q such that, for every ABox A, the certain answers to q over T , A and the answers to q over A (viewed as an interpretation) coincide. In particular, under standard certain answer semantics for DLs (which differs from the definition of certAns(q, K) under count semantics given above), query answering for UCQs is FO rewritable for several members of the DL-Lite family. Since RA captures (domain-independent) FO logic, the evaluation of the query obtained via rewriting can be delegated to a RDBMS. Then in [14], this notion of rewritability has been adapted to a different target query language, called BCALC, which captures relational bag algebra [10], and can be translated into SQL queries with aggregation.

Query answering under count semantics over a relational DB can be viewed as a specific case of query answering under bag semantics, investigated notably in [10,12]. Instead, in our setting, and in line with the OMQA/OBDA literature, we assume that the input ABox is a set rather than a bag. The counting problem over sets has also been studied recently in the relational DB setting [15,9], but from the perspective of combined complexity, where the query is considered part of the input (i.e., its size is not assumed to be fixed).

As for (DL-Lite) KBs, in [8] an alternative (epistemic) count semantics is defined, which counts over all grounded tuples (i.e., over N I ) entailed by the KB. Such a semantics does not account for existentially implied individuals, and thus cannot capture the statistics motivating our work.

Closer to our concern is the work presented in [11], which introduces the count semantics for CQs over a DL KB adopted in this paper. In particular the Count problem, which is the decision variant of query answering under count semantics, was shown in [11] to be coNP-hard in data complexity for the relatively inexpressive DL DL-Lite core , even when negated concepts are forbidden. This implies that for this DL and arbitrary CQs, query answering under count semantics is not rewritable into a target query language for which query answering is easier than coNP in data complexity.

Then, rewritability of CQs over a DL-Lite KB was investigated in [14] for the related problem of query answering under bag semantics. In particular, a rewriting algorithm was provided for rooted CQs into the language BCALC (which can be evaluated in TC 0 ), and for a DL that extends DL-Lite core with a restricted form of role subsumption. This result does not immediately transfer to our setting though, for two reasons. First, this DL cannot express number restrictions on the right-hand side (RHS) of TBox axioms, and therefore cannot encode statistics like the ones from our motivating example. Second, as shown in [14], for DL-Lite core already, bag and count semantics differ in the presence of existential quantification on the left-hand side (LHS) of TBox axioms, which are typically used to express the domain and range of an atomic role.

To understand this difference, we recall the basics of query answering under bag semantics (and refer to [14] for a complete definition.) A bag interpretation I maps each atomic concept A (resp. atomic role P ) to a bag A I (resp. P I ). Such bag can be seen as a function that maps each element of ∆ I (resp. ∆ I × ∆ I ) to the number of times it occurs in the bag. This function . I is then extended to complex concepts and roles inductively (see [14]). And I satisfies an axiom

Now let q(x) ← p 1 (t 1 ), . . . , p n (t n ) be a CQ, let I be a bag interpretation, let V be the set of variables that appear in q, let ω be a mapping from x to N I , let Γ = {γ : V → ∆ I | γ| dist(q) = ω}, and let k = γ∈Γ 1≤i≤n (p i ) I (γ(t i )). Then ω, k is a bag answer to q over I iff k ≥ 1. We use bagAns(q, I) to denote the set of bag answers to q over I. And if K is a KB, we use bagCertAns(q, K) to denote the certain answers to q over K under bag semantics, defined analogously to certain answers under count semantics. 3 The difference between bag and count semantics is illustrated in [14] with the following example:

Example 1. Consider the KB K = T , A , where

and the query q() ← A 2 (y). If we evaluate this query under count semantics, then certAns(q, K) = { {}, 1 } (i.e., the only certain answer to q is the mapping with empty domain {}, with multiplicity 1), because the following structure is a model of K: However, such structure does not accurately represent a bag interpretation. Let us now build a (minimal) bag interpretation I for K. To satisfy A, we set A I 1 (a) = 1 and A I 1 (b) = 1. Then to satisfy A 1 ∃P , we introduce a single element u (as above) and obtain P I (a, u) = 1 and P I (b, u) = 1. Therefore (P − ) I (u, a) = 1 and (P − ) I (u, b) = 1, which, according to the semantics proposed in [14], imply that (∃P − ) I (u) = 2. Then in order for this bag interpretation to satisfy ∃P − A 2 , it must be the case that (A 2 ) I (u) = 2. So the only certain answer to q over K under bag semantics is the empty mapping with multiplicity 2, i.e. bagCertAns(q, K) = { {}, 2 }.

It was also shown in [14] that query answering under bag and count semantics coincide for the DL that extends DL-Lite core with role inclusion, but disallows concepts of the form ≥ 1 R on the LHS of axioms. which we denote here with 3 The notation used in [14] for certain answers under both bag and count semantics is slightly different from ours. Let dist(q) = {x1, .., xn}. Then the certain answers to q under bag semantics are represented in [14] as a partial function µ : (N C ) n → N + . Instead, we use bagCertAns(q, K) = { {x1 → c1, .., xn → cn}, k | µ(c1, .., cn) = k}.

As for count semantics, let ω, k ∈ certAns(q, K). Then the definition provided in Section 2 implies that there is no k = k such that ω, k ∈ certAns(q, K). Instead, in [11,14], ω, k is considered a certain answer under count semantics for each

DL-Lite H ∃ core . However, our focus is once again on logics that allow for number restrictions on the RHS of axioms (and thus can encode statistics). So a natural question is whether this result still holds for DL-Lite H ∃ core extended with such axioms. Let DL-Lite HN -∃ core denote this DL (equivalently, DL-Lite HN -∃ core is the fragment of DL-Lite HN - core that disallows concepts of the form ≥ 1 R on the LHS of axioms). To answer this question, the bag semantics proposed in [14] needs to be extended to concepts of the form ≥ n R. One way to do this is to define

/n, for any bag interpretation I and d 1 ∈ ∆ I , where "/" denotes integer division. With this definition, the proof provided in [14,Proposition 85] can be immediately extended to DL-Lite HN -∃ core :

Proposition 2. For any DL-Lite HN -∃ core KB K and CQ q certAns(q, K) = bagCertAns(q, K)

Proof (sketch). The proof of Proposition 85 in [14] uses the fact that for any DL-Lite H ∃ core KB K and model I of K under count semantics, there is a bag interpretation I b that is a model of K under bag semantics, and verifies ans(q, I) = bagAns(q, I b ) for any CQ q. This bag interpretation is defined for

KB and I a model of K, then I b as defined above is still a model of K under bag semantics.

The proof of Proposition 85 in [14] also uses the fact that for any DL-Lite H ∃ core bag KB K and model I of K under bag semantics, there is an interpretation I s that is a model of K under count semantics, and such that for any CQ q, mapping ω over dist(q) and k ∈ N + ∪ {+∞}, if ω, k ∈ bagAns(q, I), then ω, k ∈ ans(q, I s ) for some k ≤ k. This interpretation is defined for

The rest follows from the original proof.

Finally, in [4,5], for DL-Lite N - core and under count semantics, a query rewriting algorithm was provided for rooted CQs into a variant of RA extended with aggregation and arithmetic functions. As for the rewriting of [14], the output query does not depend on the ABox. However, such algorithm is mostly of theoretical interest, and not well suited for implementation (see Section 4). Two negative results were also provided in [4,5], which further circumscribe the scope of rewritability. Specifically, for DL-Lite H core , Count was shown to be P-hard both for rooted CQs and for CQs whose body contains a single atom. This implies that for this DL and these classes of queries, query answering under count semantics is not rewritable into a target query language for which query answering is easier than P.

Query answering under count semantics was shown in [4,5] to be rewritable for rooted CQs and DL-Lite N - core , into a target query language that extends RA with aggregation and some algebraic functions, thanks to a query rewriting algorithm inspired by PerfectRef [6]. However, the size of the rewritten query may be exponential in the size of the input TBox. More specifically, it may be exponential both in the number of axioms (precisely, in the depth of the deepest concept hierarchy that can be inferred from the TBox), and in the encoding of numbers that appear in number restrictions (if encoded in binary, thus polynomial in the value of such numbers). In many applications, it is reasonable to assume that the number of axioms in the TBox remains limited, so the first source of exponential blow-up may not be a major practical limitation. On the other hand, as illustrated in Section 1, values that appear in number restrictions (such as the one in ≥ 20000 enrolledIn − ) may depend on the size of the domain under consideration, and thus, in some applications, they are likely to be of the same order of magnitude as the size of the ABox itself. This might be unmanageable in practice, in scenarios where we have to deal with large amounts of data.

In the following, we describe how the rewriting algorithm of [4,5] can be adapted (for the same DL, source, and target query languages), so that the size of the output query remains linear in the size of the (binary) encoding of numbers in number restrictions. Moreover, this new rewriting guarantees that the number of algebraic operators in the output query only depends on the number of axioms of the TBox. The algorithm of [4,5] exploits the so-called chase model I K can of K. This model is such that, for DL-Lite N - core and rooted CQs, certAns(q, K) and ans(q, I K can ) coincide. Specifically, we illustrate how the rewriting algorithm from [4,5] can be modified by running it on the same example as the one used in [4,5]. Whenever relevant, we will explicitly point out the differences between the two algorithms. The rewriting from [4,5] generates a set of queries that can be directly translated into a SQL query. The target language for this rewriting makes use of nested aggregation in the form of special "atoms" of the form ∃ =k .P (x, y), with k ∈ N, which intuitively correspond to a SQL COUNT DISTINCT operation, together with a boolean condition stating that the result of the aggregation operation over y must be equal to k. If the TBox contains an axiom the form C ≥ n R, then for each k ∈ [1..n], the rewriting of [4,5] generates one sub-query. Hence, the number of generated sub-queries is linear in n, and exponential in the binary encoding of n, which makes it unpractical.

In our variant, we drop the boolean condition and use instead the notation z = count(y).P (x, y), where z is now a variable storing the result of the same aggregation operation. Like in [4,5], we use negation, multiplication, and subtraction. In addition, our target language also requires the SQL function greatest(x,y) (that returns the largest value between x and y), and the aggregation operator SUM. We show through our running example that, despite our modifications, the target language for the rewriting can still be translated into SQL. Consider the following KB K = T , A and CQ q:

The chase model I K can of K is represented in Figure 2. The rewriting algorithm operates on a set Q of queries. This set is initialized with a syntactic variant of the input query:

Intuitively, such query corresponds to the following SQL query4 SELECT x , COUNT ( DISTINCT y1 , y2 ) as cnt FROM A , P1 , P2 WHERE A . x = P1 . x A AND P1 . y1 = P2 . y1 GROUP BY x Then each rewriting step selects a query Q in Q, and extends Q with a set of new queries, obtained by applying some rewriting rule to Q, until saturation is reached. In the previous query, since variable y 2 is unbound, we can apply a rewriting step over atom P 2 (y 1 , y 2 ) with respect to axiom ∃P − 1 ≥ 3 P 2 , producing the query: Q(x, cnt = sum(num)), Q(x, y 1 , num = greatest(0, 3 − z)), {q(x, y 1 ) ← A(x), P 1 (x, y 1 ), P 1 (_, y 1 )} ∧ z = cnt(y 2 ). P 2 (y 1 , y 2 )

This query corresponds to the following SQL query:

SELECT x , SUM ( num ) as cnt FROM ( SELECT x , y1 , greatest ( , 3 -z ) as num FROM ( SELECT x , y1 FROM A , P1 , ( SELECT x as _ , y1 FROM P1 ) as P1a ) WHERE A . x = P1 . x AND P1 . y1 = P1a . y1 ) AS J1 , ( SELECT y1 , COUNT ( DISTINCT y2 ) as z FROM P2 GROUP BY y1 ) AS J2 WHERE J1 . y1 = J2 . y1 ) GROUP BY x the one terminating in node b that has only two P 2 -successors in A. This path is captured by our query, which returns as answer {x → a, cnt → 1}: indeed, there is a single way of extending this path into the anonymous part. The last query has to be interpreted in a similar way. The query retrieves the individual a, since this node has only one P 1 -successor in A but should have at least two P 1 -successors according to T . The answer to such query is {x → a, cnt → 3}. Indeed, there are three ways of extending the match {x → a} into the anonymous part. Now, a last aggregation (with SUM) over all queries in Q yields the desired answer {x → a, cnt → 6}, which indeed corresponds to the answer {x → a}, 6 to our input query over I K can .

In this paper, we have improved the query rewriting technique proposed in [4,5] for rooted CQs under count semantics over a DL-Lite N - core KB, into a target query language that extends RA with aggregation and arithmetic functions. We have illustrated how the exponential blow-up of the output query in the numbers that occur in the TBox, characteristic of the rewriting of [4,5], can be avoided by extending the target rewriting language, specifically with the aggregate operator sum and with the binary function greatest. We also show that this enriched language can still be translated into SQL. Considering that numeric values that appear in the TBox may in practice be of the same order of magnitude as the size of the ABox, this new rewriting algorithm is a significant step towards a practical implementation of query answering under this semantics.