Virtual OBDA over Expressive Ontologies: Rewritings and Approximations?

Abstract

In this paper we extend virtual OBDA to more expressive ontology languages than that of DL-LiteR, which is the logic underpinning the W3C ontology language OWL 2. We achieve this by relying on two well-known mechanisms, namely conservative rewriting and approximation, and compiling some of the domain semantics into OBDA mappings.

1 Introduction

Ontology-Based Data Access (OBDA) is a popular paradigm that enables end users to access data sources through an ontology, abstracting away low-level details of the data sources themselves. The ontology provides a high-level description of the domain of interest, and is semantically linked to the data sources by means of a set of mapping assertions [ 7, 16 ]. Typically, the data sources are represented as relational data, the ontology is a set of logical axioms over concepts and roles, and each mapping assertion relates an SQL query over the database to a concept or role of the ontology.

Making OBDA work efficiently over large amounts of data, requires that query answering over the ontology is first-order (FO)-rewritable1 [ 8, 1 ], which in turn limits the expressiveness of the ontology language, and the degree of detail with which the domain of interest can be captured. The current language of choice for OBDA is DL-LiteR, the logic underlying OWL 2 QL [ 24 ], which has been specifically designed to ensure FOrewritability of query answering. Hence, it does not allow one to express disjunctive information, or any form of recursion on the data (e.g., as resulting from qualified existentials on the left-hand side of concept inclusions), since using such constructs in general causes the loss of FO-rewritability [ 9 ]. For this reason, in many situations the expressive power of DL-LiteR is too restricted to capture real-world scenarios.

The aim of this work is to overcome these limitations of DL-LiteR by allowing the use of additional constructs in the ontology. To be able to exploit the added value coming from OBDA in real-world settings, an important requirement is the efficiency of query answering, achieved through a rewriting-based approach. This is only possible for ontology languages that are FO-rewritable. Two general mechanisms that have ? This paper is an abridged version of [ 5 ]. 1 Recall that FO queries constitute the core of SQL. been proposed to cope with computational complexity coming from high expressiveness of ontology languages, and that allow one to regain FO-rewritability, are conservative rewriting [ 20 ] and approximation [ 26, 10 ]. In the former, an ontology in a powerful language is rewritten, when possible, into an equivalent one in a restricted language, while in the latter it is approximated, thus losing part of its semantics.

In this work, we significantly extend the practical impact of both approaches by bringing into the picture the mapping, an essential component of OBDA that has been ignored so far. Indeed, it is a fairly expressive component of an OBDA system, since it allows one to make use of arbitrary SQL (hence FO) queries to relate the content of the data source to the elements of the ontology. Hence, a natural question is how one can use the mapping component to capture as much as possible additional domain semantics, resulting in better approximations or more cases where conservative rewritings are possible, while maintaining a DL-LiteR ontology.

We illustrate how this can be done on an example. Consider a bank domain, where we can specify that a checking account in the name of a person is a simple account by means of the axiom CAcc u 9inNameOf.Person v SAcc. Further, assume that the information about the accounts and their owners is stored in a database D, and that the predicates CAcc, inNameOf, and Person are connected to D respectively via the mapping assertions sql 1(x) CAcc(x), sql 2(x; y) inNameOf(x; y) and sql 3(x) Person(x), where each sql i is an SQL query over D. Then this non-DL-LiteR axiom can be encoded by adding the assertion sql 1(x) ./ sql 2(x; y) ./ sql 3(y) SAcc(x) to the mapping. This assertion connects D directly to the ontology term SAcc by making use of a join of the SQL queries in the original mapping. We observe that the resulting mapping, together with the ontology in which the non-DL-LiteR axiom has been removed, constitutes a conservative rewriting of the original OBDA specification.

In this paper, we elaborate on this idea, by introducing a novel framework for rewriting and approximation of OBDA specifications. Specifically, we provide a notion of rewriting based on query inseparability of OBDA specifications [ 3 ]. To deal with those cases where it is not possible to rewrite the OBDA specification into a query inseparable one whose ontology is in DL-LiteR, we give a notion of approximation that is sound for query answering. We develop techniques for rewriting and approximation of OBDA specifications based on compiling the extra expressiveness into the mappings. We target rather expressive ontology languages, and for Horn-ALCHIQ, a Horn fragment of OWL 2, we study decidability of existence of OBDA rewritings, and techniques to compute them when they exist, and to approximate them, otherwise.

