Querying Inconsistent Prioritized Data

Abstract

This extended abstract accompanies an invited talk at DL 2024 and presents a summary of some recent results on querying inconsistent prioritized data. 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:

Keywords

• eol>inconsistency handling
• prioritized data
• optimal repairs

-

• 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 completionoptimal 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 . 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 diferent reasoning modes of SAT solvers. The orbits system implements diferent algorithms and encodings for the case where conflicts are binary. It takes as input the conflicts, 1The 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 efective, 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 diference, 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(≻ ) if it is a stable extension of ,≻ . Moreover, if ≻ is transitive or if has only binary conflicts, then ,≻ is coherent so ℛ ∈ PRep(≻ ) if it is a preferred extension of ,≻ . Since there is no notion of extension that corresponds to globallyor 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 diference 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). 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: Proceedings 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).

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: Proceedings 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: Proceedings 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. (Gestion 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