Conjunctive Regular Path Queries in Lightweight Description Logics

1 Introduction

Recent years have seen a rapidly growing interest in using description logic (DL) ontologies to query instance data. In databases, similar attention has been paid to the related problem of querying graph databases which, like DL instance data, are sets of ground facts using only unary and binary predicates, i.e., node- and edge-labeled graphs [Consens and Mendelzon, 1990; Barcel´o et al., 2010]. The relevance of both problems lies in the fact that in many application areas, data can be naturally represented in such form. This applies, in particular, to XML and RDF data. While the DL and database communities share some common research goals, the research agendas they have pursued differ significantly. In DLs, the focus has been on designing efficient algorithms for answering (plain) conjunctive queries in the presence of ontological constraints. By contrast, work on graph databases typically does not consider ontological knowledge, but instead aims at supporting expressive query languages, like regular path queries (RPQs) and their extensions, which enable sophisticated navigation of paths. Such path navigation has long been considered crucial for querying data on the web. Indeed, it lies at the core of the XPath language for querying XML data, and of the property paths feature of SPARQL 1.1, the language recently recommended as the new standard for querying RDF data.

In this paper, we are interested in the problem of querying DL knowledge bases using various kinds of regular

Magdalena Ortiz and Mantas ˇSimkus

Institute of Information Systems Vienna University of Technology, Austria

path queries. We mainly focus on conjunctive (two-way) regular path queries (C(2)RPQs), which are one of the most expressive and popular languages for querying graph databases. CRPQs simultaneously extend plain conjunctive queries (CQs) and basic RPQs: they allow conjunctions of atoms that can share variables in arbitrary ways, where the atoms may contain regular expressions that navigate the arcs of the database (or roles, in DL parlance). In the case of 2RPQs and C2RPQs, roles can be navigated in both directions. C2RPQs have already been studied for DLs, but all existing results concern expressive DLs for which reasoning is provably intractable. In particular, algorithms have been proposed for ZIQ, ZIO, and ZOQ [Calvanese et al., 2007b; 2009], for which query answering is 2-EXPTIME hard. Even in data complexity, that is, when the query and ontology are assumed fixed, these algorithms need exponential time. More recently, algorithms for answering C2RPQs in HornSHOIQ and Horn-SROIQ were proposed [Ortiz et al., 2011]. These algorithms run in polynomial time in the size of the data, but still require exponential time in the size of the ontology. By contrast, to the best of our knowledge, path queries have not yet been considered for the lightweight DLs of the DL-Lite [Calvanese et al., 2007a] and EL [Baader et al., 2005] families, which underly the OWL 2 QL and EL profiles. This is surprising given that the low complexity of these DLs makes them better suited for data-intensive applications.

This paper aims to remedy this situation by providing algorithms and precise complexity bounds for answering (C)2RPQs in the EL and DL-Lite families of lightweight DLs. We show that in data complexity, the query answering problem for CR2PQs is NL-complete for DL-Lite and P-complete for EL, which in both cases is the lowest complexity that could be expected. For combined complexity, we prove PSPACE-completeness for both DL-Lite and EL, but somewhat surprisingly obtain a tractability result for 2RPQs for both DLs. All of our upper bounds apply to extensions of EL and DL-Lite with role inclusions. Full proofs of all results can be found in a technical report [Bienvenu et al., 2013].

2 Preliminaries

We briefly recall the syntax of DL-LiteR [Calvanese et al., 2007a] and ELH [Baader et al., 2005] (and relevant sublogics). As usual, we assume sets NC, NR, and NI of concept names, role names, and individuals. We will use NR to refer to NR ∪ {r- | r ∈ NR}, and if R ∈ NR, we use R- to mean r- if R = r and r if R = r-. An ABox is a set of assertions of the form A(b) or r(b, c), where A ∈ NC, r ∈ NR, and b, c ∈ NI. We use Ind(A) to refer to the set of individuals in A. A TBox is a set of inclusions, whose form depends on the DL in question. In DL-Lite, inclusions take the form B1 ⊑ (¬)B2, where each Bi is either A (where A ∈ NC) or ∃R (where R ∈ NR). DL-LiteR additionally allows role inclusions of the form R1 ⊑ (¬)R2, where R1,R2 ∈ NR. DL-LiteRDFS is obtained from DL-LiteR by disallowing inclusions which contain negation or have existential concepts (∃R) on the right-hand side. In EL, inclusions have the form C1 ⊑ C2, where C1,C2 are complex concepts constructed as follows: C := ⊤ | A | C ⊓ C | ∃r.C. The DL ELH additionally allows role inclusions of the form r ⊑ s, where r, s ∈ NR. Note that in EL(H) TBoxes, inverse roles are not permitted. A knowledge base (KB) K = (T , A) consists of a TBox T and an ABox A.

