Introduction

Ontology-based data access (OBDA) [2] is a recent application of Description Logics (DLs) that is gaining momentum. The idea behind OBDA is to use a DL ontology as a means to access a set of data sources, so as to mask the user from all applicationdependent aspects of data, and to extract useful information from the sources based on a conceptual representation of the domain, expressed as a TBox in a suitable DL. In current approaches to OBDA, the intensional level of the ontology (the TBox) is fixed once for all at design time, and the mapping assertions specify how the data at the sources correspond to instances of the concepts, roles, and attibutes in the TBox. More precisely, the various mapping assertions determine a sort of virtual ABox, in which the individual objects are built out from data, and the instance assertions are specified through the relationships between the sources and the elements of the ontology.

Several OBDA projects have been carried out in the last years [9], and OBDA systems have been designed to support OBDA applications [1]. The experience gained in this work has shown that there are important aspects that are missing in current OBDA technology. In this paper, we concentrate on three such aspects.

The first aspect is related to the need of making the intensional level of the ontology more dynamic. Indeed, in real applications, the information about which are the concepts and roles that are relevant in the domain of interest is often stored in the data sources. Consider, for example, the database D of a motor industry shown in figure 1, storing data about different types of cars (table T-CarTypes), and various cars of such types (table T-Cars) manufactured by the firm. The key observation is that the database D stores information not only about the instances of concepts, but also about the concepts themselves, and their relationships. For example, table T-CarTypes tells us that there are four concepts in our ontology that are subconcepts of the concept Car, and, implicitely, tells us that they are mutually disjoint. hand, provides information about the instances of the various concepts, as well as other properties about such instances.

The second aspect is related to the need of metamodeling constructs in the language used to specify the ontology [4,6]. Metamodeling allows one to treat concepts and properties as first-order citizens, and to see them as individuals that may constitute the instances of other concepts, called meta-concepts. In our example, it is convenient to introduce in the ontology the concept Car-Type, whose instances are exactly the subconcepts of cars stored in table T-CarTypes. In this way, we allow users to dynamically acquire knowledge about relevant car types through simple queries asking for the instances of the meta-concept Car-Type.

The third aspect deals with the need of designing tractable algorithms for query answering in OBDA systems. In [8], it is argued that, since the data sources used in OBDA systems are likely to be very large, such systems should be based on DLs that are tractable in data complexity. In particular, [8] advocates the use of the DL-Lite family, that allows for First-Order Logic (FOL) rewritability of (unions of) conjunctive queries. We remind the reader that in a DL enjoing FOL rewritability, query answering can be divided in two steps. In the first step, called rewriting, using the TBox only, the query q is transformed into a new FOL query q , and in the second step q is evaluated over the ABox. The correctness of the whole method relies on the fact the answers to q over the ABox coincide with the certain answers to q over the whole ontology. The challenge is now to design tractable query answering algorithms even in cases where the mappings relate data at the sources both to the extensional and the intensional level of the ontology, and meta-concepts and meta-roles are used in the queries. In this paper, we address the above aspects, and present the following contributions.

(i) We introduce the notion of mapping-based knowledge base (MKB) (Section 3), to formalize the situation where both the extensional and the intensional level of the ontology are determined by suitable mapping assertions involving the data sources.

(ii) We describe the higher-order DL Hi (DL-Lite R ) (Section 2), based on the approach presented in [5]. In that paper, it is shown how, starting from a traditional DL L, one can define its higher-order version, called Hi(L). Here, we apply this idea, and present Hi (DL-Lite R ), which is the higher-order version of DL-Lite R [3].

(iii) We show that answering queries posed to MKBs expressed in Hi (DL-Lite R ) can be done efficiently through FOL rewriting (Section 4). More specifically, we describe an algorithm that, given a query q over a MKB, rewrites q into a FOL query that is evaluated taking into account only the mapping assertions M A of the MKB involving the extensional level of the ontology. Hence query answering can be delegated to a DBMS, as in the case of traditional OBDA systems.

2 Higher-order DL-Lite R In this section, we describe the higher-order DL Hi (DL-Lite R ), based on the approach presented in [5]. Every traditional DL L is characterized by a set OP (L) of operators, used to form concept and role expressions, and a set of MP (L) of meta-predicates, used to form assertions. Each operator and each meta-predicate have an associated arity. If symbol S has arity n, then we write S/n to denote such a symbol and its arity. For DL-Lite R , we have

