Spectra of Cardinality Queries over Description Logic Knowledge Bases
Quentin Manière, Marcin Przybyłko
Abstract
Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or infinity, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over ALCIF ontologies: they are essentially the subsets of N and infinity closed under addition. For most sublogics of ALCIF, we show that possible spectra enjoy simpler shapes, being [ m, infinity ] or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of ALCIF. We also study the data complexity of computing the proposed effective representation and establish the FP^NP[log]-completeness of this task under several settings.
BibTeX
@article{Manière_Przybyłko_2025, title={Spectra of Cardinality Queries over Description Logic Knowledge Bases}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33652}, DOI={10.1609/aaai.v39i14.33652}, abstractNote={Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or infinity, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over ALCIF ontologies: they are essentially the subsets of N and infinity closed under addition. For most sublogics of ALCIF, we show that possible spectra enjoy simpler shapes, being [ m, infinity ] or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of ALCIF. We also study the data complexity of computing the proposed effective representation and establish the FP^NP[log]-completeness of this task under several settings.}, number={14}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Manière, Quentin and Przybyłko, Marcin}, year={2025}, month={Apr.}, pages={15067-15074} }