Introduction

Ontologies play a key role in the Semantic Web [4], data modeling, and information integration [19]. Recent trends in ontological reasoning have shifted from decidability issues to tractability ones, as e.g. reflected by the work on the DL-Lite family of tractable description logics (DLs) [12,22]. An important result of these works is that the main variants of DL-Lite are not only decidable, but that answering (unions of) conjunctive queries for these logics is in LOGSPACE, and actually in AC 0 , in data complexity (i.e., the complexity where both the query and the constraints are fixed), and query answering in DL-Lite is FO-rewritable [12]. As observed in [21], the lack of value creation makes plain Datalog not very well suited for ontological reasoning with inclusion axioms either. It is thus natural to extend Datalog in order to nicely accommodate ontological axioms and constraints such as those expressible in the DL-Lite family.

This paper proposes and studies variants of Datalog that are suited for efficient ontological reasoning, and, in particular, for tractable ontology-based query answering. We introduce the Datalog ± family of Datalog variants, which extend plain Datalog by the possibility of existential quantification in rule heads, and by a number of other features, and, at the same time, restrict the rule syntax in order to achieve tractability. In the Datalog ± family, rules are a restricted form of tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). More specifically, in guarded Datalog ± , rules are guarded TGDs (GTGDs), i.e., TGDs with a single atom in the body that contains all universally quantified variables; in linear Datalog ± , rules are linear TGDs (LTGDs), i.e., TGDs that have a single atom in the body. We characterize the data complexity of query answering for both the above sublanguages of Datalog ± . We show that query answering is PTIME-complete and in AC 0 (which is the complexity of evaluating fixed first-order formulas over a database or finite structure), when the query and the set of GTGDs and LTGDs are fixed, respectively. We then enrich Datalog ± by adding negative constraints, which are Horn clauses with a (not necessarily guarded) conjunction of atoms in their body and the truth constant false, denoted ⊥, in the head. We show that the introduction of such constraints does not increase the complexity of query answering in Datalog ± . As a further extension, we add non-conflicting keys, which are special EGDs that do not interact with TGDs, and thus also do not increase the complexity of query answering in Datalog ± . We deal only with keys, since this suffices to capture the most common tractable ontology languages in the literature. The class of non-conflicting keys is a generalization of the one in [10]. Further results. We have several other results that, for space reasons, we do not include here. We refer the reader to [8] for more details. A central result is that the Datalog ± family is able to express the most common tractable ontology languages, in particular, the DL-Lite family [12] and F-Logic Lite [9]. In particular, it is interesting to see that linear Datalog ± enriched with non-conflicting keys is expressive enough to capture the expressive power of the description logics DL-Lite F , DL-Lite R , and DL-Lite A , which are highly suitable for ontological modeling and reasoning. Finally, we are able to deal with an extension of Datalog ± with stratified negation. We provide a canonical model and a perfect model semantics, and we show that they coincide. We thus provide a natural stratified negation for query answering over ontologies, which has been an open problem to date, since it is in general based on several strata of infinite models. Related work. Note that the results of the present paper are related to but very different from the results in [7], where complexity issues of guarded TGDs as well as of another class, called weakly guarded TGDs, were first studied. There, it was shown that the combined complexity of query answering and fact inference with guarded TGDs is 2-EXPTIME complete, and it was noted that the data complexity is polynomial, which is now much refined by the present paper. Extensions of Datalog that allow the introduction of values not appearing in the active domain of the input database have been proposed in the literature [1,5,11,10]; the introduction of such values is usually called value invention. Other works integrate Datalog with description logic knowledge bases [16,6,23], which is a different perspective.

Preliminaries

