=Paper=
{{Paper
|id=Vol-2954/abstract-6
|storemode=property
|title=Cardinality Queries over DL-Lite Ontologies (Extended abstract)
|pdfUrl=https://ceur-ws.org/Vol-2954/abstract-6.pdf
|volume=Vol-2954
|authors=Meghyn Bienvenu,Quentin Manière,Michaël Thomazo
|dblpUrl=https://dblp.org/rec/conf/dlog/BienvenuMT21a
}}
==Cardinality Queries over DL-Lite Ontologies (Extended abstract)==
https://ceur-ws.org/Vol-2954/abstract-6.pdf
Cardinality Queries over DL-Lite Ontologies
(Extended abstract) ? ??
Meghyn Bienvenu1[0000−0001−6229−8103] , Quentin Manière1[0000−0001−9618−8359] ,
and Michaël Thomazo2[0000−0002−1437−6389]
1
CNRS, University of Bordeaux, Bordeaux INP, LaBRI, Talence, France
2
Inria, DI ENS, ENS, CNRS, University PSL, Paris, France
Abstract. We summarize our recent work [5] on classifying the com-
plexity of answering cardinality queries over DL-Lite ontologies.
Keywords: Ontology-mediated query answering · Counting queries
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 different 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 infinite)
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 differ between models, [10] advocated a form of
certain answer semantics that considers lower and upper bounds on the count
value across different models. Their work provided the first 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: coNP-
complete in data complexity for the well-known DL-Litecore and DL-LiteH core
dialects. A recent work by [4] refined and generalized the complexity results from
?
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).
2 M. Bienvenu et al.
Concept cardinality query Role cardinality query
0
DL-Litecore TC -c TC0 -c
DL-LiteH
pos TC0 -c† TC0 -c | co-PM-c | coNP-c
DL-LiteH
core TC0 -c | L-c | coNP-c | ? TC0 -c | L-c | co-PM-c | coNP-c | ?
Table 1. Data complexity of cardinality queries based upon concept and role atoms for
various DL-Lite dialects. † : upper bound holds for all DL-LiteH
core ontologies without
negative role inclusions.
[10] to a wider class of counting queries and identified 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 first 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 ∃z.A(z) and
∃z1 , 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-LiteH core , 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 con-
cept atom, TC0 membership holds even for the fragment of DL-LiteH core obtained
by disallowing negative role inclusions. By contrast, for role cardinality queries,
we show that coNP-hard situations arise in DL-LiteH pos , which allows only posi-
tive concept and role inclusions. In fact, we obtain a complete data complexity
classification for DL-LiteH pos , showing that every ontology-mediated query is ei-
0
ther TC -complete, coNP-complete, or is in P and logspace-equivalent to the
complement of Perfect Matching (whose precise complexity is a longstand-
ing open problem). The preceding classification does not extend to DL-LiteH core :
we identify new sources of coNP-hardness and further exhibit L-complete cases.
We find it intriguing that such complex behaviour arises in what appears at first
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 find the optimal way of merging witnesses for existential axioms.
Cardinality Queries over DL-Lite Ontologies (Extended abstract) 3
References
1. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family
and relations. Journal of Artificial 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., Leclère, M., Mugnier, M., Salvat, E.: On rules with existential variables:
Walking the decidability line. Journal of Artificial Intelligence (JAR) 175(9-10),
1620–1654 (2011)
4. Bienvenu, M., Manière, Q., Thomazo, M.: Answering counting queries over DL-
Lite ontologies. In: Proc. of the 29th International Joint Conference on Artificial
Intelligence (IJCAI). pp. 1608–1614 (2020)
5. Bienvenu, M., Manière, Q., Thomazo, M.: Cardinality queries over DL-Lite ontolo-
gies. In: Proc. of the 30th International Joint Conference on Artificial 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
Artificial Intelligence (IJCAI). pp. 1658–1666 (2020)
9. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable
reasoning and efficient 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., Za-
kharyaschev, M.: Ontology-based data access: A survey. In: Proc. of the 27th
International Joint Conference on Artificial Intelligence (IJCAI). pp. 5511–5519
(2018)