In OBDA systems, cached rewritings can be used to signi cantly shorten the process of nding rewritings of bigger queries. The main challenge in using cached rewritings is nding the optimal combination to apply, a problem which is NP-complete. In this paper, we present a way to calculate the value of a cached rewriting, and propose using this value to decide which cached rewritings to apply. The idea behind our technique is to estimate how much computation, in particular optimization, has gone into the rewriting. This can tell us something about which cached rewritings we should prioritise, and also when to cache a rewriting. In order to quantify optimization, we de ne a measure of UCQs, and calculate this measure at di erent stages of the rewriting.
Ontology-based data access (OBDA) [
The usual way of answering a query over the ontology in the OBDA
framework [
In this paper, we therefore study the following problem: Given a query Q to answer and a set of cached rewritings of previous queries, how useful is each cached rewriting likely to be, if it is applicable to Q? Knowing this, the system can make sensible decisions as to which cached rewritings to try and apply, and in what order.
As a measure of the usefulness of an existing cached rewriting, previous work
by Di Pinto et al. [
In this section, we de ne basic notions related to OBDA systems and their components: databases, ontologies, and mappings. We then give a de nition of query rewriting and unfolding, followed by a formal de nition of cached query rewritings as mappings that possess speci c properties. 2.1
In this paper, we assume a xed relational schema S, and adopt the standard
notions for conjunctive queries (CQs) over S [
Given a conjunctive query Q and a tuple of constants t, we write Q[t] for the query obtained by replacing the free variables of Q with the constants in t. Given a database instance D and a query Q, we write ans(Q; D) for the set of answers to Q over D, de ned in the standard way. 2.2
An ontology is a description of a domain of interest in some formal language. Here, we consider the languages of Description Logics (DLs). In general, an ontology expressed in a description logic is a pair O = hT ; Ai, where the TBox T contains axioms specifying universal properties of the concepts and roles in the domain, while the ABox A speci es instances of concepts and roles. In the OBDA setting, the ABox is given by mappings rather than explicitly, and so the TBox is the only relevant component. We therefore set O = T .
In the examples discussed in this paper, we will use the description logic
DL-LiteA [
E !
(U ) F ! T1 j : : : j Tn V ! U j :U where A is a concept name, P is a role name, U is an attribute name, and T1; : : : ; Tn are value-domains. We let O be a set of ontology predicates, and
C a set of constants. The semantics of DL-LiteA is de ned in terms of rstorder interpretations I = ( I ; I ) over O [ C . The non-empty domain I is the union of the disjoint sets V and IO, where V is the domain for interpreting data values, and IO is the domain for interpreting object constants. The interpretation function I is de ned as follows:
AI P I U I
I O I O I O
I O
V (:B)I =
IO n BI (:Q)I = ( IO
IO) n QI (:U )I = ( IO
V ) n U I (P )I = f(o; o0) j 9v:[(o0; o) 2 P I ]g (9Q)I = fo j 9o0:[(o; o0) 2 QI ]g ( (U ))I = fo j 9v:[(o; v) 2 U I ]g ( (U ))I = fv j 9o:[(o; v) 2 U I ]g: A DL-LiteA TBox T is a nite set of axioms of the form
B v C
Q v R
E v F
U v V (funct Q) (funct U ): The interpretation I satis es an axiom X v Y if XI Y I . I satis es (funct Z) if for every o; o0; o00 2 IO, if (o; o0) 2 ZI and (o; o00) 2 ZI , then o0 = o00. 2.3
In the general case, a mapping assertion m between a database schema S and
an ontology O has the form Q q, where the body Q is a CQ over S, and the
head q a CQ over the vocabulary of O [
An OBDA system speci cation is a triple B = hO; S; Mi where S is a database schema, M a set of mapping assertions, and O an ontology. The semantics of query answering in OBDA systems are usually de ned using rst-order interpretations.
De nition 1 (OBDA semantics). Let B = hO; S; Mi be an OBDA system speci cation, and D a database for S. A rst order interpretation I with I j= D is a model for B if { I j= O, and { for every tuple of constants t from D, and every mapping assertion Q q 2 M, we have that I j= q[t] whenever I j= Q[t].
The set of answers to a query q over B and D is the set of tuples t from D such that q[t] is true in every model of B and D. We write ans(q; B; D) for the answers to q over B and D.
As mentioned in the introduction, answering a query in an OBDA system is usually done by rewriting and unfolding the query into the correct database queries to execute.
De nition 2 (Rewriting and unfolding). Let B = hO; S; Mi be an OBDA system speci cation, and q a CQ over the vocabulary of O. A rewriting of q under B is a query q0 over the same vocabulary such that ans(q0; h;; S; Mi; D) = ans(q; B; D) for every database instance D.
An unfolding of the rewriting q0 of q is a query Q over S such that ans(Q; D) = ans(q; B; D) for every database instance D.
We can now de ne the notion of a perfect mapping assertion, which captures the idea of caching the rewriting and unfolding of a query.
De nition 3 (Perfect mapping assertion [
Each cached rewriting and unfolding is a perfect mapping assertion. In
fact, caching is one of the primary methods for obtaining perfect mapping
assertions [
As part of their full OBDA rewriting algorithm, Di Pinto et al. [
Given a conjunctive query q, ReplaceSubqueryR goes through the perfect
mapping assertions in the order speci ed by some heuristic, modifying q
whenever the perfect mapping assertion is applicable. The order of application
is signi cant, since the application of one perfect mapping assertion can prohibit
the subsequent application of another. Finding the optimal combination of
perfect mapping assertions to apply is NP-hard [
Our goal is to de ne an improved heuristic for the order of application of perfect mapping assertions.
The following example, based on one of the challenges faced by the Optique project1, shows how we create perfect mapping assertions.
Example 4. Let company(name; owner; manager; accountant) be a database table. We de ne the concepts Company and Owner, M anager and Accountant, and the roles hasOwner, hasM anager, and hasAccountant. We de ne the TBox, 9hasOwner v Company;9
> 9hasM anager v Company;= ; >: 9hasAccountant v Company ;> and mapping assertions 8> 9y; z; w:company(x; y; z; w) >> 9z; w:company(x; y; z; w) M = < > 9y; w:company(x; y; z; w) > > : 9y; z:company(x; y; z; w)
Company(x) hasOwner(x; y) hasM anager(x; z) > > hasAccountant(x; w);> 9 > > > = :
We now look at the query q(x) = Company(x). The ontology rewriting of Company(x) is q0(x) = Company(x) _ 9v:hasOwner(x; y)
_ 9v:hasM anager(x; y) _ 9v:hasAccountant(x; y): When unfolding q0(x) we get the UCQ which is obviously equivalent to 9y; z; w:company(x; y; z; w) _ 9v; z; w:company(x; v; z; w) _ 9y; v; w:company(x; y; v; w) _ 9y; z; v:company(x; y; z; v); 9y; z; w:company(x; y; z; w): We cache this rewriting by saving the perfect mapping assertion 9y; z; w:company(x; y; z; w)
Company(x):
Example 4 illustrates one situation where perfect mapping assertions are
useful. An alternative way of dealing with his particular example is by modifying
the set M of mapping assertions according to the TBox [
In order to evaluate the quality of a perfect mapping assertion, we need some way of measuring a UCQ. We will use this measure to quantify the amount of optimization that has gone into creating a perfect mapping assertion.
There are several ways to measure the size of a conjunctive query. For ease of exposition, we will use the number of atoms in the query in our examples, although the number of variables is usually more relevant to the exact cost of optimising a query, since query optimisation amounts to nding homomorphisms between queries. If the number of variables is approximately linear in the number of atoms, the results of using either will be similar.
Furthermore, the number of atoms in each conjunction of the unfolding of a conjunctive query can be approximated from the number of mapping assertions that mentions conjunct. On the other hand, nding the number of variables requires an analysis of each mapping assertion.
The size of a UCQ is harder to describe with a single number, because UCQs have two dimensions: the conjunctions and the conjuncts in them. De nition 5 (Measure of UCQs). Let Q = CQ1 _ : : : _ CQk be a UCQ, size(CQi) the size (e.g. number of atoms) of CQi, and f a weighting function. De ne g(x) = x if f is at most linear, and g = f 1 otherwise. The measure of Q is
SQ = g k ! X f (size(CQi)) : i=1
The function f de nes how SQ depends on the size of the conjunctive queries, the function g makes SQ at most linear in the sum of the sizes. Our choice of g will make SQ of the order O(k maxi[size(CQi)]), where, and k is the number of conjunctive queries in the UCQ. We choose f according to the following observations.
{ f constant: We disregard the size of disjuncts. The cost of performing optimizations is assumed to be insigni cant compared to the cost of rewriting, unfolding and storing the query. { f linear: The cost of optimization is assumed to be on the same order as the cost of rewriting, unfolding and storing the query. { f polynomial or exponential: The cost of optimization is assumed to be more important than the cost of rewriting, unfolding and storing the query.
The above list is explains how di erent de nitions of f a ects the measure SQ. It gives a strong indication of how we should de ne f , depending on what we want to use the measure SQ for. In Sections 5 and 6, we will use linear f . We get back to the choice of f brie y in Section 7.
Having de ned a measure for UCQs, we are now in a position to assign a value to the body Q of a perfect mapping assertion Q q. Such an analysis gives us some information about how much we stand to gain by applying this perfect mapping assertion. We can, however, get an even better picture by looking at the process of rewriting q. Doing this, we can get a measure of how complex q really is in the relevant OBDA system.
De nition 6 (Maximal expansion). Let q be a query, B = hO; S; Mi an OBDA system speci cation, and R an ontology rewriting algorithm. The maximal expansion of q over B and R, denoted me(q; B; R), is the unoptimised ontology rewriting and unfolding of q over B using R.
We write me(q; B) when the choice of R is clear from the context. When the OBDA system is also understood from the context, we let Sme(q) denote the measure of me(q; B). The following example shows how we calculate Sme(q). Example 7. We look at an OBDA system speci cation with TBox axioms A v 9R and S v T , and the mapping
M = 8 QA1 > >>< QR1 > QS1 > >: QT1
A; QA2 R; QR2 S; QS2 T; QT2
A; QA3 R; QR3 S; T; QT3
A;
R; QR4 T 9 > R;>=> > > > ; and rewrite the query q(x; y) = 9z:R(x; z) ^ T (x; y). The ontology rewriting of q according to rewriting algorithm R is q0(x; y) = [9z:R(x; z) ^ T (x; y)] _ [9z:R(x; z) ^ S(x; y)]
_ [A(x) ^ T (x; y)] _ [A(x) ^ S(x; y)] We choose f (x) = g(x) = x, let size(CQ) be the number of atoms in CQ, and calculate Sme(q). If each QXn is a query without joins, then the resulting maximal expansion is a UCQ with joins of size 2. The rst disjunct in q0 is unfolded into 12 conjunctive queries of size 2, since there are four queries mapped to R and 3 to T . We do similar calculations with each disjunct of q0, and end up with a total of 35 conjunctive queries, each of size 2. Therefore Sme(q) = 70.
In Example 7, we assumed that there were no con icts between mapping assertions during the unfolding. Such con icts can arise when there the mapping assertions contain constants in place of some variables. In this case, only those mapping assertions that have constants replacing the same variables can create con ict, and this will usually only be the case for a very few combinations of assertions. If constants are common in the used mapping assertions, then greater care must be taken when using approximations of Sme(q).
With a measure for UCQs and the notion of maximal expansions, we are now
in a position to expand on the heuristic suggested by Di Pinto et al. [
For a perfect mapping assertion Q q, we calculate the measures Sq, SQ and Sme(q). Note that Sq = size(q), since q is a conjunctive query.During both ontology rewriting and unfolding, the size of a conjunctive query can grow exponentially. In both cases there is generally multiple options for dealing with every conjunct, and the result is a very large UCQ. For this reason, we will use log SQ and log Sme(q), since they will be approximately proportional to Sq. We also calculate the ratio log Sme(q)= log SQ, which tells us how much optimisation has gone into the creation of the perfect mapping assertion. We use this optimization ratio to adjust other measures of the value of the perfect mapping assertion.
If Sq is large for a perfect mapping assertion Q q, that is, the size of q is large, then applying it cuts a large portion of the original query. There is, however, a risk that this portion could be rewritten directly without much di culty. In order to compensate for this e ect, we scale Sq by the optimisation ratio log Sme(q)= log SQ.
A perfect mapping assertion is also valuable if the corresponding Sme(q) is large, no matter the size of Sq. Again, we scale log Sme(q) by the optimisation ratio log Sme(q)= log SQ.
Assigning a weight parameter to each of these compound measures, we get the heuristic a (log Sme(q))2 log SQ + b Sq log Sme(q) + cSq
log SQ
We assume Sq, log SQ and log Sme(q) have the same units, since they are all approximately linear in the size of the head q of the perfect mapping assertion Q q. Then, the unit of each term in the above sum is the same, and also approximately linear in the size(q). This means that the ratio between the terms will be fairly stable in respect to typical query size, and as such, the tuning of the parameters a, b, and c will not be very sensitive to the typical query size. Example 8. We look at an ontology with an empty TBox, and the four roles R1, R2, R3, and R4. We de ne the set of mapping assertions
j M = fQi
Ri j j = 1; : : : ; i2g; where i = 1; : : : ; 4. We let size(CQ) be the number of atoms in CQ, and assume that each Qij is atomic. We let f (x) = x, and calculate Sq and Sme(q) for di erent conjunctions of Ri, with each role occurring at most once in each query. The results are shown in Table 1. We see that Sme(q) gives us a much ner division than Sq, which only divides the queries into 3 groups. Given the query
R1(x1; x2) ^ R2(x2; x3) ^ R3(x3; x4) ^ R4(x4; x5); and the perfect mapping assertions there is a good chance that our best option is to apply the second, shorter perfect mapping assertion, because the maximal expansion of R3(x3; x4) ^ R4(x4; x5) is so large. In order to be more precise, we would need to obtain the measures SQA and SQB .
R1 R1 R1 R2
R1 R1 R1 R2 R2 R3 R2 R2 R3 R3 q R1 R2 R3 R4 R2 R3 R4 R3 R4 R4 R3 R4 R4 R4
Sq 1 1 1 1 2 2 2 2 2 2 3 3 3 3
Sme(q) 1 4 9 16 8 18 32 72 128 288 108 192 432 1728
Di Pinto et al. [
We suggest the heuristic a (log Sme(q))2 + b Sq log Sme(q) + cSq
log SQ log SQ
If we let a = b = 0, c 6= 0, and de ne size(CQ) to be the number of atoms in
CQ, then our heuristic becomes the same as the one used in [
Since Sq, Sme(q), and SQ are relatively cheap to calculate or approximate
during rewriting, and cheap to store in a cache, we claim our suggested heuristic,
in many settings, will outperform the simpler heuristic provided by [
We plan to continue this work by experimentally verifying our results. In particular, we would like to compare the di erent weighting and scaling functions discussed here on real-world datasets. Another line of enquiry would be to see how well these heuristics can substitute for e.g. techniques to eliminate mapping redundancy, as discussed in Section 3.