When managing large-scale knowledge bases, we frequently need to modify their vocabulary. We might want to forget a sensitive concept to preserve privacy, create a simplified view for a specific task via uniform interpolation, or contract the knowledge base by removing an outdated axiom.
Intuitively, these operations sound like simple subtraction: if you remove a piece of data or a term, the remaining knowledge base should just get smaller. However, in expressive Description Logics (DLs) and rule languages, this intuition breaks down completely. Modifying a finite knowledge base can suddenly require an infinite number of axioms to preserve the remaining logical consequences. This phenomenon is known as the finite representability problem.
The Intuition: Why Shrinking Creates Infinities
To understand why removing information can require infinite axioms, consider how description logics express relationships. Suppose an ontology contains a chain of implications involving a "middle-man" concept, $B$:
$$A \sqsubseteq \exists R.B$$ $$B \sqsubseteq \exists R.B$$
This finite set of rules implies an infinite sequence of logical consequences about the role $R$: $A$ must have an $R$-successor, which has an $R$-successor, which has another $R$-successor, and so on, infinitely. The concept $B$ acts as a finite generator for this infinite chain.
Now, imagine we want to forget the concept $B$ while preserving every logical consequence that can be stated using only $A$ and $R$. Without the helper concept $B$ to loop back on, how do we express that $A$ initiates an infinite chain of $R$-successors?
In standard description logics, we cannot. We can write an axiom stating that $A$ has one successor ($\exists R.\top$), or two ($\exists R.\exists R.\top$), or three. But to capture the entire deductive closure of the original ontology without $B$, we would have to write an infinite conjunction of these increasingly deep existential restrictions. The finite syntax of our original logic is simply not expressive enough to encapsulate the remaining knowledge.
Forgetting and Uniform Interpolation
This expressivity gap is a fundamental barrier to modularizing and cleaning up ontologies. As shown by Boris Konev et al. in Forgetting and Uniform Interpolation in Large-Scale Description Logic Terminologies, eliminating specific vocabulary while preserving all logical consequences frequently yields a target theory that cannot be expressed within the original logic's syntax.
This lack of closure under uniform interpolation is not a minor edge case; it is a systemic property of expressive logics. Carsten Lutz et al. proved in Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics that for the standard expressive logic $\mathcal{ALC}$, deciding whether a finite uniform interpolant even exists is 2-EXPTIME-complete. When it does exist, the resulting ontology can be triple-exponentially larger than the original. To maintain semantic completeness without an exponential explosion, the authors demonstrate that one must shift to more powerful formalisms, such as fixpoint logics ($\mu$-calculus), which natively support the recursion required to capture infinite chains.
The barrier extends beyond description logics to database theory and existential rules. As Zhe Wang et al. demonstrated in Forgetting and Unfolding for Existential Rules, removing even a single predicate from an existential rule workflow can require an infinite set of rules to preserve logical equivalence, rendering the exact result undecidable in standard finite frameworks.
The Failure of Formula-Based Contraction
A closely related problem occurs in belief revision when we want to contract an ontology—explicitly retracting a specific axiom or consequence.
In simple propositional logic, contraction is straightforward: you look at the deductive closure, remove the unwanted formula, and select a maximal subset of remaining formulas. However, Bernardo Cuenca Grau et al. showed in Ontology Contraction: Beyond the Propositional Paradise that this strategy fails in description logics. Because the deductive closure of a description logic ontology is typically infinite, formula-based contraction methods cannot guarantee a finite or representable result.
As the authors elaborate in How to Contract Ontologies, many computationally efficient description logics are fundamentally not closed under contraction. The logically ideal result of removing information simply cannot be expressed using the input language's syntax, forcing a harsh trade-off between maintaining language constraints and achieving precise logical retraction.
What Makes Logics Behave Badly?
The risk of losing finite representability depends heavily on the specific constructors allowed in the logic:
- Existential and Value Restrictions: As noted by Guilin Qi et al. in A Forgetting-based Approach for Reasoning with Inconsistent Distributed Ontologies, complex interactions between role names and value restrictions complicate the definition of forgetting beyond a purely syntactic level, creating a gap in model-theoretic semantics.
- Transitivity and Numerical Restrictions: Features like transitivity or counting constraints make it even easier to generate implicit infinite structures. Yizheng Zhao et al. in Forgetting Concept and Role Symbols in ALCOIHµ(∇, ⊓)-Ontologies highlight that these properties regularly cause forgetting tasks to output non-finite consequence sets.
- Nominals and Role Intersections: In Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents, Tim S. Lyon et al. point out that nominals (singleton sets) and role intersections frequently break standard constructive interpolation frameworks, preventing the direct computation of explicit definitions from proofs.
Practical Workarounds: Approximations and Hybrids
Because a perfect, finite result often does not exist mathematically, researchers have developed alternative paradigms to make ontology modification practical:
- Finite Approximations: Instead of aiming for an exact but impossible infinite consequence set, Kewen Wang et al. in Concept and Role Forgetting in ALC Ontologies proposed using a sequence of finite approximations. This allows reasoning tools to operate on a usable, bounded version of the modified knowledge base that gets progressively closer to the ideal semantic result.
- Structural and Hybrid Frameworks: To handle contraction without getting lost in infinite deductive closures, Bernardo Cuenca Grau et al. proposed hybrid semantic frameworks that preserve both the human-readable syntactic structure of the ontology and its intended logical behavior, bypassing purely logic-based subset selection.
- Graph-Based Pruning: In simpler profiles like DL-Lite, the boundaries are cleaner. Kewen Wang et al. demonstrated in Incosistency-Tolerant Forgetting in DL-lite that graph-based databases and algorithms can efficiently prune messy or inconsistent data while maintaining robust reasoning capabilities, avoiding the expressivity traps of more complex description logics.
Key Foundational Work
Concept and Role Forgetting in ALC{\mathcal {ALC}} Ontologies (2009) — contributed 2 concept elements to this direction.
Forgetting and Uniform Interpolation in Large-Scale Description Logic Terminologies (2009) — contributed 1 concept elements to this direction.
A Forgetting-based Approach for Reasoning with Inconsistent Distributed Ontologies (2008) — contributed 1 concept elements to this direction.