=Paper=
{{Paper
|id=None
|storemode=property
|title=Mapping Data to Higher-Order Description Logic Knowledge Bases
|pdfUrl=https://ceur-ws.org/Vol-745/paper_23.pdf
|volume=Vol-745
|dblpUrl=https://dblp.org/rec/conf/dlog/PintoGLR11
}}
==Mapping Data to Higher-Order Description Logic Knowledge Bases==
https://ceur-ws.org/Vol-745/paper_23.pdf
Mapping Data to Higher-Order Description Logic
Knowledge Bases
Floriana Di Pinto, Giuseppe De Giacomo, Maurizio Lenzerini, Riccardo Rosati
Dipartimento di Informatica e Sistemistica Antonio Ruberti
Sapienza Università di Roma
lastname@dis.uniroma1.it
Abstract. In this paper we introduce the notion of mapping-based knowledge
base (MKB), to formalize those ontology-based data access (OBDA) scenarios
where both the extensional and the intensional level of the ontology are deter-
mined by suitable mapping assertions involving the data sources. We study rea-
soning over MKBs in the context of Hi(DL-LiteR ), a higher-order version of
the DL DL-LiteR . We show that answering queries posed to MKBs expressed in
Hi(DL-LiteR ) can be done efficiently through FOL rewriting: hence, query an-
swering can be delegated to a DBMS, as in the case of traditional OBDA systems.
1 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 application-
dependent 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 sys-
tems 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 ontol-
ogy 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. Table T-Cars, on the other
T-Cars
T-CarTypes
NumberPlate CarType EngineSize BreakPower Color TopSpeed
Code TypeName AB111 T1 2000 200 Silver 260
T1 Coupé AF333 T2 3000 300 Black 200
T2 SUV BR444 T2 4000 400 Grey 220
T3 Sedan AC222 T4 2000 125 Dark Blue 180
T4 Estate BN555 T3 1000 75 Light Blue 180
BP666 T1 3000 600 Red 240
Fig. 1. The database of a motor industry
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 lan-
guage 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 dy-
namically 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 0 , and in the second step q 0 is evaluated
over the ABox. The correctness of the whole method relies on the fact the answers to
q 0 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-LiteR ) (Section 2), based on the ap-
proach 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-LiteR ), which is the higher-order version of DL-LiteR [3].
(iii) We show that answering queries posed to MKBs expressed in Hi (DL-LiteR )
can be done efficiently through FOL rewriting (Section 4). More specifically, we de-
scribe 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 MA of the MKB involv-
ing the extensional level of the ontology. Hence query answering can be delegated to a
DBMS, as in the case of traditional OBDA systems.
2
2 Higher-order DL-LiteR
In this section, we describe the higher-order DL Hi (DL-LiteR ), 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-LiteR , we have
– OP (DL-LiteR ) = {Inv /1, Exists/1};
– MP (DL-LiteR ) = {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-LiteR . Therefore, the intuitive mean-
ing 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-LiteR ) 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-LiteR (S, V), over the alpha-
bets S and V for Hi(DL-LiteR ) as follows:
– if E ∈ S then E ∈ τDL-LiteR (S, V);
– if V ∈ V then V ∈ τDL-LiteR (S, V);
– if C/n ∈ OP (DL-LiteR ) and t1 , . . . , tn ∈ τDL-LiteR (S, V) then C(t1 , . . . , tn ) ∈
τDL-LiteR (S, V).
Ground terms, i.e., terms without variables, are called expressions, and the set of ex-
pressions is denoted by τDL-LiteR (S).
A DL-LiteR -atom, or simply atom, over the alphabets S and V for Hi(DL-LiteR )
is a statement of the form M (E1 , . . . , En ) where M ∈ MP (DL-LiteR ), n is the arity
of M , and for every 1 ≤ i ≤ n, Ei ∈ τDL-LiteR (S, V). If X is a subset of V, a is
a DL-LiteR -atom, and all variables appearing in a belongs to X, then a is called an
X-atom in DL-LiteR .
Ground DL-LiteR -atoms, i.e., DL-LiteR -atoms without variables, are called
DL-LiteR -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-LiteR ) knowledge base (KB) over S is a set of DL-LiteR -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-LiteR ) is based on the notion of
interpretation structure. An interpretation structure is a triple Σ = h∆, Ic , Ir i where:
(i) ∆ is a non-empty (possibly countably infinite) set; (ii) Ic is a function that maps
each d ∈ ∆ into a subset of ∆; and (iii) Ir 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 Ic ; and (iii) a binary relation,
i.e., a role, through Ir .
3
An interpretation for S (simply called an interpretation, when S is clear from the
context) over the interpretation structure Σ is a pair I = hΣ, Io i, where
– Σ = h∆, Ic , Ir i is an interpretation structure, and
– Io is a function that maps:
1. each element of S to a single object in ∆; and
2. each element C/n ∈ OP (DL-LiteR ) 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-LiteR ) are as follows:
(a) for each d1 ∈ ∆, if d = Inv Io (d1 ) then dIr = (dI1 r )−1 ;
(b) for each d1 ∈ ∆, if d = Exists(d1 ) then dIc = {e | ∃e1 s.t. he, e1 i ∈
dI1 r }.
We extend Io to ground terms in τDL-LiteR (S) inductively as follows: if C/n ∈
OP (DL-LiteR ), then (C(t1 , . . . , tn ))Io = C Io (E1Io , . . . , EnIo ).
We now turn our attention to the interpretation of terms in Hi (DL-LiteR ). To in-
terpret non-ground terms, we need assignments over interpretations, where an assign-
ment µ over hΣ, Io i is a function µ : V → ∆. Given an interpretation I = hΣ, Io i
and an assignment µ over I, the interpretation of terms is specified by the function
(·)Io ,µ : τDL-LiteR (S, V) → ∆ defined as follows:
– if t ∈ S then tIo ,µ = tIo ;
– if t ∈ V then tIo ,µ = µ(t);
– if t is of the form C(t1 , . . . , tn ), then tIo ,µ = C Io (tI1 o ,µ , . . . , tIno ,µ ).
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 (E1 , E2 ) if E1Io ,µ ∈ (E2Io ,µ )Ic ;
– I, µ |= Inst R (E1 , E2 , E3 ) if hE1Io ,µ , E2Io ,µ i ∈ (E3Io ,µ )Ir ;
– I, µ |= Isa C (E1 , E2 ) if (E1Io ,µ )Ic ⊆ (E2Io ,µ )Ic ;
– I, µ |= Isa R (E1 , E2 ) if (E1Io ,µ )Ir ⊆ (E2Io ,µ )Ir ;
– I, µ |= Disj C (E1 , E2 ) if (E1Io ,µ )Ic ∩ (E2Io ,µ )Ic = ∅;
– I, µ |= Disj R (E1 , E2 ) if (E1Io ,µ )Ir ∩ (E2Io ,µ )Ir = ∅.
A Hi (DL-LiteR ) KB H is satisfied by I if all the assertions in H are satisfied by I 1 .
As usual, the interpretations I satisfying H are called the models of H. A Hi (DL-LiteR )
KB H is satisfiable if it has at least one model.
3 Mapping-based knowledge bases
As we said in the previous section, a Hi (DL-LiteR ) 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
1
We do not need to mention assignments here, since all assertions in H are ground.
4
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-LiteR ) mapping-based knowledge base (MKB) is a pair K =
hDB , Mi 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 = hx1 , . . . , xn i, and ψ is an
X-atom in DL-LiteR , with X = {x1 , . . . , xn }.
In the following, if K = hDB , Mi is a MKB, then we denote by MA the set of
mapping assertions from M whose head predicate is either Inst C or Inst R . Further-
more, we denote by MT the set M \ MA , 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 map-
ping M an instance-mapping if M = MA , 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-LiteR ) MKB K = hDB , Mi, 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 = {x1 , . . . , xn }, 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 xi with vi (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 = hDB , Mi if I
satisfies every assertion in M with respect to DB .
The following example shows how Hi (DL-LiteR ) 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-LiteR ) MKB K1 = hD, Mi, where the mapping M is defined as follows:
– M1: {y | T-CarTypes(x, y)} ; Isa C (y, Car)
– M2: {(x, z) | T-Cars(x, y, t, u, v, q) ∧ T-CarTypes(y, z)} ; Inst C (x, z)
– M3: {(x, y) | T-CarTypes(z1 , x) ∧ T-CarTypes(z2 , y) ∧ x 6= y} ; Disj C (x, y)
5
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 com-
mon 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
table in D:
T-NewCars NumberPlate CarType Height Weight EngineSize BreakHorsePower
CM777 Camper 2,50 mt 680 Kg 4000 cc 200 bhp
CM888 Camper 2,20 mt 550 Kg 3000 cc 150 bhp
CV333 Caravan 2,30 mt 620 Kg 3000 cc 200 bhp
CV222 Caravan 2,50 mt 580 Kg 4000 cc 250 bhp
The new situation can be modeled in our framework by simply adding to M the fol-
lowing mapping assertions:
– M4: {y | T-NewCars(x, y, t, u, v, q)} ; Isa C (y, Car)
– M5: {(x, z) | T-NewCars(x, z, t, u, v, q)} ; Inst C (x, z)
– M6: {(x, y) | T-NewCars(z1 , x) ∧ T-NewCars(z2 , y) ∧ x 6= y} ; Disj C (x, y)
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 meta-
predicate 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-LiteR (S) ∪ V. We
define a query atom as an atom constituted by the application of a meta-predicate in
MP (DL-LiteR ) to a set of q-terms, and we call a query atom ground if no variable oc-
curs in it. A query atom whose meta-predicate is Inst C or Inst R is called an instance-
query atom. A higher-order conjunctive query (HCQ) of arity n is an expression of
the form q(x1 , . . . , xn ) ← a1 , . . . , am where q, called the query predicate, is a symbol
not in S ∪ V, every xi belongs to V, every ai is a (possibly non-ground) query atom,
6
and all variables x1 , . . . , xn occur in some aj . The variables x1 , . . . , xn are called the
free variables (or distinguished variables) of the query, while the other variables oc-
curring in a1 , . . . , am 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 ← a1 , . . . , an is satisfied in I, µ if every query atom ai 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-LiteR ) 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(t1 , . . . , tn ) ← a1 , . . . , am , a ground-
ing substitution of q is a substitution θ such that t1 θ, . . . , tn θ are ground terms. We
call t1 θ, . . . , tn θ a grounding tuple. The set of certain answers to q in K is the set of
grounding tuples t1 θ, . . . , tn θ that make the Boolean query qθ ← a1 θ, . . . , an θ logi-
cally 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 K1 = hD, Mi of example 1. Interesting queries
that can be posed to K1 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 (0 AB1110 , x).
4 Query answering
In this section, we study the problem of answering IHUCQs over Hi (DL-LiteR ) 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-LiteR ) KB.
Then, we will present a query answering algorithm for MKBs based on the above per-
fect 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 consis-
tency 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 (e1 , e2 ), we
say that e2 occurs as a concept argument in α. Given an assertion α = Inst R (e1 , e2 , e3 ),
we say that e3 occurs as a role argument in α. Given an assertion α = Isa C (e1 , e2 ),
we say that e1 and e2 occur as concept arguments in α. Given an assertion α =
Isa R (e1 , e2 ), we say that e1 and e2 occur as role arguments in α. Given an assertion
α = Disj C (e1 , e2 ), we say that e1 and e2 occur as concept arguments in α. Given an
assertion α = Disj R (e1 , e2 ), we say that e1 and e2 occur as role arguments in α.
7
A DL atom is an atom of the form N (t) or N (t1 , t2 ), where N is a name
and t, t1 , t2 are either variables or names. An extended CQ (ECQ) is a conjunc-
tion 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 pred-
icate 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-LiteR ) 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-LiteR ) TBox to the perfect reformulation of a standard UCQ over a DL-LiteR
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 re-
formulation 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 0 and a TBox T , we say that q 0 is a partial metagrounding of
q with respect to T if q 0 = σ(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 0 | q 0 is a partial metagrounding of q with respect to T }
Moreover,
S 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:
– if α = Inst C (e1 , e2 ) and e2 has the form Exists(e0 ) where e0 is an expression
which is not of the form Inv (e00 ), then Normalize(α) = Inst R (e1 , , e0 );
– if α = Inst C (e1 , e2 ) and e2 has the form Exists(Inv (e0 )) where e0 is any expres-
sion, then Normalize(α) = Inst R ( , e1 , e0 );
– if α = Inst R (e1 , e2 , e3 ) and e3 is of the form Inv k (e0 ) where k ≥ 1 and k is
an even number and e0 is an expression which is not of the form Inv (e00 ), then
Normalize(α) = Inst R (e1 , e2 , e0 );
– if α = Inst R (e1 , e2 , e3 ) and e3 is of the form Inv k (e0 ) where k ≥ 1 and k is
an odd number and e0 is an expression which is not of the form Inv (e00 ), then
Normalize(α) = Inst R (e2 , e1 , e0 ).
8
Given an IHCQ q ← α1 , . . . , αn , Normalize(q) returns the IHCQ q ←
Normalize(α1 ), . .S . , 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:
– q ∈ Q;
– if q 0 ∈ Q and q 0 contains an atom α of the form Inst R (t1 , , t2 ), and either
Exists(t2 ) occurs in M or Exists(x) (where x is a variable) occurs in M, then
the query obtained from q 0 by replacing α with the atom Inst C (t1 , Exists(t2 ))
belongs to Q;
– if q 0 ∈ Q and q 0 contains an atom α of the form Inst R ( , t1 , t2 ), and ei-
ther Exists(Inv (t2 )) occurs in M or Exists(Inv (x)) (where x is a variable)
occurs in M, then the query obtained from q 0 by replacing α with the atom
Inst C (t1 , Exists(Inv (t2 ))) belongs to Q;
– if q 0 ∈ Q and q 0 contains an atom α of the form Inst R (t1 , t2 , t3 ) and either Inv (t2 )
occurs in M or Inv (x) (where x is a variable) occurs in M, then the query obtained
from q 0 by replacing α with the atom Inst R (t2 , t1 , Inv (t3 ))) belongs to Q.
Finally,
S 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-LiteR shown in [3].2
We 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 fol-
lows: (i) for each atom of q of the form Inst C (t1 , t2 ), if t2 ∈ Concepts(T ) then replace
the atom with the atom t2 (t1 ); (ii) for each atom of q of the form Inst R (t1 , t2 , t3 ), if
t3 ∈ Roles(T ) then replace the atom with the atom t3 (t1 , t2 ). 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 fol-
lows: (i) for each atom of q of the form t2 (t1 ), replace the atom with the atom
Inst C (t1 , t2 ); (ii) for each atom of q of the form t3 (t1 , t2 ), replace the atom with the
atom Inst R (t1 , t2 , t3 ). 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-LiteR TBox T , instance-mapping M
OUTPUT: Boolean IHUCQ Q0
Q0 = PMG(Q, T );
Q1 = Normalize(Q0 );
Q2 = τ (Q1 , T );
Q3 = PerfectRef (Q2 , T );
Q4 = τ − (Q3 , T );
Q0 = Denormalize(Q4 , M);
return Q0 ;
2
We are actually considering a slight generalization of the algorithm, which allows for the
presence of a ternary relation (Inst R ) in the query.
9
The IHUCQ returned by RewriteIUCQ(Q, T , M) constitutes a perfect reformula-
tion 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-LiteR
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 predi-
cates 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].3
In 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 MA . Analo-
gously, we denote by DB MT the database constituted by every relation R of DB such
that R occurs in MT . We are now ready to present our query answering algorithm.
ALGORITHM Answer (Q, K)
INPUT: Boolean IHUCQ Q, Hi (DL-LiteR ) MKB K = hDB , Mi
OUTPUT: true if K |= Q, false otherwise
T = Retrieve(MT , DB MT );
Q0 = RewriteIUCQ(Q, T , MA );
Q00 = UnfoldDB(Q0 , MA );
if DB MA |= Q00
then return true
else return false
The algorithm starts by retrieving the TBox from the DB through the mapping MT .
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
MA . 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].
Lemma 1. Let M be an instance-mapping and let Q be a IHUCQ. Then, for every
database DB , hM, DB i |= Q iff DB MA |= UnfoldDB(Q, M).
3
Here we assume that the algorithm UnfoldDB takes as input a EUCQ and an instance-mapping.
This corresponds to actually considering a straightforward extension of the algorithm pre-
sented in [8] in order to deal with the presence of the ternary predicate Inst R .
10
The above lemma allows us to prove correctness of the algorithm Answer .
Theorem 2. Let K = hDB , Mi be a Hi (DL-LiteR ) 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-LiteR ) MKBs.
Theorem 3. Let K = hDB , Mi be a Hi (DL-LiteR ) 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.
5 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.
References
1. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez-Muro,
R. Rosati, M. Ruzzi, and D. F. Savo. The Mastro system for ontology-based data access.
Semantic Web Journal, 2(1):43–53, 2011.
2. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, and R. Rosati. Ontology-
based database access. In Proc. of SEBD 2007, pages 324–331, 2007.
3. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning
and efficient query answering in description logics: The DL-Lite family. J. of Automated
Reasoning, 39(3):385–429, 2007.
4. W. Chen, M. Kifer, and D. S. Warren. HILOG: A foundation for higher-order logic program-
ming. J. of Logic Programming, 15(3):187–230, 1993.
5. G. De Giacomo, M. Lenzerini, and R. Rosati. Higher-order description logics for domain
metamodeling. In Proc. of AAAI 2011, 2011.
6. J. Z. Pan and I. Horrocks. OWL FA: a metamodeling extension of OWL DL. In Proc. of
WWW 2006, pages 1065–1066, 2006.
7. J. Parsons and Y. Wand. Emancipating instances from the tyranny of classes in information
modeling. ACM Trans. on Database Systems, 25(2):228–268, 2000.
8. A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking
data to ontologies. J. on Data Semantics, X:133–173, 2008.
9. D. F. Savo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodrı́guez-Muro, V. Romagnoli, M. Ruzzi,
and G. Stella. M ASTRO at work: Experiences on ontology-based data access. In Proc. of
DL 2010, volume 573 of CEUR, ceur-ws.org, pages 20–31, 2010.
11