Jean-Franc ¸ois Baget

Marie-Laure Mugnier
email: mugnier@lirmm.fr

Sebastian Rudolph
email: sebastian.rudolph@kit.edu

Michaël Thomazo
email: thomazo@lirmm.fr

Complexity Boundaries for Generalized Guarded Existential Rules

In this report, we establish complexities of the conjunctive query entailment problem for classes of existential rules (also called Tuple-Generating Dependencies or Datalog+/-rules). Our contribution is twofold. First, we introduce the class of greedy bounded treewidth sets (gbts) of rules, which covers guarded rules, and their known generalizations, namely (weakly) frontierguarded rules. We provide a generic algorithm for query entailment with gbts, which is worst-case optimal for combined complexity with bounded predicate arity, as well as for data complexity. Secondly, we classify several gbts classes, whose complexity was unknown, namely frontier-one, frontierguarded and weakly frontier-guarded rules, with respect to combined complexity (with both unbounded and bounded predicate arity) and data complexity.

Introduction

First-order Horn rules (without function symbols except constants) have long been used in artificial intelligence, as well as in databases under name Datalog. We consider here an extension of these rules that allows to create existentially quantified variables (ability called value invention in databases [START_REF] Abiteboul | Foundations of Databases[END_REF]). More precisely, these extended rules are of the form Body → Head, where Body and Head are conjunctions of atoms, and variables occurring only in the Head are existentially quantified. E.g., ∀x(Human(x) → ∃y(HasParent(x, y) ∧ Human(x))). Such rules are known in databases as Tuple-Generating Dependencies (TGDs) [START_REF] Beeri | A proof procedure for data dependencies[END_REF] and have been extensively used, e.g. for data exchange [START_REF] Fagin | Data exchange: semantics and query answering[END_REF]. Recently, the corresponding logical fragment has gained new interest in the context of ontological knowledge representation. It has been introduced as the Datalog+/-framework in [CGK08, CGL09, CGL + 10], and independently, stemming from graph-based knowledge representation formalisms [START_REF] Chein | Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs[END_REF], as ∀∃-rules [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF][START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]. This rule-based framework is particularly well-suited to the topical ontological query answering problem, which consists of querying data while taking ontological knowledge into account. In particular, it generalizes the core of new description logics (DL) tailored for conjunctive query answering [CGL + 07, LTW09, BLMS08, CGL09, BLM10]1 . Moreover, in the case the DL-Lite family [CGL + 07], it has been shown that this covering by a Datalog+/-fragment is done without increasing complexity [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF].

The ability to generate existential variables, associated with arbitrarily complex conjunctions of atoms, makes entailment with these rules undecidable [START_REF] Beeri | The implication problem for data dependencies[END_REF][START_REF] Chandra | Embedded implicational dependencies and their inference problem[END_REF]. Since the birth of TGD, and recently within the Datalog+/-and ∀∃rule frameworks, various conditions of decidability have been exhibited. Three "abstract" classes have been introduced in [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF] to describe known decidable behaviours: an obvious condition of decidability is the finiteness of the forward chaining (known as the chase in the TGD framework [START_REF] Johnson | Testing containment of conjunctive queries under functional and inclusion dependencies[END_REF]); sets of rules ensuring this condition are called finite expansion sets (fes); a more general condition introduced in [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF] accepts infinite forward chaining provided that the facts generated have a bounded treewidth (when seen as graphs); such sets of rules are called bounded treewidth sets (bts); then decidability follows from the decidability of first-order logic (FOL) classes with the bounded treewidth model property [START_REF] Courcelle | The monadic second-order logic of graphs: I. recognizable sets of finite graphs[END_REF]. The third condition, giving rise to finite unification sets, relies on the finiteness of (a kind of) backward chaining mechanism. None of these three abstract classes is recognizable [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF].

In this paper, we focus on the bts paradigm and its main "concrete" classes. (Pure) Datalog rules (i.e. without existential variables) are fes (thus bts). Guarded rules [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF] are inspired by the guarded fragment of FOL. Their body has an atom (the guard) that contains all variables from the body. Guarded rules are bts (and not fes), they are generalized by weakly guarded rules (wg), in which the guarding condition is relaxed: only "affected" variables need to be guarded; intuitively, affected variables are variables that are possibly mapped, during the forward chaining process, to newly created variables [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF]. wg-rules include Datalog rules (in which there are no affected variables). Other decidable classes rely on the notion of the frontier of a rule (the set of variables shared between the body and the head of a rule). In a frontier-one rule (fr1), the frontier is restricted to a single variable [START_REF] Baget | Extending decidable cases for rules with existential variables[END_REF]. In a frontier-guarded rule (fg), an atom in the body guards the frontier [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]. Hence, fg-rules generalize both guarded rules and fr1-rules. When only affected variables from the frontier need to be guarded, we obtain the still decidable class of weakly frontier guarded rules (wfg), which generalizes both fg and wg classes [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]. Of all known recognizable bts classes, wfg is the class subsuming the most of the others. Example 1 (with the usual simplified syntax for rules) HasParent(x, y), HasParent(y, z) → isGdParent(z) is Datalog and fr1 but not guarded; WorksOn(x, z), WorksOn(y, z), StudentTandem(x, y) → Grade(x, t), Grade(y, t) is fg, but is neither fr1, nor guarded, nor Datalog.

Contrarily to fes and fus, the definition of bts does not provide a constructive entailment procedure. Some of its subclasses, namely guarded and wg, are provided with an algorithm and their complexity is known [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF]. However, this is not the case for the fr1, fg and wfg classes. The aim of this paper is to solve these algorithmic and complexity issues.

Our contribution is twofold. First, by imposing a restriction on the allowed derivation sequences, we define a subclass of bts, namely greedy bts (gbts), which has the nice property of covering the wfg class (thus all bts classes cited above). gbts are defined by a very simple condition: when such a set is processed in forward chaining, any application of a rule R from this set maps the whole frontier of R to terms belonging to the initial facts or to the atoms added by a single previous rule application. The fundamental property fulfilled by gbts is that to any derivation is naturally associated a bounded treewidth decomposition of the derived facts, which can be built in a greedy manner. We provide a generic algorithm for this class, which is worst-case optimal for data complexity, as well as for combined complexity in the case where predicate arity is bounded. Secondly, we classify the wfg, fg and fr1 classes with respect to both combined (with and without bound on the predicate arity) and data complexities. We also consider the case of rules with an acyclic (more precisely, hypergraph-acyclic) body and point that bodyacyclic fg-rules coincide with guarded rules from an expressivity and complexity perspective.

FIG. 1 shows the complexity lines for these classes of rules with three complexity measures, i.e., combined complexity without or with bound on the predicate arity, and data complexity. Notice that data complexity and bounded-arity combined complexity are not strictly layered. While fg-rules are much easier for data complexity (PTIME) than for bounded-arity combined complexity (2EXPTIME), wg-rules are in EXPTIME for both. Precise complexity results obtained are given in TAB. 1. New results are indicated by a star.

Preliminaries

As usual, an atom is of the form p(t 1 , . . . , t k ) where p is a predicate with arity k, and the t i are terms, i.e. variables or constants. A conjunct C[x] is a finite conjunction of atoms, where x is the set of variables occurring in C. A fact is the existential closure of a conjunct. A (boolean) conjunctive query (CQ) has the same form as a fact, thus we identify both notions. We also see conjuncts, facts and CQ as sets of atoms. Given an atom or a set of atoms A, we denote by vars(A) and terms(A) its set of variables and of terms, respectively. Given conjuncts F and Q, a homomorphism π from Q to F is a substitution of vars(Q) by terms of F such Definition 2 (Application of a Rule) A rule R is applicable to a fact F if there is a homomorphism π from body(R) to F ; the result of the application of R on F w.r.t. π is a fact α(F, R, π) = F ∪ π safe (head(R)) where π safe is a substitution of head(R), which replaces each x ∈ fr (R) with π(x), and other variables with fresh variables. As α only depends on π |fr (R) (the restriction of π to fr (R)), we also write α(F, R, π |fr (R) ).

2EXPTIME-c EXPTIME-c wfg 2EXPTIME-c 2EXPTIME-c EXPTIME-c fg 2EXPTIME-c 2EXPTIME-c PTIME-c fr1 2EXPTIME-c 2EXPTIME-c PTIME-c wg 2EXPTIME-c EXPTIME-c EXPTIME-c guarded 2EXPTIME-c EXPTIME-c PTIME-c ba-fg 2EXPTIME-c EXPTIME-c PTIME-c ba-fr1 EXPTIME-hard (1) EXPTIME-c PTIME-c (1) EXPTIME-c if no constants in rules
Definition 3 (Derivation) Let F be a fact, and R be a set of rules. An R-derivation of F is a finite sequence

(F 0 = F ), . . . , F k s.t. for all 0 ≤ i < k, there is R i ∈ R and a homomorphism π i from body(R i ) to F i s.t. F i+1 = α(F i , R i , π i ).
Theorem 1 (Forward Chaining) Let F and Q be two facts, and R be a set of rules. Then F, R |= Q iff there exists an R-derivation

(F 0 = F ), . . . , F k such that F k |= Q.
A knowledge base (KB) K = (F, R) is composed of a finite set of facts (seen as a single fact) F and a finite set of rules R. We denote by C the set of constants occurring in (F, R) and by P the set of predicates occurring in R. The (boolean) CQ entailment problem is the following: given a KB K = (F, R) and a (boolean) CQ Q, does F, R |= Q hold ?

We now specify some already introduced notions. A fact can naturally be seen as a hypergraph whose nodes are the terms in the fact and whose hyperedges encode atoms. The primal graph of this hypergraph has the same set of nodes and there is an edge between two nodes if they belong to the same hyperedge. The treewidth of a fact is defined as the treewidth2 of its associated primal graph. A set of rules R is called a bounded treewidth set (bts) if for any fact F there exists an integer b such that, for any fact F that can be R-derived from F , treewidth(F ) ≤ b. A rule R is guarded if there is an atom a ∈ body(R) (called a guard) with vars(body(R)) ⊆ vars(a). R is weakly guarded (wg) if there is a ∈ body(R) (called a weak guard) that contains all affected variables from body(R). The notion of affected variable is relative to the rule set: a variable is affected if it occurs only in affected predicate positions, which are positions that may contain a new variable generated by forward chaining (see [START_REF] Fagin | Data exchange: semantics and query answering[END_REF] for a precise definition). The important point is that a rule application necessarily maps non-affected variables to terms from the initial fact. R is frontierone

