The Impact of Disjunction on Query Answering Under Guarded-Based Existential Rules

1 Introduction

Rule-based languages have a prominent presence in the areas of artificial intelligence and databases. A noticeable formalism, originally intended for expressing complex queries over relational databases, is Datalog, i.e., function-free first-order Horn logic. Strong interest in enhancing Datalog with existential quantification in rule-heads emerged in recent years, see, e.g., [Baget et al., 2011a; 2011b; Kr¨otzsch and Rudolph, 2011; Thomazo et al., 2012; Cal`ı et al., 2012a]. This interest stems from the inability of plain Datalog to infer the existence of new objects which are not already in the extensional database [Patel-Schneider and Horrocks, 2007]. The obtained rules are known under a variety of names such as existential rules, tuple-generating dependencies (TGDs), and Datalog± rules. Unfortunately, the addition of existential quantification as explained above can easily lead to undecidability of the main reasoning tasks, and in particular of conjunctive query answering [Beeri and Vardi, 1981]. Therefore, several concrete languages which guarantee decidability have been proposed, see, e.g., [Fagin et al., 2005; Cal`ı et al., 2008; Baget et al., 2011a; Kr¨otzsch and Rudolph, 2011; Cal`ı et al., 2012a; 2012b; Leone et al., 2012]. Nevertheless, TGDs in general are not powerful enough for nondeterministic reasoning.

Example 1 Consider the following set of rules:

σ1 : parentOf (X, Y ), father(Y ) → ∃Z gparentOf (X,Z)

σ2 : gparentOf (X, Y ) → child(Y )

σ3 : child(X) → boy(X) ∨ girl(X)

which expresses a simple and natural statement: "a parent of a father is a grandparent of some child, which in turn is a boy or a girl". Although σ1 and σ2 are TGDs, σ3 is not, due to the presence of disjunction in the head.

Obviously, to be able to represent such kind of disjunctive knowledge, we need to enrich the existing classes of TGDs with disjunction in the head, or, equivalently, to consider disjunctive TGDs (DTGDs) [Deutsch and Tannen, 2003]. Such an extension of plain Datalog (a.k.a. full TGDs), called disjunctive Datalog, has been studied in [Eiter et al., 1997]. More recently, special cases of the problem of query answering under guarded-based DTGDs have been investigated [Alviano et al., 2012; Gottlob et al., 2012]. However, the picture of the computational complexity of the problem is still foggy, and there are several challenging issues to be tackled.

Our main goal is to better understand the impact of disjunction on query answering under the main guarded-based classes of TGDs, and how existing complexity results for TGDs are affected by adding disjunction. Guardedness is a well-accepted paradigm, giving rise to robust languages that capture important lightweight description logics such as DLLite [Calvanese et al., 2007] and EL [Baader, 2003].

In the present work, we concentrate on the following fundamental questions: what is the exact complexity of conjunctive query (CQ) answering under (weakly-)(frontier-)guarded DTGDs [Cal`ı et al., 2008; Baget et al., 2011a], and their main subclasses, i.e., linear DTGDs and disjunctive IDs (DIDs) [Cal`ı et al., 2012a]? How is it affected if we consider a signature of bounded arity, or a fixed set of dependencies? Moreover, how is it affected if we pose the queries in a more expressive query language, in particular using unions of CQs (UCQs)? As we shall see, the addition of disjunction has a significant effect on the complexity of CQ answering. Indeed, we establish an unexpectedly strong lower bound, which is critical towards the closing of the above issues.

Our contributions can be summarized as follows:

1. We show that CQ answering for (weakly-)(frontier-) guarded DTGDs is 2EXPTIME-complete in the combined complexity; this also holds for UCQs. Regarding the data complexity, we show that under frontierguarded DTGDs it is coNP-complete, while for weaklyfrontier-guarded it is EXPTIME-complete. The upper bounds are easily obtained by exploiting results on more expressive languages such as guarded negation firstorder logic [B´ar´any et al., 2011], while the lower bounds are inherited from existing results on TGDs.
2. We show that CQ answering under a fixed set of DIDs is 2EXPTIME-hard, even if restricted to predicates of arity at most three. In case of UCQs, the above result holds even for unary and binary predicates. These surprisingly strong lower bounds are established by a reduction from an appropriate variant of the validity problem of CQs w.r.t. a B¨uchi automaton [Bj¨orklund et al., 2008]. Together with the 2EXPTIME upper bound discussed above, this gives us the complete picture for the computational complexity of our problem.
3. We investigate a natural fragment of DIDs with lower combined complexity. In fact, we consider frontier-one dependencies (i.e., only one variable is propagated from the body to the head), and we show that the combined complexity decreases to EXPTIME-complete.
4. We show that frontier-guarded DTGDs, combined with negative constraints, are strictly more expressive than DL-LiteHbool [Artale et al., 2009], one of the most expressive languages of the DL-Lite family. This allows us to show that query answering under DL-LiteHbool is in 2EXPTIME in combined complexity. The matching lower bound holds since our complexity results on DIDs imply that, for every description logic equipped with limited existential quantification, role inverse and union, query answering is 2EXPTIME-hard.

A technical report containing the full proofs is available at http://www.cs.ox.ac.uk/people/michael.morak/pubs/ ijcai2013-techrep.pdf.

2 Preliminaries

Technical Definitions. We define the following pairwise disjoint (infinite) sets: a set Γ of constants, a set ΓN of labeled nulls, and a set ΓV of regular variables. We denote by X sequences (or sets) of variables X1, . . . ,Xk. A relational schema R is a set of relational symbols (or predicates). A position r[i] in R is identified by a predicate r ∈ R and its i-th argument. A term t is a constant, null, or variable. An atom has the form r(t1, . . . , tn), where r is a relation, and t1, . . . , tn are terms. For an atom a, we denote terms(a) and var(a) the set of its terms and the set of its variables, respectively; these extend to sets of atoms. Conjunctions and disjunctions of atoms are often identified with the sets of their atoms. An instance I for a schema R is a (possibly infinite) set of atoms r(t), where r ∈ R and t is a tuple of constants and nulls. A database D is a finite instance such that terms(D) ⊂ Γ. We assume the reader is familiar with (unions of) conjunctive queries ((U)CQs). The answer to a CQ q over an instance I is denoted q(I). A Boolean (U)CQ q has positive answer over I, denoted I |= q, if 〈〉 ∈ q(I).

Disjunctive Tuple-generating Dependencies. A disjunctive tuple-generating dependency (DTGD) σ over a schema R is a first-order formula ∀Xϕ(X) → ∨ni=1 ∃Yψi(X,Yi), where n ⩾ 1, X ∪ Y ⊂ ΓV , and ϕ, ψ1, . . . , ψn are conjunctions of atoms over R; ϕ is the body of σ, denoted body(σ), while ∨ni=1 ψi is the head of σ, denoted head(σ). If n = 1, then σ is called tuple-generating dependency (TGD). For brevity, we will omit the universal quantifiers in front of DTGDs. An instance I satisfies σ, written I |= σ, if the following holds: whenever there exists a homomorphism h such that h(ϕ(X)) ⊆ I, then there exists i ∈ {1, . . . , n} and h′ ⊇ h such that h′ (ψi(X,Yi)) ⊆ I; I satisfies a set Σ of DTGDs, denoted I |= Σ, if I satisfies each σ ∈ Σ.

A DTGD σ is guarded if there exists an atom a ∈ body(σ), called guard, which contains all the variables occurring in body(σ). Weakly-guarded DTGDs extend guarded DTGDs by requiring only the body-variables that appear at affected positions, i.e., positions at which a null value may appear during the disjunctive chase (see below) to appear in the guard; for the formal definition see [Cal`ı et al., 2008]. The concept of frontier can be used to generalize (weakly-)guarded DTGDs. The frontier of a DTGD σ is the set of variables var(body(σ))∩var(head(σ)). σ is frontier-guarded if there exists an atom a ∈ body(σ) which contains all the variables occurring in its frontier. The class of weakly-frontier-guarded DTGDs is defined analogously. A DTGD σ is linear if it has only one body-atom. Disjunctive inclusion dependencies (DIDs) are obtained by restricting linear DTGDs as follows: the head is a disjunction of atoms (and not of conjunctions), and there are no repeated variables in the body or in the head.

