Walking the Complexity Lines for Generalized Guarded Existential Rules

1 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. 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(Parent(y, x) ∧ Human(y))). Such rules are known in databases as TupleGenerating Dependencies (TGDs) and have been extensively used, e.g. for data exchange [Fagin et al., 2005]. 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 [Cal`ı et al., 2008; Cal`ı et al., 2009; Cal`ı et al., 2010], and independently, stemming from graph-based knowledge representation formalisms [Chein and Mugnier, 2009], as ∀∃-rules [Baget et al., 2009; Baget et al., 2010]. 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 [Cal`ı et al., 2009; Baget et al., 2010].

Sebastian Rudolph KIT Germany

rudolph@kit.edu Micha¨el Thomazo Univ. Montpellier II France thomazo@lirmm.fr

The ability to generate existential variables, associated with arbitrarily complex conjunctions of atoms, makes entailment with these rules undecidable [Beeri and Vardi, 1981; Chandra et al., 1981]. Since the birth of TGDs, and recently within the Datalog+/- and ∀∃-rule frameworks, various conditions of decidability have been exhibited. Three "abstract" classes have been introduced in [Baget et al., 2010] 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 [Johnson and Klug, 1984]); sets of rules ensuring this condition are called finite expansion sets (fes); a more general condition introduced in [Cal`ı et al., 2008] 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 [Courcelle, 1990]. The third condition, giving rise to finite unification sets (fus), relies on the finiteness of (a kind of) backward chaining mechanism. None of these three abstract classes is recognizable, i.e., the associated membership problem is undecidable [Baget et al., 2010].

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 [Cal`ı et al., 2008] 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 [Cal`ı et al., 2008]. 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 [Baget et al., 2009]. In a frontier-guarded rule (fg), an atom in the body guards the frontier [Baget et al., 2010]. Hence, fg-rules generalize both guarded rules and fr1rules. 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 [Baget et al., 2010]. Of all known recognizable bts classes, wfg is the class subsuming the most of the others.

Example 1 Parent(x, y), Parent(y, z) → isGdParent(x) (with simplified syntax) is Datalog and fr1 but not guarded; while 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 [Cal`ı et al., 2008; Cal`ı et al., 2009]. 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). We provide a generic algorithm for this class, which is worstcase optimal for data complexity, as well as for combined complexity in the case where predicate arity is bounded. Second, 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 a hypergraph-acyclic body (notation ba) and point out that body-acyclic 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 boundedarity 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. Detailed proofs can be found in the accompanying research report [Baget et al., 2011].

1. ExpTime-c if no constants in rules

Table 1: Combined and Data Complexities

2 Preliminaries

As usual, an atom is of the form p(t1, . . . , tk) where p is a predicate with arity k, and the ti 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. 1 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, vars(A) and terms(A) denote 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 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 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.

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)).

Definition 3 (Derivation) Let F be a fact, and R be a set of rules. An R-derivation of F is a finite sequence (F0 = F), . . . , Fk s.t. for all 0 ≤ i < k, there is Ri ∈ R and a homomorphism πi from body(Ri) to Fi s.t. Fi+1 = α(Fi, Ri, π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 (F0 = F), . . . , Fk such that Fk |= 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

1 Note that thereby we generalize the traditional notion of a fact in order to take existentially quantified variables into account.

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 treewidth 2 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 [Fagin et al., 2005] for a precise definition). The only property of affected variables used in this paper is that a rule application necessarily maps non-affected variables only to terms from the initial fact F. R is frontier-one (fr1) if |fr(R)| = 1. R is frontier-guarded (fg) if there is a ∈ body(R) with vars(fr(R)) ⊆ vars(a). R is weaklyfrontier guarded (wfg) if there is a ∈ body(R) that contains all affected variables from fr(R).

3 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 (F0 = F), . . . , Fk is said to be greedy if, for all i with 0 ≤ i < k, there is j < i such that πi(fr(Ri)) ⊆ vars(Aj) ∪ vars(F0) ∪ C, where Aj = π safe j (head(Rj)).

Example 2. Let R = {R0, R1} where: R0 = r1(x, y) → r2(y, z) and R1 = r1(x, y), r2(x, z), r2(y, t) → r2(z, t).

Let F0 = {r1(a, b), r1(b, c)} and S = F0, . . . , F3 with F1 = α(F0, R0, {(y, b)}), A0 = {r2(b, x1)}, F2 = α(F1, R0, {(y, c)}), A1 = {r2(c, x2)}, F3 = α(F2, R1, π2), with π2 = {(z, x1), (t, x2)}; there is no Aj s.t. {π2(z), π2(t)} ⊆ terms(Aj), 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 x0 with terms(x0) = vars(F) ∪ C and atoms(x0) = atoms(F), and ∀0 ≤ i < k, we add a node xi+1 with terms(xi+1) = vars(Ai+1) ∪ vars(F) ∪ C and atoms(xi+1) = atoms(Ai+1). Since S is greedy, there is at least a j such that πi(fr(Ri)) ⊆ terms(xj). We add an edge between xi+1 and xj ′ , j ′ being the smallest having this property. The nodes of DT(S ) are also called "bags".

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

2 We assume that the reader is familiar with this notion.

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 be a rule from a wfg rule set R and let g be a weak frontier guard of R. If R is applied by π and let π(g) = a, then a ∈ F or a ∈ Ai for some i. Thus R is gbts. □

Note that gbts strictly contains wfg. Indeed, {R} is gbts, but not wfg (nor fes), with R = r1(x, y), r2(y, z) → r(x, x ′ ), r(y, y ′ ), r(z, z ′ ), r1(x ′ , y ′ ), r2(y ′ , z ′ ).

4 An algorithm for gbts

Greediness ensures that, at each step of a derivation, the current derivation tree can be extended to a bounded-width tree decomposition of any to-be-derived fact. It follows that rule applications create only a bounded number of "relevant patterns". When we have created all possible patterns, "largeenough" to map Q, we can halt the derivation process. In [Cal`ı et al., 2009], 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 an oracle. Sets of oracles generalize types. To simplify the presentation, we translate Q into a rule RQ = Q → match where match is a fresh nullary predicate (note that fr(RQ) is empty). The question is now R ∪ {RQ} |= match.