(fr1) if |fr (R)| = 1. R is frontier-guarded (fg) if there is a ∈ body(R)
with vars(fr (R)) ⊆ vars(a). R is weakly-frontier guarded (wfg) if there is a ∈ body(R) that contains all affected variables from fr (R).

Greedy Bounded-Treewidth Sets of Rules

In a greedy derivation, every rule application maps the frontier of the rule into terms added by a single previous rule application or occurring in the initial fact:

Definition 4 (Greedy Derivation) An R-derivation (F 0 = F ), . . . , F k is said to be greedy if, for all i with 0 ≤ i < k, there is j < i such that π i (fr(R i )) ⊆ vars(A j ) ∪ vars(F 0 ) ∪ C, where A j = π safe j (head(R j )). Example 2. Let R = {R 0 , R 1 } where: R 0 = r 1 (x, y) → r 2 (y, z) and R 1 = r 1 (x, y), r 2 (x, z), r 2 (y, t) → r 2 (z, t). Let F 0 = {r 1 (a, b) ∧ r 1 (b, c)} and S = F 0 , . . . , F 3 with: F 1 = α(F 0 , R 0 , {(y, b)}), A 0 = {r 2 (b, x 1 )}, F 2 = α(F 1 , R 0 , {(y, c)}), A 1 = {r 2 (c, x 2 )}, F 3 = α(F 2 , R 1 , π 2 ), with π 2 = {(z, x 1 ), (t, x 2 )};
there is no A j s.t. {π 2 (z), π 2 (t)} ⊆ terms(A j ), thus S is not greedy.

To any greedy derivation S of F can be assigned a unique derivation tree DT(S) built iteratively as follows: the root is a node x 0 with terms(x 0 ) = vars(F )∪ C and atoms(x 0 ) = atoms(F ), and ∀0 ≤ i < k, we add a node x i+1 with terms(x i+1 ) = vars(A i+1 ) ∪ vars(F ) ∪ C and atoms(x i+1 ) = atoms(A i+1 ). Since S is greedy, there is at least a j such that π i (fr(R i )) ⊆ terms(x j ). We add an edge between x i+1 and x j , j being the smallest integer such that x j has this property. The nodes of DT(S) are also called "bags".

Property 2 Let S = F 0 . . . , F k be a greedy derivation. Then DT(S) is a tree decomposition of F k of width bounded by |vars(F )|+|C|+max(|vars(head(R))| R∈R ).

Definition 5 (greedy bounded-treewidth set of rules (gbts)) R is said to be a greedy bounded-treewidth set (gbts) if (for any fact F ) any R-derivation (of F ) is greedy.

The class gbts is a strict subclass of bts (e.g. in Example 2: R is fes but not gbts). It is nevertheless an expressive subclass of bts since it contains wfg: Property 3 wfg-rules are gbts.

Proof: Let R (from a wfg rule set R) with weak frontier guard g. Assume R is applied by π and let π(g) = a. Either a ∈ F or a ∈ A i for some i. Thus R is gbts.

The following example shows that gbts strictly contains wfg: R = r 1 (x, y), r 2 (y, z) → r(x, x ), r(y, y ), r(z, z ), r 1 (x , y ), r 2 (y , z ); {R} is gbts, but not wfg (nor fes).

An Algorithm for gbts

The intuition underlying the decidability of gbts is that rule applications create a bounded number of "relevant patterns". When we have created all possible patterns, "large-enough" to map Q, we can halt the derivation process. In [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF], a specific notion of type is used for that purpose. However, to take non-guarded rules into account, we need to generalize it. We thus define the ultimate applicability of a rule, and the related notion of oracle. Sets of oracles generalize types. To simplify the presentation, we translate Q into a rule R Q = Q → match where match is a fresh nullary predicate (note that fr (R Q ) is empty). The question is now whether

R ∪ {R Q } |= match.
Definition 6 (Ultimate applicability, oracle) Let F be a fact, R be a set of gbts rules, and S = F 0 (= F ), . . . , F i+1 be an R-derivation of F (with F j+1 = F j ∪ A j , ∀0 ≤ j ≤ i), and let x j be the bag of DT (S) associated with A j . We say that R ∈ R is ultimately applicable to x j if there is an R-derivation F 0 (= F ), . . . , F j , . . . , F i+1 , . . . , F l with a homomorphism π from body(R) to F l and π(fr(R)) ⊆ terms(x j ) = vars(A j )∪vars(F )∪C. We say that π |fr (R) is an oracle for the ultimate applicability of R on x j . An ultimate R-derivation is a sequence F 0 , . . . , F k where ∀0 ≤ i < k, there is R ∈ R and an oracle π |fr (R) for the ultimate applicability of R on some x j with j < i such that

F i+1 = α(F i , R, π |fr (R) ).
Any derivation is an ultimate derivation and an ultimate derivation F 0 , F 1 , . . . , F k can always be extended to a derivation F 0 , F 1 0 , . . . ,

F i 1 0 , F 1 , . . . , F k-1 , F 1 k-1 , . . . , F i k k-1 , F k , where F i contains F i .
We now define an equivalence relation ∼ Q on the bags of a derivation tree with the following informal meaning: x i ∼ Q x j means that a rule body can be ultimately mapped on x i iff if can be mapped similarly on x j .

Definition 7 (∼ Q ) Let T be a derivation tree, x and y two bags of T . x ∼ Q y iff there is a bijective substitution ψ of terms(x) by terms(y) s.t. ∀R ∈ R, π is an oracle for R on x iff ψ • π is an oracle for R on y.

Algorithm 1 behaves as a classical breadth-first forward chaining (also called "chase" in databases) with two main differences. First, instead of looking for homomorphisms to check the applicability of rules, it uses oracles for ultimate applicability, thus building an ultimate derivation tree. Secondly, ∼ Q allows to prune the ultimate derivation tree. 3Theorem 4 ∼ Q Ultimate Saturation is sound and complete for CQ entailment with R gbts.

Proof: Should we not take into account the ∼ Q equivalence relation, soundness and completeness of the algorithm would immediately follow from the correspondence between rule application and ultimate rule application. However, ∼ Q is used to cut whole subtrees of the derivation tree. To prove that this partial exploration does not prevent completeness, we have to prove the following property: "if x ∼ Q y and x parent of x , then there is a child y of y such that x ∼ Q y ". Thus exploring only one subtree of two ∼ Q equivalent bags will be sufficient to preserve the completeness of the algorithm.

We first build y = copy [x←y] (x ) the bag obtained from y "as x is obtained from x". The bag x was obtained by ultimately applying some rule R according to some oracle π, that mapped fr(R) to terms from atoms(x). Thus, since x ∼ Q y, there exists an oracle ψ•π that maps fr(R) to terms from atoms(y). The bag y thus corresponds to that ultimate rule application, and its atoms are built accordingly (precisely, atoms(y ) = (ψ • π) saf e (head(R))).

Algorithm 1: ∼ Q Ultimate Saturation Data: Two facts F , Q, gbts rule set R Result: YES if F, R |= Q, NO otherwise. R ← R ∪ {R Q }; T ← newTree(x 0 ) ; //
It remains now to prove that x ∼ Q y i.e., to prove the following property P : "there exists a bijection ψ from terms(x ) to terms(y ) such that π is an oracle for R in x iff ψ • π is an oracle for R in y ". The bijective substitution ψ is built as follows: for any term t of x that is already in x, ψ (t) = ψ(t). Otherwise, we define ψ (t) = t where t and t have been safely rewritten from the same term in head(R).

We first point out that it is immediate to see that x = copy [y←x] (y ) ∼ Q x . Indeed, x and x are two bags created by the same ultimate rule application, the second one creating only redundancy. They have thus equivalent oracles (i.e., their sets of oracles are equals up to the natural bijection from terms(x ) to terms(x )). Should we be able to prove the first direction of property P , the second would then immediately follow: if π is an oracle on y , then (first direction of property P ), there is an oracle π on x that is equivalent to an oracle π on x .

It remains only to check that if π is an oracle for some R on x , then ψ • π is also an oracle on y . In order to do that, we generalize the notion of copy: instead of copying the child of a bag x under a ∼ Q equivalent node y, we copy a whole subtree of x under y. The definition of the copy of a subtree immediately follows from the copy of a unique bag, by means of a trivial recursion.

Then we point out that if π is an oracle for R on x , then there is a subtree rooted in x such that body(R) can be mapped (using a homomorphism π that extends π) to the fact associated with a minimal derivation generating that subtree. Let us consider a minimal such subtree. Finally, we show that body(R) can also be mapped to the fact associated with the copy of that subtree under the equivalent node y, and that ψ • π is an oracle of R in y . The proof is made by induction on the depth of that subtree.

Let us know study the complexity of Algorithm 1. If we denote by T max the maximum number of non-equivalent nodes that can be generated, the asymptotic complexity of Algorithm 1 is

T max × |R| × [(cost of a call to oracles (R, x)) + |oracles(R, x)| × (cost of checking the existence of a ∼ Q equivalent node)]. Property 5 Let R be gbts, Q a query, F a fact. Let q = max i (|terms(body(R i ))|), b = |terms(F )| + max i (|terms(head(R i ))|) + |C|
and w the maximum predicate arity. Let S be an ultimate derivation of F , x a bag of DT(S). The cost of a call to

oracles(R, x) is in the order of poly(b b , 2 b q+1 2 |P|.q w+1
).

Proof:

See Section 4.1. Checking y ∼ Q z has a cost O(b b × (|R| × q b ) 2
) and T max is upper-bounded by 2 |R|×b q , hence the following theorem (with hardness results stemming from wfg subclass):

Theorem 6 CQ entailment is in 3EXPTIME for combined complexity, 2EXPTIMEcomplete when the arity of the predicates is bounded and EXPTIME-complete for data complexity.

Computing the set of oracles of a bag