Query Answering. The models of D and Σ, denoted mods(D,Σ), is the set of instances {I | I ⊇ D and I |= Σ}. The answer to a CQ q w.r.t. D and Σ, denoted ans(q, D, Σ), is the set of tuples of constants ⋂I∈mods(D,Σ){t | t ∈ q(I)}. The answer to a Boolean CQ q w.r.t. D and Σ is positive, denoted D∪Σ |= q, if 〈〉 ∈ ans(q, D, Σ). The answer to a UCQ w.r.t. D and Σ is defined analogously. The problem, called CQAns, tackled in this work is defined as follows: given a CQ q, a database D, a set Σ of DTGDs, and a tuple of constants t, decide whether t ∈ ans(q,D,Σ). The problem UCQAns is defined analogously. Notice that (U)CQAns for arbitrary CQs can be easily reduced to (U)CQAns for Boolean CQs, just by substituting the given tuple t into the CQs; thus, we focus on Boolean CQs. The data complexity of the above problems is calculated taking only the database as input. For the combined complexity, the query and set of DTGDs count as input as well.

Disjunctive Chase. We employ the disjunctive chase introduced in [Deutsch and Tannen, 2003]. Consider an instance I, and a DTGD σ : ϕ(X) → ∨ni=1 ∃Yψi(X, Y). We say that σ is applicable to I if there exists a homomorphism h such that h(ϕ(X)) ⊆ I, and the result of applying σ to I with h is the set {I1, . . . , In}, where Ii = I ∪ h′ (ψi(X, Y)), for each i ∈ {1, . . . , n}, and h′ ⊇ h is such that h′ (Y ) is a "fresh" null not occurring in I, for each Y ∈ Y. For such an application of a DTGD, which defines a single DTGD chase step, we write I〈σ, h〉{I1, . . . , In}. A disjunctive chase tree of a database D and a set Σ of DTGDs is a (possibly infinite) tree such that the root is D, and for every node I, assuming that {I1, . . . , In} are the children of I, there exists σ ∈ Σ and a homomorphism h such that I〈σ, h〉{I1, . . . , In}. The disjunctive chase algorithm for D and Σ consists of an exhaustive application of DTGD chase steps in a fair fashion, which leads to a disjunctive chase tree T of D and Σ; we denote by chase(D,Σ) the set {I | I is a leaf of T}. Note that each leaf of T is well-defined as the least fixpoint of a monotonic operator. By construction, each instance of chase(D,Σ) is a model of D and Σ. Interestingly, chase(D,Σ) is a universal set model of D and Σ, i.e., for each I ∈ mods(D,Σ), there exists J ∈ chase(D,Σ) and a homomorphism hJ such that hJ(J) ⊆ I [Deutsch et al., 2008]. This implies that, given a UCQQ, D∪Σ |= Q iff I |= Q, for each I ∈ chase(D,Σ).