We briefly recall some basics on databases, queries, TGDs, and the chase. Databases and Queries. We assume (i) an infinite universe of data constants ∆ (which constitute the "normal" domain of a database), (ii) an infinite set of (labeled) nulls ∆ N (used as "fresh" Skolem terms, which are placeholders for unknown values, and can thus be seen as variables), and (iii) an infinite set of variables X (used in dependencies and queries). Different constants represent different values (unique name assumption), while different nulls may represent the same value. We assume a lexicographic order on ∆ ∪ ∆ N , with every symbol in ∆ N following all symbols in ∆. We denote by X sequences of variables X 1 , . . . , X k with k 0. We assume a relational schema R, which is a finite set of relation names (or predicates). A term t is a constant, null, or variable. An atomic formula (or atom) a has the form P (t 1 , ..., t n ), where P is n-ary predicate, and t 1 , ..., t n are terms. We denote by dom(a) the set of all its arguments. These notations naturally extend to sets and conjunctions of atoms. Conjunctions of atoms are often identified with the sets of their atoms. A database (instance) D for R is a (possibly infinite) set of atoms with predicates from R and arguments from ∆ ∪ ∆ N . Such D is ground iff it contains only atoms with arguments from ∆. A conjunctive query (CQ) over R has the form Q(X) = ∃YΦ(X, Y), where Φ(X, Y) is a conjunction of atoms with the variables X and Y. A Boolean CQ (BCQ) over R is a CQ of the form Q(). Answers to CQs and BCQs are defined via homomorphisms, which are mappings µ :

∆ ∪ ∆ N ∪ X → ∆ ∪ ∆ N ∪ X such that (i) c ∈ ∆ implies µ(c) = c, (ii) c ∈ ∆ N implies µ(c) ∈ ∆ ∪ ∆ N ,

and (iii) µ is naturally extended to atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ Q(X) = ∃YΦ(X, Y) over a database D, denoted Q(D), is the set of all tuples t over ∆ for which there exists a homomorphism µ :

X ∪ Y → ∆ ∪ ∆ N such that µ(Φ(X, Y)) ⊆ D and µ(X) = t. The answer to a BCQ Q() over D is Yes, denoted D |= Q, iff Q(D) = ∅.

TGDs. Given a relational schema R, a tuple-generating dependency (TGD) σ is a firstorder formula of the form ∀X∀Y Φ(X, Y) → ∃Z Ψ (X, Z), where Φ(X, Y) and Ψ (X, Z) are conjunctions of atoms over R, called the body and the head of σ, respectively. We usually omit the universal quantifiers in TGDs. Such σ is satisfied in a database D for R iff, whenever there is a homomorphism h that maps the atoms of Φ(X, Y) to atoms of D, there exists an extension h of h that maps the atoms of Ψ (X, Z) to atoms of D. All sets of TGDs are finite here. The notion of query answering under TGDs is defined as follows. For a set of TGDs Σ on R, and a database D for R, the set of models of D given Σ, denoted mods(Σ, D), is the set of all databases B such that B |= D ∪ Σ. The set of answers to a CQ Q on D given Σ, denoted ans(Q, Σ, D), is the set of all tuples a such that a ∈ Q(B) for all B ∈ mods(Σ, D). The answer to a BCQ Q over D given Σ is Yes, denoted D ∪ Σ |= Q, iff ans(Q, Σ, D) = ∅. Note that query answering under general TGDs is undecidable [3], even when the schema and TGDs are fixed [7]. Query answering under a certain class C of TGDs is said to be FO-rewritable iff, for every given CQ Q and for every given set Σ of TGDs in C, there exists a first order query Q F O such that, for every instance D, it holds Q F O (D) = ans(Q, Σ, D). We recall that the two problems of CQ and BCQ evaluation under TGDs are LOGSPACE-equivalent [13,18,17,15]. Moreover, it is easy to see that the query output tuple (QOT) problem (as a decision version of CQ evaluation) and BCQ evaluation are AC 0 -reducible to each other. Henceforth, we thus focus only on the BCQ evaluation problem. All complexity results carry over to the other problems. We also recall that query answering under TGDs is equivalent to query answering under TGDs with only singleton atoms in their heads [7]. In the sequel, w.l.o.g., every TGD has a singleton atom in its head. The TGD Chase. The chase was introduced for checking the implication of dependencies [20], and later also for checking query containment [18]. It repairs a database relative to a set of dependencies, so that the result of the chase satisfies the dependencies. By "chase", we refer both to the chase procedure and to its output. The TGD chase works on a database through so-called TGD chase rules (for an extended chase with also equality-generating dependencies (EGDs), see [8]). The TGD chase rule comes in two flavors: oblivious and restricted, where the restricted one repairs TGDs only when not satisfied. We focus on the oblivious one, since it makes proofs technically simpler. The (oblivious) TGD chase rule defined below is the building block of the chase.

