The Combined Approach to Ontology-Based Data Access

1 Ontology-Based Data Access

The paradigm of ontology-based data access (OBDA) has recently emerged as an exciting application of knowledge representation and reasoning technologies in information management systems [Dolby et al., 2008; Heymans et al., 2008; Poggi et al., 2008a]. In a nutshell, the underlying idea is to facilitate access to data by separating the user from the raw data sources using an ontology that provides a user-oriented view of the data and makes it accessible via queries formulated solely in the language of the ontology without any knowledge of the actual structure of the data.

To make this idea more precise, let us assume that the ontology, T , is given by a finite set of sentences of (a suitable fragment of) first-order logic (FO) and the data D by a finite set of ground atoms P(a1, . . . , an) of FO, where the ai are individual names (constants) and P is an n-ary predicate symbol. A query q(⃗x) is an FO-formula with free variables ⃗x, called the answer variables. At its core, the OBDA scenario is typical of the logic-based approach to knowledge representation, where logical theories are employed to represent knowledge, and reasoning is required to unlock that knowledge for applications. In OBDA, the ontology T is typically used to enrich the data with additional vocabulary for querying, to translate between different data and query vocabularies, and for reconciling the different vocabularies of multiple data sources. The data D is assumed to be incomplete to allow for the inference of additional data by means of reasoning. This requires, at least in principle, reasoning over a potentially infinite set of possible models of T and D. Thus, the fundamental query-answering problem we are facing is to decide whether a tuple ⃗a of individual names from D is a certain answer to q over T and D-i.e., whether q(⃗a) is true in every FO-modelMof T and D. In contrast, the relational database paradigm presupposes that the data is complete, so answering a query means checking whether it holds in the single model given by D.

As a simple illustration of OBDA, consider the query

asking for US cities with an airport named after a WW2 hero. Let us assume that we have a database DB with tables for all the relations mentioned in ϕ(x), except the more abstract concept ww2 hero, and with additional tables for ww2 deco (WW2 decoration) and recipient of . Thus, DB contains atoms such as

city(Chicago), has airport(Chicago,ORD), located in(Chicago,US), named for(ORD,O ′Hare), recipient of (O ′Hare, ww2 medal of honor), ww2 deco(ww2 medal of honor).

As DB contains no data for the relation ww2 hero, no answer to ϕ(x) over DB can be found. However, if we describe WW2 heros by means of an ontology H with sentences such as

Chicago becomes an answer to ϕ(x) over H and DB.

To be useful in practice, OBDA should scale to large amounts of data and preferably be as efficient as standard relational database management systems (RDBMSs), where decades of research have been invested to make them scalable. Realistically, this means that we are interested in such ontology and query languages for which OBDA is efficiently reducible to tasks that can be executed using existing RDBMSs. Thus, given T , D and q(⃗x) as above, we want to compute a finite FO model D′ and an FO query q′ (⃗x) such that

(ans) ⃗a is an answer to q′ (⃗x) over D′ if, and only if, ⃗a is a certain answer to q(⃗x) over T and D.

To illustrate the type of reduction we have in mind, observe that querying (H, DB) with ϕ(x) can be reduced to asking ϕ(x) over the extension DB′ of DB with a table for ww2 hero containing all names in DB who are recipients of a WW2 decoration (which can be easily computed). Another possible reduction is to use the same database DB but rewrite the query ϕ(x) to a new query ϕ′ (x), which results from ϕ(x) by replacing the conjunct ww2 hero(z) with

As the size of data is normally large and many different queries can be posed to the same database, at least the following two requirements should supplement (ans):

(dat) D′ is computable in polynomial time in D and does not depend on q(⃗x);

(que) q′ (⃗x) does not depend on D.

