Query Rewriting and Optimisation with Database Dependencies in Ontop

Abstract

We present technologies that underpin the OBDA system Ontop and take full advantage of storing data in relational databases. We discuss the theoretical foundations of Ontop, including the tree-witness query rewriting, T -mappings and optimisations based on database integrity constraints and SQL features. Ontology-based data access (OBDA) [18] is regarded as a key ingredient for the new generation of information systems. In the OBDA paradigm, an ontology denes a high-level global schema and provides a vocabulary for user queries, thus isolating the user from the details of the data source structure (which can be a relational database, a triple store, a datalog engine, etc.). The OBDA system transforms user queries into the vocabulary of the data and then delegates the actual query evaluation to the data sources. In this paper, we concentrate on OBDA for ontologies formulated in OWL 2 QL, a pro le of OWL 2 speci cally tailored to support rewriting of conjunctive queries (CQs) over ontologies into rst-order (FO) queries. A standard architecture of such an OBDA system over relational data sources can be represented as follows:

Introduction

CQ q rewriting +

TBox T

FO q0

ABox A

unfolding mapping + + ABox virtualisation

SQL data D The user is given an OWL 2 QL TBox T and can formulate CQs q(x) in the signature of T . The system rewrites q and T into an FO-query q0(x), called a rewriting of q and T , such that (T ; A) j= q(a) i A j= q0(a), for any ABox A and any tuple a of individuals in A. A number of di erent rewriting techniques have been proposed and implemented for OWL 2 QL (PerfectRef [ 18 ], Presto/Prexto [24, 23], Rapid [ 4 ], the tree-witness rewriting [ 11 ]) and its extensions ([ 12 ], Nyaya [ 7 ], Requiem/Blackout [ 16, 17 ], Clipper [ 5 ]).

The rewriting q0 is formulated in the signature of T and has to be further transformed into the vocabulary of the data source D before being evaluated. For instance, q0 can be unfolded into an SQL query by means of a GAV mapping M relating the signature of T to the vocabulary of D. Strangely enough, mappings and unfoldings have largely been ignored by query rewriting algorithms (with Mastro-I [ 18 ] being an exception), partly because the data was assumed to be given as an ABox (say, as a universal table in a database or as a triple store). We consider the query transformation process as consisting of two steps|query rewriting and unfolding|and argue that this brings practical bene ts (even in the case of seemingly trivial mappings for universal tables or triple stores).

The performance of rst OBDA systems based on the architecture above was marred by large rewritings that could not be processed by RDBMSs, which led the OBDA community to intensive investigations of rewriting techniques and optimisations. There are 3 main reasons for large CQ rewritings and unfoldings: (E) Sub-queries of q with existentially quanti ed variables can be folded in many di erent ways to match the canonical models of possible (T ; A), all of which must be re ected in the rewriting q0. (H) The concepts and roles for atoms in q can have many sub-concepts and sub-roles according to T , which also have to be included in the rewriting q0. (M) The mapping M can have multiple de nitions of the ontology terms, which may result in an exponential blowup when q0 is unfolded into a (most suitable for RDBMSs) union of Select-Project-Join queries.

In fact, most of the proposed rewriting techniques try to tame (E): various optimisations are used in uni cation strategies to reduce the size of UCQs, with conjunctive query containment as the last resort. Presto [24] and the tree-witness rewriting [ 11 ] use non-recursive datalog to deal with (H); this, however, is of little help if a further transformation to a UCQ is required. The combined approach [ 13, 15 ] constructs nite representations of (in general) in nite canonical models of (T ; A) thereby totally removing (H). It also solves (E) for TBoxes without role inclusions; otherwise, rewritings can still be of exponential size, or the ltering procedure [ 15 ] may have to run exponentially many times.

In theory, (E) turns out to be incurable under the architecture above: there exist CQs and OWL 2 QL TBoxes for which any FO- (or non-recursive datalog) rewriting results in a superpolynomial (or exponential) blowup [ 10 ], which happens independently of the contribution of (H) and (M); the polynomial rewriting of [ 8 ] hides this blowup behind the existential quanti cation over special constants. Fortunately, it seems that only (arti cially) complex CQs and TBoxes trigger issues with (E). For real-world CQs and ontologies, the number of foldings in (E) appears to be very small and can be e ciently dealt with by suitable rewritings [ 11 ].