Guarded Negation FO. Guarded negation first-order logic (GNFO) restricts first-order logic by requiring that all occurrences of negation are of the form a ∧ ¬ϕ, where a is an atom containing all the free variables of ϕ [B´ar´any et al., 2011]. The formulas of GNFO are generated by the recursive definition ϕ ::= r(t1, . . . , tn)|t1 = t2|ϕ1 ∧ ϕ2|ϕ1 ∨ ϕ2|∃Xϕ|a ∧ ¬ϕ. GNFO is strictly more expressive than guarded first-order logic (GFO) [Andr´eka et al., 1998].

3 Known Results on Guarded-based DTGDs

We give an overview over known results, and we survey the best existing lower bounds that can be immediately inherited. Our discussion is outlined in Table 1, where each row corresponds to a fragment of DTGDs (which is decoded by substituting L for linear, G for guarded, W for weakly and F for frontier), each column corresponds to a complexity variant, and known completeness results are shown in boldface.

Overview. To the best of our knowledge, the only work done on query answering under guarded-based disjunctive DTGDs can be found in [Alviano et al., 2012] and [Gottlob et al., 2012]. The first paper investigates the data complexity of query answering under (weakly-)guarded and linear DTGDs. For weakly-guarded it is EXPTIME-complete, while for guarded and linear it is coNP-complete. Moreover, the case of atomic queries has been considered, and it was shown that it is in LOGSPACE. Notice that the above coNP-hardness is implicit in [Calvanese et al., 2006], where it was shown that query answering under a TBox with a single axiom A ⊑ B ⊔ C, which is equivalent to A(X) → B(X)∨C(X), is coNP-hard. The second paper studies both the combined and data complexity of atomic query answering under guarded and linear DTGDs. For guarded DTGDs the combined complexity is 2EXPTIME-complete, while the data complexity is coNP-complete (which agrees with the analogous result above). For linear DTGDs the combined complexity is EXPTIME-complete, while the data complexity is in AC0 (improving the LOGSPACE upper bound mentioned above). Notice that the AC0 upper bound was obtained by showing that the problem is first-order rewritable.

