In knowledge representation, we often find ourselves wanting to "forget" information. Whether we are trying to protect privacy by removing sensitive concepts from a medical database, simplifying a massive ontology like SNOMED CT for a specific task, or modularizing a complex system, the goal is the same: remove specific terms or axioms while preserving every logical consequence that can be expressed using the remaining vocabulary.
This process is formally known as forgetting or uniform interpolation. While it sounds like a simple filtering task, research has shown that it is a deep logical challenge. In many expressive Description Logics (DLs), the "shadow" left behind by forgotten information is often too complex to be described by the original logic's syntax.
The Expressibility Barrier
The fundamental problem in forgetting is closure. If you have a knowledge base written in a specific logic, and you remove a concept, is the resulting set of implications still expressible in that same logic?
As Bernardo Cuenca Grau, Evgeny Kharlamov, and Dmitriy Zheleznyakov argue in Ontology Contraction: Beyond the Propositional Paradise, Description Logics lack the "propositional paradise" where such operations are straightforward. In propositional logic, you can always find a finite set of formulas to represent what remains. In DLs, however, removing a single term can create a "hole" that requires an infinite number of axioms to fill, or requires logical features that the original language simply doesn't possess.
For example, Carsten Lutz and Frank Wolter demonstrated in Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics that for the logic $\mathcal{ALC}$, a valid interpolant might not exist unless you extend the logic with fixpoint operators (the mu-calculus). Without these extensions, the logical consequences of the "forgotten" terms might be triple-exponentially larger than the original ontology—if they can be expressed at all.
Why Forgetting Fails to Stay Finite
Intuition suggests that removing information should make a file smaller. In logic, the opposite often happens. When you "forget" a concept $A$, you must explicitly state all the indirect relationships that $A$ used to mediate.
Imagine an ontology where HeartSurgeon implies Surgeon, and Surgeon implies MedicalProfessional. If we forget the middle term Surgeon, we must add a direct link from HeartSurgeon to MedicalProfessional. In complex ontologies with role hierarchies, inverses, and transitivity, these indirect links can explode.
Zhe Wang, Kewen Wang, and Xiaowang Zhang showed in Forgetting and Unfolding for Existential Rules that for certain rule-based languages, this process is not just difficult—it is undecidable. There is a "fundamental expressibility barrier" where capturing the remaining knowledge requires an infinite set of rules.
Strategies for Practical Forgetting
Despite these theoretical hurdles, researchers have developed several mechanisms to make forgetting work in practice:
- Fixpoint Extensions: As noted by Lutz and Wolter, we can move to more powerful formalisms like the mu-calculus to capture the "infinite" consequences of forgetting in a finite way.
- Finite Approximations: In Concept and Role Forgetting in ALC Ontologies, Kewen Wang and colleagues suggest that since a perfect finite result doesn't always exist, we can use a sequence of approximations that get closer and closer to the ideal "forgotten" state.
- Ackermann-based Calculus: Yizheng Zhao and Renate A. Schmidt developed methods using Ackermann’s Lemma to eliminate symbols from highly expressive ontologies (including those with nominals and role inverses) while maintaining logical consistency, as seen in Forgetting Concept and Role Symbols in ALCOIHµ+(∇, ⊓)-Ontologies.
- Sequent Calculi: More recently, Tim S. Lyon and Jonas Karge have explored constructive interpolation. In Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents, they show how to extract definitions of concepts directly from formal proofs, providing a path to compute what a concept "means" in terms of other symbols.
From Theory to Large-Scale Engineering
The ultimate test for these ideas is their application to massive, real-world datasets. Boris Konev, Dirk Walther, and Frank Wolter demonstrated in Forgetting and Uniform Interpolation in Large-Scale Description Logic Terminologies that these techniques can be scaled to medical ontologies. By identifying specific logic extensions, they proved it is possible to create task-specific versions of giant terminologies without losing their reasoning power.
Even when the data is messy, the principles of forgetting can be applied. Kewen Wang and Peng Xiao extended this to Inconsistency-Tolerant Forgetting in DL-lite, showing that we can prune symbols from inconsistent knowledge bases while preserving the integrity of the remaining information.
In summary, forgetting is the art of surgical removal in logic. It works by identifying the "logical footprint" of a concept and re-weaving the surrounding axioms to bridge the gap, a process that pushes the boundaries of what standard Description Logics can express.