TL;DR
This paper introduces a novel approach for "forgetting" symbols (concepts and roles) from expressive description logic ontologies, enabling the creation of simplified, focused views. Their method is unique in handling ontologies with nominals, role inverses, and even fixpoint operators, while demonstrating strong performance on real-world datasets.
What Problem Does This Paper Address?
Ontologies, which formally represent knowledge, can become very large and complex. For practical applications like ontology analysis, summarization, reuse, or debugging, it's often necessary to create "restricted views" of an ontology that exclude certain concepts or roles. This process, known as "forgetting" or "uniform interpolation," aims to remove specified symbols while preserving all logical consequences that don't involve those symbols.
Existing methods for forgetting in description logics have limitations. Many struggle with expressive features like nominals (specific individuals acting as concepts), role inverses (e.g., hasParent vs. isParentOf), or the ability to express recursive definitions using fixpoint operators. Furthermore, forgetting role symbols is generally much harder than forgetting concept symbols. This paper tackles the challenge of developing a forgetting method for a highly expressive description logic, ALCOIHµ⁺(∇, Π), which includes these complex features, aiming to provide a more practical and versatile tool for ontology engineering.
Methods
The authors propose an Ackermann-based approach for forgetting symbols in ALCOIHµ⁺(∇, Π) ontologies. The method involves three main phases:
- Clause Conversion: The input ontology (TBox and RBox axioms) is converted into a set of clauses.
- Forgetting Phase: This is the core of the method. It iteratively eliminates symbols from a user-defined set Σ.
- Definer Symbols: To handle complex structures, especially during role forgetting, auxiliary "definer symbols" are introduced. These are temporary concept symbols that help in transforming clauses into a "reduced form" suitable for elimination.
- Ackermann Rules: Specialized "Ackermann rules" (for concepts and roles) are applied to transform clauses containing the symbol to be forgotten (the "pivot") into a form where the pivot can be eliminated. These rules are designed to preserve logical equivalence up to the forgotten symbols.
- Heuristic Ordering: The order in which symbols are forgotten can significantly impact performance. The system can either use a user-specified order or a heuristic based on symbol frequency counts.
- Definer Elimination: After all target role symbols are forgotten, the introduced definer symbols are eliminated using concept forgetting rules.
- Definer Elimination Phase: Any introduced definer symbols are removed using concept forgetting techniques.
The logic ALCOIHµ⁺(∇, Π) itself is notable for including:
- Nominals (e.g.,
{London}) - The top role (∇) and role conjunction (Π)
- Role inverses (r⁻)
- Least fixpoint operators (µ) for recursive definitions, restricted to positive occurrences.
Datasets
The evaluation was performed on ontologies taken from the NCBO BioPortal and the Oxford Ontology repositories. These ontologies were restricted to the ALCOIH(∇, Π) fragment, with any subconcepts beyond this scope replaced by T (top concept). Specifically, 354 ontologies from BioPortal (averaging 875 axioms each) and 180 ontologies from Oxford (averaging 154 axioms each) were used.
Key Insights and Ideas
- Handling Expressivity is Key: The paper demonstrates that forgetting in highly expressive description logics (with nominals, fixpoints, etc.) is not just theoretically possible but also practically feasible. The inclusion of nominals is a significant contribution, as it's the first approach to support forgetting them.
- Definer Symbols as a Bridge: The introduction of definer symbols is a clever mechanism to overcome the difficulty of transforming complex clauses into a state where Ackermann rules can be applied, particularly for role forgetting.
- Role Forgetting is Tough but Solvable: While role forgetting is acknowledged as significantly harder than concept forgetting, the proposed calculus and the use of definer symbols enable its successful implementation even in expressive logics.
- Heuristics Matter for Performance: The choice of forgetting order can dramatically improve efficiency. The paper shows that their heuristic ordering significantly speeds up the process and increases success rates compared to arbitrary ordering.
- Fixpoints and Role Conjunctions are Not Always Necessary: Despite the logic's expressivity, the evaluation suggests that for many real-world ontologies, the forgetting solutions don't necessarily require fixpoints or role conjunctions, indicating that simpler representations are often sufficient.
Key Results
- High Success Rates: The implementation achieved very high success rates: 96.7% for BioPortal ontologies and 86.2% for Oxford ontologies when forgetting concept symbols. For role forgetting, the success rate was 100% across the board.
- Improved Efficiency with Heuristics: Using the heuristic ordering for symbol elimination improved time efficiency by 124.1% for BioPortal and 136.9% for Oxford ontologies in concept forgetting.
- Fixpoint Usage: Fixpoints appeared in the results for concept forgetting in 8.3% of BioPortal cases and 13.8% of Oxford cases.
- Role Forgetting is Slower but Robust: Role forgetting took significantly longer than concept forgetting but maintained a 100% success rate. Clause growth in role forgetting solutions was modest.
- Definer Symbol Usage: Definer symbols were introduced in only a small proportion of ontologies during role forgetting, suggesting that many ontologies have relatively "flat" structures concerning roles.
Limitations and Future Work
- Transitive Roles: The current method does not handle forgetting transitive roles. While concept forgetting can be extended, forgetting role symbols in the presence of transitive roles leads to complexities that are not yet fully understood or representable finitely.
- Role Functionality and Numerical Quantifiers: Extending the method to handle role functionality and numerical quantifier restrictions remains an open problem.
- Further Optimization: While the heuristic ordering is effective, further research into optimal forgetting orderings could yield even better performance.
- Practicality of Fixpoints: While the logic supports fixpoints, their occurrence in forgetting solutions might still pose challenges for some downstream applications. Investigating ways to minimize or eliminate fixpoints in results, where possible, could be beneficial.
Summary updated