Inherited Lower Bounds. The best existing lower bounds for our problem are the following: (i) 2EXPTIME in combined complexity, and also EXPTIME in case of boudned arity, for guarded DTGDs [Cal`ı et al., 2008], (ii) 2EXPTIME for frontier-guarded DTGDs in case of bounded arity [Baget et al., 2011b; Lutz, 2008], (iii) EXPTIME for DIDs in combined complexity; this holds since the rules employed in [Gottlob et al., 2012] to prove an analogous result for linear DTGDs are DIDs, and (iv) Π2 P for fixed sets of DIDs; this follows from a result in [B´ar´any et al., 2010] which states that query answering under fixed universal GFO sentences is Π2 P -hard. Notice that in the proof of this result a sentence of the form ∀X∀Y ∀Z r(X, Y, Z) → s(X, Y ) ⊕ s(X, Z) is used; however, the result holds even if we replace ⊕ with ∨ since the minimal models of a ∨ b coincide with those of a ⊕ b.

4 The Complexity of Query Answering

Apart from the three known completeness results which are shown in boldface in Table 1, for all the other cases the exact complexity is unknown. We tackle these open problems, and we present a complete picture of the complexity of the problem studied here.

4.1 Combined Complexity

Upper Bound. First, we establish an upper bound for query answering under the most expressive class that we treat in this paper, i.e., weakly-frontier-guarded DTGDs, by exploiting a result on satisfiability of GNFO.

Theorem 1 UCQAns under weakly-frontier-guarded DTGDs is in 2EXPTIME in combined complexity.

Proof (sketch). We provide a reduction to satisfiability of GNFO which is in 2EXPTIME [B´ar´any et al., 2011]. First, we polynomially reduce our problem to UCQAns under frontierguarded DTGDs by exploiting the reduction from weaklyfrontier-guarded TGDs to frontier-guarded TGDs proposed in [Baget et al., 2011b]. Thus, given a UCQ Q, a database D, and set Σ of weakly-frontier-guarded DTGDs, there exists a polynomial translation τ such that D ∪ Σ |= Q iff τ(D)∪τ(Σ) |= τ(Q), where τ(Σ) is a set of frontier-guarded DTGDs. It is easy to see that τ(Σ) can be equivalently rewritten as a GNFO formula [B´ar´any et al., 2012]. More precisely, a frontier-guarded DTGD ∀Xϕ(X) → ∃Yψ(X,Y) is equivalent to ¬(∃Xϕ(X) ∧ ¬∃Yψ(X, Y)) which falls in GNFO since all the free variables of ∃Yψ(X,Y) appear in the frontier-guard of ϕ(X). Moreover, ¬τ(Q) trivially falls in GNFO. Therefore, τ(D) ∧ τ(Σ) ∧ ¬τ(Q) is a GNFO formula and the claim follows since τ(D) ∪ τ(Σ) |= τ(Q) iff τ (D) ∧ τ (Σ) ∧ ¬τ (Q) is unsatisfiable.

Notice that an alternative way to obtain the above result is to reduce our problem to query answering under GFO which is also in 2EXPTIME [B´ar´any et al., 2010].

Lower Bound. Recall that CQAns for guarded TGDs is 2EXPTIME-hard [Cal`ı et al., 2008] in combined complexity, while for frontier-guarded TGDs remains 2EXPTIME-hard even in the case of bounded arity [Baget et al., 2011b]. Although these results, together with Theorem 1, close the combined complexity for (weakly-)(frontier-)guarded, and also the case of bounded arity for (weakly-)frontier-guarded, they are not strong enough to complete the complexity picture of our problem. In what follows we present a series of strong 2EXPTIME lower bounds for query answering. We assume the reader is familiar with B¨uchi automata and infinite trees (see, e.g., [Gr¨adel et al., 2002]).

Theorem 2 CQAns under DIDs is 2EXPTIME-hard, even for predicates of arity at most two.

Before proving the above theorem, we first introduce the following intermediate result: Given a finite set of labels Λ, we define a schema S = {child, parentorchild} ∪ Λ. These predicates are used to represent binary trees, with the obvious semantics. Given a CQ q over S and a B¨uchi tree automaton T over binary trees, where all states are accepting and have at least one successor state, we define q to be valid w.r.t. T, iff it holds that every (possibly infinite) binary tree accepted by T entails q. We claim that deciding this problem is hard for 2EXPTIME, which can be shown by adapting the 2EXPTIMEhardness of the same problem for finite trees over schema S ′ = {child , descendent} ∪ Λ in [Bj ¨orklund et al., 2008].