In this section, we show how to compute the set of oracles associated with a bag of DT (S), where S is an ultimate derivation, and evaluate the cost of this computation.

Notations: Given a derivation (or ultimate derivation) S of F , we note S(F ) the last fact of S. By an extension S of S = (F 0 , . . . , F k ), we mean a derivation with prefix S, i.e., S = (F 0 , . . . , F k , . . . , F ). The extension of S = (F 0 , . . . , F k ) with (R, π| f r(R) ), where R is a rule and

π| f r(R) maps f r(R) to F k is S = (F 0 , . . . , F k , α(F k , R, π| f r(R) )).
In the following, F denotes the initial fact and R is a gbts set of rules.

Alternative derivation tree, alternative (ultimate) patterns and oracles

We define an alternative derivation tree in order to ensure that patterns (which are defined below) are in finite number. Instead of encoding

A i = π saf e i (head(R i )) in a bag x i+1 , we encode head(R i ) in x i+1 , i.e., terms(x i+1 ) = terms(head(R i )) ∪ vars(F ) ∪ C. Then, to keep track of π| f r(R i )
, we label the edge between x i+1 and its parent. For convenience, we also define a mapping Ψ x i+1 , which assigns to each term in terms(x i+1 ) its corresponding term in F i+1 .

Definition 8 (Alternative derivation tree) Let S = (F 0 , . . . , F k ) be an R-derivation of F . We build the alternative derivation tree of S (notation ADT (S)) in the following way. The root of the tree is a node x 0 such that terms(x 0 ) = vars(F )∪C. We define Ψ x 0 as the identity on terms(x 0 ). For all i ∈ {0, . . . , k -1}, we add a node x i+1 such that terms(x i+1 ) = terms(head(R i )) ∪ vars(F ) ∪ C. Since S is greedy, there is at least one node x j such that Ψ x j (terms(x j )) contains π i (fr(R i )). There is even a smallest j such that x j has that property. We add an edge between x i+1 and x j , which is labeled by a substitution j i+1 of fr(R i )∪vars(F )∪C by terms(x j ) such that, for all x ∈ f r(R i ), Ψ x j • j i+1 (x) = π i (x) and j i+1 is the identity on the other terms. Finally, we define

Ψ x i+1 : terms(x i+1 ) → terms(F i+1 ), with Ψ x i+1 (t) = Ψ x j (j i+1 (t)) if t ∈ domain(j i+1
) and the safe substitution operated to add A i to F i otherwise.

The alternative pattern of a bag describes the different ways facts with at most n terms can be mapped using some terms of the bag.

Definition 9 (Alternative pattern of a bag) Let S = (F = F 0 , . . . , F k ) be an Rderivation of F . Let B be a bag of ADT(S). The alternative4 n-pattern of B in S is the set of all pairs (G j , π j ) such that:

• G j is a conjunction with at most n terms;

• π j is a substitution of some terms from G j by terms from B such that Ψ B •π j is extendable to a homomorphism from G j to F k .

We are moreover interested in what happens later on in the forward chaining process, and that is why we define ultimate patterns.

Definition 10 (Alternative ultimate pattern of a bag) Let S = (F = F 0 , . . . , F k ) be an R-derivation of F . Let B be a bag of ADT(S). The alternative ultimate npattern of B in S in the union of all the alternative n-patterns of B in S , for all extensions S of S.

From now, we consider that n = max i (|body(R i )|) (i.e., n = q in Property 5). If we are able to compute ultimate patterns, we can compute the set of oracles for a given bag:

Property 7 (Correspondence between oracles and alternative patterns) Let S be an R-derivation of F . Let B a bag in DT (S), and B the corresponding bag in ADT (S). Given R ∈ R, π : fr(R) → terms(B) is an oracle for the ultimate applicability of R on B iff there exists π : fr(R) → terms(B ) such that (body(R), π ) belongs to the alternative ultimate pattern of B and π = Ψ B • π .

Proof: Direct consequences from definitions.

In the following, we omit the qualifier "alternative" for patterns since all patterns considered are alternative patterns. We keep the distinction between a derivation tree and an alternative derivation tree.

Computation of (alternative) ultimate patterns

First, we show how to compute the ultimate pattern of the root of the alternative derivation tree. Then, we show that the ultimate pattern of any bag can be computed in polynomial time (with respect to the number of patterns and the number of junctions, defined hereafter) as long as the ultimate pattern of its parent is known. In both computations, we rely on a translation of our problem into a rewriting system on terms, which are trees (those terms have thus nothing to do with terms in Q or in the KB). Those trees represent derivation trees: nodes are intuitively the same thing as bags. They are labeled by patterns. Edges are labeled by "junctions" which are equal to the j mappings in an ADT, i.e., represent how terms are shared between the bags which are abstracted into nodes. The rules of the original problem are translated into creation rules, and we add update rules in order to maintain the property that the label of a node is the pattern of the corresponding bag in the derivation tree.

This translation being done, determining the ultimate pattern of a bag with pattern p boils down to the following question: starting from a tree t consisting of a single node labeled by p, what is the maximal label (given a natural order on patterns, i.e., inclusion) that can label the root of a term rewritten from t? Put this way, it does not seem easier to determine the ultimate pattern of a bag. To overcome this difficulty, we close our set of rewriting rules in such a way that if p can evolve into p after an arbitrary number of rule applications with the initial set of rules, then there is a rule p → p in the closed set. Then, the problem of determining the ultimate pattern of a bag of pattern p is reduced to the problem of searching the maximal p such that there exists a rule p → p in the closed set of rules.

Definition 11 ((J, P )-rewriting system) A (J, P )-rewriting system (or, when not ambiguous, a rewriting system) is a set of rules of the following forms:

• p i → j(p i , p j ) • p i → p i • j(p i , p j ) → j(p i , p j ) • j(p i , p j ) → j(p i , p j )
with p i , p j , p i , p j ∈ P and j ∈ J. Rules of the first kind are called creation rules. The other rules are update rules.

A creation rule creates a new node labeled by p j , and linked by an edge labeled j to an existing node labeled by p i . The other rules update the label of an existing node.

We now define a rewriting system that meets our needs. Let us first notice that in the alternative derivation tree, all terms are included in B = vars(F ) ∪ C ∪ ∪ i (vars(head(R i ))). Thus, we can define every pattern as a set of pairs (G, π), with π being a substitution of a subset of terms(G) by terms(B). We denote by P the set of all such pairs. We also define the notion of junction:

Definition 12 (Junction) A junction j is a mapping from a subset of B containing vars(F ) ∪ C to B such that j(c) = c if c ∈ vars(F ) ∪ C.
Rewriting systems act upon terms, whose definition is below.

Definition 13 (Term) A term is a tree whose nodes are labeled by a pattern and edges by junctions.

We aim at defining a rewriting system that builds the tree of patterns of an alternative derivation tree. Intuitively, this tree of patterns is a term having the same structure as the ADT, with its nodes being labeled by the pattern of the corresponding bag and its edges by the label of the corresponding edge.

Definition 14 (Tree of patterns of an alternative derivation tree) Let S be a derivation of F , and ADT(S) be its alternative derivation tree. The tree of patterns of ADT(S) is a term t built recursively as follows:

• if S is the trivial derivation (restricted to F ), then t is a node, labeled by p F , the pattern (in S) of the bag containing terms(F ) ∪ C (i.e., the set of pairs (G, σ) with G being a conjunction over at most n terms and σ being a homomorphism from G to F ). This node is said to be associated with the unique bag of ADT (S).

• if S is a derivation with m rule applications, let t be the tree of patterns associated with the m-1 first rule applications. Let v be the node associated with the bag B to which we add a child B : we add a child v to v and associate v with B . We label each node of t by the pattern in S of the bag associated with this node, and we label the edge between v and v by j, where j is the label of the edge between B and B in ADT(S).

Let us first have a look at the result in the alternative derivation tree of the application of (R, π) to S(F ). B being the closest bag to the root containing π(f r(R)), we add a child B to B. What is the pattern of B ? We split the answer to this question into two parts.

First part. We can first give a lower bound on the pattern of B : it contains at least all pairs (G, σ) where σ is a substitution of some terms from G by terms from B such that Ψ B • σ can be extended to a homomorphism from G to the atoms that were added at the last step.

Second part. However, there are possibly homomorphisms that use also atoms and/or terms that were already in S(F ). Moreover, the last rule application may have allowed new homomorphisms in other bags. We thus have to update patterns, by using information of the following kind: if B is a child of B and the pattern of B (resp. B ) contains (G, σ) (resp. (G , σ )), then B contains (G , σ ), whose construction depends on how terms are shared by B and B ; similarly, information can be propagated from B to B .

Rules for the first part. Each bag should have a corresponding node in the mimicking term. We first define the "minimum" pattern of the newly created bag.

Definition 15 (n-pattern associated with a (C, π)) Let C be a conjunction. Let π be a substitution of terms from C by terms from C. The n-pattern associated with (C, π) is the set of pairs (G, σ) with G being a conjunction over at most n terms and σ being a homomorphism from G to π(C).

Using this definition, we propose a set of rules allowing to mimic the creation of new bags.

Definition 16 (Creation rules associated with (R, π)) Let p be a pattern and R ∈ R. For every π : fr(R) → B such that (body(R), π) ∈ p , we define a creation rule: p → j(p, p head(R),π ), where p head(R),π is the pattern associated with (head(R), π ), where π is such that π (x) = π (y) if and only if π(x) = π(y), and j is a mapping with domain fr(R) ∪ vars(F ) ∪ C, equal to π on fr(R) and to the identity otherwise.

Rules for the second part. However, we are not only interested in the minimal pattern of the generated bag, but in having the exact pattern for every bag in the derivation. Thus, we add now update rules, which will ensure that a node in the term is labeled by the pattern of the corresponding bag in the derivation tree.

We first define a union operation on conjunctions.

Definition 17 (G(G 1 , G 2 , π 1 , π 2 , j))
Let G 1 and G 2 be two conjunctions of atoms, B 1 and B 2 two bags, π 1 a substitution of some terms from G 1 by terms of B 1 , π 2 a substitution of some terms from G 2 by terms of B 2 , and j a substitution of some terms from B 2 by terms of B 1 . We assume w.l.o.g. that terms in G 1 and G 2 are disjoint. We define G(G 1 , G 2 , π 1 , π 2 , j) as the conjunct obtained from the atoms in G 1 and G 2 by merging terms having the same image by π 1 or by j • π 2 .

