Cardinality Queries over DL-Lite Ontologies (Extended abstract) ? ??

Abstract

We summarize our recent work [5] on classifying the complexity of answering cardinality queries over DL-Lite ontologies. A major topic in ontology-mediated query answering (OMQA) research has been to understand the complexity of OMQA and identify tractable settings [11,6,12]. Nowadays, for the most commonly considered query language, namely, conjunctive queries (CQs), we have an almost complete picture of the complexity landscape for ontologies formulated in a wide range of di erent description logics (DLs) [2] and rule-based languages [3,7]. In particular, it has been shown that CQ answering is tractable in data complexity for ontologies expressed in the most commonly considered dialects of the DL-Lite family [9,1], which are often employed in OMQA. A crucial property of such DL-Lite dialects and other Horn DLs is that they admit a canonical model, which is a single (possibly in nite) model that, by virtue of being homomorphically embeddable into every model, is guaranteed to give the correct answers to all CQs. While CQs are a natural and well-studied class of queries, there are many other relevant forms of database queries that could be potentially be employed in OMQA. In the present work, our focus will be on counting queries, which together with other forms of aggregate queries, are widely used for data analysis, yet still not well understood in the context of OMQA. A natural way to equip CQs with counting is to count the number of distinct query matches for each answer. As the count value may di er between models, [10] advocated a form of certain answer semantics that considers lower and upper bounds on the count value across di erent models. Their work provided the rst investigation of the complexity of answering counting CQs in the presence of ontologies, revealing such queries to be much more challenging to handle than plain CQs: coNPcomplete in data complexity for the well-known DL-Litecore and DL-LitecHore dialects. A recent work by [4] re ned and generalized the complexity results from

Keywords

• Ontology-mediated query answering
• Counting queries

-

? Partially supported by ANR project CQFD (ANR-18-CE23-0003) ?? © 2021 for this paper by its authors. Use permitted under Creative Commons

License Attribution 4.0 International (CC BY 4.0).

M. Bienvenu et al.

Concept cardinality query

Role cardinality query DL-Litecore

DL-LitepHos

DL-LitecHore

TC0-c TC0-cy TC0-c

TC0-c j co-PM-c j coNP-c

TC0-c j L-c j coNP-c j ?

TC0-c j L-c j co-PM-c j coNP-c j ?

[ 10 ] to a wider class of counting queries and identi ed a restricted scenario with very low (TC0-complete) data complexity: rooted CQs coupled with DL-Litecore ontologies. A similar tractability result for connected rooted CQs was proven independently by [ 8 ], who also initiated a study of the impact of other restrictions on query shape and developed the rst query rewriting procedure for counting CQs. Notably, both the aforementioned TC0 result and the rewriting procedure crucially relied upon showing that the canonical model gives the right answers under the considered restrictions.

While recent studies have improved our understanding of the complexity of counting CQs, there nevertheless remain many unanswered questions. In this work, we focus on Boolean atomic counting queries of the form 9z:A(z) and 9z1; z2:R(z1; z2), which we term cardinality queries as they correspond to the natural task of determining (bounds on) the cardinality of a given concept or role name. The data complexity of answering such basic counting queries remains completely open for DL-Litecore ontologies, whilst for DL-LitecHore, the problem is known to be P-hard and in coNP [ 8 ]. The main results of our investigation are displayed in Table 1. We show that when ontologies are expressed in DL-Litecore, cardinality query answering is tractable in data complexity and enjoys the lowest possible complexity (TC0-complete). For cardinality queries based upon a concept atom, TC0 membership holds even for the fragment of DL-LitecHore obtained by disallowing negative role inclusions. By contrast, for role cardinality queries, we show that coNP-hard situations arise in DL-LitepHos, which allows only positive concept and role inclusions. In fact, we obtain a complete data complexity classi cation for DL-LitepHos, showing that every ontology-mediated query is either TC0-complete, coNP-complete, or is in P and logspace-equivalent to the complement of Perfect Matching (whose precise complexity is a longstanding open problem). The preceding classi cation does not extend to DL-LitecHore: we identify new sources of coNP-hardness and further exhibit L-complete cases. We nd it intriguing that such complex behaviour arises in what appears at rst glance to be a simple OMQA setting. Moreover, in all of the tractable cases we identify, the canonical model may not yield the minimum cardinality, and query answering involves solving non-trivial optimization problems. This led us to devise an entirely new approach based upon exploring a space of strategies to nd the optimal way of merging witnesses for existential axioms.

Cardinality Queries over DL-Lite Ontologies (Extended abstract)

References

1. Artale , A. , Calvanese , D. , Kontchakov , R. , Zakharyaschev , M.: The DL-Lite family and relations . Journal of Arti cial Intelligence Research (JAIR) 36 , 1 { 69 ( 2009 )

2. Baader , F. , Horrocks , I. , Lutz , C. , Sattler , U. : An Introduction to Description Logic . Cambridge University Press ( 2017 )

3. Baget , J. , Leclere , M. , Mugnier , M. , Salvat , E.: On rules with existential variables: Walking the decidability line . Journal of Arti cial Intelligence (JAR) 175(9-10) , 1620 { 1654 ( 2011 )

4. Bienvenu , M. , Maniere , Q. , Thomazo , M. : Answering counting queries over DLLite ontologies . In: Proc. of the 29th International Joint Conference on Arti cial Intelligence (IJCAI) . pp. 1608 { 1614 ( 2020 )

5. Bienvenu , M. , Maniere , Q. , Thomazo , M. : Cardinality queries over DL-Lite ontologies . In: Proc. of the 30th International Joint Conference on Arti cial Intelligence (IJCAI) . pp. 1801 { 1807 ( 2021 )

6. Bienvenu , M. , Ortiz , M. : Ontology-mediated query answering with data-tractable description logics . In: Tutorial Lectures of the 11th Reasoning Web International Summer School . pp. 218 { 307 ( 2015 )

7. Cal , A. , Gottlob , G. , Lukasiewicz , T. : A general datalog-based framework for tractable query answering over ontologies . Journal of Web Semantics (JWS) 14 , 57 { 83 ( 2012 )

8. Calvanese , D. , Corman , J. , Lanti , D. , Razniewski , S. : Counting query answers over a DL-Lite knowledge base . In: Proc. of the 29th International Joint Conference on Arti cial Intelligence (IJCAI) . pp. 1658 { 1666 ( 2020 )

9. Calvanese , D. , Giacomo , G.D. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and e cient query answering in description logics: The DL-Lite family . Journal of Automated Reasoning (JAR) 39(3) , 385 { 429 ( 2007 )

10. Kostylev , E.V. , Reutter , J.L. : Complexity of answering counting aggregate queries over DL-Lite . Journal of Web Semantics (JWS) 33 , 94 { 111 ( 2015 )

11. Poggi , A. , Lembo , D. , Calvanese , D. , De Giacomo , G. , Lenzerini , M. , Rosati , R.: Linking data to ontologies . Journal of Data Semantics 10 , 133 { 173 ( 2008 )

12. Xiao , G. , Calvanese , D. , Kontchakov , R. , Lembo , D. , Poggi , A. , Rosati , R. , Zakharyaschev , M. : Ontology-based data access: A survey . In: Proc. of the 27th International Joint Conference on Arti cial Intelligence (IJCAI) . pp. 5511 { 5519 ( 2018 )