Proof (sketch). The proof is by reduction from the validity problem of CQs q over S w.r.t. B¨uchi tree automata T over binary trees, as defined above. We construct a database D, a set Σ of DIDs, and a query q′ = q over schema R, such that D ∪ Σ |= q′ iff q is valid w.r.t. T. Let ST be the set of states of T. The schema R is as follows: It includes S, and for each pair (s, a), where s ∈ ST and a ∈ Λ, there are unary predicates s and ps,a in R. Moreover, for each transition (s, a) ↦→ s1, s2 in the transition function δ of T , we have binary predicates child i [(s, a), s1, s2], for i ∈ {1, 2}, in R. Intuitively, child i [(s, a), s1, s2](X, Y ) says that Y is the i-th child of X, where X is in state s and labelled a, and Y is in state si. We now define Σ as follows:

• For each s ∈ ST , s(X) → ∨a∈Λ and δ(s,a)̸=∅ ps,a(X)
• For each (s, a) ∈ ST × Λ, ps,a(X) → a(X)
• For all transitions (s, a) ↦→ s1, s2:
• ps,a(X) → ∃Y child i [(s, a), s1, s2](X, Y )
• child i [(s, a), s1, s2](X, Y ) → si(Y )
• child i [(s, a), s1, s2](X, Y ) → child(X, Y )
• child(X, Y ) → parentorchild(X, Y )
• child(X, Y ) → parentorchild(Y,X)

The database D contains a single atom sI(c), where sI is the initial state of T. For each instance I ∈ chase(D,Σ), if restricted to the child- and label-predicates only, by construction and due to the fact that each state of T has at least one successor, this is an infinite binary tree accepted by T . Moreover, the parentorchild-predicate in I is semantically equivalent to the parentorchild-relation of T , and therefore we get that D ∪ Σ |= q′ only if q is valid w.r.t. T. The converse direction follows from the fact that all states are accepting.

Notice that the constructed set Σ of DIDs in the above proof depends on T, and the underlying schema R contains a predicate for every state and label of T. This proof can now be extended, such that Σ is a fixed set of DIDs and R a fixed schema with arity at most two. However, to devise this encoding, we need the expressive power of UCQs.

Theorem 3 UCQAns under fixed sets of DIDs is 2EXPTIMEhard, even for predicates of arity at most two.

Proof (sketch). We adapt the proof of Theorem 2 in the following way: Instead of labelling each tree node with a state s and label a, we generate a chain of nodes, with the length of the chain encoding s and a. This can easily be done by the DIDs next (X) → ∃Y chain(X, Y ) and chain(X, Y ) → next(Y )∨end(Y ). Using this adaptation, neither the schema nor the set of DIDs depends on T any longer. The CQ of the proof of Theorem 2 can now be carefully adapted to this new encoding of states and labels, and also to check that: (i) any chain has length at most n, where n is polynomial in the size of T, and (ii) each node and its two children are consistent with the transition function of T .

In the following, we will show that the above theorem holds also for CQs, at the expense of increasing the arity of the underlying schema by one. In the sequel, given a schema R, let arity(R) be the maximum arity over all predicates of R. Notice that the following technical result holds for arbitrary DTGDs, and not just for DIDs.

Lemma 4 Let R be a relational schema. Consider a UCQ Q over R, a database D for R, and a set Σ of DTGDs over R. We can construct in polynomial time a CQ q′ over a schema R′ , a database D′ for R′ , and a set Σ′ of DTGDs such that arity(R′ ) = arity(R)+1, andD∪Σ |= Q iff D′ ∪Σ′ |= q′ .

Proof (sketch). The schema R′ is obtained from R by increasing the arity of every predicate by one. Moreover, we add three predicates or, true and false. Each DTGD in Σ is adapted in such a way that it always propagates this additional position to the atoms in the head. Each CQ qi ∈ Q is translated into a new CQ q′i [Xi], where a fresh variable Xi is added to all atoms in qi at the new position. The body of the new query q′ is false(Z1) ∧qi∈Q q′i [Xi]∧or(Zi,Xi,Zi+1)∧ true(Zk+1), where k = |Q|. The database D′ is obtained from D by extending each atom in such a way that the fresh constant t ∈ Γ appears in the new position. Also, the atoms true(t) and false(f), where f ∈ Γ is a fresh constant, are added. Furthermore, we add an isomorphic image of every q′i [Xi] to D′ , where Xi is replaced by f. Finally, we add the atoms or(t, t, t), or(f, t, t), or(t, f, t) and or(f, f, f).

