In the ideal vision of the Semantic Web, knowledge bases are living entities that evolve as new information arrives. However, a fundamental tension exists between the efficiency of a logic and its ability to change. When we update a lightweight ontology—specifically those in the DL-Lite family used for large-scale data access—we often find that the resulting state of knowledge is impossible to express within the original logic.
This phenomenon is known as the closure problem. It forces researchers to choose between losing information, moving to a more computationally expensive logic, or using clever approximations to bridge the gap.
The Problem of Inexpressibility
Lightweight description logics like DL-Lite are designed to keep reasoning tasks, such as query answering, within polynomial time. To achieve this speed, they intentionally omit certain complex features, most notably disjunction (the logical "OR").
As Giuseppe De Giacomo, Maurizio Lenzerini, and their colleagues first detailed in On the Update of Description Logic Ontologies at the Instance Level, updating the "facts" (the ABox) of an ontology while keeping the "rules" (the TBox) fixed can lead to a set of logical models that no longer fit the original syntax.
Why Logic Breaks
The intuition behind this failure is that updates often introduce ambiguity. Imagine a rule stating that every "Employee" must have a "Manager." If we delete the specific fact that "Alice manages Bob," the logic still knows Bob must have a manager. The new state of knowledge is effectively: "Bob is managed by X OR Y OR Z..."
Because DL-Lite cannot explicitly represent this "OR," the updated knowledge base cannot be written down in the same language. Evgeny Kharlamov and Dmitriy Zheleznyakov identified that this specifically happens when mandatory participation constraints interact with role-based negation, as explored in Understanding Inexpressibility of Model-Based ABox Evolution in DL-Lite.
Model-Based vs. Formula-Based Evolution
To handle these updates, researchers generally follow two different philosophical paths:
- Model-Based Semantics: This approach looks at the "possible worlds" (models) compatible with the new information and tries to find a new knowledge base that represents exactly those worlds. As shown in Updating ABoxes in DL-Lite, this is the path most likely to hit the inexpressibility wall because it tries to be perfectly precise.
- Formula-Based Semantics: Instead of looking at models, this approach treats the knowledge base as a collection of formulas and applies rules to add or remove them. Diego Calvanese and his co-authors proposed "Careful Semantics" and "Bold Semantics" to ensure that updates remain within the original logic's syntax while maintaining as much information as possible, even when updating the schema-level TBox (Updating TBoxes in DL-Lite).
Bridging the Gap: Approximations and Scaffolding
When a perfect representation is impossible, we must approximate. In On the Approximation of Instance Level Update and Erasure in Description Logics, the authors introduced the concept of maximal approximation—finding the strongest possible statement in the original logic that is still true after the update.
A more sophisticated technique involves logical scaffolding. When the logic isn't expressive enough to capture an update, we can introduce auxiliary constants or roles to act as placeholders for the missing information. In Trust-Sensitive Evolution of DL-Lite Knowledge Bases, Ian Horrocks and his colleagues used a technique called s-approximation to handle updates from sources with varying levels of reliability. This allows the system to integrate "partially trusted" data without breaking the underlying logical structure.
Practical Implementation and Performance
While much of this research is theoretical, it has direct implications for how we build high-performance data systems. For example, the incR approach described by Changlong Wang and Zhiyong Feng uses directed graphs (digraphs) to maintain the transitive closure of an ontology. By updating the graph incrementally rather than re-reasoning from scratch, they achieve significantly faster performance during evolution (Updating Direct Graph for Incremental Reasoning in OWL 2 QL Ontology).
Ultimately, the study of ontology evolution in DL-Lite is a study of balance. By understanding exactly where and why a logic fails to capture change, researchers can design systems that evolve gracefully—using approximations where they must, and efficient algorithms where they can.