TGD CHASE RULE. Consider a database D for a relational schema R, and a TGD σ on R of the form Φ(X, Y) → ∃Z Ψ (X, Z). Then, σ is applicable to D if there exists a homomorphism h that maps the atoms of Φ(X, Y) to atoms of D. Let σ be applicable, and h 1 be a homomorphism that extends h as follows: for each

X i ∈ X, h 1 (X i ) = h(X i ); for each Z j ∈ Z, h 1 (Z j ) = z j ,

where z j is a "fresh" null, i.e., z j ∈ ∆ N , z j does not occur in D, and z j lexicographically follows all other nulls already introduced. The application of σ adds to D the atom h 1 (Ψ (X, Z)) if not already in D.

The important notion of the (derivation) level of an atom in a TGD chase is defined as follows. Let D be the initial database from which the chase is constructed. Then: (1) The atoms in D have level 0. (2) Let a TGD Φ(X, Y) → ∃Z Ψ (X, Z) be applied at some point in the construction of the chase, and let h and h 1 be as in the TGD chase rule. If the atom with highest level among those in h 1 (Φ(X, Y)) has level k, then the added atom h 1 (Ψ (X, Z)) has level k + 1. The chase algorithm for Σ and D consists of an exhaustive application of the TGD chase rule in a breadth-first (level-saturating) fashion, which leads as result to a (possibly infinite) chase for Σ and D, denoted chase(Σ, D). The chase of level up to k 0 for Σ and D, denoted chase k (Σ, D), is the set of all atoms in chase(Σ, D) of level at most k. The (possibly infinite) chase relative to TGDs is a universal model, i.e., for every B ∈ mods(Σ, D), there exists a homomorphism that maps chase(Σ, D) onto B [15,7], and thus Q(chase(Σ, D)) = ans(Q, Σ, D).

Guarded Datalog ±

We now introduce guarded Datalog ± as a class of special TGDs that show computational data tractability, while being at the same time expressive enough to model ontologies. BCQs relative to such TGDs can be evaluated on a finite part of the chase of constant size in the data complexity.

A TGD σ is guarded iff it contains an atom in its body that contains all universally quantified variables of σ. The leftmost such atom is the guard atom (or guard) of σ. The non-guard atoms in the body of σ are the side atoms of σ.

Example 3.1. The TGD r(X, Y ), s(Y, X, Z) → ∃W s(Z, X, W ) is guarded (via the guard s(Y, X, Z)), while the TGD r(X, Y ), r(Y, Z) → r(X, Z) is not guarded.

Sets of guarded TGDs (with single-atom heads) are theories in the guarded fragment of first-order logic [2]. In the sequel, let R be a relational schema, let D be a database for R, and let Σ be a set of guarded TGDs on R. We first give some preliminary definitions as follows. The chase graph for Σ and D is the directed graph consisting of chase(Σ, D) as the set of nodes and having an arc from a to b iff b is obtained from a and possibly other atoms by a one-step application of a TGD σ ∈ Σ. Here, we mark a as guard iff a is the guard of σ. The guarded chase forest for Σ and D is the restriction of the chase graph for Σ and D to all atoms marked as guards and their children. The subtree of an atom a in this forest, denoted subtree(a), is the restriction of the forest to all successors of a. The type of an atom a, denoted type(a), is the set of all atoms b in chase(Σ, D) that have only constants and nulls from a as arguments. Informally, the type of a is the set of all atoms that determine the subtree of a in the forest.

Example 3.2. Consider the TGDs σ 1 : r 1 (X, Y ), r 2 (Y ) → ∃Zr 1 (Z, X) and σ 2 : r 1 (X, Y ) → r 2 (X), applied on an instance D = {r 1 (a, b), r 2 (b)}. The first part of the (infinite) guarded chase forest for {σ 1 , σ 2 } and D is shown in Fig. 3, where every arc is labeled with the applied TGD.

