Complexity Landscape for Counting Queries (Extended Abstract)

Meghyn Bienvenu, Quentin Manière, Michaël ThomazoDescription Logics 2022 · OpenReview

Introduction

In the field of Ontology-Mediated Query Answering (OMQA), ontologies provide a formal framework to query databases using domain knowledge. While standard conjunctive queries are well-understood, counting conjunctive queries (CCQs)—such as "How many employees work in Sales?"—present significant computational challenges. The primary difficulty stems from the "open-world assumption" inherent in ontologies: because information is incomplete, there isn't a single definitive count, but rather a range of possible counts across all valid models. Researchers typically focus on determining the minimum and maximum possible counts.

This research, presented at the 35th International Workshop on Description Logics (DL 2022), maps the complexity of CCQs across various Horn description logics. It extends previous work from the simple DL-Lite family into more expressive logics like $\mathcal{EL}$, which allows for conjunctions (e.g., an object belonging to both category A and category B).

Methodology: Finding the Minimum Count

To determine the complexity of these queries, the authors developed a novel approach to identify the "minimum count" model. Their methodology rests on three pillars:

  1. The Central Component ($\mathcal{I}^*$): The authors proved that for any knowledge base, there exists a model that minimizes the count value. This model consists of a "central" arbitrary structure containing all assignments for counting variables, surrounded by "tree-shaped" structures. Crucially, they established that the size of this central component can be mathematically bounded.
  2. Local Consistency and Type-Elimination: To verify if a candidate central component can be extended into a valid global model, the researchers employed "patterns" (pairs of adjacent elements) and local consistency checks. This technique mirrors "type-elimination" procedures used in logic to prune impossible configurations.
  3. Closed Predicate Reduction: To establish lower bounds (the minimum difficulty of the problem), the authors linked counting queries to OMQA with "closed predicates"—scenarios where certain categories are assumed to be complete.

Complexity Results

The study provides a definitive map of complexity classes for different logics and query types. A major contribution is "closing the gap" for certain DL-Lite dialects, such as DL-Lite$^\mathcal{H}_{core}$, which was previously unknown but is now proven to be 2EXP-complete.

Table 1: Complexity of counting queries across various Horn description logics.

Key findings from the complexity analysis include:

  • CCQ Answering: Established as 2EXP-complete for $\mathcal{EL}$ and its extensions. This indicates that these queries are extremely difficult to solve in the worst-case scenario.
  • Cardinality Queries: Simpler queries (counting members of a single category) range from NL (very easy) to coNEXP (very hard) depending on the logic's expressivity.
  • Data Complexity: Despite high "combined complexity" (query + ontology + data), the "data complexity" (scaling with database size) remains coNP-complete for all studied $\mathcal{EL}$ logics.

Discussion and Future Directions

The transition from DL-Lite to $\mathcal{EL}$ significantly changes the computational landscape. Because $\mathcal{EL}$ allows for complex intersections of categories, the techniques used for simpler logics are insufficient, necessitating the "central component" approach.

While 2EXP-completeness is theoretically daunting, the authors suggest several paths forward:

  • Practical Algorithms: There is a pressing need for algorithms that perform well on real-world data despite worst-case theoretical bounds. The coNP data complexity results suggest that SAT solvers could be effectively employed for implementation.
  • Tractability Search: In simpler logics, "rooted" queries are easier to solve. However, this study found that such restrictions do not necessarily simplify the $\mathcal{EL}$ family. Identifying new, "natural" restrictions that lead to polynomial-time (PTime) solutions remains a primary goal for future research.

As a theoretical study, these results are based on mathematical proofs regarding complexity classes (NP, EXP, 2EXP) rather than empirical datasets. They provide the foundational "complexity map" necessary for building the next generation of ontology-mediated query systems.

Summary updated

BibTeX
@inproceedings{bienvenu2022complexity,
  author = {Meghyn Bienvenu and Quentin Manière and Michaël Thomazo},
  title = {{Complexity Landscape for Counting Queries (Extended Abstract)}},
  booktitle = {Description Logics},
  year = {2022},
  url = {https://openreview.net/forum?id=0zawtZOxwE},
}
Figure