Hierarchical data, where facts may refer to di erent categories in an ordered hierarchy, in the style of the multi-dimensional data model, arises in many applications. When these hierarchies are not captured by subclasses, but require navigation along roles, this data cannot be satisfactorily queried in the standard OBDA setting based on rstorder rewritable languages like DL-Lite. For this reason, we study how to extend DL-Lite with complex role inclusions (CRIs) in a way that overcomes this limitation. Complex role inclusions (CRIs) cause the loss of rst-order rewritability in general, but we study meaningful restrictions which guarantee that rewritability is preserved.
qT (x)
FO rewritability is important as it allows to implement OBDA by using standard database technologies. A missing functionality in OBDA is leveraging hierarchical knowledge not captured by subclass relations. Event locations may range from a speci c venue, to more general locations such as the city or the country where the event occurs. But unlike our previous example, venue is not a subclass of city, and there is no natural way to express in DL-Lite that if an event occurs in a venue located in a city, then it occurs in that city. Therefore, when evaluated over (Te; Ae), the query q2 retrieves ex1 but not the expected c1: q2(x)
CulturEvent(x); occursIn(x; y); y = Vienna: c1 ex1
Irsccoun locatedIn Irsccoun locatedIn StateOpera Vienna
Venue City ev1 n I s r u c c o
Austria
Country
The previous is a prototypical example of dimensional knowledge: venues, cities, and countries can be seen as di erent levels in the Location dimension. Dimensional knowledge arises in many settings, and it is useful for storing and accessing data at di erent granularity levels. To store and query time-stamped data, a Time dimension including day, month, and year could be used; the physical parts of complex objects may be ordered along a hierarchy of components. These hierarchies are often called dimensions, and are formalized as a nite set of categories with a partial order between them. Figure 3, shows a formalization for a Location dimension. Modeling and leveraging dimensional knowledge in query answering has been a major research problem in the database community, we discuss some works in Section 5. In this paper, we make a step towards extending the OBDA setting to leverage dimensional knowledge. In order to capture this kind of knowledge, we propose to extend the expressive power of DL-Lite with complex role inclusions (CRIs). For instance, adding the CRI occursIn locatedIn v occursIn to our example captures the missing knowledge, and makes c1 an answer to q2.
While CRIs enables DL-Lite to capture hierarchical knowledge, their
addition is in general computationally costly. They easily lead to undecidability if
unrestricted [
We consider the core fragment of DL-Lite with role inclusions DL-LiteH [
B := ? j A j 9r r := p j p ; where A 2 NC, p 2 NR, B is called a concept, and p an inverse role. The set of roles is de ned as NR = NR [ fp j p 2 NRg. We assume w.l.o.g. that a DL-LiteH TBox T is a nite set of concept inclusion axioms taking any of the following normal forms :
A v A0;
A v 9p; 9p v A; p v s; p v s ; together with a set of disjointness axioms of the form disj(A; A0), and disj(p; p0). For example, the ontology in Figure 2 is expressed with the DL-LiteH TBox:
A DL-LiteH ABox (or dataset ) is a nite set of assertions A(a), and p(a; b), with a; b 2 NI, A 2 NC, and p 2 NR, and we denote ind(A) as the set of individuals occurring in A. A knowledge base (KB) is a pair K = (T ; A). The semantics is de ned as usual in terms of interpretations I = ( I ; I ) consisting of a nonempty domain I and an interpretation function I , that complies with the standard name assumption in the sense that aI = a for every a 2 NI.
We consider the class of conjunctive queries and unions thereof. A term is either an individual name or a variable. A conjunctive query (CQ) is a rst order formula with free variables x and existential variables y that takes the form q(x) '(x; y), with ' a conjunction of atoms of the form A(x); r(x; y), and t = t0, where A 2 NC, r 2 NR, and t; t0 range over terms. Instance queries are CQs with exactly one atom and no existential variables. The terms occurring 1 https://arxiv.org/abs/1808.02850 in q are denoted terms(q), and the variables vars(q). The free variables x of a query are called answer variables.
Let I be an interpretation, q(x) a CQ. An answer to q in I is a tuple a from I of length jxj such that there is a map : terms(q) 7! I satisfying (i) (x) = a, (ii) (b) = b for each individual b, (iii) I j= P ( (z)) for each atom P (z) in q, and (iv) (t) = (t0) for each atom t = t0 in q, and in that case we write I j= q(a). The map is called a match for q in I. We denote ans(q(x); I) as the set of all answers to q in I. The certain answers of q(x) over A w.r.t. T , denoted cert(q; T ; A), is de ned as the tuples of individuals that are an answer to q in I, for every model I of (T ; A). 3
A complex role inclusion (CRI) is an expression of the form r s v t, with r; s; t 2 NR. An interpretation I = ( I ; I ) satis es a CRI r s v t if for all d1; d2; d3 2 I , (d1; d2) 2 rI , (d2; d3) 2 sI imply (d1; d3) 2 tI . We assume a set NRs NR of simple roles closed w.r.t. inverses (i.e. s 2 NRs implies s 2 NRs ); for each r 2 NR n NRs , r is a non-simple role.
De nition 1 (DL-LiteHR). A DL-LiteHR TBox T is a DL-LiteH TBox that may also contain CRIs, and such that: { For every CRI r s v t 2 T , s is simple and t is non-simple. { If s v t 2 T and t 2 NRs , then s 2 NRs .
The restriction to a simple role s in De nition 1 guarantees that recursion is linear, avoiding a possible explosion in the size of rewritings.
Properties such as FO-rewritability are a ected by CRIs. In the case of DL-Lite,
even one single xed CRI r s v r destroys rst-order rewritability, since it can
easily enforce r to capture reachability along the s-edges of a given graph.
Lemma 1. [
Non-recursive DL-LiteHR We start by de ning a suitable notion of recursive CRIs. For a DL-LiteHR TBox T , the recursion graph GT of T is the directed graph that contains (i) a node vA for each concept name A in T , (ii) a node vr for each role name r in T , and (iii) there exists an edge from a node vP 0 to a node vP whenever P occurs on the left-hand-side and P 0 on the right-hand-side of an axiom in T . A CRI t s v r is recursive w.r.t. a TBox T if GT has a path from vt or vs to vr. De nition 2. A DL-LitenHoRn-rec TBox is a DL-LiteHR TBox without recursive CRIs.
Restricting CRIs to be non-recursive indeed guarantees FO-rewritability. For a CQ q, we denote by zq an arbitrary but xed variable not occurring in q. An atom substitution = [ 1= 2] can be applied to q if 1 q and the e ect is to replace atoms 1 with atoms 2 in q.
De nition 3. Let T be a DL-LitenHoRn-rec TBox. For CQs q; q0, we write q whenever q0 is obtained by T q0
or by applying an atom substitution
to q, as follows: S1 S2 S3 S4 S5 S6 = [A2(x)=A1(x)], if A1 v A2 2 T and A2(x) 2 q; = [r(x; y)=A(x)], if A v 9r 2 T , r(x; y) 2 q and y is a non-answer variable occurring only once in q; = [A(x)=r(x; zq)], if 9r v A 2 T and A(x) 2 q; = [s(x; y)=r(x; y)], if r v s 2 T and s(x; y) 2 q; = [s(x; y)=r(y; x)], if r v s 2 T and s(x; y) 2 q; = [r(x; y)=ft(x; zq); s(zq; y)g], if t s v r 2 T and r(x; y) 2 q; By applying
T exhaustively, we obtain a FO-rewriting of a given query q.
De nition 4. The rewriting of q w.r.t. T is the rew (q; T ) = fq0 j q T q0g such that for each q0 2 rew (q; T ) there is no q00 2 rew (q; T ) isomorphic to q0, where q T q0 is the re exive, transitive closure of q T q0.
For any CQ q, rew (q; T ) is a nite query that can be e ectively computed. Lemma 2. Let T be a DL-LitenHoRn-rec TBox and let q a CQ. Each q0 2 rew (q; T ) is polynomially bounded in the size of T and q, and can be obtained in a polynomial number of steps.
Proof (sketch). Due to the non-recursiveness of the dependency graph and the restriction on simple roles, we show that we can assign to queries a (suitably bounded) degree that roughly corresponds to the number of rewriting steps that can be further applied. We prove that for each q0 such that q T q0, the degree does not increase, and after polynomially many steps we will reach q T q00 such that the degree strictly decreases.
The next result is shown analogously as in [
Non-recursive CRIs preserve FO-rewritability of DL-Lite, but their addition is far from harmless. Indeed, unlike the extension with transitive roles, even non-recursive CRIs increase the complexity of testing KB consistency. Theorem 2. Consistency checking in DL-LitenHoRn-rec is coNP-complete. sc2 scn p21 Proof. Upper-bound: Similarly as for standard DL-Lite, inconsistency checking can be reduced to UCQ answering, using a CQ q for testing whether each disjointness axiom is violated. By Lemmas 2 and 1, an NP procedure can guess one such q , guess a q0 in its rewriting, and evaluate q0 over A.
Lower-bound: We reduce the complement of 3SAT to KB satis ability. Suppose we are given a conjunction ' = c1^ ^cn of clauses of the form `i1 _`i2 _`i3 , where the `k are literals, i.e., propositional variables or their negation. Let x0; : : : ; xm be all the propositional variables occurring in '. In order to encode the possible truth assignments of each variable xi, we take two fresh roles rxi and rxi , intended to be disjoint. We construct a DL-LitenHoRn-rec TBox T' containing, for every 0 i m, the following axioms: disj(rxi ; rxi );
Ai v 9rxi u 9rxi ; 9rxi v Ai+1; 9(rxi ) v Ai+1; rxi v t; rxi v t These axioms have a model that is a full binary tree, rooted at A0 and whose edges are labeled with the role t, and with di erent combinations of the roles ri and rxi . Intuitively, each path represents a possible variable truth assignment. Further, T' contains axioms relating each variable assignment with the clauses it satis es, using roles sc1 ; : : : ; scn . More precisely, we have the following role inclusions for 0 i m, and 1 j n: rxi v scj ; if xi 2 cj rxi v scj ; if :xi 2 cj (1) To encode the evaluation of all clauses, we have axioms propagating down the tree all clauses satis ed by some assignment. Note that we could do this easily using a CRI such as scj t v scj . However, this would need a recursive role scj . Since the depth of the assignment tree is bounded by m, we can encode this (bounded) propagation using at most m roles sicj (1 i n) for each clause cj , which will be declared as subroles of another role scj . For 1 j n and 1 i < m, we have the CRIs: scj t v sc1j ; sicj t v sic+j1; sicj v scj .
Thus, if cj is satis ed in a t-branch of the assignment tree, its leaf will have an incoming scj edge. Now, in order to encode that there is at least one clause that is not satis ed, we need to forbid the existence of a leaf satisfying the concept 9(sc1 ) u u 9(scn ) . This cannot be straightforwardly written in DL-LitenHoRn-rec, but we resort again to CRIs to propagate information: 9(sc1 ) 9(pii 1) In DL-LitenHoRn-rec we cannot express CRIs like the one in our motivating example. To overcome this, we introduce an extension with certain kind of recursive CRIs. De nition 5 (recursion safe DL-LiteHR). A DL-LiterHecR-safe TBox T is a DL-LiteHR TBox where every CRI r1 s v r2 2 T satis es the following conditions: { If r2 is recursive, then every cycle in GT containing r2 has length at most one, and r1 = r2. { There is no axiom of the form B v 9t 2 T with t vsT s or t vsT s , where vsT denotes the re exive and transitive closure of s1 v s2 2 T with s2 2 NRs .
The key idea behind recursion safety is that every recursive CRI is `guarded' by a simple role that is not existentially implied. For query answering, we can then assume that only ABox individuals are connected by these guarding roles, and thus CRIs only ` re' close to the ABox (that is, each pair in the extension of a recursive role has at least one individual). In fact, we show below that every consistent recursion-safe KB has a model where both conditions hold. Example 1. Ke is recursion safe, since occursIn locatedIn v occursIn is the only CRI, and locatedIn is not implied by any existential axiom in Te.
In DL-LiterHecR-safe, consistency checking and instance query answering are tractable. In fact, for a given KB, we can build a polynomial-sized interpretation that is a model whenever the KB is consistent, and that can be used for testing entailment of assertions and of disjointness axioms.
De nition 6. Let (T ; A) be a DL-LiterHecR-safe KB. We de ne an interpretation ET ;A as follows. As domain ET ;A = D0 [ D1 [ D2 we use the individuals in A, fresh individuals car that serve as r- llers for individual a, and fresh individuals cr that serve as shared r- llers for the objects that are not individuals in A: D0 = ind(A);
D1 = fcar j a 2 D0; r occurs on the rhs of a CI in T g;
D2 = fcr j r occurs on the rhs of a CI in T g: The interpretation function has aET ;A = a for each a 2 ET ;A , and assigns to each concept name A and each role name r in T the minimal set of the form AET ;A ET ;A , rET ;A ET ;A ET ;A such that the following conditions hold, for all A 2 NC, B a concept, and r; r1; r2; s; t 2 NR: 1. A(a) 2 A implies a 2 AET ;A , and r(a; b) 2 A implies (a; b) 2 rET ;A . 2. For each B v 9r 2 T , a 2 BET ;A \ D0 implies (a; car) 2 rET ;A . 3. For each B v 9r 2 T , d 2 BET ;A \ (D1 [ D2) implies (d; cr) 2 rET ;A . 4. For each B v A 2 T , d 2 BET ;A implies d 2 AET ;A . 5. For each r1 v r2 2 T , (a; b) 2 rET ;A implies (a; b) 2 rET ;A .
1 1 6. For each r s v t 2 T , (a; b) 2 rET ;A and (b; c) 2 sET ;A imply (a; c) 2 tET ;A .
For ET ;A, we can show the following useful properties: Proposition 1. Let T = Tp [ Tn be a DL-LiterHecR-safe TBox, where Tp contains only positive inclusions, and Tn contains only disjointness axioms. Then, for every ABox A:
Proof (sketch). To prove P1, we assume that (T ; A) is consistent. Verifying that ET ;A satis es all but the disjointness axioms is straightforward. Let I be an arbitrary model of (T ; A). For d; d0 2 I , let tpI (d) = fB j d 2 BI g the set of concepts satis ed at d in I, and tpI (d; d0) = fr j (d; d0) 2 rI g, the set of roles connecting d and d0 in I. We show the following claim: Claim. For any given d 2 tpI (e) and (ii) for each d0 2 exists e0 2
I such that tpET ;A (d; d0)
tpI (e; e0).
ET ;A (i) there exists e 2
I such that tpET ;A (d)
ET ;A such that tpET ;A (d; d0) 6= ; we have that there
Towards a contradiction, assume there is = disj(B1; B2) 2 T such that ET ;A 6j= ; the case of role disjointness axioms is analogous. Then there is d 2
ET ;A with B1; B2 2 tpET ;A , and by the claim above, B1; B2 2 tpI (d) for each model I. Hence ET ;A , and this concludes proof of P1; P2 and P3 can also be shown using the above claim and the fact that ET ;A is a model of the KB.
This proposition allows us to establish the following results: Theorem 3. KB consistency and instance query answering in recursion safe DL-LiteHR are in PTime for combined complexity.
The recursion safe fragment of DL-LiteHR is not FO-rewritable: indeed, the TBox in the proof of Lemma 1 is recursion safe. However, we can get rid of recursive CRIs and regain rewritability if we have guarantees that they will only be relevant on paths of bounded length. We formalize this rough intuition next.
foreach ord(s; A; ) 2 C do q1(x; y) s(x; y), q2(x; y) A1(x); s(x; y); A2(y) ;
W
A1 A2 if ans(q1; ET ;A) 6 ans(q2; ET ;A) then return false ; q3(x; y) W A1(x); s(x; y); A2(y) ;
A16 A2 if ans(q3; ET ;A) 6= ; then return false ; return true.
Algorithm 1: CheckAdmissibility De nition 7 (k-bounded ABox). Let T be a DL-LiteHR TBox and A an ABox. Let S be a set of simple roles. Given a; b 2 ind(A), we say that there exists an S-path of length n between a and b (in A w.r.t. T ) if there exist pairwise distinct d1; : : : ; dn 1 2 ind(A) with di 62 fa; bg, and s1(a; d1); : : : ; si(di 1; di); : : : ; sn(dn 1; b) 2 A such that si vsT s and s 2 S, 1 i < n. Let Sr = fs j r s v r 2 T g. We say that A is k-bounded for T if for each recursive r 2 T there is no Sr-path of size larger than k.
We simulate recursive CRIs by unfolding them into k non-recursive ones. De nition 8 (k-unfolding). For an arbitrary DL-LiterHecR-safe TBox T , and xed k 0, a k-unfolding of T is a DL-LitenHoRn-rec TBox Tk obtained by replacing each r s v r 2 T with the axioms: r v r0 rj 1 s v rj rj v r^ (1 j k); where r^ and rj are fresh role names. For a CQ q, let q^ be the query obtained from q by replacing, for every r s v r 2 T , each r(x; y) 2 q by r^(x; y). For k-bounded ABoxes, rew(q^; Tk) is an FO-rewriting of q.
Lemma 3. Let T be a DL-LiterHecR-safe TBox, Tk a k-unfolding of T for some k 0, and let q be a CQ over T . Then, for every k-bounded ABox A: cert(q; T ; A) = Proof (sketch). In a nutshell, recursion-safety ensures that recursive CRIs in T can only ` re' in the chase along Sr-paths in the ABox. If A is k-bounded for T , then such paths have length k, so we get that every pair (d; d0) that should be added to a recursive role r is added to some rj , and hence to r^. 4
We introduce order constraints to express the order between categories of a dimension.
De nition 9. An order constraint takes the form ord (s; A; ), with s 2 NRs , A NC nite, and a strict partial order over A. I satis es ord (s; A; ) if sI
[ A1;A22A (A1I
A2I ); (4) sI \
[ (A1I A1 A2
A2I ) = ;: (5)
Intuitively, if ord (s; A; ) is satis ed in I, then all objects connected via role s are instances of A-concepts, in away that is compliant with the order . Equation 5 disallows also s-paths that are order compliant but connect instances of A-concepts which are incomparable w.r.t. . If such paths are allowed, one cannot guarantee k-boundednes. An alternative solution would have been to restrict concepts in A to be disjoint.
Example 2. The Location dimension from Figure 3 is captured by Ke = (Te; Ae) and the constraint c = ord (locatedIn; fVenue; City; Countryg; ) (6) with Venue City Country. In each model of Ke satisfying c, the role locatedIn only connects instances of Venue with those of City or Country, and instances of City only with those of Country, thus capturing the intended semantics of the dimension. 4
An useful insight is that order constraints can provide k-bounded guarantees. De nition 10. C covers a role r in T if there exists a partial order (A; ) such that for every role s in the set fs j r s v r 2 T g, ord (s; A0; ) 2 C for some A0 A. We say that C covers T , if it covers every role r in T . Further, (T ; A) is C-admissible if ET ;A satis es each c 2 C.
For example, the singleton set containing the ordering constraint c from (6), covers Te, and Ke is fcg-admissible since ETe;Ae satis es c.
Lemma 4. Let (T ; A) be a recursion-safe DL-LiteHR KB, and let C be a set of order constraints covering T . If (T ; A) is C-admissible, then A is `(C)-bounded for T , where `(C) := maxfjAj j ord(s; A; ) 2 Cg.
Proof (sketch). For any I, if I j= ord (s; A; ), for each chain of individuals a1; : : : ; an with (ai; ai+1) 2 sI for all 1 j < n, we have n jAj. This applies to ET ;A, as (T ; A) is C-admissible. Further, C covers T , so for each Sr = fs j r s v r 2 T g, all Sr-paths in ET ;A have size `(C). Finally, all Sr-paths in A w.r.t. T are also in ET ;A, so their length is `(C).
Lemmas 3 and 4 give us the desired result: we obtain FO-rewritability in the presence of CRIs, whenever order constraints allow us to guarantee boundedness. Theorem 4. Let T be a DL-LiterHecR-safe TBox, C a set of order constraints that covers T , and q a CQ. Let qC be the `(C)-rewriting of q w.r.t. T . Then, for each ABox A such that (T ; A) is consistent and C-admissible, cert(q; T ; A) = cert(qC ; ;; A).
Finally, we note that C-admissibility amounts to evaluate simple queries on ET ;A. This can be done in time that is polynomial in C, T , and A, using the procedure in Algorithm 1. Moreover, although testing C-admissibility is data dependent, once it is established, FO-rewritability is guaranteed for any CQ. Proposition 2. Checking C-admissibility for recursion-safe DL-LiteHR KBs is in PTime in combined complexity. 5
CRIs have been studied since the earliest DL research, when role value maps
where considered very desirable [
The notion of dimension used here is basis of the multi-dimensional data
model used for online-analytical processing (OLAP) [
In this paper we have advocated to use CRIs for getting more complete answers in the OBDA setting, particularly in the presence of dimensional knowledge. We extended DL-LiteH with CRIs. Severe restrictions are needed to preserve FO-rewritability, but we have identi ed a setting that is both natural and useful for the desired use case. An investigation of DL-LiteHR without the simple roles restriction is left for future work. Finding e ective ways to guarantee Cadmissibility, and identifying settings in which it can be tested via FO-queries, also seems to be an interesting challenge.