Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs⋆

Abstract

Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistency-tolerant semantics have been proposed. In these semantics, the input database is erroneous, and a repair is a maximally consistent database subset. Diferent notions of maximality (such as subset and cardinality maximality) have been considered. In this paper, we give a precise picture of the computational complexity of inconsistency-tolerant query answering in a wide range of Datalog+/languages under the cardinality-based versions of three prominent repair semantics.

Keywords

• eol>Knowledge representation
• Existential rules
• Inconsistencies
• Query answering
• Complexity

1. Introduction

In many ontology-based applications, such as ontology-based data extraction from the Web, or ontology-based integration of diferent data sources, it is very likely that the data are inconsistent with the ontology, and thus inconsistency-tolerant semantics for ontology-based query answering are urgently needed. Among the most prominent ontology languages are description logics (DLs) [ 2 ] and existential rules from the context of Datalog± [ 3 ].

The most widely accepted semantics for querying inconsistent ontological knowledge bases is perhaps consistent query answering (CQA), which was first developed for relational databases [ 4 ] and then generalized as the ABox repair (AR) semantics for several DLs [ 5 ]. Consistent query answering is based on the concept of repair, which is a maximal consistent subset of the input database. A fact/query is entailed by an ontological knowledge base in consistent query answering, if it is (classically) entailed by all the repairs (under the ontology). Several other repair semantics for querying inconsistent knowledge bases have recently been developed as alternatives. In the intersection of repairs (IAR) semantics [ 5 ], an answer is considered to be valid, if it can be inferred from the intersection of the repairs (and the ontology). The intersection of closed repairs (ICR) [ 6 ] is another semantics, in which an answer is valid, if it can be inferred from the intersection of the closure of the repairs (and the ontology). Recently, the AR semantics was extended to the generalized repair (GR) semantics [ 7 ]. In the GR semantics, also ontological rules may be removed. This generalization was extended to the IAR and ICR semantics in [ 8 ]

Interestingly, the IAR and the ICR semantics can be seen as under-approximation of the AR semantics and analyzing their complexity helps to understand whether such approximations have actually lower complexities (see also [ 9, 10 ] for other approximation approaches). Beside this, a crucial advantage of the IAR and the ICR semantics is that their intersection of (closed) repairs can be materialized [ 11, 12 ], while the AR semantics exists only virtually.

The complexity of consistent query answering when the ontology is described via one of the main DLs is well-understood. Rosati [ 13 ] studied the data and combined complexity for a wide spectrum of DLs, while Bienvenu [ 6 ] identified cases for simple ontologies (within the DL-Lite family) for which tractable data complexity results can be obtained. In [ 14 ], the data and diferent types of combined complexity of consistent query answering have been studied for ontologies described via existential rules and negative constraints.

Alternative maximality notions for repairs, such as cardinality-maximal repairs [ 15 ], rather than subset-maximal ones, have been explored less. Bienvenu et al. [ 16 ] analyzed the data and the combined complexity of query answering under the AR and IAR semantics over the language DL-Liteℛ for various notions of maximal repairs, among which maximum cardinality.

This paper continues this line of research on cardinality-maximal consistent query answering, and we analyze the complexity of the above three inconsistency-tolerant query answering semantics for a wide range of Datalog± languages and for several diferent complexity measures.

2. Preliminaries