As usual, the semantics is based upon interpretations, which take the form I = (∆I , ·I ), where ∆I is a non-empty set and ·I maps each a ∈ NI to aI ∈ ∆I , each A ∈ NC to AI ⊆ ∆I , and each r ∈ NR to rI ⊆ ∆I ×∆I . The function ·I is straightforwardly extended to general concepts and roles, e.g. (¬A)I = ∆I \ AI , (∃r.C)I = {c | ∃d : (c, d) ∈ rI , d ∈ C I }, and (P -)I = {(c, d) | (d, c) ∈ P I }. An interpretation I satisfies G ⊑ H if GI ⊆ HI ; it satisfies A(a) (resp. r(a, b)) if aI ∈ AI (resp. (aI , bI ) ∈ rI ). I is a model of (T , A) if I satisfies all inclusions in T and assertions in A.

To simplify the presentation, we will assume that ELH TBoxes are in normal form, meaning that all concept inclusions are of one of the following forms:

withA,A1,A2,B ∈ NC∪{⊤}. It is well-known (cf. [Baader et al., 2005] that for every ELH TBox T , one can construct in polynomial time an ELH TBox T ′ in normal form (possibly using new concept names) such that T ′ |= T and every model of T can be expanded to a model of T ′ .

We use sig(T ) to denote the set of all concept and role names appearing in a TBox T . For ease of reference, we also define sets BCT of basic concepts and TCT of tail concepts for T as follows: BCT = TCT = NC ∩ sig(T ) if T is an ELH TBox, and TCT = {∃r, ∃r- | r ∈ NR ∩ sig(T )} and BCT = (NC ∩ sig(T )) ∪ TCT for a DL-LiteR TBox T .

Canonical Models We recall the definition of canonical models for DL-LiteR and ELH KBs. For both DLs, the domain of the canonical model IT ,A for a KB (T , A) consists of paths of the form aR1C1 . . .RnCn (n ≥ 0), where a ∈ Ind(A), each Ci is a tail concept, and each Ri a (possibly inverse) role. When T is a DL-LiteR TBox, the domain ∆IT ,A contains exactly those paths aR1∃R1 . . .Rn∃Rn which satisfy:

When T is an ELH TBox in normal form, the domain ∆IT ,A contains exactly those paths ar1A1 . . . rnAn for which each ri ∈ NR, and:

We denote the last concept in a path p by tail(p), and define IT ,A by taking:

Note that IT ,A is composed of a core consisting of the ABox individuals and an anonymous part consisting of (possibly infinite) trees rooted at ABox individuals. We will use IT ,A|e to denote the submodel of IT ,A obtained by restricting the universe to paths having e as a prefix.

Regular Languages We assume the reader is familiar with regular languages, represented either by regular expressions or nondeterministic finite state automata (NFAs). An NFA over an alphabet Σ is a tuple α = 〈S, Σ, δ, s0, F 〉, where S is a finite set of states, δ ⊆ S ×Σ× S the transition relation, s0 ∈ S the initial state, and F ⊆ S the set of final states. We use L(α) to denote the language defined by an NFA α, and when the way a regular language is represented is not relevant, we denote it simply by L.

3 Path Queries

We now introduce the query languages studied in this paper.

Definition 1. A conjunctive (two-way) regular path query (C2RPQ) has the form q(⃗x) = ∃⃗y ϕ where ⃗x and ⃗y are tuples of variables, and ϕ is a conjunction of atoms of the forms:

• (i) A(t), where A ∈ NC and t ∈ NI ∪ ⃗x ∪ ⃗y, and
• (ii) L(t, t′ ), where L is (an NFA or regular expression defining) a regular language over NR∪{A? | A ∈ NC}, and t, t′ ∈ NI ∪ ⃗x ∪ ⃗y.

As usual, variables and individuals are called terms, and the variables in ⃗x are called answer variables. A query with no answer variables is called a Boolean query.

Conjunctive (one-way) regular path queries (CRPQs) are obtained by disallowing symbols from NR \ NR in atoms of type (ii), and conjunctive queries (CQs) result from only allowing type-(ii) atoms of the form r(t, t′ ) with r ∈ NR. Twoway regular path queries (2RPQs) consist of a single atom of type (ii), and regular path queries (RPQs) further disallow symbols from NR \ NR. Finally, instance queries (IQs) take the form A(x) with A ∈ NC, or r(x, y) with r ∈ NR.

We now define the semantics of C2RPQs. For a regular language L over the alphabet NR ∪ NR ∪ {A? | A ∈ NC}, we call d2 an L-successor of d1 in I if there is some w = u1 . . . un ∈ L and some sequence e0, . . . , en of elements in ∆I such that e0 = d1, en = d2, and, for all 1 ≤ i ≤ n:

A match for a Boolean C2RPQ q in an interpretation I is a mapping π from the terms in q to elements in ∆I such that:

- π(t) ∈ AI for each atomA(t) in q, and

- π(t′ ) is an L-successor of π(t), for each L(t, t′ ) in q. We write I |= q if there is a match for q in I, and T ,A |= q if I |= q for every model I of T ,A.

Given an C2RPQ q with answer variables v1, . . . , vk, we say that a tuple of individuals (a1, . . . , ak) is a certain answer for q w.r.t. T , A just in the case that in every model I of T ,A there is a match π for q such that π(vi) = aIi for every 1 ≤ i ≤ k. Deciding whether a tuple of individuals is a certain answer for an C2RPQ can be linearly reduced to Boolean C2RPQ entailment. For this reason, we consider only the latter problem in what follows.

It is well known that the canonical model IT ,A can be homomorphically embedded into any model of T ,A, hence a CQ q is entailed from T ,A if and only if there is a match for q in IT ,A. This result can be easily lifted from CQs to C2RPQs, as C2RPQs are also monotonic and their matches are preserved under homomorphisms.

This property will be a crucial element in establishing our main theorem:

Theorem 3. The complexity results in Figure 1 hold.

We split the proof of this theorem into parts, with the lower bounds shown in the next section, and the (more involved) proofs of the upper bounds outlined in Section 5.

4 Lower Bounds

We start by establishing the required lower bounds.

Proposition 4. Boolean CRPQ entailment is

1. NL-hard in data complexity for DL-LiteRDFS;
2. P-hard in data complexity for EL;
3. NP-hard in combined complexity for DL-LiteRDFS;
4. PSPACE-hard in combined complexity for DL-Lite & EL.

Statements (1) and (2) hold even for RPQs.

Proof. Statement (1) follows from the analogous result for graph databases [Consens and Mendelzon, 1990]. It can be shown by a simple reduction from the NL-complete directed reachability problem: y is reachable from x in a directed graph G if and only if (x, y) is an answer to r∗ (x, y) w.r.t.

the ABox AG encoding G. Statement (2) is immediate given the P-hardness in data complexity of instance checking in EL [Calvanese et al., 2006], and (3) follows from the well-known NP-hardness in combined complexity of CQ entailment for databases [Abiteboul et al., 1995].

For statement (4), we give a reduction from the problem of emptiness of the intersection of an arbitrary number of regular languages, which is known to be PSPACE-complete [Kozen, 1977]. Let L1, . . . , Ln be regular languages over alphabet Σ. We will use the symbols in Σ as role names, and we add a concept name A. Let A = {A(a)} and q = ∃x L1(a, x) ∧ . . . ∧Ln(a, x). For DL-Lite, we will use the following TBox: T = {A ⊑ ∃r | r ∈ Σ} ∪ {∃r- ⊑ ∃s | r, s ∈ Σ}. For EL, we can use T = {A ⊑ ∃r.A | r ∈ Σ}. Notice that in both cases the canonical model IT ,A consists of an infinite tree rooted at a such that every element in the interpretation has a unique r-child for each r ∈ Σ (and no other children). Thus, we can associate to every domain element the word over Σ given by the unique path from a, and moreover, for every word w ∈ Σ∗ we can find an element ew whose path from a is exactly w. This means that if w ∈ L1 ∩ . . . ∩ Ln, we obtain a match for q in the canonical model by mapping x to ew. Conversely, if q is entailed, then any match in the canonical model defines a word which belongs to every Li, which means L1 ∩ . . . ∩ Ln is non-empty.

For (2)RPQs in DL-LiteRDFS and EL, we inherit combined complexity lower bounds of NL and P respectively from IQs. For DL-Lite, we establish a P lower bound for 2RPQs, which contrasts with the NL-completeness of instance checking.

Proposition 5. Boolean 2RPQ entailment in DL-Lite is Phard in combined complexity, assuming an NFA representation of the regular language.

Proof sketch. Consider the P-complete entailment problem in which one is given a propositional formula T = ρ1 ∧ . . . ∧ ρm ∧ v1 over variables v1, . . . , vn with ρi = vi1 ∧ vi2 → vi3 , and the problem is to decide whether T |= vn. We construct a DL-Lite TBox T and 2RPQ q such that T , {A(a)} |= q if and only if T |= vn. We let T consist of the axioms:

and q = ∃xα(x, x), where α = (S, Σ, δ, s0, {vout n }) is the NFA defined as follows:

- δ contains (s0,A?, vin n ), and for each ρi = vj ∧ vk → vℓ, the following transitions: (vin ℓ , ri,1, vin j ), (vout j , ri,1 , ρi), (ρi, ri,2, vin k ), and (vout k , ri,2 , vout ℓ ). Note: we use v1 in place of vin 1 and vout 1 .

The first transition in δ enforces that x must be mapped to a and that there must be a loop at a from state vin n to vout n . Intuitively, a state vin ℓ indicates that vℓ needs to be proven, and vout ℓ signals that vℓ has been successfully derived. From a state vin ℓ , the available transitions correspond to the rules in T which conclude on vℓ: selecting transition (vin ℓ , ri,1, vin j ) means choosing to use ρi to derive vℓ. The transitions (vout ℓ , ri,1 , ρi) and (ρi, ri,2, vin k ) allow us to move to the second variable of ρi once the first variable of ρi has been derived. When both variables have been proven, the transition (vout k , ri,2 , vout ℓ ) allows us to exit the derivation of vℓ. Thus, any loop from vin n to vout n in IT ,{A(a)} corresponds to a derivation of vn, and conversely, any derivation of vn yields a path witnessing the entailment of q.

As a corollary, we get P-hardness of RPQs in DL-LiteR, by using role inclusions to simulate the inverse roles in the query. We leave open whether the preceding hardness result applies when regular languages are given as regular expressions.

5 Upper Bounds

The main objective of this section will be to define a procedure for deciding IT ,A |= q for a KB (T ,A) and C2RPQ q. The procedure comprises two main steps. First, we rewrite q into a set Q of C2RPQs such that IT ,A |= q if and only if IT ,A |= q′ for some q′ ∈ Q. The advantage of the rewritten queries is that in order to decide whether IT ,A |= q′ , we will only need to consider matches which map the variables to Ind(A). The second step decides the existence of such restricted matches for the rewritten queries.

In order to more easily manipulate regular languages, it will prove convenient to use NFAs rather than regular expressions. Thus, in what follows, we assume all binary atoms take the form α(t, t′ ), where α is an NFA over NR ∪ NR ∪ {A? | A ∈ NC}. Given α = 〈S, Σ, δ, s0, F 〉, we use αs,G to denote the NFA 〈S, Σ, δ, s, G〉, i.e., the NFA with the same states and transitions as α but with initial state s and final states G.

5.1 Loop Computation

A key to defining our rewriting procedure will be to understand how an atom L(t, t′ ) can be satisfied in the anonymous part of the canonical model IT ,A. A subtlety arises from the fact that the path witnessing the satisfaction of an atom L(t, t′ ) may be quite complicated: it may move both up and down, passing by the same element multiple times, and possibly descending below t′ . This will lead us to decompose an atom L(t, t′ ) into multiple "smaller" atoms corresponding to segments of the L-path which are situated wholly above or below an element. Importantly, we know that the canonical model displays a high degree of regularity, since whenever two elements p1 and p2 in the anonymous part end with the same concept (i.e., Tail(p1) = Tail(p2)), the submodels IT ,A|p1 and IT ,A|p2 are isomorphic. In particular, this means that if Tail(p1) = Tail(p2), then p1 is an L-successor of itself in the interpretation IA,T |p1 just in the case that p2 is an L-successor of itself in the interpretation IA,T |p2 .

We will require a way of testing for a given TBox T and NFA α with states s, s′ whether Tail(e) = C ensures that there is a loop from e back to itself, situated wholly within IT ,A|e, which takes α from state s to state s′ . To this end, we construct a table Loopα which contains for each pair s, s′ of states in α, a subset of TCT . If T is a DL-LiteR TBox, then Loopα is defined inductively using the following rules:

1. for every s ∈ S: Loopα[s, s] = TCT
2. if C ∈ Loopα[s1, s2] and C ∈ Loopα[s2, s3], then C ∈ Loopα[s1, s3]
3. if C ∈ TCT , T |= C ⊑ A, and (s1,A?, s2) ∈ δ, then C ∈ Loopα[s1, s2]
4. if T |= C ⊑ ∃R, T |= R ⊑ R′ , T |= R- ⊑ R′′ , (s1,R′ , s2) ∈ δ, ∃R- ∈ Loopα[s2, s3], (s3,R′′ , s4) ∈ δ, C ∈ TCT , and C ̸= ∃R, then C ∈ Loopα[s1, s4]

For ELH, we replace the last rule by:

• 4'. if T |= C ⊑ ∃r.D, T |= r ⊑ r′ , T |= r ⊑ r′′ , (s1, r′ , s2) ∈ δ, D ∈ Loopα[s2, s3], (s3, r′′-, s4) ∈ δ, and C ∈ TCT , then C ∈ Loopα[s1, s4]

Example 6. Consider a DL-LiteR TBox T containing the inclusions B ⊑ ∃r, ∃r- ⊑ B, B ⊑ ∃t1, and t1 ⊑ t-2 , and consider the query q = ∃xy.r∗ t1t2r-(x, y), B(y), or equivalently, q = ∃xy.α(x, y), B(y), where α = 〈{s0, s1, s2, s3}, {r, t1, t2, r-}, δ, s0, {s3}〉 and δ = {(s0, r, s0), (s0, t1, s1), (s1, t2, s2), (s2, r-, s3)}. In the first step of the loop computation, we infer that Loopα[si, si] is the set of all tail concepts for 0 ≤ i ≤ 4. Next, by rule 4, and using T |= B⊑∃t1, T |= ∃r- ⊑ ∃t1, T |= t-1 ⊑ t2, (s0, t1, s1), ∃t-1 ∈ Loopα[s1, s1], and (s1, t2, s2), we can infer that B ∈ Loopα[s0, s2] and ∃r- ∈ Loopα[s0, s2]. In a further step, we can use T |= B ⊑ ∃r, (s0, r, s0), ∃r- ∈ Loopα[s0, s2], and (s2, r-, s3) to obtain B ∈ Loopα[s0, s3].

Note that the table Loopα can be constructed in polynomial time in |T | and |α| since entailment of inclusions is polynomial for both DL-LiteR and ELH. The following lemma shows that Loopα has the desired meaning:

Lemma 7. For every element p ∈ ∆IA,T \Ind(A): Tail(p) ∈ Loopα[s, s′ ] if and only if p is an L(αs,s′)-successor of itself in the interpretation IA,T |p.

5.2 Query Rewriting

Our aim is to rewrite our query in such a way that we do not need to map any variables to the anonymous part of the model. We draw our inspiration from a query rewriting procedure for Horn-SHIQ described in [Eiter et al., 2012]. The main intuition is as follows. Suppose we have a match π for q which maps some variable y to the anonymous part, and no other variable is mapped below π(y). Then we modify q so that it has essentially the same match except that variables mapped to π(y) are now mapped to the (unique) parent of π(y) in IT ,A. The delicate point is that we must "split"

PROCEDURE rewrite(q, T )

1. Choose either to output q or to continue.
2. Choose a non-empty set Leaf ⊆ vars(q) and y ∈ Leaf. Rename all variables in Leaf to y.
3. Choose C ∈ TCT such that T |= C ⊑ B whenever B(y) is an atom of q. Drop all such atoms from q.
4. For each atom α(t, t′ ) where α = 〈S,Σ, δ, s, F〉 is an NFA and y ∈ {t, t′},
5. choose a sequence s1, . . . , sn of distinct states from S such that sn ∈ F,
6. replace α(t, t′ ) by the atoms αs,s1 (t, y), αs1,s2 (y, y), . . . , αsn-2,sn-1 (y, y), αsn-1,sn (y, t′ ).
7. Drop all atoms αs,s′ (y, y) such that C ∈ Loopα[s, s′ ].
8. Choose some D ∈ BCT and R, R1, R2 ∈ NR such that:
9. (a) C = ∃R- and T |=D ⊑ ∃R [for DL-LiteR], or R ∈ NR and T |= D ⊑ ∃R.C [for ELH ].
10. (b) T |= R ⊑ R1 and T |= R ⊑ R2
11. (c) for each atom α(y, x) with α = 〈S,Σ, δ, s, F〉, there exists s′ ∈ S such that (s, R1 , s′ )∈δ.
12. (d) for each atom α(x, y) with α = 〈S,Σ, δ, s, F〉, there exist s′′ ∈ S, sf ∈ F with (s′′ , R2, sf ) ∈ δ.

For atoms of the form α(y, y), both (c) and (d) apply.

1. Replace
2. each atom α(y, x) with x ̸= y by αs′ ,F (y, x)
3. each atom α(x, y) with x ̸= y by αs,s′′ (x, y)
4. each atom α(y, y) by atoms αs′ ,s′′ (y, y) with s, s′ , s′′ , F as in Step 6.
5. If D ∈ NC is the concept chosen in Step 6, add D(y) to q. If D = ∃P -, add αP (z, y) to q, where z is a fresh variable and L(αP ) = {P}. Go to Step 1.

Figure 2: Query rewriting procedure rewrite.

atoms of the form α(t, t′ ) with y ∈ {t, t′} into the parts which are satisfied in the subtree IT ,A|π(y), and those which occur above π(y), whose satisfaction still needs to be determined and thus must be incorporated into the new query. With each iteration of the rewriting procedure, we obtain a query which has a match which maps variables "closer" to the core of IT ,A, until eventually we find some query that has a match which maps all terms to Ind(A).

In Figure 2, we give a recursive non-deterministic query rewriting procedure rewrite which implements the above intuition. Slightly abusing notation, we will use rewrite(q, T ) to denote the set of queries which are output by some execution of rewrite on input q,T .

Example 8. We illustrate two different ways to apply the rewriting step to the query q = ∃xy.r∗ t1t2r-(x, y), B(y) in Example 6. First, let Leaf = {x} be the set chosen in step 2. There is no renaming to do, so we proceed to step 3 and choose ∃r-. In step 4, we choose the sequence s2, s3, and replace α(x, y) by αs0,s2 (x, x), αs2,s3 (x, y). Since ∃r- ∈ Loopα[s0, s2], we drop the first atom and keep only αs2,s3 (x, y). In step 6, we can choose B for D, and r for the roles R, R1, R2. This ensures (a) and (b). For (c), we can take s3 since (s2, r-, s3) ∈ δ. In step 7, we replace αs2,s3 (x, y) by αs3,s3 (x, y). At the end of step 8, we are left with the query q′ = ∃xyz.r(z, y), αs3,s3 (x, y), B(y), which is output as a rewriting when we return to step 1. We remark that q′ is equivalent modulo T to the simpler ∃yz.r(z, y) since by choosing x = y, the atom αs3,s3 (x, y) is trivially satisfied, and B(y) is enforced by r(z, y) and the inclusion ∃r- ⊑ B. Intuitively, this rewriting captures the fact that, whenever we have an element e in an interpretation that satisfies ∃r-, then we can map x to e, thereby ensuring that the initial segment r∗ t1t2 is satisfied below e. Moreover, by mapping y to the r-predecessor of e, we satisfy the remaining r-.

As further illustration, suppose that in step 2, we choose Leaf = {x, y}, and let y be the selected variable. After renaming, we obtain q = ∃y.α(y, y), B(y). In step 3, we choose ∃r-, which leads us to drop the atom B(y), leaving us with ∃y.α(y, y). In step 4, we choose the sequence that contains only s3, so the atom α(y, y) is left untouched. Since ∃r- ∈ Loopα[s0, s3], we can drop this atom in step 5, obtaining the empty query. In step 6, we choose D = B and R = R1 = R2 = r. Step 7 is inapplicable since there are no binary atoms. Finally, in step 8, we add B(y) to obtain the query q = ∃y.B(y). Intuitively, this rewriting captures that if some element e satisfies B, then we can map both x and y to it to obtain a query match in which the regular expression r∗ t1t2r-(x, y) is fully satisfied below e.

The next lemma shows that using rewrite(q, T ), we can reduce the problem of finding an arbitrary query match to finding a match involving only ABox individuals.

Lemma 9. T ,A |= q if and only if there exists a match π for some query q′ ∈ rewrite(q, T ) in IA,T such that π(t) ∈ Ind(A) for every term t in q′ .

We remark that the number of variables and atoms in each query in rewrite(q, T ) is linearly bounded by |q|. This is the key property used to show the following:

Lemma 10. There are only exponentially many queries in rewrite(q, T ) (up to equivalence), each having size polynomial in |q|.

5.3 Query Evaluation

Even when all terms are mapped to ABox individuals, the paths between them may need to pass by the anonymous part in order to satisfy the regular expressions in the query. This leads us to define a relaxed notion of query entailment, which exploits the fact that if all variables are mapped to Ind(A), only loops (that is, paths from an individual a to itself in IA,T |a) may participate in the paths between them. Hence, we look for paths in the ABox that may use such loops to skip states in the query automata.

As part of our query evaluation procedure, we will need to decide for a given individual a whether a is an L(αs,s′)- successor of itself in IA,T |a. We cannot use Loopα directly, since it does not take into account the concepts which are entailed due to ABox assertions. We note however that the set of loops starting from a given individual is fully determined by the set of basic concepts which the individual satisfies. We thus define a new table ALoopα such that ALoopα[s, s′ ] contains all subsets G ⊆ BCT such that a is an L(αs,s′)- successor of itself in IA,T |a whenever G = {C ∈ BCT | a ∈ C IT ,A }. Note that the table ALoopα is exponential in |T |, but the associated decision problem is in P:

Lemma 11. It can be decided in polytime in |T | and |α| whether G ∈ ALoopα[s, s′ ].

We use ALoopα to define a relaxed notion of query match.

Definition 12. We write T ,A |≈ q if there is a mapping π from the terms in q to Ind(A) such that:

• (a) π(c) = c for each c ∈ NI,
• (b) T ,A |= A(π(t)) for each atomA(t) in q, and
• (c) for each α(t, t′ ) ∈ q with α = 〈S,Σ, δ, s, F〉, there is a sequence (a0, s0), . . . , (an, sn) of distinct pairs from Ind(A) × S such that a0 = π(t), an = π(t′ ), s0 = s, sn ∈ F , and for every 0 ≤ i < n, either:
• (i) ai = ai+1 and {C ∈ BCT | T,A |= C(ai)} ∈ ALoopα[si, si+1], or
• (ii) T ,A|=R(ai, ai+1) and (si,R, si+1)∈δ for some R.

The following lemma characterizes C2RPQ entailment in terms of relaxed matches.

Lemma 13. T ,A |= q if and only if T ,A |≈ q′ for some q′ ∈ rewrite(q, T ).

By applying the preceding characterization, we obtain our C2RPQ upper bounds:

Proposition 14. Boolean C2RPQ entailment is

1. NL in data complexity for DL-LiteR and DL-LiteRDFS;
2. P in data complexity for ELH;
3. NP in combined complexity for DL-LiteRDFS;
4. PSPACE in combined complexity for DL-LiteR and ELH.

Proof sketch. By Lemmas 9 and 13, T , A |= q just in the case that T ,A |≈ q′ for some q′ ∈ rewrite(q, T ). For statements 1 and 2, if T and q are fixed, then computing rewrite(q, T ) requires only constant time in |A|. To decide whether T , A |≈ q′ for q′ ∈ rewrite(q, T ), we guess a mapping π from the terms in q′ to Ind(A) and verify that it satisfies the conditions in Definition 12. Note that for condition (c), we cannot keep the whole sequence (a0, s0), . . . (an, sn) in memory at once, so we use a binary counter that counts up to |Ind(A)×S| and store only one pair of nodes (ai, si), (ai+1, si+1) at a time. The data complexity of verifying conditions (b) and (c) is the same as for instance checking in the corresponding DL: AC0 for DL-LiteR, and P for ELH. This yields the desired upper bounds of NL and NL P =P, respectively.

For statement 4, instead of building the whole set rewrite(q, T ), which can be exponential, we generate a single q′ ∈ rewrite(q, T ) non-deterministically. By Lemma 10, every query in rewrite(q, T ) can be generated after at most exponentially many steps, so we can use a polynomial-size counter to check when we have reached this limit. Since each rewritten query is of polynomial size (Lemma 10), and we keep only one query in memory at a time, the generation of a single query in rewrite(q, T ) requires only polynomial space. We can then use the same strategy as above to decide in polynomial space whether T ,A |≈ q′ . This yields a non-deterministic polynomial space procedure for deciding T ,A |= q. Using the well-known fact that NPSPACE = PSPACE, we obtain the desired upper bound.

For statement 3, we note that if T is an DL-LiteRDFS TBox, rewrite(q, T ) = {q}. Thus, it suffices to decide T ,A |≈ q, which can be done by guessing a mapping π and verifying in polytime that π satisfies the conditions of Definition 12.

By moving to 2RPQs, we can achieve tractability even in combined complexity.

Proposition 15. Boolean 2RPQ entailment is

1. NL in combined complexity for DL-LiteRDFS;
2. P in combined complexity for DL-LiteR and ELH.

Proof sketch. For (1), we can iterate over all mappings π of the (at most two) query variables, and for each mapping, we check whether the conditions of Definition 12 are met using the same strategy as in the proof of point 1 of Proposition 14. Recall that in DL-LiteRDFS, instance checking is in NL w.r.t. combined complexity [Calvanese et al., 2007a].

For (2), we first give a polynomial reduction to the problem of deciding whether T ,A |≈ q′ with q′ a 2RPQ. When q = ∃xyL(x, y) with x ̸= y, we can simply replace q by q′ = ∃xy Σ∗ · L · Σ∗ (x, y), where Σ = NR ∪ NR ∪ {A? | A ∈ NC}, since T ,A |= q iff T ,A |≈ q′ . For queries of the form ∃xL(x, x), the proof is more involved and passes by the definition of an alternative rewriting procedure for 2RPQs, which is similar in spirit to rewrite but is guaranteed to run in polynomial time. We can then check for a match of a 2RPQ in the ABox using essentially the same strategy as for (1), except that we must now perform some polynomial-time ALoopα tests to verify condition (c) of Definition 12.

6 Conclusion and FutureWork

In this paper, we established tight complexity bounds for answering various forms of regular path queries over knowledge bases formulated in lightweight DLs from the DL-Lite and EL families. Our results demonstrate that the query answering problem for these richer query languages is often not much harder than for the CQs and IQs typically considered. Indeed, query answering remains tractable in data complexity for the highly expressive class of C2RPQs, and for 2RPQs, we even retain polynomial combined complexity.

In future work, we plan to explore other useful extensions of regular path queries, such as nested path expressions (along the lines of [P´erez et al., 2010]), and the addition of path variables (recently explored in [Barcel´o et al., 2010]).

Acknowledgements The authors were supported by a Universit´e Paris-Sud Attractivit´e grant and the ANR project PAGODA ANR-12-JS02-007-01 (Bienvenu), the FWF project T515-N23 (Ortiz), and the FWF project P25518-N23 and the WWTF project ICT12-015 ( ˇSimkus).