A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean · 2025

Read A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases by Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07742.txt.

Introduction

Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, and Robin Jean gave a rule-based way in 2025 to state preferences among conflicting facts in a knowledge base. When a knowledge base contradicts itself, repair methods drop some facts to restore sense, and a priority ranking decides which facts survive. How to write that ranking down was largely unaddressed.

Their framework lets users declare preference rules, from which the ranking between facts is computed. Stated preferences can form cycles, which break a ranking, so they study when a rule set can never cycle and also give practical cycle-removal methods. A first system ties the rules to actual querying of inconsistent bases, with experiments reported. Readers get the missing front end for a mature theory: a way to say, in rules, which facts you trust more.

Catalog record

CREATORMeghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-07742

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean Abstract Repair-based semantics have been extensively studied as a means of obtaining meaningful answers to queries posed over inconsistent knowledge bases (KBs). While several works have considered how to exploit a priority relation between facts to select optimal repairs, the question of how to specify such preferences remains largely unaddressed. This motivates us to introduce a declarative rule-based framework for specifying and computing a priority relation between conflicting facts. As the expressed preferences may contain undesirable cycles, we consider the problem of determining when a set of preference rules always yields an acyclic relation, and we also explore a pragmatic approach that extracts an acyclic relation by applying various cycle removal techniques. Towards an end-to-end system for querying inconsistent KBs, we present a preliminary implementation and experimental evaluation of the framework, which employs answer set programming to evaluate the preference rules, apply the desired cycle resolution techniques to obtain a priority relation, and answer queries under prioritized-repair semantics. 1 Introduction Inconsistency-tolerant semantics are a well-established approach to querying data inconsistent w.r.t. some constraints, both in the relational database and ontology-mediated query answering settings (cf. recent surveys [ 2019 , 2020 ] ). Such semantics typically rely on (subset) repairs , defined as maximal subsets of the data consistent w.r.t. the constraints. The most well-known, called the AR semantics in the KR community and corresponding to consistent query answering in the database community, considers that a Boolean query holds true if it holds in every repair. The more cautious IAR semantics amounts to querying the repairs intersection, and the less cautious brave semantics only requires that the query holds in some repair. Since an inconsistent dataset may have a lot of repairs, several notions of preferred repairs have been proposed in the literature, to restrict the possible worlds considered to answer queries, for example by taking into account some information about the reliability of the data [ 2007 , 2013 , 2014 , 2022 , 2023 ] . In particular, since its introduction by ? ( ? ), the framework of prioritized databases , in which a priority relation between conflicting facts is used to define optimal repairs , has attracted attention, with numerous theoretical results [ 2017 , 2020 , 2020 , 2023 ] , and an implementation [ 2022 ] . However, the crucial question of obtaining the priority relation was left unaddressed, preventing the adoption of this framework in practice. Indeed, it is not realistic to expect users to manually input a binary relation between the facts. In our work, we tackle this challenge by developing a general rule-based approach to specifying preferences over conflicting facts. After introducing the background on optimal repair-based inconsistency-tolerant semantics in Section 2 , we present in Section 3 our framework for specifying a priority relation between conflicting facts via preference rules. A distinguishing feature of our work is that we address the issue of cycles in the expressed preferences, first by investigating the problem of deciding whether a given set of preference rules is guaranteed to produce an acyclic relation, and second by providing a pragmatic approach that uses cycle removal strategies to extract an acyclic relation. Section 4 describes our implementation which employs answer set programming to evaluate the preference rules, apply the desired cycle resolution techniques to obtain a priority relation, and answer queries under optimal repair-based semantics. Finally, we present in Section 5 a preliminary experimental evaluation of the overall framework. Sections 6 and 7 discuss related and future work. Proofs and additional details on the implementation and experiments are provided in the appendix. All materials to reproduce the experiments (e.g. datasets, logic programs) are available at https://github.com/rjean007/PreferenceRules-ASP 2 Preliminaries We recall the framework of inconsistency-tolerant querying of prioritized knowledge bases, as considered in [ 2022 , 2024 ] . We assume that readers are familiar with first-order logic and consider three disjoint sets of predicates {\bf{P}} , constants {\bf{C}} and variables {\bf{V}} . As usual, each predicate has an associated arity n\geq 1 , and we shall use {\bf{P}}_{n} for the set of the n -ary predicates in {\bf{P}} . Knowledge bases A knowledge base (KB) \mathcal{K}=(\mathcal{D},\mathcal{T}) consists of a dataset \mathcal{D} and a logical theory \mathcal{T} : \mathcal{D} is a finite set of facts of the form P(c_{1},\ldots,c_{n}) with P\in{\bf{P}}_{n} , c_{i}\in{\bf{C}} for 1\leq i\leq n , and \mathcal{T} is a finite set of first-order logic (FOL) sentences built from {\bf{P}} , {\bf{C}} and {\bf{V}} . We denote by \mathsf{sig}(\mathcal{K}) and \mathsf{const}(\mathcal{K}) (resp. \mathsf{sig}(\mathcal{D}) , \mathsf{const}(\mathcal{D}) ) the set of predicates and constants that occur in \mathcal{K} (resp. in \mathcal{D} ). A KB \mathcal{K}=(\mathcal{D},\mathcal{T}) is consistent , and \mathcal{D} is called \mathcal{T} -consistent , if \mathcal{D}\cup\mathcal{T} has some model. Otherwise, \mathcal{K} is inconsistent , denoted \mathcal{K}\models\bot . Typically, \mathcal{T} will be either an ontology (formulated in some description logic or decidable class of existential rules) or a set of database constraints . In particular, we consider: • Description logics of the DL-Lite family [ 2007 ] , such as DL-Lite core , whose axioms take the form \mathsf{B}_{1}\sqsubseteq(\neg)\mathsf{B}_{2} , with \mathsf{B}_{i}\in{\bf{P}}_{1}\cup\{\exists\mathsf{R},\exists\mathsf{R}^{-}\mid\mathsf{R}\in{\bf{P}}_{2}\} . • Denial constraints of the form \alpha_{1}\wedge\ldots\wedge\alpha_{n}\rightarrow\bot , where each \alpha_{i} is a relational or inequality atom, which includes in particular functional dependencies (FDs) such as P(x,y,z)\wedge P(x,y,z^{\prime})\wedge z\neq z^{\prime}\rightarrow\bot . Queries A conjunctive query (CQ) is a conjunction of relational atoms P(t_{1},\ldots,t_{n}) ( P\in{\bf{P}}_{n} , t_{i}\in{\bf{C}}\cup{\bf{V}} ), where some variables may be existentially quantified. Given a query q(\vec{x}) , with free variables \vec{x} , and a tuple of constants \vec{a} such that |\vec{a}|=|\vec{x}| , q(\vec{a}) denotes the first-order sentence obtained by replacing each variable in \vec{x} by the corresponding constant in \vec{a} . A (certain) answer to q(\vec{x}) over \mathcal{K} is a tuple \vec{a}\in\mathsf{const}(\mathcal{K})^{|\vec{x}|} such that q(\vec{a}) holds in every model of \mathcal{K} , denoted \mathcal{K}\models q(\vec{a}) . A cause for q(\vec{a}) w.r.t. \mathcal{K}=(\mathcal{D},\mathcal{T}) is an inclusion-minimal \mathcal{T} -consistent subset \mathcal{C}\subseteq\mathcal{D} such that (\mathcal{C},\mathcal{T})\models q(\vec{a}) . The set of causes for q(\vec{a}) w.r.t. \mathcal{K} is denoted by \mathit{Causes}(q(\vec{a}),\mathcal{K}) . Conflicts and repairs A conflict of \mathcal{K}=(\mathcal{D},\mathcal{T}) is an inclusion-minimal subset \mathcal{D}^{\prime}\subseteq\mathcal{D} such that (\mathcal{D}^{\prime},\mathcal{T})\models\bot . The set of conflicts of \mathcal{K} is denoted \mathit{Conf}(\mathcal{K}) . A (subset) repair of \mathcal{K} is an inclusion-maximal subset \mathcal{R}\subseteq\mathcal{D} such that (\mathcal{R},\mathcal{T})\not\models\bot . The set of repairs of \mathcal{K} is denoted \mathit{SRep}(\mathcal{K}) . Prioritized KBs A priority relation \succ for a KB \mathcal{K}=(\mathcal{D},\mathcal{T}) is an acyclic 1 1 1 In line with existing work on prioritized repairs, we do not require priority relations to be transitive. binary relation over the facts of \mathcal{D} such that if \alpha\succ\beta , then there exists \mathcal{C}\in\mathit{Conf}(\mathcal{K}) such that \{\alpha,\beta\}\subseteq\mathcal{C} . It is total if for every pair \alpha\neq\beta such that \{\alpha,\beta\}\subseteq\mathcal{C} for some \mathcal{C}\in\mathit{Conf}(\mathcal{K}) , either \alpha\succ\beta or \beta\succ\alpha . A completion of \succ is a total priority relation \succ^{\prime}\ \supseteq\ \,\succ . A prioritized KB \mathcal{K}_{\succ} is a KB \mathcal{K} with a priority relation \succ for \mathcal{K} . Priority relations are used to select optimal repairs. We recall the notions of Pareto- and completion-optimal repairs 2 2 2 Staworko et al. ( ? ) further introduces a third notion

Read the complete text