Complexity of Approximate Query Answering under Inconsistency in Datalog+/-

1 Introduction

Description logics (DLs) and existential rules from the context of Datalog± are popular ontology languages. In realworld ontology-based applications involving large amounts of data (such as ontology-based data extraction and/or integration), 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.

Consistent query answering, first developed for relational databases [Arenas et al., 1999] and then generalized as the AR semantics for several DLs [Lembo et al., 2010], is the most widely accepted semantics for querying inconsistent ontologies. Query answering under the AR semantics is known to be a hard problem, even for very simple languages [Lembo et al., 2010]. For this reason, several other semantics have been recently developed with the aim of approximating consistent query answering [Lembo et al., 2010; Bienvenu, 2012; Lukasiewicz et al., 2012a; Bienvenu and Rosati, 2013].

In particular, in [Lembo et al., 2010], besides the AR semantics, three other inconsistency-tolerant query answering semantics are proposed, including the approximate intersection of repairs (IAR) semantics, in which 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) [Bienvenu, 2012] is another approximate semantics, in which an answer is valid, if it can be inferred from the intersection of the closure of the repairs (and the ontology).

There are several reasons for the practical relevance of the IAR and the ICR semantics, and thus for motivating an indepth analysis of their computational properties. First, they are two natural semantics that identify "surer" answers than the AR semantics, and so they can also be seen as underapproximations of the latter. Investigating their complexity helps to understand whether such approximations have actually lower complexities, which is indeed the case for different languages and complexity measures considered in this paper. Second, recent work on explanation in the context of inconsistency-tolerant query answering shows that explanations are much easier to define and compute for the IAR semantics [Bienvenu et al., 2016]. Third, the IAR and ICR semantics are amenable to preprocessing (the intersection can be computed offline, and then standard querying algorithms can be employed online)-indeed, this has been used to implement the IAR semantics [Lembo et al., 2015], and for ICR, it has been remarked in [Bienvenu and Bourgaux, 2016].

The complexity of query answering under AR semantics when the ontology is described via one of the central DLs is well-understood. Rosati [2011] studied the data and combined complexity for a wide spectrum of DLs, while Bienvenu [2012] identified cases for simple ontologies (within the DL-Lite family) for which tractable data complexity results can be obtained. In [Lukasiewicz et al., 2012a; 2013; 2015], the data and different types of combined complexity of the AR semantics have been studied for ontologies described via existential rules and negative constraints.

Bienvenu et al. [2014a] analyzed the data and the combined complexity of query answering under the AR and IAR semantics for different notions of maximal repairs over the language DL-LiteR. Recently, the AR semantics was extended to the generalized repair (GR) semantics and its computational complexity analyzed [Eiter et al., 2016]. In the GR semantics, also ontological rules may be removed, and some database atoms and rules are assumed to be non-removable.

This paper continues this line of research and integrates the generalized repair semantics of [Eiter et al., 2016] with the two intersection-based approximate repair semantics. We analyze the complexity of approximate inconsistency-tolerant query answering for a wide range of Datalog± languages and for several different complexity measures; in particular:

• ▷ We consider different popular inconsistency-tolerant semantics, namely, the IAR and the ICR semantics, in both their standard and their generalized repair variants.
• ▷ We consider the most popular Datalog± languages: lin-

ear, guarded, sticky, and acyclic existential rules, along with "weak" generalizations, as well as full (i.e., nonexistential) restrictions, and full rules in general.

• ▷ We analyze the data, fixed-program combined, boundedarity combined, and combined complexity.

2 Datalog±

In this section, we briefly recall some basics on existential rules from the context of Datalog± [Calì et al., 2012a].