There are various possible refinements of these conditions. The query-rewriting approach of [Calvanese et al., 2007] does not allow modifications of the data, so that (dat) is replaced with D′ = D. As a result, this approach is only applicable to description logics for which query-answering belongs to the class AC0 for data complexity (that is, if only the data is regarded as input, whereas the ontology and the query are regarded as fixed). Although guaranteeing the same data complexity as in RDBMSs, the rewriting approach does not impose any restrictions on the size of the 'rewritten' queries q′ (⃗x), which may be exponential in the size of q and so prohibitive for efficient execution by RDBMSs.

In this paper, we suggest a different refinement of conditions (dat) and (que) by taking account of the size of T :

(dat′ ) D′ is computable in polynomial time in both T andD, preferably using RDBMSs;

(que′ ) q′ (⃗x) is polynomial in T and q(⃗x).

These conditions emerge from the combined approach to OBDA suggested in [Lutz et al., 2009; Kontchakov et al., 2010] and aim at scenarios where it is allowed to manipulate the source data (which is not always the case in information integration). The motivation for this approach is twofold. First, by allowing D′ ̸= D, we gain the advantage of much smaller and transparent rewritings q′ (⃗x) of the query. The experimental data we discuss below indicates that this leads to significant performance improvements. Second, the approach advocated here is not confined to the languages for which OBDA is in AC0 for data complexity. As shown in [Lutz et al., 2009], it can be successfully applied to ontology languages for which query-answering is PTIME-complete for data complexity.

Over many years now, the most popular and successful ontology languages are based on description logics. In fact, the DL-Lite family of description logics [Calvanese et al., 2007; Artale et al., 2009] was specifically designed for the rewriting approach to OBDA and is the logical underpinning of the profile OWL2QL of the OWL2 Web Ontology Language. In our exposition of the combined approach below, we focus on a simple member of the DL-Lite family, but also briefly discuss its applicability to the EL family of description logics, which underlies the OWL 2 EL profile of OWL 2.

2 DL-Litehorn

To discuss the main ideas behind the combined approach, we consider the description logic DL-Litehorn [Artale et al., 2009] designed to represent relationships between concepts (unary predicates in FO or classes in OWL) and the domains and ranges of roles (binary relations in FO or properties in OWL). Ontologies in DL-Litehorn, as well as most other description logics, are called TBoxes (T for terminology) and consist of inclusions between concepts. The expressive power of the logic depends then on the constructors available to build concepts. In the case of DL-Litehorn, roles R and concepts C are built from concept names Ai and role names Pi, i ≥ 0, according to the following syntax rules:

and a DL-Litehorn TBox T is a finite set of concept inclusions (CIs) C1 ⊓ · · · ⊓ Cn ⊑ C, where the Ci and C are concepts. Every CI can be regarded as a first-order Horn sentence. For example, ∃P ⊓ ∃P - ⊑ A has exactly the same meaning as ∀x (∃y P (x, y) ∧ ∃y P (y, x) → A(x)).

Thus, TBoxes are interpreted in standard FO structures I = (ΔI ,AIi , P I i )i≥0, where ΔI is a non-empty domain, AIi ⊆ ΔI and P I i ⊆ ΔI ×ΔI . We set ⊤I = ΔI , ⊥I = ∅, (P - i )I = {(x, y) | (y, x) ∈ P I i }, and

so ∃P is interpreted as the domain of P and ∃P - as its range. We write I |= bigsqcapni=1 Ci ⊑ C and say that bigsqcapni=1 Ci ⊑ C is satisfied in I if ⋂ni=1 C I i ⊆ C I .

In description logic, ground atoms of the form A(a) and P(a, b), where A is concept name, P a role name, and a, b individual names, are called concept assertions and role assertions, respectively. An ABox, A, is a finite set of concept and role assertions, which is used to store instance data. In interpretations I, aI is the domain element interpreting the individual name a in I. As usual, I |= A(a) if aI ∈ AI , and I |= P(a, b) if (aI , bI ) ∈ P I .

