Cardinality Queries over DL-Lite Ontologies

Meghyn Bienvenu, Quentin Manière, Michaël Thomazo

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.

Comparison of the canonical model (a) with alternative models and strategies (b, c) for cardinality queries.

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").

Comprehensive complexity map for concept and role cardinality queries across DL-Lite dialects.

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

Abstract

Ontology-mediated query answering (OMQA) employs structured knowledge and automated reasoning in order to facilitate access to incomplete and possibly heterogeneous data. While most research on OMQA adopts (unions of) conjunctive queries as the query language, there has been recent interest in handling queries that involve counting. In this paper, we advance this line of research by investigating cardinality queries (which correspond to Boolean atomic counting queries) coupled with DL-Lite ontologies. Despite its apparent simplicity, we show that such an OMQA setting gives rise to rich and complex behaviour. While we prove that cardinality query answering is tractable (TC0) in data complexity when the ontology is formulated in DL-Lite-core, the problem becomes coNP-hard as soon as role inclusions are allowed. For DL-Lite-pos-H (which allows only positive axioms), we establish a P-coNP dichotomy and pinpoint the TC0 cases; for DL-Lite-core-H (allowing also negative axioms), we identify new sources of coNP complexity and also exhibit L-complete cases. Interestingly, and in contrast to related tractability results, we observe that the canonical model may not give the optimal count value in the tractable cases, which led us to develop an entirely new approach based upon exploring a space of strategies to determine the minimum possible number of query matches.
BibTeX
@inproceedings{bienvenu2021cardinality,
  author = {Meghyn Bienvenu and Quentin Manière and Michaël Thomazo},
  title = {{Cardinality Queries over DL-Lite Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/248},
}
Figure