r 1 (z 2 , z 1 ) . . . r 1 (z 1 , a) r 1 (a, b) σ 1 σ 1 σ 1 σ 2 σ 2 σ 2 r 2 (b) r 2 (a) r 2 (z 1 )r 2 (z 2 ) Fig. 1. Guarded chase forest in Example 3.2.

Given a finite set S ⊆ ∆ ∪ ∆ N , two sets of atoms A 1 and A 2 are S-isomorphic (or isomorphic if S = ∅) iff there exists a bijection β :

A 1 ∪ dom(A 1 ) → A 2 ∪ dom(A 2

) such that (i) β and β −1 are homomorphisms, and (ii)

β(c) = c = β −1 (c)

for all c ∈ S. Two atoms a 1 and a 2 are S-isomorphic (or isomorphic if S = ∅) iff {a 1 } and {a 2 } are S-isomorphic. The notion of S-isomorphism (or isomorphism if S = ∅) is naturally extended to more complex structures, such as pairs of two subtrees (V 1 , E 1 ) and (V 2 , E 2 ) of the guarded chase forest, and two pairs (b 1 , S 1 ) and (b 2 , S 2 ), where b 1 and b 2 are atoms, and S 1 and S 2 are sets of atoms. The following lemma shows that if two atoms have S-isomorphic types, then their subtrees are also S-isomorphic. Lemma 3.1. Let S be a set of constants and nulls, and a 1 and a 2 be atoms from chase(Σ, D) with S-isomorphic types. Then, the subtree of a 1 is S-isomorphic to the subtree of a 2 .

The next lemma provides an upper bound for the number of all non-T -isomorphic pairs consisting of an atom and a type. Using the above two lemmas, we are now ready to prove that the atoms in the type of an atom a in the guarded chase forest cannot be generated at a depth of the guarded chase forest that exceeds the depth of the atom a by a value that depends only on the TGDs. Here, the guarded depth of an atom a in the guarded chase forest for Σ and D, denoted depth(a), is the length of the path from D to a in the forest. Note that this is generally different from the derivation level.

Proof. Let k = (2w) w • 2 (2w) w•|R|

, where w is the maximal arity of a predicate in R. Suppose depth(b) > depth(a) + k for one atom b in the type of a. That is, the path P in the guarded chase forest leading to b has a length greater than k from the depth of a. Suppose first b contains no nulls. By Lemma 3.2, there are two isomorphic atoms h and h (in this order) on P with isomorphic types (see Fig. 3). By Lemma 3.1, the subtree of h is isomorphic to the subtree of h . But then b is also in the subtree of h, on a path Q that is at least one edge shorter than P , which contradicts the assumption that P is the path leading to b. Suppose next the set of nulls N in b is nonempty, and consider the common predecessor c of a and b of largest depth. By Lemma 3.2, there are two N -isomorphic atoms h and h (in this order) on P with N -isomorphic types (see Fig. 3). Since b is in the type of a, it cannot contain new nulls compared to a. Since c is the common predecessor of a and b of largest depth, b also cannot contain new nulls compared to c, and thus compared to h and h . So, b is in the types of both h and h . By Lemma 3.1, the subtree of h is N -isomorphic to the subtree of h . But then b is also in the subtree of h, on a path Q that is at least one edge shorter than P , which contradicts the assumption that P is the path leading to b. In summary, all atoms in the type of a can be obtained on paths of length at most k.

