Counting Query Answers over a DL-Lite Knowledge Base

1 Introduction

Counting answers to a query is an essential operation in data management, and is supported by virtually every database management system. 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. In such a setting, counting may take into account two types of information: grounded assertions (typically DB records), and existentially quantified statements (typically statistics).

As a toy example, the following is an imaginary KB storing a parent/child relation, where explicit instances (e.g., Alice is the child of Kendall) coexist with existentially quantified ones (e.g., Parker has 3 children):

The presence of both types of information is common when integrating multiple data sources. One source may provide detailed records (e.g., one record per purchase, medical visit, etc.), whereas another source may only provide statistics (number of purchases, of visits, etc.), due to anonymization, access restriction, or simply because the data is recorded in this way.

In such scenarios, counting answers to a query over a KB may require operations that go beyond counting records. E.g., in our example, counting the minimal number of children that must exist according to the KB (where children can be explicit or existentially quantified elements in the range of hasChild) requires some non-trivial reasoning. The answer is 4: Bob or Carol may be the second child of Kendall, but Alice cannot be the third child of Parker (because Alice has two parents already), so a fourth child must exist.

One of the most extensively studied frameworks for query answering over a KB is Ontology Mediated Query Answering (OMQA)1 [Calvanese et al., 2008a; Bienvenu and Ortiz, 2015]. In OMQA, the background knowledge takes the form of a set of logical statements, called the TBox, and the records are a set of facts, called the ABox. TBoxes are in general expressed in Description Logics (DLs), which are decidable fragments of First-Order logic that typically can express the combination of explicit and existentially quantified instances mentioned above. Therefore OMQA may provide valuable insight about the computational problem of counting over such data (even though, in practice, DLs may not be the most straightforward way to represent such data).

For Conjunctive Queries (CQs) and Unions of CQs (UCQs), DLs have been identified with the remarkable property that query answering over a KB does not induce extra computational cost (w.r.t. worst-case complexity), when compared to query answering over a relational DB [Xiao et al., 2018]. This key property has led to the development of numerous techniques that leverage the mature technology of relational DBs to perform query answering over a KB. In particular, the DLLite family [Calvanese et al., 2007; Artale et al., 2009] has been widely studied and adopted in OMQA/OBDA systems, resulting in the OWL 2QL standard [Motik et al., 2012].

Yet the problem of counting answers over a DL-Lite KB has seen relatively little interest in the literature. In particular, whether counting answers exhibits desirable computational properties analogous to query answering is still a partly open question for such DLs. A key result for counting over DLLite KBs was provided by Kostylev and Reutter [2015], who also formalized the semantics we adopt in this paper (which we call count semantics). For CQs interpreted under count semantics, they show a coNP lower bound in data complexity, i.e., considering that the sizes of the query and TBox are fixed. However, their reduction relies on a CQ that computes the cross-product of two relations, which is unlikely to occur in practice. Later on, it was shown2 by Nikolaou et al. [2019] that coNP-hardness still holds (for a more expressive DL) using a branching and cyclic CQ without cross-product. Building upon these results, we further investigate how query shape affects tractability.

1Also referred to as OBDA (for Ontology Based Data Access), when emphasis in placed on mappings connecting external data sources to a TBox [Xiao et al., 2018].

Another important question is whether relational DB technologies may be leveraged for counting in OMQA, as done for boolean and enumeration queries. A key property here is rewritability, extensively studied for DL-Lite and UCQs [Calvanese et al., 2007], i.e., the fact that a query over a KB may be rewritten as an equivalent UCQ over its ABox only, intuitively "compiling" part of the TBox into this new UCQ. An important result in this direction was provided by Nikolaou et al. [2019], but in the context of query answering under bag semantics. For certain DL-Lite variants, it is shown that queries that are rooted (i.e., with at least one constant or answer variable) can be rewritten as queries over the ABox. Despite there being a correspondence between bag semantics and count semantics, they show that these results do not automatically carry over to query answering under count semantics, due the way bag answers are computed in the presence of a KB.

So in this work, we further investigate the boundaries of tractability and rewritability for CQs with counting over a DLLite KB, with an emphasis on DLs that can express statistics about missing information. As is common for DBs, we focus on data complexity, i.e., computational cost in the size of the ABox (likely to grow much faster than the query or TBox).

Due to space limitations, the techniques used to obtain our results are only sketched, but full proofs are available in the extended version of this paper [Calvanese et al., 2020].

2 Preliminaries and Problem Specification

We assume mutually disjoint sets NI of individuals (a.k.a. constants), NE of anonymous individuals (induced by existential quantification), NV of variables, NC of concept names (i.e., unary predicates, denoted with �), and NR of role names (i.e., binary predicates, denoted with %). In the following, boldface letters, e.g., c, denote tuples, and we treat tuples as sets.

