Evaluating ontology-mediated queries (OMQs) is computationally intractable. On the one hand, this is due to the complexity of reasoning with the ontology alone, which is ExpTime-hard even for relatively simple description logics such as E LI. On the other hand, it is due to evaluating the actual queries, which is NP-hard in combined complexity for the widely used class of conjunctive queries (CQs). As a consequence, the complexity of evaluating ontology-mediated queries has been analyzed from several angles. Traditionally, one xes an ontology language L and a query language Q and studies the complexity of evaluating OMQs from the resulting OMQ language (L; Q), inspecting combined complexity, data complexity, or parameterized complexity [5,8,9,15,16,19,20,21,24]. Recently, this approach has been complemented by more ne-grained analyses. A negrained approach to data complexity is pursued in [3,23,22], where the aim is to identify for every OMQ Q 2 (L; Q), the precise data complexity of evaluating Q. A ne-grained study of parameterized complexity is initiated in [2,1], aiming to identify for every class of OMQs C (L; Q), the precise complexity of evaluating OMQs from C when the parameter is the size of the OMQ. A main aim in this approach is to delineate classes C for which evaluation is xed-parameter tractable (FPT) from classes for which evaluation is W[1]-hard, and it turns out that bounded treewidth is an essential property in this context. In all of these studies, OMQ evaluation means that an answer candidate is given as part of the input, in the form of a tuple of constants a, and then the aim is to decide whether a is indeed an answer. There are, however, many other natural modes of evaluating OMQs such as computing all answers and counting the number of answers (of which there can be exponentially many). This abstract reports on work concerned with counting the number of answers to OMQs. This is important, for example, when there are too many answers to compute all of them, and it is also a fundamental operation in data analytics and in decision support. In fact, answer counting is supported by almost every data management system. Despite its relevance, however, the problem has received little attention so far in ontology-mediated querying. Notable exceptions are [18,17,4,7], mostly in the context of the DL-Lite family of description logics. Our aim is to study the parameterized complexity of counting the number of answers to OMQs formulated in the language (G; UCQ) where UCQ denotes
unions of conjunctive queries and G denotes guarded TGDs used as an ontology
language, also known as guarded Datalog [
Before we state our results, let us brie y describe the situation in answer
counting for classes of conjunctive queries and UCQs in the classical setting, i.e.
without ontologies. In [
It is also shown in [
We establish a similar classi cation for classes of OMQs from the OMQ
language (G; UCQ) which we state in the following. For Q 2 (G; UCQ), we use
Q9 to denote the existential rewriting of Q which is equivalent to Q and does
not use existential quanti ers in TGD heads in the ontology. Such a rewriting
can be e ectively constructed [
cl9CM(C) = fcore(chO9 (p)) j 9Q 2 C : Q9 = (O9; S; q9) and p 2 clCM(q9)g 1 Here and in what follows, we generally assume that all CQs are homomorphism cores, up to the answer variables. Without this assumptions, one would have to require that each CQ in C is equivalent to a CQ that has bounded treewidth and bounded treewidth of the contract.
Answer Counting for OMQs based on Guarded TGDs where chO(q) denotes the result of chasing q with O. An OMQ has full data schema if every relation symbol can occur in the data.
Theorem 1. Let C (G; UCQ) be a recursively enumerable class of OMQs with full data schema and relation symbols of bounded arity. Then the following hold: 1. If the treewidths and contract treewidths of CQs in cl9CM(C) are bounded, then
AnswerCount(C) is in FPT.
2. If the treewidths of CQs in cl9CM(C) are unbounded and the contract treewidths
of CQs in cl9CM(C) are bounded, then AnswerCount(C) is W[
Count(C) is #W[
The upper bounds are easy to obtain by replacing the given OMQ with its
existential rewriting, constructing the (then nite) chase, and then applying the
results for UCQs discussed above. In the lower bounds, we also rst transition
to the existential rewriting. We then give parameterized Turing-reductions from
CQ-based OMQs to UCQ-based ones and, in a second step, from CQs without
ontologies to CQ-based OMQs. Our constructions are strongly inspired by those
from [
It is interesting to note that the ontology interacts with all three measures from Theorem 1, that is, there are classes C (G; UCQ) such that the treewidths of CQs in the OMQs in C are unbounded while the treewidths of CQs in cl9CM(C) are bounded, and likewise for contract treewidth and dominating starsize.
Regarding rami cations for description logic, we recall that every ontology formulated in E LIH can be transformed into a well-known normal form that avoids syntactic nesting of concept constructors, and that E LIH-ontologies in normal form fall within G. Consequently, Theorem 1 still holds when G is replaced with E LIH, assuming normal form. The case where E LIH-ontologies are not in normal form can be covered by an easy modi cation of our proofs. In fact, we could extend Theorem 1 to ontologies that are sets of frontier-guarded TGDs in which the treewidth of the rule bodies is bounded by a constant. This also captures E LIH-ontologies that are not in normal form.
Acknowledgments. This research was supported by ERC consolidator grant 647289 CODA.