2 We next show that BCQs can be evaluated using only a finite, initial portion of the guarded chase forest, whose size is determined by the TGDs only. Here, the guarded chase of level up to k 0 for Σ and D, denoted g-chase k (Σ, D), is the set of all atoms in the forest of depth at most k. Lemma 3.4. Let Q be a BCQ over R. If there exists a homomorphism µ that maps Q into chase(Σ, D), then there exists a homomorphism λ that maps Q into g-chase k (Σ, D), where k depends only on Q and R. , and w is the maximal arity of a predicate in R. Suppose there exists a homomorphism that maps Q into chase(Σ, D). Let µ be a homomorphism of this kind such that depth(µ) = q∈Q depth(µ(q)) is minimal. We now show that µ(Q) is contained in g-chase k (Σ, D). Towards a contradiction, suppose the contrary. Consider the tree consisting of all atoms in µ(Q) and their ancestors in the guarded chase forest for Σ and D. As µ(Q) is not contained in g-chase k (Σ, D), this tree must contain a path P of length greater than δ of which all inner nodes (i.e., without start and end node) do not belong to µ(Q) and have no branches (i.e., have exactly one outgoing edge). Let a be the start node of P . By Lemma 3.2, there are two dom(a)-isomorphic atoms h and h on P with dom(a)-isomorphic types. By Lemma 3.1, subtree(h) is dom(a)-isomorphic to subtree(h ). Thus, we can remove h and the path to h , obtaining a path that is at least one edge shorter. Let ι be the homomorphism mapping subtree(h ) to subtree(h), and let µ = µ • ι. Then, µ is a homomorphism that maps Q into chase(Σ, D) such that depth(µ ) < depth(µ), which contradicts µ being a homomorphism of this kind such that depth(µ) is minimal. This shows that µ(Q) is contained in g-chase k (Σ, D). 2

The following definition captures a general property, where also the whole derivation of the query atoms are contained in the finite, initial portion of the guarded chase forest, whose size is determined by the TGDs only. Definition 3.1. We say that Σ has the bounded guard-depth property (BGDP) iff, for every database D for R and for every BCQ Q, whenever there exists a homomorphism µ that maps Q into chase(Σ, D), then there exists a homomorphism λ of this kind such that all ancestors of λ(Q) in the chase graph for Σ and D are contained in gchase γg (Σ, D), where γ g depends only on Q and R.

Linear Datalog ±

We now introduce linear Datalog ± as a variant of guarded Datalog ± , where we prove that query answering is even FO-rewritable (and thus in AC 0 ) in the data complexity. Nonetheless, linear Datalog ± is still expressive enough for representing ontologies [8] in many cases. A TGD is linear iff it contains only a singleton body atom. Notice that linear Datalog ± generalizes the well-known class of inclusion dependencies.

We first define the bounded derivation-depth property, which is strictly stronger than the bounded guard-depth property. Clearly, in the case of linear TGDs, for every a ∈ chase(Σ, D), the subtree of a is determined only by a, instead of type(a) (cf. Lemma 3.1). Therefore, for a single atom, its depth coincides with the number of applications of the TGD chase rule that are necessary to generate it. By this observation, as an immediate consequence of the fact that guarded TGDs enjoy the BGDP, we obtain that linear TGDs have the bounded derivation-depth property. The next result shows that queries relative to TGDs with the bounded derivation-depth property are FO-rewritable. Theorem 4.1. Let Σ be a set of TGDs over a relational schema R, D be a database for R, and Q be a BCQ over R. If Σ enjoys the BDDP, then Q is FO-rewritable.

As an immediate consequence of the fact that linear TGDs enjoy the BDDP and of Theorem 4.1, we have that BCQs are FO-rewritable in the linear case.

Corollary 4.1. Let R be a relational schema, Σ be a set of linear TGDs over R, D be a database for R, and Q be a BCQ over R. Then, Q is FO-rewritable.

Extensions

In this section, we extend Datalog ± with negative constraints and EGDs, which are both important when representing ontologies.

Negative Constraints. A negative constraint (or constraint) is a first-order formula of the form ∀XΦ(X) → ⊥, where Φ(X) is a (not necessarily guarded) conjunction of atoms. It is often also written as ∀XΦ (X) → ¬p(X), where Φ (X) is obtained from Φ(X) by removing the atom p(X). We usually omit the universal quantifiers.

Example 5.1. If the unary predicates c and c represent two classes, we may use the constraint c(X), c (X) → ⊥ to assert that the two classes have no common instances. Similarly, if additionally the binary predicate r represents a relationship, we may use c(X), r(X, Y ) → ⊥ to enforce that no member of the class c participates to r.

Query answering on a database D under TGDs Σ T and constraints Σ C can be done effortlessly by additionally checking that every constraint σ = Φ(X) → ⊥ ∈ Σ C is satisfied in D given Σ T , each of which can be done by checking that the BCQ Q σ = Φ(X) evaluates to false in D given Σ T . We write