We here briefly recall some basics on existential rules from the context of Datalog ± [ 3 ]. 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, null, or variable. We assume a set of predicates, each associated with an arity. An atom has the form (1, . . . , ), where is an -ary predicate, and 1, . . . , are terms. An atom containing only constants is called fact. Conjunctions of atoms are also identified with the sets of their atoms. An instance is a (possibly infinite) set of atoms defined over constants and nulls. A database is a finite instance containing 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. With a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms. A conjunctive query (CQ) has the form ∃Y(X, Y), where (X, Y) is a conjunction of atoms without nulls. The answer to over an instance , denoted (), is the set of all |X|-tuples t over C for which there is a homomorphism ℎ such that ℎ((X, Y)) ⊆ and ℎ(X) = t. A Boolean CQ (BCQ) is a CQ ∃Y(Y), i.e., all variables are existentially quantified; is true over , denoted |= , if () ̸= ∅, i.e., there is a homomorphism ℎ with ℎ((Y)) ⊆ . Dependencies. A tuple-generating dependency (TGD) is an FO 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 , written |= , 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 , written |= , if there is no homomorphism ℎ such that ℎ( (X)) ⊆ . Given a set Σ of TGDs and NCs, satisfies Σ, written |= Σ, if satisfies each TGD and NC of Σ. For brevity, we omit the universal quantifiers in front of TGDs and NCs, and use the comma (instead of ∧) for conjoining atoms. For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs. Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.

The Datalog± languages ℒ that we consider to guarantee decidability are among the most frequently analyzed in the literature, namely, linear (L) [ 3 ], guarded (G) [ 17 ], sticky (S) [ 18 ], and acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [ 18 ] and weakly acyclic TGDs (WA) [19], as well as their “full” (i.e., existential-free) proper restrictions linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively, and full TGDs (F) in general. We also recall the following further inclusions: L ⊂ G and F ⊂ WA ⊂ WS. We refer to [ 14 ] for a more 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 TGDs and NCs subsets, respectively, of Σ. The set mods(KB ) of models of KB = (, Σ) is the set of instances { | ⊇ ∧ |= Σ}; KB is consistent if mods(KB ) ̸= ∅, otherwise KB is inconsistent. The answer to a CQ w.r.t. KB is the set of tuples ans(, KB ) = ⋂︀{() | ∈ mods(KB )}. The answer to a BCQ is true, denoted KB |= , if ans(, KB ) ̸= ∅. Another way to define the existential rules semantics is via the concept of the Chase (see, e.g., [20, 21]). The decision version of the CQ answering problem is: for a knowledge base KB , a CQ , and a tuple of constants t, decide whether t ∈ ans(, KB ). Since CQ answering can be reduced in logspace to BCQ answering, we focus on BCQs. BCQ(ℒ) denotes the problem of BCQ answering when restricted over programs belonging to ℒ.

Following Vardi [22], the combined complexity of BCQ answering considers the database, the set of dependencies, 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 an integer constant. The fixed-program-combined (or fp-combined) complexity considers the sets of TGDs and NCs as fixed; the data complexity also assumes the query fixed. Table 1 recalls the complexity results of BCQ answering for the languages here considered [ 14 ].

A language ℒ is FO-rewritable if given any program Σ ∈ ℒ and any BCQ , there exists an FO-query Σ such that, for all databases we have that (, Σ) |= if |= Σ. All languages from Table 1 with ac0 data complexity are FO-rewritable.

Inconsistency-Tolerant Semantics. In classical BCQ answering, an inconsistent knowledge base entails every query, as everything follows from a contradiction. Clearly, the answers obtained in such cases are not meaningful. Three prominent inconsistency-tolerant semantics for query answering under existential rules are the ABox repair (AR) semantics, its approximation by the intersection of repairs (IAR), and the intersection of closed repairs (ICR) semantics [ 5, 6 ]; all three are based on the notion of repair, which is a maximal consistent subset of the database.

Symmetrically, the concept of repair is linked to that of culprit. Intuitively, a culprit is a minimal subset of that, together with Σ entails some NC; a culprit for an NC is a “minimal explanation” [23, 24] of the NC. By deleting from a minimal hitting set [25, 26, 27] of facts intersecting all culprits, we obtain a repair = ∖ .

We now define inconsistency-tolerant semantics for a generic concept of repair maximality.