-OP (DL-Lite R ) = {Inv /1, Exists/1}; -MP (DL-Lite R ) = {Inst C /2, Inst R /3, Isa C /2, Isa R /2, Disj C /2, Disj R /2}.

We assume that the reader is familiar with DL-Lite R . Therefore, the intuitive meaning of all the above symbols should be clear. The formal specification of their semantics will be given shortly. Syntax. We assume the existence of two disjoint, countably infinite alphabets: S, the set of names, and V, the set of variables. Intutively, the names in S are the symbols denoting the atomic elements of a Hi(DL-Lite R ) knowledge base. The building blocks of such a knowledge base are assertions, which in turn are based on terms and atoms.

We inductively define the set of terms, denoted by τ DL-Lite R (S, V), over the alphabets S and V for Hi(DL-Lite R ) as follows:

-

if E ∈ S then E ∈ τ DL-Lite R (S, V); -if V ∈ V then V ∈ τ DL-Lite R (S, V); -if C/n ∈ OP (DL-Lite R ) and t 1 , . . . , t n ∈ τ DL-Lite R (S, V) then C(t 1 , . . . , t n ) ∈ τ DL-Lite R (S, V).

Ground terms, i.e., terms without variables, are called expressions, and the set of expressions is denoted by τ DL-Lite R (S).

A DL-Lite R -atom, or simply atom, over the alphabets S and V for Hi(DL-Lite R ) is a statement of the form M (E 1 , . . . , E n ) where M ∈ MP (DL-Lite R ), n is the arity of M , and for every 1 ≤ i ≤ n, E i ∈ τ DL-Lite R (S, V). If X is a subset of V, a is a DL-Lite R -atom, and all variables appearing in a belongs to X, then a is called an X-atom in DL-Lite R .

Ground DL-Lite R -atoms, i.e., DL-Lite R -atoms without variables, are called DL-Lite R -assertions, or simply assertions. Thus, an assertion is simply an application of a meta-predicate to a set of expressions. Intuitively, an assertion is an axiom that predicates over a set of individuals, concepts or roles.

A Hi(DL-Lite R ) knowledge base (KB) over S is a set of DL-Lite R -assertions over S. To agree with the usual terminology of DLs, we use the term TBox to denote a set of Isa C , Isa R , Disj C and Disj R assertions, and the term ABox to denote a set of Inst C and Inst R assertions. Semantics. Our definition of semantics for Hi (DL-Lite R ) is based on the notion of interpretation structure. An interpretation structure is a triple Σ = ∆, I c , I r where: (i) ∆ is a non-empty (possibly countably infinite) set; (ii) I c is a function that maps each d ∈ ∆ into a subset of ∆; and (iii) I r is a function that maps each d ∈ ∆ into a subset of ∆ × ∆. In other words, Σ treats every element of ∆ simultaneously as: (i) an individual; (ii) a unary relation, i.e., a concept, through I c ; and (iii) a binary relation, i.e., a role, through I r .

An interpretation for S (simply called an interpretation, when S is clear from the context) over the interpretation structure Σ is a pair I = Σ, I o , where -Σ = ∆, I c , I r is an interpretation structure, and -I o is a function that maps: 1. each element of S to a single object in ∆; and 2. each element C/n ∈ OP (DL-Lite R ) to an n-ary function C Io : ∆ n → ∆ that satisfies the conditions characterizing the operator C/n. In particular, the conditions for the operators in OP (DL-Lite R ) are as follows:

(a) for each

d 1 ∈ ∆, if d = Inv Io (d 1 ) then d Ir = (d Ir 1 ) −1 ; (b) for each d 1 ∈ ∆, if d = Exists(d 1 ) then d Ic = {e | ∃e 1 s.t. e, e 1 ∈ d Ir 1 }. We extend I o to ground terms in τ DL-Lite R (S) inductively as follows: if C/n ∈ OP (DL-Lite R ), then (C(t 1 , . . . , t n )) Io = C Io (E Io 1 , . . . , E Io n ).

