Non-Objection Inference for Inconsistency-Tolerant Query Answering

Salem Benferhat, Zied Bouraoui, Madalina Croitoru, Odile Papini, Karim TabiaIJCAI 2016

Abstract

This paper introduces "non-objection inference," a novel approach to querying inconsistent databases governed by an ontology. By requiring that at least one data "repair" supports a query and no other repair contradicts it, the authors provide a semantics that is more informative than standard cautious approaches while remaining computationally efficient (polynomial time) for the widely used DL-Lite logic family.

Introduction

In Ontology-Based Data Access (OBDA), a formal model (an ontology) is used to query underlying data. However, real-world data is often messy and may conflict with ontological rules—for example, a database listing a person as both a "Teacher" and a "Student" when the ontology defines these roles as mutually exclusive. In such cases, standard logic breaks down.

The traditional "gold standard" for handling this is AR-semantics (universal entailment), which only accepts an answer if it is true in every possible consistent version of the data, known as "repairs." While safe, AR-semantics is often too cautious, returning very few results, and is computationally expensive (co-NP-complete). Conversely, credulous semantics ($∃$) accepts an answer if it is true in at least one repair, but this can lead to logically inconsistent answer sets. This research seeks a "Goldilocks" solution: an inference method that is more productive than AR-semantics, safer than credulous semantics, and fast enough for large-scale applications.

Non-Objection Inference Framework

The authors propose Non-Objection Inference ($no$) and two variants to balance productivity and safety:

  1. Non-Objection ($no$): A query is accepted if there is at least one repair that entails it, and no repair is inconsistent with the query. This acts as a "veto" system: one repair votes "yes," and the answer is accepted as long as no other repair strongly objects by being logically incompatible with the query.
  2. Cardinality-based Non-Objection ($cno$): This restricts both the "yes" and the "veto" power to only the largest repairs (those containing the most facts).
  3. Limited-based Non-Objection ($lno$): Any repair can provide a "yes," but only the largest repairs have the power to "veto."
The hierarchy of inference methods showing the relationships between AR, cno, no, lno, and credulous semantics.

The researchers focus on the DL-Lite family of description logics. They leverage "first-order rewritability," allowing complex ontological queries to be transformed into standard SQL queries that run efficiently on traditional databases.

Experimental Evaluation

The approach was evaluated using the LUBM20 ontology and the Extended University Data Generator (EUDG). To create a challenging environment, the authors added 1,296 negative constraints to induce inconsistencies. Data was managed using an SQLite engine with ABoxes containing up to approximately 30,000 facts.

Key Results and Performance

The core insight of this work is shifting the focus from universal agreement to the absence of strong disagreement. This allows the system to ignore minor inconsistencies that do not directly contradict the query.

Experimental results showing computation times (in milliseconds) for different ABox sizes and queries.

As shown in the experimental data, query evaluation for $no$-inference is highly efficient, typically taking only milliseconds. The primary bottleneck identified was the initial computation of the "negated closure" of the ontology (the IC column), which took approximately 850-860 seconds. However, this is a one-time preprocessing step.

Furthermore, the authors proved that $no$-inference can be computed in polynomial time for DL-Lite, a significant improvement over the co-NP-complete complexity of AR-semantics. Unlike credulous semantics, $no$-inference is guaranteed to produce a set of answers that are mutually consistent with the ontology's rules.

Conclusion and Future Work

While $no$-inference offers a powerful and efficient alternative for DL-Lite, the cardinality-based variants ($cno$ and $lno$) are computationally heavier, falling into the $\Delta^p_2$ complexity class. Future work will explore the complexity of these inferences in other lightweight description logics, such as the EL family, and investigate their behavior in propositional logic settings.

Summary updated

BibTeX
@inproceedings{benferhat2016non,
  author = {Salem Benferhat and Zied Bouraoui and Madalina Croitoru and Odile Papini and Karim Tabia},
  title = {{Non-Objection Inference for Inconsistency-Tolerant Query Answering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure