Spectra of Cardinality Queries over Description Logic Knowledge Bases

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.