Spectra of Cardinality Queries over Description Logic Knowledge Bases
This work addresses a theoretical problem in knowledge representation and reasoning, providing incremental insights into query answering over ontologies.
The paper tackles the problem of computing and representing the spectra (sets of possible answers) of cardinality queries over Description Logic knowledge bases, identifying a class of queries with effectively representable spectra and showing that for most sublogics, spectra have simple shapes like intervals. It establishes the computational complexity of computing this representation as FP^NP[log]-complete.
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 $\infty$, 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 $\mathcal{ALCIF}$ ontologies: they are essentially the subsets of $\mathbb{N} \cup \{ \infty \}$ closed under addition. For most sublogics of $\mathcal{ALCIF}$, we show that possible spectra enjoy simpler shapes, being $[ m, \infty ]$ 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 $\mathcal{ALCIF}$. We also study the data complexity of computing the proposed effective representation and establish the $\mathsf{FP}^{\mathsf{NP}[\log]}$-completeness of this task under several settings.