Oblivious and Semi-Oblivious Boundedness for Existential Rules

1 Introduction

We consider the setting of ontology-based query answering (OBQA) in which answers to conjunctive queries are logically entailed from a knowledge base constituted of a set of facts and an ontology. Existential rules, also known as Tuple Generating Dependencies (TGDs) in database theory, are an expressive knowledge representation language well studied in the OBQA setting [Cal`ı et al., 2009; Baget et al., 2011; Cal`ı et al., 2013]. These rules generalize function-free Horn rules (like those of datalog) with existentially quantified variables in the rule heads, which allow one to assert the existence of unknown individuals, and hence to reason in open domains. Beside datalog, existential rules generalize the Semantic Web language RDF Schema, as well as most Description Logics used in the OBQA context, namely Horn description logics, in particular those at the core of the tractable profiles of the ontological language OWL 2.

The two main approaches developed to answer conjunctive queries on existential rules knowledge bases are materialization and query rewriting. Both can be seen as ways of reducing query answering to a classical database query evaluation problem. Materialization relies on a forward chaining technique, called the chase, that consists in expanding the factbase with the facts entailed by rules until fixpoint. In contrast, query rewriting is a backward chaining mechanism that consists in rewriting an input query using relevant rules, so that its answers on the knowledge base are exactly the answers of the rewritten query on the factbase alone. Query answering being undecidable for existential rules, both materialization and query rewriting may not terminate.

This led to intensive research aiming at characterizing decidable and tractable classes of existential rules. Several syntactic restrictions were proposed to ensure chase termination (e.g. weak-acyclicity [Fagin et al., 2005]) or the existence of a (finite) first-order rewriting of a conjunctive query, a property referred as FO-rewritability [Calvanese et al., 2007]. Nevertheless, the interactions between chase termination and FO-rewritability have been little investigated so far, and not much is known for existential rules on which both hold. What are the relationships between these two properties?

Answering this question leads us to another fundamental problem, which has been extensively studied for datalog, namely (uniform) boundedness [Hillebrand et al., 1995]. Boundedness concerns the recursivity of rules, and asks whether there is an upper bound on the depth of the chase, which is independent from any factbase. The property is key for practical optimization of reasoning as it implies that the ruleset is essentially non-recursive (although syntactic conditions may fail to capture this). It is known that boundedness and FO-rewritability are equivalent in the case of datalog [Ajtai and Gurevich, 1994], but this does not hold for existential rules. Moreover, in the setting of existential rules, the notion of boundedness also depends on the considered chase variant as every chase behaves differently with respect to termination.

We focus our attention on the oblivious and semi-oblivious (a.k.a. Skolem) chase [Marnette, 2009]. As a matter of fact, almost all known sufficient conditions for chase termination fall within these chase variants (from the simplest ones: richacyclicity [Hernich and Schweikardt, 2007], weak-acyclicity [Fagin et al., 2005] and acyclic-GRD [Baget et al., 2011] to the more general MFA [Grau et al., 2013]), at the exception of the recent work of [Carral et al., 2017] which applies to the restricted chase variant. Importantly, we consider a breadthfirst version for both variants, which ensures the minimal depth of the chase [Delivorias et al., 2018].

Our main contribution is a characterization of boundedness in terms of chase termination and FO-rewritability. This means that a set of rules is bounded if and only if it ensures both chase termination for any instance and FO-rewritability for any conjunctive query. We show this by proving two orthogonal results. The first is a bound on the depth of existential variables when the chase terminates on all instances. The second is a bound on the (breadth-first) rank at which facts using terms of a given depth are inferred.

This connection reveals important differences between the two variants. For the oblivious case we show that, when chase termination holds, FO-rewritability on full-atomic queries (queries with a single atom and only answer variables) is equivalent with FO-rewritability. Moreover, for the case of fully-existential rules (rules where all head atoms have at least one existential variable), we show that chase termination is equivalent to boundedness and so it implies FO-rewritability. None of these properties hold for the semi-oblivious chase.

Recognizing if a set of existential rules is bounded is undecidable already for datalog [Hillebrand et al., 1995]. However, we show the decidability of the problem for major classes of existential rules as direct corollaries of our characterizations and existing results from the literature. Precisely, the problem is PSpace-complete for linear and sticky rules and in 2Exptime for guarded rules. Finally, we consider the k-boundedness problem (i.e., whether the chase terminates in k steps on all instances), which was recently proven decidable for several chase variants, including those investigated here [Delivorias et al., 2018]. We show that deciding if a ruleset is k-bounded is in 2Exptime for the breadth-first (semi-) oblivious chase and co-NExptime-complete for datalog.