Notation. Let T be a set of terms, π 1 be a mapping from B 1 to T , and π 2 be a mapping from B 2 to T . If for every

x ∈ B 1 ∩ B 2 , π 1 (x) = π 2 (x), we define π 1 ∪ π 2 (x) from B 1 ∪ B 2 to T such that π 1 ∪ π 2 (x) = π 1 (x) if x ∈ B 1 , and π 1 ∪ π 2 (x) = π 2 (x) otherwise.
Definition 18 (Upward / Downward update rule) To every triple (p 1 , j, p 2 ) ∈ P × J × P , we assign an upward update rule:

j(p 1 , p 2 ) → j(p 1 , p 2 )
where p 1 is built in the following way:

• p 1 ⊆ p 1
• for all (G 1 , π 1 ) ∈ p 1 , (G 2 , π 2 ) ∈ p 2 , we add every (G , π ), where G is a conjunction over at most n terms such that there exists ϕ homomorphism from G to G(G 1 , G 2 , π 1 , π 2 , j), and π is a restriction of (π 1 ∪ (j • π 2 )) • ϕ having a range included in range(π 1 ) ∪ range(j).

We also assign to (p 1 , j, p 2 ) a downward update rule:

j(p 1 , p 2 ) → j(p 1 , p 2 )
where p 2 is defined in a similar way: p 2 ⊆ p 2 and, for all (G 1 , π 1 ) ∈ p 1 , (G 2 , π 2 ) ∈ p 2 , we add every (G , π ), where G is a conjunction over at most n terms such that there exists ϕ homomorphism from G to G(G 1 , G 2 , π 1 , π 2 , j), and π is a restriction of (π 1 ∪ π 2 ) • ϕ with j • π 1 = π 1 and range(π ) ⊆ range(π 1 ) ∪ range(π 2 ).

In the following, we show that R-derivations of a fact F are "equivalent" to some rewritings (canonical rewritings, defined hereafter) of p F .

Property 8 Let S be a derivation of F , and R ∈ R. Let B be a bag of ADT (S), and v B the corresponding node in the tree of patterns t of ADT (S). R is applicable by some π : body(R) → S(F ) with range(π |f r ) ⊆ Ψ B (terms(B)) iff there exists π such that

Ψ B • π = π |fr(R) and (body(R), π |f r(R) ) ∈ pattern(B) = label(v B ).
Moreover, t , obtained from t by applying the creation rule associated with (R, π) as high as possible in t, has the same structure as the tree of patterns of ADT (S ), where S is the extension of S with (R, π).

Proof: By definition of a pattern, (body(R), π |f r(R) ) belongs to the pattern of B iff Ψ B • π can be extended to a homomorphism from body(R) to F . From the definition of a tree of patterns, label(v B ) = pattern(B). Since in the derivation tree, the new bag is added as a child as close to the root as possible and t has the same structure as ADT (S), we conclude that t has the same structure as ADT (S ).

In the following, t built as in the previous property is called the primitive tree of patterns of ADT (S ).

We now show that, after a rule application leading to add a new bag B as the child of a bag B in the alternative derivation tree, we can compute the pattern of B by updating the tree of patterns: after having applied the creation rule to create the node assigned to B and compute its "primitive pattern", it is sufficient to apply a downward update rule (from the node assigned to B to the node assigned to B ).

Property 9 Let S be a derivation of F and S be the extension of S with (R, π). Let t be the tree of patterns of ADT (S) and t be the primitive tree of patterns of ADT (S ). Let B be the bag created by (R, π) and B its parent in ADT (S ), let v and v be the nodes respectively assigned to B and B in t , and let j be the label of the edge between v and v . Let p and p be the respective labels of v and v in t . The label of v in the tree of patterns of ADT (S ), i.e., the pattern of B in S , is p obtained by applying the downward update rule j(p, p ) → j(p, p ). ⇐ Conversely, let (G, ψ) be in p . The first possible case is that (G, ψ) belongs to p , and thus it belongs to the pattern of B . Otherwise, there exists (G 1 , G 2 , ψ 1 , ψ 2 ) such that G is a conjunction over at most n terms that maps by some ϕ to G(G 1 , G 2 , ψ 1 , ψ 2 , j), with (G 1 , ψ 1 ) ∈ p, (G 2 , ψ 2 ) ∈ p , and ψ being a restriction of (ψ 1 ∪ ψ 2 ) • ϕ s.t. ψ 1 = j • ψ 1 , and having range included in the terms of B . It remains to note that there is a homomorphism from

G(G 1 , G 2 , ψ 1 , ψ 2 , j) to S (F ) that extends Ψ B • (ψ 1 ∪ ψ 2 ), thus Ψ B • ψ is extendable to a homomor- phism from G to S (F ).
We conclude that (G, ψ) belongs to the pattern of B .

Definition 19 Let S be a derivation of F and S be the extension of S with (R, π). Let t be the tree of patterns of ADT (S), and t be the primitive tree of patterns of ADT (S ). The update of t is done in the following way:

• apply the downward update rule applicable to the bag newly created,

• traverse the tree t starting from this node and applying all possible update rules for each node.

Property 10 Let S be a derivation of F and S be the extension of S with (R, π).

Let t be the tree of patterns of ADT (S), and t be the primitive tree of patterns of ADT (S ). The update of t is the tree of patterns of ADT (S ).

Proof: By induction. The base case is Property 9. The recursive step is done similarly to the proof of Property 9.

Let us point out that we build the tree of patterns of an alternative derivation tree by using a canonical rewriting sequence, as defined below.

Definition 20 (Canonical rewriting sequence) A rewriting sequence is said to be canonical if for all creation rule r associated with (R, π) and applied to a term t:

• either r is applied to the root of t,

• or, let v 1 be the node to which r is applied, v 2 be its parent and let j be the label of the edge between v 1 and v 2 . r should fulfill that range(π) ⊆ domain(j).

Moreover, between two applications of creation rules, update rules are applied until no further modification is possible.

It is easy to associate with such a rewriting sequence leading to a term t a derivation whose t is the tree of patterns:

Property 11 With any canonical rewriting sequence r of p F (the pattern associated with F ), we can associate a derivation S of F such that the term obtained from p F by applying r is the tree of patterns of ADT(S).

Proof: Built recursively on the length of the rewriting sequence (to each creation rule corresponds a rule application).

We order patterns by inclusion.

Definition 21 Let p be a pattern and t p be the term restricted to a node labeled by p. There exists p * c such that p * c is the biggest pattern that can be at the root of a term rewritten from t p with a canonical rewriting sequence. We call this pattern the canonical limit of p.

Proof: Arguments: finite number of patterns + monotonicity of rewriting rules + confluence.

From Property 10 and Property 11, we obtain the following property:

Property 12 Let F be a fact. The ultimate pattern of F is the canonical limit of p F .

Proof: Comes directly from the equivalence between derivation sequence and rewriting sequence shown in previous properties.

Then, if we denote by l the cost of computing the canonical limit of a pattern, the cost of the computation of the ultimate pattern of the root of ADT (S) is O(l).

Assuming that we know the ultimate pattern of a bag, we can compute the ultimate pattern of its child in a similar fashion:

Property 13 Let S be a derivation of F . Let B 1 be a bag and B 2 be a child of B 1 , created by a rule application (R, π). If p 1 is the ultimate pattern of B 1 , then one can compute the ultimate pattern of B 2 in the following way: start from p 2 , where p 2 is the pattern associated with (head(R), π ), such that π (x) = π (y) iff π(x) = π(y); apply downward update rules on p 1 , getting p 2 , then compute the canonical limit of p 2 . This limit is the ultimate pattern of B 2 . Proof: Since p 1 is the ultimate pattern of B 1 , it is useless to update it. The rest of the proof is the same as for Property 12.

We have seen that we can compute the ultimate pattern of any bag if we are able to compute the canonical limit of any pattern in the rewriting system associated with our set of rules. We focus then on this question in the following. First, we relax the condition on the rewriting sequence, showing that the canonical limit is equal to the limit of a pattern.

Definition 22 Let p be a pattern. There exists p * such that p * is the biggest pattern that can be the root of a term rewritten from p. We call this pattern the limit of p. Property 14 Let p ∈ P . The canonical limit of p is equal to the limit of p.

Proof: We canonize every rewriting sequence, by induction on the length of the rewriting. First, we associate with the term restricted to the node labeled by p (on which we apply non-canonized rules) another term restricted to a single node labeled by p. Each time we apply a rule in the non-canonized sequence, we apply it to the "correct" node, which is an ancestor of the associated node in the canonized term. We ensure that the label of the associated term is bigger than the label of the initial term.

• For the empty rewriting sequence, that is trivial; • Let us assume that we have built a canonical rewriting sequence with the desired property. The interesting case is when we apply a creation rule. Let us assume that we apply it on v in the initial term. Let v be the node associated with v. There are two possibilities: the range of π is not included in the domain of the junction of v with its parent, we can freely add the new node below v . Otherwise, we consider its first ancestor fulfilling this condition, and add the new node below it. We show then as in properties 9 and 10 that the conditions on patterns is still fulfilled.

The only step left it to compute the limit of a pattern. Given a rewriting system S, we define the closure of S, by adding rules which allow to simulate a succession of rules in a single step. Closure operations are presented below:

• add p i → p i for any p i

• if p i → p j ∈ S and p j → p k ∈ S, then p i → p k ∈ S • if p i → ϕ(p i , p j ) ∈ S and p j → p k ∈ S, then p i → ϕ(p i , p k ) ∈ S
• if p i → ϕ(p i , p j ) ∈ S and p j → p j ∈ S and ϕ(p i , p j ) → ϕ(p i , p j ) ∈ S then

p i → p i ∈ S
The closure of a rewriting system is the set of rules obtained by applying closure operations until a fixpoint is reached. It is well defined, since there is a finite number of rules. Moreover, we can compute it in polynomial time in P and J. The key property is the following:

Property 15 Let S be a rewriting system. Let p be a pattern, and t p be the term restricted to a root labeled by p. There exists a term t derived from t p with rules from S whose root is labeled by p if and only if p → p is in the closure of S.

Proof: ⇒ We prove by induction on k that for any S, if t can we derived with rules from S into a term with root labeled by p in k steps, then p → p belongs to the k-closure of S. ⇐ We prove by induction on k that for any S, if a rule is added at the k th step of closure, the same local effect can be achieved in at most 3 k operations with the initial rule set.

Property 16

The closure of a rewriting system can be computed in polynomial time in the number of patterns and junctions.

Proof: The cost comes from the computation of the closure. There is a number of rules which is polynomial in |P |, |J|. At each step of closure, at least one rule is added, then at most a polynomial number of closure steps are performed. Each step has a polynomial cost in the number of rules, thus the closure can be computed in polynomial time in |P |, |J|.

Corollary 17

The limit of a pattern can be computed in polynomial time in the number of patterns and junctions.

Proof of property 5:

We can check that the cardinality of J is at most b b and the cardinality of P is at most 2 b q+1 2 |P|.q w+1

. Then, from the previous property, the limit of a pattern, and thus the ultimate pattern of a bag, can be computed in time poly(b b , 2 b q+1 2 |P|.q w+1 ). By Property 7, the set of oracles for a bag is thus computed with the same complexity.

Weakly Frontier-Guarded Rules

First, the EXPTIME-complete data complexity of wfg-rules directly follows from EXPTIME membership of gbts (SECT. 4) and EXPTIME-hardness of wg-rules [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF].

We now prove that w(f)g-rules can be polynomially translated into (f)g-rules. In particular, this allows us to exploit the 2EXPTIME membership result established in the next section for fg-rules. W.l.o.g. we assume here that the initial fact F does not contain any variable. Then, a homomorphism from a rule body to a derived fact necessarily maps non-affected variables to constants in C. Thus, by replacing non-affected variables in rules with all possible constants, we obtain an equivalent set of rules (Section 5.1). However, this partial grounding produces a worst-case exponential blow-up in the number of non-affected variables per rule. We thus provide a way to simulate partial groundings with only polynomial blowup (Section 5.2). Note however that this second translation does not preserve the predicate arity.

Translation by Partial Grounding

Given a rule R in a set of rules R, let nav(R) denote the set of variables that are not affected in R. Let ground(R) denote the set containing all rules obtained by uniformly substituting the non-affected variables of R by constants, i.e., ground(R) = {σ(R) | σ : nav(R) → C}. Moreover let ground(R) = R∈R ground(R). Let s = max R∈R |nav(R)| the maximal number of nonaffected variables per rule.

Lemma 1 Let R be a set of rules, F a fact and Q a query. Then we have that

F, R |= Q if and only if F, ground(R) |= Q. Proof: For any R ∈ R and R i ∈ ground(R), let h R i : body(R) → body(R i )
denote the homomorphism naturally associated with the grounding. Given R ∈ R, let us consider a homomorphism h : body(R) → F . Then, there is

R i ∈ ground(R) and h : body(R i ) → F , such that h = h • h R i . Conversely, for any R i ∈ ground(R) and any h : body(R i ) → F , we have a homomorphism h = h • h R i : body(R) → F . Note that h(head(R)) = h (head(R i )).
It follows that any derivation sequence with R can be expressed as a derivation sequence with ground(R), and reciprocally.

The following properties are immediate. Note that for a rule R, the number of rules in ground(R) is equal to |C| |nav(R)| .

Property 18 (Properties of ground)

• If R is weakly (frontier-) guarded, then ground(R) is (frontier-) guarded.

• |ground(R)| is exponential in the number of affected variables per rule and polynomial in the size of F (more precisely: the size of C).

• ground is arity-preserving.

A more clever partial grounding

For convenience, we fix bijections # R : nav(R) → [1..|nav(R)|] which for every rule, assign numbers to all the non-affected variables. Now let v 1 , . . . , v m and v 1 , . . . , v s be variable symbols not used in R, where m = |C| and s = max(|nav(R)|) R∈R .

We now define the function τ , mapping rules from R to frontier-guarded rules as follows:

τ (∀x 1 ...x k (body → (∃y 1 ...y k head))) = ∀τ R (x 1 )...τ R (x k ) v 1 ...v m (τ R (body) → (∃y 1 ...y k τ R (C))) τ R ( i∈I a i ) = i∈I τ R (a i ) τ R (p(t 1 , ..., t l )) = p(v 1 , ..., v m , v 1 , ..., v s , τ R (t 1 ), ..., τ R (t l )) τ R (t) = v # R (t) if t ∈ nav(R) t otherwise.
Note that thereby the arity of all predicates is increased by m + s. The first m positions will be used to permanently hold all constants c 1 , . . . , c m and the next s positions will serve as a pool for special "safe variables" (i.e., non-affected) which will be used for our implicit grounding. Now we let

τ (R) := {τ (R) | R ∈ R} ∪ S,
where S contains for every predicate p (let its arity be l) from R the rules R p

c i →v j ∀v 1 , . . . , v m , v 1 , . . . , v s , x 1 , . . . , x l (p(v 1 , . . . , v m , v 1 , . . . , v s , x 1 , . . . , x l ) → p(v 1 , . . . , v m , v * 1 , . . . , v * n , x 1 , . . . , x l ))
where v * j = v i and v * k = v k for all k = j. Thereby, the rule R c i →v j is used to realize the bindings the constant c i to the safe variable v j , which in turn will be used in the above translation to realize the implicit grounding. S contains m • s rules for every predicate p, i.e., the total size of τ (R) is polynomially bounded by the combined size of F and R. Note that the choice of c 1 at positions m + 1, . . . , m + s is just an arbitrary one. Similarly, τ (Q) := {τ (atom) | atom ∈ Q}.

Analog to the argumentation above, we see that the size of τ (F ) is polynomially bounded by the combined size of F and R.

Let us now sketch the ideas of the translation. Any atom having the form p(c 1 , . . . , c m , . . . , e 1 , . . . , e l ) corresponds to a fact p(e 1 , . . . , e l ) originally present F , where F is S-derived from τ (F ), can be naturally restricted to a homomorphism h : body(R) → F .

We now prove the lemma. (⇒) Assume F, ground(R) |= Q. Then, there is a derivation sequence from F to a fact F k and a homomorphism from Q to F k , which, by remark (3), can be extended to a homomorphism from τ (Q) to τ (F k ). Let us show that τ (F k ) can be indeed τ (R)-derived from τ (F ). From remark (4): if R i is applicable to a fact F by a homomorphism h, then τ (R) is applicable by an extension h of h to a fact F S-derivable from τ (F ). Furthermore, from remark (2) τ (α(F , R i , h)) is Sderivable from α(F , τ (R), h ). Thus, from any ground(R)-derivation sequence from F to F k , one can build an τ (R)-derivation from τ (F ) to τ (F k ). (⇐) Assume τ (F ), τ (R) |= τ (Q). Then, there is a derivation sequence, say D, from τ (F ) to a fact F k and a homomorphism from τ (Q) to F k . From D, we extract the sequence of applications of τ (R) rules for all R ∈ R. This subsequence yields a ground(R)-derivation sequence from F to F q , such that F k = τ (F q ). Indeed, assume, for a given rule R ∈ R, τ (R) is applicable to a fact F by homomorphism h . h maps nav(R) to a subset of C. Let R i be the rule corresponding to this partial grounding. Let F be the fact such that F can be S-derived from τ (F ). Then R i is applicable to F by the natural restriction h of h , and by remark (2), α(F , τ (R), h ) is S-derivable from τ (α(F, R i , h)). Thus, from any τ (R)-derivation from τ (F ) to F k , one can extract a ground(R)-derivation sequence from F to a fact F q . Since there is a homomorphism from τ (Q) to F k , F k is not only S-derivable from τ (F q ) but is equal to τ (F q ). By remark (3), there is a homomorphism from Q to F q .

Theorem 19 Given F , R (wfg) and Q, we have that

F, R |= Q iff τ (F ), τ (R) |= τ (Q).
Proof: Consequence of Lemmas 1 and 2.

By adding the set of variables nav(R) to each atom in R, τ transforms each weak guard (of body(R) or f r(R)) into a guard. S is a set of rules with atomic head (furthermore Datalog) thus it is guarded. Hence, if R is a set of wg (resp. wfg) rules, then fg(R) is a set of g (resp. fg) rules.

Property 20 (Properties of τ )

• If R is weakly (frontier-) guarded, then τ (R) is (frontier-) guarded. • |τ (R)| is polynomial in the combined size if R and F (more precisely: the size of C).
it is straightforward that it can be equivalently written as the first-order sentence

S R : ¬∃x 1 , . . . , x k (H ∧ ¬p R (x i 1 , . . . , x i k ))
which in turn is obviously equivalent to the set {S * , S * * } of formulae consisting of

S * R : ¬∃x 1 , . . . , x k (H ∧ p R (x i 1 , . . . , x i k )) and S * * R : ∀x i 1 , . . . , x i k (p(x i 1 , . . . , x i k )∧¬p R (x i 1 , . . . , x i k ) → p R (x i 1 , . . . , x i k ))
for a newly introduced predicate p R (remember that p(x i 1 , . . . , x i k ) ∈ H). S * * R can be equivalently transformed into

S * * * R : ∀x i 1 , . . . , x i k (p(x i 1 , . . . , x i k ) → p R (x i 1 , . . . , x i k )∨p R (x i 1 , . . . , x i k ))
which is in GF (but not a guarded ∀∃-rule, as it contains a disjunction in the head). So finally, we get that

F, R |= Q iff F ∪ {T R , S * * * R | R ∈ R} ∪ {S * R | R ∈ R} |= Q ( †)
where the first two sets are in GF and the third consists of negated existentially quantified conjunctions of atoms. Hence we can conceive every S * R as a negated conjunctive query ¬Q R . Consequently we have

{S * R | R ∈ R} ≡ {¬Q R | R ∈ R} ≡ R∈R ¬Q R ≡ ¬ R∈R Q R
which allows to rephrase ( †) as