General. We assume a set C of constants, a set N of labeled nulls, and a set V of variables. A term t is a constant, null, or variable. We also assume a set of predicates, each associated with an arity, i.e., a non-negative integer. An atom has the form p(t1, . . . , tn), where p is an n-ary predicate, and t1, . . . , tn are terms. Conjunctions of atoms are often identified with the sets of their atoms. An instance I is a (possibly infinite) set of atoms p(t), where t is a tuple of constants and nulls. A database D is a finite instance that contains only constants. A homomorphism is a substitution h : C∪N∪V → C∪N∪V that is the identity on C and maps N to C ∪ N. A conjunctive query (CQ) q has the form ∃Yφ(X, Y), where φ(X, Y) is a conjunction of atoms without nulls. The answer to q over an instance I, denoted q(I), is the set of all tuples t over C for which there is a homomorphism h such that h(φ(X, Y)) ⊆ I and h(X) = t. A Boolean CQ (BCQ) q is a CQ ∃Yφ(Y), i.e., all variables are existentially quantified; q is true over I, denoted I |= q, if q(I) ̸= ∅, i.e., there is a homomorphism h with h(φ(Y)) ⊆ I.

Dependencies. A tuple-generating dependency (TGD) σ is a first-order formula ∀X∀Y ϕ(X, Y) → ∃Z p(X, Z), where X ∪ Y ∪ Z ⊆ V, ϕ(X,Y) is a conjunction of atoms, and p(X,Z) is an atom, all without nulls; ϕ(X,Y) is the body of σ, denoted body(σ), while p(X,Z) is the head of σ, denoted head(σ). For clarity, we consider single-atom-head TGDs; however, our results can be extended to TGDs with a conjunction of atoms in the head. An instance I satisfies σ, written I |= σ, if the following holds: whenever there exists a homomorphism h such that h(ϕ(X,Y)) ⊆ I, then there exists h′ ⊇ h|X, where h|X is the restriction of h on X, such that h′ (p(X, Z)) ∈ I. A negative constraint (NC) ν is a firstorder formula ∀Xϕ(X) → ⊥, where X ⊆ V, ϕ(X) is a conjunction of atoms without nulls, called the body of ν, denoted body(ν), and ⊥ denotes the truth constant false. An instance I satisfies ν, written I |= ν, if there is no homomorphism h such that h(ϕ(X)) ⊆ I. Given a set Σ of TGDs and NCs, I satisfies Σ, written I |= Σ, if I 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 body atoms. Given a class of TGDs C, we denote by C⊥ 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.

Knowledge Bases. A knowledge base is a pair (D, Σ), where D is a database, and Σ is a program. For programs Σ, ΣT and ΣNC are the subsets of Σ containing the TGDs and NCs of Σ, respectively. The set of models of KB =(D,Σ), denoted mods(KB), is the set of instances {I | I ⊇D∧I |= Σ}. We say that KB is consistent, if mods(KB) ̸= ∅, otherwise KB is inconsistent. The answer to a CQ q relative to KB is the set of tuples ans(q,KB) = ⋂{q(I) | I ∈ mods(KB)}. The answer to a BCQ q is true, denoted KB |= q, if ans(q,KB) ̸= ∅. The decision version of the CQ answering problem is as follows: given a knowledge base KB, a CQ q, and a tuple of constants t, decide whether t ∈ ans(q,KB). Since CQ answering can be reduced in LOGSPACE to BCQ answering, we focus on BCQs. Following Vardi (1982), 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 fpcombined) complexity considers the sets of TGDs and NCs as fixed; the data complexity also assumes the query fixed.

The Datalog± languages that we consider to guarantee decidability are among the most frequently analyzed in the literature, namely, linear (L) [Calì et al., 2012a], guarded (G) [Calì et al., 2013], sticky (S) [Calì et al., 2012b], and acyclic TGDs (A), along with their "weak" (proper) generalizations weakly guarded (WG) [Calì et al., 2013], weakly sticky (WS) [Calì et al., 2012b], and weakly acyclic TGDs (WA) [Fagin et al., 2005], as well as their "full" (proper) restrictions linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively, and full (i.e., existential-free) TGDs (F) in general. We also recall the following further inclusions: L⊂G, F⊂WA⊂WS, and F⊂WG. We refer to [Eiter et al., 2016] for a more detailed overview and complexity results.

