Inconsistency-tolerant semantics are approaches to provide meaningful answers to queries even in the presence of inconsistent knowledge. Several such semantics rely on the notion of a repair, which is a “maximal” consistent subset of the database, where diferent maximality criteria might be adopted depending on the application at hand. Common maximality criteria assume that all facts in a database are equally important. However, in several real-world applications, it is often the case that diferent facts have diferent importance. In this paper, we consider Datalog± knowledge bases where database facts are weighted, with weights expressing facts' importance (or reliability or some other aspect of interest). We present recent results on the complexity of querying inconsistent knowledge bases in this setting.
In real-world applications, data possibly coming from diferent sources may exhibit inconsistencies.
Obtaining meaningful query answers in these scenarios can be achieved by resorting to
inconsistencytolerant semantics. Popular ones are the ABox repair (AR), first defined for relational databases [
In this paper, we consider the case where database facts are associated with weights (e.g., quantitatively measuring their reliability), a scenario arising in many applications. For example, consider a neurosymbolic system in which the neuronal part of the system produces some predictions as database facts associated with a confidence score (see, e.g., [ 13] and references therein). Then, in case of inconsistencies, these values can be used in the computation of most reliable repairs. In such a setting, a natural criterion to define repairs is to select the weight-maximal consistent subsets of the database. In this paper, we discuss recent results presented in [14] on the complexity of the AR, IAR, and ICR semantics when such a notion of repair is adopted in the presence of weighted knowledge bases expressed via Datalog± languages.
General. We assume a set C of constants, a set N of labeled nulls, and a set V of variables. A term is a constant, a null, or a variable. We also assume a set of predicates, each associated with an arity, i.e., a non-negative integer. An atom has the form (1, . . . , ), where is an -ary predicate, and 1, . . . , are terms. An atom containing only constants is also called a fact. Conjunctions of atoms are often identified with the sets of their atoms. An instance is a (possibly infinite) set of atoms containing only constants and nulls. A database is a finite instance that contains only constants. A homomorphism is a substitution ℎ : C ∪ N ∪ V → C ∪ N ∪ V that is the identity on C and maps N to C ∪ N. A Boolean conjunctive query (BCQ) has the form ∃Y(Y), where (Y) is a conjunction of atoms without nulls. A BCQ is true over an instance , denoted |= , if there is a homomorphism ℎ with ℎ((Y)) ⊆ . Dependencies. A tuple-generating dependency (TGD) is a first-order formula ∀X∀Y ( (X, Y) → ∃Z (X, Z)), where X, Y, and Z are pairwise disjoint sets of variables, (X, Y) is a conjunction of atoms, and (X, Z) is an atom, all without nulls. An instance satisfies a TGD , written |= , if the following holds: whenever there exists a homomorphism ℎ such that ℎ( (X, Y)) ⊆ , then there exists ℎ′ ⊇ ℎ|X, where ℎ|X is the restriction of ℎ on X, such that ℎ′((X, Z)) ∈ . A negative constraint (NC) is a first-order formula ∀X ( (X) → ⊥), where X ⊆ V, (X) is a conjunction of atoms without nulls, and ⊥ denotes the truth constant false. An instance satisfies an NC , written |= , if there is no homomorphism ℎ such that ℎ( (X)) ⊆ . We will use to denote the BCQ ∃X (X). Given a set Σ of TGDs and NCs, satisfies Σ, written |= Σ, if satisfies each TGD and NC of Σ. For a class C of TGDs, C⊥ denotes the combination of C with arbitrary NCs. Finite sets of TGDs and NCs are called programs. The Datalog± languages we consider are among the most frequently analyzed in the literature, namely, linear (L) [15], guarded (G) [16], sticky (S) [17], and acyclic TGDs (A), the “weak” generalizations weakly sticky (WS) [17] and weakly acyclic TGDs (WA) [18], their “full” restrictions linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively, and full TGDs (F) in general. We refer to [12, 5] for a detailed overview. Knowledge Bases. A knowledge base is a pair (, Σ), where is a database and Σ is a program. For a program Σ, Σ and ΣNC denote the subsets of Σ containing the TGDs and NCs of Σ, respectively. The set of models of KB = (, Σ), denoted mods(KB ), is the set of instances { | ⊇ ∧ |= Σ}. We say that KB is consistent if mods(KB ) ̸= ∅, otherwise KB is inconsistent. The answer to a BCQ relative to KB is true, denoted KB |= , if |= for every ∈ mods(KB ). Another way to define ontological query answering is via the concept of the Chase (see, e.g., [16, 19]).
The BCQ answering problem is: given a knowledge base KB and a BCQ , decide whether KB |= . Following [20], the combined complexity of BCQ answering considers the database, the program, and the query as part of the input. The bounded-arity-combined (or ba-combined) complexity assumes that the arity of the underlying schema is bounded by constant. The fixed-program-combined (or fp-combined) complexity considers the program fixed; in the data complexity the query is fixed as well. We refer to [5] for an overview of the complexity of BCQ answering for the languages in this paper. For more on computational complexity theory we refer the reader to any textbook on the topic, such as [21]. 3. Inconsistency-Tolerant Semantics for Weighted KBs From now on, we implicitly assume that the database of any knowledge base comes along with a weight function : → N assigning weights to its facts. For every ′ ⊆ , assigns a weight to ′ defined as (′) = ∑︀∈′ ( ) (with a slight abuse of notation, applies to both facts and sets of facts). For every 1, 2 ⊆ , we write 1 ≤ 2 (resp., 1 < 2) if (1) ≤ (2) (resp., (1) < (2)).
Given a knowledge base KB = (, Σ), a selection of KB is a database ′ such that ′ ⊆ . A selection ′ of KB is consistent if (′, Σ) is consistent. Symmetrically, the concept of consistent selection is linked to that of culprit, which is a subset of s.t. (, Σ ) |= for some ∈ ΣNC . By deleting from a hitting set ([22, 23, 24]) of facts intersecting all culprits, we obtain a consistent selection ′ = ∖ .
Definition 3.1. A ≤ -repair of a knowledge base KB is a consistent selection ′ of KB such that there is no consistent selection ′′ of KB with ′ < ′′.
For a knowledge base KB = (, Σ), Rep≤ (KB ) denotes the set of all ≤ -repairs of KB , and the closure of KB , denoted Cl (KB ), is the set of all facts built from constants in and Σ, entailed by and the TGDs of Σ.
Definition 3.2. Let KB be a knowledge base and let be a BCQ.
• KB entails under the ≤ -AR semantics, denoted KB |=≤ -AR , if (′, Σ) |= for all ′ ∈
Rep≤ (KB ). • KB entails under the ≤ -IAR semantics, denoted KB |=≤ -IAR , if ( , Σ) |= , where = ⋂︀{′ | ′ ∈ Rep≤ (KB )}. • KB entails under the ≤ -ICR semantics, denoted KB |=≤ -ICR , if ( , Σ) |= , where = ⋂︀{Cl ((′, Σ)) | ′ ∈ Rep≤ (KB )}.
The problems whose complexity we are interested in are denoted as ≤ -(ℒ), with ∈ {AR, IAR, ICR}, and are defined as follows: Given a knowledge base (, Σ) with Σ ∈ ℒ, and a BCQ , does (, Σ) |=≤ -S hold?
The complexity results are summarized in Tables 1 and 2. All entries are completeness results. The complexity ranges from Δp2- to 2exp-completeness. For more details on how the results have been derived, we refer the reader to [14]. Here we focus on the main takeaways the complexity analysis provides.
The IAR and ICR semantics have the same complexity, which is a behavior shown by cardinalitymaximal repairs as well [6], while this does not hold for subset-maximal ones [5]. As usual (under other maximality criteria to define repairs), the IAR and ICR semantics are at most as expensive as the AR semantics. Indeed, we can see that the complexity increases when moving from the IAR/ICR to the AR semantics only in the fixed-program combined complexity, while the complexity does not change across the three inconsistency-tolerant semantics under the remaining complexity measures (namely, data, bounded-arity combined, and combined complexity).
It is also interesting to compare weight-maximal repairs with subset-maximal and cardinality-maximal ones, whose complexity results can be found in [5] and [6], respectively. Clearly, weight-maximal repairs generalize cardinality-maximal ones (the latter can be simply modeled by assigning the same weight to all facts), and when we move from the latter to the former, the complexity of all inconsistency-tolerant semantics increases in several cases. Compared with subset-maximal repairs, the complexity of all inconsistency-tolerant semantics under weight-maximal repairs is always at least as high as the one under subset-maximal repairs. Overall, we can conclude that while weights give us the flexibility of assigning diferent importance to diferent facts, they incur an increase of complexity compared with more “standard” notions of repairs. ba-c. Δp3 Δp3 pnexp exp Δp3 2exp
Comb. pspace exp pnexp 2exp exp 2exp
ℒ L⊥, LF⊥, AF⊥
S⊥, SF⊥
A⊥
G⊥
F⊥, GF⊥ WS⊥, WA⊥
Data
fp-c. Δp2 Δp2 Δp2 Δp2 Δp2 Δp2
We have considered the problem of querying inconsistent knowledge bases whose database facts are weighted. We have discussed recent results, presented in [14], on the complexity of inconsistent-tolerant semantics in such a setting.
Future research includes defining other semantics for inconsistency-tolerant OMQA, by considering more elaborate user preferences over repairs [25, 26, 27, 28, 29, 30, 31] and also considering compact representations [32, 33, 34]. Another interesting approach that has been investigated recently in the context of handling inconsistent knowledge is that of measuring inconsistencies via the Shapley value [35], it would be interesting to bring to existential rules the ideas implemented for DLs [36, 37, 38]. As a natural extension of the setting considered in this paper, TGDs and NCs might be weighted too, similarly to what has been recently done in [39], which considers weighted knowledge bases where both axioms and assertions have weights. Another direction for future work is to devise approximation algorithms that are practical, as done in the setting of incomplete databases [40, 41], e.g. by resorting to a logic programming approach [42]. Recently, there has been an increasing interest on explainable AI, including explaining query answering under existential rules [43, 44, 45] and DLs [46, 47]. In particular, [46, 48, 49] addressed the problem of explaining why a query is entailed or not under inconsistencytolerant semantics, where repairs are subset-maximal. An interesting direction for future work is to address the same problem for weight-maximal repairs.
Enrico Malizia’s work was supported by the European Union – NextGenerationEU programme, through the Italian Ministry of University and Research (MUR) PRIN 2022-PNRR grant P2022KHTX7 “DISTORT”— CUP: J53D23015000001, under the Italian “National Recovery and Resilience Plan” (PNRR), Mission 4 Component 1.
Cristian Molinaro acknowledges the support of the PNRR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU. [5] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-tolerant query answering for existential rules, Artif. Intell. 307 (2022) 103685. [6] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query answering in Datalog+/– under cardinality-based repairs, in: Proc. AAAI, 2019, pp. 2962–2969. [7] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proc. AAAI, 2014, pp. 996–1002. [8] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering in relational databases, Ann. Math. Artif. Intell. 64 (2012) 209–246. [9] M. Bienvenu, C. Bourgaux, Querying and repairing inconsistent prioritized knowledge bases:
Complexity analysis and links with abstract argumentation, in: Proc. KR, 2020, pp. 141–151. [10] M. Bienvenu, C. Bourgaux, Querying inconsistent prioritized data with ORBITS: Algorithms, implementation, and experiments, in: Proc. KR, 2022. [11] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, in: Proc. KR 2020, 2020, pp. 203–212. [12] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, Artif. Intell. 312 (2022) 103772. [13] E. Tsamoura, T. M. Hospedales, L. Michael, Neural-symbolic integration: A compositional perspective, in: Proc. AAAI, 2021, pp. 5051–5060. [14] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of inconsistency-tolerant query answering in datalog+/- under preferred repairs, in: Proc. KR, 2023, pp. 472–481. [15] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query answering over ontologies, J. Web Sem. 14 (2012) 57–83. [16] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174. [17] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query answering problem, Artif. Intell. 193 (2012) 87–128. [18] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering, Theor.
Comput. Sci. 336 (2005) 89–124. [19] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger graphs,
Proc. VLDB Endow. 14 (2021) 943–956. [20] M. Y. Vardi, The complexity of relational query languages, in: Proc. STOC, 1982, pp. 137–146. [21] S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press,
Cambridge, UK, 2009. [22] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions, Inf.
Comput. 197 (2005) 90–121. [23] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, in: Proc. CSL-LICS, 2014, pp. 43:1–43:10. [24] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, SIAM J. Comput. 47 (2018) 456–492. [25] T. Lukasiewicz, E. Malizia, On the complexity of CP-nets, in: Proc. AAAI, 2016, pp. 558–564. [26] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting, Artif. Intell. 272 (2019) 101–142. [27] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets: Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636. [28] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential active integrity constraints, Expert Syst. Appl. 168 (2021) 114297. [29] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract argumentation, in: Proc. IJCAI, 2022, pp. 2517–2524. [30] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, Non-transferable utility coalitional games via mixed-integer linear constraints, J. Artif. Intell. Res. 38 (2010) 633–685. [31] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ based on counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33. [32] E. Malizia, L. Palopoli, F. Scarcello, Infeasibility certificates and the complexity of the core in coalitional games, in: Proc. IJCAI, 2007, pp. 1402–1407. [33] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, On the complexity of compact coalitional games, in:
Proc. IJCAI, 2009, pp. 147–152. [34] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact games,
ACM Trans. Comput. Theory 7 (2014) 3:1–3:52. [35] L. S. Shapley, A value for -person games, in: H. W. Kuhn, A. W. Tucker (Eds.), Contributions to the Theory of Games, Volume II, Princeton University Press, Princeton, NJ, USA, 1953, pp. 307–317. [36] X. Deng, V. Haarslev, N. Shiri, Measuring inconsistencies in ontologies, in: The Semantic Web:
Research and Applications, 2007, pp. 326–340. [37] M. Bienvenu, D. Figueira, P. Lafourcade, When is shapley value computation a matter of counting?,
Proc. ACM Manag. Data 2 (2024) 105. [38] M. Bienvenu, D. Figueira, P. Lafourcade, Shapley Value Computation in Ontology-Mediated Query
Answering, Technical Report arXiv:2407.20058, CoRR, 2024. [39] M. Bienvenu, C. Bourgaux, R. Jean, Cost-based semantics for querying inconsistent weighted knowledge bases, in: Proc. KR, 2024. [40] M. Console, P. Guagliardo, L. Libkin, Approximations and refinements of certain answers via many-valued logics, in: Proc. KR, 2016, pp. 349–358. [41] S. Greco, C. Molinaro, I. Trubitsyna, Approximation algorithms for querying incomplete databases,
Inf. Syst. 86 (2019) 28–45. [42] S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, NP datalog: A logic language for expressing search and optimization problems, Theory Pract. Log. Program. 10 (2010) 125–166. [43] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers under existential rules, in: Proc. IJCAI, 2019, pp. 1639–1646. [44] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Explanations for negative query answers under existential rules, in: Proc. KR, 2020, pp. 223–232. [45] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Preferred explanations for ontology-mediated queries under existential rules, in: Proc. AAAI, 2021, pp. 6262–6270. [46] M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over inconsistent DL-Lite knowledge bases, J. Artif. Intell. Res. 64 (2019) 563–644. [47] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Explanations for ontology-mediated query answering in description logics, in: Proc. ECAI, 2020, pp. 672–679. [48] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query answering under existential rules, in: Proc. AAAI, 2020, pp. 2909–2916. [49] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under inconsistency-tolerant semantics, in: Proc. IJCAI, 2022, pp. 2705–2711.