We can show that the above construction is correct. For any query q′i [Xi], there exists a homomorphismmapping it to D′ . However, this is not useful to satisfy q′ , as Xi is mapped to f. By construction however, the only way to satisfy q′ is to map at least one subquery q′i [Xi] to chase(D′ ,Σ′ ), such that Xi maps to t. Note that the only atoms in chase(D′ , Σ′ ) containing t are the ones obtained from the original copy of D. Thus, we have that whenever a subquery qi ∈ Q is true in a model of D∪Σ, then q′ is true in the corresponding model of D′ ∪ Σ′ , and the claim follows.

Theorem 3 and Lemma 4 immediately imply the following:

Corollary 5 CQAns under fixed sets of DIDs is 2EXPTIMEhard, even for predicates of arity at most three.

Interestingly, the above corollary closes an open question stated in [B´ar´any et al., 2010], regarding the complexity of query answering under fixed GFO sentences. It was shown that the problem in question is PSPACE-hard even for CQs, and in EXPTIME in case of acyclic CQs. However, the exact complexity was left as an open problem. Clearly, Corollary 5 gives a 2EXPTIME-completeness result since query answering under GFO is in 2EXPTIME in general. By combining Theorem 1 and Corollary 5, we get the following.

Corollary 6 (U)CQAns under (weakly-)(frontier-)guarded DTGDs, linear DTGDs and DIDs is 2EXPTIME-complete in combined complexity. This holds even for predicates of arity at most three, and for fixed sets of dependencies.

4.2 Data Complexity

As already discussed in Section 3, for guarded and weaklyguarded DTGDs the data complexity is coNP-complete and EXPTIME-complete, respectively. Below, we show that it remains the same for (weakly-)frontier-guarded DTGDs.

Theorem 7 (U)CQAns under frontier-guarded DTGDs is coNP-complete, while for weakly-frontier-guarded DTGDs it is EXPTIME-complete in data complexity.

