--- title: "Answering Conjunctive Regular Path Queries over Guarded Existential Rules" authors: - "Jean-François Baget" - "Meghyn Bienvenu" - "Marie-Laure Mugnier" - "Michael Thomazo" doi: "10.24963/ijcai.2017/110" url: "https://ijcai.org/proceedings/2017/110" pdf: "https://ijcai.org/proceedings/2017/0110.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "793-799" track: "Main track" keywords: - "Knowledge Representation, Reasoning, and Logic: Logics for Knowledge Representation" - "Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning" - "Knowledge Representation, Reasoning, and Logic: Knowledge Representation Languages" --- # Answering Conjunctive Regular Path Queries over Guarded Existential Rules Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, Michael Thomazo *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 793-799. DOI: [10.24963/ijcai.2017/110](https://doi.org/10.24963/ijcai.2017/110) ## Abstract Ontology-mediated query answering is concerned with the problem of answering queries over knowledge bases consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries, navigational queries are gaining increasing attention. In this paper, we investigate the complexity of answering two-way conjunctive regular path queries (CRPQs) over knowledge bases whose ontology is given by a set of guarded existential rules. We first consider the subclass of linear existential rules and show that CRPQ answering is EXPTIME-complete in combined complexity and NL-complete in data complexity, matching the recently established bounds for answering non-conjunctive RPQs. For guarded rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of CRPQ answering is the same as for plain conjunctive queries, namely, 2EXPTIME-complete in combined complexity and PTIME-complete in data complexity. ## Full text ## 1 Introduction In ontology-mediated query answering (OMQA), a database is enriched with an ontological layer that expresses domain knowledge, and queries are answered by taking into account the information from both the data and ontology. Two main families of ontology languages are considered in this setting, namely description logics (DLs) and existential rules (see e.g. the survey chapters [Ortiz and Simkus, 2012; Kontchakov et al., 2013; Bienvenu and Ortiz, 2015] on OMQA with DLs and [Calì et al., 2009a; Mugnier and Thomazo, 2014] for existential rules). Although most work on OMQA to date has focused on the fundamental class of conjunctive queries (CQs), navigational queries are gaining increasing attention. The simplest such queries are regular path queries (RPQs, [Florescu et al., 1998]), which ask for paths defined by a given regular language, hence allowing for a controlled form of recursion over binary predicates. Many extensions of RPQs have been considered, including conjunctive regular path queries (CRPQs) which generalize both RPQs and CQs. In particular, SPARQL 1.1, the new W3C standard for querying RDF data, ## Marie-Laure Mugnier Univ. Montpellier, France mugnier@lirmm.fr Michael Thomazo Inria, France michael.thomazo@inria.fr extends its core queries, which roughly correspond to CQs, to CRPQs. In recent years, such queries have been investigated for a variety of description logics, ranging from highly expressive DLs of the Z family [Calvanese et al., 2007; 2009; 2014], to Horn DLs like Horn-SROIQ [Ortiz et al., 2011] and lightweight DLs of the DL-Lite and EL families [Stefanoni et al., 2014; Bienvenu et al., 2015]. When the data are not only graphs, as in RDF and DL fact bases, but more generally hypergraphs, or, in logical terms, sets of facts with any predicate arity, navigational queries are still very relevant as binary relations remain central in data and ontological modeling. While the complexity landscape for answering navigational queries in the presence of DL ontologies is now quite clear, the combination of navigational queries and existential rules has only just recently begun to be explored. In [Bienvenu and Thomazo, 2016], the authors studied the complexity of RPQ answering over linear existential rules, a natural generalization of DL-LiteR. It was shown that the problem complexity remains the same as for DL-LiteR in terms of data complexity (NL-complete) and combined complexity with bounded predicate arity (PTIMEcomplete). However, in the unbounded arity case, the combined complexity rises to EXPTIME-complete. Interestingly, in DL-LiteR, RPQ answering is easier than CQ answering for combined complexity (P- vs. NP-complete [Bienvenu et al., 2015]), while the opposite holds for linear rules without arity restriction (CQ answering being PSPACE-complete [Calì et al., 2009a]). In this paper, we make a step towards a better understanding of the complexity of answering CRPQs over existential rule bases, focusing on a central class of existential rules, namely guarded rules, of which linear rules are a special case [Calì et al., 2008; 2009b]. Note that the problem is already known to be decidable (from [Rudolph and Krötzsch, 2013]). Summary of the contributions. We obtain tight complexity results for both combined and data complexities over guarded rules and their linear subclass. Namely, CRPQ answering in the linear case is EXPTIME-complete in combined complexity, PSPACE-complete in combined complexity with bounded arity and NL-complete in data complexity (Thm 1); hence, it is not more difficult than RPQ answering, except for combined complexity with bounded arity (in which case the complexity is again the same as for DL-LiteR). In the guarded case, CRPQ answering is 2EXPTIME-complete in combined complexity, EXPTIME-complete in combined complexity with bounded arity, and PTIME-complete in data complexity (Thm 2); hence, it is not more difficult than plain CQ answering. To achieve these results, we first investigate the case of linear rules and provide a CRPQ answering algorithm that uses RPQ answering as an oracle and runs within the mentioned complexity classes. The matching lower bounds come from earlier results on RPQ and CQ answering. We next provide a non-trivial reduction of the guarded case to the linear case. This translation involves a double exponential blow-up of the rule base (while the instance only grows exponentially in the predicate arity). However, a careful analysis of the algorithm provided for linear rules shows that it actually runs in 2EXPTIME with respect to the input guarded knowledge base (and in EXPTIME in the case of bounded-arity rules). ## 2 Preliminaries We consider a vocabulary composed of a finite set of predicates and an infinite set of constants. A (standard) atom α has the form r(t) where r is a predicate of arity n and t is a tuple of terms (i.e., variables or constants) with |t| = n. For 1 ≤ i ≤ |t|, we denote by α[i] the term at position i in α. We denote by terms(α) the set of terms in α and extend the notation to a set of atoms. A ground atom contains only constants. An instance is a finite set of facts, which are grounds atoms. A conjunctive query (CQ) has the form q(x) = ∃y.B where x and y are disjoint tuples of variables, and B is a conjunction of atoms such that terms(B) = x ∪ y. A tuple of constants a = π(x), where π denotes a substitution, is a certain answer to q(x) over I if I |= q(a), where q(a) = ∃y.π(B) and |= denotes classical logical entailment. A CQ is Boolean if x = ∅. We often identify (the existential closure of) a conjunction of atoms with the set of these atoms. Given two sets of atoms A and B, a homomorphism from B to A is a substitution π of the variables in B by the terms in A such that π(B) ⊆ A. It holds that A |= B iff there is a homomorphism from B to A. Given a (possibly infinite) set of atoms A and a set of terms T, A|T denotes the subset of A containing the atoms whose arguments are a subset of T . Existential Rules An existential rule (or simply rule) is of the form ∀x∀y.[B(x, y) → ∃z.H(y, z)] where B and H are non-empty conjunctions of atoms on variables, respectively called the body and the head of the rule, and x, y and z are pairwise disjoint. The variables of z are called existential variables. For brevity, quantifiers are often omitted, and we write B → H. We will make the classical assumption that the head of a rule is restricted to a single atom. A set of atoms G is guarded if it contains an atom α (called a guard) such that terms(α) = terms(G). Since G may have several guards, we use the notation (G, α) to specify that α is the considered guard. A rule is guarded if its body is guarded. A rule is linear if its body contains a single atom. A knowledge base (KB) is of the formK = (I,R), where I is an instance and R a set of existential rules. Let K = (I,R) be a KB and q(x) be a CQ. A certain answer to q over K is a tuple of constants a such that I, R |= q(a). A rule R = B → α is applicable to a set of atoms A if there is a homomorphism π from B to A. The result of the application of R on A according to π is the atom πs (α), where πs extends π by assigning a distinct fresh variable (called a null) to each existential variable. The application is said to generate the set of atoms A ∪ πs (α), which is uniquely defined up to the choice of nulls. The chase is the fundamental tool on existential rules. Starting from the instance, it performs rule applications in a breadth-first manner. Several variants of the chase are known. We consider here the simplest variant, known as the oblivious chase, which at each breadth-first step performs all new rule applications, and proceeds until no rule is applicable according to a new homomorphism. All the chase variants compute a so-called universal model of the KB, i.e., a possibly infinite set of facts seen as a classical logical interpretation, which is a model of the KB that maps by homomorphism to any other model of the KB. The result of the chase is also called chase. It follows that for any K = (I,R) and CQ q, (I,R) |= q iff the chase of K is a model of q iff there is a homomorphism from q to the chase of K. (Conjunctive) Regular Path Queries A regular language can be represented either by a regular expression or by a nondeterministic finite automaton (NFA). Let Σ be a finite set of symbols. A regular expression E over Σ is defined by the grammar: E → ε | a | E · E | E + E | E ∗ , where a ∈ Σ and ε denotes the empty word. An NFA over Σ is a tuple A = (S,Σ, δ, s0, F), where S is a finite set of states, δ ⊆ S ×Σ×S is the transition relation, s0 ∈ S is the initial state and F ⊆ S is the set of final states. We denote by P2 the binary predicates in our vocabulary and set P ± 2 = P2 ∪ {r- | r ∈ P2}. A path atom takes the form Λ(t, t′ ), where Λ is a regular language over P ± 2 and t, t′ are terms. Note that standard atoms with binary predicates are a special case of path atoms. We assume w.l.o.g. that automata associated with distinct path atoms have disjoint sets of states. A conjunctive two-way regular path query (CRPQ 1 ) has the form q(x) = ∃y.B and is defined as a CQ except that B is a conjunction of standard and path atoms. We extend the usual definition of an interpretation I = (∆, .I ) being a model of a conjunction of atoms by saying that, for a regular language Λ, (d, d′ ) ∈ ΛI if there are r1 . . . rn ∈ Λ and (d = d0, . . . , dn = d′ ) ∈ ∆n+1 such that ∀1 ≤ i ≤ n, if ri ∈ P2 then (di-1, di) ∈ rI i , otherwise ri = s-i and (di, di-1) ∈ sIi . We call p = d0r1d1 · · · rndn a path in I. A match for a Boolean CRPQ q in an interpretation I = (∆, .I ) is a mapping π from the terms in q to elements of ∆ such that (i) π(a) = aI for each constant a; (ii) π(t) ∈ rI for each standard atom r(t) in q; and (ii) (π(t), π(t′ )) ∈ ΛI for each path atom Λ(t, t′ ) in q. Note that the restriction of π to the standard atoms of q is a homomorphism. Then I is a model of q if and only if there is a match for q in I. Certain answers are defined in the same way as for CQs. Since the chase of K = (I,R) is a universal model, and CRPQs are closed by homomorphism, I,R |= q if and only if there is a match π of q in the chase of K. A path of terms in the chase is the natural translation of a path in an interpretation. 1 As we only consider the two-way variant, we will use the abbreviation (C)RPQ instead of the more traditional (C)2RPQ. The CRPQ Answering problem asks, given a KB K = (I,R), a CRPQ q(x) and a tuple of constants a whether a is an answer to q w.r.t. K. The CRPQ Entailment problem asks, given a KB K = (I,R) and a Boolean CRPQ q, if I,R |= q. Both problems are classically polynomially reducible one to another. To simplify the presentation, we will study the CRPQ Entailment problem. ## 3 Chase Graph of Linear Rules With the chase is naturally associated a derivation graph, in which nodes are labelled by atoms and edges represent rule applications, i.e., there is an edge (ν, ν ′ ) if the application of a rule to the atom that labels ν has produced the atom that labels ν ′ . In the case of linear rules, this graph is a forest. Several derivation graphs can be associated with the same chase, since the same atom may be produced in different ways. However, in our proofs we need to be independent from a particular graph and to have an edge (ν, ν ′ ) if and only if a rule application to the atom that labels ν can produce the atom that labels ν ′ . Hence, we will consider a particular graph that encodes all derivations associated with a given chase. This graph is still a forest. Definition 1 Let I be an instance and R be a set of linear rules. The chase graph associated with (I,R), denoted by CG(I,R) (and simply CG if the context is clear), is a possibly infinite node-labeled directed forest built as follows (we use ℓ for the labeling function): - the roots are in bijection with I via ℓ; - for every node ν and rule R ∈ R applicable to ℓ(ν), there is exactly one edge from ν to a node ν ′ labeled by the atom resulting from this rule application. Note that an atom can label two distinct nodes, effectively encoding two different ways of generating that same atom. Given (I,R), the chase graph is uniquely defined, up to the choice of nulls. We formally define the chase as the set of all atoms that label CG(I,R). We denote it by chase(I,R). We can now express a fundamental property of linear rules: each atom from the instance can be 'chased' independently. Property 1 Let R be a set of linear rules and I be an instance. Then chase(I, R) = ∪α∈I chase({α}, R). For ν and ν ′ in the same tree of CG, glb(ν, ν ′ ) denotes their greatest lower bound (i.e., their deepest common ancestor). An essential property of the chase graph is that, for any null z, the nodes labeled by the atoms that contain z form a connected component. This is also true for the initial terms inside each tree. In the next proposition, to distinguish between undirected paths in CG and the previously introduced paths (on terms in the chase), we call the former atom-paths. Proposition 1 (Connectivity property) Let ν1 and ν2 be two nodes of CG(I, R) and t ∈ terms(ℓ(ν1)) ∩ terms(ℓ(ν2)). Then: Figure 1: Part of CG(Ie,Re) ![Image](https://ijcai.org/proceedings/2017/fulltext/110/image_000000_37163b5ad005daa09228f5030739cacd3125d47ac820cd2e9aadf658da0eb20f.png) - either t is contained in I and there are atom-paths P1 from ν1 to a root ν ′1 and P2 from ν2 to a root ν ′2 such that for every node ν ∈ P1 ∪ P2, ℓ(ν) contains t; - or there is an atom-path P from ν1 to ν2, and it is such that for every node ν ∈ P, ℓ(ν) contains t. The next proposition specifies the relationships between a path in the chase and an atom-path in the chase graph. It strongly relies on the connectivity property. Proposition 2 Let ν1 and ν2 be two nodes in CG under a common root. Let p = t1 . . . tp be a path in the chase such that t1 occurs in ℓ(ν1) and tp occurs in ℓ(ν2). Then for any node ν on the atom-path from ν1 to ν2 in CG, ℓ(ν) contains a term ti from p. Example 1 Let Re contain the following rules: Part of CG(Ie = {b(a1, a2, a3, a4), t(a1)},Re) is represented in Fig. 1. For clarity, we represent directly the atoms that label nodes (here, the labeling is injective). The terms ai are constants while the terms zi are nulls. Let us consider the following path of terms in the chase: p = a4 n z1 n z2 r a3 s a2 r a1. We can see that the structure associated with p has no direct connection with the structure of the chase graph. However, Prop. 2 allows us to make a connection: if we take any pair of nodes ν1 and ν2 labeled by atoms that respectively contain a4 and a1, we can see that along the atom-path between ν1 and ν2 all the nodes contain at least a term from p. Now, consider the following Boolean CRPQ q (existential quantifiers omitted): There is a match of q to the partial chase: x1 ↦→ a1, x2 ↦→ a2, x3 ↦→ a3, x4 ↦→ a4, x5 ↦→ a1. Note that (n∗ (rsr)∗ )(x4, x5) is mapped to the path p. The atoms of the chase graph involved in this match are underlined. ## 4 CRPQEntailment over Linear Rules In this section, we describe a method for CRPQ entailment in the presence of linear rules, which allows us to pinpoint the worst-case complexity of this problem. Throughout this section, we let I be an instance, R a set of linear rules, and q be the Boolean CRPQ we wish to answer. As it will be important to keep track of the paths in the chase that link the terms of a pair of atoms, we define the set of transitions between two atoms. Definition 2 Let α1 and α2 be two atoms of chase(I,R) of arities k1 and k2 respectively. The transitions from α1 to α2, denoted by Tq,I,R(α1, α2), is the set of quadruples (i1, s1, i2, s2) such that 1 ≤ i1 ≤ k1, 1 ≤ i2 ≤ k2, and there exists an automaton A in q and a path p in chase(I, R) going from α1[i1] to α2[i2] such that λ(p) takes A from s1 to s2. More generally, by transition, we will mean a quadruple (i1, s1, i2, s2) where s1, s2 are states appearing in q, and i1, i2 do not exceed the maximum predicate arity in I ∪ R. We now introduce the key technical notion underlying our approach, namely, proof schemes. Formally, a proof scheme is a directed forest whose nodes are atoms, together with transitions for different pairs of atoms occurring in the proof scheme. Intuitively, proof schemes correspond to a subset of chase atoms, with the transitions placing requirements on the paths linking these atoms. Definition 3 A proof scheme is a pair P = (F, T ) such that: - F = (V, E) is a directed forest; - V is a set of atoms; - for each null n, the set of nodes in which n occurs form a connected subgraph of F; - T is a set of pairs (τ, (α1, α2)), where τ is a transition, α1 and α2 belong to V ; - for each (τ, (α1, α2)) ∈ T , either α1 = α2, (α1, α2) ∈ E, (α2, α1) ∈ E, or both α1 and α2 are roots. The terms of a proof scheme, denoted by terms(P), is the union of all the terms of atoms in V . We next define valid proof schemes. The validity conditions enforce that the proof scheme behaves as intended: its atoms can be mapped into the chase graph in a way that respects the forest structure, and the transitions in the proof scheme are indeed realized in the chase. Note that valid proof schemes are not far, in essence, from the proof generators used in [Gottlob et al., 2015] for deciding CQ entailment in linear rule KBs; however, the presence of transitions and their interactions with linear rules make the validity check much more complex. The idea is to consider the following bruteforce algorithm for CRPQ answering: enumerate all proof schemes, check whether the considered proof scheme is valid w.r.t I,R and q and whether there is a 'match' of q in the proof scheme. To obtain our complexity results, we will upper bound the size of the proof schemes that need to be considered and the complexity of the validity check. To formalize the notion of a valid proof scheme, we need the classical notion of the type of an atom, as well as the notion of isomorphic atoms with respect to a bijection, which allows us to identify atoms that 'act the same'. Definition 4 The type of an atom r(t1 . . . tk) is the pair (r, P) where P is the partition of {1, . . . , k} induced by term equality (i.e., i and j are in the same class of P iff ti = tj). Definition 5 Two atoms α1 and α2 are isomorphic with respect to a bijection b from a set of terms T1 to a set of terms T2 if they have the same type (r, P) and, for any class C of P, if α1[C] ∈ T1 then α2[C] = b(α1[C]), otherwise α2[C] ̸∈ T2, and α1[C] and α2[C] are both nulls. Definition 6 A proof scheme P = (F, T ) with F = (V, E) is valid w.r.t. (I, R, q) if there is an injective mapping w from terms(P) to terms(chase(I,R)) such that: - for each root atom α ∈ V , w(α) = α and α ∈ I; - for each atom α ∈ V , w(α) belongs to chase(I,R); - for each atom α ∈ V , α and w(α) are isomorphic with respect to the identity function on terms(I); - for each edge (α1, α2), it holds that: - α2 and w(α2) are isomorphic with respect to the bijection b from terms(α1) to terms(w(α1)) induced by their common type; - CG(I,R) contains nodes ν1, ν2 such that ν1 ≺ ν2, ℓ(ν1) = w(α1), ℓ(ν2) = w(α2). - for each (τ, (α1, α2)) ∈ T : τ ∈ Tq,I,R(w(α1), w(α2)). In a proof scheme, transitions label pairs of atoms (α1, α2) such that α1 = α2, or both atoms are roots, or one is the parent of the other in a tree. Saturation builds all the transitions that can be obtained by composing these transitions: Definition 7 Let P=(F, T ) be a proof scheme. The saturation of T is the smallest set T ′ such that T ⊆ T ′ and {((i1, s1, i2, s2), (α1, α2)), ((i2, s2, i3, s3), (α2, α3))} ⊆ T ′ implies ((i1, s1, i3, s3), (α1, α3)) ∈ T ′ . After saturating the transitions of P, one may not keep a proof scheme as new transititions may label any pair of atoms, however if P is valid, the validity conditions remain satisfied. We next define the notion of a match of a query in a proof scheme to formalize what it means for a query to be mapped into the part of the chase represented by a valid proof scheme. Definition 8 Let P = (F, T ) be a proof scheme with F = (V,E). We say that there is a match of q in P if there is a mapping π from vars(q) to terms(P) such that: - if α is a standard atom in q, then π(α) ∈ V ; - if α = Λ(x, y) is a path atom in q with associated NFA A, then there is a pair ((ix, s, iy, f), (αx, αy)) in the saturation of T such that π(x) = αx[ix], π(y) = αy[iy] and s (resp. f) is an initial (resp. final) state of A. Note that the problem of deciding if there is a match from given q in given P is NP-complete. The next proposition shows that CRPQ answering reduces to the existence of a match in a valid proof scheme. Proposition 3 I,R |= q if and only if there exists a match of q in some valid proof scheme. Proof Sketch: Suppose I, R |= q, and let π′ be a match of q in chase(I, R). Let V1 be the set of images of the standard atoms of q, as well as the atoms in which the image of the terms of q has been created. Let V ′ 1 contain for each α ∈ V1 a node να ∈ CG such that ℓ(να) = α. Define V ′ 2 = V ′ 1 ∪{glb(ν, ν ′ )}, where the union is performed over all (ν, ν ′ ) ∈ V ′ 1 ×V ′ 1 such that ν and ν ′ have the same root in CG. Let F be the forest structure induced by CG over V ′ 2 . We define V as {ℓ(ν) | ν ∈ V ′ 2 }, and E as the pairs (ℓ(ν), ℓ(ν ′ )) for any edge (ν, ν ′ ) in F. We then define T as the transitions from α1 to α2 such that one is the child of the other, or both are roots, or α1 = α2. One can check that π′ is a match of q in P = ((V,E), T ). The main argument is as follows: by Prop. 2, the saturation of P contains all the transitions that hold between an atom and its descendants. As the glb of any two nodes with the same root also belongs to F, the saturation of P also contains all the transitions that hold between any pair of atoms of P. As the mapping of standard atoms is direct, π′ is a match of q in P. The converse direction follows from the definitions. □ Importantly, the size of the valid proof scheme built in the previous proof is polynomial in the size of q, so it is only necessary to consider polynomial-size proof schemes. It remains to show how to test whether a given proof scheme is valid. We will make use of the following lemma, which shows how transitions between an atom in the chase graph and an ancestor atom can be computed using the transitions relating its parent atom to the same ancestor, together with the transitions that can be obtained by considering the atom in isolation. Lemma 1 Suppose ν2 is a descendant of ν1 in CG(I,R), ν3 is a child of ν2, and αi = ℓ(νi) for 1 ≤ i ≤ 3. Then: 1. (i1, s1, i3, s3) ∈ Tq,I,R(α1, α3) iff there exist (i1, s1, i2, s2) ∈ Tq,I,R(α1, α2) and (i′2 , s2, i3, s3) ∈ Tq,{α3},R(α3, α3) such that α2[i2] = α3[i′2 ] 2. (i1, s1, i3, s3) ∈ Tq,I,R(α3, α1) iff there exist (i1, s1, i′2 , s2) ∈ Tq,{α3},R(α3, α3) and (i2, s2, i3, s3) ∈ Tq,I,R(α2, α1) such that α2[i2] = α3[i′2 ] 3. (i1, s1, i4, s4) ∈ Tq,I,R(α3, α3) iff there exist (i1, s1, i′2 , s2) ∈ Tq,{α3},R(α3, α3), (i2, s2, i3, s3) ∈ Tq,I,R(α2, α2), and (i′3 , s3, i4, s4) ∈ Tq,I,R(α3, α3) such that α3[i′2 ] = α2[i2] and α3[i′3 ] = α2[i3] We now exploit this lemma and existing complexity results on RPQ answering to design a procedure for checking validity of a proof scheme, with the following complexity: Proposition 4 Checking the validity of a proof scheme can be done in single exponential time, in polynomial space if predicate arity is bounded, and in NL if q and R are fixed. Proof Sketch: First observe that if α, α′ are root atoms of P, we can compute Tq,I,R(α, α′ ) by calling an RPQ entailment oracle. We then work from the roots to the leaves, guessing for each edge (α1, α2) in P, a sequence of rule applications that take α1 to α2, which ensures the satisfaction of the fourth validity condition. Importantly, we can bound the length of this sequence by noticing that after exponentially many rule applications, we will have generated two atoms β1, β2 that 'behave the same' (roughly: they are isomorphic w.r.t. terms(α1) and have the same transitions w.r.t. α1 and w.r.t. themselves). To check the fifth validity condition, we leverage Lemma 1 to inductively construct the set of transitions between α1 and α2, and between α2 and itself. Note that we can directly compute Tq,{α2},R(α2, α2) using RPQ entailment. The procedure we have sketched runs in nondeterministic polynomial space (constant space if q and R are fixed) with access to an RPQ entailment oracle. It then suffices to recall that RPQ entailment is in EXPTIME, in P for bounded-arity rules, and in NL if q and R are fixed. □ Since all polysize proof schemes can be enumerated in polynomial space, by Prop. 4 we obtain that the brute-force algorithm runs in EXPTIME in the general case, in PSPACE if the arity is bounded, and in NL if q and R are fixed (in which case the number of proof schemes and their size are constants, and checking the existence of a match is in constant time). Matching lower bounds are inherited from RPQ answering with linear rules [Bienvenu and Thomazo, 2016], or CRPQ answering in DL-LiteR [Bienvenu et al., 2015]. Theorem 1 CRPQ entailment under linear rules is EXPTIME-complete in combined complexity, PSPACEcomplete in combined complexity with bounded-predicate arity, and NL-complete in data complexity. ## 5 Extension to Guarded Rules We reduce CRPQ answering under guarded rules to CRPQ answering under linear rules. For simplicity, we assume that all the predicates in I also occur in R (however, the reduction is easily extended to drop this restriction). We first explain the ideas that underly the reduction. Prop. 1, which states that, under linear rules, facts can be chased independently, fails for guarded rules. However, a kind of independence can be recovered if instead of single fact we consider the (maximal) subset of the chase guarded by this fact, as expressed by Prop. 5, which also applies to non-necessarily ground atoms. Proposition 5 For any set of atoms F, it holds that chase(F,R) is equivalent to ⋃α∈F chase(F ∗ α ,R), where F ∗ α = chase(F, R)|terms(α). By recursively using Prop. 5, one can devise the following alternative chase procedure. Let F = I; (i) Compute F ∗ the restriction of chase(F,R) to terms(F); this can be done by calling an oracle for each candidate atom on terms(F) to decide if it is entailed by chase(F,R); (ii) For each α ∈ F ∗ and G the maximal subset of F ∗ guarded by α (i.e., G = F ∗ α ), for each rule ρ ∈ R, let π be the homomorphism from body(ρ) to G that maps the guard of ρ to α: (ii-1) apply ρ to G by π and let Gρ,π be the restriction of the generated set to the subset guarded by πs (head(ρ)); (ii-2) Perform steps (i) and (ii) with F = Gρ,π; (iii) The chase is the union of all the F ∗ built at Step (i). Now, let (I,R) be the original KB, where R is a set of guarded rules, and (I ′ ,R′ ) be the translated KB, where R′ is a set of linear rules. Roughly, the reduction allows to simulate the alternative chase outlined above, with the translation being as follows: (i) we build I ′ from (I,R) by replacing each α ∈ I by an atom that represents chase(I,R)|terms(α) and, (ii) we build R′ by replacing each rule ρ ∈ R by a set of linear rules, each representing an application of ρ to a distinct guarded subset of chase(I, R). This construction will require new predicates associated with guarded sets of atoms. We will show that chase(I,R) and chase(I ′ ,R′ ) are homomorphically equivalent when restricted to the original predicates, which implies that chase(I ′ ,R′ ) can be used to answer CRPQs as these are closed under homomorphism. To obtain a finite number of guarded sets (hence a finite set of new predicates, which will ensure the finiteness of the set of rules R′ ), we have to rename them in a canonical way. To that end, we consider a new set of canonical variables X = {T1, . . . , T2w}, where w is the maximal predicate arity (2w will be the maximal number of terms in a rule fromR′ ). Definition 9 Let α be an atom which may contain both classical terms and canonical variables. The canonical renaming Φα,Y of α w.r.t Y ⊆ X is a substitution from terms(α) to X such that Φα,Y(ti) = ti if ti ∈ X, otherwise Φα,Y(ti) = Tj where j is the smallest integer such that Tj ̸∈ Y, Tj does not occur in α, and Tj ̸= Φα,Y(tk) for all k < i. If Y = ∅, we simply write Φα. We denote by G the set of guarded atoms over canonical variables. Note that G is finite. For any guarded set (G, α), it holds that (Φα(G), Φα(α)) ∈ G. To each guarded set (G, α) in chase(I,R) can be assigned a complex predicate, of the form pΦα(G) with the same arity as α. As G is finite, so is the set of complex predicates. The canonical atom associated with a guarded set (G, α) is can(G, α) = pΦα(G)(terms(α)). Definition 10 The guarded translation of I w.r.t. R is I ′ = {can(G(α, I,R)) | α ∈ I}, where G(α, I,R) denotes the guarded set (chase(I, R)|terms(α), α). Example 2 Consider Ex. 1, where Ie = {α1, α2}, with α1 = b(a1, a2, a3, a4) and α2 = t(a1). In the following, we underline the guard in a guarded set. G(α2, Ie,Re) = {t(a1)}, hence can(G(α2, Ie,Re)) = p{t(T1)}(a1). G(α1, Ie,Re) = {b(a1, a2, a3, a4), r(a4, a1), r(a2, a1), s(a3, a2), n(a3, a4), r(a4, a3)}, hence can(G(α1, Ie, Re)) = pG′ (a1, a2, a3, a4), where G′ is obtained by a canonical renaming of G(α1, Ie,Re) (here, each ai is simply replaced by Ti). The set R′ is composed of two kinds of linear rules: rules that rebuild atoms on the original vocabulary (reconstruction rules) and rules that simulate the chase (complex rules). Definition 11 Let (G, α) ∈ G. The set of reconstruction rules associated with (G, α) contains for each β ∈ G the (range-restricted) rule of the form can(G, α) → β. Definition 12 Let (G, α) ∈ G and ρ ∈ R be applicable to G by π. Let α′ = πs (head(ρ)) and Φα′ ,terms(α) be the canonical renaming of α′ w.r.t. terms(α). The complex rule associated with G, ρ and π is: can(G, α) → can(G′ , Φα′ ,terms(α)(α′ )) where G′ = Φα′ ,terms(α)(chase(G ∪ {α′ }, R)|terms(α′ )). Example 3 Consider Re from Ex. 1 and G = {b(T1, T2, T3, T4), p(T1)} a guarded set in G. The rule b(x, y, z, t) → h(y, z, t, u) is applicable to G through π = {x ↦→ T1, y ↦→ T2, z ↦→ T3, t ↦→ T4}. Hence, we build the complex rule p{b(T1,T2,T3,T4),p(T1)}(T1, T2, T3, T4) → pG′(T2, T3, T4, T5), where G′ = {h(T2, T3, T4, T5), n(T3, T4),n(T4, T5), s(T3, T2),r(T4, T3), s(T5, T4)}. We finally obtain R′ = Rr ∪ Rc, where Rr (resp Rc) is the set of all reconstruction (resp. complex) rules. To prove the correctness of the reduction, we rely on the notion of the expansion of an atom. Definition 13 The expansion of a complex atom α is defined as expansion(α) = chase(α, Rr) \ α. The expansion of a set of complex atoms is the union of the expansions of its atoms. Observe that the expansion of chase(I ′ ,R′ ) is equal to its restriction to atoms with predicates in the original vocabulary. We thus focus on the correspondence between Rc and R. Lemma 2 Let (G, α = r(t)) be a guarded set of atoms. The following two statements hold: - let ρ ∈ R be applicable to G by π, and let F = G ∪ πs (head(ρ)). There exists a complex rule ρ′ applicable - to pΦα(G)(t) by π′ such that: expansion(pΦα(G)(t) ∪ π′s (head(ρ′ ))) |= F . - let ρ′ ∈ Rc be applicable to G′ = pΦα(G)(t) by π′ , and let F ′ = G′ ∪ π′s (head(ρ′ )). There exists ρ ∈ R applicable to G, generating F , such that: chase(G,R)|terms(F) |= expansion(F ′ ). Lemma 2 allows us to show that expansion(chase(I ′ , Rc)) ≡ chase(I , R). Proposition 6 Given (I,R), I ′ and R′ as defined above can be computed in 2EXPTIME in combined complexity, EXPTIME when the arity is bounded, and in PTIME in data complexity. The number of types whose predicate appears in R′ is at most a double exponential in I and R (exponential when the arity is bounded, and constant w.r.t. the data). The next theorem follows from the provided reduction and our results for linear rules. Let us remark that the reduction to linear rules not being polynomial, we do not directly obtain the desired upper bounds. However, by carefully analyzing the algorithm for linear rules, we can show that it actually runs polynomially in the number of types. Theorem 2 CRPQ entailment under guarded rules is 2EXPTIME-complete in combined complexity, EXPTIMEcomplete in combined complexity with bounded-predicate arity, and PTIME-complete in data complexity. ## 6 Conclusion We have made an important step in understanding the complexity of answering navigational queries over existential rules, by determining the precise complexity of answering CRPQs under linear and guarded rules, two central subclasses of existential rules. Our results are quite positive, as we showed that answering CRPQs under guarded rules is not harder than answering the more well-known CQs, under both combined complexity (with or without arity restrictions) and data complexity. For linear rules, we proved that moving from RPQs to CRPQs does not incur any additional computational cost, and for bounded-arity rules, we have the same complexity as for DL-LiteR. We believe that the simulation of guarded rules by linear rules is of independent interest. ## Acknowledgements We thank Swan Rocher for fruitful discussions. This work was supported by the French ANR project PAGODA (ANR12-JS02-0007). ## References 1. [Bienvenu and Ortiz, 2015] Meghyn Bienvenu and Mag- dalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Reasoning Web, pages 218-307, 2015. 2. [Bienvenu and Thomazo, 2016] Meghyn Bienvenu and Michaël Thomazo. On the complexity of evaluating regular path queries over linear existential rules. In Web Reasoning and Rule Systems -10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings, pages 1-17, 2016. 3. [Bienvenu et al., 2015] Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. Regular path queries in lightweight description logics: Complexity and algorithms. J. Artif. Intell. Res. (JAIR), 53:315-374, 2015. 4. [Calì et al., 2008] Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. In Proc. of KR, pages 70-80, 2008. 5. [Calì et al., 2009a] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. Datalog extensions for tractable query an- swering over ontologies. In Semantic Web Information Management -A Model-Based Perspective, pages 249- 279. 2009. 6. [Calì et al., 2009b] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general datalog-based framework for tractable query answering over ontologies. In Proc. of PODS, pages 77-86, 2009. 7. [Calvanese et al., 2007] Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Answering regular path queries in ex- pressive description logics: An automata-theoretic ap- proach. In Proc. of AAAI, pages 391-396, 2007. 8. [Calvanese et al., 2009] Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Regular path queries in expressive de- scription logics with nominals. In Proc. of IJCAI, pages 714-720, 2009. 9. [Calvanese et al., 2014] Diego Calvanese, Thomas Eiter, and Magdalena Ortiz. Answering regular path queries in ex- pressive description logics via alternating tree-automata. Inf. Comput., 237:12-55, 2014. 10. [Florescu et al., 1998] Daniela Florescu, Alon Levy, and Dan Suciu. Query containment for conjunctive queries with regular expressions. In Proc. of PODS, 1998. 11. [Gottlob et al., 2015] Georg Gottlob, Marco Manna, and An- dreas Pieris. Polynomial rewritings for linear existential rules. In Q. Yang and M. Wooldridge, editors, Proceed- ings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Ar- gentina, July 25-31, 2015, pages 2992-2998. AAAI Press, 2015. 12. [Kontchakov et al., 2013] Roman Kontchakov, Mariano Rodriguez-Muro, and Michael Zakharyaschev. Ontology- based data access with databases: A short course. In Reasoning Web, pages 194-229, 2013. [Mugnier and Thomazo, 2014] Marie-Laure Mugnier and Michaël Thomazo. An introduction to ontology-based query answering with existential rules. In Reasoning Web, pages 245-278, 2014. 13. [Ortiz and Simkus, 2012] Magdalena Ortiz and Mantas Simkus. Reasoning and query answering in description logics. In Reasoning Web, pages 1-53, 2012. 14. [Ortiz et al., 2011] Magdalena Ortiz, Sebastian Rudolph, and Mantas Šimkus. Query answering in the Horn frag- ments of the description logics SHOIQ and SROIQ. In Proc. of IJCAI, 2011. 15. [Rudolph and Krötzsch, 2013] Sebastian Rudolph and Markus Krötzsch. Flag & check: data access with monad- ically defined queries. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 -27, 2013, pages 151-162, 2013. 16. [Stefanoni et al., 2014] Giorgio Stefanoni, Boris Motik, Markus Krötzsch, and Sebastian Rudolph. The complex- ity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases. J. of Art. Intell. Res. (JAIR), 51:645-705, 2014.