Answering Counting Queries over DL-Lite Ontologies

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

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.

General complexity landscape for CCQs in DL-Lite, showing data and combined complexity bounds.

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.

Complexity for exhaustive rooted CCQs, highlighting the efficiency gains from structural restrictions in DL-Lite_core.

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

Abstract

Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unex-plored. In this paper, we introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries in the presence of DL-Lite ontologies. As it follows from existing work that query answering is intractable and often of high complexity, we consider some practically relevant restrictions, for which we establish improved complexity bounds.
BibTeX
@inproceedings{bienvenu2020answering,
  author = {Meghyn Bienvenu and Quentin Manière and Michaël Thomazo},
  title = {{Answering Counting Queries over DL-Lite Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/223},
}
Figure