We now turn our attention to the interpretation of terms in Hi (DL-Lite R ). To interpret non-ground terms, we need assignments over interpretations, where an assignment µ over Σ, I o is a function µ : V → ∆. Given an interpretation I = Σ, I o and an assignment µ over I, the interpretation of terms is specified by the function

(•) Io,µ : τ DL-Lite R (S, V) → ∆ defined as follows: -if t ∈ S then t Io,µ = t Io ; -if t ∈ V then t Io,µ = µ(t); -if t is of the form C(t 1 , . . . , t n ), then t Io,µ = C Io (t Io,µ 1 , . . . , t Io,µ n

). Finally, we define the semantics of atoms, by defining the notion of satisfaction of an atom with respect to an interpretation I and an assignment µ over I as follows:

-

I, µ |= Inst C (E 1 , E 2 ) if E Io,µ 1 ∈ (E Io,µ 2 ) Ic ; -I, µ |= Inst R (E 1 , E 2 , E 3 ) if E Io,µ 1 , E Io,µ 2 ∈ (E Io,µ 3 ) Ir ; -I, µ |= Isa C (E 1 , E 2 ) if (E Io,µ 1 ) Ic ⊆ (E Io,µ 2 ) Ic ; -I, µ |= Isa R (E 1 , E 2 ) if (E Io,µ 1 ) Ir ⊆ (E Io,µ 2 ) Ir ; -I, µ |= Disj C (E 1 , E 2 ) if (E Io,µ 1 ) Ic ∩ (E Io,µ 2 ) Ic = ∅; -I, µ |= Disj R (E 1 , E 2 ) if (E Io,µ 1 ) Ir ∩ (E Io,µ 2 ) Ir = ∅.

A Hi (DL-Lite R ) KB H is satisfied by I if all the assertions in H are satisfied by I1 . As usual, the interpretations I satisfying H are called the models of H. A Hi (DL-Lite R ) KB H is satisfiable if it has at least one model.

Mapping-based knowledge bases

As we said in the previous section, a Hi (DL-Lite R ) KB is simply a set of assertions. One might think of such a set of assertions as explicitly stated by the designer of the KB. This is a reasonable assumption only in those cases where the ontology is managed by an ad-hoc system, and is built from scratch for the specific application. However, in many applications, it is of interest to derive the KB directly from a set of data sources, so that the assertions of the KB are defined by specific mappings to such data sources. The resulting notion will be called mapping-based knowledge base.

In the following, we assume that the data sources are expressed in terms of the relational data model. In other words, all the technical development presented in the rest of this section assumes that the set of sources to be linked to the knowledge base is one relational database. Note that this is a realistic assumption, since many data federation tools are now available that are able to wrap a set of heterogeneous sources and present them as a single relational database.

When mapping relational data sources to a knowledge base over S, one should take into account that sources store "data values", and such data values should not be confused with the elements in S. To face this impedance mismatch problem, [8] proposes to structure the mapping assertions in such a way that the elements of the knowledge base are denoted by terms built out from data values stored at the sources using special function symbols. Although we could in principle follow the same idea here, for the sake of simplicity, in this paper we assume that the relational data sources store directly elements of S. Note, however, that all the results presented in the next sections easily extend to the case where mappings build complex terms for denoting the elements of the knowledge base.

We are now ready to provide the definition of mapping-based knowledge base.

Definition 1. A Hi (DL-Lite R ) mapping-based knowledge base (MKB) is a pair K = DB , M such that: (i) DB is a relational database; (ii) M is a mapping, i.e. a set of mapping assertions, each one of the form Φ(x) ; ψ, where Φ is an arbitrary FOL query over DB of arity n > 0 with free variables x = x 1 , . . . , x n , and ψ is an X-atom in DL-Lite R , with X = {x 1 , . . . , x n }.

In the following, if K = DB , M is a MKB, then we denote by M A the set of mapping assertions from M whose head predicate is either Inst C or Inst R . Furthermore, we denote by M T the set M \ M A , i.e., the set of mapping assertions from M whose head predicate belongs to the set {Isa C , Isa R , Disj C , Disj R }. We call a mapping M an instance-mapping if M = M A , i.e., if the metapredicates Inst C and Inst R are the only ones to appear in the right-hand side of the mapping assertions in M.