We denote by Ind(A) the set of individual names occurring in A, and often write P -(a, b) ∈ A instead of P(b, a) ∈ A. A DL-Litehorn knowledge base (KB) is a pair K = (T ,A). An interpretation I is a model of a KB K = (T , A) if I |= α for all α ∈ T ∪ A. We write K |= α whenever I |= α for all models I of K. K is consistent if it has a model. Consistency of DL-Litehorn KBs is known to be PTIME-complete [Artale et al., 2009] for combined complexity.

Example 1. Consider the KB K = (T , {A(a)}), where

Two models of K, called GK and UK, are depicted below:

First-order (FO) queries q(⃗x) to a KB K are constructed from concept and role names (treated as unary and binary predicates) using individual names and variables (called, as usual, terms). We say that a tuple ⃗a ⊆ Ind(A) (of the same length as ⃗x) is an answer to q(⃗x) in an interpretation I if I |= q[⃗a], where q[⃗a] results from replacing the (free) variables ⃗x in q(⃗x) with constants ⃗a. The set of all answers to q in I is denoted by ans(q, I). A tuple ⃗a ⊆ Ind(A) is a certain answer to q(⃗x) over K if I |= q[⃗a] for all models I of K. The set of all certain answers to q over K is denoted by cert(q, K).

Example 2. Let q(x) = ∃y, z (T(x, y) ∧R(y, z) ∧ T(z, y)) and K be as in Example 1. Then a is an answer to q(x) in GK, but not a certain answer to q(x) over K as UK ̸|= q[a].

Conditions (ans) and (dat) cannot be satisfied for arbitrary FO queries-simply because FO is undecidable. Although such queries are allowed in standard database languages such as SQL, most commonly used in practice are conjunctive queries (CQs) of the form q(⃗x) = ∃⃗y ϕ(⃗x, ⃗y), where ϕ is constructed from atomic predicates using only conjunction (in databases, CQs are known as SPJ queries). In more general positive existential queries, disjunction is also allowed in ϕ.

Thus, the problem we are facing now is how to compute, ideally in polynomial time, given a DL-Litehorn KB K = (T ,A) and a CQ q(⃗x), a finite FO-structure GK, independently from q(⃗x), and an FO-query q′ (⃗x), independently from A, such that (ans) holds: for every tuple ⃗a ⊆ Ind(A), ⃗a ∈ cert(q,K) if, and only if, ⃗a ∈ ans(q′ , GK). The key to a solution is the well-known property of Horn theories: the existence of least Herbrand, or canonical, models which give all correct answers to CQs [Apt, 1990]. (We note here that all ontology languages used for OBDA so far are sub-languages of the Horn fragment of FO, which is not able to express any kind of disjunctive information.)

3 Canonical Models

To construct the canonical model, UK, for a DL-Litehorn KB K = (T , A), we start with A and then exhaustively apply the CIs from T , always introducing new elements in role domain and ranges if necessary (as in Example 1). Formally, the domain of UK consists of paths of the form acR1 · · · cRn , n ≥ 0, such that a ∈ Ind(A) and the following conditions hold:

(agen) K |= ∃R1(a) but R1(a, b) /∈ A for all b ∈ Ind(A), in which case we write a ⇝ cR1 ;

We denote the last element in a path σ by tail(σ), and define UK by taking:

The following theorem, reflecting the fact that any model of K contains a homomorphic image of UK, provides a basis for reductions of OBDA to query-answering in RDBMSs:

Theorem 3. For every consistent DL-Litehorn KB K and every positive existential query q, cert(q, K) = ans(q, UK).

The consistency check K |= ⊥ required in this theorem can be easily encoded as an FO-query over K. So the real problem here is how to cope with the fact that UK can be large, even infinite.

Note first that, although UK can be infinite, its structure is quite regular: we have a 'kernel' given by the ABox A, each element a of which is a root of a tree with branches of the form a ⇝ cR1 ⇝ · · · ⇝ cRn , where the cRi represent 'witnesses' for the existential restrictions ∃Ri. The concepts from T to which the elements of UK belong are computed (in polynomial time) by applying the 'rules' in T : for instance, acR1 · · · cRn ∈ AUK if, and only if, T |= ∃Rn ⊑ A.

