Answering Counting Queries over DL-Lite Ontologies

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

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 unexplored. 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.

Introduction

In standard databases, counting is straightforward because the data is assumed to be complete (the Closed World Assumption). However, in Ontology-Mediated Query Answering (OMQA), we query incomplete data enriched by logical rules. This environment operates under the Open World Assumption: just because an entity is not explicitly in the database does not mean it does not exist.

For instance, if an ontology rule states "Every person has a mother," the system infers the existence of mothers even if they aren't named. This makes aggregate queries like counting incredibly difficult. Different valid interpretations (models) of the data might yield different exact counts, as anonymous individuals might be the same or different people across models. This paper formally defines a broader class of counting queries and maps their computational complexity.

Formalizing Counting Conjunctive Queries (CCQs)

The authors introduce Counting Conjunctive Queries (CCQs), which split variables into three types: answer variables, standard existential variables (used to check path existence), and counting variables (the entities being tallied).

To manage uncertainty, the semantics return an answer interval [m, M], representing the minimum and maximum possible counts across all valid models of the knowledge base. To analyze the complexity of finding these bounds, the authors utilize "interleaving"—a theoretical method of merging parts of an arbitrary model with a structured "canonical model." This allows them to prove that if a countermodel exists, a bounded-size countermodel must also exist, which is essential for establishing complexity limits.

Complexity Analysis and Key Results

The study reveals that counting is inherently difficult in the general case. Finding the lower bound of a count over DL-Lite ontologies is coNP-complete in data complexity. This difficulty arises because the system must consider all possible ways anonymous individuals might overlap or be distinct.

Complexity of answering general Counting Conjunctive Queries (CCQs).

Structural Restrictions

The authors investigated structural restrictions to identify more tractable sub-problems:

  • Rooted queries: Every variable must be connected to a known constant or answer variable. Surprisingly, rootedness alone does not reduce complexity; rooted CCQs remain coNP-complete.
  • Exhaustive queries: Every non-answer variable is treated as a counting variable.

The "Exhaustive Rooted" Sweet Spot

When a query is both rooted and exhaustive, the complexity drops significantly for DL-Lite$_{core}$ ontologies. The data complexity falls to TC$^0$-complete, meaning the problem can be solved efficiently using parallelizable circuits. However, for the more expressive DL-Lite$_{\mathcal{R}}$, data complexity remains coNP-complete.

Complexity of answering exhaustive rooted CCQs.

Limitations and Future Work

A major limitation in DL-Lite is that the upper bound of a count is almost always infinity, as the logic does not restrict how many anonymous individuals can exist. To address this, future work should explore Description Logics with functional roles or quantified number restrictions (e.g., "a person has exactly two parents"). Such restrictions would allow systems to infer meaningful upper bounds. Additionally, the authors highlight the need to expand this framework to other aggregate functions like MIN, MAX, SUM, and AVERAGE.

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