=Paper=
{{Paper
|id=Vol-3739/abstract-13
|storemode=property
|title=A Principle-based Framework for Repair Selection in Inconsistent Ontologies (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3739/abstract-13.pdf
|volume=Vol-3739
|authors=Said Jabbour,Yue Ma,Badran Raddaoui
|dblpUrl=https://dblp.org/rec/conf/dlog/Jabbour0R24
}}
==A Principle-based Framework for Repair Selection in Inconsistent Ontologies (Extended Abstract)==
https://ceur-ws.org/Vol-3739/abstract-13.pdf
A Principle-based Framework for Repair Selection in
Inconsistent Ontologies (Extended Abstract)
Said Jabbour1 , Yue Ma2 and Badran Raddaoui3
1
CRIL, CNRS UMR 8188, Université d’Artois, France
2
LISN, CNRS UMR 9015, Université Paris-Saclay, France
3
SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, France
Abstract
This paper investigates a general principle-based framework for retrieving preferred repairs from inconsistent
ontologies under a broad family of strategies. To begin with, we define a set of principles that ensure rational
behaviours of repair selection strategies. Then, we classify the strategies into two basic categories: (i) ranking
repairs without requiring formula information; and (ii) ranking repairs based on formula information. Based on
this classification, we introduce several novel repair selection strategies and show that our framework encompasses
a range of popular existing strategies. Additionally, through a systematical analysis of these selection strategies
using the proposed principles, we conclude that our principles allow for effective discrimination among the
strategies. Finally, preliminary experimental results are presented to show the feasibility of our proposed
framework.
Keywords
Ontologies, Inconsistency handling, Preferred repairs, Rationality principle
1. Introduction
The study of preferences has a long tradition in various disciplines. It has been recently applied in
query answering over databases [1], propositional logic knowledge bases (KBs) [2, 3], description logic
KBs [4, 5, 6], and the existential rule language [7]. In this context, these existing proposals rely on the
concept of repairs, that is, the ⊆-maximal consistent subsets of formulas.
The need of retrieving preferred repairs is justified by numerous issues associated with using all
repairs. The primary drawback of reasoning with all repairs stems from their typically large numbers
in real-world applications [8]. Moreover, repairs are often not equally important in practice. For
example, when one data source is more reliable than another or when new information is preferred over
earlier ones [9]. We may also prefer one repair over another if it contains less problematic information
[10, 11, 12, 13, 14, 15, 16]. Therefore, in this paper, we turn our attention to how to choose the most
preferred repairs among all the potential repairs of an inconsistent KB, while filtering out undesired
repairs. Unlike [5], and in line with [4, 6, 17, 7], we aim to guarantee that the retrieved consistent
subsets are still ⊆-maximal.
Despite their success, the aforementioned proposals on preferred repairs-based query answering
have been generally developed using ad hoc repair selection strategies. A basic strategy is based on
the cardinality of repairs. More advanced strategies often use some aggregation functions of formula
information (e.g., weight, priority level, inconsistency measure), either provided as system inputs or
computed from the given KB. Without being limited to aggregation functions, this paper provides a
complementary principle-based framework that allows us to define different repair selection strategies to
retrieve preferred repairs from inconsistent KBs. This paper makes the following concrete contributions:
• We propose a set of logical principles that guarantee rational behaviours of repair selection
strategies.
DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway
*
Corresponding author.
†
These authors contributed equally.
$ jabbour@cril.fr (S. Jabbour); ma@lisn.fr (Y. Ma); badran.raddaoui@telecom-sudparis.eu (B. Raddaoui)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
• We present various repair selection strategies that allow for comparing repairs using solely the
internal structure of a KB.
• We evaluate the different repair selection strategies against the proposed principles (Table 1),
showing that these principles allow for an effective discrimination among different strategies.
The extended version of this paper has been accepted by the International Conference on Autonomous
Agents and Multi-agent Systems (AAMAS 2024) [18].
2. Principle-based framework for repair selection
Our framework is not restricted to a particular logic language, but we consider here Description Logics
(DL) and write K for the set of all DL-based KBs.
Definition 1. For a DL KB 𝒦 = ⟨𝒯 , 𝒜⟩, an ABox repair is a ⊆-maximal subset 𝒜′ of 𝒜 such that 𝒯 ∪ 𝒜′
is consistent. An ABox conflict is a ⊆-minimal subset 𝒜′′ of 𝒜 s.t. ⟨𝒯 , 𝒜′′ ⟩ |= ⊥. We denote by ℛ(𝒦)
and 𝒞(𝒦) the set of all possible repairs and conflicts of 𝒦, respectively.
In what follows, the repairs of a given KB will be ordered according to some criteria to determine
only the most desired ones. More formally, our framework returns the set of preferred repairs among
the (large) candidate set of repairs by taking as input three basic elements:
• a knowledge base 𝒦 ∈ K,
• a formula characterisation 𝑐ℎ over formulas in ℒ: 𝑐ℎ can be a binary function or relation over
Form(ℒ), e.g., a weight, a distance, or a priority relation between two formulas. Though 𝑐ℎ
could be arbitrary, the following property is natural for 𝑐ℎ to satisfy: If 𝛼 ≡ 𝛼′ and 𝛽 ≡ 𝛽 ′ , then
𝑐ℎ(𝛼, 𝛽) = 𝑐ℎ(𝛼′ , 𝛽 ′ ).
• a repair comparison strategy, written ≽𝑠 ⊆ ℛ(𝒦) × ℛ(𝒦), to compare the repairs of 𝒦.
Definition 2. Let 𝒦 ∈ K and 𝑅, 𝑅′ ∈ ℛ(𝒦). A repair comparison strategy ≽𝑠 is an acyclic preference
relation over ℛ(𝒦) with 𝑅 ≽𝑠 𝑅′ , meaning that 𝑅 is preferred over 𝑅′ . Given a relation 𝑐ℎ, a repair
selection function is a mapping ℱ : 𝒦 × 𝑐ℎ× ≽𝑠 → Ξ s.t. Ξ ∈ 2ℛ(𝒦) .
An optimal repair selection function is a repair selection function ℱ such that there is no 𝑅 ∈
ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) and 𝑅′ ∈ (ℛ(𝒦) ∖ ℱ(𝒦, 𝑐ℎ, ≽𝑠 )) such that 𝑅′ ≻𝑠 𝑅.
Rationality Principles Definition 2 is general enough regarding the repair comparison strategy
≽𝑠 and the formula characterisation 𝑐ℎ. To restrict the possible candidates, we first establish a set of
desiderata that a suitable optimal repair selection function ℱ should fullfil. Such formal principles are
important for defining, characterizing, and comparing selection functions. We refer the long version
of the paper for the intuitions underlying these principles: Abstraction: For any 𝒦 ∈ K and any
isomorphism1 𝛾, we have that ∀𝑅 ∈ ℛ(𝒦), 𝑅 ∈ ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) iff 𝛾(𝑅) ∈ ℱ(𝛾(𝒦), 𝑐ℎ, ≽𝑠 ).
Equivalence Invariance: For 𝒦1 , 𝒦2 ∈ K, if 𝒦1 ∼ = 𝒦2 , then for each 𝑅 ∈ ℱ(𝒦1 , 𝑐ℎ, ≽𝑠 ), there exists
𝑅′ ∈ ℱ(𝒦2 , 𝑐ℎ, ≽𝑠 ) s.t. 𝑅 ∼
=⋃︀𝑅′ .
Coverness: For any KB 𝒦, 𝑅∈ℱ (𝒦,𝑐ℎ,≽𝑠 ) 𝑅 = 𝒦.
Non-Emptiness: ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) ̸= ∅, if ℛ(𝒦) ̸= ∅.
Monotonicity: If 𝑐ℎ1 , 𝑐ℎ2 are two relations s.t. 𝑐ℎ2 ⊆ 𝑐ℎ1 , then ℱ(𝒦, 𝑐ℎ1 , ≽𝑠 ) ⊆ ℱ(𝒦, 𝑐ℎ2 , ≽𝑠 ).
Non-Discrimination: ℱ(𝒦, 𝑐ℎ, ∅) = ℛ(𝒦).
Reducibility: If 𝒦 ⊢ ⊥, then ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) ⊂ ℛ(𝒦).
Consistency: If 𝒦 ̸⊢ ⊥, then ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) = {𝒦}.
Improvement: Given 𝒦, 𝒦′ ∈ K, if 𝒦 ⊆ 𝒦′ , then for any 𝑅 ∈ ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) and 𝑅′ ∈ ℱ(𝒦′ , 𝑐ℎ, ≽𝑠 ),
𝑅 ̸≻𝑠 𝑅′ .
Stability: Given 𝒦, 𝒦′ ∈ K, if 𝒦 ⊆ 𝒦′ , for any 𝑅 ∈ ℱ(𝒦, 𝑐ℎ, ≽𝑠 ), there exists 𝑅′ ∈ ℱ(𝒦′ , 𝑐ℎ, ≽𝑠 )
1
The isomorphism 𝛾 renames all the variables (i.e., concept, role names, and instances). We apply 𝛾 to formulas and knowledge
bases.
such that 𝑅 ⊆ 𝑅′ .
Uniqueness: |ℱ(𝒦, 𝑐ℎ, ≽𝑠 )| = 1.
Non-Triviality: There is 𝒦 ∈ K such that ℱ(𝒦, 𝑐ℎ, ≽𝑠 ) ⊂ℛ(𝒦).
The intuition about the principles is as follows: The Equivalence Invariance concerns the main
intuition behind the logical equivalence between two sets of formulas. It ensures that two equivalent
KBs exhibit the same behaviour according to the function ℱ. The Coverness principle requires that a KB
should be covered by its preferred repairs, i.e., each formula in 𝒦 must belong to at least one preferred
repair. The Non-Emptiness principle says that an optimal repair selection strategy ℱ must return at
least one preferred repair. Monotonicity implies that looking at richer preferences among formulas
can only narrow down the set of preferred repairs. The Non-Discrimination principle states that the
preferred repairs are the set of all repairs when no repair comparison strategy is expressed. Reducibility
claims that there always exists a manner to remove certain repairs from being the selected preferred
ones. Consistency states that if a KB is consistent, then the only preferred repair is the base itself.
The Improvement principle says that the expansion of a KB can only result in better preferred repairs
according to ≽𝑠 . The Stability principle states that the expansion of a KB 𝒦 preserves all the formulas
involved in the preferred repairs of 𝒦. Uniqueness says that an optimal repair selection strategy should
return one unique preferred repair. Finally, the Non-Triviality principle is to avoid repair selection
functions that do not discriminate between repairs and return all repairs for any KB 𝒦.
Table 1 details the principles satisfied by different repair selection functions discussed below. In the
table, we highlight DL-Lite, for which ABox conflict sets are always binary, i.e., |𝒞(𝒦)| = 2.
3. Categories of selection strategies
We distinguish two categories of selection repair strategies: the ones defined on a given 𝑐ℎ as in many
existing work; and the ones independent of 𝑐ℎ for the setting where no formula information is available.
The former includes improvement-based strategies [1, 17] and the scoring function-based strategy
≥score [2]. We focus on presenting the other category here.
Table 1 √ √*
Principles vs. repair selection strategies: (resp. ) means that the strategy satisfies the property
(resp. under certain conditions), ⊗ stands for unsatisfaction, and NA means inapplicability.
Principles ≽card ≽#
comp ≽⊇
comp ≽cover
√ √ √
Abstraction √ √
Equivalence Invariance ⊗ √
Coverness ⊗
√ ⊗
√ √
Non-Emptiness √ √ √
Monotonicity √ √ √
Non-Discrimination
Reducibility ⊗
√ ⊗
√ ⊗
√
Consistency √ √
Improvement √ (DL-Lite), ⊗ (in general) ⊗
Stability ⊗ (DL-Lite), ⊗ (in general) ⊗
Uniqueness ⊗
√ ⊗√ ⊗
√
Non-Triviality ⊗ (DL-Lite), (in general)
𝑐ℎ-Free Selection Strategies A straightforward way for filtering preferred repairs without using 𝑐ℎ
involves employing a cardinality-based criterion [4] that can be formalized in our notation as follows.
Given two repairs 𝑅, 𝑅′ ∈ ℛ(𝒦), 𝑅 ≽card 𝑅′ iff. |𝑅| ≥ |𝑅′ |. The key idea underlying the cardinality-
based method is to retain as many information as possible. A problem with ≽card is that no account is
taken of the possible interaction between repairs of a given KB.
So we propose a strategy called compatibility-based strategy that compares all pairs of repairs based
on the next criterion: We prefer the repairs having more compatibility with other repairs, i.e., opposed
by less repairs by ignoring their intersection. Formally,
Definition 3. Let 𝒦 ∈ K and 𝑅 ∈ ℛ(𝒦). The compatible set of 𝑅 w.r.t. ℛ(𝒦), written comp(𝑅, 𝒦),
is defined as comp(𝑅, 𝒦) = {𝑅′ ∈ ℛ(𝒦) | (𝑅 ∖ 𝑅′ ) ∪ (𝑅′ ∖ 𝑅) ̸⊢ ⊥}. Then for 𝑅, 𝑅′ ∈ ℛ(𝒦),
𝑅 is preferred to 𝑅′ by cardinality (resp. set-inclusion), written 𝑅 ≽# ′ ⊇ ′
comp 𝑅 (resp. 𝑅 ≽comp 𝑅 ), iff.
′
|comp(𝑅, 𝒦)| ≥ |comp(𝑅 , 𝒦)| (resp. comp(𝑅, 𝒦) ⊇ comp(𝑅 , 𝒦)). ′
Unfortunately, the compatibility-based strategies are not specifically geared toward DL-Lite. In fact,
the notion of compatible set of a repair is trivial because it becomes a singleton and only contains the
repair itself. This result also explains the violation of Non-Triviality and satisfaction of Stability of
≽𝑥comp (𝑥 ∈ {#, ⊆}) for DL-Lite.
Another strategy without using 𝑐ℎ is called cover-based strategy that aims to selecting among
the repairs the ones covering the KB. The coverness in ⋃︀ KBs is defined as follows: Given a KB 𝒦,
Γ = {𝒦1 , . . . , 𝒦𝑛 | 𝒦𝑖 ⊆ 𝒦, 1 ≤ 𝑖 ≤ 𝑛} is a cover of 𝒦 iff 1≤𝑖≤𝑛 𝒦𝑖 = 𝒦. A cover Γ of 𝒦 is minimal
if there exists no other cover Γ′ of 𝒦 s.t. Γ′ ⊂ Γ. We call Γ a minimal repair cover of 𝒦, if 𝒦𝑖 ∈ ℛ(𝒦)
for 1 ≤ 𝑖 ≤ 𝑛. We write cover(𝒦) for the set of minimal repair covers of 𝒦.
Definition 4. Let 𝒦 ∈ K. For two repairs 𝑅, 𝑅′ ∈ ℛ(𝒦), we say that 𝑅 ≽cover 𝑅′ if there is Γ ∈ cover(𝒦)
such that 𝑅 ∈ Γ.
This definition implies that the set of the preferred repairs will be the union of minimal covers, i.e.,
ℱ(𝒦, ∅, ≽cover ) = Γ∈cover(𝒦) Γ. Moreover, we have examples showing that even for the language
⋃︀
{#,⊆}
with binary conflict property, which makes 𝑅 ≽comp 𝑅′ strategy trivial, the ≽cover strategy is still
able to give non-trivial results.
Feasibility study We presented above several novel strategies for selecting preferred repairs. Table 1
summarises the repair selection strategies and their satisfaction of a rich set of rationality principles. It
shows that our principles give an effective way to discriminate among these optimal repair selection
strategies.
A preliminary empirical study compares the compatibility-based and the cardinality-based strategies
for a real-world KB constructed using the National Downloadable File given by the Centers for Medicare
and Medicaid Services2 , as outlined in [19]. We conclude that computing preferred repairs is a feasible
task.
Acknowledgments
This work was funded, in part, by the Agence Nationale de la Recherche ANR under grant EXPIDA:
ANR-22-CE23-0017.
References
[1] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering
in relational databases, Ann. Math. Artif. Intell. 64 (2012) 209–246.
[2] S. Konieczny, P. Marquis, S. Vesic, Rational inference relations from maximal consistent subsets
selection, in: IJCAI, 2019, pp. 1749–1755.
[3] B. Raddaoui, C. Straßer, S. Jabbour, A comparative study of ranking formulas based on consistency,
in: IJCAI, 2023, pp. 3330–3337.
[4] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases
under preferred repair semantics, in: AAAI, 2014, pp. 996–1002.
[5] S. Benferhat, Z. Bouraoui, K. Tabia, How to select one preferred assertional-based repair from
inconsistent and prioritized dl-lite knowledge bases?, in: IJCAI, 2015, pp. 1450–1456.
2
https://data.cms.gov/provider-data/
[6] B. Yun, S. Vesic, M. Croitoru, P. Bisquert, Inconsistency measures for repair semantics in OBDA,
in: J. Lang (Ed.), IJCAI, 2018, pp. 1977–1983.
[7] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query
answering under existential rules, Artif. Intell. 312 (2022) 103772.
[8] B. Nebel, Belief revision and default reasoning: Syntax-based approaches, in: KR, 1991, pp.
417–428.
[9] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query
answering under existential rules, in: KR, 2020, pp. 203–212.
[10] A. Hunter, S. Konieczny, Measuring inconsistency through minimal inconsistent sets, in: KR, 2008,
pp. 358–366.
[11] S. Jabbour, B. Raddaoui, Measuring inconsistency through minimal proofs, in: ECSQARU, 2013,
pp. 290–301.
[12] B. Raddaoui, On the measure of conflicts: an argumentation-based framework, J. Appl. Non Class.
Logics 28 (2018) 240–259.
[13] S. Jabbour, Y. Ma, B. Raddaoui, Handling disagreement in ontologies-based reasoning via argu-
mentation, in: Web Information Systems Engineering - WISE, 2019, pp. 389–406.
[14] J. S. Ribeiro, M. Thimm, Consolidation via tacit culpability measures: Between explicit and implicit
degrees of culpability, in: KR, 2021, pp. 529–538.
[15] S. Jabbour, Y. Ma, B. Raddaoui, A framework for reasoning about uncertainty in ontologies, IEEE
Intell. Syst. 37 (2022) 27–37.
[16] J. Heyninck, B. Raddaoui, C. Straßer, Ranking-based argumentation semantics applied to logical
argumentation, in: IJCAI, 2023, pp. 3268–3276.
[17] M. Bienvenu, C. Bourgaux, Querying and repairing inconsistent prioritized knowledge bases:
Complexity analysis and links with abstract argumentation, in: KR, 2020, pp. 141–151.
[18] S. Jabbour, Y. Ma, B. Raddaoui, Towards a principle-based framework for repair selection in
inconsistent knowledge bases, in: AAMAS, 2024, pp. 907–915.
[19] M. Bienvenu, C. Bourgaux, Querying Inconsistent Prioritized Data with ORBITS: Algorithms,
Implementation, and Experiments, in: KR, 2022.