We have implemented our techniques in a prototype system called ONTOPROX, which exploits functionalities provided by the ONTOP [ 27 ] and CLIPPER systems [ 14 ] to rewrite or approximate an OBDA specification expressed in Horn-SHIQ to one that can be directly processed by any OBDA system. We have evaluated ONTOPROX over synthetic and real OBDA instances against (i) the default ONTOP behavior, (ii) local semantic approximation (LSA), (iii) global semantic approximation (GSA), and (iv) CLIPPER over materialized ABoxes. Using ONTOPROX, for a few queries we have been able to obtain more answers (in fact, complete answers, as confirmed by CLIPPER). However, for many queries ONTOPROX showed no difference with respect to the default ONTOP behavior. One reason for this is that in the considered real-world scenario, the mapping designers put significant effort to manually create complex mappings that overcome the limitations of DL-LiteR. Essentially they followed the principle of the technique presented here, producing an OBDA specification that was already “complete” by design.

The observations above immediately suggest a significant practical value of our approach, which can be used to facilitate the design of new OBDA specifications for existing expressive ontologies: instead of a manual compilation, which is cumbersome, error-prone, and difficult to maintain, mapping designers can write straightforward mappings, and the resulting OBDA specification can then be automatically transformed into a DL-LiteR OBDA specification with rich mappings.

Omitted proofs can be found in the extended version of this paper [ 4 ]. 2 2.1

Preliminaries

Ontologies We assume to have the following pairwise disjoint countably infinite alphabets: NC of concept names, NR of role names, and NI of constants (also called individuals). We consider ontologies expressed in Description Logics (DLs). Here we present the logics Horn-ALCHIQ, the Horn fragment of SHIQ without role transitivity, and DL-LiteR, for which we develop some of the technical results in the paper. However, the general approximation framework is applicable to any OWL 2 fragment.

A Horn-ALCHIQ TBox in normal form [ 18, 14 ] is a finite set of axioms of the following forms: concept inclusions (CIs) di Ai v C, role inclusions (RIs) R1 v R2, and role disjointness axioms R1 u R2 v ?, where A, Ai denote concept names, R, R1, R2 denote role names P or their inverses P , and C denotes a concept of the form ?, A, 9R.A, 8R.A, or 1 R.A. For an inverse role R = P , we use R to denote P . ? denotes the empty concept/role. A DL-LiteR TBox is a finite set of axioms of the form B1 v B2, B1 u B2 v ?, R1 v R2, and R1 u R2 v ?, where Bi denotes a concept of the form A or 9R.>. In what follows, for simplicity we write 9R instead of 9R.>, we use N to denote either a concept or a role name, and assume that all TBoxes are in normal form.

An ABox is a finite set of membership assertions of the form A(c) or P (c; c0), where c; c0 2 NI. For a DL L, an L-ontology is a pair O = hT ; Ai, where T is an L-TBox and A is an ABox. A signature is a finite set of concept and role names. An ontology O is said to be defined over (or simply, over) if all the concept and role names occurring in it belong to (and likewise for TBoxes, ABoxes, concept inclusions, etc.). When T is over , we denote by sig(T ) the subset of actually occurring in T . Moreover we denote with Ind(A), the set of individuals appearing in A.

The semantics, models, and the notions of satisfaction and consistency of ontologies are defined in the standard way. We only point out that we adopt the Unique Name Assumption (UNA), and for simplicity we also assume to have standard names, i.e., for every interpretation I and every constant c 2 NI interpreted by I, we have that cI = c. 2.2

OBDA and Mappings Let S be a relational schema over a countably infinite set NS of database predicates. For simplicity, we assume to deal with plain relational schemas without constraints, and with database instances that directly store abstract objects (as opposed to values). So, a database instance D of S is a set of ground atoms over the predicates in NS and the constants in NI.2 Queries over S are expressed in SQL. We use '(x) to denote that query ' has x = x1; : : : ; xn as free (i.e., answer) variables, where n is the arity of '. Given a database instance D of S and a query ' over S, ans('; D) denotes the set of tuples of constants in NI computed by evaluating ' over D.

In OBDA, one provides access to an (external) database through an ontology TBox, which is connected to the database by means of a mapping. Given a source schema S and a TBox T , a (GAV) mapping assertion between S and T has the form '(x) A(x) or '0(x; x0) P (x; x0); where A and P are respectively concept and role names, and '(x), '0(x; x0) are arbitrary (SQL) queries expressed over S, called source queries. Intuitively, given a database instance D of S and a mapping assertion m = '(x) A(x), the instances of the concept A generated by m from D is the set ans('; D); similarly for a mapping assertion '(x; x0) P (x; x0).

