Computing Concept Referring Expressions for Queries on Horn ALC Ontologies

Moritz Illich, Birte GlimmIJCAI 2022 · DOI

TL;DR

This paper introduces a novel algorithm for generating "concept referring expressions" (CREs) in Description Logics (DLs). These CREs describe implicitly defined individuals by relating them to explicitly named ones, going beyond traditional instance queries. The approach leverages existing OWL reasoners as black boxes and introduces a "uniqueness" criterion for CREs, achieving efficient computation for large ontologies.

What Problem Does This Paper Address?

Traditional knowledge base queries typically return explicit individual names. However, many individuals are implicitly defined through relationships within the knowledge base. For example, if we know "John is a person" and "every person has a mother who is a person," a query for "Person" would return "John," but not his mother. Concept Referring Expressions (CREs) aim to address this by providing descriptions that identify these anonymous individuals. Existing methods for computing CREs often struggle with efficient integration into modern DL reasoners or lack robust handling of uniqueness and singularity. This paper tackles the challenge of efficiently computing CREs that are not only certain and singular but also unique, ensuring that each distinct anonymous individual is represented by exactly one CRE.

Methods

The core of this paper is a novel algorithm for computing CREs for generalized instance queries on Horn ALC ontologies. The algorithm operates by treating existing OWL reasoners as black boxes, meaning it doesn't need to know the internal workings of the reasoner, only its standard query capabilities.

The algorithm proceeds in several key steps:

  1. Initialization: For each explicitly named individual in the knowledge base, an initial CRE is formed, and a "current concept" representing the individual's most specific known properties is established.
  2. Constructing CREs: This is the main recursive part of the algorithm. It iteratively builds CREs by:
  3. Finding suitable existential restrictions: Identifying relationships (existential restrictions) that connect the current concept to another. Crucially, it uses a "reduced existential restriction" definition to ensure singularity. This means if multiple existential restrictions involving the same role exist, only those that don't lead to redundant descriptions are considered.
  4. Incorporating universal restrictions: Adding universal restrictions to further specify the individuals reached through existential restrictions.
  5. Filtering for uniqueness and avoiding cycles: A significant contribution is the explicit handling of uniqueness, preventing duplicate CREs that describe the same individual. It also implements a cycle detection mechanism, similar to tableau algorithms, to ensure termination when dealing with cyclic ontologies by compactly representing repeated patterns.
  6. Checking for Answers: At each step, the algorithm checks if the current CRE represents a valid answer to the query. This is done by verifying if the current concept is subsumed by the query concept.
  7. Recursive Extension: If the current CRE is not yet an answer, or even if it is, the algorithm recursively extends it to explore further possibilities.

Datasets

The paper evaluates its algorithm on several existing ontologies: codinteraction-A, ore_ont_2608, ore_ont_4516, ore_ont_3313, HAO, VO, and DTO. These ontologies were adapted to conform to Horn ALC and merged with their imports to create complete knowledge bases for testing. No new benchmarks were introduced.

Key Insights and Ideas

  • Leveraging OWL Reasoners as Black Boxes: This is a significant practical advantage, allowing the algorithm to be used with any compliant OWL reasoner without needing to reimplement complex reasoning logic.
  • The "Uniqueness" Criterion: Beyond certainty and singularity, the paper introduces a crucial criterion of uniqueness for CREs. This ensures that each distinct anonymous individual is represented by exactly one CRE, avoiding redundancy and improving the clarity of query results.
  • Reduced Existential Restrictions: The definition of "reduced existential restrictions" is key to ensuring singularity. By carefully selecting existential restrictions, the algorithm avoids generating CREs that could describe multiple individuals.
  • Cycle Detection for Termination: The algorithm's ability to handle cyclic ontologies and guarantee termination through cycle detection is vital for practical applications, as it prevents infinite loops and ensures a finite output.
  • Efficiency for Large Ontologies: The algorithm demonstrates impressive performance, computing CREs for the most general concept (T) in under a minute for ontologies with thousands of individuals and concepts.

Key Results

The paper's prototypical implementation shows that the algorithm can efficiently compute CREs for large ontologies. For instance, computing CREs for the top-level concept (T) on ontologies with thousands of individuals and concepts takes less than a minute. The evaluation highlights that the performance is influenced by the complexity of subsumption checking, with different reasoners (HermiT and JFact) showing varying strengths on different ontologies. The paper also demonstrates that for certain ontologies with many existential restrictions but few individuals, not computing subsumption hierarchies can lead to faster runtimes.

Limitations and Future Work

  • Reasoning Engine Choice: The paper acknowledges that the choice of OWL reasoner significantly impacts performance and suggests further investigation into which reasoner is optimal for different ontologies.
  • Integration with Reasoners: The authors propose that directly integrating the algorithm into a reasoner could offer further optimization by leveraging internal data structures.
  • Extensions to Horn ALC: Future work includes extending the algorithm to handle Description Logics beyond Horn ALC. This is a significant challenge, as extensions might invalidate the tree-like universal model property, which is fundamental to the current singularity definition, and may require re-examination of the algorithm's core principles.

Summary updated

BibTeX
@inproceedings{illich2022computing,
  author = {Moritz Illich and Birte Glimm},
  title = {{Computing Concept Referring Expressions for Queries on Horn ALC Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/370},
}

Loading related content...

Figure