In order to define the semantics of a Hi (DL-Lite R ) MKB K = DB , M , we need to define when an interpretation satisfies an assertion in M with respect to a database DB . To this end, we make use of the notion of ground instance of an atom, and the notion of answer to a query over DB . Let ψ be an X-atom with X = {x 1 , . . . , x n }, and let v be a tuple of arity n with values from DB . Then the ground instance ψ[x/v] of ψ is the formula obtained by substituting every occurrence of x i with v i (for i ∈ {1, .., n}) in ψ. Also, if DB is a relational database, and q is a query over DB , we write ans(Φ, DB ) to denote the set of answers to q over DB .

We now specify when an interpretation satisfies a mapping assertion with respect to a database. We say that an interpretation I satisfies the mapping assertion Φ(x) ; ψ with respect to the database DB , if for every tuple of values v ∈ ans(Φ, DB ), the ground atom ψ[x/v] is satified by I. We say that I is a model of K = DB , M if I satisfies every assertion in M with respect to DB .

The following example shows how Hi (DL-Lite R ) mapping-based knowledge bases can be used to model real world situations in a suitable manner.

Example 1. Consider the database D shown in the introduction. We define a Hi (DL-Lite R ) MKB K 1 = D, M , where the mapping M is defined as follows:

-M1: {y | T-CarTypes(x, y)} ; IsaC (y, Car) -M2: {(x, z) | T-Cars(x, y, t, u, v, q) ∧ T-CarTypes(y, z)} ; InstC (x, z) -M3: {(x, y) | T-CarTypes(z1, x) ∧ T-CarTypes(z2, y) ∧ x = y} ; Disj C (x, y)

Intuitively, M1 states that every type of car (whose name appears in the second column of table T-CarTypes, i.e. Coupé, SUV, Sedan, etc.) is a Car. M2, instead, indicates how to correctly retrieve the instances of different types of cars (e.g. car with plate number AB111 has to be retrieved as an instance of the concept Coupé, cars with plate numbers AF333 and BR444 as instances of the concept SUV, and so on). Finally, the intended meaning of assertion M3 is that different types of cars are pairwise disjoint (e.g. a Coupé is not a SUV, a SUV is not a Sedan, and so on). Obviously, mapping assertions are always written by people who know the semantics of the information stored in the database. Notice that the mapping assertions in M are able to model the car-types hierarchy without knowing a priori (i.e. at design-time) all the different kinds of cars that are produced by the motor industry.

Suppose now that the motor industry decides to introduce new types of cars to its car fleet, and in particular it decides to produce Campers and Caravans as well, thus extending the hierarchy. As one can imagine, these new kinds of cars share some common characteristics with the previous car types, even though not all of them. Therefore, it might be a reasonable choice for the database designers to introduce a new relational The new situation can be modeled in our framework by simply adding to M the following mapping assertions: where mapping M4 states that the new kinds of cars (Camper and Caravan) are Cars, the second assertion indicates how to correctly retrieve their instances, (e.g. car with plate number CM777 as an instance of Camper), and mapping M6 states that the new types of cars are pairwise disjoint (i.e. a Camper is not a Caravan). Notice that if (instead of creating a new table) the new kinds of cars had been simply introduced into the initial table T-CarTypes (thus without modifying D in any way), the new concepts (Camper and Caravan) would been automatically detected at run-time by mappings M1-M3, whitout requiring any further mapping definition.

Next, we introduce the notion of query, which in turn relies on the notion of "query atom". Intuitively, a query atom is a special kind of atom, constituted by a metapredicate applied to a set of arguments, where each argument is either an expression or a variable. More precisely, we define the set of q-terms to be τ DL-Lite R (S) ∪ V. We define a query atom as an atom constituted by the application of a meta-predicate in MP (DL-Lite R ) to a set of q-terms, and we call a query atom ground if no variable occurs in it. A query atom whose meta-predicate is Inst C or Inst R is called an instancequery atom. A higher-order conjunctive query (HCQ) of arity n is an expression of the form q(x 1 , . . . , x n ) ← a 1 , . . . , a m where q, called the query predicate, is a symbol not in S ∪ V, every x i belongs to V, every a i is a (possibly non-ground) query atom, and all variables x 1 , . . . , x n occur in some a j . The variables x 1 , . . . , x n are called the free variables (or distinguished variables) of the query, while the other variables occurring in a 1 , . . . , a m are called existential variables. A HCQ constituted by instance atoms only is called an instance HCQ (IHCQ). A higher-order union of conjunctive queries (HUCQ) of arity n is a set of HCQs of arity n with the same query predicate. A HUCQ constituted by instance HCQs only is called an instance HUCQ (IHUCQ). A HCQ/HUCQ is called Boolean if it has no free variables.