2 Preliminary Definitions

We consider a relational vocabulary V = (P, C) constituted of a finite set of predicates P and a finite set of constants C. A term v is a constant of C or a variable. An atom is of the form p(v1 . . . vk) where p is a predicate of arity k and the vi are terms. We denote by terms() the set of its terms and extend the notation to sets of atoms. An embedding ϕ from a set of atoms A to a set of atoms A′ is a substitution of terms(A) with terms(A′ ) such that ϕ(A) ⊆ A′ . A homomorphism is an embedding which is the identity on constants.

An instance I is a conjunction of atoms on constants and (globally) existentially quantified variables. It is finite unless otherwise specified. Throughout this paper, we see an instance I as the set of its atoms and call fact any atom f that belongs to this set. Given a finite set P of predicates, the critical instance Ia is composed of all facts built on P and special constant a. Any instance I on P can be embedded into Ia.

An existential rule σ is a closed formula ∀¯x¯ y(B[¯x, ¯ y] → ∃¯ zH[¯x, ¯ z] where B and H are sets of atoms built on variables called the body and the head of the rule, also denoted by body(σ) and head(σ) respectively. The set of variables ¯x shared by B and H is called the frontier of the rule and is denoted by fr(σ). The set of variables ¯ z that belong to H only are called existential variables and are denoted by ex(σ). Universal quantifiers will often be omitted in the remainder of the paper. A rule such that ex(σ) = ∅ is called datalog. A rule where all head atoms contain at least one existential variable is called fully-existential and denoted by FE-rule. We say that a rule σ is applicable on an instance I if there is a homomorphism π from body(σ) to I and call the pair (σ, π) a trigger of I. Given a trigger (σ, π), we denote by π|fr(σ) ⊆ π the restriction of π to fr(σ).

A knowledge base (KB) is a pair (I,Σ) where I is an instance and Σ a set of existential rules. The chase is a fundamental tool for computing logical consequences from a KB

since, when it terminates, it computes a universal model of the KB, i.e., a model that maps by homomorphism to any other model of the KB (with a model being seen here as an instance). In this work, we focus our attention on the breadthfirst oblivious (o-chase) and semi-oblivious (so-chase) variants. As discussed in Section 3.3, the breadth-first behavior is particularly interesting when studying boundedness.

Definition 1. Let (I, Σ) be a knowledge base and ⋆ ∈ {o, so} a chase variant. Then, the breadth-first ⋆-chase is defined as follows: ⋆-chase0 (I, Σ) = I and for all saturation rank i ≥ 0

where (σ, π) is any trigger of ⋆-chasei (I,Σ) and π⋆ ⊇ π a substitution that replaces each existential variable z ∈ ex(σ) with a fresh variable named as follows:

• πo(z) = z(σ,π)
• πso(z) = z(σ,π|fr(σ))

Then, we define ⋆-chase(I,Σ) = ⋃∞i≥0 ⋆-chasei (I,Σ). The ⋆-chase terminates on (I,Σ) if there is a rank k with ⋆-chase(I , Σ) = ⋆-chasek (I , Σ).

Note that for the o-chase fresh variables are named by the trigger fromwhich they have been generated. Instead, for the so-chase the naming only depends on the frontier-restriction of the homomorphism of the trigger. This means that any two triggers having the same rule and agreeing on the image of its frontier variables produce equal results, hence only one of them is actually considered by the so-chase. The so-chase is very close to the Skolem chase, which relies on a skolemisation of the rules: first, each rule σ is transformed by replacing each occurrence of an existential variable z with a functional term f σ z (fr(σ)) on the frontier of σ; then the o-chase is run on the skolemised rules. At each saturation rank, the Skolem chase produces a result isomorphic to that of the so-chase (up to the renaming of each Skolem term by the corresponding fresh variable), hence the forthcoming results on the so-chase also hold for the Skolem chase.

Example 1. Consider the rule σ = p(x, y) → ∃z p(x, z). Then o-chase(I, Σ) with I = {p(a, b)} and Σ = {σ} is infinite - as the chase does not terminate. The atom p(a, z(σ,π1)) with π1 = {x ↦→ a, y ↦→ b} is first inferred, then p(a, z(σ,π2)) with π2 = {x ↦→ a, y ↦→ z(σ,π1)}, and so on. Here, each rule application enables a new trigger. In contrast, so-chase(I, Σ) is finite, in that only the first rule application will be performed, producing p(a, z(σ,{x↦→a})), since all triggers map the frontier variable x to a. For the Skolem chase, σ is rewritten as σ′ = p(x, y) → p(x, f σ z (x)). The first rule application according to trigger (σ′ , π1) produces p(a, f σ z (a)), then the chase halts as the same atom is produced by the next trigger.

Definition 2. The rank of a fact f ∈ ⋆-chase(I,Σ), denoted by rank(f), is 0 if f ∈ I and 1 +max{rank(f ′ )|f ′ ∈ π(body(σ))} if f is produced by the trigger (σ, π). This definition is naturally extended to terms and sets of facts. The rank of ⋆-chase(I, Σ) is the smallest k such that ⋆-chase(I, Σ) = ⋆-chasek (I, Σ) if ⋆-chase(I, Σ) terminates, and it is infinite otherwise.

Note that for the breadth-first chases we consider the above definition implies that rank(f) is the smallest k such that f ∈ ⋆-chasek (I, Σ) \ ⋆-chasek-1 (I, Σ).

An FO-query φ(x1, ..., xn) is a (function free) first-order formula whose free variables (called answer variables) are exactly {x1, ..., xn}. A conjunctive query (CQ) is an FO-query which is an existentially quantified conjunction of atoms. An atomic query is a CQ with a single atom. A full-atomic query is an atomic query where all terms are free variables. A query is called Boolean if it does not have any free variable. As for instances, it will be handful to see CQs as sets of atoms, of course by distinguishing the answer variables. A union of conjunctive queries (UCQ) Q is a disjunction of CQs with the same free variables, also seen as a set of CQs.

A tuple of constants (a1, ..., an) ∈ C n is an answer to a CQ Q(x1, ..., xn) on an instance I if there is a homomorphism h from Q to I such that h(xi) = ai for 1 ≤ i ≤ n. Equivalently, I |= Q[xi ↦→ ai], where |= denotes the classical logical consequence and Q[xi ↦→ ai] is the Boolean query obtained from Q substituting each xi with ai. A tuple of constants (a1, ..., an) ∈ C n is a certain answer to Q on a KB (I,Σ) if I,Σ |= Q[xi ↦→ ai]. This is equivalent to the existence of a saturation rank k such that ⋆-chasek (I,Σ) |= Q[xi ↦→ ai]. In other words, the certain answers to Q on (I, Σ) are exactly its answers on the possibly infinite instance ⋆-chase(I, Σ). The set of (certain) answers to a UCQ Q is the union of the sets of (certain) answers to the CQs it contains.

2.1 Termination vs Boundedness

To begin our study, we need to present the relationships between chase termination and boundedness. Let ⋆ ∈ {o, so} be a chase variant, the ⋆-chase termination class, denoted by CT⋆ , contains all rulesets Σ such that ⋆-chase(I,Σ) terminates for all instances I. The ⋆-boundedness class, denoted by BN⋆ , contains all bounded rulesets Σ, i.e., for which there exists an integer k such that ⋆-chasek (I, Σ) = ⋆-chase(I, Σ) for all instances I . Obviously, BN⋆ ⊂ CT⋆ .

Example 2. Let σ1 = p(x, y) ∧ p(y, z) → p(x, z) and σ2 = p(x, y) ∧ p(w, z) → p(x, z). Because both rules are datalog, {σ1} ∈ CT⋆ and {σ2} ∈ CT⋆ . However, Σ = {σ1} ̸∈ BN⋆ , since the rank of ⋆-chase(I,Σ) depends on I. In contrast, {σ2} ∈ BN⋆ and the bound is k = 1. Similarly, {σ1, σ2} ∈ BN⋆ . Indeed, σ2 produces at the first rank all atoms that can be produced by σ1 at later ranks.

To get a better understanding of boundedness, it will be useful to decompose each rule of a set thereby distinguishing between its "datalog part" and its "existential part". For instance, a rule of the form p(x, y) → ∃z p(x, z) ∧ q(x) can be decomposed into a datalog rule p(x, y) → q(x) and an FErule p(x, y) → ∃z p(x, z). Let σ be any existential rule of the form B → HF ∧ HD where B is the set of body atoms, HF is the set of head atoms with at least one existential variable and HD are the remaining head atoms. The datalog-fully existential decomposition of σ, denoted by DF(σ), returns a set made of the FE-rule B → HF together with a (single head) datalog rule of the form B → HiD , for each HiD ∈ HD. The definition is then extended to sets DF(Σ) = ⋃σ∈Σ DF(σ). This decomposition preserves boundedness and termination.

Proposition 1. Σ ∈ CT⋆ iff DF(Σ) ∈ CT⋆ and Σ ∈ BN⋆ iff DF(Σ) ∈ BN⋆ , when ⋆ ∈ {o, so}.

3 Upper Bounding the Chase Depth

Our approach consists of defining a notion of existential depth for facts, proper to each chase, which is finite on a given instance if and only if the chase terminates on that instance. Then we show that for each chase, the existential depth of all facts produced by the chase for a given ruleset are bounded by those of the critical instance. This means that whenever the chase terminates on the critical instance there is an upper bound to the existential depth of the facts, for all instances. In the next section, with these results in hand, we use FOrewritability to bound the rank at which any fact of a certain existential depth will be inferred. This will give us a characterization of boundedness for the oblivious and so-chase in terms of FO-rewritability and chase termination.

3.1 The Oblivious Case

Intuitively, the notion of existential depth of a termmeasures the number of fresh variable generation steps that led to the creation of this term.

Definition 3. The existential depth (or simply depth) of a term v that belongs to o-chase(I, Σ) is

where vB is any term in π(body(σ)) used by a trigger (σ, π) which generates v. The existential depth of a fact f is the maximum existential depth of its terms. The existential depth of o-chase(I,Σ) is the maximum existential depth of its facts if it is finite and is infinite otherwise.

To illustrate the definition, consider Example 1. The existential depth of terms in o-chase(I, {σ}) is unbounded, which is in line with the non-termination of the o-chase on (I, {σ}). The rule σ1 in Example 2. shows the difference between rank and existential depth. For any I, the existential depth of terms (hence facts) is 0 because σ1 is datalog, however their rank depends on I. More generally, for any term v and fact f in o-chase(I,Σ) it holds that depth∃(v) ≤ rank(v) and depth∃(f) ≤ rank(f). Hence, if o-chase(I,Σ) terminates, its existential depth is finite. Reciprocally, when the existential depth of o-chase(I, Σ) is finite, so it is the number of its terms, and o-chase(I,Σ) terminates. We point out that when dealing with sets of FE-rules the notions of rank and existential depth coincide, as illustrated by Example 1.

Proposition 2. If Σ is a set of FE-rules then, for all instance I and term v in o-chase(I, Σ), holds that depth∃(v) = rank(v).

It should be clear that, for a given ruleset, the o-chase may have unbounded rank even when it terminates on all instances (see for instance Example 2). Nevertheless, when a ruleset is in CT o , our goal is to show that there exists a bound on the existential depth of its terms, which holds for all instances. Aiming at this, we present a lemma stating that existential depth of terms are preserved by embeddings.

Lemma 3. For any embedding ϕ from I to I ′ and any i ≥ 0, there exists an embedding ϕ′ ⊇ ϕ from o-chasei (I, Σ) to o-chasei (I ′ ,Σ) which preserves the existential depth of terms, i.e., for every term v in o-chase(I,Σ) it holds that depth∃(v) = depth∃(ϕ′ (v)).

It is well-known that the o-chase terminates on all instances if and only if it terminates on the critical instance [Marnette, 2009]. We leverage this property to compute a bound on the existential depth under chase termination.

Theorem 4. When Σ ∈ CT o there exists a constant kd such that for every instance I, the existential depth of a term in o-chase(I, Σ) is bounded by kd.

Proof. Because Σ ∈ CT o , the o-chase terminates on the critical instance Ia. Let kd be the largest rank such that terms(o-chasekd (Ia,Σ)) \ terms(o-chasekd-1 (Ia,Σ)) ̸= ∅. Every instance I can be embedded into Ia. By Lemma 3 the existential depth of the terms in o-chase(I, Σ) is bounded by that of o-chase(Ia, Σ), which is in turn bounded by kd.

Chase termination is a necessary condition for boundedness as it bounds the existential depths of the variables generated by the chase - but not the rank (see the datalog case). Interestingly, for FE-rules, chase termination also becomes a sufficient condition for boundedness, because the notion of rank and existential depth coincide (Proposition 2).

For general existential rules, we will later show that when a restricted form of FO-rewritability holds, one can also provide a bound to the rank of the o-chase (Theorem 14).

3.2 The Semi-Oblivious Case

When applied to the so-chase, the previous notion of existential depth is not preserved by embedding, which hinders the possibility of using the critical instance to bound the existential depth of terms. As illustrated below, this is due to the fact that the so-chase makes equal the result of two distinct triggers agreeing on a rule frontier.

Example 3. Consider I = {p(a, b)}, I ′ = I ∪ {r(a, b)} and Σ = {σ1 : p(x, y) → ∃z r(z, y) σ2 : r(x, y) → ∃z s(y, z)}. Then, so-chase2 (I, Σ) = I ∪ { r(z(σ1,π), b) ∪ s(b, z(σ2,π)) } with π = {y ↦→ b}. Also, so-chase2 (I, Σ) ⊆ so-chase1 (I ′ , Σ) because all triggers applied by the chase from I are already applicable on I ′ . The application of σ2 on r(a, b) and r(z(σ1,π), b) gives equal results, hence so-chase1 (I ′ ,Σ) = so-chase2 (I ′ ,Σ). In the embeddings from so-chase2 (I,Σ) to so-chase2 (I ′ ,Σ), z(σ2,π) is mapped to itself, but both occurrences have different existential depth (resp. 2 and 1).

It is therefore natural to turn to the following notion of depth, which accounts for frontier terms only.

Definition 4. The frontier existential depth (or simply frontier depth) of a term v that belongs to so-chase(I, Σ) is

where vB is any term in π(fr(σ)) used by a trigger (σ, π) which generates v. Accordingly, the frontier depth of a fact f is the maximum frontier depth of its terms. The frontier depth of so-chase(I, Σ) is defined as the maximum frontier depth of its facts if it is finite and is infinite otherwise.

Note that frontier depth coincides with the (usual) depth of terms generated by the Skolem chase.

Clearly, depth fr ∃ (v) ≤ depth∃(v) for all v in o-chase(I, Σ). The following example illustrates the difference between the two notions of (existential) depth.

Example 4. Let Σ = {σ = p(x, y, u) → ∃z p(y, x, z)}. Starting from I = {p(a, b, c)}, the o-chase generates an infinite number of fresh variables v with increasing depth∃(v). The rank of the so-chase is instead 2 and for each fresh variable v, depth fr ∃ (v) = 1 as all triggers map fr(σ) to terms(I).

It is worth noting that not only the oblivious notion of exitential depth is not effective for studying the so-chase, but also that the frontier depth is not well characterizing the behavior of the o-chase either. The crux is that the finiteness of the frontier depth cannot be related with the termination of the o-chase, as illustrated by Example 4. Using such a notion to study the o-chase would impede us, for instance, to establish Corollary 5, which relies on the fact that rank and existential depth coincide for the oblivious-chase (Property 2).

We are now ready to show that the frontier depth is preserved by embeddings. The next lemma and theorem are the counter-parts of Lemma 3 and Theorem 4 for the so-chase.

Lemma 6. For any embedding ϕ from I to I ′ and any i ≥ 0, there exists an embedding ϕ′ ⊇ ϕ from so-chasei (I,Σ) to so-chasei (I ′ , Σ) which preserves the frontier depth of terms.

Theorem 7. When Σ ∈ CT so there exists a constant kd such that for every instance I, the frontier depth of a term in so-chase(I, Σ) is bounded by kd.

3.3 On the Interest of the Breadth-First Chase

We conclude this section with some remarks on the interest of studying boundedness for breadth-first chases. We assume that the reader is familiar with the notion of chase sequence. 1 We define the rank of a chase sequence on (I, Σ) as the maximal rank of its facts if it is finite, and infinite otherwise.

For the (semi-)oblivious chase, it is well-known that there is a terminating chase sequence for (I,Σ) if and only if all chase sequences for (I, Σ) terminate. However, not all terminating chase sequences have the same rank, and the minimal rank is obtained with breadth-first sequences [Delivorias et al., 2018]. This makes the notion of boundedness we consider equivalent to studying whether there exists a bound such that, for all instance, there exists a terminating chasing sequence whose rank is within the bound. Hence, it characterizes the fact that the chase can indeed terminate within that bound, if a strategy ensuring a minimal sequence rank is followed.

1 A chase sequence is any sequence of triggers satisfying the applicability criterion of the chase variant. For the oblivious chase, the same trigger should not be applied twice. For the semi-oblivious chase a trigger is not applied if a trigger for the same rule assigning the same image for the frontier variables has been applied before.

It is therefore natural to consider breadth-first chases which achieve this property, like the (semi-)oblivious chase. Example 2 illustrates this concept and shows that, already for datalog, the rank of some chase sequences may be not bounded, while the rank of all breadth-first sequences is bounded. This happens for instance if all applications of the transitivity rule σ2 are performed before the rule σ1.

In the special case of FE-rules, it is not hard to see that all oblivious chase sequences for (I,Σ) have the same rank. However, this does not hold for the semi-oblivious chase. Below, a variation of Example 2, where some dummy variables are introduced, illustrates this point.

Example 5. Let Σ = {σ1, σ2}, with σ1 = p(x, y, t) ∧ p(y, z, u) → ∃v p(x, z, v) and σ2 = p(x, y, t)∧p(w, z, u) → ∃v p(x, z, v). The rank of so-chase(I, Σ) is bounded by 2 for any I, while again performing all applications of σ2 before σ1 gives derivations of different ranks.

4 The Impact of First Order Rewritability

We now turn our attention to FO-rewritability and show that it yields a bound on the rank of specific (sets of) facts that share terms with the initial instance I. For the o-chase, we bound the rank of facts that have all their terms in I. For the so-chase, we consider triggers that map a rule frontier to terms of I: we do not bound the rank of facts that allow to fire such triggers, but we show that for each such trigger t = (σ, π), there is a trigger t′ = (σ, π′ ) that agrees with t on the mapping of fr(σ) and that is fired at a bounded rank. In Section 5, we will leverage these results to show that FOrewritability yields a bound on the rank of all facts with a certain existential depth. For the o-chase, a restricted version of FO-rewritability is sufficient to get these properties.

We say that a pair (Q,Σ) is FO-rewritable (resp. UCQrewritable) if there is an FO-query (resp. a UCQ) Q such that, for all I, the certain answers to Q on (I,Σ) are exactly the answers to Q on I. It is known that FO-rewritability is equivalent to UCQ-rewritability 2 . A set of rules Σ is FOrewritable (or equivalently, UCQ-rewritable) if (Q, Σ) is FOrewritable for every CQ Q. We denote by FO-R the class of FO-rewritable rulesets. We will also consider specific classes of CQs. Given a class of CQs C, we say that a ruleset Σ is FO-rewritable with respect to C if (Q,Σ) is FO-rewritable for all Q ∈ C. We denote by FO-RC the corresponding class. We first point out that FO-rewritability with respect to fullatomic queries, denoted by FO-R AF , is a strictly weaker property than FO-rewritability.

Proposition 8. FO-R AF ⊃ FO-R

Proof. The inclusion holds by definition, and to see that it is strict consider Σ = {σ = p(x, x1), p(x1, x2), p(x2, z) → ∃y p(x, y), p(y, z)}. Σ is not FO-rewritable as for the Boolean query Q = {p(a, u), p(u, b)}, where a and b are constants, (Q,Σ) is not FO-rewritable (we would need an infinite union of Boolean CQs of the form {p(a, u0), ...p(ui-1, ui), p(ui, b)}, none of these queries being contained in another). However, Σ ∈ FO-R AF as (Q,Σ)

2 It follows from the Homomorphism preservation theorem, a classical result in model theory.

is FO-rewritable for any Q ∈ AF . Indeed, σ cannot bring any answer to such query (in more technical terms, an existential variable of σ cannot be unified with an answer variable).

Note also that since full-atomic queries have only answer variables, they cannot be rewritten by means of FE-rules. Thus, every set of FE-rules is trivially in FO-R AF . More interestingly, to check if Σ ∈ FO-R AF one can restrict the fullatomic queries of interest to those corresponding to the heads of the datalog rules yielded by the DF-decomposition of Σ.

Proposition 9. Let Σ be a ruleset and HDΣ be the full-atomic queries given by heads of the datalog rules in DF(Σ). Then, Σ ∈ FO-R AF if and only if Σ ∈ FO-R HDΣ .

The following lemma upper bounds the rank of all facts with terms in I for sets of rules enjoying FO-rewritability on full-atomic queries.

Lemma 10. If Σ ∈ FO-R AF there is a constant kAF such that, for any instance I and fact f such that terms(f) ⊆ terms(I), when f ∈ o-chase(I, Σ) it holds that rank(f) ≤ kAF.

Proof. The number of (non-isomorphic) full-atomic queries to be considered is finite, as for Proposition 9. We take for kAF the maximal number of breadth-first rewriting steps necessary to obtain a UCQ-rewriting of a full-atomic query (we refer here to the breadth-first rewriting based on aggregated piece-unifiers, see [K¨onig et al., 2013]).

The previous lemma also holds for the so-chase, however we want to derive a bound on the rank of facts with a certain frontier depth, and for that full-atomic rewritability is not enough. To illustrate, consider Σ = {σ = p(x, y, u), p(y, z, v) → ∃w p(x, z, w)}. Here Σ ∈ FO-R AF (the only rewriting of a full-atomic query is the query itself because of the existential variable w). For any instance I, the frontier depth of facts in the so-chase is bounded by 1, however there is no bound on their rank (although the so-chase terminates). Therefore, we give a different property for the so-chase, which requires the power of FO-rewritability.

Lemma 11. If Σ ∈ FO-R there is a constant kFO such that, for any instance I and any trigger (σ, π) from so-chase(I, Σ) with π(fr(σ)) ⊆ terms(I), there is also a trigger (σ, π′ ) from so-chase(I, Σ) such that π′ |fr(σ) = π|fr(σ) and rank(f) ≤ kFO for all f ∈ π′ (body(σ)).

Proof. Similar to the proof of Lemma 10 but considering CQs of the form Qbody(σ) whose atoms correspond to the atoms of body(σ), for σ ∈ Σ, and all variables are existentially quantified except for those in fr(σ). The number of such queries is bounded by the cardinal of Σ. We take for kFO the maximal number of breadth-first rewriting steps necessary to obtain a UCQ-rewriting from any Qbody(σ) query. The proof actually shows that FO-rewritability with respect to rule body queries is sufficient to derive the lemma.

5 Boundedness: Linking Depth and Rank

We can finally establish a connection between the rank and depth of a fact when the chase is run on FO-rewritable sets of rules. This will immediately lead us to a characterization of boundedness for the oblivious and semi-oblivious chases.

Theorem 12. If Σ ∈ FO-R AF then for all instance I and fact f ∈ o-chase(I, Σ) we have that rank(f) ≤ depth∃(f) × (kAF + 1) + kAF with kAF the bound provided by Lemma 10.

Theorem 13. If Σ ∈ FO-R then for all instance I and fact f ∈ so-chase(I,Σ) we have that rank(f) ≤ depth fr ∃ (f) × (kFO + 1) + kFO with kFO the bound provided by Lemma 11.

For the o-chase, boundedness is exactly termination and FO-rewritability on full-atomic queries. Furthermore, for rulesets in CT o , the notions of FO-R and FO-R AF coincide.

Proof. We start by showing that BN o ⊆ FO-R ∩ CT o . By definition BN o ⊆ CT o . Then, BN o ⊆ FO-R follows from the equivalence between FO-R and the bounded-depth derivation property [Gottlob et al., 2014]. Moreover, by Proposition 8 we have BN o ⊆ FO-R AF ∩ CT o . To conclude the proof, by Theorem 4 and 12 we have that FO-R AF ∩ CT o ⊆ BN o and again by Proposition 8 follows FO-R ∩ CT o ⊆ BN o .

For the so-chase, boundedness can be characterized again as termination and FO-rewritability by Theorem 7 and 13.

Summing up, we have the following differences between boundedness for o-chase and so-chase. o-chase-boundedness requires i) o-chase termination and full-atomic-rewritability and ii) is equivalent to o-chase termination for FE-rules. Intuitively, when a set of rules Σ is decomposed into DF(Σ), the fully-existential part may cause non-termination of the o-chase, while the datalog part may cause non-FOrewritability. Furthermore, the fully-atomic queries possibly leading to infinite rewritings in this case correspond to the heads of the datalog rules. Note however that this restricted form of FO-rewritability has still to be verified with respect to the whole set of rules. In contrast, so-chaseboundedness i) requires a stronger form of FO-rewritability and ii) FE-rules do not behave differently from general existential rules for this chase. Intuitively, for the so-chase, any existential rule (even an FE-rule) has an "underlying" datalog rule. This is illustrated by the following transformation. To each rule σ in Σ we assign a special predicate pσ of arity |fr(σ)|. Ψ(Σ) is obtained from Σ by replacing each rule σ = B → H with two rules: a datalog rule B → pσ(fr(σ)) and a rule pσ(fr(σ)) → H. It can be shown that Σ ∈ CT so iff Ψ(Σ) ∈ CT o and that Σ ∈ BN so iff Ψ(Σ) ∈ BN o . This may also provide an alternative path to study so-chase boundedness by reducing it to o-chase boundedness.