Given a knowledge base KB = (, Σ), a selection ′ of KB is a database such that ′ ⊆ . A selection ′ of KB is consistent, if mods ((′, Σ)) ̸= ∅. Consistent selections of knowledge bases can be ordered according to some criteria to select the more desired ones. Given a preorder ≼ over a set of databases, for two elements ′, ′′ ∈ , ′ ≺ ′′ denotes that ′ ≼ ′′ and ′′ ̸≼ ′. A database ∈ is ≼-maximal in if there is no ′ ∈ such that ≺ ′. Definition 1. A ≼-repair of a knowledge base KB is a consistent selection of KB that is ≼-maximal in the set of all the consistent selections of KB .

We now define the three diferent inconsistency-tolerant semantics for BCQ answering. Rep≼(KB ) denotes the set of all ≼-repairs of KB . The closure Cl (KB ) of KB is the set of all facts built from constants in and Σ, entailed by and the TGDs of Σ.

Definition 2. Let KB be a knowledge base, let be a BCQ, and let ≼ be an order over the consistent selections of KB . • KB entails under the ABox repair semantics and order ≼ (≼-AR), denoted by KB |=≼-AR , if, for all ′ ∈ Rep≼(KB ), (′, Σ) |= . • KB entails under the intersection of repairs semantics and order ≼ (≼-IAR), denoted by

KB |=≼-IAR , if (* , Σ) |= , where * = ⋂︀{′ | ′ ∈ Rep≼(KB )}. • KB entails under the intersection of closed repairs semantics and order ≼ (≼-ICR), denoted by KB |=≼-ICR , if ( , Σ) |= , where = ⋂︀{Cl ((′, Σ)) | ′ ∈ Rep≼(KB )}.

An interesting class of repairs are those selected by the cardinality order ‘≤ ’ [ 16 ]. A ≤ -repair of a knowledge base KB is a maximum cardinality consistent selection of KB . Here, we consider only the ‘≤ ’ order, hence, we often call ≤ -repairs simply repairs, and by Rep(KB ), we mean Rep≤ (KB ). Cardinality-maximal repairs are very appropriate when it is known (or believed) that all the facts in the database have the same (possibly small) probability of being erroneous. In these cases, larger repairs are preferred, because fewer facts are dropped [ 16 ]. When facts in the database have diferent likelihoods of being erroneous, then other concepts of repairs can also be taken into consideration [ 6, 28 ].

3. Complexity Analysis

Compared to the case where subset maximality is considered, using maximum cardinality in several cases comes at a cost, needed to compute the largest repair’s size. However, this is sometimes masked out by the complexity of classical/AR/IAR/ICR BCQ answering. Compared to ≤ -AR-BCQ answering, the complexity of ≤ -IAR- and ≤ -ICR-BCQ answering slightly drops and is the same. Their complexity is the same because the complexity of either classical BCQ reasoning or of computing the biggest repairs’ size dominate the task’s complexity. Therefore, in this setting ICR has an advantage over IAR, as ICR is a finer AR’s approximation than IAR.

3.1. Membership Results

A first result allows us to show most of the complexity upper-bounds of Table 2. The intuition behind this theorem is as follows. First we can compute the size of the biggest repairs via a binary search, then through some additional oracle calls it is possible to check whether the query is entailed or not under the inconsistency-tolerant semantics (see [ 1 ] for more details). Theorem 3. Let be a Datalog± language. If BCQ answering from knowledge bases over is in C in the data / ba-combined / combined complexity (resp., data / ba-combined complexity), then ≤ -AR and ≤ -IAR (resp., ≤ -ICR) BCQ answering from knowledge bases over is in p with an oracle for npC[(log )] in the data / ba-combined / combined complexity (resp., data / ba-combined complexity).

The previous result relies on the guess of a query entailment disprover to be passed to the oracle. However, this cannot be done for the ICR case in the combined complexity, as the guess might need be too large. We hence need a tailored proof analyzing all languages case by case. Theorem 4. ≤ -ICR BCQ answering in the combined complexity from knowledge bases over Datalog± the languages here considered is in the complexity classes shown in Table 2.

