Abstract
This paper investigates the computational complexity of cardinality queries—counting the number of instances of a concept or role—over ontologies formulated in the DL-Lite family of description logics. While traditional Ontology-Mediated Query Answering (OMQA) focuses on the existence of answers, cardinality queries seek the "certain answer," defined as the minimum count across all possible models. The authors establish a comprehensive complexity map, identifying tractable fragments in $TC^0$ and hard cases that are coNP-complete, while introducing a novel "merging strategy" to overcome the limitations of standard canonical models.
Introduction
In the paradigm of Ontology-Mediated Query Answering (OMQA), data is queried through the lens of an ontology that provides domain knowledge via logical rules. Most research in this field has focused on standard conjunctive queries, which ask whether a specific answer exists. However, practical data analysis often requires counting, such as determining the number of patients with a particular diagnosis or the number of students enrolled in a course.
Counting in the presence of an ontology is challenging due to the "open-world assumption": the data is typically incomplete, and many different models (possible worlds) may satisfy the ontology and the data. For cardinality queries, the goal is to find the certain answer, which is the minimum number of matches that must exist in every possible model. While general counting queries are known to be coNP-complete, this paper focuses on atomic cardinality queries—counting instances of a single concept or role—to determine if they offer better computational properties.
The Canonical Model and Merging Strategies
A cornerstone of DL-Lite reasoning is the canonical model, a single representative model that provides the correct answers for standard queries. A key insight of this paper is that the canonical model is insufficient for cardinality queries. Because it is "maximally expanded" to satisfy existential axioms, it may contain more individuals than are strictly necessary, leading to an overestimation of the minimum count.
To find the true minimum count, the authors developed a framework based on merging strategies. This approach involves identifying ways to "merge" anonymous individuals—those required by the ontology's rules—with existing data constants or with each other. By treating the problem as an optimization task to minimize the query predicate's count, the authors can determine the certain answer.
Complexity Map and Key Results
The authors provide a complete classification of the data complexity for cardinality queries across several DL-Lite dialects. The results reveal a significant asymmetry between counting concepts ("things") and counting roles ("links").
Key Findings:
- Tractability in $DL-Lite_{core}$: For the basic dialect, cardinality queries for both concepts and roles are in $TC^0$. This is the "gold standard" for database efficiency, as $TC^0$ problems are highly parallelizable and can be solved efficiently even on very large datasets.
- Concept vs. Role Asymmetry: In the $DL-Lite^H_{pos}$ dialect, concept counting remains in $TC^0$, but role counting exhibits a trichotomy of complexity: $TC^0$, co-PM-complete (related to the complement of the Perfect Matching problem), or coNP-complete.
- The Impact of Negative Axioms: The addition of negative constraints (e.g., disjointness in $DL-Lite^H_{core}$) introduces new bottlenecks, potentially driving the complexity of concept queries up to coNP-complete.
- Intermediate Complexity: The connection to the Perfect Matching problem is particularly noteworthy, as it represents a rare case of "intermediate" complexity that is not yet known to be in P or coNP-complete.
Conclusion and Future Directions
This research provides a rigorous theoretical foundation for counting in DL-Lite ontologies. By moving beyond the canonical model and introducing merging strategies, the authors have mapped the boundaries of tractability for cardinality queries.
Future work includes extending these techniques to more complex query shapes beyond atomic concepts and roles. Additionally, while the $TC^0$ results are theoretically promising, translating these merging strategies into practical, SQL-based query rewriting algorithms remains an important step for real-world implementation in database systems.
Summary updated