We summarize our recent work [1] on extending the study of counting queries to Horn description logics outside the DL-Lite family.
Ontology-mediated query answering (OMQA) facilitates access to data through the use of
ontologies, which provide a convenient vocabulary for query formulation and capture domain
knowledge that can be exploited to obtain more complete query results. The OMQA approach
has been extensively studied over the past fifteen years [
While most work on OMQA considers that the user query is a conjunctive query (CQ), there has been significant interest in exploring the possibility of adopting more expressive query languages for OMQA. In particular, several works have investigated ways of equipping CQs with some form of counting [7, 8, 9]. A recent approach, proposed in [10] as a generalization of [8], considers counting conjunctive queries (CCQs) that are syntactically defined like standard CQs except that some variables may be designated as counting variables. In each model of the knowledge base, we can count the number of possible assignments to the counting variables that make the query answer hold. As the count value may difer between models, the goal is to identify intervals that provide upper and lower bounds on the count values across all models.
The problem of answering CCQs is intractable, in both data and combined complexity, for common DL-Lite dialects such as DL-Litecore and DL-Litecℋore[8]. Recent works have shown that intractability arises even for simple forms of CCQs [11, 12]. However, some interesting tractable cases have also been identified, notably, rooted CCQs [ 10, 11, 13] and cardinality queries [12] † coNP
NL 2EXP coNP coNP coNEXP†
NL
NL coNEXP†
† coNP † coNP 2EXP
ℰℒ(ℋ⊥), ℰℒ(ℋℐ)
EXP EXP 2EXP ℰℒ(ℋ)ℐ⊥ coNEXP coNEXP 2EXP coupled with DL-Litecore ontologies. Query rewriting techniques have also begun to be explored [14]. However, despite these advances, we still have only a partial understanding of CCQ answering in common DL-Lite dialects, and the precise combined complexity has remained elusive: the current bounds for DL-Litecℋore are between coNEXP and coN2EXP [8]. Moreover, to the best of our knowledge, CCQ answering has not yet been studied for DLs outside the DL-Lite family.
In [
Using this new approach, we are able to establish a 2EXP upper bound in combined complexity for ℰ ℒℋℐ⊥. A matching lower bound, which applies to both ℰ ℒ and DL-Litepℋos, is obtained by establishing a novel connection between CCQ answering and OMQA with closed predicates. This yields 2EXP-completeness for a wide range of Horn DLs and closes the combined complexity gap for CCQ answering in DL-Litecℋore. We further prove a coNEXP lower bound for DL-Litepos, which matches an existing coNEXP upper bound, yielding the precise combined complexity for DL-Litecore as well. We also explore how to shrink the size of the models implicitly generated by our procedure, producing models with bounded size which we use to show that CCQ answering is coNP-complete in data complexity for all logics between ℰ ℒ and ℰ ℒℋℐ⊥.
In addition to CCQs, we also investigate the special case of cardinality queries, which correspond to Boolean atomic CCQs and allow us to ask for (bounds on) the number of members of a given concept or role. We obtain a complete picture of data and combined complexity of answering cardinality queries in ℰ ℒℋℐ⊥ and its various sublogics. While the data complexity is coNP-complete for all considered logics, the combined complexity ranges from NL or coNP in DL-Lite logics to EXP or coNEXP for ℰ ℒ and its extensions. We achieve these results using a variety of techniques: refinements of our approach for general CCQs, adaptations of existing constructions, and further reductions involving closed predicates. Table 1 summarizes the combined complexity results for both CCQs and cardinality queries.
We have extended the study of CCQ answering to Horn DLs outside the DL-Lite family,
establishing a complete picture of the combined and data complexity of the problems of answering
CCQs and cardinality queries in ℰ ℒℋℐ⊥ and its various sublogics. Interestingly, the new
techniques we devised not only allowed us to close some open questions concerning the combined
complexity of CCQ answering in DL-Lite, but also extend to non-Horn DLs: the 2EXP procedure
can be adapted to handle ℒℋℐ KBs as our investigations, not presented in [
Going forward, the main challenge is to develop practical algorithms. A first direction is to look for restrictions on the query or ontology that ensure polynomial data complexity for logics of the ℰ ℒ family. Unfortunately, our results on cardinality queries show that restrictions as have been considered for DL-Lite [11, 10, 12] are not suficient to obtain tractability in ℰ ℒ, so novel restrictions need to be identified. Second, it would be desirable, for ℰ ℒ but also for DL-Lite, to develop more refined coNP procedures that are amenable to implementation using SAT solvers. We believe that our improved understanding of the structure of optimal models will prove helpful for both of these research directions.
Partially supported by ANR project CQFD (ANR-18-CE23-0003). [5] D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Tractable reasoning and eficient query answering in description logics: The DL-Lite family, Journal of Automated Reasoning (JAR) 39 (2007) 385–429. [6] F. Baader, S. Brandt, C. Lutz, Pushing the ℰ ℒ envelope, in: Proceedings of the 19th international joint conference on Artificial intelligence (IJCAI), 2005, pp. 364–369. [7] D. Calvanese, E. Kharlamov, W. Nutt, C. Thorne, Aggregate queries over ontologies, in: Proceedings of the 2nd International Workshop on Ontologies and Information Systems for the Semantic Web (ONISW), 2008, pp. 97–104. [8] E. V. Kostylev, J. L. Reutter, Complexity of answering counting aggregate queries over
DL-Lite, Journal of Web Semantics (JWS) (2015) 94–111. [9] C. Feier, C. Lutz, M. Przybylko, Answer counting under guarded TGDs, in: Proceedings of the 24th International Conference on Database Theory (ICDT), 2021. [10] M. Bienvenu, Q. Manière, M. Thomazo, Answering counting queries over DL-Lite ontologies, in: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020, pp. 1608–1614. [11] D. Calvanese, J. Corman, D. Lanti, S. Razniewski, Counting query answers over a DL-Lite knowledge base, in: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020, pp. 1658–1666. [12] M. Bienvenu, Q. Manière, M. Thomazo, Cardinality queries over DL-Lite ontologies, in: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021, pp. 1801–1807. [13] C. Nikolaou, E. V. Kostylev, G. Konstantinidis, M. Kaminski, B. C. Grau, I. Horrocks, Foundations of ontology-based data access under bag semantics, Journal of Artificial Intelligence (AIJ) (2019) 91 – 132. [14] D. Calvanese, J. Corman, D. Lanti, S. Razniewski, Rewriting count queries over DL-Lite TBoxes with number restrictions, in: Proceedings of the 33rd International Workshop on Description Logics (DL), 2020. [15] M. Thomazo, J. Baget, M. Mugnier, S. Rudolph, A generic querying algorithm for greedy sets of existential rules, in: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2012. [16] S. Rudolph, M. Krötzsch, P. Hitzler, Type-elimination-based reasoning for the description logic ℋℐ using decision diagrams and disjunctive datalog, Logical Methods in Computer Science (LMCS) 8 (2012). [17] T. Eiter, C. Lutz, M. Ortiz, M. Simkus, Query answering in description logics: the knots approach, in: Proceedings of the 16th International Workshop on Logic, Language, Information and Computation (WoLLIC), 2009, pp. 26–36.