This paper, presented at AAAI-25, explores a fundamental shift in how we think about counting queries in the context of Description Logic (DL) Knowledge Bases. Instead of asking for a single "certain" answer, the authors investigate the spectrum—the entire set of possible counts across all valid models of a knowledge base.
TL;DR
The researchers characterize the "shapes" of possible answer sets (spectra) for counting queries across various Description Logics. They demonstrate that while these sets can be complex, they often follow predictable patterns (like being closed under addition), and they establish the computational complexity of representing these spectra, ranging from polynomial time to $FP^{NP[\log]}$-completeness.
What Problem Does This Paper Address?
In Ontology-Mediated Query Answering (OMQA), we usually deal with "certain answers"—things that are true in every possible model of our data. However, for counting queries (e.g., "How many students are enrolled in this course?"), different models might yield different numbers.
Previous research often looked for "uniform bounds" (e.g., "there are at least 5 and at most $\infty$ students"). But these bounds are often too loose. For example, a knowledge base might imply that the number of students must be an even number or at least 10, but never 7. The spectrum of a query is the set of all such possible counts. The challenge is that this set could theoretically be any arbitrary collection of natural numbers, making it difficult to compute or represent efficiently.
Methods
The authors focus on Cardinality Queries (counting instances of concepts or roles) over the $\mathcal{ALCIF}$ family of Description Logics. Their approach involves:
- Algebraic Characterization: They prove that for "connected" and "individual-free" queries, the spectrum is a subsemigroup of $(\mathbb{N} \cup \{\infty\}, +)$. This means if $n$ and $m$ are possible answers, $n+m$ is also a possible answer.
- Effective Representation: Because these sets are ultimately periodic, they can be represented compactly as a triple $(S, M, \alpha)$, where $S$ is a finite set of "small" answers, $M$ is a threshold, and $\alpha$ defines a periodic pattern for numbers larger than $M$.
- Cycle-Reversion Techniques: To handle the Horn fragment of $\mathcal{ALCIF}$ (specifically $\mathcal{ELIF}_\perp$), they adapt "cycle-reversion" techniques. This involves analyzing the dependencies in the ontology to see if a concept can be "pumped" to create models with increasingly larger counts.
- Complexity Analysis: They analyze the "data complexity"-how hard it is to compute this representation as the size of the data (the ABox) grows.
Key Insights and Ideas
- The Shape of Infinity: In most standard DLs, if a count can be non-zero, it can usually be infinite ($\infty$). The spectrum is almost always a subsemigroup containing $\infty$.
- Logic Dictates Shape:
- In $\mathcal{ALCIF}$, spectra can have "gaps" and periodic behavior (e.g., $\{0, 2, 4, 6, \dots, \infty\}$).
- In simpler logics like $\mathcal{ALCI}$ or $\mathcal{ALCF}$, the spectrum is much simpler: it's always an interval of the form $[M, \infty]$ (possibly with $\{0\}$ added).
- The "Aha" Moment on Addition: The realization that spectra for connected queries are closed under addition is pivotal. It allows the authors to use the theory of numerical semigroups to guarantee that every spectrum has a finite, "effective" representation.
Key Results
The paper provides a complete characterization of which sets of numbers can actually be spectra for different DL fragments. The computational complexity of computing these spectra varies significantly based on the expressiveness of the logic used.
- Complexity Classes: For the most basic logic (DL-Lite$_{core}$), the spectrum can be computed in Polynomial Time (FP). For more expressive logics (like $\mathcal{ALC}$, $\mathcal{ELIF}_\perp$, or $\mathcal{ALCI}$), the task is $FP^{NP[\log]}$-complete. This means it's roughly as hard as finding the maximum size of a clique in a graph—it requires a logarithmic number of calls to an NP oracle.
- Role vs. Concept: Counting roles (relationships) is generally harder than counting concepts (classes). Even in simple logics like $\mathcal{EL}_\perp$, role cardinality queries can produce complex spectra with gaps, whereas concept queries remain simpler.
Limitations and Future Work
- Query Constraints: The most elegant results (closure under addition) require the query to be "connected" and "individual-free." If a query refers to specific named individuals (like "Alice"), the spectrum might not be a subsemigroup, making it harder to represent.
- Combined Complexity: The paper focuses on data complexity. The "combined complexity" (where the size of the ontology and the query also grow) remains an open area for deeper investigation.
- Bag Semantics: The authors note that while their work is related to "bag semantics" (where duplicates matter), the two are not identical, and bridging this gap is a suggested future direction.
Summary updated