# Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments

arXiv: https://arxiv.org/abs/2202.07980 · HTML: https://mlsanity.com/paper/2202.07980/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 30 references that are in the map.
- First posted on arXiv 16 Feb 2022.

## Builds on (most cited first, 3 of 3)

- [HoloClean: Holistic Data Repairs with Probabilistic Inference](https://mlsanity.com/paper/1702.00820/) (2017)
- [Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation](https://mlsanity.com/paper/2003.05746/) (2020)
- [A SAT-based System for Consistent Query Answering](https://mlsanity.com/paper/1905.02828/) (2019)

## Built on by (most cited first, 4 of 4)

- [Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints](https://mlsanity.com/paper/2306.03523/) (2023)
- [Dealing with Inconsistency for Reasoning over Knowledge Graphs: A Survey](https://mlsanity.com/paper/2502.19023/) (2025)
- [An Embedding-based Approach to Inconsistency-tolerant Reasoning with Inconsistent Ontologies](https://mlsanity.com/paper/2304.01664/) (2023)
- [Exploiting Uncertainty for Querying Inconsistent Description Logics Knowledge Bases](https://mlsanity.com/paper/2306.09138/) (2023)

## Abstract (arXiv)

We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases, which consist of a logical theory, a set of facts, and a priority relation between conflicting facts. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion). Deciding whether a query answer holds under these semantics is (co)NP-complete in data complexity for a large class of logical theories, and SAT-based procedures have been devised for repair-based semantics when there is no priority relation, or the relation has a special structure. The present paper introduces the first SAT encodings for Pareto- and completion-optimal repairs w.r.t. general priority relations and proposes several ways of employing existing and new encodings to compute answers under (optimal) repair-based semantics, by exploiting different reasoning modes of SAT solvers. The comprehensive experimental evaluation of our implementation compares both (i) the impact of adopting semantics based on different kinds of repairs, and (ii) the relative performances of alternative procedures for the same semantics.