Complexity Classes. We briefly recall the complexity classes that we encounter. The complexity class AC0 is the class of all decision problems that can be solved by uniform families of Boolean circuits of polynomial size and constant depth. PSPACE (resp., P, EXP, 2EXP) is the class of all problems that can be decided in polynomial space (resp., polynomial time, exponential time, double exponential time) on a deterministic Turing machine. NP and NEXP are the classes of all problems that are decidable in polynomial and exponential time on a nondeterministic Turing machine, respectively, and co-NP and co-NEXP are their complementary classes, where 'yes' and 'no' instances are interchanged. The class ΘP2 is the class of all problems that can be decided in polynomial time by a deterministic Turing machine with either a logarithmic number of calls to an NP oracle, or (equivalently) a constant number of rounds of polynomially many parallel calls to an NP oracle. P NEXP is the class of all problems that are decidable in deterministic polynomial time using a NEXP oracle. The class ΣP2 is the class of all problems that can be decided in nondeterministic polynomial time using an NP oracle, and ΠP2 is the complement of ΣP2 . The above complexity classes and their inclusion relationships (which are all currently believed to be strict) are: AC0 ⊆ P ⊆ NP, co-NP ⊆ ΘP2 ⊆ ΣP2 ,ΠP2 ⊆ PSPACE ⊆ EXP ⊆ NEXP, co-NEXP ⊆ P NEXP ⊆ 2EXP.

3 Approximate Inconsistency Semantics

We now recall three prominent inconsistency-tolerant semantics for ontology-based query answering, namely, the ABox repair (AR) semantics and its approximation by the intersection of repairs (IAR) and the intersection of closed repairs (ICR) semantics [Lembo et al., 2010; Bienvenu, 2012]; all three are based on the notion of repair, which is a maximal consistent subset of the given database. Furthermore, we newly define generalized repair variants [Eiter et al., 2016] of the two intersection-based approximate repair semantics.

Classically, errors leading to inconsistencies are assumed to be only in the database. Eiter et al. [2016] introduced the generalized inconsistency semantics allowing for errors also in the ontology, and for parts of the database and the ontology to be without errors. We analyze the aforementioned inconsistency-tolerant semantics also for this generalized framework. More specifically, for a knowledge base (D, Σ), the generalized semantics allows also (i) to minimally remove TGDs from Σ, and (ii) to partition both D and Σ into a hard and a soft part of non-removable and removable elements, respectively. The so partitioned database (resp., program) is called flexible database (resp., program).

One application of the generalized semantics is debugging mappings between distributed ontologies. In this context, every ontology for itself is error-free, whereas the mappings between the ontologies may be erroneous (e.g., as they are automatically generated). Similarly, some (e.g., manually checked) parts of the underlying databases may be without errors, while other (e.g., automatically generated) parts may contain errors. Under the generalized semantics, inconsistent distributed ontologies are repaired by removing a minimal set of database atoms and existential rules from the mappings.

Another important application is debugging ontologies that have been created in part manually (or checked manually, ensuring error-freeness) and in part enriched by automatically learned additional parts. The manually created part is modeled as the hard database and program, while the additionally learned part is the soft database and program.

Notice that NCs are non-removable (only TGDs can be removed). This is especially well-suited in the aforementioned applications, which require to repair rules, but not negative constraints (or equality-generating dependencies).

A flexible database is a pair (Dh,Ds) of databases, called the hard and soft database, respectively. A flexible program is a pair (Σh,Σs) consisting of a finite set Σh of TGDs and NCs and a finite set Σs of TGDs, called the hard and soft program, respectively. A flexible knowledge base is a pair ((Dh, Ds), (Σh, Σs)), where (Dh, Ds) is a flexible database, and (Σh,Σs) is a flexible program. Note that a (standard) knowledge base (D,Σ) is a special case of a flexible one ((Dh, Ds), (Σh, Σs)), where Dh =∅, Ds =D, Σh =Σ, and Σs = ∅. Below, we provide definitions for flexible knowledge bases that generalize the ones for (standard) knowledge bases.

For knowledge bases KB ′ =(D′ ,Σ′ ) and KB ′′ =(D′′ , Σ′′ ), we write KB ′ ⊆KB ′′ , if D′ ⊆D′′ and Σ′ ⊆Σ′′ . A selection of a flexible knowledge base ((Dh,Ds), (Σh, Σs)) is a knowledge base (D′ ,Σ′ ) such that Dh ⊆ D′ ⊆(Dh∪Ds) and Σh⊆Σ′ ⊆(Σh∪Σs). A repair of a flexible knowledge base FKB is an inclusion-maximal consistent selection of FKB. Rep(FKB) denotes the set of all repairs of FKB. Notice that for (standard) knowledge bases, a repair is usually defined as a maximal consistent subset of the database. However, when a flexible knowledge base models a standard one (i.e., Dh = ∅ and Σs = ∅), the definition above coincides with the classical one and the difference is only notational.