In this paper, we attack both (H) and (M) at the same time using two key observations. First, the schema and integrity constraints (dependencies), , of the data source D together with the mapping M often provide valuable information about the class of possible ABoxes over which the user CQ is rewritten. (Note that these ABoxes are virtual representations of D and do not have to be materialised.) For example, if we know that all our virtual ABoxes A are 9-complete with respect to T (that is, contain witnesses for all concepts 9R in T ) then we do not face (E); if all A are H-complete (that is, B(a) 2 A whenever A(a) 2 A and T j= A v B, and similarly for roles) then (H) disappears. Second, we can make the virtual ABoxes H-complete by taking the composition of T and M as a new mapping. This composition, called a T -mapping [20], can be simpli ed with the help of and the features of the target query language before being used in the unfolding. As the simpli cations use , they preserve correct answers only over database instances satisfying . (Even if the mappings are trivial and the ABox comes from a universal table or a triple store, it often has a certain structure and satis es certain constraints, which could be taken into account to make query answering more e cient [ 9 ]).

These observations underpin the system Ontop (ontop.inf.unibz.it), which is implemented at the Free University of Bozen-Bolzano and available as a Protege plugin, a SPARQL endpoint and OWLAPI and Sesame libraries. The process of query rewriting and unfolding in Ontop with all optimisations is shown in the picture below:

tw-rewriting Ê unfolding CQ q

+

TBox T

UCQ qtw completion Ë

SQO Ì + + mapping M ABox completion dependencies ABox A + ABox virtualisation + SQO

Í

T -mapping

SQL

H-complete ABox A

+

data D ABox virtualisation This architecture, which is our main contribution, will be discussed in detail in the remainder of the paper. Here we only emphasise the key ingredients: Ê the tree-witness rewriting qtw assumes the virtual ABoxes to be H-complete; it separates the topology of q from the taxonomy de ned by T , is fast in practice and produces short UCQs; Ë the T -mapping combines the system mapping M with the taxonomy of T to ensure H-completeness of virtual ABoxes; Ì the T -mapping is simpli ed using the Semantic Query Optimisation (SQO) technique and SQL features; the T -mapping is constructed and optimised for the given T and only once, and is used for unfolding all rewritings qtw; Í the unfolding algorithm uses SQO to produce small and e cient SQL queries. Our experimental results [22, 21] (also www.dcs.bbk.ac.uk/~roman/tw-rewriting) show that when applied to real-world queries, ontologies and databases, Ontop automatically produces rewritings of reasonably high quality and its performance is comparable to that of traditional RDBMSs with hand-crafted queries.

OWL 2 QL and Databases

The language of OWL 2 QL contains individual names ai, concept names Ai, and role names Pi (i 1). Roles R and basic concepts B are de ned by the grammar:

R ::=

Pi j

Pi ;

B ::= ? j

Ai j 9R: A TBox, T , is a nite set of inclusions of the form B1 v B2;

B1 v 9R:B2;

B1 u B2 v ?;

R1 v R2;

R1 u R2 v ?: An ABox, A, is a nite set of atoms of the form Ak(ai) or Pk(ai; aj ). The semantics for OWL 2 QL is de ned in the usual way based on interpretations I = ( I ; I ) [ 2 ]. The set of individual names in A is denoted by ind(A). Although ABoxes do not contain inverse roles, we write P (a; b) 2 A if P (b; a) 2 A; also, we write 9R(a) 2 A if R(a; b) 2 A, for some b. We denote by vT the subsumption relation induced by T and write S1 vT S2 if T j= S1 v S2, where S1 and S2 both are either basic concepts or roles.

