Abstract: Ontology-Mediated Query Answering (OMQA) bridges the gap between raw data and conceptual knowledge. While standard conjunctive queries focus on existence, real-world applications frequently demand counting capabilities. This paper formalizes counting conjunctive queries (CCQs) over DL-Lite ontologies, addressing the challenge of "anonymous" individuals—entities inferred by logical axioms but absent from the database. The authors provide a detailed complexity landscape and identify "rootedness" as a key structural property that enables highly efficient query answering.
Introduction: The Challenge of Counting in OMQA
In OMQA, an ontology provides a high-level schema that can imply the existence of individuals not explicitly named in the data. For instance, an ontology stating "every person has two parents" implies two individuals for every person in the database. Standard counting in databases fails here because it ignores these logically implied entities. This paper addresses the need for a semantics that accounts for these anonymous individuals while remaining computationally feasible.
Methodology: A Generalized Framework
The authors introduce a generalized CCQ formalism that distinguishes between answer variables, existential variables, and counting variables. To handle the potential for infinite models, they focus on identifying the "certain" lower and upper bounds for counts.
A key technical contribution is the "model interleaving" technique. By merging arbitrary countermodels with canonical models, the authors demonstrate that countermodels of bounded size exist, allowing them to establish upper complexity bounds in classes like coNEXP. They also investigate structural restrictions, specifically "rooted" queries, to see if common real-world constraints improve performance.
The Complexity Landscape
The research maps out the computational cost of CCQs across different members of the DL-Lite family. Generally, data complexity is coNP-complete for both DL-Lite$_{core}$ and DL-Lite$_{\mathcal{R}}$, while combined complexity can reach coN2EXP for the more expressive fragments.
The Power of Rootedness
A significant finding is the impact of "rooted" queries. A query is rooted if every variable in the query graph is connected to a known individual or an answer variable. For "exhaustive" rooted queries—those that count all possible matches—the complexity drops dramatically. In DL-Lite$_{core}$, these queries achieve $TC^0$-completeness in data complexity, making them suitable for highly parallel processing and efficient implementation in practice.
Key Insights
- Counting Variables: Surprisingly, allowing multiple counting variables does not necessarily increase complexity beyond the single-variable case.
- Optimal Bounds: Identifying the "best" lower bound (the highest number that is a valid lower bound) is DP-complete, which is harder than simple verification.
- Finite-Depth Ontologies: Restricting ontologies to finite depth (where chains of inferred individuals are bounded) reduces combined complexity from potentially double-exponential to single-exponential (coNEXP).
Conclusion and Future Work
This work provides a solid theoretical foundation for counting in OMQA by resolving previously open questions regarding complexity and semantics. Future research will explore more expressive logics, such as those with functional roles or full number restrictions, and extend the framework to other aggregate functions like SUM, AVG, MIN, and MAX.
Summary updated