Example 1. Consider the flexible database (Dh,Ds) given by

asserting that p is a postdoc, a researcher, a professor, and the leader of the research group g, and that p′ is the leader of g′ . Consider also the flexible program (Σh, Σs) defined as

expressing that professors and postdocs are researchers, professors and postdocs form disjoint sets, and leaderOf has Prof as domain and Group as range. It is easy to see that mods(D, Σ)=∅, since p violates the disjointness constraint.

The flexible knowledge base ((Dh, Ds), (Σh, Σs)) has two repairs (D′ , Σ′ ) and (D′′ , Σ′′ ):

In both, the atom Prof (p) is removed; in the first one, also the rule leaderOf (X, Y ) → Prof (X) is removed, while in the second one, the atom leaderOf (p, g) is removed.

We now define the inconsistency-tolerant semantics considered. For a knowledge base KB =(D,Σ), the closure Cn(KB) of KB is the set of all ground atoms, built from constants in D and Σ, entailed by D and the TGDs of Σ. Let FKB be a flexible knowledge base, and let q be a BCQ.

• FKB entails q under the generalized repair (GR) semantics, if, for all KB ′ ∈ Rep(FKB), KB ′ |= q.
• FKB entails q under the generalized intersection of repairs (GIAR) semantics, if (D∗ ,Σ∗ ) |= q, where D∗ = ⋂{D′ | (D′ ,Σ′ ) ∈ Rep(FKB)} and Σ∗ = ⋂{Σ′ | (D′ , Σ′ ) ∈ Rep(FKB)}.
• FKB entails q under the generalized intersection of closed repairs (GICR) semantics, if (DI,Σ∗ ) |= q, where DI = ⋂{Cn(KB ′ ) | KB ′ ∈ Rep(FKB)} and Σ∗ = ⋂{Σ′ | (D′ ,Σ′ ) ∈ Rep(FKB)}.

In the definition above, observe that if FKB is a standard knowledge base, then Σ∗ =Σ, and thus the definition above generalizes the AR, IAR, and ICR semantics for standard knowledge bases to the case of flexible knowledge bases.

We talk of BCQ answering under the GR, GIAR, and GICR semantics when flexible knowledge bases can be arbitrary, and we talk of BCQ answering under the AR, IAR, and ICR semantics when flexible knowledge bases are restricted to model standard knowledge bases (i.e., Dh = ∅ and Σs = ∅).

4 Complexity Results

We give a precise picture of the complexity of BCQ answering from existential rules under the IAR, ICR, GIAR, and GICR semantics, which is summarized in Fig. 1; it ranges frommembership in AC0 to 2EXP-completeness.

In detail, ICR- and GICR-BCQ answering (Fig. 1, right side) is complete for co-NP (resp., ΘP2 ) in the data (resp., fpcombined) complexity for all languages of existential rules, but for WG⊥, where it is EXP-complete. The combined complexity of ICR- and GICR-BCQ answering is among PSPACE (for L⊥, LF⊥, and AF⊥), EXP (for S⊥, SF⊥, F⊥, and GF⊥), P NEXP (for A⊥), and 2EXP (for G⊥, WS⊥, WA⊥, and WG⊥), while the ba-combined complexity is among ΠP2 (for L⊥, LF⊥, AF⊥, S⊥, SF⊥, F⊥, and GF⊥), EXP (for G⊥ and WG⊥), P NEXP (for A⊥), and 2EXP (for WS⊥ and WA⊥). So, the complexity of ICR- and GICR-BCQ answering nearly coincides with the complexity of AR- and GR-BCQ answering [Eiter et al., 2016], except for the ΘP2 (rather than ΠP2 ) entries. The complexity of IAR- and GIAR-BCQ answering (Fig. 1, left side) slightly drops to AC0 and NP in the data and fp-combined complexity, resp., for the first-order rewritable languages (i.e., for L⊥, LF⊥, AF⊥, S⊥, SF⊥, and A⊥).