For the upper-bounds in the fp-combined setting, we can actually provide tighter ones, as checking the consistency of a set of facts is feasible in the complexity class of BCQ answering in the data complexity (and not in the fp-complexity), because the NCs are fixed. Theorem 5. If BCQ answering from knowledge bases over a Datalog± language is in D in the data complexity and in C in the fp-combined complexity, then ≤ -AR (resp., ≤ -IAR and ≤ -ICR) BCQ answering from knowledge bases over is possible by a computation in p with an oracle for npD[(log )], followed by a computation in co-npC (resp., C), in the fp-combined complexity.

3.2. Hardness Results

We can show matching lower-bounds for the upper-bounds found in the previous section.

The following result is via a reduction from the Θp2-complete problem InAllMaxIS [ 15 ]: for a graph and a vertex , decide if belongs to all the max-size independent sets of . Theorem 6. For every ∈ {AR, IAR, ICR}, ≤ -C BCQ answering from knowledge bases over LF⊥, AF⊥, and SF⊥ is Θp2-hard in the data complexity.

For the next result, the reduction is from the classical Πp2-complete problem of deciding the validity of a QBF ∀∃ (, ).

Theorem 7. ≤ -AR BCQ answering from knowledge bases over LF⊥, AF⊥, and SF⊥ is Πp2-hard in the fp-combined complexity.

The Θp3-hardness of the following problems is via a reduction from the Θp3-complete problem Comp-Valid2: given sets and of QBFs with 2 alternating quantifiers, decide whether the number of valid formulas in is bigger than the number of valid formulas in [29] (this is a generalization of the Comp-SAT problem [30]).

Theorem 8. For every ∈ {AR, IAR, ICR}, ≤ -C BCQ answering from knowledge bases over LF⊥, AF⊥, and SF⊥ is Θp3-hard in the ba-combined complexity.

The next hardness is obtained via a reduction from the following pnexp-hard problem [ 14 ]: for a triple (, TP 1, TP 2), where is an integer in unary notation, and TP 1 and TP 2 are two tiling problems for the exponential square 2 × 2, decide whether there is an initial condition of length , such that TP 1 has no solution with , and TP 2 has a solution with . Theorem 9. For any ∈ {AR, IAR, ICR}, ≤ -C BCQ answering for A⊥ are pnexp-hard in the ba-combined and combined complexity.

The remaining hardness results follows from the hardness of BCQ answering.

4. Summary and Outlook

We have analyzed BCQ answering under diferent cardinality-maximal inconsistency-tolerant semantics, for the most popular Datalog± languages and complexity measures.

Future research include defining other semantics for inconsistency-tolerant ontological query answering, considering weighed repairs and more elaborate user preferences over repairs [31, 32, 33, 34, 35]. Also, in the line of a more recent research, it would be interesting to extend the concepts of explanations for inconsistency-tolerant query answering [36, 37] to cardinalitymaximal repairs, and mix this with the notions of preferred explanations [38] and explanations for negative query answers [39].

Acknowledgments

This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1, and by the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1. [19] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering,

Theor. Comput. Sci. 336 (2005) 89–124. [20] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger graphs, VLDB Endow. 14 (2021) 943–956. [21] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Exploiting equality generating dependencies in checking chase termination, VLDB Endow. 9 (2016) 396–407. [22] M. Vardi, The complexity of relational query languages, in: STOC, 1982, pp. 137–146. [23] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers under existential rules, in: IJCAI, 2019, pp. 1639–1646. [24] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontologymediated query answering in description logics, in: ECAI, 2020, pp. 672–679. [25] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, SIAM J. Comput. 47 (2018) 456–492. [26] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,

Inf. Comput. 197 (2005) 90–121. [27] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, in: LICS, 2014, pp. 43:1–43:10. [28] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, in: KR, 2020, pp. 203–212. [29] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ based on counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33. [30] T. Lukasiewicz, E. Malizia, On the complexity of CP-nets, in: AAAI, 2016, pp. 558–564. [31] 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. [32] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:

Pareto and majority voting, Artif. Intell. 272 (2019) 101–142. [33] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:

Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636. [34] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential active integrity constraints, Expert Syst. Appl. 168 (2021) art. no. 114297. [35] 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. [36] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query answering under existential rules, in: AAAI, 2020, pp. 2909–2916. [37] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under inconsistency-tolerant semantics, in: IJCAI, 2022. [38] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270. [39] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Explanations for negative query answers under existential rules, in: KR, 2020, pp. 223–232.

References

[1] T. Lukasiewicz , E. Malizia , A. Vaicenavičius , Complexity of inconsistency-tolerant query answering in Datalog+/- under cardinality-based repairs , in: AAAI , 2019 , pp. 2962 - 2969 .

[2] F. Baader , D. Calvanese , D. L. McGuinness , D. Nardi , P. F. Patel-Schneider (Eds.), The Description Logic Handbook , 2nd ed., Cambridge University Press, 2007 .

[3] A. Calì , G. Gottlob, T. Lukasiewicz , A general Datalog-based framework for tractable query answering over ontologies , J. Web Sem . 14 ( 2012 ) 57 - 83 .

[4] M. Arenas , L. E. Bertossi , J. Chomicki , Consistent query answers in inconsistent databases , in: PODS , 1999 , pp. 68 - 79 .

[5] D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , D. F. Savo , Inconsistency-tolerant semantics for description logics , in: RR , 2010 , pp. 103 - 117 .

[6] M. Bienvenu , On the complexity of consistent query answering in the presence of simple ontologies , in: AAAI , 2012 , pp. 705 - 711 .

[7] T. Eiter , T. Lukasiewicz , L. Predoiu, Generalized consistent query answering under existential rules , in: KR , 2016 , pp. 359 - 368 .

[8] T. Lukasiewicz , E. Malizia , C. Molinaro , Complexity of approximate query answering under inconsistency in Datalog± , in: IJCAI, 2018 , pp. 1921 - 1927 .

[9] S. Greco , C. Molinaro , Probabilistic query answering over inconsistent databases , Ann. Math. Artif. Intell. 64 ( 2012 ) 185 - 207 .

[10] S. Greco , C. Molinaro , I. Trubitsyna , Computing approximate query answers over inconsistent knowledge bases , in: IJCAI , 2018 , pp. 1838 - 1846 .

[11] D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , D. F. Savo , Inconsistency-tolerant query answering in ontology-based data access , J. Web Sem . 33 ( 2015 ) 3 - 29 .

[12] M. Bienvenu , C. Bourgaux , Inconsistency-tolerant querying of description logic knowledge bases , in: Reasoning Web , 2016 , pp. 156 - 202 .

[13] R. Rosati , On the complexity of dealing with inconsistency in description logic ontologies , in: IJCAI , 2011 , pp. 1057 - 1062 .

[14] T. Lukasiewicz , E. Malizia, M. V. Martinez , C. Molinaro , A. Pieris , G. I. Simari , Inconsistencytolerant query answering for existential rules , Artif. Intell . 307 ( 2022 ) art . no. 103685 .

[15] A. Lopatenko , L. E. Bertossi , Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics , in: ICDT , 2007 , pp. 179 - 193 .

[16] M. Bienvenu , C. Bourgaux , F. Goasdoué , Querying inconsistent description logic knowledge bases under preferred repair semantics , in: AAAI , 2014 , pp. 996 - 1002 .

[17] A. Calì , G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints , J. Artif. Intell. Res . 48 ( 2013 ) 115 - 174 .

[18] A. Calì , G. Gottlob , A. Pieris , Towards more expressive ontology languages: The query answering problem , Artif. Intell . 193 ( 2012 ) 87 - 128 .