D ∪ Σ T |= Σ C iff every σ ∈ Σ C is false in D given Σ T .

We thus obtain immediately the following result. Here,

a BCQ Q is true in D given Σ T and Σ C , denoted D ∪ Σ T ∪ Σ C |= Q, iff (i) D ∪ Σ T |= Q or (ii) D ∪ Σ T |= Σ C (as usual in DLs).

Theorem 5.1. Let R be a relational schema, Σ T and Σ C be sets of TGDs and constraints on R, respectively, D be a database for R, and Q be a BCQ on R. Then,

D ∪ Σ T ∪ Σ C |= Q iff (i) D ∪ Σ T |= Q or (ii) D ∪ Σ T |= Q σ for some σ ∈ Σ C .

The next theorem shows that constraints do not increase the data and combined complexity of answering BCQs in the guarded and linear case. Theorem 5.2. Let R be a relational schema, Σ T and Σ C be sets of TGDs and constraints on R, respectively, D be a database for R, and Q be a BCQ. Then, deciding D ∪ Σ T ∪ Σ C |= Q in the guarded (resp., linear) case has the same data and the same combined complexity as deciding D ∪ Σ T |= Q in the guarded (resp., linear) case.

EGDs and Non-Conflicting Keys. An equality-generating dependency (or EGD) σ is a first-order formula of the form ∀X Φ(X) → X i = X j , where Φ(X), called the body of σ, is a conjunction of atoms, and X i and X j are variables from X. We call X i = X j the head of σ. Such σ is satisfied in a database D for R iff, whenever there exists a homomorphism h such that h(Φ(X, Y)) ⊆ D, it holds that h(X i ) = h(X j ).

Example 5.2. The EGD r(X, Y ), r(X, Y ) → Y = Y expresses that the second argument of the binary predicate r functionally depends on the first argument of r.

The chase is naturally extended to databases under EGDs in addition to TGDs: The chase of a database D in the presence of two sets Σ T and Σ E of TGDs and EGDs, respectively, denoted chase(Σ T ∪ Σ E , D), is computed by iteratively applying (1) a single TGD once, according to the order specified above, and (2) the EGDs, as long as applicable (i.e., until a fixpoint is reached), where EGDs are applied as follows:

EGD CHASE RULE. Consider a database D for a relational schema R, and an EGD σ on R of the form Φ(X) → X i = X j . Such an EGD σ is applicable to D iff there exists a homomorphism η : Φ(X) → D such that η(X i ) and η(X j ) are different and not both constants. If η(X i ) and η(X j ) are different constants, then there is a hard violation of σ, and the chase fails. Otherwise, the result of the application of σ to D is the database h(D) obtained from D by replacing every occurrence of a non-constant element e ∈ {η(X i ), η(X j )} in D by the other element e (if e and e are both nulls, then e precedes e in the lexicographic order).

While adding negative constraints is computationally effortless, adding EGDs is more problematic. The interaction of TGDs and EGDs leads to undecidability of query answering even in simple cases, such that of functional and inclusion dependencies [14], or keys and inclusion dependencies (see, e.g., [10], where the proof of undecidability is done in the style of Vardi as in [18]). It can even be seen that a fixed set of EGDs and guarded TGDs can simulate a universal Turing machine, and thus query answering and even propositional ground atom inference is undecidable with such fixed sets of dependencies. For this reason, we consider a restricted class of EGDs, namely, nonconflicting key dependencies (or NC keys), which show a controlled interaction with TGDs (and negative constraints), such that they do not increase the complexity of answering BCQs. Nonetheless, this class is sufficient for ontology modeling.