Definition 6 (Ultimate applicability, oracle) Let F be a fact, R be a set of gbts rules, and S = F0(= F), . . . , Fi+1 be an R-derivation of F (with Fj+1 = Fj ∪ Aj, ∀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 F0(= F), . . . , Fj, . . . , Fi+1, . . . , Fl with a homomorphism π from body(R) to Fl and π(fr(R)) ⊆ vars(Aj) ∪ vars(F) ∪ C. We say that π|fr(R) is an oracle for the ultimate applicability of R on xj. An ultimate R-derivation is a sequence F0, . . . , Fk 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 Fi = α(Fi-1, R, π|fr(R)).

Any derivation is an ultimate derivation and an ultimate derivation F0, F1, . . . , Fk can always be extended to a derivation F0, F 1 0 , . . . , F i1 0 , F ′ 1 , . . . , F ′ k-1 , F 1 k-1 , . . . , F ik k-1 , F ′ k , where F ′ i contains Fi.

We now define an equivalence relation ∼Q on the bags of the derivation tree with the following informal meaning: xi ∼Q xj means that a rule body can be ultimately mapped in xi iff if can be mapped similarly in xj.

Definition 7 (∼Q) Let T be a derivation tree, x and y two bags of T. x ∼Q y if 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 of 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. Second, ∼Q allows to prune the ultimate derivation tree. 3

Theorem 4 Ultimate Saturation is sound and complete for CQ entailment with R gbts.

Proof: (sketch). Without the ∼Q check, soundness and completeness would follow from the correspondence between standard and ultimate derivations. To prove that the pruning performed by the ∼Q check does not prevent completeness, we show that: "if x ∼Q y and x parent of x ′ , then there is a child y ′ of y s.t. x ′ ∼Q y ′ ". We first build y ′ = copy x←y (x ′ ) the node obtained from y "as x ′ is obtained from x". Obviously x ′′ = copy y←x (y ′ ) ∼Q x ′ . It remains to prove that if π is an oracle of R = (B, H) on x ′ , then it is also an oracle of R on y ′ . For that, we generalize the copy notion: instead of copying a child of a node x under a ∼Q equivalent node y, we copy a whole subtree of x under y. We point out that if π is an oracle of R on x ′ (and not on x), then there is a finite subtree Tx ′ rooted in x ′ s.t. B is mapped to the fact associated with a minimal derivation generating Tx ′ . Finally, we show that B is also mapped to the fact associated with a minimal derivation generating the copy of Tx ′ rooted in the ∼Q equivalent node y. The proof is by induction on the depth of Tx ′ . □

Let us focus on the complexity of Algorithm 1. If Tmax denotes the maximum number of non-equivalent nodes that can be generated, the complexity of Algorithm 1 is O(Tmax × |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(|terms(body(Ri))|), b = |terms(F)| + maxi(|terms(head(Ri))|) + |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 ).

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

Proof: See [Baget et al., 2011].

□

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

Theorem 6 CQ entailment for gbts is in 3ExpTime for combined complexity, 2ExpTime-complete for predicate with bounded arity and ExpTime-complete for data complexity.

5 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 [Cal`ı et al., 2008].

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. However, this partial grounding produces a worst-case exponential blow-up in the number of nonaffected variables per rule. We thus provide a way to simulate partial groundings with only polynomial blow-up.

Let nav(R) denote the non-affected variables in R ∈ R. For convenience, we fix bijections #R : nav(R) → {1, ..., |nav(R)|} which for every R, assign numbers to all the non-affected variables. Now let v1, . . . , vm and v ′ 1 , . . . , v ′ s be variable symbols not used in R, where m = |C| and s = maxR∈R |nav(R)|. We now define the function τ, mapping rules from R to fgrules as follows: For terms t, let τR(t) = v ′ #R(t) if t ∈ nav(R) and τR(t) = t otherwise. We extend τR to atoms by letting τR ( p(t1, ..., tl) ) = p(v1, ..., vm, v ′ 1 , ..., v ′ s , τR(t1), ..., τR(tl)), which is lifted to sets of atoms in the usual way. Finally, for a rule R : body(R) → head(R), we let τ(R) = τR(B) → τR(H)

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 c1, . . . , cm and the next s positions will serve as a pool for special non-affected variables which will be used for our implicit grounding. Now we let τ(R) := {τ(R) | R ∈ R} ∪ S, where S contains for every predicate p ∈ P (let its arity be l) the rules S p ci ↦ →v ′ j

p(v1, .., vm, v ′ 1 , .., v ′ s , x1, .., xl) → p(v1, .., vm, v ∗ 1 , .., v ∗ s , x1, .., xl) where v ∗ j = vi and v ∗ k = v ′ k for all k nequal j. Thereby, the rule S ci ↦ →v ′ j is used to realize the bindings of the constant ci to the non-affected variable v ′ j . Now let τ(F) = {τ ′ (a) | a ∈ F} and τ(Q) = {τ ′ (a) | a ∈ Q} where

Note that the choice of c1 at positions m + 1, . . . ,m + s is just an arbitrary one; the rules from S allow to "put" any combination of constants at these positions. We have arrived at a translation that suits our needs.

Theorem 7 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. It is easy to check that, given F, R (wfg) and Q, we have that F, R |= Q iff τ(F), τ(R) |= τ(Q). □

6 Frontier-Guarded and Frontier-One Rules

In this section, we show that fg- and fr1-rules are both PTimecomplete for data complexity and 2ExpTime-complete for combined complexity no matter whether predicate arity is bounded or not. B´ar´any et al. (2010) showed 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 8 CQ entailment for fg-rules is in 2ExpTime.

Proof: We observe that every fg-rule R can be translated into two rules one of which is guarded and the other is Datalog. Given the frontier guard p(t1, . . . , tn) ∈ body(R), we introduce a new n-ary predicate pR and let separate(R) be the set containing the two rules SR : body(R) → pR(t1, . . . , tn) and TR : pR(ti, . . . , tn) → head(R). It is immediate that for any fg-rule set R, we have F, R |= Q exactly if F, ⋃ R∈R separate(R) |= Q.

Obviously, TR is guarded (and hence also lies in GF). Now we transform SR as follows (abbreviating (t1, . . . , tn) by t and vars(body(R)) by x as well as introducing a new predicate p ′ R ):

Hence F, R |= Q iff

where the first two sets are in GF and the third consists of negated existentially quantified conjuncts. Hence we can conceive every S ′ R as a negated CQ ¬QR. Consequently we have

which allows to rephrase (†) as

leaving us with a GF theory on the lhs and a union of boolean CQ on the rhs. This translation is clearly linear. □

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 Lutz (2007).

Theorem 9 CQ entailment for fr1-rules with bounded predicate arity is 2ExpTime-hard.

Proof: (Sketch) We show that Lutz' knowledge base representation of the halting problem for exponentially space-bounded alternating Turing machines can be expressed by fr1-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 [Kr¨otzsch et al., 2007] thus enabling to formulate acceptance for existential states without disjunction; (2) each negated concept ¬A is replaced by a concept B defined to be disjoint with A, which is possible because the tertium non datur part of the negation is not needed; (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. We obtain a CQ entailment problem w.r.t. a set of fr1-rules with at most binary predicates which encodes the halting problem, therefore showing the claim. □

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.

Lemma 1 For every constant-free fg-rule set R there exists a natural number wR satisfying the following: Suppose F, R |= a for some F and an atom a = p(z1, . . . , zl) with terms(a) ⊆ terms(F) and suppose that the corresponding derivation F = F0, . . . , Fk is such that for every atom a ′ with a ′ ∈ Fk-1 and terms(a ′ ) ⊆ terms(F) holds a ′ ∈ F. Then there is a set V ⊆ terms(F) with |V| ≤ wR such that F|V, R |= a where F|V := {b | b ∈ F, terms(b) ⊆ V}.

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 8 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. 4 We lift the function ξA to conjuncts and rules in the obvious way. Now, letting PGA(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 ′ ∈ PGA(R), R ∈ R ∪ {Q → match} }

Lemma 2 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.

Relying on Lemma 1 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 9 Given a constant-free fg-rule set R, we define the Datalog-program P(R) as follows: Let {y1, . . . , ywR } be a set of variable symbols. Let G denote the finite set of all atoms with predicates from R and terms from {y1, . . . , ywR }.

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

Now let P(R) be the set of Datalog rules containing every ∀y1, . . . , ywR (B → h) (with B ⊆ G and h ∈ G) for which B, R |= h.

Then coupling constant removal and the preceding Datalog translation, we can establish the following proposition, which gives rise to the expected theorem.

Lemma 3 For a set R of fg rules holds F, R |= Q iff ξA(F), P(cfree(R, Q)) |= match.

Theorem 10 CQ entailment for fg- and fr1-rules is PTimecomplete for data complexity.

Proof: Thanks to Lemma 3, we have reduced the problem to atom entailment in Datalog. Noting that P(cfree(R, Q)) 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 [Dantsin et al., 2001]. PTime-hardness for data complexity is a direct consequence of the same result for propositional Horn logic. □

Tree-like structures often lead to lower complexity. Hence, let us focus on fg-rules with an acyclic body (ba), in the sense that the hypergraph associated with their body is acyclic. 5 First, note that guarded rules are trivially bafg-rules. In turn, a KB with ba-fg-rules can be polynomially translated into a KB with guarded rules while preserving the predicate arity. 6 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). Concerning bafr1-rules, PTime-complete data complexity follows from the proof of Th. 10; about combined complexity, ExpTimehardness with bounded arity (thus with unbounded arity too) follows from the fact that standard reasoning in the weaker DL fragment Horn-FLE is already ExpTime-hard [Kr¨otzsch et al., 2007]; 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 ExpTime membership for the constant-free variant, but not for the general case.

7 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. We conjecture that the latter problem is decidable, however it can be shown that it is at least 2ExpTimehard. 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.

5 A hypergraph is acyclic if each of its connected components can be decomposed into a "join tree" (classical notion); we slightly generalize this notion by ignoring constants in hyperedge intersections.

6 Due to space restriction, this translation cannot be detailed. It relies on the join tree decomposition of each rule body.

Acknowledgments. Sebastian Rudolph was supported by the ExpresST project funded by the German Research Foundation (DFG), as well as by LIRMM (Montpellier, France).