Proof (sketch). The coNP upper bound is obtained by reducing our problem to UCQAns under GFO sentences. This can be done by employing the linear reduction of CQAns under frontier-guarded TGDs to UCQAns under GFO sentences given in [Baget et al., 2011b]. The lower bound follows immediately since CQAns under DIDs is already coNPhard. Consider now a UCQ Q, a database D, and set Σ of weakly-frontier-guarded DTGDs. First, we reduce our problem to UCQAns under frontier-guarded DTGDs by replacing the non-affected variables in rules with all possible constants in D. Clearly, the obtained set Σ′ is of exponential size in the number of non-affected variables, but of polynomial size in |terms(D)|. As discussed above, a linear translation τ exists such that D ∪ Σ′ |= Q iff D ∪ τ(Σ′ ) |= τ(Q), where τ(Σ′ ) is a GFO sentence and τ(Q) a UCQ. It is important to say that, although |τ(Q)| depends on D, the size of each CQ of τ(Q) does not depend on D. As shown in [B´ar´any et al., 2010], UCQAns under GFO is in 2EXPTIME w.r.t. to the size of each CQ of the given UCQ and the maximum arity of the schema, and in EXPTIME w.r.t. to the size of the sentence. Since the size of each query of τ (Q) and the maximum arity of the schema are constant, and the size of τ (Σ′ ) is polynomial in D, we get an EXPTIME upper bound w.r.t. D. The lower bound follows immediately since UCQAns for weaklyguarded TGDs is EXPTIME-hard [Cal`ı et al., 2008].

5 Reducing the Complexity

In contrast to our previous results, we demonstrate a way of reducing the combined complexity of query answering under DIDs. We consider frontier-one DIDs, i.e., DIDs with a frontier of cardinality exactly one, for which the complexity is reduced to EXPTIME-complete. Notice that the class of frontier-one TGDs has been proposed in [Baget et al., 2011a]. Clearly, frontier-one formalisms are quite close to DL axioms since concept inclusions propagate only one object.

Theorem 8 (U)CQAns for frontier-one DIDs is EXPTIMEcomplete in combined complexity.

Proof (sketch). Consider a database D, and a set Σ of frontier-one DIDs. It is possible to associate a tree structure with every instance I ∈ chase(D,Σ): I is partitioned into bags of atoms, such that I ′ is one such bag, and for each term t occurring in an atom of I \ I ′ , there exists a bag, denoted bag(t), such that the atoms in bag(t) contain t; t is called the input value of bag(t). These bags are used as labels of the tree structure, such that the bag containing I ′ labels the root, and two bags bag(t1), bag(t2) are in a parent-child relation iff there exists an atom containing t2 in bag(t1). Due to the monadic nature of frontier-one DIDs, the number of atoms in each bag is polynomial in D and Σ and the number of isomorphic bags is exponential in the size of Σ.

The above tree structure was introduced in [Benedikt et al., 2012] for finite instances, but can be extended to infinite trees. It is therefore possible to show that there exists a Rabin automaton (see, e.g., [Gr¨adel et al., 2002]) that is empty iff no instance of chase(D, Σ) satisfies q. This tree automaton represents the tree structure of the instances of chase(D, Σ) that do not satisfy q. Moreover, the size of the automaton is exponential in D and Σ due to the fact that, as shown in [Benedikt et al., 2012], for every instance I ∈ chase(D, Σ) with I ̸|= q, the tree structure is diversified (i.e., there is no bag except the root that contains two atoms with the same predicate, and there are no directly related bags sharing a term at the same position). Given that Rabin automata can be checked for emptiness in linear time, we establish the desired upper bound.

The lower bound is obtained by a careful adaptation of the proof of Theorem 2 in order to simulate a PSPACE alternating Turing machine using a chain of length n, instead of a binary tree of depth n, to store the configurations.

Another formalism with a lower combined complexity is the class of full-identity DIDs, that is, rules of the form r(X1, . . . ,Xn) → ∨mi=1 pi(X1, . . . ,Xn) which allow us only to copy a tuple. It is easy to show that the combined complexity reduces to coNP-complete. As we are not able to permutate terms, each instance of the chase is of polynomial size in the database and the schema. Thus, it suffices to guess such an instance I, and check that it does not entail the query. The lower bound is implicit in [Calvanese et al., 2006], where it was shown that query answering under rules of the form A(X) → B(X)∨C(X) is coNP-hard in data complexity. Notice that query answering under DIDs where each rule is frontier-one or full-identity is EXPTIME-complete.

6 Relationships with Existing DLs

As already observed in [Gottlob et al., 2012], guarded DTGDs are strictly more expressive than ELU [Baader et al., 2005], that is, the well-known DL EL extended with disjunction. It is indeed straightforward to see that every normalized ELU TBox, which may contains axioms of the form A ⊑ B, A ⊓ B ⊑ C, A ⊑ ∃R.B and A ⊑ B ⊔ C, where A, B, C are concept names and R is a role name, can be translated in logarithmic space into a set of guarded DTGDs.

The goal of this section is to show an analogous result for DL-LiteHbool [Artale et al., 2009], one of the most expressive languages of the DL-Lite family, and also to investigate the impact of our previously established results on query answering under description logics, and in particular under DLLiteHbool . Let us recall that this logical language contains object names a0, a1, . . ., concept names A0,A1, . . ., and role names P0, P1, . . .. Complex roles R and concepts C are defined as follows: R ::= Pk|P - k , B ::= ⊥|Ak|∃R and C ::= B|¬B|C1 ⊓ C2. A TBox T is a finite set of concept and role inclusion axioms of the form C1 ⊑ C2 and R1 ⊑ R2, and its semantics can be defined by translating it into first-order logic by using an operator τ .

Expressive Power. We establish that frontier-guarded[⊥] DTGDs, that is, the formalism obtained by combining frontier-guarded DTGDs with negative constraints (NCs) of the form ∀Xϕ(X) → ⊥, where ϕ is a conjunction of atoms without any syntactic restrictions, are strictly more expressive than DL-LiteHbool . Notice that the complexity of query answering under frontier-guarded[⊥] DTGDs is the same as for frontier-guarded, since deciding whether the given set of dependencies is consistent can be reduced to query answering under frontier-guarded DTGDs; see, e.g., [Cal`ı et al., 2012a].

It is easy to see that role inclusions are translated by τ into IDs; e.g., τ(R ⊑ S) = R(X, Y ) → S(X, Y ). However, in general, for a concept inclusion C ⊑ D, τ(C ⊑ D) is neither a DTGD nor an NC; however, we can show that any τ(C ⊑ D) can be transformed into a set of frontierguarded[⊥] DTGDs in polynomial time.

Lemma 9 For every concept inclusion α = C ⊑ D, a set Σα of frontier-guarded[⊥] DTGDs can be constructed in polynomial time such that τ(C ⊑ D) and Σα are equisatisfiable.

