Answering Counting Aggregate Queries over Ontologies of the DL-Lite Family

Egor V. Kostylev, Juan L. ReutterAAAI 2013 · DOI

Abstract

In the realm of the Semantic Web, the Open World Assumption (OWA) presents a significant challenge for aggregate functions like counting. This paper, originally presented at AAAI 2013, establishes a formal framework for answering counting queries over ontologies within the DL-Lite family. By defining "certain answers" for aggregates as the minimum possible count across all valid models, the authors provide a mathematically robust semantics that respects the OWA. The study includes a comprehensive complexity analysis, demonstrating that while counting aggregates increase the computational burden compared to standard conjunctive queries, the problems remain decidable.

Introduction

The Semantic Web relies on description logics (DLs) to represent knowledge, with the DL-Lite family being particularly prominent due to its efficiency in query answering. However, traditional query answering focuses on retrieving individuals. When it comes to statistical or aggregate information—such as "how many children does Ann have?"—standard semantics often fall short. This paper by Egor V. Kostylev and Juan L. Reutter addresses this gap by formalizing counting aggregates under the Open World Assumption.

The Problem: Counting in an Open World

In traditional relational databases, the Closed World Assumption (CWA) implies that any fact not explicitly stored is false. Counting is a straightforward operation of tallying rows. In contrast, ontologies operate under the Open World Assumption (OWA). If a knowledge base states that "Ann is a parent" and the ontology includes the axiom "every parent has at least one child," we can infer that Ann has at least one child, even if no specific child is named in the data.

Standard "certain answer" semantics, which typically involve the intersection of answers across all possible models, fail for counting. If one model suggests Ann has one child and another suggests she has two, the intersection of the sets {1} and {2} is empty. Previous "epistemic" approaches only counted individuals explicitly named in the database, which would incorrectly return a count of zero for Ann. The authors propose a shift: treating the certain answer as the minimum possible count that holds in every valid model.

Methodology: Aggregate Certain Answers

The authors introduce the concept of Aggregate Certain Answers. Under this framework, a number $n$ is considered a certain answer to a counting query if the count is at least $n$ in every possible model of the knowledge base. This effectively provides a lower bound on the count, which is the most meaningful information available in an open-world setting.

The analysis focuses on two key members of the DL-Lite family:

  1. $DL-Lite_{core}$: The foundational logic of the family, supporting basic class inclusions.
  2. $DL-Lite_R$: An extension that allows for role inclusions (e.g., "if $x$ is a father of $y$, then $x$ is a parent of $y$"), which is the basis for the OWL 2 QL profile.

Complexity Analysis

The researchers mapped the computational difficulty of these queries using two metrics: Data Complexity (scaling with the amount of data) and Combined Complexity (scaling with both data and the complexity of the query/ontology).

Standard Conjunctive Queries (CQs) in DL-Lite are known for their low data complexity (in $AC^0$), allowing them to be rewritten as SQL queries and executed efficiently over relational databases. However, the introduction of counting aggregates causes a significant jump in complexity.

Key Results

The paper's primary contribution is a definitive complexity map for counting in DL-Lite.

Complexity results for counting queries in DL-Lite variants.

As shown in the table above, data complexity for both $DL-Lite_{core}$ and $DL-Lite_R$ moves to coNP-complete. This indicates that while the problem is harder than standard retrieval, it remains within a manageable class of intractability.

The combined complexity results are more varied. For $DL-Lite_{core}$, the complexity of COUNT queries is in coNExpTime, while COUNT DISTINCT (Cntd) queries are $\Pi^p_2$-complete. In the more expressive $DL-Lite_R$, both types of queries reach coNExpTime-complete. This explosion in complexity highlights the impact of role inclusions on aggregate reasoning.

Discussion and Limitations

The "minimum" approach is highly effective for COUNT because the maximum count in an open world is often infinite. However, the authors note that this logic does not extend naturally to other aggregates like AVERAGE or SUM. In those cases, the minimum value across infinite models might be $-\infty$, rendering the "certain answer" meaningless without further constraints.

Furthermore, the coNP-complete data complexity suggests that these queries cannot be directly translated into simple SQL SELECT COUNT(*) statements. Practical implementation will require specialized algorithms or heuristic-based approximations to handle the inherent complexity of reasoning over multiple models.

Conclusion

Kostylev and Reutter's work provides a solid theoretical foundation for counting in the Semantic Web. By defining aggregate certain answers as lower bounds, they bridge the gap between the Open World Assumption and the practical need for statistical data. While the complexity results pose challenges for implementation, they provide a clear roadmap for future research into optimizing aggregate query answering in description logics.

Summary updated

BibTeX
@inproceedings{kostylev2013answering,
  author = {Egor V. Kostylev and Juan L. Reutter},
  title = {{Answering Counting Aggregate Queries over Ontologies of the DL-Lite Family}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8646},
}
Figure