A conjunctive query (CQ) q(x) is a rst-order formula 9y '(x; y), where ' is a conjunction of atoms of the form Ak(t1) or Pk(t1; t2), and each ti is a term (an individual or a variable in x or y). We often use the datalog notation for CQs, writing q(x) '(x; y) (without the existential quanti ers), and call q the head and ' the body of the rule. The variables in x are called answer variables. A tuple a ind(A) is a certain answer to q(x) over (T ; A) if I j= q(a) for all models I of (T ; A); in this case we write (T ; A) j= q(a). We sometimes identify q with the set of its atoms, and set R(x; y) = P (x; y) if R = P , and R(x; y) = P (y; x) if R = P .

As explained in the introduction, we assume that the data comes from a relational database rather than an ABox. We view databases [ 1 ] as triples (R; ; I), where R is a database schema, containing predicate symbols (with their arity) for both stored database relations and views (together with their de nitions in terms of stored relations), is a set of integrity constraints over R (in the form of inclusion and functional dependencies), and I is a data instance over R (satisfying ). The vocabularies of R and T are linked together by means of mappings given by a domain expert or extracted (semi-)automatically. A mapping, M, from R to T is a set of (GAV) rules of the form

S(x) '(x; z); where S is a concept name or a role in T and '(x; z) a conjunction of atoms with stored relations and views from R and a lter, that is, a Boolean combination of built-in predicates such as = and <. (Note that, by including views in the schema, we can express any SQL query in mappings.) Given a mapping M from R to T , the ground atoms S(a), for S(x) '(x; z) in M and I j= 9z '(a; z), comprise the ABox, AI;M, which is called the virtual ABox for T and M over I. We can now de ne certain answers to a CQ q over a TBox T and a database (R; ; I) linked by a mapping M as certain answers to q over (T ; AI;M).

The Tree-Witness Rewriting over H-complete ABoxes In the rewriting used in Ontop, we assume that the ABoxes A are H-complete with respect to T in the sense that S2(a) 2 A whenever S1(a) 2 A and S1 vT S2. The issue of completing ABoxes will be discussed in Sec. 4.

Let q(x) = 9y '(x; y). As is well-known, for any ABox A, there is a canonical model CT ;A of (T ; A) such that, for all a ind(A), we have (T ; A) j= q(a) i CT ;A j= q(a) i there is a homomorphism h : q(a) ! CT ;A. The domain of CT ;A consists of two parts: ind(A) and the witnesses introduced by the 9 quanti ers in T . We assume that every a 2 ind(A) with B(a) 2 A roots a (possibly in nite) subtree CTB(a) of CT ;A, which may intersect another such subtree only on their common root (each CTB(a) is isomorphic over the signature of T to the canonical model of (T [ fA v Bg; fA(a)g), for a fresh concept name A).

CTB1 (a1) a1 : B1

CTB1 (a2)

CTB2 (a2) P1; P2

P2 a2 : B1; B2 a3

