Nested Regular Path Queries in Description Logics

Abstract

Both in knowledge representation and in databases, there has been great interest recently in expressive mechanisms for querying data, while taking into account complex domain knowledge [9]. Description Logics (DLs), which on the one hand underlie the W3C standard Web Ontology Language (OWL), and on the other hand are able to capture at the intensional level conceptual modeling formalisms like UML and ER, are considered particularly well suited for representing a domain of interest [7]. In DLs, instance data, stored in a so-called ABox, is constituted by ground facts over unary and binary predicates (concepts and roles, respectively), and hence resembles data stored in graph databases [12,4]. There is a crucial difference, however, between answering queries over graph databases and over DL ABoxes. In the former, the data is assumed to be complete, hence query answering amounts to the standard database task of query evaluation. In the latter, it is typically assumed that the data is incomplete and additional domain knowledge is provided by the DL ontology (or TBox). Hence query answering amounts to the more complex task of computing certain answers, i.e., those answers that are obtained from all databases that both contain the explicit facts in the ABox and satisfy the TBox constraints. This difference has driven research in different directions. In databases, expressive query languages for querying graph-structured data have been studied, which are based on the requirement of relating objects by flexibly navigating the data. The main querying mechanism that has been considered for this purpose is that of one-way and two-way regular path queries (RPQs and 2RPQs) (cf. [13]). Conjunctive 2RPQs (C2RPQs) [10] are a significant extension of such queries that add to the navigational ability the possibility of expressing arbitrary selections, projections, and joins over objects related by 2RPQs, in line with conjunctive queries (CQs) over relational databases. Two-way RPQs are present in the property paths in SPARQL 1.1 [15], the new standard RDF query language, and in XPath as well. An additional construct that is present in XPath is the possibility of using test operators, also known as nesting, to express sophisticated conditions along navigation paths. This construct has been advocated for querying RDF graphs in the extension of SPARQL called nSPARQL [17], and it has been added to RPQs in the language of nested regular expressions for querying graph databases [3,4]. It is important to notice that existential tests in general This work has been supported by ANR project PAGODA (ANR-12-JS02-007-01), EU IP Project FP7-318338 OPTIQUE, FWF projects T515 and P25518, and WWTF project ICT12-015.

Introduction

Graph DBs DL-Lite Horn DLs (EL, Horn-SHIQ) Expressive DLs (ALC, SHIQ, ZIQ) data NL-c NL-c P-c data NL-c combined

NP-c NL-c PSPACE-c P-c

PSPACE-c data NL-c NL-c P-c combined P-c / NP-c

EXP-c EXP-c coNP-h

EXP-c coNP-h 2EXP-c coNP-h 2EXP-c cannot be captured even by C2RPQs, hence adding nesting effectively increases the expressive power of 2RPQs and of C2RPQs.

In the DL community, query answering has been investigated extensively for a wide range of DLs, but most work has been devoted to CQs and unions thereof (see [ 5 ] for discussion and references). C2RPQs have been explored for very expressive DLs [ 11 ], and recently also for the so called lightweight DLs, which are popular for query answering and data access [ 6 ]. Here we consider the extensions 2RPQs and C2RPQs with nesting, obtaining the complexity bounds summarized in Table 1. For DLs containing at least E LI, we are able to encode nesting away, thus showing that the worst-case complexity of query answering is not affected by this construct. By contrast, for lightweight DLs (starting already from DL-Lite!), we are able to show that adding nesting to 2RPQs leads to a surprising jump in combined complexity, from P-complete to EXP-complete. Via a sophisticated rewriting-based technique, we prove that for DL-Lite the problem remains in NL in data complexity. We thus demonstrate that adding nesting to (C)2RPQs does not affect the worst-case data complexity of query answering for lightweight DLs.

See [ 5 ] for the full version of this paper. 2

Preliminaries

