Abstract
While standard query answering in the DL-Lite family of ontologies is famously efficient, counting instances under the Open World Assumption presents a significant computational challenge. This paper maps the complexity landscape for "cardinality queries"—questions regarding the number of instances of a concept or relationship. We reveal that even minor additions to an ontology's logic can elevate the problem from highly tractable to computationally daunting, identifying the precise boundaries of efficiency across various DL-Lite dialects.
Introduction
In Ontology-Mediated Query Answering (OMQA), logical rules are used to query data that may be incomplete. For the popular DL-Lite family, answering Conjunctive Queries (CQs) is highly efficient. However, real-world data analysis often requires counting (e.g., "How many patients have this symptom?").
Under the Open World Assumption, a query does not return a single count; instead, we must determine the minimum and maximum possible counts across all valid models of the data. Previous research indicated that counting can be $coNP$-complete even for simple DL-Lite dialects. This work seeks to delineate the exact boundary where counting remains tractable and where it becomes intractable.
Methodology
The study focuses on Boolean atomic cardinality queries:
- Concept cardinality: $\exists z.A(z)$ (Counting instances in category A)
- Role cardinality: $\exists z_1, z_2.R(z_1, z_2)$ (Counting pairs related by R)
These are analyzed across three dialects of increasing expressivity:
- $DL-Lite_{core}$: The most basic version.
- $DL-Lite_{pos}^{\mathcal{H}}$: Adds role inclusions (sub-typing relationships).
- $DL-Lite_{core}^{\mathcal{H}}$: Adds disjointness constraints (e.g., "A person cannot be both a 'Buyer' and a 'Seller'").
Standard OMQA relies on a "canonical model," which often contains more individuals than necessary for counting purposes. To address this, the authors developed a "merging witnesses" approach, employing optimization strategies to find the minimum number of individuals required to satisfy the ontology without violating its rules.
Key Insights
- The Canonical Model Trap: For counting, the canonical model is often "too big." Minimum counts require solving optimization problems to collapse required objects where possible.
- Role Complexity: Counting concept instances is generally easier than counting roles. Role counting introduces dependencies that frequently lead to $coNP$-hardness.
- Graph Theory Links: A specific case in $DL-Lite_{pos}^{\mathcal{H}}$ was found to be logspace-equivalent to the complement of Perfect Matching (co-PM), linking ontology querying to a classic, long-standing problem in graph theory.
Key Results
The authors provide a complete classification of data complexity, showing how problem difficulty scales with database size. The results range from $TC^0$ (highly efficient/parallelizable) to $coNP$-complete (likely intractable for large datasets).
As shown in the figure above, $DL-Lite_{core}$ remains efficient for both query types. However, the introduction of role hierarchies and disjointness constraints introduces significant complexity, including cases that are $L$-complete (logarithmic space) or $coNP$-complete.
Conclusion and Future Work
The research identifies several open questions, particularly within the $DL-Lite_{core}^{\mathcal{H}}$ dialect, where some cases remain unclassified (marked with "?" in the results). Future work will focus on mapping these remaining gaps, developing practical approximation algorithms for $coNP$-hard cases, and extending these results to more complex counting queries beyond simple atomic structures.
Summary updated