Query-Driven Repairing of Inconsistent DL-Lite Knowledge Bases

Meghyn Bienvenu, Camille Bourgaux, François GoasdouéIJCAI 2016 · OpenReview

Abstract

In Ontology-Mediated Query Answering (OMQA), real-world data often contradicts the underlying ontology, leading to inconsistencies. While inconsistency-tolerant semantics provide a way to query such data, they do not resolve the underlying errors. This paper proposes a query-driven approach to knowledge base (KB) repair. Instead of cleaning the entire dataset, the system uses user feedback on specific query results to guide targeted, optimal repairs. We formalize the Query-Driven Repairing Problem (QRP) and introduce interactive algorithms that leverage SAT solvers to identify erroneous assertions efficiently.

Introduction

The challenge of maintaining large-scale knowledge bases lies in the inherent messiness of real-world data. In the context of DL-Lite$_R$ ontologies, which underpin the OWL 2 QL profile, data inconsistencies are common. Existing methods often focus on "living with inconsistency" through specialized semantics. However, these do not improve data quality over time. Manual cleaning is often infeasible due to the sheer volume of data.

This research addresses this gap by focusing repair efforts on the data relevant to a user's current queries. By allowing users to label query results as "wanted" (missing but expected) or "unwanted" (present but incorrect), the system can identify a "repair plan"—a set of additions or deletions—that aligns the data with the user's expectations and the ontology's constraints.

Methods: The Query-Driven Repairing Problem

The authors formalize the Query-Driven Repairing Problem (QRP) as an interactive process. The system identifies a set of atomic changes (deletions or additions of facts) to the ABox (the data layer) based on user feedback.

Optimality and Preference

Because satisfying all user requests may be impossible or lead to further contradictions, the paper defines optimal plans using Pareto and lexicographic preferences. These preferences balance the desire to include wanted answers against the need to remove unwanted ones. While checking local optimality is computationally efficient, global optimality for certain settings is coNP-complete, motivating the use of greedy, interactive algorithms.

The OptDRP Algorithm

For "deletion-only" repairs, the authors developed OptDRP, a specialized algorithm that uses a SAT solver to identify "necessarily false" assertions. These are facts that must be removed to satisfy the user's feedback.

SAT encoding for identifying necessarily false assertions in the OptDRP algorithm.

The encoding shown in the figure allows the system to efficiently determine which assertions $x_\alpha$ are incompatible with the user's requirements. By presenting these to the user for validation, the system minimizes manual effort while maximizing the impact of each repair step.

Experimental Evaluation

The approach was evaluated using the CQAPri benchmark, based on the Lehigh University Benchmark (LUBM). The test environment included:

  • Ontology: A DL-Lite$_R$ version of LUBM with added constraints to induce conflicts.
  • Data: Two ABoxes (c5 and c29) with approximately 10 million assertions each.
  • Conflict Levels: Data sets with 5% and 29% conflict rates were used to simulate varying degrees of data quality.

Results and Key Insights

The experiments demonstrated that the system is highly scalable. For datasets with 10 million facts, identifying relevant assertions and checking for potential solutions took only a few milliseconds. Computing "necessarily false" assertions for hundreds of relevant facts typically took between 30ms and 1.3 seconds.

A key insight is the "computational cliff" regarding optimality. The transition from local to global optimality checks justifies the interactive, local-improvement approach. Furthermore, the system successfully converged to optimal repair plans in all test cases, typically identifying at most one subset of wanted answers that could not be satisfied without violating the ontology.

Conclusion and Future Work

This query-driven approach provides a practical path toward cleaner knowledge bases by focusing on the data that matters most to users. While the current framework handles deletions effectively, future work will address the "query abduction" problem—determining which specific facts to add to satisfy missing answers. Additionally, the authors aim to optimize the ranking heuristics used to prioritize which facts a user should validate first, as current "impact" calculations can be computationally expensive for very large sets of assertions.

Summary updated

Abstract

We consider the problem of query-driven repairing of inconsistent DL-Lite knowledge bases: query answers are computed under inconsistency-tolerant semantics, and the user provides feedback about which answers are erroneous or missing. The aim is to find a set of ABox modifications (deletions and additions), called a repair plan, that addresses as many of the defects as possible. After formalizing this problem and introducing different notions of optimality, we investigate the computational complexity of reasoning about optimal repair plans and propose interactive algorithms for computing such plans. For deletion-only repair plans, we also present a prototype implementation of the core components of the algorithm.
BibTeX
@inproceedings{bienvenu2016query,
  author = {Meghyn Bienvenu and Camille Bourgaux and François Goasdoué},
  title = {{Query-Driven Repairing of Inconsistent DL-Lite Knowledge Bases}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=Bkb_-EzuZH},
}
Figure