When managing knowledge bases, we expect to add or remove information seamlessly. However, in lightweight Description Logics (DLs) like the $DL-Lite$ family—which power modern ontology-based data access—dynamic change introduces a fundamental paradox. While these languages are intentionally restricted to ensure highly efficient, polynomial-time querying, updating or erasing facts within them can yield a state of knowledge that is completely impossible to express using the original language's syntax.
This phenomenon is known as a failure of expressive closure under evolution. It forces a difficult trade-off: either sacrifice the computational efficiency of the language by moving to a more complex logical framework, or sacrifice information by settling for an approximation of the truth.
Why Evolution Forces Disjunctions
To understand why expressive closure fails, we must look at how data updates interact with schema constraints. Lightweight description logics maintain efficiency by omitting disjunctive reasoning (the logical "OR"). Yet, as Evgeny Kharlamov et al. demonstrate in Understanding Inexpressibility of Model-Based ABox Evolution in DL-Lite, the interaction between mandatory participation constraints and role-based negation inherently generates disjunctions during an update.
Consider a simple ontology with a rule (TBox) stating that every Professor must teach at least one Course:
$$\text{Professor} \sqsubseteq \exists \text{teaches}$$
Now, suppose our database of facts (ABox) asserts that Alice is a professor and she teaches CS101:
$$\text{Professor}(\text{Alice}), \quad \text{teaches}(\text{Alice}, \text{CS101})$$
What happens if we decide to delete the fact that Alice teaches CS101? Under standard "minimal change" semantics, we want to alter as little information as possible. We have two choices to maintain consistency with our schema rule:
- Alice is no longer a professor.
- Alice is still a professor, but she teaches some other, unspecified course.
To capture the true state of the world without losing information, the knowledge base must assert that either Alice is not a professor, or she teaches an unknown course distinct from CS101. This is fundamentally a disjunctive statement. As Evgeny Kharlamov et al. show in On Prototypes for Winslett's Semantics of DL-Lite ABox Evolution, these role interactions force a choice between mutually exclusive states. Because lightweight description logics are not designed to handle disjunctions, the updated knowledge base cannot be written down within the original framework.
Model-Based vs. Formula-Based Evolution
The severity of the inexpressibility problem depends heavily on how one defines the semantics of change. Research generally splits evolution into two paradigms:
Model-Based Evolution
Model-based approaches look at the structural interpretations (models) of the world. When an update occurs, the system selects the new models that are "closest" to the original models.
As Dmitriy Zheleznyakov et al. show in On expansion and contraction of DL-Lite knowledge bases, traditional model-based evolution (such as Winslett’s semantics) is largely unsuitable for $DL-Lite$ because the resulting sets of models routinely fall outside the language's expressibility limits. The precise boundaries of this failure are tracked by Evgeny Kharlamov et al. in Capturing Instance Level Ontology Evolution for DL-Lite, confirming that model-based tracking forces an escalation into more expensive logical frameworks.
Formula-Based Evolution
Instead of evaluating abstract models, formula-based evolution operates directly on the syntactic expressions of the knowledge base. To circumvent the inexpressibility barrier, the authors of Updating ABoxes in DL-Lite introduced Naive and Careful Semantics. These formula-based approaches discard the problematic disjunctive side-effects of an update, ensuring that the resulting knowledge base remains expressible in $DL-Lite$ and can be computed in polynomial time.
A similar strategy applies when evolving the schema rules themselves. In Updating TBoxes in DL-Lite, Dmitriy Zheleznyakov et al. proposed Bold Semantics, a formula-based framework for schema evolution that avoids logical dead ends (where concepts become impossible to instantiate) while preserving tractability.
Knowledge Base Evolution
│
├─► Model-Based Semantics (e.g., Winslett's)
│ │
│ └─► Tracks closest possible worlds ──► Introduces Disjunctions ──► Inexpressibility Failure
│
└─► Formula-Based Semantics (Naive, Careful, Bold)
│
└─► Modifies syntax directly ────────────────────────────────────► Preserves Expressive Closure
Coping with Inexpressibility
When applications demand semantics that break closure—such as exact erasures or integrating uncertain data—investigators rely on two primary workarounds: approximation and language extension.
Maximal and Trust-Sensitive Approximations
If a precise update cannot be expressed in the language, the next best option is to find the closest valid representation that can be expressed. Giuseppe De Giacomo et al. formalized this in On the Approximation of Instance Level Update and Erasure in Description Logics by introducing algorithms to compute the "maximal approximation" of an update or erasure within $DL-Lite_{\mathcal{F}}$, capturing as much of the logical consequence as the syntax permits.
Approximation becomes even more vital when data sources are not entirely reliable. In Trust-Sensitive Evolution of DL-Lite Knowledge Bases, Dmitriy Zheleznyakov et al. proved that description logics lack closure when updates are weighted by the provider's trust level. To resolve this, the authors developed s-approximations, which use auxiliary symbols to construct a consistent, valid representation of trust-aware data evolution without breaking the underlying reasoner.
Escaping to More Expressive Logics
Rather than losing information via approximation, another approach is to temporarily export the updated knowledge into a more powerful language. In Understanding Inexpressibility of Model-Based ABox Evolution in DL-Lite, Evgeny Kharlamov et al. introduced a method using "prototypes" to compile complex, disjunctive updates into First-Order Logic with two variables ($FO[2]$). This allows the system to perfectly preserve the semantics of change when the target environment can tolerate higher computational complexity.
Ultimately, managing change in description logics requires balancing semantic perfection against computational reality. Whether through materialization maintenance techniques for complex existential quantifiers—such as those explored by Markus Brenner et al. in Embracing Change by Abstraction Materialization Maintenance for Large ABoxes—or through tailored formula semantics, navigating expressive non-closure remains a central challenge in knowledge base evolution.
Key Foundational Work
On the Approximation of Instance Level Update and Erasure in Description Logics (2007) — contributed 3 concept elements to this direction.
On the Update of Description Logic Ontologies at the Instance Level (2006) — contributed 1 concept elements to this direction.