The EXP- and 2EXP-hardness results for WG⊥ are immediate by the EXP- and 2EXP-hardness of standard BCQ answering in these cases. In the rest of this section, we give proof sketches and ideas for some of the other results.

4.1 Membership Results

IAR semantics. For a knowledge base (D,Σ), where Σ = ΣT ∪ΣNC is over a Datalog± language whose BCQ answering is in C, we can decide in NPC that (D, Σ) does not entail a BCQ q under IAR semantics by guessing and checking that there exist: (1) a database D⋆ ⊆D with (D⋆ , ΣT ) ̸|=q, and (2) repairs D′α with α̸∈D′α, one for each α ∈ D \ D⋆ (witnessing that the intersection of the repairs is a subset of D⋆ ).

This proves all upper bounds equal to and above co-NP in Fig. 1, left side, excluding the ΘP2 memberships.

Theorem 2. If BCQ answering from databases under programs over some Datalog± language L is in C in the data (resp., fp-combined, ba-combined, and combined) complexity, then IAR-BCQ answering from databases under programs over L is in co-NPC in the data (resp., fp-combined, ba-combined, and combined) complexity.

Consider the Datalog± languages whose BCQ answering in the data complexity is in AC0 , i.e., L⊥, S⊥, A⊥, LF⊥, AF⊥, and SF⊥. To evaluate a BCQ under the IAR semantics, in the fp-combined complexity, the NCs are fixed and correspond to a fixed UCQ over the database. We can thus compute all ground instances of conjunctions, and calculate all minimal ones in polynomial time. We then remove all their atoms from the database, producing the intersection of all repairs, which we use to evaluate the query, which is in NP for L⊥, S⊥, and A⊥ (and so also for LF⊥, AF⊥, and SF⊥); this is thus also the overall upper bound in the fp-combined complexity.

Theorem 3. IAR-BCQ answering for L⊥, S⊥, and A⊥ (and LF⊥, AF⊥, and SF⊥) is in NP in the fp-combined complexity.

Consider next the Datalog± languages whose BCQ answering in the data complexity is in P. In the fp-combined complexity, checking that a selection of a knowledge base in WS⊥ or G⊥ (and thus also in WA⊥, F⊥, or GF⊥) is a repair is feasible in polynomial time, because the TGDs and NCs are fixed, and answering BCQs in the data complexity and atomic queries in the fp-combined complexity for these languages is in P. A P machine can compute the intersection of the repairs by asking in parallel to polynomially many NP oracles whether there exists a repair that excludes a specific ground atom. Once the intersection is computed, an additional NP oracle call allows to decide whether the intersection of repairs entails the query-we recall that BCQ answering in the fpcombined complexity for the WS⊥ and G⊥ (and thus also for the WA⊥, F⊥, and GF⊥) languages is in NP. Overall, BCQ query answering under the IAR semantics is in ΘP2 , which proves all ΘP2 upper bounds in Fig. 1, left side.

Theorem 4. IAR-BCQ answering for WS⊥ and G⊥ (and WA⊥, F⊥, and GF⊥) is in ΘP2 in the fp-combined complexity.

ICR semantics. The following theorem shows that ICRBCQ answering for a Datalog± language L is in co-NPC in the data, fp-combined, and ba-combined complexity, where C is an upper bound for BCQ answering for L. It can be shown similarly to Theorem 2: we guess and verify some D⋆ ⊆Cn(D,ΣT ) with (D⋆ , ΣT ) ̸|=q, and, for each (of the polynomially many) α∈Cn(D,ΣT ) \D⋆ , some repair D′α with α̸∈Cn(D′α,ΣT ). This proves all corresponding upper bounds in Fig. 1, right side, including the P NEXP = coNP NEXP membership for A⊥, excluding memberships in ΘP2 .

Theorem 5. If BCQ answering from databases under programs over some Datalog± language L is in C in the data (resp., fp- and ba-combined) complexity, then ICR-BCQ answering from databases under programs over L is in co-NPC in the data (resp., fp- and ba-combined) complexity.