6 Decidability and Complexity

From the undecidability of (uniform) boundedness of datalog [Hillebrand et al., 1995], we immediately obtain the undecidability of membership to BN o and BN so . A notable class of datalog rules with decidable boundedness (more precisely in linear time) is chain datalog [Guessarian and Peixoto, 1994]. We obtain that membership to BN so , CT so and FO-R remains undecidable for FE-rules, while the decidability of membership to BN o , hence to CT o , is still open.

Importantly, new decidability and complexity results about boundedness for specific existential rules studied in the literature can be obtained as direct corollaries of our results. This is in particular the case for classes known to be FO-rewritable.

Corollary 16. For any class of existential rules C ∈ FO-R, it holds that: C ∈ BN o iff C ∈ CT o , and C ∈ BN so iff C ∈ CT so .

This implies that membership to BN o and BN so is PSpacecomplete for the two main classes of FO-rewritable existential rules, namely linear and sticky. Indeed, deciding CT o and CT so is PSpace-complete for both [Calautti et al., 2015; Calautti and Pieris, 2019]. We also get an upper bound on the complexity of membership to BN o and BN so for a major class of existential rules, namely guarded. This class is neither CT so nor FO-R. However, membership to CT o and CT so for guarded rules is decidable in 2Exptime [Calautti et al., 2015]. Then a careful reduction from [Barcel´o et al., 2018] allows us to set the result. The paper shows that checking FO-rewritability for a single query under guarded rules is in 2Exptime. This suffices since by Lemma 10 and 11 we need to test only a polynomial number of queries.