Let I be an interpretation and µ an assignment over I. A Boolean HCQ q of the form q ← a 1 , . . . , a n is satisfied in I, µ if every query atom a i is satisfied in I, µ. A Boolean HUCQ Q is satisfied in I, µ if there exists a Boolean HCQ q ∈ Q that is satisfied in I, µ. A Boolean HUCQ Q is satisfied in I, written I |= Q, if there exists an assignment µ over I such that Q is satisifed in I, µ. Given a Boolean HUCQ Q and a Hi (DL-Lite R ) KB K, we say that Q is logically implied by K (denoted by K |= Q) if for each model I of K there exists an assignment µ such that Q is satisfied by I, µ.

Given a non-Boolean HUCQ q of the form q(t 1 , . . . , t n ) ← a 1 , . . . , a m , a grounding substitution of q is a substitution θ such that t 1 θ, . . . , t n θ are ground terms. We call t 1 θ, . . . , t n θ a grounding tuple. The set of certain answers to q in K is the set of grounding tuples t 1 θ, . . . , t n θ that make the Boolean query q θ ← a 1 θ, . . . , a n θ logically implied by K. Notice that, in general, the set of certain answers may be infinite even if the KB is finite. Therefore, it is of interest to define suitable notions of safeness, which guarantee that the set of answers is bounded. This issue, however, is beyond the scope of the present paper. Indeed, in this paper, we focus on Boolean queries only, so as to address the computation of certain answers as a decision problem.

Example 2. Let us refer to the MKB K 1 = D, M of example 1. Interesting queries that can be posed to K 1 include: (i) Return all the instances of Car manufactured by the motor industry, each one with its own type: q(x, y) ← Inst C (x, y), Inst C (y, Car); (ii) Return all the concepts which car with plate number 'AB111' belongs to: q(x) ← Inst C ( AB111 , x).

Query answering

In this section, we study the problem of answering IHUCQs over Hi (DL-Lite R ) MKBs. Our query answering technique is based on query rewriting, so we will first deal with the problem of computing a perfect reformulation of a IHUCQ over a Hi (DL-Lite R ) KB. Then, we will present a query answering algorithm for MKBs based on the above perfect reformulation technique. In the following, we assume that the MKB is consistent. This does not constitute a limitation, since it is possible to show that checking consistency of a MKB can also be done through query answering, by means of techniques analogous to the ones defined for DL-Lite.

We start with some auxiliary definitions. Given an assertion α = Inst C (e 1 , e 2 ), we say that e 2 occurs as a concept argument in α. Given an assertion α = Inst R (e 1 , e 2 , e 3 ), we say that e 3 occurs as a role argument in α. Given an assertion α = Isa C (e 1 , e 2 ), we say that e 1 and e 2 occur as concept arguments in α. Given an assertion α = Isa R (e 1 , e 2 ), we say that e 1 and e 2 occur as role arguments in α. Given an assertion α = Disj C (e 1 , e 2 ), we say that e 1 and e 2 occur as concept arguments in α. Given an assertion α = Disj R (e 1 , e 2 ), we say that e 1 and e 2 occur as role arguments in α.

A DL atom is an atom of the form N (t) or N (t 1 , t 2 ), where N is a name and t, t 1 , t 2 are either variables or names. An extended CQ (ECQ) is a conjunction of DL atoms, Inst C atoms and Inst R atoms. An extended UCQ (EUCQ) is a union of ECQs. Given an atom α, Pred (α) denotes the term appearing in predicate position in α (such a term may be either a variable or an expression). Given a TBox T , we denote by Concepts(T ) the set {e, Exists(e), Exists(Inv (e)) | e ∈ E and e occurs as a concept argument in T } and denote by Roles(T ) the set {e, Inv (e) | e ∈ E and e occurs as a role argument in T }. Given a mapping M and a database DB , we denote by Retrieve(M, DB ) the Hi (DL-Lite R ) KB H defined as:

H = {ψ(t) | Φ(x) ; ψ ∈ M and DB |= Φ(t)}

Given an instance-mapping M and an ABox A, we say that A is retrievable through M if there exists a database DB such that A = Retrieve(M, DB ).

Query rewriting. We start by providing an intuitive explanation of our rewriting technique. The basic idea is to reduce the perfect reformulation of an IHUCQ over a Hi (DL-Lite R ) TBox to the perfect reformulation of a standard UCQ over a DL-Lite R TBox, which can be done e.g. by the algorithm PerfectRef presented in [3]. To do so, we have to first transform a IHUCQ into a standard UCQ, actually an EUCQ. This is done through a first partial grounding of the query (through the function PMG) and then through the functions Normalize and τ presented below. Once computed the perfect reformulation of the EUCQ, we then have to transform the EUCQ back into a IHUCQ, through the functions Denormalize and τ − presented below.

Given two IHCQs q, q and a TBox T , we say that q is a partial metagrounding of q with respect to T if q = σ(q) where σ is a partial substitution of the metavariables of q with the expressions occurring in T such that, for each metavariable x of q, either σ(x) = x or: (i) if x occurs in a concept position in q, then σ(x) ∈ Concepts(T ); (ii) if x occurs in a role position in q, then σ(x) ∈ Roles(T ). Given an IHCQ q and a TBox T , we denote by PMG(q, T ) the set of all partial metagroundings of q with respect to T , i.e., the following IHUCQ Q: Q = {q | q is a partial metagrounding of q with respect to T } Moreover, given a IHUCQ Q and a TBox T , we define PMG(Q, T ) as the IHUCQ q∈Q PMG(q, T ).

Given an instance atom α, we define Normalize(α) as follows: Given an IHCQ q ← α 1 , . . . , α n , Normalize(q) returns the IHCQ q ← Normalize(α 1 ), . . . , Normalize(α n ). Finally, given an IHUCQ Q, we define Normalize(Q) as q∈Q Normalize(q). Given an IHCQ q and an instance-mapping M, Denormalize(q, M) is the IHUCQ Q defined inductively as follows:

-if α = Inst C (e 1 ,

q ∈ Q; if q ∈ Q and q contains an atom α of the form Inst R (t 1 , , t 2 ), and either Exists(t 2 ) occurs in M or Exists(x) (where x is a variable) occurs in M, then the query obtained from q by replacing α with the atom Inst C (t 1 , Exists(t 2 )) belongs to Q; if q ∈ Q and q contains an atom α of the form Inst R ( , t 1 , t 2 ), and either Exists(Inv (t 2 )) occurs in M or Exists(Inv (x)) (where x is a variable) occurs in M, then the query obtained from q by replacing α with the atom Inst C (t 1 , Exists(Inv (t 2 ))) belongs to Q; if q ∈ Q and q contains an atom α of the form Inst R (t 1 , t 2 , t 3 ) and either Inv (t 2 )

occurs in M or Inv (x) (where x is a variable) occurs in M, then the query obtained from q by replacing α with the atom Inst R (t 2 , t 1 , Inv (t 3 ))) belongs to Q. Finally, given an IHUCQ Q and a mapping M, we define Denormalize(Q, M) as q∈Q Denormalize(q, M).

Given an IHUCQ Q and a TBox T , we denote by PerfectRef (Q, T ) the EUCQ returned by the query rewriting algorithm for DL-Lite R shown in [3]. 2We now define the functions τ and τ − which translate IHUCQs into EUCQs and vice versa. Given an IHCQ q and a TBox T , τ (q, T ) is the ECQ obtained from q as follows: (i) for each atom of q of the form Inst C (t 1 , t 2 ), if t 2 ∈ Concepts(T ) then replace the atom with the atom t 2 (t 1 ); (ii) for each atom of q of the form Inst R (t 1 , t 2 , t 3 ), if t 3 ∈ Roles(T ) then replace the atom with the atom t 3 (t 1 , t 2 ). Then, given an IHUCQ Q, we define τ (Q, T ) = {τ (q, T ) | q ∈ Q}.