F ∪ {T R , S * * * R | R ∈ R} |= Q ∨ R∈R Q R ( ‡)
which leaves us with a GF theory on the left hand side and a union of boolean conjunctive queries on the right hand side. Since the presented translation from the original problem to UCQ entailment in GF is linear, we have thus established the theorem.

To prove the 2EXPTIME-hardness of fr1-rules we adopt and adapt the construction used to show 2EXPTIME-hardness for CQ entailment in the DL ALCI from [START_REF] Lutz | Inverse roles make conjunctive queries hard[END_REF].

Theorem 23 CQ entailment for fr1-rules with bounded predicate arity is 2EXPTIMEhard.

Proof: We show that Lutz' knowledge base representation of the halting problem for exponentially space-bounded alternating Turing machines can be expressed by frontier-guarded ∀∃-rules by applying the following modifications:

1. The acceptance condition is encoded in a "backward-manner" as in the encoding used to prove EXPTIME-hardness for Horn-FLE in [START_REF] Krötzsch | Complexity boundaries for Horn description logics[END_REF].

2. Negated concepts ¬A are replaced by a concept B defined to be disjoint with A.

3. The query is modified and turned into Horn rules. This ensures that information about configuration changes can be propagated forward making the use of disjunction obsolete.

Then we get a rule set R with at most binary predicates encoding the above mentioned problem and therefore showing the claim.

For our construction, we modify the encoding of computations of the Turing-Machine in the following way: when visiting an existential state, we enforce the presence of all successor states instead of nondeterministically picking just one: R ∃s m+2 .(q a) (q ,a ,M )∈δ(q,a) ∃s.(R T q ,a ,M ) for all q ∈ Q ∃ , a ∈ Γ Obviously, this different encoding necessitates to revisit the way the acceptance condition is encoded. Rather than just forbidding that the rejecting state q r occurs anywhere, we determine whether the initial configuration is accepting by propagating information of acceptance backwards the computation tree back to the initial configuration using the concept name T accept :

R ∃s m+2 .q a T accept R ∃s m+2 .(q a) ∃s.(R T q ,a ,M T accept ) T accept for all q ∈ Q ∃ , a ∈ Γ, (q , a , M ) ∈ δ(q, a) R ∃s m+2 .(q a) (q ,a ,M )∈δ(q,a) ∃s.(R T q ,a ,M T accept ) T accept for all q ∈ Q ∀ , a ∈ Γ
We now further modify T w in a semantics-preserving way in order to obtain a Horn-ALC rs TBox. First substitute every occurrence of ¬A i by a new atomic concept A i , likewise substitute ¬H by H and q∈Q ¬q by Q, then add the following set of axioms to T w : A i A i ⊥ for i < m, H H ⊥, and Q q∈Q ⊥. Note that this encoding is possible as the tertium non datur part of the negation is not needed for the modeling.

As next observation we find that some of the conditions for configuration trees which are not in Horn-ALC rs can be discarded or rewritten into Horn form:

• G a∈Γ a a,a ∈Γ,a =a ¬(a a ) The disjunction on the right hand side can be safely dismissed as the subsequent axiomatization realizes that (1) every tape position of the initial configuration gets assigned one entry and (2) the interplay of axioms and the way we rewrite the query into a rule ensures that a complete assignment of tape entries in one configuration ensures a complete assignment in all successor configurations.

• (L i H) (∀s.((L i+1 A i ) → H) ∀s.((L i+1 A i ) → H)) (∀s.((L i+1 A i ) → H) ∀s.((L i+1 A i ) → H))
This axiom ensures that there is exactly one position on the tape where the head is located. By a similar argument as above, we know that the rest of the axiomatization already ensures that there is at least one head position indicated in every configuration. In order to guarantee that in every configuration there is at most one head position, we can alternatively use the following axioms:

L i ∃s.(L i+1 H A i+1 ) H ∀s.(L i+1 A i+1 → H).
• L m H ∀s 2 .(G → q∈Q q) This axiom can be discarded as well, as the rest of the axioms ensures a deterministic assignment of one q to the head position.

We now come to the core part of our modification. Recap that the purpose of the conjunctive query q w = q Y ∪ q Z ∪ i<m q i w is to detect cases where tape entries with the same binary addresses deviate in terms of their entries or the indicated state of the Turing machine. Thereby q Y ∪ i<m q i w is used to identify pairs of corresponding cells (and bind them to variables v and v ) whereas q Z detects deviating assignments in order to rule them out. As we aim at enforcing synchronized entries rather than eliminating models where they are out of sync, we only reuse the identification part of the query in our rule bodies and define

R sync = {R C | C ∈ Q ∪ {Q} ∪ Γ} where R C is defined as q Y ∪ i<m q i w ∪ {C(v)} → C(v ).
Summing up, we have come up with a set of first-order Horn rules R sync and rewritten Lutz' TBox T w into a Horn-ALC rs TBox T w , such that (using the firstorder semantics) A w ∪ T w ∪ R sync |= T accept (a) exactly if the Turing machine accepts w. We further find that A w ∪ T w ∪ R sync can be rewritten from Horn-ALC rs to Horn-ALCI such that ground consequences are preserved (see again [START_REF] Lutz | Inverse roles make conjunctive queries hard[END_REF]). Finally, the standard translation into first-order logic of any Horn-ALCI knowledge base yields a frontier-1 rule base. Likewise, the rewriting of R sync yields only ∀∃-rules with frontier size one (note however for Section 7 that these rules are not acyclic). Consequently we have shown that the word problem of an alternating ExpSpace-bounded Turing machine can be polynomially encoded into the entailment problem for frontier-one ∀∃-rules with predicate arity ≤ 2. Hence we have shown 2EXPTIME-hardness for the latter.

Data Complexity of fg-and fr1-rules

The proof for PTIME membership for data complexity is based on a specific locality property of derivations for fg-rules which is established in the following lemma 4.

Let us first assume that no constant occurs in R and Q (we will introduce them later). As we are interested in data complexity, we consider that R and Q are fixed. Let n be the maximal number of frontier variables occurring in R and let m be the maximal number of variables occurring in the body of any rule or in Q. Now, let G denote all the semantically different formulae of the shape

∃x 1 , . . . , x m ( atom∈Conj atom)
where Conj is a subset of the set of all atoms obtained from predicates P and terms from {x 1 , . . . , x m , y 1 , . . . , y n }. Given terms t 1 , . . . , t n , it suffices to know for which ϕ ∈ G holds ϕ[y 1 /t 1 , . . . , y n /t n ] in order to determine what roles t 1 , . . . , t n can play in any rule application. Obviously, G is finite, so let |G| = ν. For any specific ϕ and t 1 , . . . , t n we need at most m terms (i.e. assignments to the existentially quantified variables) to witness that ϕ[y 1 /t 1 , . . . , y n /t n ] holds. Hence, an upper bound for witnesses for all respective ϕs is w max := ν • m.

We now proof two auxiliary lemmas. that Ground is finite). Now let D be the set of Datalog rules (i.e., such that var(head) ⊆ var(body)) that contains every ∀y 1 , . . . , y wmax (body → head) (with body ⊆ Ground and head ∈ Ground) for which body, R |= head.5 Then, let P(R, Q) contain D.

• Likewise, for every grounding Q of Q (i.e., obtained from Q by mapping its variables to {y 1 , . . . , y wmax }) and any body ∈ Ground with body, R |= Q , let P(R, Q) contain the rule ∀y 1 , . . . , y wmax (body → match), where match is a new nullary predicate symbol.

Then we get the following lemma:

Lemma 5 For R (fg) without constants, for every fact

F , F, R |= Q iff F, P(R, Q) |= match.
Proof: ⇐: all rules of the first kind in P(R, Q) are consequence of R and the body of the match rules encode facts built on variables to which Q can be mapped with a surjective homomorphism.

⇒: First, it is straightforward that F, R |= Q F, R ∪ {Q → match} |= match.
Let F = F 0 , . . . , F k be a derivation sequence for F, R∪{Q → match} |= match.

We split this derivation sequence starting from F 0 at every point where F i+1 \ F i = {a} for an atom a with vars(a ) ⊆ vars(F 0 ). We end up with separate derivation sequences F a 1 , F ∪ {a 1 } a 2 , . . ., F ∪ {a 1 , . . . , a l-1 } a l = match, each satisfying the condition that the finally derived fact is the only new fact which contains only variables from vars(F ). For every of these derivation sequences F j a j we can apply Lemma 4 to find sets of variables V j ⊆ vars(F j ) such that F j | V j , R |= a j . Yet, then P(R, Q) contains an according rule which allows to deduce a j from F j in one step. Put together this gives a deduction of F, P(R, Q) |= match.

In order to leverage the above lemma for arbitrary fg-rule sets containing constants, we need to transform the task of deciding F, R |= Q into a setting where constants are excluded. The following definition and lemma provide for this by applying a partial grounding and subsequently shifting positions taken by constants into predicates.

Definition 24 Let R be an arbitrary fg-rule set and let Q be a CQ. Let A be the set of constants occurring in R and Q. For every predicate p of arity k occurring in R and Q and every partial mapping γ : {1, . . . , k} → A, we let p γ denote a new (k -|dom(γ)|)-ary predicate. Let ξ A map atoms from R and Q to new atoms by projecting out positions filled by constants from A. 6 We lift the function ξ A to conjuncts and rules in the obvious way. Now, letting P G A (R) denote all partial groundings of R where some universally quantified variables are substituted by constants from A, we define the rule set cfree

(R, Q) = {ξ A (R ) | R ∈ P G A (R), R ∈ R ∪ {Q → match}}
Lemma 6 For R (fg), cfree(R, Q) is fg and constant-free. Given a fact F and assuming fixed R and Q, the size of ξ A (F ) and the time to compute it is polynomially bounded by

|F |. Moreover F, R |= Q iff ξ A (F ), cfree(R, Q) |= match.
The preceding lemma then allows to extend Lemma 5 to fg-rules with constants:

Lemma 7 For R (fg) holds F, R |= Q exactly if ξ A (F ), P(cfree(R, Q), match) |= match.
We can now state the following complexity Theorem:

Theorem 24 CQ entailment for fg-and fr1-rules is PTIME-complete for data complexity.

Proof: Thanks to Lemma 7, we have reduced the problem to atom entailment in Datalog. Noting that P(cfree(R, Q), match) is independent from F and (w.l.o.g. assuming that F contains only constants) that ξ A (F ) consists only of ground atoms, PTIME data complexity membership follows from the PTIME data complexity of entailment in Datalog [START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF]. PTIME-hardness for data complexity is a direct consequence of the same result for propositional Horn logic.

Body-Acyclic fg-and fr1-Rules

Tree-like structures often lead to lower complexity. We focus here fg-rules with an acyclic body (in the sense of hypergraph-acyclicity). In this section, we study the complexity of frontier-guarded rules with an acyclic body. The acyclicity notion considered here is the hypergraph acyclicity stemming from database theory, which corresponds to the independently defined notion of an acyclic guarded covering [START_REF] Kerdiles | Saying it with Pictures: a logical landscape of conceptual graphs[END_REF] (see [START_REF] Chein | Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs[END_REF] for details about this equivalence).

To simplify the next notions, we first proceed with some normalization of a set of fg-rules, such that all rules are either disconnected (they have an empty frontier) or they have a non-empty frontier and a "variable-connected" body:

1. Let R be a rule with a non-empty frontier and let B be the hypergraph assigned to body(R). For each node in B assigned to a constant, split it in as many nodes as hyperedges it belongs to (thus each constant node obtained belongs to a single hyperedge); let B be the hypergraph obtained; let C f be the connected component of B that contains the frontier guard(s) (if there are several frontier guards, they are all in the same connected component);

2. build a rule R 0 by gathering all connected components of B except C f ; the body of R 0 is made of the conjunction of all these atoms and its head is restricted to a single nullary predicate p 0 .

3. build the rule R f with body made of the atoms from C f and p 0 , and head equal to head(R).

Let us consider an instance (F, R, Q) of the entailment problem, where R is a set of fg-rules. We process all non-disconnected rules from R as described above, which yields an equivalent set of rules. Then, we eliminate disconnected rules (initial disconnected rules and obtained R 0 rules) by integrating them to F as in [START_REF] Baget | Walking the decidability line for rules with existential variables[END_REF]: this can be done with d calls to an oracle solving the entailment problem for fg-rules, where d is the number of disconnected rules.

From now on, we thus assume that all fg-rules have a non-empty frontier and their body on non-nullary predicates is "variable-connected", i.e., the associated hypergraph is connected and cannot be disconnected by the above step 1 (B = B ). We will also ignore nullary predicates, as they play absolutely no role.

Body-Acyclic fg-Rules (General case)

Let H be a hypergraph. The acyclicity of H is usually defined with respect to its socalled dual graph, whose nodes are the hyperedges of H and edges represent their intersection. We will use here a close notion, that we call decomposition graph of a set of atoms, which groups together a guard and the atoms it guards into a single node.

We assign the following decomposition graph D(S) to a set of atoms S:

• Let {C 1 , . . . C p } be a partition of S such that each C i is guarded, with p minimal for this property.

• The set of nodes of D(S) is {C 1 , . . . C p } and there is an edge C i C j (with i = j) if C i and C j share (at least) a variable; each edge C i C j is labeled by the variables common to C i and C j (noted vars(C i C j )).

An edge C i C j of the decomposition graph is said to be removable if there is another path between C i and C j such that the labels of all edges in this path contain the label of C i C j (this condition has to do with the so-called running decomposition property: the set of nodes in which a given variable occurs yields a connected subgraph of the decomposition graph; removing removable edges keeps this property). S is said to be (hypergraph-) acyclic (which corresponds to the fact that the associated hypergraph is acyclic) if each connected component of its decomposition graph can be turned into a tree by removing only removable edges (such a tree is usually called a join tree in databases). It is well known that when a hypergraph is acyclic, a join tree/forest can be built from it in polynomial time. An fg-rule R is said to be (ba) if its body is hypergraph-acyclic.

Note that our starting assumption (variable-connected body) ensures that the decomposition graph of the fg-rules we consider is connected. Let R be a ba-fg rule and let J be an join tree associated with body(R). Let C r be a J node that contains a frontier guard. J is considered as rooted in C r , which yields a direction of its edges from children to parents: a directed edge (C i , C j ) is from a child to its parent. R is translated into a set of guarded rules {R 1 , . . . R p } as follows:

• To each edge (C i , C j ) is assigned the atom a i = q i (var(CiCj)), where q i is a new predicate • To each C i = C r is assigned the rule:

R i = (conjunct(C i ) ∧ (C k ,C i ) a k ) → a i
• To C r is assigned the rule R r = (conjunct(C r ) ∧ (C k ,Cr) a k ) → head(R)

Note that the decomposition graph associated with the body of a guarded rule is restricted to a single node. Thus, guarded rules are trivially ba-fg rules. The above translation is the identity on guarded rules. The translation is linear in the size of the rule and arity-preserving (the arity of the new predicates is bounded by the arity of existing predicates). We conclude that the complexity of conjunctive query entailment with ba-fg-rules is the same as with guarded rules: for combined complexity, it is EXPTIME-complete with bounded arity and 2EXPTIME-complete with unbounded arity; it is in P for data complexity.

The above reduction is polynomial in the size of the rule and arity-preserving. Thus, previous complexity results on guarded rules apply to ba-fg-rules (in particular they are EXPTIME-complete for bounded-arity combined complexity, while fg-rules are 2EXPTIME-complete).

Finally, let us point out that hypergraph-acyclicity of rule bodies alone is not enough to obtain good properties: that the head of a rule is connected to only one node of the decomposition graph (thus, that the frontier is guarded) is crucial. Without this assumption, the entailment problem remains undecidable. This can be checked for instance with the reduction from the word problem in a semi-Thue system, known to be undecidable, to the entailment problem (in a conceptual graph setting) built in [START_REF] Baget | The Complexity of Rules and Constraints[END_REF]. This reduction yields rules with a body restricted to a path and frontier of size 2.

Body-Acyclic fg-Rules (Unary/Binary case)

We now consider the special case of predicates with arity bounded by 2, which is relevant w.r.t. description logics. Let us note ba-fg-2 this rule fragment.

To a set of binary atoms is naturally associated a (multi-)graph (unary atoms can be ignored for our purpose). The acyclicity notion can be simplified. Let us say that a cycle in such a graph is a true cycle if it contains only (distinct) variable nodes and is of length strictly greater than 2 (in other words, multi-edges are allowed).

Property 25 A set of binary atoms has no true cycle if and only if it is hypergraphacyclic.

Proof: In the binary case, edges in the decomposition graph contain exactly one variable. Let G S be the graph of the atom set S and D S be its decomposition graph. If G S has no true cycle, then any cycle in D S is made of edges labeled by the same variable; thus, any of these edges is removable, which breaks the cycle. In the other direction: take a true cycle in G S , which passes through k distinct variables, k ≥ 2. It yields a cycle in D S with all k edges labeled by a distinct variable. It can be checked that if D S has a cycle whose edges do not have all the same label (and in this case this cycle has at least three edges with distinct labels), then it cannot be made acyclic (f.i., by induction on the number of removable edges in D S ).

Let us now sketch links between the ba-fg-2 rule fragment and Horn description logics, firstly introduced in [START_REF] Hustadt | Data complexity of reasoning in very expressive description logics[END_REF]. Based on the fact that description logics [BCM + 07] are fragments of first-order logic, the logic Horn-L for some DL L is roughly defined as the axioms of L whose standard translation into FOL and subsequent skolemisation yields Horn clauses. The ba-fg-2 fragment includes the DL Horn-ALCOI Self ( ) (see [START_REF] Krötzsch | Complexity boundaries for Horn description logics[END_REF] for a treatment of Horn DLs -ALC denotes the basic Boolean-closed description logic; O indicates the nominals and is needed if constants are involved; I stands for role inverse; Self allow concepts of the form ∃R.Self to indicate roles looping back to their source, ( ) indicates role conjunction). As a consequence of results from [START_REF] Krötzsch | Complexity boundaries for Horn description logics[END_REF], deduction of single atom facts (and hence CQ entailment) in Horn-ALCOI Self ( ) is EXPTIME-hard; CQ answering is known to be in 2EXPTIME as a consequence of results in [START_REF] Calvanese | Regular path queries in expressive description logics with nominals[END_REF]. However note that ba-fg-2 rules are more expressive than that: they allow for arbitrarily structured rule heads, whereas for Horn-ALCOI Self ( ) rule heads are required to be essentially tree-structured (a consequence implicitly imposed by the DL notation).

Still from the results on guarded rules, we get that conjunctive query entailment with ba-fg-2 rules is in EXPTIME for combined complexity and in P for data complexity. An EXPTIME lower bound easily follows from the fact that standard reasoning in the much weaker Horn-FLE is already EXPTIME-Hard, as shown in [START_REF] Krötzsch | Complexity boundaries for Horn description logics[END_REF] 7 . The problem is thus EXPTIME-complete. Since rules translating Horn-FLE are both guarded and fr18 , this lower bound holds for ba-guarded rules and ba-fr1-rules.

Body-Acyclic Frontier-1 Rules

PTIME-complete data complexity follows from the proof of Th. 24; about combined complexity, EXPTIME-hardness with bounded arity (thus with unbounded arity too) follows from the fact that standard reasoning in the weaker DL fragment Horn-FLE is EXPTIME-hard (see preceding subsection); from EXPTIME membership of guarded rules in the bounded arity case, we conclude that ba-fr1-rules are EXPTIME-complete with bounded-arity. The only remaining question is whether they are simpler than ba-fg-rules in the unbounded arity case. We established EXP-TIME membership for the constant-free variant, and keep trying to prove it for the general case.

Conclusion

We have introduced the notion of greedy bts of existential rules that subsumes guarded rules as well as their known generalizations and gives rise to a generic algorithm for deciding CQ entailment. Moreover, we have classified known gbts subclasses w.r.t. their combined and data complexities. Some interesting open issues remain, e.g. the exact complexity of gbts in the unbounded predicate arity case and the recognizability of gbts. Future work will aim at the integration of rules expressing equality and other properties such as transitivity into this framework, preserving decidability, and trying to keep the desirable PTIME data complexity of fg-rules.