ICR-BCQ answering for all the considered Datalog± languages but WG⊥ is in ΘP2 in the fp-combined complexity. This is obtained by adapting the proof of Theorem 4: a P machine computes the intersection of closed repairs by asking in parallel to its NP oracle whether a ground atom is not in the closure of a repair. Being the program fixed, there are only polynomially many different ground atoms to consider. This proves all ΘP2 upper bounds in Fig. 1, right side.

Theorem 6. ICR-BCQ answering for all the considered Datalog± languages but WG⊥ is in ΘP2 in the fp-combined complexity.

As for the combined complexity of ICR-BCQ answering, let (D, Σ) be a knowledge base with Σ over a Datalog± language whose BCQ reasoning is in a deterministic complexity class C. We can decide in PSPACE·C that (D,Σ) does not entail a BCQ q by checking, for all ground instances q′ of q, that there is a repair D⋆ ⊆D such that (D⋆ ,ΣT ) ̸|= q′ . This proves all corresponding upper bounds in Fig. 1, right side, including the P NEXP = PSPACE · P NEXP membership for A⊥,

Theorem 7. If BCQ answering from databases under programs over some Datalog± language L is in the deterministic complexity class C in the combined complexity, then ICRBCQ answering from databases under programs over L is in PSPACE · C in the combined complexity.

Generalized repair semantics. All upper bounds for IAR (resp., ICR) BCQ answering from databases D under Datalog± programs Σ carry over to GIAR (resp., GICR) BCQ answering from databases (Dh,Ds) under Datalog± programs (Σh, ∅). Based on this, also all membership results for IAR (resp., ICR) BCQ answering under existential rules carry over to GIAR (resp., GICR) BCQ answering, as long as the existential rules are closed under adding 0-ary body atoms, proving all corresponding upper bounds in Fig. 1 but for the linear cases (for which it is not hard to derive the upper bounds by genuine proofs: rules in the repair can be polynomially guessed, like data).

Theorem 8. Let L be a Datalog± language that is closed under adding 0-ary atoms to rule bodies. If IAR (resp., ICR) BCQ answering from databases and programs over L is in C in the data, combined, and ba- and fp-combined complexity, then GIAR (resp., GICR) BCQ answering from flexible databases and programs over L is also in C in the data, combined, and ba- and fp-combined complexity, respectively.

4.2 Hardness Results

As BCQ answering under the IAR and ICR semantics for Datalog± languages L coincides with BCQ answering for L when there are no inconsistencies, we immediately obtain hardness for all NP, PSPACE, EXP, and 2EXP entries in Fig. 1.

IAR semantics. co-NP-hardness of BCQ answering under IAR semantics in the data complexity is shown by a reduction from unsatisfiability of 3CNF formulas. It produces a knowledge base with a fixed GF⊥ program and fixed query. This proves all open co-NP-hardness results in Fig. 1, left side.

Theorem 9. IAR-BCQ answering for GF⊥ (and F⊥) is coNP-hard in the data complexity.

The following result shows that IAR-BCQ answering for A⊥ is P NEXP -hard in the ba-combined complexity, proving all P NEXP -hardness results in Fig. 1, left side. Intuitively, the reduction for the P NEXP -hardness proof in [Eiter et al., 2016] for AR-BCQ answering for A⊥ in the ba-combined complexity is turned into a P NEXP -hardness proof for IAR-BCQ answering in this case. There, one encodes initial tiling assignments v1(Xi), . . . , vn(Xn) and has a ground atomic query q, which we now also include in the database along with a fresh ground atom nq and the NC v1(Xi) ∧ . . . ∧ vn(Xn) ∧ q ∧ nq → ⊥. This intuitively "forces" the atom q into the database.

Theorem 10. IAR-BCQ answering for A⊥ is P NEXP -hard in the ba-combined complexity.

The next result shows that BCQ answering under the IAR semantics for GF⊥ (and thus also for F⊥, G⊥, WA⊥, and WS⊥) in the fp-combined complexity is ΘP2 -hard. A sketch of the technically quite involved proof is given below.

Theorem 11. IAR-BCQ answering for GF⊥ (and F⊥, G⊥, WA⊥, and WS⊥) is ΘP2 -hard in the fp-combined complexity.

