/ coNEXP
coNEXP-h / coN2EXP
coNEXP-c (f.-d. TBox)
Exh. rooted
PP-c
2p-h
PP-h
/ coNEXP
the aggregation are required to match to data constants. However, as discussed in
[
7
], 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 bene t) that there must be at least 3
children. This led Kostylev and Reutter [
7
] to de ne 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 di erent 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 2p-hard (resp.
coNEXPhard) in combined complexity for DL-Litecore (resp. DL-LiteR). Several questions
were left unanswered by their work, including the di culty of recognizing the
optimal lower bound and the impact of allowing multiple aggregation variables.
In the present work, which is reported in [
1
], we return to the issue of
handling counting queries in OMQA and make several important contributions. We
rst introduce a new notion of counting CQ that generalizes the two forms of
queries from [
7
] and allows arbitrarily many counting variables. 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 we further provide an improved
coNEXP upper bound for the relevant case of nite-depth TBoxes. We also
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 [
8
], identi ed a case in which rootedness leads to
tractable data complexity for counting queries. This motivated us to perform
a thorough investigation of rooted counting queries, which yielded several
improvements upon existing complexity bounds (see Table 1), including a tight
PP-completeness result for the natural subclass of exhaustive rooted counting
CQs, in which every non-answer variable is a counting variable. As our nal
contribution, we investigate the problem of recognizing the best certain interval