We establish tight complexity bounds for answering an extension of conjunctive 2-way regular path queries over EL and DL-Lite knowledge bases. It has been extensively argued in the description logic (DL) community that answering queries over ABoxes in the presence of ontological constraints formulated in a DL TBox is a fundamental reasoning service. In databases, similar attention has been paid to the related problem of querying graph databases, which are relational databases where only unary and binary predicates occur, or in other words, node- and edge-labeled graphs [8, 3]. The relevance of both problems lies in the fact that in many application areas data can be naturally modeled as an ABox or a graph database. This applies, in particular, to XML data on the web, including RDF datasets. While the two communities share some common research goals, the research agendas they have pursued differ significantly. In the DL community, the focus has been on designing efficient algorithms for answering (plain) conjunctive queries in the presence of expressive 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. This paper aims to help bridge this gap, by considering an expressive extension of RPQs, and providing algorithms and precise complexity bounds for the E L and DL-Lite families of lightweight DLs. We build on conjunctive (2-way) regular path queries (C2RPQs), which 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 (roles) in both directions. C2RPQs are one of the most expressive and popular languages for querying graph databases. These queries have already been studied for some DLs. In particular, automata-based algorithms have been proposed for the very expressive DLs ZIQ, ZIO, and ZOQ [5, 6], 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 were proposed in [11] for Horn-SHOIQ and Horn-SROIQ. They are polynomial in data complexity but still EXPTIME in combined, which is worst-case optimal for these ? This work partially supported by the Austrian Science Fund (FWF) grants P20840 and T515.
Introduction
Jo¨rg Siekmann
worksIn hasAdvisor wroteThesisTThehseissisJS76 hahssTausobTpmiitcliettedToCompUunteirvS.Ecisesnecxe worksIn AI-AutDed1
ComputerScience AI-MAS3 locatedIn
UK
Country Thesis ThesisGS89 submittedTo hasTopic
Univ.
Kaiserslautern logics. For prominent lightweight DLs like the DL-Lite [4] and E L [2], which underly the OWL 2 profiles, queries with regular paths had not been explored and many questions remained open, like whether algorithms that require only polynomial space are possible. In DL-Lite, FO-rewritability and AC0 data complexity are clearly lost, since we can express reachability, but it was not known whether P-hardness was avoidable.
We propose an extension of C2RPQs that we call conjunctive (2-way) regular path queries with complex labels, abbreviated `-C2RPQs. To illustrate its expressiveness, we consider a graph representation of the Mathematics Genealogy Project (MGP) database, which contains about 160K historic records of advisor relationships of PhD holders in mathematics and related disciplines. We use nodes for mathematicians, theses, topics of research, and universities. Nodes and edges are labeled with concepts (unary relations) and roles (binary relations), respectively. Figure 1 depicts a fragment of such a graph.
Unification and
Matching Problems wroteThesis hasTitle SmGoerlkta worksInwoMrkastIhnLAoIg-iDc&LsF1oundaAtioI-nHs yLo1 oLOvoergrdiePcro-PSlyroomrgtoerdarpmThmyicpianelgsly
MathLogic&Foundations
Fig. 1: Example graph database of the Mathematics Genealogy Project
An ontology containing the axioms in Fig. 2 can be used to express, for example,
that a person that works in computer science or that wrote a doctoral thesis in computer
science is a computer scientist (
(
edge bases is PSPACE-complete, but drops to NP if we consider DL-LiteRDFS. For data complexity, the problem is NLSPACE-complete for DL-Lite and P-complete for E L. 2
Preliminaries
usual, we assume sets NC, NR, and NI of concept names, role names, and individuals.
R = r and r if R = r . An ABox is a set of assertions of the form A(b) or r(b; c), where
on the DL in question. In DL-Lite, inclusions take the form B1 v (:)B2, where each
role inclusions of the form R1 v (:)R2, where R1; R2 2 NR. DL-LiteRDFS is obtained from DL-LiteR by disallowing inclusions which contain negation or have existential concepts (9R) on the right-hand side. In E L, inclusions have the form C1 v C2, where C1; C2 are complex concepts constructed as follows: C := > j A j C u C j 9r:C. The
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 2 NI to aI 2 I , each
straightforwardly extended to general concepts and roles, e.g. (:A)I = I n AI and (9r:C)I = fc j 9d : (c; d) 2 rI ; d 2 CI g. I satisfies G v H if GI HI ; it satisfies A(a) (resp. r(a; b)) if aI 2 AI (resp. (aI ; bI ) 2 rI ). I is a model of K = (T ; A) if I satisfies all inclusions in T and assertions in A.
meaning that all concept inclusions are of one of the following forms: > v A A v B A v 9r:B B1 u B2 v A 9r:B v A with A; B; B1; B2 concept names. It is well-known that for every E LH TBox T , one can construct in polynomial time a normalized E LH TBox T 0 that uses fresh concept names such that T 0 j= T and every model of T can be expanded to a model of T 0.
lows: BC = NC [ f9R j R 2 NRg for DL-LiteR, and BC = NC for E LH.
consist of paths of the form aR1C1 : : : RnCn (n 0), where a 2 Ind(A), each Ci is a basic concept, and each Ri a (possibly inverse) role. When T is a DL-LiteR TBox, the domain IT ;A contains exactly those paths aR19R1 : : : Rn9Rn which satisfy: – if n 1, then T ; A j= 9R1(a); – for 1 i < n, T j= 9Ri v 9Ri+1 and Ri 6= Ri+1.
ar1A1 : : : rnAn for which each ri 2 NR, and: – if n 1, then T ; A j= 9r1:A1(a); – for 1 i < n, T j= Ai v 9ri+1:Ai+1.
AIT ;A = fa 2 Ind(A) j T ; A j= A(a)g [ fp 2 IT ;A n Ind(A) j T j= tail(p) v Ag rIT ;A = f(a; b) j r(a; b) 2 Ag [ f(p1; p2) 2 IT ;A IT ;A j p2 = p1 S C and T j= S v rg[ f(p2; p1) 2 IT ;A IT ;A j p2 = p1 S C and T j= S v r g
ymous part consisting of (possibly infinite) trees rooted at ABox individuals. We will use IT ;Aje to denote the submodel of IT ;A obtained by restricting the universe to paths having e as a prefix.
sented either by regular expressions or nondeterministic finite state automata (NFAs). An NFA over an alphabet is a tuple = hS; ; ; s0; F i, where S is a finite set of states, S S the transition relation, s0 2 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
Conjunctive Regular Path Queries with Complex Labels
Definition 1. By B(S) we denote the set of all (positive) Boolean formulas built from the symbols in S [ ftrue; falseg using the connectives ^ and _. A conjunctive (twoway) regular path query with complex labels (abbreviated to `-C2RPQ) has the form q(x) = 9y ' where x and y are tuples of variables, and ' is a conjunction of atoms of the following forms: (i) (t), where 2 B(NC) and t 2 NI [ x [ y, and (ii) L(t; t0), where L is (an NFA or regular expression defining) a regular language over B(NR) B(NC), and t; t0 2 NI [ x [ y.
answer variables. A query with no answer variables is called Boolean.
If all atoms of type (i) are of the form A(t) with A 2 NC, and the regular languages L in atoms of type (ii) comprise only symbols of the form (R; true) with R 2 NR, then q is called a conjunctive (two-way) regular path query (C2RPQ). Conjunctive one-way regular path queries with complex labels (`-CRPQs) and conjunctive one-way regular path queries (CRPQs) are defined analogously, the only difference being that they use formulas from B(NR) instead of B(NR) in atoms of type (ii). Conjunctive queries (CQs) are C2RPQs where all atoms of type (ii) have the form (R; true)(t; t0) with R 2 NR.
R. Recall the MGP database. The query q1(x; y) in Fig. 3 searches for pairs of computer scientists that have a biologist as common academic ancestor, and such that there is a physicist on that path. It returns, among others, Jack Minker and Edmund Clarke, who have the biologist and mathematician Johann Bernoulli (1667–1748) as common ancestor on a path including the physicist and mathematician Joseph Fourier (1768 – 1830); as well as Gert Smolka and Georg Gottlob, who have as ancestors Nikolaus Poda von Neuhaus, an Austrian entomologist (1723 - 1798), and the physicist Ludwig Boltzmann (1844 – 1906). The query q2(x; y) searches for a common academic ancestor x of Robert Kowalski and Franz Baader, together with the country y where the ancestor’s thesis was defended; it requires all ancestors on the path to be computer scientists and logicians. It returns one tuple: (Bernard Meltzer, UK). The query q3(x) is similar but we require x to be a biologist or physicist, and additionally allow physicists along the path. This query retrieves 8 people, going back to Gabriel Gruber (1740–1805), a Jesuit priest, philosopher, mathematician and professor of physics. q1(x; y) = CompScientist _ Logician(x); CompScientist _ Logician(y); hasAdvisor (hasAdvisor; Physicist) hasAdvisor (hasAdvisor; Biologist)
(hasAdvisor ) (hasAdvisor ; Physicist) (hasAdvisor ) (x; y) q2(x; y) = [ hasAdvisor; CompScientist ^ Logician ](RKowalski; x); [ hasAdvisor; CompScientist ^ Logician ](FBaader; x) [wroteThesis submittedTo locatedIn](x; y) q3(x) = [(hasAdvisor; ((CompScientist ^ Logician) _ Physicist))
(hasAdvisor; Biologist _ Physicist)](RKowalski; x) [ hasAdvisor; ((CompScientist ^ Logician) _ Physicist) (hasAdvisor)](FBaader; x)
We now define the semantics of `-C2RPQs. We say that a set X X satisfies a formula ' 2 B(X), written X j= ', if the formula that results from replacing each v 2 X by true if v 2 X and by false otherwise is equivalent to true. For a regular language L over the alphabet B(NR) B(NC), we call d2 an L-successor of d1 in I if there is some w = ( 1; 1) : : : ( n; n) 2 L and some sequence e0; : : : ; en of elements in I such that e0 = d1, en = d2, and, for all 1 i n: fR 2 NR j hei 1; eii 2 RI g j= i and fA 2 NC j ei 2 AI g j= i:
terms in q to elements in I such that: – (c) = cI if c 2 NI, – fA 2 NC j (t) 2 AI g j= for each atom (t) in q, and – (t0) is an L-successor of (t) for each atom L(t; t0) in q.
We write I j= q if there is a match for q in I, and T ; A j= q if I j= q for every model I of T ; A.
viduals (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. Just as for CQs and C2RPQs, 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.
into any model of T ; A, hence a CQ q is entailed by 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. Lemma 1. For every DL-LiteR or E LH KB (T ; A) and Boolean `-C2RPQ q: T ; A j= q if and only if IT ;A j= q.
and PSPACE-complete in combined complexity for DL-LiteR; the combined complexity drops to NP-complete for DL-LiteRDFS. For E LH, the problem is P-complete in data complexity and PSPACE-complete in combined complexity. All lower bounds hold also for CRPQs and in the absence of role inclusions.
4
Lower Bounds
2. P-hard in data complexity for E L;
4. PSPACE-hard in combined complexity for DL-Lite and E L.
be shown by a simple reduction from the NLSPACE-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 (
well-known NP-hardness in combined complexity of CQ entailment for databases [1].
tersection of an arbitrary number of regular languages, which is known to PSPACEcomplete [10]. Consider some regular languages L1; : : : ; Ln over alphabet . We will use the symbols in as role names, and we add a concept name A. Then we set A = fA(a)g and q = 9x L1(a; x) ^ : : : ^ Ln(a; x). For DL-Lite, we will use the following TBox: T = fA v 9r j r 2 g [ f9r v 9s j r; s 2 g. For E L, we can use T = fA v 9r:A j r 2 g. 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 2 (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 2 we can find an element ew whose path from a is exactly w. This means that if w 2 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. tu 5
Upper Bounds The main objective of this section will be to define procedure for deciding IT ;A j= q for a given KB T ; A and a given `-C2RPQ q. The procedure comprises two main steps. First, we rewrite q into a set Q of `-C2RPQs such that IT ;A j= q if and only if IT ;A j= q0 for some q0 2 Q. The advantage of the rewritten queries is that in order to decide whether IT ;A j= q0, we will only need to consider matches which map the variables to Ind(A). The second step evaluates the rewritten queries over the core part of the canonical model involving only Ind(A).
prove convenient to use NFAs rather than regular expressions. Thus, in what follows, we assume all binary atoms take the form (t; t0), where is an NFA over B(NR) B(NC). Given = hS; ; ; s0; F i, we use s;G to denote the NFA hS; ; ; s; Gi, i.e. the NFA with the same states and transitions as but with initial state s and final states G.
A key to defining our rewriting procedure will be to understand how an atom L(t; t0) 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; t0) may be quite complicated: it may move both up and down, passing by the same element multiple times, and possibly descending below t0. This will lead us to decompose an atom L(t; t0) 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 ;Ajp1 and IT ;Ajp2 are isomorphic. In particular, this means that if Tail(p1) =
that p2 is an L-successor of itself in the interpretation IA;T jp2 .
s; s0 whether Tail(e) = C ensures that there is a loop from e back to itself, situated
wholly within IT ;Aje, which takes from state s to state s0. To this end, we construct
a table Loop which contains for each pair s; s0 of states in , a subset of BC. If T is a
DL-LiteR TBox, then Loop is defined inductively using the following rules:
(
entailment of inclusions is polynomial for both DL-LiteR and E LH. The following lemma shows that Loop has the desired meaning: Lemma 2. For every element p 2 IA;T n Ind(A): Tail(p) 2 Loop [s; s0] if and only if p is an L( s;s0 )-successor of itself in the interpretation IA;T jp.
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 [9]. 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” atoms of the form (t; t0) with y 2 ft; t0g into the parts which are satisfied in the subtree IT ;Aj (y) (these have already been shown to hold, so can be dropped), 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).
Leaf to y. 3. Choose some concept C 2 BC such that fB j T j= C v Bg j= ' for every atom '(y). Drop all such atoms from q. 4. For each atom (t; t0) where = hS; ; ; s; F i is a NFA and y 2 ft; t0g, – choose a sequence s1; : : : sn of distinct states from S such that sn 2 F , – replace the atom (t; t0) in q by the atoms s;s1 (t; y), s1;s2 (y; y), . . . , sn 2;sn 1 (y; y), sn 1;sn (y; t0).
which are output by some execution of rewrite on input q,T . We remark that the number of variables and atoms in each query in rewrite(q; T ) is linearly bounded by the original q. This is the key property used to show the following: Lemma 3. There are only exponentially many queries in rewrite(q; T ) (up to equivalence), and each one has size polynomial in jqj.
ing an arbitrary query match to finding a match involving only ABox individuals. Lemma 4. T ; A j= q if and only if there exists a match for some query q0 2 rewrite(q; T ) in IA;T such that (t) 2 Ind(A) for every term t in q0.
Query Evaluation We have reduced T ; A j= q to checking whether there is a match for some q0 2 rewrite(q; T ) with (t) 2 Ind(A) for every term t in q0. However, 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. To handle this problem, we 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 ja) 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.
Thus, as part of our evaluation procedure, we will need to decide for a given individual a whether a is an L( s;s0 )-successor of itself in IA;T ja. We cannot use the table 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 concepts in BC which the individual satisfies. We thus introduce a new table ALoop such that ALoop [s; s0] contains all subsets G BC such that a is an L( s;s0 )-successor of itself in IA;T ja whenever G = fC 2 BC j a 2 CIT ;A g. Note that the size of ALoop is exponential in jT j, but the associated decision problem is in P: Lemma 5. It can be decided in polytime in jT j and j j whether G 2 ALoop [s; s0]. Definition 2. We write T ; A j q if there is a mapping such that: from the terms in q to Ind(A) (a) (c) = c for each c 2 NI, (b) fA 2 NC j T ; A j= A( (t))g j= for each atom (t) in q, and (c) for each (t; t0) 2 q with = hS; ; ; s; F i, there is a sequence (a0; s0); : : : (an; sn) of distinct pairs from Ind(A) S such that a0 = (t), an = (t0), s0 = s, sn 2 F , and for every 0 i < n, one of the following holds: (i) ai = ai+1 and fC 2 BC j T ; A j= C(ai)g 2 ALoop [si; si+1] (ii) there is some ( ; ) 2 with (si; ( ; ); si+1), fR 2 NR j T ; A j=
R(ai; ai+1)g j= and fA 2 NC j T ; A j= A(ai+1)g j= .
Lemma 6. T ; A j= q if and only if T ; A j q0 for some q0 2 rewrite(q; T ).
1. NLSPACE in data complexity for DL-LiteR and DL-LiteRDFS; 2. P in data complexity for E LH;
4. PSPACE in combined complexity for DL-LiteR and E LH.
Proof. By Lemmas 4 and 6, we can reduce T ; A j= q to deciding whether T ; A j q0 for some q0 2 rewrite(q; T ). For items 1 and 2, if T and q are fixed, then computing rewrite(q; T ) requires only constant time in jAj. To decide whether T ; A j q0 for q0 2 rewrite(q; T ), we guess a mapping from the terms in q0 to Ind(A) and verify that it satisfies the conditions in Definition 2. 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) jSj and store only one pair of nodes (ai; si); (ai+1; si+1) at a time. To verify conditions (b) and (c)(ii) we need checks of the form fR 2 NR j T ; A j= R(a; b)g j= and fA 2 NC j T ; A j= A(a)g j= . Each one amounts to a fixed number of instance checks (one for each symbol in or ), hence the data complexity of these checks is the same as for instance checking in the corresponding
NLSPACE for the former, and NLSPACE P =P for the latter.
For statement 4, instead of building the whole set rewrite(q; T ), which can be exponential, we generate a single q0 2 rewrite(q; T ) non-deterministically. More precisely, we take the initial query q and apply a sequence of rewriting steps to obtain some q0 2 rewrite(q; T ). By Lemma 3, every query in rewrite(q; T ) can be generated after at most exponentially many steps, so we can use a polynomial-sized counter to check when we have reached this limit. Since each rewritten query is of polynomial size (Lemma 3), and we keep a single query in memory at a time, the generation of a single query in rewrite(q; T ) requires only polynomial space. Then we can use the same strategy as above to decide in polynomial space whether T ; A j q0. We thus have a non-deterministic polynomial space procedure for deciding T ; A j= q. Using the well-known fact that NPSPACE =PSPACE, we obtain the desired upper bound.
be rewritten, i.e. rewrite(q; T ) = fqg. Thus, it suffices to decide whether T ; A j q. We then remark that the procedure described above is in NP, since we guess a (polysize) mapping and verify in polytime that satisfies the conditions of Definition 2. In future work, we plan to study what types of restrictions on the TBox and query lead to better combined complexity. We also wish to explore other types of path-based query languages. One interesting extension which has been recently proposed for graph databases [3] is the addition of path variables. In Boolean queries, these prove useful for speaking about equality of paths. For example, one might want to find whether there is a chain of advisors of the same length between both Edmund Clarke and Bernoulli, and Jack Minker and Bernoulli. Things become even more interesting if we allow path variables in the output. By outputting the paths for the preceding query, we could discover that Clarke and Minker have a path to Bernoulli of length 12. We could even output the common areas of expertise of the scientists along the path to find out that both have an 8-step path to some physicist (Poisson and Fourier), that in turn reach