Functions, Atoms. dom" 5 " and range" 5 " denote the domain and range of a function 5 . Given � � dom" 5 ", the function 5 restricted to the elements in � is denoted 5 j�. A function 5 is constant-preserving iff 2 = 5 "2" for each 2 2 dom" 5 " \ NI. If ( � dom" 5 ", we use 5 "(" for f 5 "B" j B 2 (g. If t = hC1� � � � � C=i is is a tuple with elements in dom" 5 ", we use 5 "t" for h 5 "C1"� � � � � 5 "C="i.

An atom 0 has the form �"B" or %"B� C", with � 2 NC, % 2 NR, and B� C 2 NI [NE [NV.

2The result was stated for the related setting of bag semantics, but the same reduction holds for count semantics as well.

Figure 1: Syntax of DL-Litecore roles ', basic concepts �, and concepts �, where = denotes a positive integer, i.e., = 2 N , .

Interpretations, Homomorphisms. An interpretation I is a FO structure h� I � � I i, where the domain � I is a non-empty subset of NI [ NE, and the interpretation function � I is a function that maps each constant 2 2 NI to itself (i.e., 2 I = 2, in other words, we adopt the standard names assumption), each concept name � 2 NC to a set � I � � I , and each role name % 2 NR to a binary relation % I � � I � � I .

Given an interpretation I and a constant-preserving function 5 with domain � I , we use 5 "I" to denote the interpretation defined by � 5 "I" = 5 "� I " and � 5 "I" = 5 "� I " for each � 2 NC [NR. Given two interpretations I1, I2, we use I1 � I2 as a shortcut for � I1 � � I2 and � I1 � � I2 , for each � 2 NC [NR. A homomorphism � from I1 to I2 is a constant-preserving function with domain � I1 that verifies �"I1" � I2. We note that a set ( of atoms with arguments in NI [ NE uniquely identifies an interpretation, which we denote with inter"(".

KBs, DLs, Models. AKB is a pair K = hT�Ai, where A, called ABox, is a finite set of atoms with arguments in NI, and T , called TBox, is a finite set of axioms. We consider DLs of the DL-Lite family [Artale et al., 2009], starting with the logic DL-Litecore, where each axiom has one of the forms (i) � v � (concept inclusion), (ii) � v :� (concept disjointness), or (iii) ' v ' 0 (role inclusion), where now and in the following, the symbols ', �, and � are defined according to the grammar of Figure 1, and are called respectively roles, basic concepts, and concepts. Concepts of the form �=' are called number restrictions. DL-Litepos allows only for axioms of form (i), with the requirement that the number = in number restrictions may only be 1. In this work we study extensions to this logic along three orthogonal directions: (1) allowing also for axioms of form (ii), indicated by replacing the subscript pos with core; (2) allowing also for axioms of form (iii), indicated by adding a superscript H ; (3) allowing for arbitrary numbers in number restrictions, but only on the right-hand-side (RHS) of concept inclusion, indicated by adding a superscript N - . We also use the superscript H � for logics with role inclusions, but with the restriction on TBoxes defined by Nikolaou et al. [2019], which disallows in a TBox T axioms of the form � v �='1 if T contains a role inclusion '1 v '2, for some '2 < '1.

The semantics of DL constructs is specified as usual [Baader et al., 2003]. An interpretation I is a model of hT�Ai iff inter"A" � I, and � I 1 � � I 2 holds for each axiom �1 v �2 in T. 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". We use the binary relation vT over DL-Lite concepts and roles �1, �2 to denote entailment w.r.t. a TBox T , defined by �1 vT �2 iff � I 1 � � I 2 for each model I of the KB hT � ;i.

A key property of a DL-Lite KB K is the existence of a so-called canonical model I K can, unique up to isomorphism, s.t. there exists a homomorphism from I K can to each model of K. This model can be constructed via the restricted chase procedure by Calvanese et al. [2013], Botoeva et al. [2010].

Finally, we observe that axioms of the form � v �=' can be expressed in the logic DL-Lite H core, but with a possibly exponential blowup of the TBox (assuming = is encoded in binary). For instance, the axiom � v �2% can be expressed as f� v 9%1� � v 9%2� %1 v %� %2 v %� 9% � 1 v :9% � 2 g, with %1, %2 fresh DL roles.

CQs. A Conjunctive Query (CQ) @ is an expression of the form @"x" ?1"t1"� � � � � ?="t=", where each ?8 2 NC [ NR, x � NV, each t8 � NV [ NI, and ?1"t1"� � � � � ?="t=" is syntactic sugar for the duplicate-free conjunction of atoms ?1"t1" ^ � � � ^ ?="t=". Since all conjunctions in this work are duplicate-free, we sometimes treat them as sets of atoms. The variables in x, called distinguished, are denoted by dist"@", head"@" denotes the head @"x" of @, and body"@" denotes the body f?1"t1"� � � � � ?="t="g of @. We require safeness, i.e., x � t1 [ � � � [ t=. A query is boolean if x is the empty tuple.

Answers, Certain Answers. To define query answers under count semantics, we adapt the definitions by Cohen et al. [2007] and Kostylev and Reutter [2015]. A match for a query @ in an interpretation I is a homomorphism from body"@" to I. Then, an answer to @ over I is a pair hl� :i s.t. : � 1, and there are exactly : matches d1� � � � � d: for @ in I that verify l = d8 jdist"@" for 8 2 f1� � � � � :g. We use ans"@� I" to denote the set of answers to @ over I. Similarly, if Q is a set of queries, we use ans"Q� I" to denote the set of all pairs hl� �i s.t. hl� :i 2 ans"@� I" for some : and @ 2 Q, and � = ˝ f: j hl� :i 2 ans"@� I"� @ 2 Qg. Answering a query over an interpretation (i.e., a DB) is also known as query evaluation. Finally, a pair hl� :i is a certain answer to a query @ over a KB K iff : � 1 is the largest integer such that, for each model I of K, hl� :Ii 2 ans"@� I" for some :I � :. We use certAns"@� K" to denote the set of certain answers to @ over K.

Decision Problem. The decision problem defined by Kostylev and Reutter [2015] takes as input a query @, a mapping l, a KB K, and an integer :, and decides hl� :i 2 certAns"@� K". It is easy to see that an instance of this problem can be reduced (in linear time) to an instance where @ is a boolean query and l is the empty mapping, by introducing constants in body"@". We will use the following simplified setting for the complexity results below: if @ is a boolean query and Y the empty mapping, we use : = certCard"@�K" as an abbreviation for hY� :i 2 certAns"@�K". Then, the problem Count is stated as follows:

Count Input: DL-Lite KBK, boolean CQ @, : 2 N , Decide: : = certCard"@�K"

Data complexity. As usual for query answering over DBs [Vardi, 1982] or KBs [Calvanese et al., 2007], we distinguish between combined and data complexity. For the latter, we adopt the definition provided by Nikolaou et al. [2019], i.e., we measure data complexity in the cumulated size of the ABox and the input integer : (encoded in binary).

Query Shape. As we will see later, the shape of the input CQ may play a role for tractability. We define here the different query shapes used throughout the article. Because our focus is on queries with unary and binary atoms, we can use the Gaifman graph [Bienvenu et al., 2017] of a CQ to characterize such shapes: the Gaifman graph G of a CQ @ is the undirected graph whose vertices are the variables appearing in body"@", and that contains an edge between G1 and G2 iff %"G1� G2" 2 body"@" for some role %.3 We call @ connected (denoted with @ 2 CQ C ) if G is connected, linear (@ 2 CQ L ) if the degree of each vertex in G is � 2, and acyclic (@ 2 CQ A ) if G is acyclic. We note that none of these three notions implies any of the other two. In addition, following Nikolaou et al. [2019], we call a CQ rooted (@ 2 CQ R ) if each connected component in G contains at least one constant or one distinguished variable. Finally, a CQ @ is atomic (@ 2 AQ) if j body"@"j = 1.

Rewritability. Given a query language Q, a Q-rewriting of a CQ @ with respect to a KB K = hT�Ai is a Q query @ 0 whose answers over inter"A" alone coincides with the certain answers to @ over K. For instance, for OMQA with boolean or enumeration queries, Q is traditionally the language of domain independent first-order queries, the logical underpinning of SQL. As for queries with counting, it has been shown by Grumbach and Milo [1996], Nikolaou et al. [2019] that counting answers over a relational DB can be captured by query languages with evaluation in LogSpace (data complexity).

3 RelatedWork

Query answering under count semantics can be viewed as a specific case of query answering under bag semantics, investigated notably by Grumbach and Milo [1996] and Libkin and Wong [1997], but for relational DBs rather than KBs. 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 DB setting [Pichler and Skritek, 2013; Chen and Mengel, 2016], but from the perspective of combined complexity, where the shape of the query (e.g., bounded treewidth) plays a prominent role.

As for (DL-Lite) KBs, Calvanese et al. [2008b] define an alternative (epistemic) count semantics, which counts over all grounded tuples (i.e., over NI) entailed by the KB. Such a semantics does not account for existentially implied individuals, and thus cannot capture the statistics motivating our work.

Instead, the work closest to ours, and which first introduced the count semantics that we adopt here, is the one of Kostylev and Reutter [2015], who first showed coNP-hardness of the Count problem for data complexity for DL-Litepos, with a reduction that uses a disconnected and cyclic query. coNPmembership is also shown for DLs up to DL-Lite H core.

Nikolaou et al. [2019], Cima et al. [2019] have studied query answering over a KB under bag semantics, and provide a number of complexity results (including coNP-hardness) and query answering techniques (including a rewriting algorithm). Such semantics is clearly related to the count semantics, but there are notable differences as argued by Nikolaou et al. [2019]. In short, one cannot apply the intuitive idea of treating sets as bags with multiplicities 1. Hence algorithms and complexity results cannot be transferred between the two settings, and this already holds for ontology languages that allow for existential restrictions on the LHS of ontology axioms (note that all the logics considered in this paper allow for such construct). The following example by Nikolaou et al. [2019] illustrates this.

3This definition implies that the Gaifman graph of @ has an edge from G to G if %"G� G" 2 body"@".

Example 1. Consider the KB K = hf�1 v 9%� 9% � v �g, f�1"0"� �1"1"gi and the query @"" �2"H". If we evaluate this query in the count setting, then the answer is the empty tuple hi with cardinality 1, because of the following model:

However, such structure does not accurately represent a bag interpretation. In fact, under bag semantics every concept and property is associated to a bag of elements. Such bag can be seen as a function that returns, given an element, the number of times such element occurs in the bag. We build now a (minimal) bag interpretation I for K. To satisfy A, we set � I 1 "0" = 1 and � I 1 "1" = 1 To satisfy �1 v 9%, we introduce a single element D (as above) and obtain % I "0� D" = 1 and % I "1� D" = 1. Therefore, "% � " I "D� 0" = 1 and "% � " I "D� 1" = 1, which, according to the semantics by Nikolaou et al. [2019], imply that "9% � " I "D" = 2. Therefore, to satisfy 9% � v �2, it must be that � I 2 "D" = 2. In fact, the certain answer to @ over I under bag-semantics is the empty tuple hi with multiplicity 2.�

4 Tractability and Intractability

We investigate now conditions for in/tractability (in data complexity) of Count, focusing on the impact of the shape of the query. We observe that the queries used by Kostylev and Reutter [2015] and Nikolaou et al. [2019] to show coNP-hardness are cyclic, and either disconnected or branching. Building upon these results, we further investigate whether cyclicity is necessary for intractability. Our results indicate that for certain DLs, non-connectedness or branching alone is a sufficient condition for intractability, whereas cyclicity is not. We start with a membership result:

Proposition 1. Count is in P in data complexity for DLLite H - N - pos and connected, linear CQs (CQ CL ).

Proof (Sketch). We start with DL-Lite H � pos , and then discuss how to extend the proof to DL-Lite H - N - pos . If K = hT�Ai is a DL-Lite H - N - pos KB and @ a boolean query in CQ CL , consider the set match"@� I K can" of all matches for body"@" over the canonical model I K can of K. Then viewing match"@� I K can" as a relation (i.e., a set of tuples), let �min be the set of all constant-preserving functions, whose domain is the set of all arguments in match"@� I K can" and that minimize the number of resulting tuples when applied to match"@� I K can". Because @ is connected and linear, and thanks to the limited expressivity of DL-Lite H - N - pos , it can be shown that theremust be some 5 2 �min that verifies j 5 "match"@� I K can""j = j match"@� 5 "I K can""j. Since every model I of K verifies match"@� I" � �"match"@� I K can"" for some homomorphism �, and because 5 "I K can" is a model of K, it follows that certCard"@�K" = j 5 "match"@� I K can"" j.

Then it can also be shown that j 5 "match"@� I K can""j can be computed in time polynomial in jAj.

Now for DL-Lite H - N - pos , to account for cardinality restrictions, we associate in every interpretation I a cardinality cardI "4" to each 4 2 � I : cardinality 1 for elements of NI, and possibly more than 1 for elements of NE. E.g., if K implies that an element 0 2 NI has 4 %-successors for some role %, and if there is only one 1 2 NI s.t. "0� 1" 2 % A , then "0� 4" 2 % I K can for some 4 2 NE, and card I K can "4" = 4 � 1 = 3. Applying a function 5 to an interpretation I affects these cardinalities: for each 4 2 � 5 "I" , card 5 "I" "4" = maxfcardI"4 0 " j 5 "4 0 " = 4g. Then we extend cardinality to a tuple t of elements, as cardI"t" = ˛ 42t cardI"4", and to a set ) of tuples, as cardI")" = ˝ t2) cardI"t". In this extended setting, certCard"@�K" = card 5 "I" "match"@� I K can"" for some function 5 that minimizes card 5 "I" "match"@� I K can"". And this value can still be computed in time polynomial in jAj. �

We now show that disconnectedness alone leads to intractability, i.e., cyclicity is not needed.

Proposition 2. Count is coNP-hard in data complexity for DL-Litepos and acyclic, linear, but disconnected CQs (CQ AL ).

Proof (Sketch). The proof is a direct adaptation of the one provided by Kostylev and Reutter [2015]. We use a reduction from co-3-colorability to an instance of Count. Let G = h+� �i be an undirected graph with vertices +, edges �, and without self-loops. The ABox is A = fVertex"E" j E 2 +g [ fedge"E1� E2" j "E1� E2" 2 �g [ fBlue"b"� Green"g"� Red"r"� hasColor"a� b"� hasColor"a� g"� hasColor"a� r"� edge"a� a"g for some fresh constants a, b, r, and g. The TBox is T = fVertex v 9hasColor� 9hasColor � v Colorg. And the (acyclic, non-branching) query is @"" Color"2"� edge"E1� E2"� hasColor"E1� 21"� hasColor"E2� 22"� Blue"21"� Blue"22"� edge"E3� E4"� hasColor"E3� 23"� hasColor"E4� 24"� Green"23"� Green"24"� edge"E5� E6"� hasColor"E5� 25"� hasColor"E6� 26"� Red"25"� Red"26". Then it can be verified that 4 = certCard"@� hT�Ai" iff G is not 3-colorable. �

Next we show that linearity is required for tractability:

Proposition 3. Count is coNP-hard in data complexity for DL-Lite H pos and acyclic, connected, but branching CQs (CQ AC ).

Finally, we observe that the coNP upper bound provided by Kostylev and Reutter [2015] for DL-Lite H core extends to DL-Lite HN - core ,4 since number restrictions can be encoded in DL-Lite H core, as explained in Section 2.

Proposition 4. Count is in coNP in data complexity for DLLite HN - core and arbitrary CQs (CQ).

5 Rewritability and Non-rewritability

We now investigate conditions for rewritability. We start by showing P-hardness for DLs with role inclusions and disjointness, and atomic queries.

Proposition 5. Count is P-hard in data complexity for DL-Lite H core and atomic queries (AQ).

4With a technicality: the input integer : is not included in the notion of data complexity used by Kostylev and Reutter [2015].

Proof (Sketch). We show a LogSpace reduction from the co-problem of evaluating a boolean circuit where all gates are NAND gates [Greenlaw et al., 1991] to Count. We view such a circuit as an interpretation C whose domain consists of the circuit inputs and gates. )� , �� , and )$ are unary predicates interpreted in C as the positive circuit inputs, the negative circuit inputs and the (unique) target gate respectively. % is a binary predicate s.t. "@� 6" 2 % C iff gate 6 has input @ (where @ can be either a circuit input or another gate).

The TBox T is defined by T = P [ T1 [ T2, where P = f%) v %� %� v %g, T1 = f�� v �� )� v )� )$ v )� ) v :�g and T2 = f) v 9%� � � � v "�2 %) � "� 9%) v )� 9%� v �g.5 Intuitively, the unary predicates ) and � correspond to gates that evaluate to true and false respectively in the circuit, and binary predicates %) and %� specialize % to positive and negative inputs. T2 encodes constraints pertaining to NAND gates: a positive gate must have at least one negative input, and a negative gate must have two positive inputs. Then T1 enforce that no gate can be both positive and negative, and that the circuit inputs and the output gate have the desired truth values.

Finally, as a technicality, the ABox A is an extension of C, i.e., C � inter"A". The domain of A contains 3 additional individuals t1� t2 and f , and it extends % C with - 82")� " C f%"f � 8"� %"t1� 8"g, - 82"�� " C f%"t1� 8"� %"t2� 8"g, and f%"t1� f "� %"t2� f "� %"f � t1"� %"f � t2"� %"t2� t1"� %"t1� t2"g.

Then it can be verified that C is a valid circuit iff there exists a model I of hT�Ai s.t. j% I j = j% A j. Now let @ be the query @"" %"G1� G2". It follows that C is not a valid circuit iff j% A j , 1 = certCard"@� hT�Ai". �

Assuming P * LogSpace, this implies that for such DLs, even atomic queries cannot be rewritten into a query language whose evaluation is in LogSpace, which is sufficient to capture counting over relational databases. Interestingly, the reduction can be adapted so that it uses instead a query that is rooted, connected and linear (but not atomic).

Proposition 6. Count is P-hard in data complexity for DL-Lite H core and rooted, connected, linear queries (CQ CLR ).

We now focus on positive results, and rewriting algorithms.

5.1 Universal Model

We follow the notion of universal model proposed by Nikolaou et al. [2019]: a model I of a KB K is universal for a class of queries Q iff ans"@� I" = certAns"@� K" holds for every @ 2 Q. Nikolaou et al. [2019] and Cima et al. [2019] investigated the existence of a universal model for queries evaluated under bag semantics. As we discussed in Section 3, these results carry over to the setting of count semantics, but only for ontology languages that disallow existential restriction on the LHS of ontology axioms. The existence of such model was proved over the class CQ R , for the DL-Lite 1 members up to DL-Lite b R � [Nikolaou et al., 2019] and DL-Lite b F [Cima et al., 2019], with some syntactic restrictions. It was also shown that CQ R queries can be rewritten into (BCALC) queries to be evaluated over the (bag) input ABox. Neither of these logics is able to encode numbers in the TBox though, therefore they cannot capture statistical information about missing data. And as discussed in the introduction, this information may be important in some applications [Chen and Mengel, 2016], and is one of the motivations behind our work. Note also that both logics allow for existentials on the LHS of axioms, and therefore these results do not carry over to count semantics.

5The axiom�2 %) � can be encoded into DL-Lite H core, as explained in Section 2.

Our first result shows the existence of a universal model for CQ CR and DL-Lite N - core, and queries evaluated under count semantics. Precisely, the canonical model I K can obtained via the restricted chase from Calvanese et al. [2013] and Botoeva et al. [2010] is a universal model. From now on, we denote by ch8 "K" the set of atoms obtained after applying the 8-th chase step over the KB K, and by ch1"K" the (possibly infinite) set of atoms obtained by an unbounded number of applications.

Proposition 7. DL-Lite N - core has a universal model w.r.t. Count over CQ CR queries.

Proof (Sketch). Consider a CQ CR query @ and a KB K, and let match"@� I K can" denote the set of all matches for body"@" over the canonical model I K can := ch1"K". Let I be a model of K. Then there must exist a homomorphism g from I K can to I. One immediately obtains that g"match"@� I K can"" � match"@� g"I K can"", and therefore (i) jg"match"@� I K can""j � j match"@� g"I K can""j. Then relying on the fact that @ is rooted, that the chase is restricted, and that DL-Lite N - core does not allow for role subsumption, it can proven that (ii) j match"@� I K can"j � jg"match"@� I K can""j. So from (i) and (ii) , j match"@� I K can"j � j match"@� g"I K can""j holds. Then, since g is a homomorphism from I K can to I, g"I K can" � � must hold, and therefore j match"@� g"I K can""j � j match"@� I"j. We conclude that j match"@� I K can"j � j match"@� I"j. �

5.2 Rewriting for DL-Lite N - core

We introduce PerfectRefcnt, a rewriting algorithm for DL-Lite N - core inspired by PerfectRef [Calvanese et al., 2006], and show its correctness. There is a fundamental complication in our setting, of which we provide an example. Consider a CQ @, a DL-Lite N - core KB K, and a query @ 0 among those produced by PerfectRef or any other rewriting algorithm for CQs. Then, each match l 0 for @ 0 in inter"A" can be extended to the anonymous individuals so as to form a "complete" match l for @ in inter"ch1"K"" in a certain number of ways (dictated by the axioms in the ontology). From now on, we call such number the anonymous contribution relative to @ 0 . The following example shows that the anonymous contribution is related to the number restrictions occurring in K.

Example 2. Consider the query @"G" %"G� H", and the KB K = hf� v �3%g� f�"0"gi. Starting from @, PerfectRef will produce, as part of the final rewriting, a query @ 0 "G" �"G". Note that there is a single match ' = fG 7 ! 0g for @ 0 over inter"A", and that ' can be extended into exactly three matches for @ in inter"ch1"K"", by mapping variable H into some anonymous individual. �

To deal with the fact that the anonymous contribution to a count is a non-fixed quantity that depends on the axioms in the ontology, our algorithm is substantially different from PerfectRef and significantly more complicated. It is also not related to the one by Nikolaou et al. [2019], which is based on tree-witness rewriting [Kikot et al., 2012] rather than on PerfectRef, and was not designed for settings where the anonymous contribution is a non-fixed quantity.

Given a CQ @ and a TBox T , PerfectRefcnt produces a set Q 0 of queries such that, for any ABox A, ans"Q 0 � inter"A"" = certAns"@� hT�Ai". Each query in Q 0 comes with a multiplicative factor that captures the anonymous contribution of each match for that query. Queries in Q 0 are expressed in a target (query) language, for convenience named FO(Count), which is a substantial enrichment of the one introduced in Section 2, but has a straightforward translation into SQL. Note that we use FO(Count) only to express the rewriting, while user queries over the KB are still plain CQs.

Following Cohen et al. [2007], FO(Count) allows one to explicitly specify a subset of the non-distinguished variables, called aggregation variables, for which we count the number of distinct mappings (so far, we implicitly assumed all non-distinguished variables as aggregation variables). It also allows for a multiplicative factor to be applied after the (count) aggregation operator, a restricted use of disjunctions, equalities between terms, atomic negation, and the use of nested aggregation in the form of a special 9 =8 operator (which intuitively corresponds to a nested aggregation plus a boolean condition requiring the result of the aggregation to be equal to 8).

A query in FO(Count) is a pair h&"x� cnt"y" � U"� �i, where variables x are called group-by variables, variables y are called aggregation variables (intuitively, cnt"y" corresponds to the SQL construct count distinct), x \ y = ;, U 2 N is a positive multiplicative factor, and � is a set of rules � @ : "x : y" k : � � 1 � : � < � . The symbol ':' in the head6 of each rule is to distinguish between group-by and aggregation variables. Eachk : in�is a conjunctionk : ?>B ^k : =46^k : 4@ ^k : 9 of positive atoms (k : ?>B), negated atoms (k : =46), equalities between terms (k : 4@), and special atoms (k : 9 ), which we call 9-atoms, of the form 9 =8 I � %"F� I", where 8 2 N0, F 2 x [ y, and I is a variable that occurs only once in @.

A mapping d is a match for k : in an interpretation I if:

• d"k : ?>B" � I;
• d satisfies all equalities in k : 4@ ;
• there is no d 0 � d such that d 0 "�"z"" 2 I, for some :�"z" in k : =46 ;
• for each 9 =8 H '"F� I" in k9, there are exactly 8 mappings d1� � � � � d8 such that, for 9 2 f1� � � � � 8g we have that d 9 � d and d 9 "'"F� I"" � I.

A mapping d is a match for � in an interpretation I, if for some @"x : y" k in � it is a match for k in I. Amapping l is an answer to h&"x� cnt"y" � U"� �i over I with cardinality : � U iff there are exactly : mappings [1� � � � � [: such that, for 8 2 f1� � � � � :g:

• l = [8 jx, and

· [8 can be extended to a match d for � in I s.t. djx[y = [8 . Note that our semantics also captures the case when the operator cnt"" is over an empty set of variables (in that case, the : above would be equal to 1). This technicality is necessary for the presentation of the algorithm.

6Head and body of a rule are defined as for CQs.

We are now ready to introduce PerfectRefcnt. Consider a satisfiable knowledge base K = hT� Ai, and a CQ CR query @"x" k"x� y". PerfectRefcnt takes as input @ and T and initializes the result set Q as

Then the algorithm expands Q by applying the rules AtomRewrite, Reduce, GEU, and GEV until saturation, with priority for AtomRewrite and Reduce. The set Q 0 obtained at the end of this process does not necessarily contain just queries (in the sense of our definition above), and hence needs to be normalized (see later).

To define the rules of the algorithm, we first need to introduce some notation. In the following, % � "F� I" stands for %"I� F". Hence, also '"F� I" when ' = % � stands for %"I� F". We use '_' to denote a fresh variable introduced during the execution of the algorithm. For a basic concept �, notation b"�� F" stands for �"F" if � 2 NC, or '"F� _", if � = �1'. Given a set B of basic concepts, subcT "B" is defined as the set of basic concepts f� 0 j � 0 vT �� � 2 Bg. If q, k are two conjunctions of atoms and 0 is an atom in q, we use q»0�k… (resp., q»0�>…) to denote the conjunction identical to q, but where 0 is replaced with k (resp., 0 is deleted from q). By extension, if A is a rule, A »0�k… denotes the rule head"A" body"A"»0�k…. If � is a basic concept and ' a role, cardT "�� '" denotes the maximal = s.t. � v �=' 2 T. A variable G is bound in a rule A if it is a group-by variable, or if it occurs more than once in the set of positive atoms of A. We say that G is U-blocked if it is bound, or if it occurs more than once in head"A", or if it occurs in some 9-atom in body"A". Finally, G is V-blocked if it is bound, or if it occurs more than once in head"A", or if it occurs in some atom of the form 9 =8 I '"F� I" with 8 ¡ 0.

To ease the presentation, for the exposition of rules GEU and GEV we will ignore details concerning the renaming of variables, and assume that variables belong to the input query. AtomRewrite ( �'). fBq1� � � � � q:g �' fq1� � � � � q:�1� q 0 : g if

• q: = h&"x� cnt"y" � U"� �i;
• for some A 2 �, for some �"z" 2 body"A", either:
• �"z" is of the form �"I", and � v � 2 T, or
• �"z" is of the form '"F� I", � v �=' 2 T, I is an unbound variable, and if head"A" = @"s : t", then I 8 t;

Reduce ( '). fq1� � � � � q:g ' fq1� � � � � q:�1� q 0 : g if

• q: = h&"x� cnt"y" � U"� �i;
• f�1"z1", �z2"g � body"A" for some A 2 �;
• f is a most general unifier for �"z1" and �"z2"; with the following restrictions:
• a variable in x can map only to a variable in x;
• a variable in y can map only to a variable in x [ y;
• dom"f" � z1 [ z2 and range"f" � z1 [ z2.
• q 0 : = h&"x� cnt"y" � U"� �[ ff"A »�"z2"�>…"gi.

GEU ( �U ). fq1� � � � � q:g �U fq1� � � � � q:g [ Q: if

• q: = h&"x� cnt"y" � U"� �i
• ¢ '"F� I", with F� I 2 x [ y, is an atom such that

• Let k9 be the conjunction of all exists-atoms in any rule A 2 � (by construction, such conjunction is the same for all rules in �). Then the conjunction k9^9 0 H'"F� I" (seen as a set) must not appear in other rules from fq1� � � � � q: g;
• B: is the maximal set of basic concepts � such that � v �=� ' 2 T, for some =�;
• � Q: is defined as follows. First, let part"B:" denote the set of all pairs hB 1 � B 2 i such that B 1 � B:, B 2 � B:, B 1 < ;, and subcT "B 1 " \ subcT "B 2 " = ;. Then, for a set B of basic concepts, let cpT "B" denote the cartesian product ˛ �2B subcT "�". And if B, B 0 are two sets of basic concepts, we call atomic decomposition the formula ad"B� B 0 ", defined as:

If k is a formula, let rpl"A� k" designate the rule:

Finally, if 9 is an integer, let qh" 9" be the expression:

We can now define Q: as:

GEV ( �V ). This rule is defined as �U , but with the difference that conditions ¢ and � are as follows:

• ¢ '"F� I" is an atom such that:

• � As item � for GEU, with the additional condition that all atoms in which variable H occurs are removed.

Note that, once all rules have been applied to saturation, the resulting set Q 0 is technically not yet a set of queries, because of renamed variables, constants, or repetitions in the head of a rule. To transform each element h&"x� cnt"y" � U"� �i of Q 0 into a query, we normalize it by renaming the variables in rules in �, based on their positions, according to x and y, and by replacing constants and repeated variables in the head of a rule with suitable equalities in its body.

The intuition behind PerfectRefcnt is the following. First of all, we observe that the rewriting rules AtomRewrite and Reduce are analogous to their counterparts in the original PerfectRef algorithm. The restrictions on the unifier in Reduce are meant to limit the possible renamings of variables. Rewriting rules GEU and GEV extend the way existential quantification is handled in PerfectRef, and are the only ones eliminating aggregation variables from the rules in �. Each time one such variable is eliminated, it can be potentially mapped in "=�8" different ways into the anonymous part of the canonical model. The 9-atoms, together with the relative atomic decompositions, check the number 8 of mappings that are already present in the ABox. The factor U keeps track of the number of ways variables eliminated in previous steps can be mapped into the anonymous part. Hence, the quantity "=�8" � U captures the anonymous contribution relative to the query.

Example 3. Consider the KBK = hT�Ai, with

and the input CQ @"G" �"G"� %1"G� H1"� %2"H1� H2". The chase model of K is represented in Figure 2. The initialization step sets Q = fh&"G� cnt"H1� H2" � 1", f@"G:H1� H2" �"G"� %1"G� H1"� %2"H1� H2"gig. Since H2 is unbound, we can apply rule GEU, which produces the following set Q 0 :

Rule Reduce can now be triggered by the second, the third, and the last rule in Q 0 . In particular, an application of Reduce on the second query leads to the query:

On such query we can apply rule GEV producing, among others, the following query:

Let us analyze the queries produced by PerfectRefcnt that return at least one answer. The query after the initialization step returns the number of paths "G� H1� H2" in A conforming to the structure dictated by the body of the input query. Since there are two such paths, such query returns the answer hG 7 ! 0� 2i. The queries generated by GEU check for all sub-paths "G� H1" of "G� H1� H2" such that G is an element of �, H1 is a %1-successor of G, and H1 has less %2-successors in the ABox than what the TBox prescribes. There is one such path in I K can, namely the one terminating in node 1 that has only two %2-successors in A. This path is captured by the fourth query in Q 0 , which returns as answer hG 7 ! 0� 1i: indeed, there is a single way of extending this path into the anonymous part. The queries generated by GEV are to be interpreted in a similar way. In particular, the query we highlighted retrieves the individual 0, since this node has only one %1-successor in A but it should have at least two %1-successors according to T. The answer to such query is hG 7 ! 0� 3i. Indeed, there are three ways of extending the match G 7 ! 0 into the anonymous part. Summing up the numbers, we get that our set of queries returns the answer hG 7 ! 0� 6i, which indeed is the answer to our input query over the chase model from Figure 2. �

The algorithm terminates because the application of AtomRewrite and Reduce is blocked upon reaching saturation, and each application of GEU and GEV reduces the number of variables in k by 1. The following lemmas show the correctness of PerfectRefcnt.

Lemma 8. Consider a DL-Lite N - core knowledge base K = hT�Ai and a connected, rooted CQ @. Consider a query & 0 belonging to the output of PerfectRefcnt over @ and K. Then, each match l 0 for & 0 in inter"A" can be extended into a match l for @ in inter"ch1"K"".

Proof (Sketch). The claim can be proved through a straightforward induction over the number of chase steps. �

The next lemma states that the opposite direction also holds, i.e., that all matches are retrieved.

Lemma 9. Consider a DL-Lite N - core knowledge base K = hT � Ai and a connected, rooted CQ @. Every match l for @ in inter"ch1"K"" is an extension of some match l 0 for & 0 in inter"A", where & 0 belongs to the output of PerfectRefcnt.

Proof (Sketch). The proof follows the one by Calvanese et al. [2006], however one has to pay attention to the fact that here we deal with matches rather than with assignments for the distinguished variables. Another technical difference with that proof is that in our case the nodes in the chase tree are sets of atoms rather than single atoms. �

The last lemma tells us that our way of capturing the anonymous contribution is indeed correct.

Lemma 10. Consider a DL-Lite N - core knowledge base K = hT�Ai and a connected, rooted CQ @. Consider a query h& 0 "x� cnt"y" � U"� �i belonging to the output of PerfectRefcnt over @ and K. Then, each match l 0 for & 0 in inter"A" can be extended into exactly U matches l for @ in inter"ch1"K"" with range"l n l 0 " � NE.

Proof (Sketch). By induction on the number of applications of GEU and GEV. It uses Lemma 8 and the fact that variables are never eliminated by AtomRewrite or Reduce. The atomic decomposition in GEU and GEV guarantees that all combinations of number restrictions are considered. �

Proposition 11. Consider a DL-Lite N - core knowledge base K = hT�Ai and a connected, rooted CQ @. Let Q be the set of queries returned by a run of PerfectRefcnt over @ and K. Then:

Proof (Sketch). The claim follows from Lemmas 9 and 10, and by observing that the query & 0 in Lemma 10 is unique due to 9 = 8 expressions, atomic decompositions, and the restrictions on GEU and GEV. Therefore, matches are not counted twice.�

The execution of PerfectRefcnt does not depend on the ABox. Considering that the evaluation of FO(Count) queries is in LogSpace in data complexity, this yields:

Proposition 12. Count is in LogSpace in data complexity for DL-Lite N - core and rooted, connected CQs.

6 Conclusion and Perspectives

Table 1 summarizes our results for data complexity of query answering under count semantics for variants of CQs and DLLite. Among other observations, these results indicate that for certain DLs, whether a CQ is connected and branching affects tractability. An interesting open question in this direction is whether the P-membership result for DL-Lite H - N - pos and AQ/CQ CL is tight. Indeed, the P-hardness result provided for AQ holds for a more expressive DL (namely DL-Lite H core), which allows for disjointness and arbitrary interactions between role subsumption and existential quantification.

A main contribution of this work is the query rewriting technique provided in Section 5. It shows that for connected and rooted CQs, and for variants of DL-Lite with neither disjointness nor role subsumption, rewritability into a variant of SQL with aggregates can be regained. An interesting open question is whether rewritability still holds for rooted queries and DL-Lite H - N - core , i.e., when allowing for restricted role subsumption.

Finally, it must be emphasized that this work is mostly theoretical, and does not deliver a practical algorithm for query answering under count semantics over DL-Lite KBs. In particular, the definition of data complexity that we adopted does not take into account the cardinality restrictions that may appear in the TBox. This is arguable: in scenarios where these restrictions may encode statistics, it is reasonable to consider that these numbers "grow" with the size of the data. The rewriting defined in Section 5 may produce a query whose size is exponential in such numbers (when they are encoded in binary). Therefore a natural continuation of this work is to investigate how arithmetic operations and nested aggregation can be used to yield a rewriting whose size does not depend on the numbers that appear in cardinality restrictions.

Acknowledgements

This research has been partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, by the Italian Basic Research (PRIN) project HOPE, by the EU H2020 project INODE, grant agreement 863410, by the CHISTERA project PACMEL, and by the project IDEE (FESR1133) through the European Regional Development Fund (ERDF) Investment for Growth and Jobs Programme 2014-2020.