Answering Counting Queries over DL-Lite Ontologies (Extended Abstract)

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

Introduction

In traditional database systems, aggregate queries such as COUNT, SUM, or MAX are standard operations. However, in Ontology-Mediated Query Answering (OMQA), these operations become significantly more complex due to the open-world assumption (OWA). Under OWA, ontologies can infer the existence of anonymous individuals not explicitly named in the data. For instance, if an ontology specifies that every parent has at least three children, but the database lists none for a specific individual, the "certain answer" for a count would be 3, rather than 0. This paper explores the computational boundaries of answering such counting conjunctive queries (CCQs) over the DL-Lite family of description logics.

Problem Statement

The primary challenge in OMQA counting is determining the "certain lower bound"—the minimum count that holds true across all possible models (valid versions of the world) consistent with the data and the ontology. While previous research established foundational concepts for these "certain intervals," significant gaps remained regarding the complexity of queries involving multiple variables or specific structural constraints. This work specifically addresses these gaps for $DL-Lite_{core}$ and $DL-Lite_R$, which are foundational for efficient query answering.

Methodology

The authors introduce a generalized form of Counting Conjunctive Query (CCQ) that supports multiple aggregation variables. To identify tractable fragments, they investigate two structural restrictions:

  • Rooted Queries: Every variable in the query must be connected to an answer variable or a specific individual in the data.
  • Exhaustive Rooted Queries: A more restrictive subclass where every non-answer variable is a counting variable.

The study is purely theoretical, employing mathematical proofs to establish upper and lower complexity bounds (e.g., $NP$, $coNP$, $PP$, $TC^0$) across two dimensions: data complexity (scaling with the size of the data) and combined complexity (scaling with both data and query size).

Key Insights

The research highlights "rootedness" as a critical lever for managing computational complexity. By anchoring query variables to known entities, certain intractable problems become manageable. A standout finding is that for $DL-Lite_{core}$, the "exhaustive rooted" restriction reduces data complexity to $TC^0$. This is a remarkably low complexity class, suggesting that such queries can be processed extremely efficiently using parallel architectures. Furthermore, the authors analyze the complexity of identifying the most precise interval $[n, \infty)$, finding it to be $DP$-complete in terms of data complexity.

Results

The paper provides a comprehensive complexity map for various scenarios involving rooted and exhaustive rooted queries.

Complexity results for rooted and exhaustive rooted counting CQs.

As shown in the table above, data complexity for rooted queries is generally $coNP$-complete. However, under the exhaustive rooted restriction in $DL-Lite_{core}$, it simplifies to $TC^0$-complete. Combined complexity is significantly higher, ranging from $PP$-complete to $coN2EXP$, depending on the logic and query structure. For $DL-Lite_R$ with finite-depth ontologies (f.-d. TBox), the authors established an improved $coNEXP$ upper bound for combined complexity.

Conclusion and Future Work

This work maps the computational landscape of counting queries in DL-Lite, focusing on certain lower bounds. Because DL-Lite ontologies can recursively generate anonymous individuals, upper bounds are often infinite and thus less informative. Future research directions include extending this analysis to more expressive description logics, such as the $\mathcal{EL}$ family, and exploring other aggregate functions like SUM or AVG, which present even greater semantic and computational challenges in open-world environments.

Summary updated

BibTeX
@inproceedings{bienvenu2020answering,
  author = {Meghyn Bienvenu and Quentin Manière and Michaël Thomazo},
  title = {{Answering Counting Queries over DL-Lite Ontologies (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/223},
}
Figure