Given a ECQ q and a TBox T , τ − (q, T ) is the IHCQ obtained from q as follows: (i) for each atom of q of the form t 2 (t 1 ), replace the atom with the atom Inst C (t 1 , t 2 ); (ii) for each atom of q of the form t 3 (t 1 , t 2 ), replace the atom with the atom Inst R (t 1 , t 2 , t 3 ). Then, given an IHUCQ Q, we define τ − (Q, T ) = {τ − (q, T ) | q ∈ Q}.

We are now ready to formally define our rewriting algorithm, which takes as input a IHUCQ, a TBox and an instance-mapping, and returns a new IHUCQ.

ALGORITHM RewriteIUCQ(Q, T , M) INPUT: Boolean IHUCQ Q, DL-Lite R TBox T , instance-mapping M OUTPUT: Boolean IHUCQ Q Q 0 = PMG(Q, T ); Q 1 = Normalize(Q 0 ); Q 2 = τ (Q 1 , T ); Q 3 = PerfectRef (Q 2 , T ); Q 4 = τ − (Q 3 , T ); Q = Denormalize(Q 4 , M); return Q ;

The IHUCQ returned by RewriteIUCQ(Q, T , M) constitutes a perfect reformulation of the query Q with respect to the TBox T and the mapping M, as formally stated by the following theorem.

Theorem 1. Let T be a TBox, let M be an instance-mapping and let Q be a IHUCQ. Then, for every ABox A that is a retrievable through M, T

∪ A |= Q iff A |= RewriteIUCQ(Q, T , M).

Query answering. Based on the above query rewriting technique, we now present an algorithm for query answering over MKBs. Our idea is to first compute a DL-Lite R TBox by evaluating the mapping assertions involving the predicates Isa C , Isa R , Disj C , Disj R over the database of the MKB; then, such a TBox is used to compute the perfect reformulation of the input IHUCQ.

To complete query answering, we now have to consider the mapping of the predicates Inst C and Inst R , and to reformulate the query thus obtained replacing the above predicates with the corresponding FOL queries of the mapping assertions. In this way we obtain a FOL query expressed on the database. This second rewriting step, usually called unfolding, can be performed by the algorithm UnfoldDB presented in [8]. 3In the following, given a mapping M and a database DB , we denote by DB MA the database constituted by every relation R of DB such that R occurs in M A . Analogously, we denote by DB MT the database constituted by every relation R of DB such that R occurs in M T . We are now ready to present our query answering algorithm. The algorithm starts by retrieving the TBox from the DB through the mapping M T . Then, it computes the perfect reformulation of the query with respect to the retrieved TBox, and next computes the unfolding of such a query with respect to the mapping M A . Finally, it evaluates the query over the database.

The following property can be proved by slightly extending the proof of correctness of the algorithm UnfoldDB shown in [8]. The above lemma allows us to prove correctness of the algorithm Answer . Theorem 2. Let K = DB , M be a Hi (DL-Lite R ) MKB, let Q be a IHUCQ. Then, K |= Q iff Answer (Q, K) returns true.

Finally, from the algorithm Answer we are able to derive the following complexity results for query answering over Hi (DL-Lite R ) MKBs. Theorem 3. Let K = DB , M be a Hi (DL-Lite R ) MKB, and let Q be a IHUCQ. Deciding whether K |= Q is in AC 0 with respect to the size of DB MA , is in PTIME with respect to the size of K, and is NP-complete with respect to the size of K ∪ Q.

Conclusions

In this paper we have investigated the possibility of generating a knowledge base on the fly, while computing instance queries, from data stored in data sources through asserted mappings. A key point to obtain such a degree of flexibility is relying on higher-order description logics which blur the distinction between classes/roles at the intensional level and individuals at the extensional level. This paper is only scratching the surfaces of the immense possibilities that this approach opens. For example, we may allow the coexistence of multiple TBoxes within the same data sources, and allow the user to select which TBox to load when querying the system, possibly depending on the query, much in the spirit of [7]. The user can in principle even compose on the fly the TBox to use when answering a query. Obviously notions such as authorization views acquire an intriguing flavor in this setting (hiding intensional as well as extensional knowledge), as well as consistency, since we may even allow for contradicting assertions to coexist as long as they are not used together when performing query answering.