Efficient Computation of General Modules for ALC Ontologies

Hui Yang, Patrick Koopmann, Yue Ma, Nicole BidoitIJCAI 2023 · DOI

TL;DR

This paper introduces a novel method for efficiently computing "general modules" for ALC ontologies, which are smaller, more concise representations that preserve key logical entailments. Their approach significantly outperforms existing methods in terms of speed and output size, making ontology reuse and analysis more practical.

What Problem Does This Paper Address?

Ontologies, used to formalize knowledge in fields like medicine and the Semantic Web, can become massive and complex. This makes them difficult to work with for tasks like reusing parts of an ontology for a specialized application or analyzing specific aspects of the knowledge. To address this, researchers have developed methods to extract "modules" – smaller subsets of an ontology that preserve certain entailments.

Classical approaches include "deductive modules" (syntactic subsets of the original ontology) and "uniform interpolants" (which use only terms from a specified signature but aren't necessarily subsets). However, existing methods for expressive description logics like ALC are often slow, produce large or complex outputs, or are undecidable. This paper tackles the challenge of creating efficient and concise modules for ALC ontologies, specifically focusing on "general modules" which offer more flexibility than classical approaches by allowing the introduction of new terms (definers) during computation, leading to potentially smaller and simpler results.

Methods

The authors propose a new method for computing general modules for ALC ontologies, building upon the concept of uniform interpolation. The core of their approach involves:

  • Ontology Normalization: The input ontology is first transformed into a "normal form" by introducing fresh names (definers) for complex sub-expressions. This simplifies the structure for subsequent processing.
  • Role Isolation: A key innovation is a technique called "role isolation." This process separates axioms based on whether they involve roles outside the target signature. This allows for more efficient handling of role-related reasoning.
  • Role Forgetting: Axioms involving roles not present in the target signature are systematically removed or transformed.
  • Concept Forgetting: Similarly, concepts not in the target signature are removed.
  • Definer Elimination: The introduced definers are then eliminated. This is done in two main steps:
  • Conjunction of Definers Elimination (Op1): This rule handles disjunctions of negative definers.
  • Single Definer Elimination (Op2): This rule removes definers that don't appear in specific axiom forms.
  • Optimization: The authors further refine the process by deleting subsumed axioms and simplifying existing ones.

This method is designed to be more efficient than existing uniform interpolation techniques, particularly by avoiding the triple exponential blow-up associated with some approaches.

Datasets

The paper evaluates their method on a corpus of 222 ontologies derived from the OWL Reasoner Evaluation (ORE) 2015 classification track. Axioms outside of ALC were removed, and ontologies with 100 to 100,000 names in their normalized form were selected. For each ontology, 50 signatures were generated, with terms chosen proportionally to their frequency in the ontology.

Key Insights and Ideas

  • General Modules Offer a Sweet Spot: The paper argues that "general modules" provide a valuable alternative to traditional modules and uniform interpolants. Their flexibility in introducing temporary definers allows for more concise and simpler outputs, which is crucial for practical applications like ontology reuse.
  • Role Isolation is Key to Efficiency: The novel "role isolation" technique is a significant contribution, enabling efficient role forgetting within ALC without resorting to external reasoners or approximations that go beyond ALC. This directly contributes to the method's speed.
  • Definer Elimination Strategy: The multi-step definer elimination process, particularly the two-step approach for conjunctions of definers, is crucial for managing complexity and avoiding the blow-up seen in other uniform interpolation methods.
  • Practical Impact on Ontology Engineering: The developed method not only computes general modules but can also be used to efficiently compute deductive modules and uniform interpolants, often outperforming existing tools in speed and output quality.

Key Results

  • Efficiency: The proposed method (GEMO) demonstrated significantly faster run times compared to state-of-the-art tools for module extraction and uniform interpolation. For example, their gmLethe method (using GEMO for intermediate steps) was substantially faster than LETHE.
  • Conciseness: The computed general modules (gm*) and uniform interpolants (gmLethe) were often substantially smaller and contained simpler axioms than those produced by other methods. For instance, the median length of the longest axiom for gm* was 3, compared to 5 for minM and much higher for LETHE and FAME.
  • Success Rate: GEMO achieved a high success rate (outputting results within 600s), second only to TL*-modules, indicating its robustness.
  • Deductive Modules: The dm method produced results with a small average size, often smaller than minM because it preserves entailments over ALC, whereas minM uses a more expressive semantics.

Limitations and Future Work

  • Theoretical Bounds: While the theoretical bound for general module size is single exponential, the authors note that in practice, modules are often much smaller.
  • Concept Elimination Optimization: The authors suggest further optimizing the concept elimination step to achieve even more concise general modules.
  • Generalization to More Expressive DLs: A key future direction is to investigate how to generalize their ideas to more expressive description logics beyond ALC.
  • Definer Introduction: While definers are eliminated, the paper acknowledges that the resulting general modules are not always uniform interpolants, which is a trade-off for efficiency and conciseness.

Summary updated

BibTeX
@inproceedings{yang2023efficient,
  author = {Hui Yang and Patrick Koopmann and Yue Ma and Nicole Bidoit},
  title = {{Efficient Computation of General Modules for ALC Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/374},
}
Figure