An OBDA specification is a triple P = hT ; M; Si, where T is a DL TBox, S is a relational schema, and M is a finite set of mapping assertions. Without loss of generality, we assume that all concept and role names appearing in M are contained in sig(T ). An OBDA instance is a pair hP; Di, where P is an OBDA specification, and D is a database instance of S. The semantics of the OBDA instance hP; Di is specified in terms of interpretations of the concepts and roles in T . We define it by relying on the (virtual3) ABox AM;D = fN (o) j o 2 ans('; D) and '(x) N (x) in Mg generated by M from D, where N is a concept or role name in T . Then, a model of hP; Di is simply a model of the ontology hT ; AM;Di.

To abstract away the low-level SQL details in source queries, following [ 13 ], we split each mapping assertion m = '(x) N (x) in M into two parts. By introducing an intermediate view name Vm for the SQL query '(x), we obtain a low-level mapping assertion of the form '(x) Vm(x), and a high-level mapping assertion of the form Vm(x) N (x). Hence, in our technical development we deal only with the high-level mappings, and directly consider the intermediate views as our data sources. 2.3

Query Answering We consider conjunctive queries, which are the basic and most important querying mechanism in relational database systems and ontologies. A conjunctive query (CQ) q(x) over a signature is a formula 9y: '(x; y), where ' is a conjunction of atoms N (z), such that N is a concept or role name in , and z are variables from x and y. The set of certain answers to a CQ q(x) over an ontology hT ; Ai, denoted cert (q; hT ; Ai), is the set of tuples c of elements from Ind(A) of the same length as x, such that q(c) (considered as a FO sentence) holds in every model of hT ; Ai. We mention two more query classes. An atomic query (AQ) is a CQ consisting of exactly one atom whose variables are all free. A CQ with inequalities (CQ6=) is a CQ that may contain inequality atoms between the variables of the predicate atoms. 2 All our results easily extend to the case where objects are constructed from retrieved database values [ 7 ]. 3 We call such an ABox ‘virtual’, because we are not interested in materializing its facts.

Given a CQ q, an OBDA specification P = hT ; M; Si and a database instance D of S, the answer to q over the OBDA instance hP; Di, denoted cert (q; P; D), is defined as cert (q; hT ; AM;Di). Observe that, when D is inconsistent with P (i.e., hP; Di does not have a model), then cert (q; P; D) is the set of all possible tuples of constants in AM;D (of the same arity as q). 3

An OBDA Rewriting Framework

We extend the notion of query inseparability of ontologies [ 6 ] to OBDA specifications. We adopt the proposal by [ 3 ], but we do not enforce preservation of inconsistency. Definition 1. Let be a signature. Two OBDA specifications P1 = hT1; M1; Si and P2 = hT2; M2; Si are -CQ inseparable if cert (q; P1; D) = cert (q; P2; D), for every CQ q over and every database instance D of S.

In OBDA, one must deal with the trade-off between the computational complexity of query answering and the expressiveness of the ontology language. Suppose that in an OBDA specification P = hT ; M; Si, T is expressed in an ontology language L that does not allow efficient query answering. A possible solution is to exploit the expressive power of the mapping to compute a new OBDA specification P0 = hT 0; M0; Si in which T 0 is expressed in a language Lt more suitable for query answering than L. The aim is to encode in M0 not only M but also part of the semantics of T , so that P0 is query-inseparable from P. This leads to the notion of rewriting of OBDA specifications. Definition 2. Let Lt be an ontology language. The OBDA specification P0 = hT 0; M0; Si is a CQ-rewriting in Lt of the OBDA specification P = hT ; M; Si if (i) sig(T ) sig(T 0), (ii) T 0 is an Lt-TBox, and (iii) P and P0 are -CQ inseparable, for = sig(T ). If such P0 exists, we say that P is CQ-rewritable into Lt.

We observe that the new OBDA specification can be defined over a signature that is an extension of that of the original TBox. This is specified by condition (i). In condition (ii), we impose that the new ontology is specified in the target language Lt. Finally, condition (iii) imposes that the OBDA specifications cannot be distinguished by CQs over the original TBox. Note that the definition allows for changing the ontology and the mappings, but not the source schema, accounting for the fact that the data sources might not be under the control of the designer of the OBDA specification.

As expected, it is not always possible to obtain a CQ-rewriting of P in an ontology language Lt that allows for efficient query answering. Indeed, the combined expressiveness of Lt with the new mappings might not be sufficient to simulate query answering over P without loss. In these cases, we can resort to approximating query answers over P in a sound way, which means that the answers to queries posed over the new specification are contained in those produced by querying P. Hence, we say that the OBDA specification P0 = hT 0; M0; Si is a sound CQ-approximation in Lt of the OBDA specification P = hT ; M; Si if P0 satisfies (i), (ii), and cert (q; P0; D) cert (q; P; D), for each CQ q over sig(T ) and for each instance D of S.

Next, we study CQ-rewritability of OBDA specifications into DL-LiteR, developing suitable techniques.

Rewriting OBDA Specifications

In this section, we develop our OBDA rewriting technique, which relies on Datalog rewritings of the TBox (and mappings). Recall that a Datalog program (with inequalities) is a finite set of definite Horn clauses without functions symbols, i.e., rules of the form head ', where ' is a finite non-empty list of predicate atoms and guarded inequalities called the body of the rule, and head is an atom, called the head of the rule, all of whose variables occur in the body. The predicates that occur in rule heads are called intensional (IDB), the other predicates are called extensional (EDB). 4.1

ET-mappings Now, we extend the notion of T-mappings introduced by [ 27 ], and define the notion of an ET-mapping that results from compiling into the mapping the expressiveness of ontology languages that are Datalog rewritable, as introduced below.

We first introduce notation we need. Let be a Datalog program and N an IDB predicate. For a database D over the EDB predicates of , let N i (D) denote the set of facts about N that can be deduced from D by at most i 1 applications of the rules in , and let N 1(D) = Si 1 N i (D). It is known that the predicate N 1( ) defined by N in can be characterized by a possibly infinite union of CQ6=s [ 11 ], i.e., there exist CQ6=s '0N ; '1N ; : : : such that N 1(D) = Si 0fN (a) j a 2 ans('iN ; D)g, for every D. The 'iN ’s are called the expansions of N and can be described in terms of expansion trees; cf. [4, Appendix A]. We denote by (N ) the set of expansion trees for N in , and abusing notation also the (possibly infinite) union of CQ6=s corresponding to it. Note that (N ) might be infinite due to the presence of IDB predicates that are recursive, i.e., either directly or indirectly refer to themselves.

We call a TBox T Datalog rewritable if it admits a translation T to Datalog that preserves consistency and answers to AQs (see, e.g., the translations by [ 17 ], [ 14 ], and [ 28 ] for Horn-SHIQ, and by [ 12 ] for SHI). We assume that T makes use of a special nullary predicate ? that encodes inconsistency, i.e., for an ABox A, hT ; Ai is consistent iff ?1 (A) is empty.4 We also assume that T includes the following auxiliary rules, whicTh ensure that T derives all possible facts constructed over sig(T ) and Ind(A) whenever hT ; Ai is inconsistent: > (x)

A(x); > (x)

A(x)

P (x; y); > (y) ?; > (x); P (x; y)

P (x; y); ?; > (x); > (y); where A and P respectively range over concept and role names in sig(T ), and > is a fresh unary predicate denoting the set of all the individuals appearing in A.

In the following, we denote with M the (high-level) mapping M viewed as a Datalog program, and with T ;M the Datalog program T [ M associated to a Datalog rewritable TBox T and a mapping M. From the properties of the translation T (and the simple structure of M), we obtain that T ;M satisfies the following: 4 Here we simply consider A as a database.

Input: Horn-ALCHIQ TBox T and mapping M.

Output: DL-LiteR TBox Tr and ET-mapping Mc.

Step 1: T1 is obtained from T by adding all CIs of the form d Ai v 9R.(d A0j ) entailed by

T , for concept names Ai; A0j 2 sig(T ).

Step 2: T2 = norm9(T1).

Step 3: T3 = normu(T2).

Step 4: Mc is etmT3 (M), and Tr is the DL-LiteR TBox consisting of all DL-LiteR axioms over sig(T3) entailed by T3 (including the trivial ones N v N ).

Lemma 1. Let hT ; M; Si be an OBDA specification where T is Datalog rewritable. Then, for every database instance D of S, concept or role name N of T , and a in Ind(AM;D), we have that hT ; AM;Di j= N (a) iff N (a) 2 N 1T ;M (D).

For a predicate N , we say that an expansion 'N 2 T ;M (N ) is DB-defined if 'N is defined over database predicates. Now we are ready to define ET-mappings. Definition 3. Let hT ; M; Si be an OBDA specification where T is Datalog rewritable. The ET-mapping for M and T , denoted etmT (M), is defined as the set of assertions of the form 'N (x) N (x) such that N is a concept or role name in T , and 'N 2 T ;M (N ) is DB-defined.

It is easy to show that, for M0 = etmT (M) and each database instance D, the virtual ABox AM0;D (which can be defined for ET-mappings as for ordinary mappings) contains all facts entailed by hT ; AM;Di. In this sense, the ET-mapping etmT (M) plays for a Datalog rewritable TBox T the same role as T-mappings play for (the simpler) DL-LiteR TBoxes. Note that, in general, an ET-mapping is not a mapping, as it may contain infinitely many assertions. However, AM0;D is still finite, given that it is constructed over the finite number of constants appearing in D.

Rewriting Horn-ALCHIQ OBDA Specifications to DL-LiteR

Let hT ; M; Si be an OBDA specification, where T is a Horn-ALCHIQ TBox over a signature . Procedure RewObda(T ; M), in Figure 1, constructs a DL-LiteR TBox Tr and an ET-mapping Mc such that hTr; Mc; Si is -CQ inseparable from hT ; M; Si.

In Step 2, the procedure applies to T1 the normalization step norm9, which gets rid of concepts of the form 9R.(d A0j ) in the right-hand side of CIs. This is achieved by the following well-known substitution [ 1 ]: every CI dm i=1 Ai v 9R.(djn=1 A0j ) in T1 is replaced with dim=1 Ai v 9Pnew , Pnew v R, and > v 8Pnew .A0j , for 1 j n, where Pnew is a fresh role name. Notice that the latter two forms of inclusions introduced by norm9 are actually in DL-LiteR, as > v 8Pnew .A0j is equivalent to 9Pnew v A0j . In Step 3, the procedure applies to T2 a further normalization step, normu, which introduces a fresh concept name AA1u uAn for each concept conjunction A1 u u An appearing in T2, and adds A1 u uAn AA1u uAn 5 to the TBox. Note that norm9(T1) 5 We use ‘ ’ to abbreviate inclusion in both directions. and normu(T2) are model-conservative extensions of T1 and T2, respectively [ 21 ], as one can easily show. We denote by rew(T ) the resulting TBox Tr, which in general is exponential in the size of T , and by comp(T ; M) the resulting ET-mapping Mc, which in general is infinite.

Example 1 Assume that the domain knowledge is represented by the TBox T = f CAccu9inNameOf.Person v SAcc g about bank accounts. Its normalization is T b = fPerson v 8inNameOf .A1; CAcc u A1 v SAccg. Assume that the database schema Sb consists of the two relations ENT(ID; TYPE; EMPID), PROD(NUM; TYPE; CUSTID), whose data are mapped to the ontology terms by means of the following mapping M: mP: SELECT ID AS X FROM ENT WHERE ENT.TYPE=’P’ Person(X) mN: SELECT NUM AS X, CUSTID AS Y FROM PROD inNameOf(X; Y) mC: SELECT NUM AS X FROM PROD P WHERE P.TYPE=’B’ CAcc(X) The corresponding high-level mapping Mb consists of the assertions: hP : fx j VPerson(x)g Person(x) hN : fx; y j VinNameOf (x; y)g inNameOf(x; y) hC : fx j VCAcc(x)g CAcc(x) Now, consider the OBDA specification Pb = hT b; Mb; Sbi. The RewObda procedure invoked on (T b; Mb) produces: – The intermediate TBoxes T1b and T2b coinciding with T b, and T3b extending T b with

ACAccuA1 CAcc u A1. – The ET-mapping Mbc = etmT3b (Mb), which extends Mb with the following three assertions: fx j VinNameOf (x; y); VPerson(y)g A1(x); fx j VCAcc(x); VinNameOf (x; y); VPerson(y)g fx j VCAcc(x); VinNameOf (x; y); VPerson(y)g

SAcc(x); ACAccuA1 (x): The procedure returns the DL-LiteR TBox Trb = fACAccuA1 v CAcc, ACAccuA1 v A1, ACAccuA1 v SAccg and the mapping Mbc. It is possible to show that PDbL-LiteR = hTrb; Mbc; Sbi is a CQ-rewriting of Pb into DL-LiteR.

The TBox T3 obtained as an intermediate result in Step 3 of RewObda(T ; M), is a model-conservative extension of T , tailored towards capturing in DL-LiteR the answers to tree-shaped CQs. This is obtained by introducing in Step 2 sufficiently many new role names, and in Step 3 new concept names, so as to capture entailed axioms that generate the tree-shaped parts of models. Note that at-most number restrictions do not participate in the generation of the tree-shaped parts of models, hence are not considered explicitly in Steps 1 to 3. On the other hand, the ET-mapping Mc = comp(T ; M) generates from a database instance a virtual ABox Av that is complete with respect to all ABox facts that might be involved in the generation of the tree-shaped parts of models of Tr and Av. This allows us to prove the main result of this section.

Theorem 2. Let hT ; M; Si be an OBDA specification such that T is a Horn-ALCHIQ TBox, and let hTr; Mci = RewObda(T ; M). Then hT ; M; Si and hTr; Mc; Si are -CQ inseparable, for = sig(T ).

Clearly, hTr; Mc; Si is a candidate for being a CQ-rewriting of hT ; M; Si into DLLiteR. However, since Mc might be an infinite set, hTr; Mc; Si might not be an OBDA specification and hence might not be effectively usable for query answering. Next we address this issue, and show that in some cases we obtain proper CQ-rewritings, while in others we have to resort to approximations. 5

Approximating OBDA Specifications

cutk

N;

= To obtain from an ET-mapping a proper mapping, we exploit the notion of predicate boundedness in Datalog, and use a bound on the depth of Datalog expansion trees.

An IDB predicate N is said to be bounded in a Datalog program , if there exists a constant k depending only on such that, for every database D, we have N k (D) = N 1(D) [ 11 ]. If N is bounded in , then there exists an equivalent Datalog program 0 such that 0 (N ) is finite, and thus represents a finite union of CQ6=s. It is well known that predicate boundedness for Datalog is undecidable in general [ 15 ]. We say that is a boundedness oracle if for a Datalog program and a predicate N it returns one of the three answers: N is bounded in , N is not bounded in , or unknown. When N is bounded, returns also a finite union of CQ6=s, denoted (N ), defining N . Given a constant k, k (N ) denotes the set of trees (and the corresponding union of CQ6=s) in (N ) of depth at most k, hence k (N ) is always finite.

We introduce a cutting operator cutk , which is parametric with respect to the cutting depth k > 0 and the boundedness oracle , which, when applied to a predicate N and a Datalog program , returns a finite union of CQ6=s as follows: ( (N ); if N is bounded in

w.r.t.

k (N ); otherwise: We apply cutting also to ET-mappings: given an ET-mapping etmT (M), the mapping cutk (etmT (M)) is the (finite) set of mapping assertions 'N (x) N (x) s.t. N is a concept or role name in T , and 'N 2 cutk (N; T ;M) is DB-defined.

The following theorem provides a sufficient condition for CQ-rewritability into DLLiteR in terms of the well-known notion of first-order (FO)-rewritability, which we recall here: a query q is FO-rewritable with respect to a TBox T , if there exists a FO query q0 such that cert (q; hT ; Ai) = ans(q0; A), for every ABox A over sig(T ) (viewed as a database). It uses the fact that if an AQ is FO-rewritable with respect to a Horn-ALCHIQ TBox T , then it is actually rewritable into a union of CQ6=s, and the fact that if T is FO-rewritable for AQs (i.e., every AQ is FO-rewritable with respect to T ), then each concept and role name is bounded in T [ 22, 2 ].

Theorem 3. Let hT ; M; Si be an OBDA specification such that T is a Horn-ALCHIQ TBox. Further, let Tr = rew(T ) and M0 = cutk (comp(T ; M)), for a boundedness oracle and some k > 0. If T is FO-rewritable for AQs, then hT ; M; Si is CQ-rewritable into DL-LiteR, and hTr; M0; Si is its CQ-rewriting. Otherwise, hTr; M0; Si is a sound CQ-approximation of hT ; M; Si in DL-LiteR.

This gives us decidable conditions for rewritability of OBDA specifications in several significant cases. It is shown by [ 2 ] and [ 22 ] that FO-rewritability of AQs relative to Horn-SHI-TBoxes, Horn-ALCF -TBoxes, and Horn-ALCIF -TBoxes of depth two is decidable. In fact, these FO-rewritability algorithms provide us with a boundedness oracle : for each concept and role name N in T , they return a FO-rewriting of the AQ N (x) that combined with the mapping M results in T ;M (N ).

Unfortunately, a complete characterization of CQ-rewritability into DL-LiteR is not possible if arbitrary FO-queries are allowed in the (low-level) mapping. Theorem 4. The problem of checking whether an OBDA specification with an E L ontology and FO source queries in the mapping is CQ-rewritable into DL-LiteR is undecidable.

However, if we admit only unions of CQs in the (low-level) mapping, it follows from decidability of boundedness of monadic Datalog programs [ 11 ] that we can fully characterize CQ-rewritability.

Theorem 5. The problem of checking whether an OBDA specification with a HornALCHI ontology of depth one and unions of CQs as source queries in the mapping is CQ-rewritable into DL-LiteR is decidable.

6 Implementation

To demonstrate the feasibility of our OBDA specification rewriting technique, we implemented the ONTOPROX6 prototype system and evaluated it over synthetic and real OBDA instances. It relies on the OBDA reasoner ONTOP7 and the complete Horn-SHIQ CQ-answering system CLIPPER8, used as Java libraries, on a standard Prolog engine (SWI-PROLOG9), and on an OWL 2 reasoner (HERMIT10).

Essentially, ONTOPROX implements the rewriting and compiling procedure described in Figure 1, but instead of computing the (possibly infinite) ET-mapping comp(T ; M), it computes its finite part cutk(comp(T ; M)). So, it gets as input an OWL 2 OBDA specification hTOWL2; M; Si and a positive integer k, and produces a DL-LiteR OBDA specification that can be used with any OBDA system. Below we describe some of the implementation details: (1) TOWL2 is first approximated to the Horn-SHIQ TBox T by dropping the axioms outside this fragment. (2) T is translated into a (possibly recursive) Datalog program and saturated with all CIs of the form d Ai v 9R.(d A0j ), using functionalities provided by CLIPPER. (3) The expansions cutk( (X)) are computed by an auxiliary Prolog program using

Prolog meta-programming. (4) To produce actual mappings that can be used by an OBDA reasoner, the views in the high-level mapping cutk(comp(T ; M)) are replaced with their original SQL definitions using functionalities of ONTOP. (5) The DL-LiteR closure is computed by relying on the OWL 2 reasoner for Horn-

SHIQ TBox classification. 6 https://github.com/ontop/ontoprox/ 7 http://ontop.inf.unibz.it/ 8 http://www.kr.tuwien.ac.at/research/systems/clipper/ 9 http://www.swi-prolog.org/ 10 http://hermit-reasoner.com/

For the experiments, we have considered two scenarios: UOBM. The university ontology benchmark (UOBM) [ 23 ] comes with a SHOIN ontology (with 69 concepts, 35 roles, 9 attributes, and 204 TBox axioms), and an ABox generator. We have designed a suitable database schema for the generated ABox, converted the ABox to a 10MB database instance for the schema, and manually created the mapping, consisting of 96 assertions11.

Telecom benchmark. The telecommunications ontology models a portion of the network of a leading telecommunications company, namely the portion connecting subscribers to the operating centers of their service providers. The current specification consists of an OWL 2 ontology with 152 concepts, 53 roles, 73 attributes, 458 TBox axioms, and of a mapping with 264 mapping assertions. The database instance contains 32GB of real-world data.

For each OBDA instance hhT ; M; Si; Di, we have evaluated the number of query answers and the query answering time with respect to five different setups: (1) The default behavior of ONTOP v1.15, which simply ignores all non-DL-LiteR axioms in T , i.e., using hT 1; M; Si where T 1 are all the DL-LiteR axioms in T . (2) The local semantic approximation (LSA) of T in DL-LiteR, i.e., using hT 2; M; Si where T 2 is obtained as the union, for each axiom 2 T , of the set of DL-LiteR axioms ( ) entailed by [ 10 ]. (3) The global semantic approximation (GSA) of T in DL-LiteR, i.e., using hT 3; M; Si where T 3 is the DL-LiteR closure of T [ 25 ]. (4) Result of ONTOPROX, i.e., hrew(T ); cut5(comp(T ; M)); Si. (5) CLIPPER over the materialization of the virtual ABox.

The details of the evaluation can be found in [ 4 ]. 7

Conclusions

We proposed a novel framework for rewriting and approximating OBDA specifications in an expressive ontology language to specifications in a weaker language, in which the core idea is to exploit the mapping layer to encode part of the semantics of the original specification, and we developed techniques for DL-LiteR as the target language.

We plan to continue our work along the following directions: (i) extend our technique to Horn-SHIQ, and, more generally, to Datalog rewritable TBoxes [ 12 ]; (ii) deepen our understanding of the computational complexity of deciding CQrewritability of OBDA specifications into DL-LiteR; (iii) extend our technique to SPARQL queries under different OWL entailment regimes [ 19 ]; (iv) carry out more extensive experiments, considering queries that contain existentially quantified variables. This will allow us to verify the effectiveness of RewObda, which was designed specifically to deal with existentially implied objects.

Acknowledgement. This work is partially supported by the EU under the large-scale integrating project (IP) Optique (Scalable End-user Access to Big Data), grant agreement n. FP7-318338. We thank Martin Rezk for insightful discussions, and Benjamin Cogrel and Elem Gu¨zel for help with the experimentation. 11 https://github.com/ontop/ontop-examples/tree/master/aaai-2016-ontoprox/uobm

References

1. Alessandro Artale , Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev . The DL-Lite family and relations . J. of Artificial Intelligence Research , 36 : 1 - 69 , 2009 .

2. Meghyn Bienvenu , Carsten Lutz, and Frank Wolter . First-order rewritability of atomic queries in Horn description logics . In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 754 - 760 , 2013 .

3. Meghyn Bienvenu and Riccardo Rosati . Query-based comparison of OBDA specifications . In Proc. of the 28th Int. Workshop on Description Logic (DL) , volume 1350 of CEUR Electronic Workshop Proceedings , 2015 .

4. Elena Botoeva , Diego Calvanese, Valerio Santarelli, Domenico Fabio Savo, Alessandro Solimando, and Guohui Xiao . Beyond OWL 2 QL in OBDA: Rewritings and approximations (Extended version) . CoRR Technical Report abs/1511 .08412, arXiv.org e-Print archive, 2015 . Available at http://arxiv.org/abs/1511.08412.

5. Elena Botoeva , Diego Calvanese, Valerio Santarelli, Domenico Fabio Savo, Alessandro Solimando, and Guohui Xiao . Beyond OWL 2 QL in OBDA: Rewritings and approximations . In Proc. of the 30th AAAI Conf. on Artificial Intelligence (AAAI) , 2016 .

6. Elena Botoeva , Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev . Query inseparability for description logic knowledge bases . In Proc. of the 14th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR) , pages 238 - 247 . AAAI Press, 2014 .

7. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Antonella Poggi, Mariano Rodriguez-Muro, and Riccardo Rosati . Ontologies and databases: The DLLite approach . In 5th Reasoning Web Int. Summer School Tutorial Lectures (RW) , volume 5689 of LNCS , pages 255 - 356 . Springer, 2009 .

8. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati . Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. of Automated Reasoning , 39 ( 3 ): 385 - 429 , 2007 .

9. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati . Data complexity of query answering in description logics . Artificial Intelligence , 195 : 335 - 360 , 2013 .

10. Marco Console , Jose´ Mora, Riccardo Rosati, Valerio Santarelli, and Domenico Fabio Savo. Effective computation of maximal sound approximations of description logic ontologies . In Proc. of the 13th Int. Semantic Web Conf. (ISWC) , volume 8797 of LNCS , pages 164 - 179 . Springer, 2014 .

11. Stavros S. Cosmadakis , Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi . Decidable optimization problems for database logic programs . In Proc. of the 20th ACM SIGACT Symp. on Theory of Computing (STOC) , pages 477 - 490 , 1988 .

12. Bernardo Cuenca Grau, Boris Motik, Giorgos Stoilos, and Ian Horrocks . Computing datalog rewritings beyond Horn ontologies . In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 832 - 838 , 2013 .

13. Floriana Di Pinto, Domenico Lembo, Maurizio Lenzerini, Riccardo Mancini, Antonella Poggi, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Optimizing query rewriting in ontology-based data access . In Proc. of the 16th Int. Conf. on Extending Database Technology (EDBT) , pages 561 - 572 . ACM Press, 2013 .

14. Thomas Eiter , Magdalena Ortiz, Mantas Simkus, Trung-Kien Tran , and Guohui Xiao . Query rewriting for Horn-SHIQ plus rules . In Proc. of the 26th AAAI Conf. on Artificial Intelligence (AAAI) , pages 726 - 733 . AAAI Press, 2012 .

15. Haim Gaifman , Harry G. Mairson, Yehoshua Sagiv, and Moshe Y. Vardi . Undecidable optimization problems for database logic programs . In Proc. of the 2nd IEEE Symp. on Logic in Computer Science (LICS) , pages 106 - 115 , 1987 .

16. Martin Giese , Ahmet Soylu, Guillermo Vega-Gorgojo, Arild Waaler, Peter Haase , Ernesto Jime´ nez -Ruiz, Davide Lanti, Martin Rezk, Guohui Xiao , O¨ zgu¨r L. O¨ zc¸ep, and Riccardo Rosati . Optique: Zooming in on Big Data. IEEE Computer , 48 ( 3 ): 60 - 67 , 2015 .

17. Ullrich Hustadt , Boris Motik, and Ulrike Sattler . Data complexity of reasoning in very expressive description logics . In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 466 - 471 , 2005 .

18. Yevgeny Kazakov . Consequence-driven reasoning for Horn-SHIQ ontologies . In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 2040 - 2045 , 2009 .

19. Roman Kontchakov , Martin Rezk, Mariano Rodriguez-Muro, Guohui Xiao , and Michael Zakharyaschev . Answering SPARQL queries over databases under OWL 2 QL entailment regime . In Proc. of the 13th Int. Semantic Web Conf. (ISWC) , LNCS . Springer, 2014 .

20. Carsten Lutz , Robert Piro, and Frank Wolter . Description logic TBoxes: Model-theoretic characterizations and rewritability . In Proc. of the 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 983 - 988 , 2011 .

21. Carsten Lutz , Dirk Walther, and Frank Wolter . Conservative extensions in expressive description logics . In Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI) , pages 453 - 458 , 2007 .

22. Carsten Lutz and Frank Wolter . Non-uniform data complexity of query answering in description logics . In Proc. of the 24th Int. Workshop on Description Logic (DL) , volume 745 of CEUR Electronic Workshop Proceedings , 2011 .

23. Li Ma , Yang Yang , Zhaoming Qiu, GuoTong Xie, Yue Pan, and Shengping Liu. Towards a complete OWL ontology benchmark . In Proc. of the 3rd European Semantic Web Conf. (ESWC) , volume 4011 of LNCS , pages 125 - 139 . Springer, 2006 .

24. Boris Motik , Achille Fokoue, Ian Horrocks, Zhe Wu, Carsten Lutz, and Bernardo Cuenca Grau. OWL Web Ontology Language profiles . W3C Recommendation , World Wide Web Consortium, October 2009 . Available at http://www.w3.org/TR/ owl-profiles/.

25. Jeff Z. Pan and Edward Thomas. Approximating OWL-DL ontologies . In Proc. of the 21st AAAI Conf. on Artificial Intelligence (AAAI) , pages 1434 - 1439 , 2007 .

26. Yuan Ren , Jeff Z. Pan , and Yuting Zhao . Soundness preserving approximation for TBox reasoning . In Proc. of the 24th AAAI Conf. on Artificial Intelligence (AAAI) , 2010 .

27. Mariano Rodriguez-Muro, Roman Kontchakov , and Michael Zakharyaschev . Ontologybased data access: Ontop of databases . In Proc. of the 12th Int. Semantic Web Conf. (ISWC) , volume 8218 of LNCS , pages 558 - 573 . Springer, 2013 .

28. Despoina Trivela , Giorgos Stoilos, Alexandros Chortaras, and Giorgos Stamou . Optimising resolution-based rewriting algorithms for OWL ontologies . J. of Web Semantics , pages 30 - 49 , 2015 .