We briefly recall the syntax and semantics of description logics (DLs). As usual, we assume countably infinite, mutually disjoint sets NC, NR, and NI of concept names, role names, and individuals. We typically use A for concept names, p for role names, and a; b for individuals. An inverse role takes the form p where p 2 NR. We let NR = NR [ fp j p 2 NRg and denote by r elements of NR .

A DL knowledge base (KB) consists of a TBox and an ABox, whose forms depend on the DL in question. For example, in the DL E LHI?, a TBox is a set of (positive) role inclusions of the form r v r0 and (negative) role inclusions of the form r u r0 v ? with cr;orn0ce2ptNsRfo,ramneddcaocnccoerpdtinignctloutshioenfsololof wthiengfosrymntaCx,vwiDth,Awh2erNeCCanadndr D2 NarRe:c4omplex

C ::= > j ? j A j 9r:C j C u C: 4 We slightly generalize the usual ELHI? by allowing for negative role inclusions. E LHI? is a Horn DL. In contrast, expressive DLs (such as ALC and SHIQ) allow disjunction C t C and universal restrictions 8r:C in complex concepts. We refer the reader to [ 2 ] for their definition. The so-called lightweight DLs can be defined as sublogics of E LHI?. E LHI is the fragment of E LHI? that has no ?. E LH and E LI are obtained by additionally disallowing inverse roles and role inclusions, respectively. DL-LiteR is also a fragment of E LHI?, in which concept inclusions can only take the forms B1 v B2 and B1 u B2 v ?, for Bi a concept name or a concept of the form 9r:> with r 2 NR . DL-Lite is the fragment of DL-LiteR that disallows role inclusions.

An ABox is a set of assertions of the form C(a) or r(a; b), where C is a complex concept, r 2 NR , and a; b 2 NI. We use Ind(A) to refer to the set of individuals in A. Semantics The semantics of DL KBs is based upon interpretations, which take the form I = ( I ; I ), where I is a non-empty set and I maps each a 2 NI to aI 2 I , each A 2 NC to AI I , and each p 2 NR to pI I I . The function I can be straightforwardly extended to complex concepts and roles. In the case of E LHI?, this is done as follows: >I = I , ?I = ;, (p )I = f(c; d) j (d; c) 2 pI g, (9r:C)I = fc j 9d : (c; d) 2 rI ; d 2 CI g, and (C uD)I = CI \DI . An interpretation I satisfies an inclusion G v H if GI HI , and it satisfies an assertion C(a) (resp. r(a; b)) if aI 2 AI (resp. (aI ; bI ) 2 rI ). A model of a KB (T ; A) is an interpretation I which satisfies all inclusions in T and assertions in A. 3

Nested Regular Path Queries

We now introduce our query languages. In RPQs, nested RPQs and their extensions, atoms are given by (nested) regular expressions whose symbols are roles. The set Roles of roles contains NR , and all test roles of the forms fag? and A? with a 2 NI and A 2 NC. They are interpreted as (fag?)I = f(aI ; aI )g and (A?)I = f(o; o) j o 2 AI g. Definition 1. A nested regular expression (NRE), denoted by E, is constructed according to the following syntax, where 2 Roles:

E ::= j E

E j E [ E j E j hEi: We assume a countably infinite set NV of variables (disjoint from NC, NR, and NI). Each t 2 NV [ NI is a term. An atom is either a concept atom of the form A(t), with A 2 NC and t a term, or a role atom of the form E(t; t0), with E an NRE and t; t0 two (possibly equal) terms.

A nested two-way regular path query (N2RPQ) q(x; y) is an atom of the form E(x; y), where E is an NRE and x; y are two distinct variables.5 A conjunctive N2RPQ (CN2RPQ) q(x) with answer variables x has the form 9y:', where ' is a conjunction of atoms whose variables are among x [ y.

A (plain) regular expression (RE) is an NRE that has no subexpressions of the form hEi. Two-way regular path queries (2RPQs) and conjunctive 2RPQs (C2RPQs) are defined analogously to N2RPQs and CN2RPQs but allowing only plain REs in atoms. 5 N2RPQs coincide with the queries called simply NREs in [ 3,4 ].

Given an interpretation I, the semantics of an NRE E is defined inductively: (E1 E2)I = E1I

E2I ; (E1 [ E2)I = E1I [ E2I ; (E1 )I = (E1I ) ; hEiI = f(o; o) j there is o0 2

I s.t. (o; o0) 2 EI g:

Assume a C2NRPQ q(x) = 9y:'. A match for q in an interpretation I is a mapping from the terms in ' to I such that (i) (a) = aI for every individual a of ', (ii) (x) 2 AI for every concept atom A(x) of ', and (iii) ( (x); (y)) 2 EI for every role atom E(x; y) of '. Let ans(q; I) = f (x) j is a match for q in Ig. An individual tuple a with the same arity as x is called a certain answer to q over a KB hT ; Ai if (a)I 2 ans(q; I) for every model I of hT ; Ai. We use ans(q; hT ; Ai) to denote the set of all certain answers to q over hT ; Ai. By query answering, we mean the problem of deciding whether a 2 ans(q; hT ; Ai).

Example 1. We consider an ABox of advisor relationships of PhD holders6. We assume an advisor relation between nodes representing academics. There are also nodes for theses, universities, research topics, and countries, related in the natural way via roles wrote, subm(itted), topic, and loc(ation). We give two queries over this ABox.

q1(x; y) = (advisor hwrote topic Physics?i) (x; y) Query q1 is an N2RPQ that retrieves pairs of a person x and an academic ancestor y of x such that all people on the path from x to y (including y) wrote a thesis in Physics. q2(x; y; z) = advisor (x; z); advisor (x; w); advisor hwrote htopic DBs?i subm loc fUSAg?i(y; z); advisor hwrote htopic Logic?i subm loc EUcountry?i (y; w) Query q2 is a CN2RPQ that looks for triples of individuals x, y, z such that x and y have both supervised z, who wrote a thesis on Databases and who submitted this thesis to a university in the USA. Moreover, x and y have a common ancestor w, and all people on the path from x to w, including w, must have written a thesis in Logic and must have submitted this thesis to a university in an EU country. 4

Complexity of Query Answering

For the lightweight DLs DL-LiteR and E L, a P upper bound in combined complexity for answering 2RPQs and a PSPACE upper bound for C2RPQs are known [ 6 ]. However, the addition of nesting causes a significant increase in complexity: already evaluating one N2RPQ in the presence of a DL-Lite or E L TBox is EXP-hard [ 5 ]. Theorem 1. N2RPQs in DL-Lite and E L are EXP-hard in combined complexity.

The above lower bound for answering N2RPQs hinges on the support for existential concepts in the right-hand-side of inclusions. If they are disallowed, then one can find a polynomial-time algorithm [ 17 ]. To our knowledge, it was open until now whether the polynomial-time upper bound is optimal. We prove P-hardness of the problem, already for plain graph databases. The proof is by a logspace reduction from the classical P-complete problem of checking entailment in propositional definite Horn theories. 6 The examples are inspired by the MGP project (http://genealogy.math.ndsu.nodak.edu/). Theorem 2. Given as input an N2RPQ q, a finite interpretation I and a pair (o; o0) 2 I I , it is P-hard to check whether (o; o0) 2 ans(q; I).

For ALC and all the expressive DLs that extend it, answering C2RPQs is 2EXP-hard. Indeed, the 2EXP hardness proof for conjunctive queries in SH by [ 14 ] can be adapted to use an ALC TBox and a C2RPQ. We show that this bound and the one in Theorem 1 are tight. This is a consequence of the fact that answering CN2RPQs can be polynomially reduced to answering non-nested C2RPQs using TBox axioms that employ inverses, conjunction on the left, and qualified existential restrictions.

Proposition 1. For each CN2RPQ q, we can compute in polynomial time an E LI TBox T 0 and C2RPQ q0 such that ans(q; hT ; Ai) = ans(q0; hT [ T 0; Ai) for every hT ; Ai.

It follows that in every DL that contains E LI, answering CN2RPQs is no harder than answering C2RPQs. From existing upper bounds for C2RPQs [ 11,16 ], we obtain: Corollary 1. Answering CN2RPQs is in 2EXP in combined complexity for all DLs contained in SHIQ, SHOI, ZIQ, or ZOI; and in EXP in combined complexity and in P in data complexity for all DLs contained in Horn-SHOIQ.

We point out that the 2EXP upper bound for expressive DLs can also be inferred, without using the reduction above, from the existing results for answering C2RPQs in ZIQ and ZOI [ 11 ].7 Indeed, these DLs support regular role expressions as concept constructors, and a nested expression hEi in a query can be replaced by a concept 9E:>. Hence, in ZIQ and ZOI, nested expressions provide no additional expressiveness and CN2RPQs and C2RPQs coincide.

The construction used in Proposition 1 also allows us to reduce the evaluation of an N2RPQ to standard reasoning in any DL that contains E LI.

Proposition 2. For every N2RPQ q and every pair of individuals a; b, one can compute in polynomial time an E LI TBox T 0, and a pair of assertions Ab(b) and As(a) such that (a; b) 2 ans(q; hT ; Ai) iff hT [ T 0; A [ fAb(b)gi j= As(a), for every DL hT ; Ai.

From this and existing upper bounds for instance checking in DLs, we easily obtain: Corollary 2. Answering N2RPQs is in EXP in combined complexity for every DL that contains E LI and is contained in SHIQ, SHOI, ZIQ, or ZOI.

We note that the EXP bounds in Corollaries 1 and 2 are optimal for all DLs that contain E LI, because standard reasoning tasks like satisfiability checking are already EXP-hard in this logic [ 1 ]. For the same reasons, the P bound for data complexity in Corollary 1 is tight for E L and its extensions [ 8 ].

The results stated so far leave a gap for the data complexity of the DL-Lite family: we inherit NL-hardness from plain RPQs, but we only have the P upper bound stemming from Proposition 1. This gap can be closed showing an NL upper bound, by extending to CN2RPQs an algorithm for answering C2RPQs due to Bienvenu et al. ([ 6 ]). The algorithm uses a sophisticated rewriting technique, and has the additional advantage of being more likely to serve as a basis for practicable techniques than the reductions sketched above. Please consult [ 5 ] for details. 7 For (1-way) CRPQs, which contain no inverse roles, the same applies to ZOQ and its sublogics. We have studied the extension of (C)2RPQs with a nesting construct inspired by XPath, and have characterized the data and combined complexity of answering nested 2RPQs and C2RPQs for a wide range of DLs. In light of the surprising jump from P to EXP in the combined complexity of answering nested 2RPQs in lightweight DLs, a relevant problem is to identify classes that exhibit better computational properties.

References

1. F. Baader , S. Brandt , and C. Lutz . Pushing the E L envelope further . In Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 ), 2008 .

2. F. Baader , D. Calvanese , D. McGuinness , D. Nardi , and P. F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation and Applications . Cambridge University Press, 2003 .

3. P. Barcelo´, J. Pe´rez, and J. L. Reutter . Relative expressiveness of nested regular expressions . In Proc. of AMW'12, CEUR Workshop Proceedings 866 , pages 180 - 195 , 2012 .

4. P. Barcelo´ Baeza. Querying graph databases . In Proc., of PODS'13 , pages 175 - 188 , 2013 .

5. M. Bienvenu , D. Calvanese , M. Ortiz , and M. Sˇimkus . Nested regular path queries in description logics . In Proc. of KR 2014 . AAAI Press, 2014 .

6. M. Bienvenu , M. Ortiz , and M. Simkus . Conjunctive regular path queries in lightweight description logics . In Proc. of IJCAI 2013 , 2013 .

7. A. Borgida and R. J. Brachman . Conceptual modeling with description logics . In Baader et al. [2] , chapter 10 , pages 349 - 372 .

8. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Data complexity of query answering in description logics . In Proc. of KR 2006 , pages 260 - 270 , 2006 .

9. D. Calvanese , G. De Giacomo, and M. Lenzerini . Conjunctive query containment and answering under description logics constraints . ACM TOCL , 9 ( 3 ): 22 . 1 - 22 .31, 2008 .

10. D. Calvanese , G. De Giacomo, M. Lenzerini , and M. Y. Vardi . Containment of conjunctive regular path queries with inverse . In Proc. of KR 2000 , pages 176 - 185 , 2000 .

11. D. Calvanese , T. Eiter , and M. Ortiz . Regular path queries in expressive description logics with nominals . In Proc. of IJCAI 2009 , pages 714 - 720 , 2009 .

12. M. P. Consens and A. O. Mendelzon. GraphLog: a visual formalism for real life recursion . In Proc. of the 9th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS'90) , pages 404 - 416 , 1990 .

13. I. F. Cruz , A. O. Mendelzon , and P. T. Wood . A graphical query language supporting recursion . In Proc. of the ACM SIGMOD Int. Conf. on Management of Data , pages 323 - 330 , 1987 .

14. T. Eiter , C. Lutz , M. Ortiz , and M. Simkus . Query answering in description logics with transitive roles . In Proc. of IJCAI 2009 , pages 759 - 764 , 2009 .

15. S. Harris and A. Seaborne . SPARQL 1 . 1 Query Language . W3C Recommendation , World Wide Web Consortium, Mar. 2013 .

16. M. Ortiz , S. Rudolph , and M. Simkus . Query answering in the Horn fragments of the description logics SHOIQ and SROIQ . In Proc. of IJCAI 2011 , pages 1039 - 1044 , 2011 .

17. J. Pe´rez, M. Arenas, and C. Gutierrez . nSPARQL: A navigational language for RDF . J. of Web Semantics , 8 ( 4 ): 255 - 270 , 2010 .