Proof (idea). Let ψ = τ(C ⊑ D). Viewed as an implication, we can treat the left-hand side as a conjunction and the righthand side as a disjunction of subformulas. Whenever such a subformula ϕ(X) is not atomic or existential (or a negated version of the two), we introduce a new auxiliary predicate tϕ(X) and two implications ϕ(X) ↔ tϕ(X). If ϕ is itself a disjunction, we additionally split the first implication (i.e., where ϕ(X) is on the left) into separate implications for each disjunct, preserving the right-hand side. We then recursively apply this transformation to the new implications, until a fixpoint is reached. The resulting implications, after removing negations by converting negated conjuncts on the left to nonnegated disjuncts on the right (and conversely for disjuncts on the right) are clearly DTGDs or NCs.

Lemma 9 implies that, if TC are the concept inclusions of T , then ΣC = ⋃α∈TC Σα is a set of frontier-guarded[⊥] DTGDs which can be constructed in polynomial time, and it is equisatisfiable with TC. Consequently, τ(TR) ∪ ΣC is a set of frontier-guarded[⊥] DTGDs which is equisatisfiable with T . Since the simple rule s(X) → r(X,X) is not expressible in DL-LiteHbool , the next result follows.

Theorem 10 Frontier-guarded[⊥] DTGDs are strictly more expressive than DL-LiteHbool .

Complexity Results. By exploiting the above construction, query answering under DL-LiteHbool can be reduced in polynomial time to CQAns under frontier-guarded[⊥] DTGDs. Recall that an ABox A is a finite set of assertions of the form Ak(ai), ¬Ak(ai), Pk(ai, aj) and ¬Pk(ai, aj); the semantics of A are defined by τ . A TBox T together with A constitute a knowledge base (KB) K = 〈T , A〉.

Lemma 11 UCQAns under DL-LiteHbool knowledge bases can be reduced in polynomial time to UCQAns under frontierguarded[⊥] DTGDs.

Proof (sketch). Consider a DL-LiteHbool KB K = 〈T ,A〉. Let DA be the database obtained from A by replacing each negated atom ¬A(a) and ¬R(a, b) with A¬(a) and R¬(a, b), respectively, where A¬ and R¬ are auxiliary predicates. Let ΣT = τ(TR) ∪ ΣC ∪ Σ⊥, where Σ⊥ contains an NC A(X), A¬(X) → ⊥ and R(X, Y ), R¬(X, Y ) → ⊥, for each concept A and role R in T , respectively. It is not difficult to verify that K |= Q iff DA ∪ΣT |= Q, for every UCQQ over K. Since ΣT is a set of frontier-guarded[⊥] DTGDs that can be constructed in polynomial time, the claim follows.

It is interesting to observe that the rules employed in the proof of Theorem 2, can be easily rewritten as DL axioms. This immediately gives us the following lower bound.

Theorem 12 Let L be a DL able to express inclusions of the form C1 ⊑ C2 ⊔ C3, C ⊑ ∃R, ∃R ⊑ C, R1 ⊑ R2 and R1 ⊑ R2 , where C,Ci are concepts and R,Ri are roles. Then, CQAns under L is 2EXPTIME-hard.

In [Artale et al., 2009] it was shown that query answering under DL-LiteHbool is coNP-complete in data complexity; however, the combined complexity was not investigated and left as an open problem. Since DL-LiteHbool is a description logic equipped with limited existential qunatification, role inverse and union, Theorems 2 and 12, together with Lemma 11, imply the next complexity result.

Corollary 13 CQAns under DL-LiteHbool knowledge bases is 2EXPTIME-complete in combined complexity.

Interestingly, the above corollary significantly strengthens a similar result for the ALCI DL in [Lutz, 2008].

7 Conclusion

In this paper, we studied in depth the query answering problem under (weakly-)(frontier-)guarded disjunctive TGDs and their main subclasses. Interestingly, query answering under a fixed set of disjunctive IDs is already 2EXPTIME-hard. We also investigated the impact of our results on query answering under DL-based formalisms; in particular, we showed that this problem for DLs equipped with limited existential quantification, role inverse and union is 2EXPTIME-hard. Regarding future work, we intend to investigate the impact of the addition of disjunction on non-guarded-based classes of TGDs.

Acknowledgements. Pierre thankfully acknowledges EPSRC Grant EP/H017690/1 "Query-Driven Data Acquisition from Web-based Datasources", Michael his DOC Fellowship of the Austrian Academy of Sciences and Andreas his EPSRC Grant EP/G055114/1 "Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms and Complexity" and ERC Grant 246858 "DIADEM".