Trust-Sensitive Evolution of DL-Lite Knowledge Bases

Dmitriy Zheleznyakov, Evgeny Kharlamov, Ian Horrocks

Introduction

Knowledge Bases (KBs) are essential for managing structured information, particularly in the context of the Semantic Web and Description Logics (DLs). However, the process of "evolution"—updating a KB with new information—traditionally relies on the assumption that incoming data is perfectly reliable. In reality, data sources such as web scrapers or sensors are often noisy or specialized. This paper addresses the challenge of integrating new data based on the provider's expertise, specifically within the DL-Lite family of logics, which underpins the OWL 2 QL standard.

The Challenge of Trust and Closure

Most evolution methods follow a "priority to the new" principle: if new information contradicts the old, the old is discarded. This is problematic when a source has limited expertise. For example, a biologist's input on physics should not necessarily override established physical laws in a general-purpose KB.

The authors identify two primary hurdles in solving this:

  1. Trust Modeling: Formally representing varying levels of source expertise.
  2. The Closure Problem: In DL-Lite, the logical result of an update often cannot be expressed within the syntax of the language itself. This "non-closure" leads to a loss of information when attempting to store the updated KB.

Formalizing Trust

The researchers model trust using an equivalence relation on possible worlds (interpretations). If a source cannot distinguish between two states of the world, they are not considered an expert regarding the differences between those states. They categorize trust into four distinct classes:

  • Total Trust (TT): The source is considered an expert on all matters (the classical approach).
  • Total Distrust (TD): The source's input is entirely ignored.
  • Assertion Trust (AT): Trust is confined to a specific set of facts or assertions.
  • Predicate Trust (PT): Trust is limited to specific categories or predicates (e.g., trusting a source about "location" but not "salary").

Overcoming Non-Closure with s-Approximation

Since DL-Lite is not closed under trust-sensitive evolution, the authors introduce s-approximation. Traditional approximation methods often lose significant semantic detail. In contrast, s-approximation allows the use of "fresh" (auxiliary) constants and roles. These act as logical scaffolding, enabling the KB to accurately represent the evolution's result without violating DL-Lite's structural constraints. This technique is particularly effective for preserving the truth of complex Boolean queries (e.g., counting distinct researchers on a project) that would otherwise be lost during a standard update.

Key Results and Complexity

The paper provides formal proofs that DL-Lite is not closed under most trust settings. To address this, the authors developed several algorithms—TT-SApprox, PT-ExtendSAx, and AT-ExtendAx—which compute maximal s-approximations in polynomial time. This ensures that the approach is computationally feasible for large-scale, real-world Knowledge Bases. Furthermore, they demonstrate that s-approximations are strictly superior to previous state-of-the-art methods (such as the AtAlg algorithm) in terms of query preservation.

Conclusion and Future Directions

This research provides a robust framework for trust-sensitive KB evolution, moving beyond the simplistic "new is always right" paradigm. While the proposed s-approximations are "maximal," future work remains to determine "optimal" approximations for every scenario. Additionally, the authors suggest integrating preference-based models (ranking multiple sources) and extending these techniques to more expressive Description Logics beyond the DL-Lite family.

Summary updated

Abstract

Evolution of Knowledge Bases (KBs) consists of incorporating new information in an existing KB. Previous studies assume that the new information should be fully trusted and thus completely incorporated in the old knowledge. We suggest a setting where the new knowledge can be partially trusted and develop model-based approaches (MBAs) to KB evolution that rely on this assumption. Under MBAs the result of evolution is a set of interpretations and thus two core problems for MBAs are closure, i.e., whether evolution result can be axiomatised with a KB, and approximation, i.e., whether it can be (maximally) approximated with a KB. We show that DL-Lite is not closed under a wide range of trust-sensitive MBAs. We introduce a notion of s-approximation that improves the previously proposed approximations and show how to compute it for various trust-sensitive MBAs.
BibTeX
@inproceedings{zheleznyakov2017trust,
  author = {Dmitriy Zheleznyakov and Evgeny Kharlamov and Ian Horrocks},
  title = {{Trust-Sensitive Evolution of DL-Lite Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10701},
}
Figure