Proof (sketch). We show a reduction from the ΘP2 -complete problem COMP-SAT: for two sets A and B of 3CNF formulas, decide whether A contains more satisfiable formulas than B [Lukasiewicz and Malizia, 2016; 2017]. COMP-SAT is ΘP2 -hard even if its instances (A,B) are restricted to be such that |A| = |B|, all formulas in A and B are defined over the same variables and have the same number of clauses, and A = {φ1, . . . , φt} and B = {ψ1, . . . , ψt} are such that φu+1 (resp., ψu+1) being satisfiable implies φu (resp., ψu) being satisfiable, for any u (intuitively, all satisfiable formulas have the lowest indices in sets A and B). From this, it follows that (A,B) is a 'yes'-instance of COMP-SAT iff there is an index u such that φu ∈ A is satisfiable, and ψu ∈ B is not.

From an instance (A,B) of COMP-SAT, we build the knowledge base KBCS1 ((A,B)) = (DCS1 ,ΣCS1 ) as follows. Let us assume that all formulas in sets A and B are defined over variables X = {x1, . . . , xn} and clauses C = {c1, . . . , cm}, with ℓj,k denoting the kth literal of the j th clause, and vj,k denoting the variable of literal ℓj,k.

Let us see the encoding of formulas ψu(X) ∈ B. For each variable xi ∈ X, there are facts Val(u, xi, t) and Val (u, xi, f ) in DCS1 , where u, xi, t , and f are constants referring to the formula number u, variable xi, and the Boolean values true and false, respectively. Constant u in the atoms above and below is required so that atoms referring to different formulas ψu ∈ B do not interfere. For each clause cj:

• there is a fact SuccCl (u, j -1, j) in DCS1 , where j -1 and j are numeric constants, and intuitively stating that the j th clause is the successor of the (j-1)th clause; and
• there is a fact encoding cj; e.g., for a clause (xp ∨ xq ∨ ¬xr), there is the fact Cl(u, j, xp, p, xq, p, xr, n) in DCS1 , where p and n are constants telling whether a literal appears positively or negatively, respectively.

Three extra facts are in DCS1 : SatChain(u, 0), MaxCl(u, m), and Unsat(u), where m is a numeric constant for the number of the formula's clauses. Rules of KBCS1 are:

Let us now see how to encode (the satisfiability) of formulas φu(X) ∈ A via facts in the database and a specific query. For each clause cj of φu(X), in the database DCS1 , there are facts encoding cj along with all the possible assignments satisfying cj . For example, for a clause (xp∨xq ∨¬xr), there are 7 facts, each of them for a possible way of satisfying cj :

where u, xp, xq, ¬xr, t, and f are constants referring to formula number u, literals xp, xq, and ¬xr, and the Boolean values true and false, respectively. Predicates encoding clauses of A's formulas are distinct from those of B's formulas.

Furthermore, in DCS1 , there are specific facts to enforce consistent assignments when recognizing satisfiable formulas in A. In particular, for each variable xi, there are 8 facts:

We define the query by showing its parts. A part enforces that assignments selected to satisfy formulas in A are consistent:

Another query's part identifies satisfiable formulas in A:

The query is qCS1 = (∃U,L1,1, T1,1, . . . ,Lm,3, Tm,3) (Clauses ∧ Consistency ∧ Unsat(U)). The TGDs do not depend on (A, B). KBCS1 (φ) is guarded and full.

It is possible to show that there is an index u, for which φu ∈ A is satisfiable and ψu ∈ B is unsatisfiable, iff KBCS1 entails qCS1 under the AR, ICR, and IAR semantics.

ICR semantics. ICR-BCQ answering in the data complexity is co-NP by a reduction unsatisfiability of 3CNF formulas. The reduction produces a knowledge base with a fixed LF⊥, AF⊥, and SF⊥ program and a fixed query. This proves all open co-NP-hardness results in Fig. 1, right side.

Theorem 12. ICR-BCQ answering for LF⊥, AF⊥, and SF⊥ (and GF⊥, F⊥, and A⊥) is co-NP-hard in the data complexity.