We now first concentrate on the semantic notion of separability for EGDs, which formulates a controlled interaction between EGDs and TGDs (and negative constraints), such that the EGDs do not increase the complexity of answering BCQs. We then provide a sufficient syntactic condition for the separability of EGDs, where we transfer a result by [10] about non-key-conflicting inclusion dependencies to the more general setting of Datalog ± . In the context of description logics, general EGDs cannot be formulated, but only keys. Therefore, we mainly focus on keys here. Definition 5.1. Let R be a relational schema, and Σ T and Σ E be sets of TGDs and EGDs on R, respectively. Then, Σ E is separable from Σ T iff for every database D for R, the following conditions (i) and (ii) are both satisfied: (i) If there is a hard violation of an EGD in chase(Σ T ∪ Σ E , D), then there is also a hard violation of some EGD of Σ E , when this EGD is directly applied to D. (ii) If there is no chase failure, then for every BCQ

Q, chase(Σ T ∪ Σ E , D) |= Q iff chase(Σ T , D) |= Q.

The following result shows that adding separable EGDs to TGDs and constraints does not increase the data and combined complexity of answering BCQs in the guarded and linear case. It follows immediately from the fact that the separability implies that chase failure can be directly evaluated on D. For fixed (resp., variable) Σ E , this can be done by evaluating a first-order formula on D (resp., in polynomial time in the size of D and Σ E ), which clearly does not increase the data (resp., combined) complexity of answering BCQs in the three cases.

Theorem 5.3. Let R be a relational schema, Σ T and Σ C be sets of TGDs and constraints on R, respectively, and D be a database for R. Let Σ E be a set of EGDs that is separable from Σ T , and Q be a BCQ. Then, deciding D ∪ Σ T ∪ Σ C ∪ Σ E |= Q in the guarded (resp., linear) case has the same data complexity and also the same combined complexity as deciding D ∪ Σ T |= Q in the guarded (resp., linear) case.

We next provide a sufficient syntactic condition for the separability of EGDs. We focus on key dependencies (KDs, or simply keys): a key κ on a predicate r specifies a set K of key attribute positions of r; it is satisfied in a database D if no two atoms in D of the form r(t) have the same values in all positions in K. Clearly, KDs are special types of EGDs. The EGD chase rule in case of a KD applies to pairs of tuples that violate the KD. For example, a KD κ asserting that the key attribute of a ternary predicate r is the first one is applicable to the instance D = {r(a, b, z 3 ), r(a, z 2 , z 1 )} (where the z i 's are nulls), and its application yields the new instance {r(a, b, z 1 )}. The following definition generalizes the notion of "non-key-conflicting" dependency relative to a set of keys, introduced in [10], to the context of arbitrary TGDs. Definition 5.2. Let κ be a key, and σ be a TGD of the form Φ(X, Y) → ∃Z r(X, Z). Then, κ is non-conflicting (NC) with σ iff either (i) the key does not apply to the predicate r in the head of σ or (ii) the positions of κ in r are not a proper subset of the X-positions in r in the head of σ, and every existentially quantified variable in σ appears only once in the head of σ. We say κ is non-conflicting (NC) with a set of TGDs Σ T iff κ is NC with every σ ∈ Σ T . We say a set of keys Σ K is non-conflicting (NC) with Σ T iff every κ ∈ Σ K is NC with Σ T . Observe that all keys but κ 4 are NC with σ, since only K 4 ⊂ H. Roughly, every atom added in a chase by applying σ would have a fresh null in some position in K 1 , K 2 , and K 3 , thus never firing κ 1 , κ 2 , and κ 3 , respectively.

The following theorem shows that the NC property between keys and TGDs implies their separability. This generalizes a useful result of [10] on inclusion dependencies to the much larger class of all TGDs. The main idea behind the proof is roughly as follows. The NC condition between a key κ and a TGD σ assures that either (a) the application of σ in the chase generates an atom with a fresh null in a position of κ, and so the fact does not violate κ (see also Example 5.3), or (b) the X-positions in the predicate r in the head of σ coincide with the key positions of κ in r, and thus any newly generated atom must have fresh distinct nulls in all but the key position, and may eventually be eliminated without violation. It then follows that the full chase does not fail. Since the new nulls are all distinct, it also contains a homomorphic image of the TGD chase. Therefore, the full chase is in fact homomorphically equivalent to the TGD chase.

Theorem 5.4. Let R be a relational schema, Σ T and Σ K be sets of TGDs and keys, respectively, such that Σ K is NC with Σ T . Then, Σ K is separable from Σ T .