# Spectra of Cardinality Queries over Description Logic Knowledge Bases

arXiv: https://arxiv.org/abs/2412.12929 · HTML: https://mlsanity.com/paper/2412.12929/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 17 Dec 2024.

## Builds on (most cited first, 4 of 4)

- [Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints](https://mlsanity.com/paper/2002.06072/) (2020)
- [Counting Query Answers over a DL-Lite Knowledge Base (extended version)](https://mlsanity.com/paper/2005.05886/) (2020)
- [Answering Counting Queries over DL-Lite Ontologies](https://mlsanity.com/paper/2009.09801/) (2020)
- [Answer Counting under Guarded TGDs](https://mlsanity.com/paper/2101.03058/) (2021)

## Abstract (arXiv)

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 ∞, 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 mathbbN cup  ∞  closed under addition. For most sublogics of ALCIF, we show that possible spectra enjoy simpler shapes, being [ m, ∞ ] 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 mathsfFP^mathsfNP[log]-completeness of this task under several settings.