=Paper=
{{Paper
|id=Vol-3739/invited-1
|storemode=property
|title=Querying Inconsistent Prioritized Data (Abstract of Invited Talk)
|pdfUrl=https://ceur-ws.org/Vol-3739/invited-1.pdf
|volume=Vol-3739
|authors=Camille Bourgaux
|dblpUrl=https://dblp.org/rec/conf/dlog/Bourgaux24
}}
==Querying Inconsistent Prioritized Data (Abstract of Invited Talk)==
https://ceur-ws.org/Vol-3739/invited-1.pdf
Querying Inconsistent Prioritized Data
Camille Bourgaux1
1
DI ENS, ENS, CNRS, PSL University & Inria, 45 rue dβUlm, 75005 Paris, France
Abstract
This extended abstract accompanies an invited talk at DL 2024 and presents a summary of some recent
results on querying inconsistent prioritized data.
Keywords
inconsistency handling, prioritized data, optimal repairs
Real-world datasets are plagued by data quality issues which may render the data inconsistent
w.r.t. a set of constraints, be they given by database dependencies or ontologies. A prominent
way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain
meaningful answers to queries [1, 2, 3]. Most of these semantics are based on the notion of
a (subset) repair, which is an inclusion-maximal subset of the data that is consistent with the
constraints. In many scenarios, this basic notion of repair can be refined by exploiting preference
information about facts. Preferred repairs can then be used in place of subset repairs in any
repair-based semantics. This paper presents a summary of some recent results [4, 5, 6] on an
approach where preferences are given by a binary priority relation between conflicting facts [7].
Formal definitions A knowledge base (KB) π¦ = (π, π― ) consists of a dataset π and a logical
theory π― : π is a finite set of facts, and π― a finite set of first-order logic (FOL) sentences.
Typically, π― is an ontology, e.g., in description logic, or a set of database constraints, e.g., denial
constraints of the form βπ₯β Β¬(πΌ1 β§ . . . β§ πΌπ ), where each πΌπ is a relational or inequality atom. A
KB π¦ = (π, π― ) is consistent if π βͺ π― has a model, and inconsistent otherwise (π¦ |= β₯). A set
of facts β¬ is π― -consistent if (β¬, π― ) is consistent. A conflict of π¦ is an inclusion-minimal subset
π β π such that (π, π― ) |= β₯; Conf (π¦) denotes the set of conflicts of π¦. A (subset) repair of
π¦ = (π, π― ) is an inclusion-maximal π― -consistent subset β β π; SRep(π¦) denotes the set of
repairs of π¦. Following [7], we assume that preferences between conflicting facts are available:
Definition 1. A priority relation β» for a KB π¦ = (π, π― ) is an acyclic binary relation over π
such that πΌ β» π½ implies {πΌ, π½} β π for some π β Conf (π¦). It is total if for all πΌ ΜΈ= π½ such that
{πΌ, π½} β π for some π β Conf (π¦), either πΌ β» π½ or π½ β» πΌ. A completion of β» is a total priority
relation β»β² β β». A prioritized KB π¦β» is a KB π¦ = (π, π― ) with a priority relation β» for π¦.
Definition 2 (Optimal repairs). Let π¦β» be a prioritized KB with π¦ = (π, π― ) and β β SRep(π¦).
A Pareto improvement of β is a π― -consistent β¬ β π such that there is π½ β β¬ β β with π½ β» πΌ
for every πΌ β β β β¬. A global improvement of β is a π― -consistent β¬ β π such that β¬ =ΜΈ β and
for every πΌ β β β β¬, there exists π½ β β¬ β β such that π½ β» πΌ. The repair β is:
DL 2024: 37th International Workshop on Description Logics, June 18β21, 2024, Bergen, Norway
$ camille.bourgaux@ens.fr (C. Bourgaux)
0000-0002-8806-6682 (C. Bourgaux)
Β© 2024 Copyright for this paper by its author. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Table 1
Data complexity [7, 4, 5]. Upper bounds hold for conjunctive queries and FOL fragments for which
consistency checking and BCQ entailment is in P. Lower bounds hold for atomic queries and any
fragment that extends DL-Litecore or functional dependencies.
Globally-optimal Pareto-optimal Completion-optimal
AR, IAR Ξ π2 -complete coNP-complete coNP-complete
Brave Ξ£π2 -complete NP-complete NP-complete
β’ Pareto-optimal if there is no Pareto improvement of β;
β’ globally-optimal if there is no global improvement of β;
β’ completion-optimal if β is a globally-optimal repair of π¦β»β² , for some completion β»β² of β».
We denote by PRep(π¦β» ), GRep(π¦β» ) and CRep(π¦β» ) the sets of Pareto-, globally- and completion-
optimal repairs. It holds that CRep(π¦β» ) β GRep(π¦β» ) β PRep(π¦β» ) β SRep(π¦).
If β» is induced by assigning scores to facts, then Pareto-, globally- and completion-optimal
repairs coincide [8, 9], and also coincide with the βπ -repairs from [10].
A Boolean conjunctive query (BCQ) π is entailed by a KB π¦ (π¦ |= π) if π holds in every model
of π¦. Hence, π¦ |= β₯ implies that π¦ |= π for every π. Meaningful answers can be obtained from
inconsistent KBs by using inconsistency-tolerant semantics based on repairs. The AR semantics
defines plausible query answers, and is used for consistent query answering in databases [11].
The brave semantics considers all possible answers, while the IAR semantics identifies the most
reliable ones. These semantics can be parametrized by the type of repair they consider.
Definition 3 (Inconsistency-tolerant semantics). Fix X β {π, π, πΊ, πΆ} and consider a prioritized
KB π¦β» with π¦ = (π, π― ) and a BCQ π. Then π is entailed by π¦β» under
β’ X-AR semantics, denoted π¦β» |=πAR π, if (β, π― ) |= π for every β β XRep(π¦β» );
β’ X-brave semantics, denoted π¦β» |=πbrave π, if (β, π― ) |= π for some β β XRep(π¦β» );
π
βοΈ
β’ X-IAR semantics, denoted π¦β» |=πΌπ΄π
π, if (β¬, π― ) |= π where β¬ = ββXRep(π¦β» ) β.
The semantics are related as follows: π¦β» |=π π π
πΌπ΄π
π β π¦β» |=AR π β π¦β» |=brave π.
Table 1 gives the data complexity of BCQ entailment under optimal repair-based semantics.1
Note that S-AR entailment is coNP-hard even in very basic settings [12, 13], while S-brave or
S-IAR entailment is tractable for DL-Lite ontologies or denial constraints [14].
Practical SAT-based approaches [5] The (co)NP complexity results naturally suggest the
interest of employing SAT solvers to compute query answers under X-AR, X-brave and X-IAR
semantics for X β {P, C}, as it has already be done for S-AR [15, 16]. There are several ways
of employing SAT encodings to compute answers under (optimal) repair-based semantics, by
exploiting different reasoning modes of SAT solvers. The orbits system implements different
algorithms and encodings for the case where conflicts are binary. It takes as input the conflicts,
1
The lower bound for G-IAR and G-brave with functional dependencies follows from the proof of [7, Theorem 2].
priority relation, and the potential query answers associated with their causes, where a cause
for π is a minimal π― -consistent subset π β π such that (π, π― ) |= π. Our experimental
comparison shows that the choice of algorithm and encoding variant may have huge impact
on the computation time. Moreover, while in some cases our results can be used to single out
some approaches as more effective, more often there are no clear winner(s). For example, we
consider two ways of encoding the absence of a cause, and choosing one instead of the other
may make a notable difference, but which one is best depends on the KB and query.
Connections with abstract argumentation [4] An argumentation framework (AF) is a pair
(Args, β) where Args is a finite set of arguments and β β Args Γ Args is the attack relation:
πΌ attacks π½ if πΌ β π½. The semantics of AFs is based on extensions, which can be seen as
coherent sets of arguments. Many notions of extension have been considered, in particular
preferred extensions and stable extensions [17]. When these two kinds of extension coincide, the
AF is called coherent. We define preference-based set-based argumentation framework (PSETAF),
a variant of AF based on collective attacks with a preference relation between arguments. We
exhibit a natural translation of a prioritized KB π¦β» into a PSETAF πΉπ¦,β» that uses π as the
arguments and show that β β PRep(π¦β» ) iff it is a stable extension of πΉπ¦,β» . Moreover, if β» is
transitive or if π¦ has only binary conflicts, then πΉπ¦,β» is coherent so β β PRep(π¦β» ) iff it is a
preferred extension of πΉπ¦,β» . Since there is no notion of extension that corresponds to globally-
or completion-optimal repairs, this speaks to the interest of adopting Pareto-optimal repairs.
The argumentation connection allows us to propose a new notion of grounded repair, directly
inspired by the grounded extension from argumentation. The (unique) grounded repair is
contained in the intersection of Pareto-optimal repairs and can be computed in polynomial time
from the dataset and conflicts. Moreover, it is more productive than the Elect semantics [18]
and lies between the non-defeated and the prioritized inclusion-based non-defeated repairs that
have been proposed in the case where the priority relation is score structured [19].
Connections with active integrity constraints [6] In the database setting, active integrity
constraints (AICs) state how to resolve constraint violations [20, 21]. A ground AIC is a formula
of the form πΌ1 β§ Β· Β· Β· β§ πΌπ β§ Β¬π½1 β§ Β· Β· Β· β§ Β¬π½π β {π΄1 , . . . , π΄π } where the πΌπ , π½π are facts and
each π΄π is an update action of the form βπΌπ for some 1 β€ π β€ π or +π½π for some 1 β€ π β€ π.
The semantics of a set of AICs is based on the notion of a repair update, defined as a minimal
set π° of update actions such that π β {πΌ | βπΌ β π°} βͺ {πΌ | +πΌ β π°} satisfies the constraints.
Many proposals have been made to select the appropriate repair updates to take into account a
set of AICs, such as founded, well-founded, grounded and justified repair updates.
Given a prioritized database (i.e., a prioritized KB such that π― is a set of database constraints),
we construct a set of ground AICs such that the Pareto-optimal repairs coincide with the repairs
obtained by applying founded, grounded and justified repair updates w.r.t. the generated set of
AICs. We also exhibit a translation of a βwell-behavedβ set of AICs into a prioritized database
and again relate Pareto-optimal repairs with founded, grounded and justified repair updates.
We take this as further evidence that Pareto-optimal repairs are an especially natural notion.
These results hold not only for denial constraints but also for universal constraints of the
form βπ₯ β Β¬(πΌ1 β§ . . . β§ πΌπ β§ Β¬π½1 β§ Β· Β· Β· β§ Β¬π½π ), where repairs can also be obtained by adding
facts (while minimizing the symmetric difference with the original database). Such constraints
and repairs could be explored in the KB setting, e.g., for ontologies with closed predicates [22].
Acknowledgments
I thank the DL 2024 workshop chairs for inviting me. The work summarized in this extended
abstract has been conducted together with Meghyn Bienvenu (CNRS & University of Bordeaux)
and supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014).
References
[1] M. Bienvenu, C. Bourgaux, Inconsistency-tolerant querying of description logic knowledge
bases, in: Tutorial Lectures of the 12th International Reasoning Web Summer School, 2016.
[2] M. Bienvenu, A short survey on inconsistency handling in ontology-mediated query
answering, KΓΌnstliche Intelligenz 34 (2020) 443β451.
[3] J. Wijsen, Foundations of query answering on inconsistent databases, SIGMOD Record 48
(2019) 6β16.
[4] M. Bienvenu, C. Bourgaux, Querying and repairing inconsistent prioritized knowledge
bases: Complexity analysis and links with abstract argumentation, in: Proceedings of the
17th International Conference on Principles of Knowledge Representation and Reasoning
(KR), 2020.
[5] M. Bienvenu, C. Bourgaux, Querying inconsistent prioritized data with ORBITS: algorithms,
implementation, and experiments, in: Proceedings of the 19th International Conference
on Principles of Knowledge Representation and Reasoning (KR), 2022.
[6] M. Bienvenu, C. Bourgaux, Inconsistency handling in prioritized databases with universal
constraints: Complexity analysis and links with active integrity constraints, in: Proceed-
ings of the 20th International Conference on Principles of Knowledge Representation and
Reasoning, (KR), 2023.
[7] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query
answering in relational databases, Annals of Mathematics and Artificial Intelligence
(AMAI) 64 (2012) 209β246.
[8] E. Livshits, B. Kimelfeld, Counting and enumerating (preferred) database repairs, in: Pro-
ceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database
Systems (PODS), 2017.
[9] C. Bourgaux, Inconsistency Handling in Ontology-Mediated Query Answering. (Ges-
tion des incohΓ©rences pour lβaccΓ¨s aux donnΓ©es en prΓ©sence dβontologies), Ph.D. thesis,
University of Paris-Saclay, France, 2016.
[10] M. Bienvenu, C. Bourgaux, F. GoasdouΓ©, Querying inconsistent description logic knowledge
bases under preferred repair semantics, in: Proceedings of the 28th AAAI Conference on
Artificial Intelligence (AAAI), 2014.
[11] L. E. Bertossi, Database Repairing and Consistent Query Answering, Synthesis Lectures
on Data Management, Morgan & Claypool Publishers, 2011.
[12] S. Arming, R. Pichler, E. Sallinger, Complexity of repair checking and consistent query
answering, in: Proceedings of the 19th International Conference on Database Theory
(ICDT), 2016.
[13] M. Bienvenu, On the complexity of consistent query answering in the presence of simple
ontologies, in: Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI),
2012.
[14] M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust
ontology-based data access, in: Proceedings of the 23rd International Joint Conference on
Artificial Intelligence (IJCAI), 2013.
[15] M. Bienvenu, C. Bourgaux, F. GoasdouΓ©, Computing and explaining query answers over
inconsistent DL-Lite knowledge bases, Journal of Artificial Intelligence Research (JAIR)
64 (2019) 563β644.
[16] A. A. Dixit, P. G. Kolaitis, A SAT-based system for consistent query answering, in: Pro-
ceedings of the 22nd International Conference on Theory and Applications of Satisfiability
Testing (SAT), 2019.
[17] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321β358.
[18] S. Belabbes, S. Benferhat, J. Chomicki, Elect: An inconsistency handling approach for
partially preordered lightweight ontologies, in: Proceedings of the 15th International
Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR), 2019.
[19] S. Benferhat, Z. Bouraoui, K. Tabia, How to select one preferred assertional-based repair
from inconsistent and prioritized DL-Lite knowledge bases?, in: Proceedings of the 24th
International Joint Conference on Artificial Intelligence (IJCAI), 2015.
[20] S. Flesca, S. Greco, E. Zumpano, Active integrity constraints, in: Proceedings of the
6th International ACM SIGPLAN Conference on Principles and Practice of Declarative
Programming (PPDP), 2004.
[21] B. Bogaerts, L. Cruz-Filipe, Fixpoint semantics for active integrity constraints, Artif. Intell.
255 (2018) 43β70.
[22] C. Lutz, I. Seylan, F. Wolter, The data complexity of ontology-mediated queries with closed
predicates, Log. Methods Comput. Sci. 15 (2019).