BCQ answering under the ICR semantics is ΘP2 -hard in the fp-combined complexity for all remaining entries in Fig. 1, right side, except for WG⊥. The proof adapts the reduction used in Theorem 11 with the reduction of Theorem 12.

Theorem13. ICR-BCQ answering in the fp-combined complexity is ΘP2 -hard for all the considered Datalog± languages.

BCQ answering under the ICR semantics for AF⊥ (and so also for F⊥) is ΠP2 -hard in the ba-combined complexity.

Theorem 14. ICR-BCQ answering is ΠP2 -hard in the bacombined complexity for AF⊥ (and F⊥).

Proof (sketch). The hardness result is proven via a reduction from the ΠP2 -complete problem NQBF2,∀ [Greco et al., 2011; Schaefer, 2001]: decide the validity of a formula Φ = (∀X)(∃Y )φ(X, Y ), where X = {x1, . . . , xn}, Y = {y1, . . . , yr}, and φ(X, Y ) = ci(1) ∧ ci(1) ∧ · · · ∧ ci(n) ∧ ci(n) ∧ c1 ∧ · · · ∧ cm is a 3CNF formula, where each xk ∈ X occurs only in the two clauses ci(k) = (xk ∨ ¬yk) and ci(k) = (¬xk ∨ yk)-intuitively, each variable xk enforces the truth value of the variable yk.

The key ideas of the reduction are as follows. Repairs encode the assignments over X. The satisfiability of φ(X, Y ) is checked through a TGD in which, via tailored facts in the knowledge base, we impose that the assignments over Y are consistent and they match the assignments over X. The predicate in the TGD's head can be derived iff φ(X, Y ) can be satisfied given the assignment over X encoded in the repair. The TGD's head can be derived in all repairs iff Φ is valid.

The following shows that ICR-BCQ answering for A⊥ is P NEXP -hard in the ba-combined complexity, proving all P NEXP - hardness results in Fig. 1, right side. This follows from the fact that ICR-BCQ answering coincides with AR-BCQ answering for ground BCQs, and that the P NEXP -hardness proof in [Eiter et al., 2016] for AR-BCQ answering for A⊥ in the ba-combined complexity only uses a ground atomic query.

Theorem 15. ICR-BCQ answering for A⊥ is P NEXP -hard in the ba-combined complexity.

The following shows all ΠP2 -hardness results in Fig. 1, right side. It is proved by adapting the proof of Theorem 14, where the TGD is encoded as two negative constraints. The ΠP2 - hardness results in Fig. 1, left side, are proved similarly.

Theorem 16. ICR-BCQ answering for L⊥, LF⊥, AF⊥, S⊥, SF⊥, F⊥, and GF⊥ is ΠP2 -hard in the ba-combined complexity.

Generalized repair semantics. The next result shows that all hardness results for IAR- and ICR-BCQ answering under the different classes of existential rules carry over to GIAR- and GICR-BCQ answering, proving all lower bounds in Fig. 1.

Theorem 17. If IAR (resp., ICR) BCQ answering from databases and programs over a Datalog± language L is C-hard in the data, combined, and ba- and fp-combined complexity, then GIAR (resp., GICR) BCQ answering from flexible databases and programs over L is also C-hard in the data, combined, and ba- and fp-combined complexity, respectively.

5 Summary and Outlook

We have given a precise picture of the complexity of BCQ answering under different approximate inconsistency-tolerant semantics (namely, the intersection of repairs (IAR) and the intersection of closed repairs (ICR) semantics) for the most popular Datalog± languages and complexity measures. In addition to the standard setting, where only database atoms can be removed, we have also considered the more general setting, where also rules may be removed (called generalized IAR (GIAR) and generalized ICR (GICR) semantics).

Future research lines include considering other classes of existential rules and to define other semantics for inconsistency-tolerant ontological query answering. In particular, it would be interesting to explore whether there are datatractable and/or even first-order rewritable other such semantics. Furthermore, a more fine-grained way to analyze the complexity of query answering would be a non-uniform approach, looking at the complexity of a single ontology or a single ontology-mediated query (see, e.g., [Bienvenu et al., 2014b; Koutris and Suciu, 2014; Hernich et al., 2017]).

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.