The DL-Lite family of description logics [
The most common approach to query answering in DL-Lite is through query rewriting. This approach consists of computing a so-called perfect rewriting of the query with respect to a TBox: the perfect rewriting of a query q for a TBox T is a query q0 that can be evaluated on the ABox only and produces the same results as if q were evaluated on both the TBox and the ABox. This approach is particularly interesting in DL-Lite, because, for every UCQ q, query q0 can be expressed in first-order logic (i.e., SQL), therefore query answering can be delegated to a relational DBMS, since it can be reduced to the evaluation of an SQL query on the database storing the ABox.
The shortcoming of the query rewriting approach is that the size of the rewritten
query may be exponential with respect to the size of the original query. In particular,
this is true when the rewritten query is in disjunctive normal form, i.e., is an UCQ. On
the other hand, [
However, it turns out that the disjunctive normal form is necessary for practical applications of the query rewriting technique, since queries of more complex forms, once translated in SQL, produce queries with nested subexpressions that, in general, cannot be evaluated efficiently by current DBMSs. So, while in some cases resorting to more compact and structurally more complex perfect rewritings may be convenient, in general this strategy does not solve the problem of arriving at an SQL expression that can be effectively evaluated on the database.
In this scenario, a very interesting way to limit the size of the rewritten UCQ has
been presented in [
As explained in [
In this paper, we present an approach that follows the ideas of [
This paper is an extended abstract of [
We assume the reader is familiar with the basics of DLs as well as with DL-LiteA [
Given an ABox A, we denote by IA the DL-LiteA interpretation such that, for every concept instance assertion C(a), aI 2 CI iff C(a) 2 A, for every role instance assertion R(a; b), haI ; bI iI 2 RI iff R(a; b) 2 A, and for every attribute instance assertion U (a; b), haI ; bI iI 2 U I iff U (a; b) 2 A.
A conjunctive query (CQ) q is an expression of the form q(x) 1; : : : ; n, where x is a tuple of variables, and every i is an atom whose predicate is a concept name or a role name or an attribute name, and whose arguments are either variables or constants, such that every variable occurring in x also occurs in at least one i. The variables occurring in x are called the distinguished variables of q, while the variables occurring in some i but not in x are called the existential variables of q. The predicate q is called the predicate of the query, and the number of elements of x is called the arity of q. A CQ is a Boolean CQ if it has no distinguished variables.
A union of conjunctive queries (UCQ) Q is a set of conjunctive queries of the same arity and having the same query predicate. A UCQ Q is a Boolean UCQ if every CQ belonging to Q is Boolean.
Given a CQ q of arity n, we denote by q(c) the Boolean CQ obtained from q by replacing the distinguished variables in x with the constants in the n-tuple of constants c. Given a CQ q of arity n, the evaluation of q in I, denoted by eval(q; I), is the set of n tuples of constants c such that I satisfies the first-order sentence q(c). The evaluation of a UCQ Q in I, denoted by eval(Q; I), is the set Sq2Q eval(q; I). The set of certain answers to a UCQ Q over a DL-LiteA ontology hT ; Ai, denoted by cert (Q; hT ; Ai), is the set of tuples TI2Mod(hT ;Ai) eval(Q; I).
Given a UCQ Q and a TBox T , a UCQ Q0 is a perfect rewriting of Q with respect to
T if, for every ABox A such that hT ; Ai is consistent, cert (Q; hT ; Ai) = eval(Q; IA).
The above notion of perfect rewriting immediately extends to any query language for
which the evaluation eval of queries on a first-order interpretation is defined. We remark
that many algorithms are available to compute perfect rewritings in DL-Lite logics (e.g.,
[
In the following, for ease of exposition, we will not consider attributes in DL-LiteA ontologies. However, all the algorithms and results that we present in this paper can be immediately extended to handle attributes (since attributes can essentially be treated in a way analogous to roles). 3
We now define the notion of EBox, which constitutes a set of extensional constraints,
i.e., constraints over the ABox. The idea of EBox has been originally introduced in [
The following definitions are valid for every DL, under the assumption that the assertions are divided into extensional assertions and intensional assertions, and extensional assertions correspond to atomic instance assertions.
Given a set of intensional assertions N and an interpretation I, we say that I satisfies N if I satisfies every assertion in N .
An extensional constraint box, or simply EBox, is a set of intensional assertions. Notice that, from the syntactic viewpoint, an EBox is identical to a TBox. Therefore, entailment of an assertion with respect to an EBox E (denoted by E j= ) is defined exactly in the same way as in the case of TBoxes.
Given an ABox A and an EBox E , we say that A is valid for E if IA satisfies E . Definition 1. (Admissible ABox) Given a TBox T and an EBox E , an ABox A is an admissible ABox for T and E if A is consistent with T and A is valid for E . We denote with ADM(T ; E ) the set of ABoxes A that are admissible for T and E .
Informally, an EBox acts as a set of integrity constraints over the ABox. Differently
from other recent approaches that have proposed various forms of integrity constraints
for DL ontologies (e.g., [
We are now ready to define the notion of perfect rewriting in the presence of both a TBox and an EBox.
Definition 2. (Perfect rewriting in the presence of an EBox) Given a TBox T , an EBox E , and a UCQ Q, a FOL query is a perfect rewriting of Q with respect to hT ; E i if, for every ABox A 2 ADM(T ; E ), hT ; Ai j= Q iff IA j= .
The above definition establishes a natural notion of perfect rewriting in the presence of an EBox E . Since E constrains the admissible ABoxes, the more selective is E (for the same TBox T ), the more restricted the set ADM(T ; E ) is. If for instance, E ; E 0 are two EBoxes such that E E 0, we immediately get from the above definitions that ADM(T ; E ) ADM(T ; E 0). Now, let Q be a UCQ, let be a perfect rewriting of Q with respect to hT ; E i and let 0 be a perfect rewriting of Q with respect to hT ; E 0i: will have to satisfy the condition hT ; Ai j= Q iff IA j= for more ABoxes A than query 0. Consequently, will have to be a more complex query than 0. Therefore, larger EBoxes in principle allow for obtaining simpler perfect rewritings.
As already explained, the goal of this paper is to use extensional constraints to optimize query rewriting in DL-LiteA. An intuitive explanation of how extensional constraints allow for simplifying query rewriting can be given by the following very simple example. Suppose we are given a TBox fStudent v Persong, an empty EBox E0, and an EBox E1 = fStudent v Persong. Now, given a query q(x) Person(x), a perfect rewriting of this query with respect to hT ; E0i is the UCQ fq(x) Person(x) q(x) Student(x)g, while a perfect rewriting of query q with respect to hT ; E1i is the query q itself. Namely, under the EBox E1 we can ignore the TBox concept inclusion Student v Person, since it is already satisfied by the ABox.
However, as already explained in [
The example above shows that we need to understand under which conditions we are allowed to use extensional constraints to optimize query rewriting. 4
Prexto
In this section we present the algorithm Prexto (Perfect Rewriting under EXTensional
cOnstraints). Prexto makes use of the algorithm Presto, originally defined in [
UCQ Q with respect to a DL-LiteA TBox T . The algorithm Presto is reported in
Figure 1. We refer the reader to [
B OA-predicate p2 , where the superscript represents the arity of the predicate (actually,
R
to handle Boolean subqueries, also 0-ary OA-predicates, i.e., predicates with no
arguments, are defined: we refer the reader to [
In the following, we modify the algorithm Presto. In particular, we make the following changes. First, the final for each cycle of the algorithm (cf. Figure 1) is not executed: i.e., the rules defining the OA-predicates are not added to the returned program. Second, the algorithm DeleteRedundantAtoms is modified to take into account the presence of disjointness assertions and role functionality assertions in the TBox. More precisely, the following simplification rules are added to algorithm DeleteRedundantAtoms(Q0; T ) (in which we denote basic concepts by B; C, role names by R; S, and datalog rules by the symbol r): 1. if p2R(t1; t2) and p2S (t1; t2) occur in r and T j= R v :S, then delete r from Q0; 2. if p1B(t) and p1C (t) occur in r and T j= B v :C, then delete r from Q0; 3. if p2R(t1; t2) and p1C (t1) occur in r and T j= 9R v :C, then delete r from Q0; 4. if p0 and p0 occur in r and T j= 0 v : 0, then delete r from Q0; 5. if p1B(t) and p0 occur in r and T j= B0 v : 0, then delete r from Q0; 6. if p2R(t1; t2) and p0 occur in r and T j= R0 v : 0, then delete r from Q0;
Input: UCQ Q, DL-LiteA TBox T , DL-LiteA EBox E Output: UCQ Q0 begin
P = Presto(Q; T ); P 0 = ;; for each OA-predicate PR2 occurring in P do
= MinimizeViews(R; E; T ); P 0 = P 0 [ fp2B(x; y) S(x; y) j S is a role name and S 2 g
[ fp2B(x; y) S(y; x) j S is a role name and S 2 g; for each OA-predicate PB1 occurring in P do
= MinimizeViews(B; E; T ); P 0 = P 0 [ fp1B(x) C(x) j C is a concept name and C 2 g
[ fp1B(x) R(x; y) j 9R 2 g [ fp1B(x) R(y; x) j 9R for each OA-predicate PN0 occurring in P do
= MinimizeViews(N 0; E; T ); P 0 = P 0 [ fp0N C(x) j C is a concept name and C0 2 g
[ fp0N R(x; y) j R is a role name and R0 2 g; P 00 = P [ P 0; Q0 = Unfold(P 00); Q0 = DeleteRedundantAtoms(Q0; E); return Q0 end 7. if p2R(t1; t2) and p2R(t1; t02) (with t2 6= t02) occur in r and (funct R) 2 T , then, if t2 and t02 are two different constants, then delete r from Q0; otherwise, replace r with the rule (r), where is the substitution which poses t2 equal to t02.
Analogous simplification rules (which can be immediately derived) hold when R; S are inverse roles in cases 1, 3 and 7.
Example 1. Let us show the effect of the new transformations added to DeleteRedundantAtoms through two examples. First, suppose T = fB v :B0; (funct R)g and suppose r is the rule q(x) p1B(y); p2R(x; y); p2R(x; z); p1B0 (z). First, the above rule 7 of algorithm DeleteRedundantAtoms can be applied, which transforms r into the rule q(x) p1B(y); p2R(x; y); p1B0 (y). Then, the above rule 2 of algorithm DeleteRedundantAtoms can be applied, hence this rule is deleted from the program. Intuitively, this is due to the fact that this rule looks for elements belonging both to concept B and to concept B0, which is impossible because the disjointness assertion B v :B0 is entailed by the TBox T . Therefore, it is correct to delete the rule from the program.
From now on, when we speak about Presto we refer to the above modified version of the algorithm, and when we speak about DeleteRedundantAtoms we refer to the above modified version which takes into account disjointness and functionality assertions.
The Prexto algorithm is defined in Figure 2. The algorithm is constituted of the following four steps: Algorithm MinimizeViews(B; E; T ) Input: basic concept (or basic role, or 0-ary predicate) B,
Output: set of basic concepts (or basic roles, or 0-ary predicates) 00 begin = fB0 j T j= B0 v Bg; 0 = ;; for each B0 2 do if there exists B00 2 then 0 = 0 [ fB0g; 00 = 0; while there exist B; B0 2 do 00 = 00 fB0g; return 00 end such that E j= B0 v B00 and E 6j= B00 v B0
0 such that B 6= B0 and E j= B v B0 and E j= B0 v B
Notice that the bottleneck of the whole process is the above step 3, since the number of conjunctive queries generated by the unfolding may be exponential with respect to the length of the initial query Q (in particular, it may be exponential with respect to the maximum number of atoms in a conjunctive query of Q). As shown by the following example, the usage of extensional constraints done at step 2 through the MinimizeViews algorithm is crucial to handle the combinatorial explosion of the unfolding. Example 2. Let T be the following DL-LiteA TBox:
isBestFriendOf v knows (funct isBestFriendOf) (funct isBestFriendOf )
Moreover, let E1; : : : ; E4 be the following concept inclusions:
E1 = FulltimeStudent v StudentWithGrant E2 = 9receivesGrantFrom v StudentWithGrant E3 = HasJob v Employee E4 = Manager v Employee and let E1 = fE1g; E2 = fE1; E2g; E3 = fE1; E2; E3g; E4 = fE1; E2; E3; E4g . Finally, let q0; q1; q2; q3 be the following simple queries: q0(x) q1(x) q2(x) q3(x)
Let us focus on query q1 and let us consider the empty EBox. In this case, during the execution of Prexto(q1; T ; ;) the algorithm MinimizeViews simply computes the subsumed sets of Student, knows, HasJob, which are, respectively:
MinimizeViews(Student; ;; T ) =
fStudent; FulltimeStudent; StudentWithGrant; 9receivesGrantFromg MinimizeViews(knows; ;; T ) = fknows; isBestFriendOf g
MinimizeViews(HasJob; ;; T ) = fHasJob; Employee; Manager; 9givesHighSalaryTo g Since two sets are constituted of four predicates and one is constituted of two predicates, the UCQ returned by the unfolding step in Prexto(q1; T ; E ) contains 32 CQs. This is also the size of the final UCQ, since in this case no optimizations are computed by the algorithm DeleteRedundantAtoms, because both the disjointness assertion and the role functionality assertions of T have no impact on the rewriting of query q1.
Conversely, let us consider the EBox E4: during the execution of Prexto(q1; T ; E ), we obtain the following sets from the execution of the algorithm MinimizeViews:: MinimizeViews(Student; E4; T ) = fStudent; StudentWithGrantg MinimizeViews(knows; E4; T ) = fknows; isBestFriendOf g
MinimizeViews(HasJob; E4; T ) = fEmployee; 9givesHighSalaryTo g Thus, the algorithm MinimizeViews returns only two predicates for Student and only two predicates for HasJob. Therefore, the final unfolded UCQ is constituted of 8 CQs (since, as above explained, the final call to DeleteRedundantAtoms does not produce any optimization).
It is possible to prove correctness of Prexto [
Theorem 1. Prexto(Q; T ; E ) runs in polynomial time with respect to the size of T [ E , and in exponential time with respect to the maximum number of atoms in a conjunctive query in the UCQ Q.
algorithm E = ; E = E1 E = E2 E = E3 E = E4 Presto+unfolding 4 4 4 4 4
TBox-min 4 4 4 4 4 Prexto-noEBox 4 4 4 4 4 Prexto-noDisj 4 3 2 2 2
Prexto-full 4 3 2 2 2 Presto+unfolding 32 32 32 32 32
TBox-min 32 32 32 32 32 Prexto-noEBox 32 32 32 32 32 Prexto-noDisj 32 24 16 12 8
Prexto-full 32 24 16 12 8 Presto+unfolding 256 256 256 256 256
TBox-min 256 256 256 256 256 Prexto-noEBox 224 224 224 224 224 Prexto-noDisj 256 144 64 48 32
Prexto-full 224 126 106 42 28 Presto+unfolding 2048 2048 2048 2048 2048
TBox-min 2048 2048 2048 2048 2048 Prexto-noEBox 1584 1584 1584 1584 1584 Prexto-noDisj 2048 864 256 192 128
Prexto-full 1584 708 188 141 94
We now compare the optimizations introduced by Prexto with some of the current
techniques for query rewriting in DL-Lite. In particular, we consider the simple DL-LiteA
ontology of Example 2 and compare the size of the UCQ rewritings generated by the
original Presto algorithm, the rewriting based on the TBox minimization technique
TBox-min shown in [
The table reported in Figure 4 shows the impact on rewriting queries q0, q1, q2 and
q3 of: (i) the disjointness axiom and the functional role axioms in T ; (ii) the EBoxes
E1; : : : ; E4. In the table, we denote by Presto+unfolding the UCQ obtained by
unfolding the nonrecursive datalog program returned by the Presto algorithm, and denote by
TBox-min the execution of Presto+unfolding which takes as input the TBox
minimized by the technique presented in [
The results of Figure 4 clearly show that even a very small number of EBox axioms may have a dramatic impact on the size of the rewritten UCQ, and that this is already the case for relatively short queries (like query q2): this behavior is even more apparent for longer queries like q3. In particular, notice that, even when only two extensional inclusions are considered (case E = E2), the minimization of the UCQ is already very significant. Moreover, for the queries under examination, extensional inclusions are more effective than disjointness axioms and role functionalily axioms on the minimization of the rewriting size.
The results also show that the technique presented in [
Finally, we remark that the above simple example shows a situation which is
actually not favourable for the algorithm, since there are very few extensional constraints
and short (or even very short) queries: nevertheless, the experimental results show that,
even in this setting, our algorithm is able to produce very significant optimizations.
Indeed, the ideas which led to the Prexto algorithm came out of a large OBDA project
that our research group is currently developing with an Italian Ministry. In this project,
several relevant user queries could not be executed by our ontology reasoner (Quonto
[
In this paper we have presented a query rewriting technique for fully exploiting the presence of extensional constraints in a DL-LiteA ontology. Our technique clearly proves that extensional constraints may produce a dramatic improvement of query rewriting, and consequently of query answering over DL-LiteA ontologies.
We believe that the present approach can be extended in several directions. First, it
would be extremely interesting to generalize the Prexto technique to ontology-based
data access (OBDA), where the ABox is only virtually specified through declarative
mappings over external data sources: as already mentioned in the introduction, in this
scenario extensional constraints would be a very natural notion, since they could be
automatically derived from the mapping specification. Then, it would be very
interesting to extend the usage of extensional constraints beyond DL-LiteA ontologies: in this
respect, a central question is whether existing query rewriting techniques for other
description logics (e.g., [
Acknowledgments This research has been partially supported by the ICT Collaborative Project ACSI (Artifact-Centric Service Interoperation), funded by the EU under FP7 ICT Call 5, 2009.1.2, grant agreement n. FP7-257593.