Each homomorphism h : q(a) ! CT ;A splits q into a sub-query mapped by h to ind(A) and a subquery mapped to the trees CTB(a), for B(a) 2 A. We can think of a rewriting of q and T as listing possible splits of q into such subqueries. We rst characterise the subqueries of q that can be mapped to subtrees CTB(a). Let t = (tr; ti) be a pair of disjoint sets of terms in q such that ti 6= ; and ti y. Consider the subset qt of q comprising atoms with terms in tr [ti but not entirely in tr: qt = S(z) 2 q j z tr [ ti and z 6 tr : We say that t is generated by a basic concept B if there is a homomorphism h : qt ! CTB(a), for some a, such that h 1(a) = tr. We call t a tree witness for q and T if t is generated by some B, qt is connected and contains all atoms of q with at least one variable from ti. (The last condition re ects the fact that if a homomorphism from q(a) sends a variable y of an atom P (y; t) 2 q to a nonroot point of a subtree CTB(a) of CT ;A then the other term t must be sent to the same subtree CTB(a).) The terms in tr (if any) are called roots and the variables in ti the interior of t. Assuming that tr = ft1; : : : ; tkg, k 0, we associate with a tree witness t a k-ary predicate twt de ned by the following set of rules: twt(x; : : : ; x)

B(x); if t is generated by B; (1) where B(x) = A(x) if B = A, B(x) = P (x; ) if B = 9P , B(x) = P ( ; x) if B = 9P , and denotes an anonymous existentially quanti ed variable (since the ABox is H-complete, we take only those basic concepts B generating t that are maximal with respect to vT ). If tr 6= ; then (1) makes all the arguments of twt equal, thus complying with h 1(a) = tr. Otherwise, tr = ; and so, twt is a propositional variable and x is existentially quanti ed in the body of (1). As the arguments of twt play identical roles, we can write twt(tr) without specifying any order on the set tr.

Tree witnesses t and t0 are consistent if they intersect only on their common roots: (tr [ ti) \ (t0r [ ti0) tr \ t0r. Each set of pairwise consistent tree witnesses determines a subquery q of q that comprises all atoms of qt, for t 2 . The subquery q is to be mapped to the CTB(a), whereas the remainder q n q , obtained by removing the atoms of q from q, is mapped to ind(A). Thus, the tree-witness rewriting qtw is de ned by the rules for the twt together with the following: qtw(x) (q n q ) ^

for consistent : ^ twt(tr); t2

Theorem 1. For any H-complete (with respect to T ) ABox A and a we have CT ;A j= q(a) i A j= qtw(a).

As de ned, the rewriting qtw is a non-recursive datalog query. In what follows, however, we regard qtw as a UCQ obtained by replacing occurrences of the twt by their de nitions. As an example, consider an ontology T with the axioms

RA v 9worksOn:Project;

Project v 9isManagedBy:Prof; worksOn v involves; isManagedBy v involves

and the CQ asking to nd those who work with professors: q(x)

worksOn(x; y) ^ involves(y; z) ^ Prof(z): CTRA(a) looks as follows: We have two tree witnesses generated by RA: a RA worksOn involves u isManagedBy

v Project involves

Prof t1 = (fxg; fy; zg); for h(x) = a; h(y) = u; h(z) = v; t2 = (fx; zg; fyg); for h(x) = h(z) = a; h(y) = u; and one tree witness t3 = (fyg; fzg) generated by Project. Thus, there are 4 sets of consistent tree witnesses: ;, ft1g, ft2g, ft3g, which give the following rewriting: (2) ind(A), qtw(x) qtw(x) qtw(x) qtw(x) worksOn(x; y); involves(y; z); Prof(z); RA(x); RA(x); Prof(x); worksOn(x; y); Project(y): (3) (4) (5) (6)

The size of the tree-witness rewriting depends on the number of consistent sets of tree witnesses for q and T . There exist CQs and TBoxes whose shortest rewritings are exponential [ 10 ]. Observe, however, that to generate many tree witnesses, the CQ q must have many subqueries that can be homomorphically mapped to some CTB(a), which requires both q and CTB(a) to be quite sophisticated, with q `mimicking' parts of CTB(a) as in the example above. To the best of our knowledge, this does not occurs in real-world CQs and ontologies used for OBDA. More often than not, they do not generate tree witnesses at all. It is also known [11, Theorem 21] that, if the CQ and ontology do not contain fragments as in the (arti cial) example above, then the number of consistent sets of tree witnesses is polynomial. As a result, the UCQ rewriting qtw is typically small in practice, and so further optimisations can be performed quickly. There are two ways of optimising this UCQ. First, we can use a subsumption algorithm to remove redundant CQs from the union: for example, (4) subsumes (5), which can therefore be safely removed. Second, we can reduce the size of individual CQs in the union using the following observation: for any CQ q (viewed as a set of atoms), q c q n fA(x)g; q c q n fA(x)g; q c q n fP (x; y)g; if A0(x) 2 q and A0 vT A and A0 6= A; if R(x; y) 2 q and 9R vT A; if R(x; y) 2 q and R vT P and R 6= P; where c reads `has the same certain answers over H-complete ABoxes.' Surprisingly, such a simple optimisation, especially for 9R vT A, makes rewritings substantially shorter [ 24, 7 ]. 4

From Rewritings over ABoxes to Database Queries The rewriting qtw works only for H-complete ABoxes. Given a mapping M from the database schema R to T , one can de ne H-complete (with respect to T ) ABoxes by taking the composition MT of M and the inclusions in T : A(x) A(x0) '(x; z) '(x0; x1; z) if A0(x) if R(x0; x1) P (x0; x1) '(x0; x1; z); if R(x0; x1) '(x; z) 2 M and A0 vT A; '(x0; x1; z) 2 M and 9R vT A; '(x0; x1; z) 2 M and R vT P: over AI;MT : (Recall that we identify P (x1; x0) with P (x0; x1), in particular, in the heads of the mapping rules.) Clearly, for any database instance I, the virtual ABox AI;MT is H-complete with respect to T . Thus, to compute answers to q over T and a virtual ABox AI;M, it su ces to evaluate the tree-witness rewriting qtw Theorem 2. For any data instance I and any tuple a (T ; AI;M) j= q(a) i AI;MT j= qtw(a). ind(AI;M), we have

Most OBDA systems rst construct rewritings over arbitrary ABoxes and only then unfold them, using mappings, into unions of Select-Project-Join queries, which are evaluated by an RDBMS. By Theorem 2, the same result can be obtained by unfolding rewritings over H-complete ABoxes with the help of the composition MT . However, in practice the resulting SQL query often turns out to be too large [ 19 ].

In Ontop, we also start with MT . But before applying it to unfold qtw, we simplify and reduce the size of MT using the database integrity constraints . A mapping M from R to T is called a T -mapping over if the ABox AI;M is H-complete with respect to T , for any data instance I satisfying . (The composition MT is a T -mapping over any .) Ontop transforms MT to a simpler T -mapping using and SQL features such as disjunctions in lter conditions.

To illustrate, we take a simpli ed IMDb1, whose schema contains relations title[m; t; y] with information about movies (ID, title, production year), and castinfo[p; m; r] with information about movie casts (person ID, movie ID, person role), and an ontology MO,2 describing the application domain in terms of, for example, concepts mo:Movie and mo:Person, and roles mo:cast and mo:year: mo:Movie mo:Movie

9mo:title;

9mo:cast;

mo:Movie v 9mo:year;

9mo:cast v mo:Person:

A mapping that relates the ontology terms to the database schema contains, for example, the following rules: mo:Movie(m) mo:title(m; t) mo:year(m; y) title(m; t; y); title(m; t; y); title(m; t; y): mo:cast(m; p) mo:Person(p) castinfo(p; m; r) castinfo(p; m; r) (7) (8) (9) 4.1

Integrity Constraints for T -mapping Optimisation Suppose a T -mapping M over contains two rules S(x) i(x; z), i = 1; 2. If one of these rules is more speci c than the other, then it can be removed without any change in the virtual ABoxes produced from database instances. To discover such `more speci c' rules, we run the standard query containment check (see, e.g., [ 1 ]) taking account of the inclusion dependencies IND , that is, integrity constraints of the form

8x 9y1 R1(z1) ! 9y2 R2(z2) ; where each Ri is a database relation and each zi contains all the variables from x and yi, possibly in a di erent order. (opt1) If

IND j= 8x 9z 1(x; z) ! 9z 2(x; z) , then M n fS(x) 1(x; z)g is a T -mapping over .

For example, since 9mo:cast vT mo:Movie, the composition MMO of the mapping M de ned by (7){(9) and MO contains the following rules for mo:Movie: mo:Movie(m) mo:Movie(m) title(m; t; y); castinfo(p; m; r): By (opt1), the latter rule is redundant because IMDb contains the foreign key (inclusion dependency)

8m 9p; r castinfo(p; m; r) ! 9t; y title(m; t; y) : 1 http://www.imdb.com/interfaces 2 http://www.movieontology.org The T -mapping optimisation (opt1) turns out to be very e ective in practice. Its power comes from the fact that describes integrity constraints of database instances, while T describes concepts and roles de ned by the mapping over the same data. Essentially, both are theories about the same entities but in di erent languages. Thus, it is no wonder that many inclusions in T are consequences of , which allows us to drastically reduce the size of T -mappings. 4.2

Disjunctions in SQL Another e cient way to reduce the size of a T -mapping is to identify rules whose bodies are equivalent up to lters with respect to constant values. More precisely, let a T -mapping M contain two rules S(x) (x; z); 'i(x; z), for i = 1; 2, such that '1 and '2 are Boolean conditions constructed from built-in predicates (such as = and <). (opt2) The result of replacing S(x) (x; z); 'i(x; z), for i = 1; 2, in M by S(x) (x; z); ('1(x; z) _ '2(x; z)) is a T -mapping over

This optimisation deals with the rules introduced due to the so-called type (discriminating) attributes [ 6 ] in database schemas. For example, the mapping M for IMDb and MO contains six rules for sub-concepts of mo:Person: mo:Actor(p)

castinfo(c; p; m; r); (r = 1); mo:Editor(p)

castinfo(c; p; m; r); (r = 6): The composition MMO contains six rules for mo:Person that di er only in the last condition (r = k), for k = 1; : : : ; 6, and (opt2) reduces them to a single one: castinfo(c; p; m; r); (r = 1) _ _ (r = 6) : Such disjunctions lend themselves to e cient query evaluation by RDBMSs. 4.3

Semantic Index: T -mappings over Materialised ABoxes In addition to working with proper relational data sources, Ontop also supports ABox storage in the form of structureless universal tables : a binary relation CA[id; concept-id] and a ternary relation RA[id1; id2; role-id] represent concept and role assertions. The universal tables give rise to trivial mappings and Ontop implements a technique, the semantic index [20], that takes advantage of SQL features in T -mappings for this scenario. The key observation is that since the IDs in the universal tables CA and RA can be chosen by the system, each concept and role in the TBox T can be assigned a numeric index and a set of numeric intervals in such a way that the resulting T -mapping contains simple SQL queries with interval lter conditions; cf. (opt2). For example, in IMDb, we have mo:Artist v mo:Person; mo:Director v mo:Person; mo:Actor v mo:Artist so we can choose index 1 and interval [ 1,1 ] for mo:Actor, 2 and [ 1,2 ] for mo:Artist, 3 and [ 3,3 ] for mo:Director and 6 and [ 1,6 ] for mo:Person. This will generate a T -mapping with, for instance, mo:Person(p) mo:Artist(p)

CA(p; concept-id); (1 CA(p; concept-id); (1 concept-id concept-id So, by choosing appropriate concept and role IDs, we, on the one hand, e ectively construct H-complete ABoxes without the expensive forward chaining procedure (and the need to store large amounts of derived assertions). On the other hand, the semantic index T -mappings are based on range expressions, which can be evaluated e ciently by RDBMSs using standard B-Tree indexes [ 6 ]. To execute the rewriting qtw over an instance data, one can simply extend qtw with the de nitions of ontology predicates provided by a T -mapping. This would result in an SQL query with subqueries (for the mapping rules). In theory, it can be passed directly to an RDMBS. It is, however, known that RDBMSs are poor at estimating the cost and planning queries with complex subqueries. Instead, Ontop unfolds rewritings and T -mappings into unions of Select-ProjectJoin queries, which are known to be optimal for execution by RDBMSs. The unfolding procedure [ 18 ] applies SLD-resolution to qtw and the T -mapping, and returns those rules whose bodies contain only database atoms (cf. partial evaluation [ 14 ]).

Ontop applies SQO [ 3 ] to rules obtained at the intermediate steps of unfolding. In particular, this eliminates redundant self-Join operations caused by rei cation of database relations by means of concepts and roles. Recall [ 1 ] that, functional dependencies are integrity constraints of the form 8x 8u18u2 9y R(z) ^ 9y R(z[u1=u2]) ! (u1 = u2) ; (10) where R is a database relation, z contains u1 and all the variables in x, y, and z[u1=u2] is the result of replacing u1 in z with u2; x is called the determinant of the dependency. (opt3) If the determinants of a functional dependency (10) coincide in atoms R(z1) and R(z2) then any rule of the form q(x) '(x; y); R(z1); R(z2) can be equivalently replaced by the result of removing duplicate atoms from the body of q(x) '(x; y); R(z1); R(z2[u1=u2]).

Consider, for example, the CQ q(t; y)

mo:Movie(m); mo:title(m; t); mo:year(m; y); (y > 2010) It has no tree witnesses, and so qtw = q. By straightforwardly applying the unfolding to qtw and the T -mapping M de ned by (7){(9), we obtain the query q0tw(t; y)

title(m; t0; y0); title(m; t; y1); title(m; t2; y); (y > 2010); which requires two (potentially) expensive Join operations. However, by using the primary key m of title: 8m 8t18t2 9y title(m; t1; y) ^ 9y title(m; t2; y) ! (t1 = t2) ; 8m 8y18y2 9t title(m; t; y1) ^ 9t title(m; t; y2) ! (y1 = y2) (a functional dependency with determinant m), we reduce two Join operations in the rst three atoms of q0tw to a single atom title(m; t; y): Note that these two Join operations were introduced to reconstruct the ternary relation from its rei cation by means of the roles mo:title and mo:year.

The role of SQO in OBDA systems appears to be much more prominent than in conventional RDBMSs, where it was initially proposed to optimise SQL queries. While some of SQO techniques reached industrial RDBMSs, it never had a strong impact on the database community because it is costly compared to statistics- and heuristics-based methods, and because most SQL queries are written by highly-skilled experts (and so are nearly optimal anyway). In OBDA scenarios, in contrast, SQL queries are generated automatically, and so SQO becomes the only tool to avoid redundant and expensive Join operations [25]. The techniques above prove to be extremely e cient in practice. Moreover, they often automatically produce queries that are similar to those written by human experts. To understand why, we brie y review the process of designing database applications [ 6 ]. It starts with conceptual modelling which describes the application domain in such formalisms as ER, UML or ORM. The conceptual model gives the vocabulary of the database and de nes its semantics by means of hierarchies, cardinality restrictions, etc. The conceptual model is turned into a relational database by applying a series of standard procedures that encode the semantics of the model into a at relational schema. These procedures include: { amalgamating many-to-one and one-to-one attributes of an entity to a single n-ary relation with a primary key identifying the entity (e.g., title with mo:title and mo:year); cf. Section 4.4; { using foreign keys over attribute columns when a column refers to the entity (e.g., title and castinfo); cf. Section 4.1; { using type (discriminating) attributes to encode hierarchical information (e.g., castinfo); cf. Sections 4.2 and 4.3.

As this process is universal, the T -mappings created for the resulting databases are dramatically simpli ed by the Ontop optimisations (opt1){(opt3), and the resulting UCQs are usually of acceptable size and can be executed e ciently by RDBMSs.

Acknowledgements. We thank the Ontop team|Timea Bagosi, Josef Hardi and Mindaugas Slusnys|at the Free University of Bozen-Bolzano for their help in developing the system and running experiments. 20. Rodr guez-Muro, M., Calvanese, D.: Dependencies: Making ontology based data access work. In: Proc. of AMW 2011. vol. 749. CEUR-WS.org (2011) 21. Rodr guez-Muro, M., Kontchakov, R., Zakharyaschev, M.: OBDA with Ontop. In: Proc. of the OWL Reasoner Evaluation Workshop 2013 (ORE 2013). CEUR-WS (2013) 22. Rodr guez-Muro, M., Kontchakov, R., Zakharyaschev, M.: Ontop at work. In: Proc. of OWL: Experiences and Directions Workshop 2013 (OWLED 2013). CEUR-WS (2013) 23. Rosati, R.: Prexto: Query rewriting under extensional constraints in DL-Lite. In:

Proc. of EWSC 2012. LNCS, vol. 7295, pp. 360{374. Springer (2012) 24. Rosati, R., Almatelli, A.: Improving query answering over DL-Lite ontologies. In:

Proc. of KR 2010. AAAI Press (2010) 25. Sequeda, J.F., Miranker, D.P.: Ultrawrap: SPARQL execution on relational data.

Tech. Rep. TR-12-10, University of Texas at Austin. Department of Computer Science (2012)

References

1. Abiteboul , S. , Hull , R. , Vianu , V. : Foundations of Databases. Addison-Wesley ( 1995 )

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

3. Chakravarthy , U.S., Fishman , D.H. , Minker , J.: Semantic query optimization in expert systems and database systems . Benjamin-Cummings Publishing Co., Inc . ( 1986 )

4. Chortaras , A. , Trivela , D. , Stamou , G.: Optimized query rewriting for OWL 2 QL . In : Proc. of CADE-23. LNCS , vol. 6803 , pp. 192 { 206 . Springer ( 2011 )

5. Eiter , T. , Ortiz , M. , Simkus , M. , Tran , T.K. , Xiao , G.: Query rewriting for HornSHIQ plus rules . In: Proc. of AAAI 2012 . AAAI Press ( 2012 )

6. Elmasri , R. , Navathe , S. : Fundamentals of Database Systems . Addison-Wesley, 6th edn. ( 2010 )

7. Gottlob , G. , Orsi , G. , Pieris , A. : Ontological queries: Rewriting and optimization . In: Proc. of ICDE 2011 . pp. 2 { 13 . IEEE Computer Society ( 2011 )

8. Gottlob , G. , Schwentick , T. : Rewriting ontological queries into small nonrecursive datalog programs . In: Proc. of KR 2012 . AAAI Press ( 2012 )

9. Kementsietsidis , A. , Bornea , M. , Dolby , J. , Srinivas , K. , Dantressangle , P. , Udrea , O. , Bhattacharjee , B. : Building an e cient RDF store over a relational database . In: Proc. of the ACM SIGMOD Int. Conf. on Management of Data (SIGMOD 2013 ). ACM ( 2013 )

10. Kikot , S. , Kontchakov , R. , Podolskii , V. , Zakharyaschev , M. : Exponential lower bounds and separation for query rewriting . In: Proc. of ICALP 2012 , Part II . LNCS, vol. 7392 , pp. 263 { 274 . Springer ( 2012 )

11. Kikot , S. , Kontchakov , R. , Zakharyaschev , M. : Conjunctive query answering with OWL 2 QL . In : Proc. of KR 2012 . AAAI Press ( 2012 )

12. Konig, M. , Leclere , M. , Mugnier , M.L. , Thomazo , M.: A sound and complete backward chaining algorithm for existential rules . In: Proc. of RR 2012. LNCS , vol. 7497 , pp. 122 { 138 . Springer ( 2012 )

13. Kontchakov , R. , Lutz , C. , Toman , D. , Wolter , F. , Zakharyaschev , M.: The combined approach to query answering in DL-Lite . In: Proc. of KR ( 2010 )

14. Lloyd , J. , Shepherdson , J.: Partial Evaluation in Logic Programming . The Journal of Logic Programming 11 ( 3-4 ), 217 {242 (Oct 1991 )

15. Lutz , C. , Seylan , I_. , Toman , D. , Wolter , F. : The combined approach to OBDA: Taming role hierarchies using lters . In: Proc. of SSWS+HPCSW 2012. CEURWS , vol. 943 ( 2012 )

16. Perez-Urbina , H. , Motik , B. , Horrocks , I.: A comparison of query rewriting techniques for DL-lite . In: Proc. of DL 2009 . CEUR-WS , vol. 477 ( 2009 )

17. Perez-Urbina , H. , Rodr guez-D az , E., Grove , M. , Konstantinidis , G. , Sirin , E. : Evaluation of query rewriting approaches for OWL 2 . In: Proc. of SSWS+HPCSW 2012 . CEUR-WS , vol. 943 ( 2012 )

18. Poggi , A. , Lembo , D. , Calvanese , D. , De Giacomo , G. , Lenzerini , M. , Rosati , R.: Linking data to ontologies . J. Data Semantics 10 , 133 { 173 ( 2008 )

19. Rodr guez-Muro, M. : Tools and Techniques for Ontology Based Data Access in Lightweight Description Logics . Ph.D. thesis, KRDB Research Centre for Knowledge and Data , Free Univ. of Bozen-Bolzano ( 2010 )