This suggests two ways of encoding UK. The rewriting approach of [Calvanese et al., 2007], illustrated by the query ϕ′ (x) from the introduction, 'builds' T into the rewritten query, independently of A. We give another example demonstrating the underlying idea:

Example 4. Take again the TBox T from Example 1 and let q(x) = ∃yR(x, y). An element a ∈ Ind(A) is an answer to q(x) in UK if either R(a, y) is in A, for some y, or R(a, y) is entailed by A and T . By inspecting T , we see that R(a, y) can only be entailed by either B(a) or T(z, a), for some z. Thus, a is an answer to q(x) over (T ,A) if, and only if, a is an answer to q(x) ∨ B(x) ∨ ∃z T (z, x) over A.

This rewriting technique reduces the OBDA problem '(T ,A) |= q(⃗x)?' for DL-Litehorn KBs to the RDBMS problem 'A |= q′ (⃗x)?' where q′ depends on q and T only. Thus, it complies with conditions (ans), (dat) and (que) and shows that answering positive existential queries over DL-Litehorn KBs is in AC0 for data complexity [Calvanese et al., 2007], the same as RDBMS query answering. However, the size of q′ (⃗x) in all reductions known so far is exponential in |q|, O((|T | · |q|)|q| ) in the worst case, and even modern RDBMSs struggle with such queries.

The combined approach of [Kontchakov et al., 2010] encodes UK in a finite FO structure, GK, by identifying all paths σ of UK with the same tail(σ)-all of them belong to the same concepts by the definition of UK-as illustrated in Example 1. Thus, the generating model GK of K is defined as follows:

The generating model GK can be constructed in polynomial time in |K|, thus complying with condition (dat′ ). In Section 5, we discuss how this can be done using RDBMSs. The canonical model UK can be viewed as the 'unraveling' of GK, with the map tail : ΔUK → ΔGK being a homomorphism from UK onto GK. As positive existential queries are preserved under homomorphisms, we obtain from Theorem 3:

Theorem 5. For every consistent DL-Litehorn KB K and every positive existential query q, cert(q,K) = ans(q, UK) ⊆ ans(q, GK).

As we saw in Example 2, the converse inclusion does not hold because by identifying elements in UK we ruin its tree structure. Here is another example:

Example 6. Suppose that K = (T , {A(a),A(b)}), where T is as in Example 1. Consider the 'fork-shaped' query q(x1, x2) = ∃y (T (x1, y) ∧T (x2, y)). Then GK and UK look as depicted below:

So we have GK |= q2[a, b], while UK ̸|= q2[a, b].

The domain of the generating model GK consists of Ind(A) and those elements of the 'witness set'

that are accessible from Ind(A) via the relation ⇝. In the combined approach, GK is computed in a preprocessing step-independently of any queries-and stored in the database. We shall discuss preprocessing in Section 5. But before that let us see how to get rid of the spurious answers to queries which can be given by GK as in Examples 2 and 6.

4 Conjunctive Query Answering

Suppose we are given a CQ q(⃗x) = ∃⃗y ϕ(⃗x, ⃗y). Our aim is to rewrite q to an FO query q† (⃗x) in such a way that (i) for every DL-Litehorn KB K = (T ,A), cert(q,K) = ans(q† , GK) and (ii) the size of q† is polynomial in the size of q. We define the rewriting q† as a conjunction

where ϕ1, ϕ2 and ϕ3 are Boolean combinations of equalities t1 = t2, and each of the ti is either a term in q or a constant cR ∈ RT . The purpose of the conjunct

is to ensure that the answer variables ⃗x receive their values from Ind(A) only, as the witnesses cR are 'implicit' elements of unknown identity and hidden from the user (labelled nulls, in the database parlance).

The conjuncts ϕ2 and ϕ3 are closely related and serve the purpose of filtering out the spurious answers discussed in Examples 2 and 6. The idea is to prevent any assignments that cannot be 'reproduced' in the canonical model UK. Due to the forest structure of UK, this requirement imposes strong constraints on the way how variables can be matched to the RT part of GK. Essentially, the part of q that is mapped to RT must be homomorphically embeddable into a forest. This intuition is captured by the following definition. Let (RT )∗ be the set of all finite words over RT (including the empty word ε). To simplify notation, we identify q with the set of its atoms and use P -(t, t′ ) ∈ q as a synonym of P(t′ , t) ∈ q.

Definition 7. Let q be a CQ and R(t, t′ ) ∈ q. A partial function f from the terms of q to (RT )∗ is a tree witness for (R, t) in q if its domain is minimal (with respect to set-theoretic inclusion) such that f(t) = ε and, for all atoms S(s, s′ ) ∈ q,

- if f(s) = ε then f(s′ ) = cR provided that R = S, and

A tree witness for (R, t) in q does not exist if, starting from R(t, t′ ), we can reach some term s in q via two different paths, which would give different values for fR,t(s) (see Example 8). But if one exists then it is unique, and we denote it by fR,t. Note that, by (rgen), GK has no paths of the form σcScS, which is reflected by the two cases in the second item of the definition.

Example 8. Let q = {R(y1, y2), S(y2, y3), S(y4, y3)}. Then the tree witnesses for (R, y1) and (S, y4) in q are:

For the cyclic query q = {T(x, y),R(y, z), T(z, y)} from Example 2, there exists no tree witness for (R, y) because we must have both fR,y(y) = ε and fR,y(y) = cRcT -, contrary to fR,y being a function. Similarly, no tree witnesses exist for (R-, z), (T, z) or (T -, y) in q.

Intuitively, the tree witness fR,t addresses those assignments π where π(t) is an ABox element but π(t′ ), for R(t, t′ ) ∈ q, is not (and so π(t′ ) = cR), by recording consequences of the fact that we must be able to reproduce π in UK: if fR,t(s) = σcS, then π has no other choice than to map s to cS, and if fR,t(s) = ε, then π must map s to π(t).

The conjunct ϕ2 implements the matching dictated by the tree witnesses. It turns out that the matches determined by fR,t also apply when t is not mapped to an ABox element. This, in turn, means that it suffices to enforce such matches for the terms s with fR,t(s) = ε:

Example 9. We illustrate ϕ2 using the 'fork-shaped' query q(x1, x2) = ∃y (T(x1, y) ∧ T(x2, y)) from Example 6. As fT,x1 (x2) = ε, we have (y = cT ) → (x1 = x2) in ϕ2, which prevents the spurious match {x1 ↦→ a, y ↦→ cT , x2 ↦→ b} of Example 6.

If the tree witness for (R, t) in q does not exist, then there are two paths from R(t, t′ ) to some term s in q. As any element σ of UK may have only one R-successor of the form σcR, this means that t′ in every R(t, t′ ) ∈ q must be mapped to an ABox element. This is ensured by the conjunct

Example 10. We illustrate ϕ3 using the 'cyclic' query q(x) = ∃y, z (T (x, y) ∧ R(y, z) ∧ T (z, y)) from Example 2. As shown in Example 8, there exist no tree witnesses for (R, y) (R-, z), (T, z) and (T -, y). This gives four conjuncts (z ̸= cR), (y ̸= cR-), (y ̸= cT ) and (z ̸= cT -) of ϕ3, which prevent the spurious matches of Example 2.

Theorem 11. For every DL-Litehorn KB K and every CQ q, ans(q† , GK) = ans(q, UK).

Given a CQ q(⃗x) and R(t, t′ ) ∈ q, it can be decided in time O(|q|) whether a tree witness for (R, t) in q exists. If it does exist, the tree witness can be computed in time O(|q|). It follows that q† can be computed in polynomial time in the size of the query q and the set RT . The length of q† is O(|q| · |T |) since ϕ1 is of length O(|q| · |T |), ϕ3 is of length O(|q|) and ϕ2 can be made of length O(|q|) as well by observing that, for each R, the condition fR,t(s) = ε induces an equivalence relation on terms. If we add a unary relation aux identifying exactly the elements of RT , then we can replace ϕ1 with ϕ′1 = ∧x∈⃗x ¬aux(x) and obtain q† of size O(|q|).

5 GeneratingModel by Views

To make the combined approach to OBDA work in practice, it is important to find a feasible way of extending the ABox A stored in the RDBMS to the generating model GK. This is all the more important as we have to reflect the changes to GK whenever facts are added to or deleted from A. Our solution is to use FO-queries to define views in the RDBMS that compute the extensions of the concept and role names in GK when executed on A. We illustrate this idea by an example and refer the reader to [Kontchakov et al., 2010] for details.

Example 12. Consider the TBox T from Example 1. We have to construct views qA(x), qB(x), qT (x, y) and qR(x, y) the answers to which over A are AGK , BGK , T GK and RGK , respectively. For example, a first attempt to design qB(x) might be the following query:

The first two disjuncts reflect the ways concept B can be entailed given T ; the last disjunct is meant to reflect the fact that cT ∈ BGK when cT is in the domain of GK. However, cT does not belong to GK if there is no element a of the ABox A that 'generates' cT , i.e., a ⇝ · · · ⇝ cT , and thus the answer returned by q′B may be too large. Fortunately, the condition 'cT is generated by an element a of the ABox' can be expressed by another FO-query, which in this case is simply gT (a) = A(a) ∧ ¬∃y T (a, y); cf. GK in Example 1. Thus we can refine the last disjunct of q′B and obtain the desired query:

The remaining views are constructed analogously.

In general, FO-queries such as qA(x) and qR(x, y) in the example above can be of exponential size in |T |. However, they always contain only polynomially many distinct subqueries, and therefore can be represented by means of polynomial non-recursive Datalog programs or a polynomial number of views of an RDBMS.

In DL-Litecore [Calvanese et al., 2007], which results from DL-Litehorn by disallowing conjunctions in CIs apart from those in disjointness constraints of the form A ⊓ B ⊑ ⊥ and roughly corresponds to OWL2QL without role inclusions, the FO-queries qA(x) and qR(x, y) are of linear size even without structure sharing. Since these queries can be

'plugged' into the query q† defined in Section 4, this yields a new implementation of the rewriting approach to OBDA. Remarkably, for the first time we achieve pure query rewriting with only a polynomial blowup of the query (which also works for the extension of DL-Litecore with role functionality constraints under the unique name assumption).

6 Experimental Evidence

Pure query rewriting for the extension of DL-Litecore with role inclusions has been implemented in the systems QuOnto [Acciarri et al., 2005; Poggi et al., 2008b], REQUIEM [P´erezUrbina et al., 2009], Presto [Rosati and Almatelli, 2010] and Nyaya [Gottlob et al., 2011]. They all rewrite CQs q into unions Q of CQs with exponentially many components (in the length of q) in the worst case, and use various query optimisation techniques to reduce the size of Q. The reduction is in some cases quite substantial, but none of the rewritings avoids an exponential blowup in the worst case.

In the combined approach, we separate inference from query processing and construct the generating models, which take care of the ontology. As a result, the rewritings of CQs over DL-Litehorn ontologies (without role inclusions) are always linear. Moreover, their simple structure ensures that answers to queries can be computed by first evaluating the original query in the generating model, and then filtering out (a small number of) tuples violating one of ϕ1, ϕ2, ϕ3. This provides true scalability comparable to RDBMSs, which is confirmed by experiments in [Kontchakov et al., 2010] showing that CQ answering with our approach is competitive in performance with executing the original queries over the data. The price we have to pay for this is the construction and maintenance of the generating model GK, which, as discussed above, can be implemented by using materialised views and then relying on the RDBMS to maintain them and propagate ABox updates. In the worst case, the size of GK is O(|A| · |T |). In practice, the experiments of [Kontchakov et al., 2010] with Galen-Lite indicate that materialization of GK results in a five-fold increase of the size of the data, and the tests of [Calvanese and Rodr´ıguez-Muro, 2011] on Stanford's BioPortal Resource Index show even a tenfold increase. In both cases, the main cause of the increase is the depth of the concept hierarchies in the considered ontologies. Interestingly, [Calvanese and Rodr´ıguez-Muro, 2011] demonstrate that the increase can be curbed, at least for DL-Litecore, by using an encoding of concept hierarchies as nested intervals (see also [DeHaan et al., 2003]).

7 Extensions and Variations

To simplify presentation, we have only considered a rather small fragment of the languages investigated in [Kontchakov et al., 2010]. First, by adopting the unique name assumption (UNA), the combined polynomial rewriting can be extended to DL-Litehorn enriched with unqualified number restrictions. (Without the UNA, conjunctive query answering becomes CONP-complete for data complexity [Artale et al., 2009]; note that in the case of DL-Litehorn considered in this paper, query answers agree with and without UNA.) For the extension of DL-Litehorn with role inclusions (i.e., expressions of the form R1 ⊑ R2), one can polynomially reduce conjunctive query answering to answering positive existential queries over TBoxes without role inclusions. At the price of a worst-case exponential blowup, the latter problem can then be reduced to answering unions of conjunctive queries; for details and side conditions, we refer the reader to [Kontchakov et al., 2010]. We note that the blowup encountered in second reduction depends only on the size of the query and on the number of role inclusions, which is typically very small in real-world ontologies.

The combined approach can also be applied to the description logic EL, which is used for large scale medical terminologies such as SNOMED CT. In contrast to DL-Lite, in EL one can qualify existential restrictions and use CIs such as ∃R.A ⊓ C ⊑ ∃R.B; however, EL does not have inverse roles. Conjunctive query answering for EL ontologies is PTIMEcomplete for data complexity, and so the rewriting approach is not applicable in this case. In [Lutz et al., 2009], the combined approach is developed for the extension ELHdr ⊥ of EL with the inconsistent concept, role inclusions, and domain and range restrictions. Although the structures of the generating models and rewritten queries are quite different from the DL-Lite case, their size is still polynomial in T and q, respectively. Here we only illustrate the polynomial representation of canonical models for EL KBs.

Example 13. Let K = (T , {C(a)}), where

The canonical model UK and the generating model GK are:

Note that the generating model GK may contain an extra element c∃R.C for each existential quantifier ∃R.C in the TBox.

Our results for DL-Lite and EL suggest a variety of future research problems. For instance, it would be of great interest to find out how the rewritings used for DL-Lite and EL can be combined so as to cover other Horn descriptions logics such as ELI or Horn-SHIQ, which use both inverse roles and qualified existential restrictions. In this case, it seems likely that the extension of the data has to be exponential in the size of the input TBox, in the worst case. As noted in [Lutz et al., 2009], DLs for which conjunctive query answering is not in PTIME for data complexity (such as ALC and SHIQ, unless PTIME = NP) necessarily involve an extension of the data that is exponential in the size of the input ABox, which we consider useless for practical purposes. It would also be of interest to investigate the combined approach for more expressive ABoxes and/or queries. First results on how the combined approach can be extended so as to cover ABoxes and queries with 'epistemic' negation are presented in [Lutz et al., 2009]. Another interesting direction is to consider the Datalog± family of languages [Gottlob et al., 2011].

Acknowledgments. This work was partially supported by the U.K. EPSRC grants EP/H05099X/1 and EP/H043594/1, by the DFG SFB/TR 8 "Spatial Cognition", and by NSERC.