How to Select One Preferred Assertional-Based Repair from Inconsistent and Prioritized DL-Lite Knowledge Bases?

Salem Benferhat, Zied Bouraoui, Karim TabiaIJCAI 2015

Introduction

In the domain of Ontology-Based Data Access (OBDA), the integration of a formal TBox (schema or logical rules) with a massive, often noisy ABox (factual data) frequently leads to logical inconsistencies. While the TBox is typically curated and reliable, the ABox often aggregates data from diverse sources with varying levels of reliability, leading to contradictions. For instance, a TBox might specify that an individual cannot simultaneously be a "Student" and a "Professor," yet the ABox might contain both assertions for the same individual.

Standard logic fails in the presence of such contradictions. To maintain reasoning capabilities, researchers employ repairs—maximal consistent subsets of the ABox. However, a single inconsistent dataset can yield an exponential number of possible repairs, making reasoning over all of them computationally prohibitive. This paper, originally presented at IJCAI 2015, proposes a paradigm shift: instead of reasoning over all repairs, can we intelligently select a single "preferred" repair to enable efficient, standard query answering?

Proposed Selection Strategies

The authors introduce several strategies for selecting a preferred repair from a prioritized ABox, where facts are organized into "strata" based on their reliability. The core of their approach is the concept of "non-defeated" repairs.

Hierarchy of repair selection strategies and their relationships.

The strategies explored include:

  1. Non-Defeated Repair ($nd$): Formed by the intersection of all possible repairs at each priority level, representing a "safe" core of information.
  2. Linear-Based Repair ($\ell nd$): A greedy approach that processes data layer-by-layer, retaining as many facts as possible from each stratum without violating the consistency established by higher-priority layers.
  3. Cardinality-Based Selection ($nd_{card}$): Prioritizes repairs containing the greatest number of facts, maximizing information retention.
  4. Consistency Constraints ($consnd_{card}$): A refinement of the cardinality approach ensuring the resulting single repair is strictly consistent with the TBox.
  5. Deductive Closure ($clnd$): Applying repair logic after expanding facts based on TBox rules to ensure more productive logical inferences.

Experimental Evaluation

The authors evaluated these methods using the DL-LiteR University Benchmark and the Extended University Data Generator (EUDG). They simulated real-world scenarios by stratifying data into 4 to 7 priority layers and injecting conflicts via 100 negative inclusion axioms in the TBox.

Search Space Reduction

One of the most striking findings is the efficiency of cardinality-based filtering. In scenarios with high conflict density, the number of possible repairs can be astronomical. As shown in the table below, the cardinality criterion ($MAR_{card}$) drastically reduces the number of candidates.

Comparison of the number of repairs and computation time between standard MAR and cardinality-based MAR.

For a dataset with 37 conflicts, the standard approach produced over 16.8 million repairs. Applying the cardinality-based selection reduced this to just 56 repairs, which can then be further narrowed down to a single preferred subbase.

Computational Performance

The research demonstrates that computing the non-defeated repair ($nd$) and its linear extension ($\ell nd$) falls within the complexity class P. This polynomial complexity ensures that the methods scale effectively to large-scale datasets. In practical tests, computing the $nd$ repair for a knowledge base with 502 conflicts and 7 priority layers took a mere 13ms. In contrast, more complex lexicographic repairs ($PAR_{lex}$) required significantly more time, highlighting the efficiency of the proposed "single repair" approach.

Key Insights and Future Directions

The "aha moment" of this research is that by justifying the selection of one "best" repair, query answering becomes as fast as standard database querying. This eliminates the need for specialized, computationally expensive "inconsistency-tolerant" algorithms during query execution.

Furthermore, the study reveals that priorities are a feature, not a bug. Increasing the number of priority levels (strata) actually simplifies conflict resolution by providing more "tie-breaking" rules, which speeds up the selection process.

Limitations

While highly effective for DL-Lite, these methods are tailored to its specific logical properties. Adapting these strategies for more expressive description logics (like SHIQ) remains a challenge. Additionally, the framework assumes a perfect TBox; if the rules themselves are contradictory (incoherent), the current methods do not apply.

Future work may explore these "single repair" strategies in the context of dynamic, streaming data where priorities and facts change in real-time.

Summary updated

BibTeX
@inproceedings{benferhat2015how,
  author = {Salem Benferhat and Zied Bouraoui and Karim Tabia},
  title = {{How to Select One Preferred Assertional-Based Repair from Inconsistent and Prioritized DL-Lite Knowledge Bases?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure