Inconsistency Measures for Repair Semantics in OBDA

Bruno Yun, Srdjan Vesic, Madalina Croitoru, Pierre BisquertIJCAI 2018 · DOI

TL;DR

This paper introduces a novel framework for handling inconsistent knowledge bases in Ontology-Based Data Access (OBDA) systems. It proposes using "inconsistency measures" to rank and filter potential "repairs" (consistent subsets of the data), leading to more precise and potentially more answers than traditional methods. This approach is demonstrated to be effective and practical, even on real-world data.

What Problem Does This Paper Address?

In many real-world applications, data is gathered from multiple, independent sources. When these sources are integrated into an Ontology-Based Data Access (OBDA) system, inconsistencies can arise. For example, one sensor might report a temperature of 25°C, while another reports 30°C for the same location and time. Traditional OBDA systems struggle with such inconsistencies, often leading to no answers or incorrect conclusions.

Existing approaches to handle this, known as "inconsistency-tolerant semantics," typically consider all possible "repairs" – maximally consistent subsets of the data. However, this can be computationally expensive and may not be ideal for applications where certain data sources are inherently more reliable or where a focus on specific aspects of the data is desired. This paper addresses the challenge of how to intelligently select and prioritize these repairs when the data itself provides clues about its own inconsistency.

Methods

The core of this paper is a "Ranking-Based Inference Framework" (RIF) that introduces three key components:

  1. Inconsistency Value: This is a function that assigns a numerical score to each fact in the knowledge base, indicating how "guilty" it is for causing inconsistencies. The paper focuses on Shapley inconsistency values, which are derived from game theory to measure the responsibility of each fact.
  2. Lifting Function: This function takes the inconsistency scores of individual facts and uses them to rank entire sets of facts (repairs). The paper explores two such functions: Lmax (comparing based on the highest-scoring fact) and Leximax (a more sophisticated comparison that considers facts in descending order of their scores).
  3. Inconsistency-Tolerant Inference: This is a standard inference mechanism (like AR, IAR, or ICR) that is then restricted to operate only on the "best" repairs identified by the inconsistency value and lifting function.

The RIF framework then defines the "top result" as the set of repairs that are considered the best according to the chosen inconsistency value and lifting function.

Datasets

The paper uses a real-world dataset from the "Pack4Fresh" project, which involved collecting data on packaging for strawberries. This dataset consists of facts and rules derived from an online poll of food industry professionals, along with expert knowledge and negative constraints. The authors also mention using KBs from a previous work ([Yun et al., 2017]) for experimental evaluation.

Key Insights and Ideas

  • Intrinsic Preference: The paper proposes using the inherent inconsistency of facts within the knowledge base itself to create preferences, rather than relying on external, pre-defined preferences. This is a significant departure from previous work.
  • Ranking Repairs: By ranking repairs based on the inconsistency of the facts they contain, the framework can focus on more reliable or less problematic subsets of the data.
  • Improved Productivity: By restricting inference to a subset of "best" repairs, the RIF can potentially yield more answers than traditional methods that consider all repairs, while still maintaining consistency.
  • Desirable Properties: The authors formally define and analyze desirable properties for their framework, such as "Free Facts Entailment," "Abstraction," and "Non Entailment Ejection," ensuring its theoretical soundness.

Key Results

The paper presents a formal framework and discusses its properties. Key results include:

  • Algorithm: A recursive algorithm (Algorithm 1) is proposed for computing the output of the RIF, which uses minimal inconsistent sets.
  • Experimental Evaluation: Experiments on two sets of KBs showed that the RIF significantly reduces the number of repairs considered (by 19.66% to 26.92%) and, in some cases, leads to faster computation times compared to a naive approach.
  • Application Scenario: In the Pack4Fresh scenario, the RIF successfully ranked packaging options (WP > PRL ~ PPF > OPL) in a way that was deemed intuitive and confirmed by packaging experts, demonstrating the practical utility of the approach.

Limitations and Future Work

  • Computational Complexity: While the RIF reduces the number of repairs, finding minimal inconsistent sets can still be computationally intensive in the worst case, potentially requiring exponential time with respect to the number of facts.
  • Choice of Inconsistency Measure: The paper focuses on Shapley inconsistency values but acknowledges that other measures could be used. The choice of measure can impact the ranking of repairs.
  • Future Work: The authors suggest exploring other inconsistency measures and lifting functions, as well as investigating the framework's performance on larger and more complex real-world datasets. They also note that their framework does not make all inconsistency-tolerant inference relations more productive, pointing to specific semantics where this is not the case.

Summary updated

BibTeX
@inproceedings{yun2018inconsistency,
  author = {Bruno Yun and Srdjan Vesic and Madalina Croitoru and Pierre Bisquert},
  title = {{Inconsistency Measures for Repair Semantics in OBDA}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/273},
}
Figure