Figure 1 :

 1 Figure 1: Complexity Boundaries. Tight bounds for gbts and ba-fr1 are yet unknown, we conjecture 3EXPTIME-completeness and EXPTIME-completeness, respectively.

  F . Definition 1 (∀∃-Rule) A ∀∃-rule (existential rule, or simply rule when not ambiguous) is a formula R = ∀x∀y(B[x, y] → (∃zH[y, z])) where B = body(R) and H = head(R) are conjuncts, resp. called the body and the head of R. The frontier of R, noted fr (R), is the set of variables vars(B) ∩ vars(H) = y.

Proof: ⇒

 ⇒ We first show that the pattern of B in S is included in p . Let (G, ψ) be in the pattern of B . By definition of a pattern, there is a homomorphism ψ from G to S (F ) that extends Ψ B • ψ. We define a partition {G o , G n } of G, where G o contains the atoms that are mapped to S(F ). Hence, G n is the inverse image by ψ of atoms created at the last step. Thus, (G n , ψ |Gn ) belongs to p and (G o , j • ψ |Go ) belongs to p. Thus, G = G(G o , G n , j • ψ |Go , ψ |Gn , j). Hence, w.r.t. notations in Definition 18, we have p 1 = p, p 2 = p and p 2 = p and we choose G = G, ϕ = id, π 1 = j • ψ |Go and π 1 = ψ |Gn .

  Furthermore, let τ (F ) := {τ (atom) | atom ∈ F } with τ (p(e 1 , . . . , e l )) = p(c 1 , . . . , c m , c 1 , . . . , c 1 s , e 1 , . . . , e l ).

Lemma 3 (

 3 Derivation Sequence Splitting) Let F, R |= Q witnessed by an according derivation sequence F = F 0 , . . . , F k . Let moreover a ∈ F i+1 \ F i be an atom with vars(a) ∈ vars(F ). Then there are derivation sequences for F, R |= a and F ∪ {a}R |= Q both having a length strictly smaller than k. Lemma 4 Let R be a fg rule set. Let F, R |= a for an atom a = p(z 1 , . . . , z l ) with vars(a) ⊆ vars(F ) for which there is an according derivation sequence F = F 0 , . . . , F k such that all atoms from F k \ {a} that contain only variables occurring in F are already present in F . Then there is a set V ⊆ vars(F ) with |V | ≤ w max such that F | V , R |= a where F | V := {b | b ∈ F, vars(b) ⊆ V }.

Table 1 :

 1

Combined and Data Complexities that π(Q) ⊆ F (we say that π maps Q to F ). It is well-known that, given two facts F and Q, F |= Q iff there is a homomorphism from Q to

The DL constructor called existential restriction (∃R.C) is fundamental in these DL. The logical encoding of an membership that contains it in its right-part requires an existentially quantified variable in the corresponding rule head. For instance, the above rule example can be seen as the logical translation of the DL inclusion Human HasP arent.Human.

We assume that the reader is familiar with this notion.

This is necessary to guarantee termination, resembling the blocking techniques applied in DL tableaux algorithms.

We call them alternative patterns since we could similarly define patterns on the bags of a derivation tree.

Here we need entailment checks with any decision procedure. But this can be done independent of the underlying fact and the created Datalog program is fixed for given R and Q.

For instance ξ {a,b} (p(x, a, b, c)) = p {2 →a,3 →b} (x, c).

It is known that conjunctive query entailment is at least as difficult as standard reasoning.

Briefly said, in Horn-FLE, we have , ∃R.C, , ⊥, and ∀R.C (only in the right side of inclusions); no role inclusion, nor role composition.

in K or derived from K. From any such fact, the rules in S allow to generate all facts of form p(c 1 , . . . , c m , c i 1 , . . . , c is , e 1 , . . . , e l ) for any i 1 , . . . , i s in 1 . . . m. We cannot make τ create all these facts directly as there would be exponentially many (and the translation would not be polynomial anymore). This will allow to map the non-affected variables added to each rule atom: if an atom a = p(t 1 , . . . , x, . . . , t l ) ∈ body(R), with x being the ith element in nav(R) (# R (x) = i), can be mapped to b = p(e 1 , . . . , c j , . . . , e l ), with x being mapped to the constant c j , then the S rules allow to generate from b an atom p(c 1 , . . . , c m , c i 1 , . . . , c j , . . . , c is , e 1 , . . . , c j , . . . , e l )

Lemma 2 Let F be a fact,R a set of rules and Q a query. Then we have

Proof:

Let us begin with some easily checked remarks: (1) All atoms initially present in τ (F ) or derived from it are of form p(c 1 , . . . , c m , c i 1 , . . . , c is , e 1 , . . . , e l ), where the c i j are constants from C.

(2) The set of atoms S-derivable from a fact p(c 1 , . . . , c m , . . . , c i 1 , . . . , c is , e 1 , . . . , e l ) is exactly the set of atoms p(c 1 , . . . , c m , c i 1 , . . . , c i s , e 1 , . . . , e l ), where the c i j are constants from C, i.e., (c i 1 , . . . , c is ) can be replaced by any s-tuple of constants.

(3) Let F be a fact, with F = F or is derived from F . Any homomorphism h : Q → F can be trivially extended to a homomorphism h : τ (Q) → τ (F ), with for all variable x in Q, h (x) = h(x). Reciprocally, any homomorphism

atoms by h(t), where # R (t) = j (t is the j-th nav variable in R). According to remark (2), F can be obtained from τ (F ) with S rules. h is defined as follows:

• τ is not arity-preserving: the arity of predicates grows with the size of C.

Corollary 21 Any instance of CQ entailment with w(f)g-rules can be polynomially translated into an instance of the same problem with (f)g-rules.

Proof: The size of τ (F ) (resp. τ (R), τ (Q)) is polynomially bounded by the combined size of F and R. By adding nav(R) to each atom in R, τ transforms each weak guard into a guard. The rules from S are guarded. Hence, if R is w(f)g, then τ (R) is (f)g. We conclude with Th. 19.

Frontier-Guarded and Frontier-One Rules

In this section, we show that fg-and fr1-rules are both PTIME-complete for data complexity and 2EXPTIME-complete for combined complexity no matter whether predicate arity is bounded or not.

Combined Complexity of fg-and fr1-rules

In [START_REF] Bárány | Querying the guarded fragment[END_REF], the authors establish the result that deciding entailment of unions of boolean CQ in the guarded fragment (GF) of FOL is 2EXPTIME-complete. This result can be used to prove the following theorem.

Theorem 22 CQ entailment for fg-rules is in 2EXPTIME.

Proof: We first observe that every frontier-guarded ∀∃-rule can be translated into two rules one of which is a guarded ∀∃-ruleand the other is Datalog: take a frontierguarded rule R : ∀x 1 , . . . , x k (H → (∃y 1 , . . . , y k C))

with a frontier guard p(x i 1 , . . . , x i k ) ∈ H. Then we introduce a new k -ary predicate p R and let separate(R) be the set containing the following two rules.

It is straightforward to see that for any frontier-guarded rule set R, we have

Obviously, T R is guarded (and hence also lies in GF) while S R is range restricted and frontier-guarded (but not necessarily guarded). The latter are the problematic ones that we have to take care of. Considering a rule of this latter type, i.e.

S R : ∀x 1 , . . . , x k (H → p R (x i 1 , . . . , x i k ))

Proof: We choose V such that it contains a witness for every satisfied ϕ w.r.t. z 1 , . . . , z l as defined above. Now we proof the statement by an induction on the derivation length k. Note that the case for k = 0 is trivial, as clearly {z 1 , . . . , z l } ∈ V . For k = 1, we have that a ∈ α(F, R, π). In that case, we can be sure that V contains a witness for the rule body of R.

For greater k, consider the first step of the derivation sequence F 1 = α(F 0 , R, π). Because of the assumption, head(R) must contain at least one existentially quantified variable per atom. Hence, let {y 1 , . . . , y m } := vars(F 1 \ F 0 ) the nonempty set of variables newly introduced by the first derivation step. Now we split the derivation sequence starting from F 1 (having length k -1) at every point where F i+1 \ F i = {a } for an atom a with vars(a ) ⊆ vars(F 1 ). We end up with separate derivation sequences F 1 a 1 , F ∪ {a 1 } a 2 , . . ., F ∪ {a 1 , . . . , a l-1 } a l = a, each satisfying the condition that the finally derived fact is the only new fact which contains only variables from vars(F 1 ). Moreover, due to our assumption, none of the a 1 , . . . , a l contains variables only from vars(F ). According to Lemma , each of these derivation sequences has length of at most k -1. We now apply the induction hypothesis to identify the variables V j ⊆ vars(F j ) with |V j | ≤ n such that F j | V j , R |= a j . The variables from V j ∩vars(F )\ {x 1 , . . . , x l } are exchanged by substitutes from V such that the set of witnessed ϕs (w.r.t. the variables contained in a j ) does not change, hence F j | V j , R |= a j still holds for the modified V j . This is possible due to the former choice of V . Each of the modified V j that we thus obtain contains only variables from V ∪{y 1 , . . . , y m }, therefore we can conclude F 1 | V ∪{y 1 ,...,ym} , R |= a. As we already know that

Relying on Lemma 4 we next provide a translation of constant-free R and Q into a Datalog program. The main idea is to "compile away" existential variables introduced in rule heads by "precomputing" deduction sequences that finally result in a query match.

Definition 23 Given a constant-free fg-rule set R, we define the Datalog-program P(R) as follows: Let {y 1 , . . . , y w R } be a set of variable symbols. Let G denote the finite set of all atoms with predicates from R and terms from {y 1 , . . . , y w R }. Now let P(R) be the set of Datalog rules containing every ∀y 1 , . . . , y w R (B → h) (with B ⊆ G and h ∈ G) for which B, R |= h.

We define the Datalog-program P(R, Q) as follows:

• Let {y 1 , . . . , y wmax } be a set of variable symbols. Let Ground denote the set of all "groundings" of P-atoms with symbols from {y 1 , . . . , y wmax } (note