Query answering in Ontology Based Data Access (OBDA) exploits the knowledge of an ontology's TBox to deal with incompleteness of the ABox (or data source). Current query-answering techniques with DL-Lite require exponential size query reformulations, or expensive data pre-processing. Also, these techniques present severe redundancy issues when dealing with ABoxes that are already (partially) complete. It has been shown that addressing redundancy is not only required for tractable implementations of decision procedures, but may also allow for sizable improvements in execution times. Considering the previous observations, in this paper we extend the results aiming at improving query answering performance in OBDA systems that were developed in [9] for DL-LiteF , to the case where also role inclusions are present in the TBox. Specifically, we first show that we can characterize completeness of an ABox by means of dependencies, and that we can use these to optimize DL-LiteA TBoxes. Second, we show that in OBDA systems we can create ABox repositories that appear to be complete w.r.t. a significant portion of any DL-LiteA TBox. The combination of these results allows us to design OBDA systems based on DL-LiteA in which redundancy is minimal, the exponential aspect of query answering is notably reduced and that can be implemented efficiently using existing RDBMSs.
The current approaches to Ontology Based Data Access (OBDA) with lightweight
Description Logics (DLs) of the DL-Lite family [
Specifically, in [
The rest of the paper is organized as follows: Section 2 gives technical preliminaries. Section 3 presents our extension to DL-LiteA of the general technique for optimizing TBoxes w.r.t. dependencies. Section 4 introduces data dependencies in OBDA systems, describing why it is natural to expect completeness of ABoxes. Section 5 presents our extension of one of the techniques for completing ABoxes in OBDA systems to allow for DL-LiteA ontologies. Section 6 concludes the paper. 2
In the rest of the paper, we assume a fixed vocabulary V of atomic concepts, denoted A (possibly with subscripts), and atomic roles, denoted P , representing unary and binary relations, respectively, and an alphabet of (object) constants. Databases. In the following, we regard a database (DB) as a pair D = hR; Ii, where R is a relational schema and I is an instance of R. The active domain D of D is the set of constants appearing in I, which we call value constants. An SQL query ' over a DB schema R is a mapping from a DB instance I of R to a set of tuples.
DL-Lite ontologies. We introduce the DL DL-LiteA, on which we base our results. In DLLiteA, a basic role, denoted R, is an expression of the form P or P , and a basic concept, denoted B, is an expression of the form A or 9R. An ontology is a pair O = hT ; Ai where T is a TBox and A an ABox. A TBox is a finite set of (positive) inclusions
(funct R). An ABox is a finite set of membership assertions A(c) or P (c; c0), where c; c0 2 . Moreover, DL-LiteA imposes the syntactic restriction that a role P declared functional, via (funct P ), or inverse functional, via (funct P ), cannot be specialized, i.e., cannot appear in the right-hand side of a role inclusion assertion R v P or R v P . Queries over ontologies. An atom is an expression of the form A(t) or P (t; t0), where t and t0 are atom terms, i.e., variables or constants in . An atom is ground if it contains no variables. A conjunctive query (CQ) q over an ontology O is an expression of the form q(x) (x; y), where x is a tuple of distinct variables, called distinguished, y is a tuple of distinct variables not occurring in x, called non-distinguished, and (x; y) is a conjunction of atoms with variables in x and y, whose predicates are atomic concepts and roles of O. We call q(x) the head of the query and (x; y) its body. A union of CQs (UCQ) is a set of CQs (called disjuncts) with the same head. Given a CQ Q with body (z) and a tuple v of constants of the same arity as z, we call a ground instance of Q the set [z=v] of ground atoms obtained by replacing in (z) each variable with the corresponding constant from v.
Semantics. An interpretation I = ( I ; I ) consists of a non-empty interpretation domain I and an interpretation function I that assigns to each constant c an element cI of I , to each atomic concept A a subset AI of I , and to each atomic role P a binary relation over I . Moreover, basic roles and basic concepts are interpreted as follows: (P )I = f(o2; o1) j (o1; o2) 2 P I g and (9R)I = fo j 9o0: (o; o0) 2 RI g. An interpretation I is a model of B1 v B2 if B1I B2I , of R1 v R2 if R1I R2I , of B1 v :B2 if B1I \ B2I = ;, and of (funct R) if for each o; o1; o2 2 I we have that (o; o1) 2 RI and (o; o2) 2 RI implies o1 = o2. Also, I is a model of A(c) if cI 2 AI , and of P (c; c0) if (cI ; c0I ) 2 P I . In DL-LiteA, we adopt the Unique Name Assumption (UNA), which enforces that for each pair of constants o1, o2, if o1 6= o2, then o1I 6= o2I . For a DL-LiteA assertion (resp., a set of DL-LiteA assertions), I j= (resp., I j= ) denotes that I is a model of (resp., ). A model of an ontology O = hT ; Ai is an interpretation I such that I j= T and I j= A. An ontology is satisfiable if it admits a model. An ontology O entails an assertion , denoted O j= , if every model of O is also a model of . Similarly, for a TBox T and an ABox A instead of O. The saturation of a TBox T , denoted sat (T ), is the set of DL-LiteA assertions s.t. T j= . Notice that sat (T ) is finite, hence a TBox.
Let A denote the set of constants appearing in an ABox A. The answer to a CQ
Q = q(x) (x; y) over O = hT ; Ai in an interpretation I, denoted ans(Q; O; I),
is the set of tuples c 2 A A such that there exists a tuple c0 2 A A
such that the ground atoms in [(x; y)=(c; c0)] are true in I. The answer to an UCQ
Q in I is the union of the answers to each CQ in Q. The certain answers to Q in O,
denoted cert (Q; O), is the intersection of every ans(Q; O; I) for all models I for O.
The answer to Q over an ABox A, denoted eval (Q; A), is the answers to Q over A
viewed as a DB instance. A perfect reformulation of Q w.r.t. a TBox T is a query Q0 such
that for every ABox A such that hT ; Ai is satisfiable, cert (Q; hT ; Ai) = eval (Q0; A).
Mappings. We adopt the definitions for ontologies with mappings from [
An interpretation I satisfies a mapping assertion '(x) ; (t) w.r.t. a DB D =
hR; Ii if for every tuple v 2 '(I) and for every ground atom X in [x=v] we have that:
if X has the form A(f (c)), then (f (c))I 2 AI , and if X has the form P (f1(c1); f2(c2)),
then ((f1(c1))I ; f2(c2)I ) 2 P I . An interpretation I is a model of V = hD; Mi,
denoted I j= V, if it satisfies every mapping in M w.r.t. D. A virtual ABox V entails an
ABox assertion , denoted V j= , if every model of V is a model of . I is a model of
OM = hT ; Vi if I j= T and I j= V. As usual, OM is satisfiable if it admits a model.
We note that, in an ontology with mappings OM = hT ; hD; Vii, we can always replace
M by a set of simple mappings, while preserving the semantics of OM. It suffices to
split each complex mapping ' ; into a set of simple mappings that share the same
SQL query ' (see [
s.t. A j= . 3
In a DL-LiteA ontology O = hT ; Ai, the ABox A may be incomplete w.r.t. the TBox T , i.e., there may be assertions B1 v B2 in T s.t. A 6j= B1 vA B2. When computing the certain answers to queries over O, the TBox T is used to overcome such incompleteness. However, an ABox may already be (partially) complete w.r.t. T , e.g., an ABox A satisfying A1 vA A2 is complete w.r.t. A1 v A2. While ignoring completeness of an ABox is ’harmless’ in the theoretical analysis of reasoning over DL-LiteA ontologies, in practice, it introduces redundancy, which manifests itself as containment w.r.t. dependencies among the disjuncts (CQs) of the perfect reformulation, making the contained disjuncts redundant. For example, let T and A be as before, and let Q be q(x) A2(x), then any perfect reformulation of Q must include q1 = q(x) A1(x) and q2 = q(x) A2(x) as disjuncts. However, since q1 is contained in q2 relative to A1 vA A2, we have that q1 will not contribute new tuples w.r.t. those contributed by q2.
It is possible to use information about completeness of an ABox, expressed as a set of dependencies, to avoid redundancy in the reasoning process. One place to do this is during query reformulation, using techniques based on conjunctive query containment (CQC) with respect to dependencies to avoid the generation of redundant queries. However, this approach is expensive, since CQC is an NP-complete problem (even ignoring dependencies), and such optimizations would need to be performed every time a query is reformulated. We show now how we can improve efficiency by pre-processing the TBox before performing reformulation. In particular, given a TBox T and a set of dependencies, we show how to compute a TBox T 0 that is smaller than T and such that for every query Q the certain answers are preserved if Q is executed over an ABox that satisfies . Specifically, our objective is to determine when an inclusion assertion of T is redundant w.r.t. , and to do so we use the following auxiliary notions. Definition 1. Let T be a TBox, B, C basic concepts, R, S basic roles, and a set of dependencies over T . A T -chain from B to C in T (resp., a -chain from B to C in ) is a sequence of inclusion assertions (Bi v Bi0)in=0 in T (resp., a sequence of inclusion dependencies (Bi vA Bi0)in=0 in ), for some n 0, such that: B0 = B, Bn0 = C, and for 1 i n, we have that Bi0 1 and Bi are basic concepts s.t., either (i) Bi0 1 = Bi, or (ii) Bi0 1 = 9R0 and Bi = 9R0 , for some basic role R0. A T -chain from R to S in T (resp., a -chain from R to S in ) is a sequence of inclusion assertions (Ri v Ri0)in=0 in T (resp., a sequence of inclusion dependencies (Ri vA Ri0)in=0 in ), for some n 0, such that: R0 = R, Rn0 = S and for 1 i n, we have that Ri0 1 = Ri. Intuitively, when there is a T -chain from B to C, the existence of an instance of B in a model implies the existence of an instance of C. For a -chain, this holds for ABox assertions. We use T -chains and -chains to characterize redundancy as follows.
of dependencies. The inclusion assertion B v C (resp., R v S) is directly redundant in T w.r.t. if (i) j= B vA C (resp., j= R vA S) and (ii) for every T -chain (Bi v Bi0)in=0 with Bn0 = B in T (resp., for every T -chain (Bi v Bi0)in=0 with Bn0 = 9R and for every T -chain (Ri v Ri0)im=0 with Rm0 = R), there is a -chain (Bi vA Bi0)in=0 (resp., a -chain (Bi vA Bi0)in=0 and a -chain (Ri vA Ri0)im=0). Then, B v C (resp.,
B0 6= B (resp., R0 6= R) s.t. (i) T j= B0 v C (resp., T j= R0 v S), (ii) B0 v C (resp.,
Given a TBox T and a set of dependencies , we apply our notion of redundancy w.r.t. to the assertions in the saturation of T to obtain a TBox T 0 that is equivalent to T for certain answer computation.
Correctness of using T 0 = optim(T ; ) instead of T when computing the certain answers to a query follows from the following theorem.
ABox A such that A j= and every UCQ Q over T , we have that cert (Q; hT ; Ai) = cert (Q; hoptim(T ; ); Ai).
Proof. First we note that during query answering, only the positive inclusions are
relevant, hence we ignore disjointness and functionality assertions. Since sat (T ) adds
to T only entailed assertions, cert (Q; hT ; Ai) = cert (Q; hsat (T ); Ai), for every Q
and A, and we can assume w.l.o.g. that T = sat (T ). Moreover, cert (Q; hT ; Ai) is
equal to the evaluation of Q over chase(T ; A). (We refer to [
(a) Case where B v C (resp., R v S) is directly redundant, and hence j= B vA C (resp., j= R vA S). We distinguish two subcases: (i) B(c) 2 A (resp., R(c; c0) 2 A). Since A j= B vA C (resp., A j= R vA S), we have C(c) 2 A (resp., S(c; c0) 2 A), and hence B v C is not applicable to B(c) (resp., R v S is not applicable to R(c; c0)). Contradiction. (ii) B(c) 2= A (resp., R(c; c0) 2= A). Then there is a sequence of chase steps starting from some ABox assertion B0(c0) (resp., R(a; a0) or B(a)) that generates B(c) (resp., R(c; c0)). Such a sequence requires a T -chain (Bi v Bi0)in=0 with B0 = B0 and Bn0 = B (resp., a T -chain (Ri v Ri0)in=0 with R0 = R0 and Rn0 = R, or a T -chain (Bi v Bi0)in=0 with B0 = B and Bn0 = 9R), such that each Bi v B0 i (resp., each Ri v Ri0 or each Bi v Bi0) is applicable in chase(T ; A). Then, by the second condition of direct redundancy, there is a -chain (Bi vA Bi0)in=0 (resp., a -chain (Ri vA Ri0)in=0 or a -chain (Bi vA Bi0)in=0 ). Since A j= B0 vA B00 (resp., A j= R0 v R00 or A j= B0 vA B00 ) we have that B00(c0) 2 A (resp., R00(a; a0) 2 A or B00(a) 2 A) and hence B0 v B00 is not applicable to B0(c0) (resp., R0 v R00 is not applicable to R0(a; a0), or B0 v B00 is not applicable to B0(a)). Contradiction.
(b) Case where B v C has been removed by Definition 2(b), and hence there exists B0 6= B such that T j= B v B0 (resp., R0 6= R s.t. T j= R v R0). First we note that any two oblivious chase sequences for T and A produce results that are equivalent w.r.t. query answering. Then it is enough to show that there exists some chase(T ; A) in which B0 v C (resp., R0 v S) is always applied before B v C (resp., R v S) and in which B v C (resp., R v S) is never applicable. Again, we distinguish two subcases: (i) B(c) 2 A (resp., R(c; c0) 2 A). Then, since B v B0 is directly redundant, we have that j= B vA B0. Since A j= , we have that B0(c) 2 A (resp., R0(c; c0) 2 A), and given that B0 v C (resp., R0 v S) is always applied before B v C (resp., R v S), C(c) (resp., S(c; c0)) is added to chase(T ; A) before the application of B v C (resp., R v S), hence B v C (resp., R v S) is in fact not applicable. Contradiction. (ii) B(c) 2= A (resp., R(c; c0) 2= A). Then, arguing as in Case (a).(ii), using B v B0 instead of B v C (resp., R v R0 instead of R v S), we can derive a contradiction. tu Complexity and implementation. Due to space limitations, we cannot provide a full description of how to compute optim(T ; ). We just note that the checks that are required by optim(T ; ) can be reduced to computing reachability between two nodes in a DAG that represents the reachability relation of the chains in T and . This operation can be done in linear time.
Consistency checking. Consistency checking may also suffer from redundancy when the ABox is already (partially) complete w.r.t. T . In this case, we need to consider, in addition to inclusion dependencies, also functional and disjointness dependencies. Due to spaces limitations we cannot provide more details, and just note that using these dependencies it is possible to extend the definitions to generate TBoxes that avoid redundant consistency checking operations. 4
The purpose of the current section is to complement our argument w.r.t. completeness of ABoxes by discussing when and why we can expect completeness in OBDA systems. We start by observing that in OBDA systems, ABoxes are constructed, in general, from existing data that resides in some form of data repository. In order to create an ABox, the system requires some form of mappings from the source to the ontology. These may be explicit logical assertions as the ones used in this paper, or they may be implicitly defined through application code. Therefore, the source queries used in these mappings become crucial in determining the structure of the ABox. In particular, any dependencies that hold over the results of these queries will be reflected in the OBDA system as ABox dependencies. Example 1. Let R be a DB schema with the relation schema employee with attributes id, dept, and salary, that stores information about employees, their salaries, and the department they work for. Let M be the following mappings:
SELECT id,dept FROM employee ; Employee(emp(id)) ^
WORKS-FOR(emp(id); dept(dept)) SELECT id,dept FROM employee ; M anager(emp(id))^
WHERE salary > 1000 MANAGES(emp(id); dept(dept)) where Employee and Manager are atomic concepts and WORKS-FOR and MANAGES are atomic roles. Then for every instance I of R, the virtual ABox V = hhR; Ii; Mi satisfies the following dependencies:
In particular, the dependency in Column 1 follows from the containment relation between the two SQL queries used in the mappings, and the remaining dependencies follow from the fact that we populate WORKS-FOR (resp., MANAGES) using the same SQL query used to populate Employee (resp., Manager).
Turning our attention to the semantics of the data sources, we note that any given DB is based on some conceptual model. At the same time, if we associate the data of any given DB to the concepts and roles of a TBox T , it follows that this data is semantically related to these concepts and roles, and that the conceptual model of the DB has some common aspects with the semantics of T . It is precisely these common aspects that get manifested as dependencies between queries in the mappings and that give rise to completeness in ABoxes. Therefore, the degree of completeness of an ABox in an OBDA system is in direct relation with the closeness of the semantics of the conceptual model of the DB and the semantics of the TBox, and with the degree in which the DB itself complies to the conceptual model that was used to design it.
Example 2. To illustrate the previous observations we extend Example 1. First we note that the intended meaning of the data stored in R is as follows: (i) employees with a salary higher than 1,000 are managers, (ii) managers manage the department in which they are employed, and (iii) every employee works for a department. Then, any TBox that shares some of this semantics will present redundancy. For example, if T is
Employee v 9WORKS-FOR
then the first row of assertions is redundant w.r.t. . Instead, the semantics of the assertions of the second row is not captured by the mappings. In an OBDA system with such components, we should reason only w.r.t. Department. This can be accomplished by optimizing T w.r.t. using the technique presented in Section 3. 5
We focus now on procedures to complete ABoxes with respect to TBoxes. The final
objective is to simplify reasoning by diverting certain aspects of the process (e.g.,
dealing with concept/role hierarchies and domain and range assertions) from the query
reformulation stage to other stages of the query answering process where they can be
handled more efficiently. We call these procedures dependency induction procedures
since their result can be characterized by a set of dependencies that hold in the ABox(es)
of the system. Formally, given an OBDA system O = hT ; Vi, where V = hhR; Ii; Mi,
we call a dependency induction procedure a procedure that uses O to compute a virtual
ABox V0 such that the number of assertions in T for which V0 is complete is higher
than those for V. An example of a dependency induction procedure is ABox expansion,
a procedure in which the data in I is chased w.r.t. T . The critical point in dependency
induction procedures is the trade-off between the degree of completeness induced, the
system’s performance, and the cost of the procedure. In [
Semantic Index. This technique applies in the context of general OBDA systems in
which we are free to manipulate any aspect of the system to improve query answering.
The basic idea is to encode the implied is-a relationships of T in the values of numeric
indexes that we assign to concept and role names. ABox membership assertions are then
inserted in the DB using these numeric values s.t. one can retrieve most of the implied
instances of any concept or role by posing simple range queries to the DB (which are
very efficient in modern RDBMSs). Our proposal is related to techniques for managing
large transitive relations in knowledge bases (e.g., the is-a hierarchy) [
such that, for each pair E1, E2 of atomic concepts or atomic roles in V , we have that T j= E1 v E2 iff there is a pair h`; hi 2 range(E2) such that ` idx (E1) h.
Using a semantic index hidx ; rangei for a TBox T , we construct V = hR; Ii with the completeness properties described above by proceeding as follows. We define a DB schema R with a universal-like relation TC [c1; idx] for storing ABox concept assertions, and a relation TR[c1; c2; idx] for storing ABox role assertions, s.t. c1 and c2 have type constant and idx has type numeric. Given an ABox A, we construct I such that for each A(c) 2 A we have hc; idx (A)i 2 TC and for each P (c; c0) 2 A we have hc; c0; idx (P )i 2 TR. The schema and the index allow us to define, for each atomic concept A and each atomic role P , a set of range queries over D that retrieves most constants c, c0 such that O j= A(c) or O j= P (c; c0). E.g., if range(A) = fh2; 35ig, we define ’SELECT c1 FROM TC WHERE idx >= 2 AND idx <= 35’. We use these queries to define the mappings of the system as follows1: (i) for each atomic concept A and each h`; hi 2 range(A), we add the mapping ` idx h(TC ) ; A(c1); (ii) for each atomic role P and each h`; hi 2 range(P ), we add the mapping ` idx h(TR) ; P (c1; c2); (iii) for each pair of atomic roles P , P 0 such that T j= P 0 v P and each h`; hi 2 range(P 0) we add the mapping ` idx h(TR) ; P (c2; c1); (iv) for each atomic concept A, each atomic role P s.t. T j= 9P v A (resp., 9P v A) and each h`; hi 2 range(P ), we add the mapping ` idx h(TR) ; A(c1) (resp., ` idx h(TR) ; A(c2)); (v) last, we replace any pair of mappings ` idx h(TC ) ; A(c1) and `0 idx h0 (TC ) ; A(c1) such that `0 h and ` h0 by the mapping min(`;`0) idx max(h;h0)(TC ) ; A(c1) (similarly for role mappings).
A semantic index can be trivially constructed by assigning to each concept and role a unique (arbitrary) value and a set of ranges that covers all the values of their subsumees. However, this is not effective for optimizing query answering since the size of M determines exponentially the size of the final SQL query. To avoid an exponential blow-up, we create hidx ; rangei using the implied concept and role hierarchy as follows.
Let T be a TBox, and DC the minimal DAG that represents the implied is-a relation between all atomic concepts of T (i.e., the transitive reducts of the concept hierarchy)2. Then we can construct idx by initializing a counter i = 0, and visiting the nodes in DC in a depth-first fashion starting from the root nodes. At each step and given the node N visited at that step, if idx (N ) is undefined, set idx (N ) = i and i = i+1, else if idx (N ) is defined, backtrack until the next node for which idx is undefined. Now, to generate range we visit the nodes in DC starting from the leafs and going up. For each node N in the visit, if N is a leaf in DC , then we set range(N ) = fhidx (N ); idx (N )ig, and if N is not a leaf, then we set range(N ) = merge(fhidx(N ); idx(N )ig [ SNi j Ni!N2DC range(Ni)), where merge is a function that, given a set r of ranges, returns the minimal set r0 of ranges that has equal coverage as r, e.g., merge(fh5; 7i; h3; 5i; h9; 10ig) = fh3; 7i; h9; 10ig. We proceed exactly in the same way with the DAG DR representing the role hierarchy. Example 3. Let A, B, C, D be atomic concepts, let R, S, M be atomic roles, and consider the TBox T = fB v A; C v A; C v D; D v 9R; 9R v D; S v R; M vRg. Let the DAGs DC and DR for T be the ones depicted in Fig. 1. The technique generates idx and range as indicated in Fig. 1, generates the mappings in Fig. 3, and for any ABox, the technique generates a virtual ABox V that satisfies all the dependencies in Fig. 2. Then, we will have that in query answering, rewriting is only necessary w.r.t. D v 9R, which would be the output of optim(T ; ).
Our evaluation of the semantic index technique, described in [
In this paper we focused on issues of redundancy and performance in OBDA systems. Several directions can be taken starting from the ideas presented here. First, although 1 Here we use relational algebra expressions instead of SQL to simplify the exposition. 2 We assume w.l.o.g. that T does not contain a cyclic chain of basic concept or role inclusions.
Under such an assumption DC is unique. 1, f(1; 3)g
A 4, f(3; 4)g
D 1 idx 3(TC ) ; A(c1) 2 idx 2(TC ) ; B(c1) 3 idx 3(TC ) ; C(c1) 3 idx 4(TC ) ; D(c1) 5 idx 7(TR) ; R(c1; c2) 6 idx 6(TR) ; S(c1; c2) 7 idx 7(TR) ; M (c1; c2) 5 idx 7(TR) ; D(c1)
TBox pre-processing is the best place to first address redundancy, it is also necessary to
apply redundancy elimination during reasoning, e.g., during query rewriting. Second,
redundancy may also appear during consistency checking, i.e., when an ABox is sound
w.r.t. to the TBox; this can also be characterized with dependencies. With respect to
evaluation, in [