Inconsistency Tolerant Query Answering

38 concepts24 papers2 proposals

When managing large-scale databases, data integration systems, or knowledge bases, reality is often messy. Databases are frequently governed by integrity constraints or ontological rules—such as "every employee must have a unique ID" or "a person cannot be both a child and a parent." However, when aggregating data from multiple autonomous sources, these rules are routinely violated.

In classical logic, a single contradiction ruins the entire system. Under the principle of explosion (ex falso quodlibet), an inconsistent knowledge base logically entails any statement whatsoever, rendering standard query engines useless.

To solve this, researchers developed Inconsistency-Tolerant Query Answering. The core intuition is simple: instead of physically cleaning the data—which can be destructive, expensive, or impossible for read-only sources—we can change the semantics of how we query the data. We can mathematically isolate contradictions at query time, ensuring that the answers returned are reliable, robust, and logically sound.

The Foundation: Database Repairs

The foundational mechanism for tolerating inconsistency is the concept of a database repair. Imagine a database that contains conflicting information. A repair is a subset of the database that satisfies all the required rules and constraints, but is maximal—meaning you cannot add any more data to it without reintroducing a contradiction.

By focusing on maximal consistent subsets, we ensure that we minimize information loss while strictly respecting the ontology or schema constraints. This concept dates back to foundational work in knowledge representation by Benferhat et al. in their paper Inconsistency Management and Prioritized Syntax-Based Entailment, which introduced intersection-based inference over preferred consistent subbases.

In data integration environments, Calì et al. applied similar principles in Query rewriting and answering under constraints in data integration systems, demonstrating that systems can ignore conflicting tuples at query time using logic programming to provide consistent answers from inconsistent sources.

When a database is inconsistent, there is rarely just one valid repair; instead, there is a space of multiple possible repairs. For instance, if a person is listed as living in both Paris and Rome, one repair will keep the Paris fact, and another will keep the Rome fact. The challenge then becomes: how do we evaluate a query across this entire space of potential repairs?

Choosing a Semantics: Cautious vs. Brave

Different applications require different levels of certainty. As summarized by Bienvenu in Ontology-Mediated Query Answering: Harnessing Knowledge to Get More from Data, the two primary baseline strategies are:

  • Cautious (or AR) Semantics: An answer is considered valid only if it can be derived from every single possible repair of the database. This ensures absolute logical consistency. As explored by Lukasiewicz et al. in From Classical to Consistent Query Answering under Existential Rules, AR semantics guarantees that your conclusions do not rely on an arbitrary choice of how to resolve a conflict.
  • Brave (or Optimistic) Semantics: An answer is valid if it holds true in at least one possible repair. This is useful for exploratory data analysis where you don't want to miss potential insights due to a strict constraint violation.

To bridge the gap between these two extremes, alternative strategies have emerged. For example, Benferhat et al. proposed a veto-based approach in Non-Objection Inference for Inconsistency-Tolerant Query Answering. Under Non-Objection Semantics, a query answer is accepted if it is supported by at least one repair and directly contradicted by none. This increases query productivity compared to universal entailment while maintaining global consistency.

The Computational Challenge and Approximations

While cautious (AR) semantics provides the highest level of certainty, it comes with a steep computational cost. Evaluating a query across every single possible combination of repairs is frequently co-NP-hard. To make inconsistency tolerance practical for real-world databases, researchers introduced two key approximations:

Intersection of All Repairs (IAR) Semantics

Instead of evaluating the query against every repair and intersecting the results, IAR semantics intersects the repairs first. It identifies the undisputed core of the data—the facts that exist in every single possible repair—and runs the query solely on that clean subset.

In Complexity of Inconsistency-Tolerant Query Answering in Datalog+/-, the authors demonstrate that IAR semantics is often first-order rewritable for specific rule fragments. This means an inconsistency-tolerant query can be compiled directly into standard SQL and executed efficiently by traditional relational database management systems.

Intersection of Closed Repairs (ICR) Semantics

A limitation of IAR is that it can miss facts that are logically inferable across all repairs but aren't explicitly shared in the raw data. ICR semantics fixes this by first computing the logical closure of each individual repair (inferring all possible facts within that repair) and then intersecting those expanded sets.

Bienvenu mapped the computational boundaries of these approaches in On the Complexity of Consistent Query Answering in the Presence of Simple Ontologies, demonstrating how the complexity of these semantics scales based on the structure of the query itself. Further analysis by Lukasiewicz et al. in Complexity of Approximate Query Answering under Inconsistency in Datalog+/- confirmed that for several rule-based fragments, querying under IAR and ICR does not increase data complexity compared to standard, inconsistency-blind query answering.

Database (Inconsistent)
   ├── Repair 1 (Consistent Subset A) ──> Closure 1 
   ├── Repair 2 (Consistent Subset B) ──> Closure 2 
   └── Repair 3 (Consistent Subset C) ──> Closure 3 

AR Semantics:  Evaluate Query on Repair 1, 2, and 3 ──> Intersect Query Answers
IAR Semantics: Intersect Repair 1, 2, and 3 ──────────> Evaluate Query on Core Data
ICR Semantics: Intersect Closure 1, 2, and 3 ─────────> Evaluate Query on Core Inferences

Practical Implementation and Extensions

To put these theoretical semantics into practice, systems must be able to filter out inconsistencies dynamically. One elegant way to achieve this is through query-based inconsistency filtering. As designed by Trivela et al. in A Framework and Positive Results for IAR-answering, standard queries can be automatically annotated with negative atoms that represent potential rule violations. This allows the query to self-filter its results, ensuring that only data consistent with all possible repairs is returned without ever having to materialize the repairs explicitly.

The framework of inconsistency tolerance has proven highly adaptable, expanding into several specialized domains:

By decoupling data consistency from data storage, inconsistency-tolerant semantics allows modern knowledge systems to remain resilient, providing reliable answers even when operating over fundamentally conflicted information.

Key Foundational Work

Query rewriting and answering under constraints in data integration systems (2003) — contributed 2 concept elements to this direction.
Inconsistency Management and Prioritized Syntax-Based Entailment (1993) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 24 papers
  2. Version 1 · 2026-10-04 · 33 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_inconsistency_tolerant_semantics_5ebac3c4,
  title = {inconsistency-tolerant semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inconsistency-tolerant-semantics/rdr_5ebac3c46139400887e816eab370f2b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_inconsistency_tolerant_semantics_5ebac3c4_v2,
  title = {inconsistency-tolerant semantics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inconsistency-tolerant-semantics/rdr_5ebac3c46139400887e816eab370f2b4/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake