Skip to Main content Skip to Navigation
New interface
Conference papers

Cardinality Queries over DL-Lite Ontologies

Meghyn Bienvenu 1 Quentin Manière 1 Michaël Thomazo 2 
2 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : Ontology-mediated query answering (OMQA) employs structured knowledge and automated reasoning in order to facilitate access to incomplete and possibly heterogeneous data. While most research on OMQA adopts (unions of) conjunctive queries as the query language, there has been recent interest in handling queries that involve counting. In this paper, we advance this line of research by investigating cardinality queries (which correspond to Boolean atomic counting queries) coupled with DL-Lite ontologies. Despite its apparent simplicity, we show that such an OMQA setting gives rise to rich and complex behaviour. While we prove that cardinality query answering is tractable (TC 0) in data complexity when the ontology is formulated in DL-Lite core , the problem becomes coNP-hard as soon as role inclusions are allowed. For DL-Lite H pos (which allows only positive axioms), we establish a P-coNP dichotomy and pinpoint the TC 0 cases; for DL-Lite H core (allowing also negative axioms), we identify new sources of coNP complexity and also exhibit L-complete cases. Interestingly, and in contrast to related tractability results, we observe that the canonical model may not give the optimal count value in the tractable cases, which led us to develop an entirely new approach based upon exploring a space of strategies to determine the minimum possible number of query matches.
Complete list of metadata
Contributor : Michaël Thomazo Connect in order to contact the contributor
Submitted on : Wednesday, October 27, 2021 - 1:58:53 PM
Last modification on : Wednesday, June 15, 2022 - 3:25:24 AM
Long-term archiving on: : Friday, January 28, 2022 - 7:01:01 PM


Files produced by the author(s)


  • HAL Id : hal-03405769, version 1



Meghyn Bienvenu, Quentin Manière, Michaël Thomazo. Cardinality Queries over DL-Lite Ontologies. IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Aug 2021, Montreal, Canada. ⟨hal-03405769⟩



Record views


Files downloads