We conclude by considering the k-boundedness problem, which asks wether the chase actually halts within k steps. The problem is decidable for the breadth-first (semi-)oblivious chase and any set of existential rules [Delivorias et al., 2018]. Therefore, the k-boundedness question becomes interesting for dealing with fragments of existential rules where boundedness is undecidable. We study here the complexity of the following version of the problem. Given a ruleset Σ and a (unary encoded) integer k, does it hold that ⋆-chasek (I, Σ) = ⋆-chase(I,Σ) for all instance I?

Theorem 17. Deciding k-boundedness is in 2Exptime for existential rules for the o-chase and so-chase; coNExptime-complete for datalog rules; in co-NExptime on FErules for the o-chase.

Proof. (Sketch) The membership results rely on the decidability arguments from [Delivorias et al., 2018]. CoNExptime-hardness for datalog is by reduction from the coNExptime-hard inclusion problem of non-recursive Boolean datalog queries [Benedikt and Gottlob, 2010].

7 Outline and Perspectives

In this paper, we have characterized boundedness in terms of FO-rewritability and chase termination, for the oblivious and semi-oblivious chase variants. We conclude with a discussion on the extent of our results to more powerful chase variants (i.e., which terminate at least when the semi-oblivious chase terminate). Theorem 13 suggests that whenever Σ ∈ FO-R if any such chase generates only terms of bounded frontier depth on all instances, then Σ is bounded. We leave open the question to determine if for other chase variants, like the restricted and the core chases, boundedness is again the intersection of chase termination and FO-rewritability.

Acknowledgements

Work supported by ANR projects CQFD (ANR-18-CE230003), DataCert (ANR-15-CE39-0009), DeLTA (ANR-16CE40-0007) and CNRS-Momentum project Managing-Data.