Introduction
In Description Logic (DL) Knowledge Bases, an ontology (TBox) defines the logical structure, while a dataset (ABox) contains specific facts. In large-scale applications, ABoxes are frequently riddled with errors or inconsistencies that contradict the TBox. Standard logic is "explosive" in these scenarios: a single contradiction can lead the system to conclude that any statement is true, rendering query results meaningless.
To address this, researchers use "inconsistency-tolerant" semantics like AR (consistent in all possible repairs) and IAR (consistent in the intersection of all repairs). However, these traditional methods treat all data as equally reliable. In practice, data often comes with varying levels of trust, such as timestamps, sensor confidence scores, or source reliability. This paper introduces "preferred repair" semantics to incorporate these priorities into the querying process without sacrificing computational feasibility.
Preferred Repair Semantics and Complexity
The authors extend the classical notion of a repair—a maximal consistent subset of data—by introducing four types of preference preorders to prioritize more reliable facts:
- Cardinality ($\le$): Prefers repairs containing the largest number of facts.
- Prioritized Set Inclusion ($\subseteq_P$): Facts are grouped by priority; repairs that retain more facts from higher-priority levels are preferred.
- Prioritized Cardinality ($\le_P$): A quantitative version of the above, counting facts at each priority level.
- Weights ($\le_w$): Each fact has a numerical weight, and repairs with the highest total weight are preferred.
A core contribution of the paper is a rigorous complexity analysis within the $DL-Lite_R$ framework. The results show that while standard IAR query answering is in P, adding preferences generally elevates the data complexity to coNP-hard or higher. Notably, Prioritized Set Inclusion ($\subseteq_P$) emerges as the most efficient preference type, with both AR and IAR remaining coNP-complete, making it the primary candidate for practical implementation.
The CQAPri System and Experimental Setup
To bridge the gap between theory and practice, the authors developed CQAPri, a SAT-based tool for query answering. The system reduces the problem to checking the unsatisfiability of propositional formulas representing the query, its potential "causes" (supporting data), and "conflicts" (contradictory data). To optimize performance, CQAPri uses an Oriented Conflict Graph to prune irrelevant assertions, ensuring the SAT solver only processes facts related to the query.
The system was evaluated using modified versions of the LUBM benchmark and the Extended University Data Generator (EUDG), scaling up to 2.1 million assertions with injected synthetic inconsistencies to test the limits of the approach.
Key Results and Insights
Experimental results demonstrate that CQAPri is highly scalable, with query answering times scaling linearly with ABox size for realistic conflict densities. The reachability analysis on the conflict graph proved exceptionally effective, often reducing the SAT solver's workload to a tiny fraction of the total dataset.
A significant insight from the evaluation is the relationship between AR and IAR semantics. As shown in the figure above, the "cautious" IAR semantics often provides a very close approximation of the more expensive AR semantics. In many cases, AR did not yield any additional answers beyond those found by IAR, suggesting that IAR can serve as a powerful heuristic for practical applications.
Limitations and Future Work
While robust, the system's performance degrades under extremely high conflict density (e.g., 30-50%), where the SAT solver becomes a bottleneck. Additionally, complex priority structures can lead to high memory consumption during graph construction. Future work includes developing an optimizer to automatically select the best solving technique—such as SAT solvers versus Integer Programming—based on the specific characteristics of the data's conflict graph.
Summary updated